的适应性强的染色体。相应地取代下一代中适应性弱的染色体。 程序中精英策略由 keepBestParents 函数和 sortFiness 函数来实现。需要说明的是 sortFitness 仅仅对 种群的索引进行了排序。然后用父代中 20%的适应度较大的优秀染色体替换子代中 20%的适应性弱的 染色体。 6、变异操作 染色体的变异可以保持种群的多样性，防止最优解的丢失以及算法收敛到局部最优解。 变异操作由 mutation 函数实现。 首先产生一个介于 0 和 1 之间的随机数 prob，若 prob 小于 MP 则进行变异操作：随机产生一个位 置 partPos，然后变异前染色体的 partPos 位置的基因为 1，则变异为 0，否则变异为 1；相应地要进行适 应度和染色体容量的变化。 7、代际更新 代际之间的更新，即用新生成的种群代替取代旧的种群。这个操作在 updateGeneration 函数中实现， 同 时 这 个 操 作 使 用 了 前 面 提 及 的 精 英 策 略 。 实 际 上 ， 父 代 种 群 中 优 秀 的 染 色 体 已 被 保 留 ， updateGeneration 中只是用新种群中的优秀染色体来代替父代中的染色体。 由于对父代和子代的染色体都进行了排序，因此程序中将子代的 80％视作优秀，将父代中的前 20％ 视作优秀。 8、算法的终止 程序中采用了一个 HASH 表来对子代种群的适应度进行 HASH 操作。HASH 表中的头结点纪录了 头结点所指向的单链表的信息。如下代码中的注释： typedef struct Head{ int maxFitness; int Count; int Diff; HASHNODE *Next; //单链表中的最大的 Fitness //HASH 到该结点的染色体的数目 //单链表中有多少不同的 Fitness }HEAD; 用这样的一个 HASH 表结构可以只需遍历 HASH 表中的头结点，即可知当前的种群的适应度最大 的染色体是否集中。 具体地，如 checkFitness 函数中的下面几行代码： index = maxFitness(hashTable); double CPount = hashTable[index].Count/(double)POPSIZE; double pDiff = hashTable[index].Diff/(double)POPSIZE; if(CPount>=0.9 && pDiff<=0.1){ sameFlag = false; } 如果当前 maxFitness 最大的头结点满足 if 语句中的判断条件，则 sameFlag 置为真，即算法停止迭 代的条件得到了满足。 TraverseHashTable 函数则用于遍历 HASH 表。 算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为 1000。 四、实验结果。 试验中用到的物品的重量和价值分别存储于以下两个数组之中。 int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}; int Value[NUMG]={2,20,5,4,19,14,18,8,11,6}; 父代种群存储于 parentGenome[NUMG]中，子代种群存储于 nextGenome[NUMG]中。程序的初始状 态和结束状态如下面的表格所示： 

Weight 21 22 22 22 26 24 22 23 26 25 初始的种群 染色体中的基因 Value 52 23 40 53 45 53 53 25 48 29 初始的 HASH 表 0010110101 0011000101 0001100011 0100010110 1010011001 1100010011 0100010110 1011010000 1010110100 0111000000 头结点索引 maxFitness Count Diff 单链表中的结点内容 0 1 3 6 9 10 12 程序在运行了 16 次后停止运行。 52 53 29 45 48 23 25 1 4 1 1 1 1 1 1 2 1 1 1 1 1 停止时的种群 52: 53:40: 29: 45: 48: 23: 25: Weight 29 29 29 29 29 29 29 28 29 29 染色体中的基因 Value 78 78 78 78 78 78 78 64 78 78 停止时的 HASH 表 0100110111 0100110111 0100110111 0100110111 0100110111 0100110111 0100110111 0100100111 0100110111 0100110111 头结点索引 maxFitness Count Diff 单链表中的结点内容 0 12 78: 64: 78 64 9 1 1 1 即可知当前 01 背包问题的最优解为 X =｛0,1,0,0,1,1,0,1,1,1｝ 对应的最优值是 78，即当前能够装入背包的最大价值。