2。4。2 交叉

交叉操作是把两个父个体的部分遗传编码进行交叉重组以此生成了新的个体。这样 既产生了全新的个体又保留了部分上一代个体中的遗传信息。交叉重组操作极大程度上 提高了遗传算法的搜索能力。因此遗传算法能够搜索到最优解主要依靠交叉操作。

2。4。3 变异

交叉操作之后需要对子代进行一定概率的变异操作，变异通过较小概率的扰动对子 代的基因产生变动。变异操作是一种局部随机搜索，在选择与交叉操作适当配合下，确 保了遗传算法的有效性；同时变异操作使得遗传算法保持了种群的多样性，避免了非成 熟收敛的出现。

2。5 遗传算法的流程

图 2-2 流程图

是否满足优化准则的条件：

①种群中个体的最大适应度超过预先设定值[12]；

②种群中个体的平均适应度超过预先设定值[12]；

③世代数超过预先设定值。

第三章 遗传算法在背包问题中的应用

3。1 背包问题

背包问题（Knapsack problem），是一个典型的 NP 完全问题，无法用确定的计算公 式对其进行有效的计算求解。

背包问题的数学模型实际上是一个 0-1 规划问题[13]。假设有 n 个物件，用 a 分别表

示每一件物品的重量，用 c j 表示每一件物品的价值 j 1,, n ，背包所能承受的最大重 量为 b 。假设物件 j 被选人背包时，则定义变量 x j  1，否则 x j  0 。考虑 n 个物件的选

n n

择与否，这样就可以得到背包内物件的总重量为  a j x j  ，物件的总价值为 cj x j  ，怎

j 1 j 1

样决定变量 x j j 1,, n 的值（即确定一个物件组合）使背包内物件总价值为最大。这 个问题解的总组合数有 2n 个，其数学模型表示如下[9]：

Maximize

n

c jx j  ； (3-1)

j 1

Subject to

n

a jx j  b ； (3-2)

j 1

x j    0或1， j  1,, n 。 (3-3)

其中， c j , a j ,b 均为正值。

3。2 对背包问题的二进制编码

应用遗传算法求解背包问题，首先需要对其进行编码，一般使用二进制编码的方式， 使用 n 位二进制字符串表示一组 0-1 决策变量 x j j 1,, n ，这样就表示出一个个体的

遗传基因型。在这样的表示方法中，若第 j 位基因码是 1 时，则代表第 j 个物体被选择；

若第 j 位基因码是 0 时，则代表第 j 个物体不被选择，这就是基因对表现型的映射。例 如一个十维的背包问题，用二进制编码将个体表示成<0，1，1，0，0，1，0，1，0，1>， 则该个体的对应于选择了物件 2，3，6，8，10 放入背包。

3。3 控制参数的确定

基本的遗传算法运行参数包括：种群大小 P，个体编码长度 L，进化最大代数 iter， 交叉率 Pc，变异率 Pm 等。

种群大小：一般取 20~100； 个体长度：一般取 10~30；

进化最大代数：一般终止进化代数为 100~1000； 变异率：一般在 50%以上；

变异率：一般在 10%以下。 面对不同的问题，需要选取不同的控制参数，一般确定控制参数都是在一定的经验