中进行多次交叉操作。

3。7 变异算子的设计

尽管交叉操作已经完成了大部分搜索的操作，但遗传算法还不能以此就能实现进化 机制。因为交叉只是完成了种群内遗传基因的交流，并不能使得基因库出现优异的基因。 这就好比生物界的近亲繁殖。因为遗传算法中的种群是一个相对封闭的搜索群体，种群 中的基因型受到个体数量的限制，即使经过足够次数的交叉操作，种群中最好的个体也 只是来源于一个较好的祖先的子个体的基因，并且这样的良好基因型会逐渐充斥整个种 群，造成问题过早收敛，而此时种群中的最优个体并不是我们所要的全局最优解。变异 正是为了避免过早收敛而产生的，变异是在遗传过程中使一部分个体产生新遗传基因， 新遗传基因的加入使得种群基因库变得丰富起来，而不会造成近亲繁殖的出现。按照变 异概率历遍整个种群的基因码，敲定需要进行变异的基因，然后对其施以微小的扰动， 从而产生不同的基因。由于我们解决背包问题进行的基因编码是二进制编码，所以只要 将需要变异的基因码进行 0-1 变换，即将 1 换为 0，或是 0 换为 1 即可。

3。8 约束问题的处理

背包问题是含有不等式约束的优化问题，即放入背包中的物品的总重量要在背包的

所能承受的最大范围内，即  a j x j    b ，xj    0或1， j  1,, n 。对于约束最优化问题的

解法有两种：一种是把有约束问题化为无约束问题，再用无约束问题的方法去解；另一 种是改进无约束问题的方法，使之能用于有约束的情况[15]。利用罚函数是目前解决约束 问题的普遍方法。罚函数法的思想是在适应度函数中加入罚函数模块，所要加入的罚函 数与问题的约束要求相关。这样，加入罚函数的适应度函数就不需要考虑约束条件了。 按照以下形式将罚函数添加到对适应度的评价中：

式中，罚函数 P(x) 为满足下列条件的连续函数：

0, x X P(x) 0, x X

r 为罚函数尺度系数，也叫惩罚因子， r 0 。 X 为问题的可行解域。

(3-5)

根据罚函数解决背包问题，设计的适应度函数如下：

xj 0或1，j 1,, n，其中， c j , a j ,b 均为正值。 根据超出背包最大容量的程度对其进行的惩罚程度也不同，当选择放入背包的物品

的价值／重量比越高或者超出背包容量越大，则惩罚的越重。由于背包的容量是对问题 解作出了一个约束性的硬性要求，因此，我们可以将惩罚因子设定为一个较大的系数， 这样就能将可行解域与不可行解域严格地分开来，所有超出约束范围的解才会被彻底淘 汰掉。这样的适应度函数设计就可以符合解决背包问题的要求了。

3。9 精英保留策略

精英保留策略是遗传算法中常见的一种优化策略，这样做是为了避免种群中适应度 高的解的丢失。比如在选择操作阶段，个体被选中的概率是按照适应度的比例进行划分 的，尽管适应度高的个体被选中的概率越高，但是由于轮盘赌的随机性，还是有适应度 高的个体没有被选择的可能，为了避免适应度高的个体丢失的可能性事件的发生，我们 有必要进行精英保留策略。

即在进行轮盘赌选择之前，按照适应度由高到低进行排序，将排名在前一定名次的 个体进行保留处理，直接保留到下一代，进行后面的交叉操作。这样有效地保证了精英 解的传承。

同时，在每一代“选择-交叉-变异”结束，再次进行整个种群的适应度计算，并从 高到底进行排序，将最优的个体进行保留，并将这一个体与后代的最优个体进行比较， 如果有更优秀的个体，则替换之前的个体，这样就留下了目前为止最优秀的个体。文献综述