2023年8月1日发(作者：)

龙源期刊网

基于遗传算法解决01背包问题研究

作者：罗星星 谢兵 刘俊等

来源：《软件导刊》2014年第02期

摘要：遗传算法[1]属于进化算法（ Evolutionary Algorithms） 的一种，它通过模仿自然界的选择与遗传机理来寻找最优解。 遗传算法具有与问题领域无关且快速随机的搜索能力，搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，搜索使用评价函数启发，过程简单，使用概率机制进行迭代，具有随机性，具有可扩展性，容易与其它算法结合。基本01背包问题，提出遗传问题解决的关键技术，设计评价函数和遗传算子，并通过散播变异、移位变异、插入变异改进01背包问题中的遗传算法，很好地解决了遗传问题。

关键词关键词：遗传算法；01背包问题；评价函数；遗传算子

中图分类号：TP312文献标识码：A 文章编号：16727800（2014）002007402

1问题描述及解的遗传表示

1.1问题描述

01背包问题是一类基础的背包问题，可以具体描叙为一个体积为volume的背包和n个物体，对于物体i，其体积为vi，价值为wi，01背包问题就是要在不超过背包体积的情况下，使装入背包的物体价值量最大。

1.2问题解的遗传表示[2]

2遗传问题解决的关键技术

2.1设计评价函数，根据个体适应值对其进行优劣判定

采用经典的赌轮选择算法[3]，评价函数的功能是从群体中选择一个基因组，选中的几率正比于基因组的适应性分数。

3遗传问题解决的改进

可以设置适应性函数，记下每一代中最差的价值，然后对种群中每一个解得出的价值减去这个最差的价值，这样相对差异变大，接下来使用轮盘选择法，可有效地从种群中移去最差的染色体，因为最差的适应性分数为0[7，8]。改进的遗传算法可选择以下不同的变异算子[810]。

3.1散播变异

2023年8月1日发(作者：)

龙源期刊网

基于遗传算法解决01背包问题研究

作者：罗星星 谢兵 刘俊等

来源：《软件导刊》2014年第02期

摘要：遗传算法[1]属于进化算法（ Evolutionary Algorithms） 的一种，它通过模仿自然界的选择与遗传机理来寻找最优解。 遗传算法具有与问题领域无关且快速随机的搜索能力，搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，搜索使用评价函数启发，过程简单，使用概率机制进行迭代，具有随机性，具有可扩展性，容易与其它算法结合。基本01背包问题，提出遗传问题解决的关键技术，设计评价函数和遗传算子，并通过散播变异、移位变异、插入变异改进01背包问题中的遗传算法，很好地解决了遗传问题。

关键词关键词：遗传算法；01背包问题；评价函数；遗传算子

中图分类号：TP312文献标识码：A 文章编号：16727800（2014）002007402

1问题描述及解的遗传表示

1.1问题描述

01背包问题是一类基础的背包问题，可以具体描叙为一个体积为volume的背包和n个物体，对于物体i，其体积为vi，价值为wi，01背包问题就是要在不超过背包体积的情况下，使装入背包的物体价值量最大。

1.2问题解的遗传表示[2]

2遗传问题解决的关键技术

2.1设计评价函数，根据个体适应值对其进行优劣判定

采用经典的赌轮选择算法[3]，评价函数的功能是从群体中选择一个基因组，选中的几率正比于基因组的适应性分数。

3遗传问题解决的改进

可以设置适应性函数，记下每一代中最差的价值，然后对种群中每一个解得出的价值减去这个最差的价值，这样相对差异变大，接下来使用轮盘选择法，可有效地从种群中移去最差的染色体，因为最差的适应性分数为0[7，8]。改进的遗传算法可选择以下不同的变异算子[810]。

3.1散播变异