《算法的乐趣》第五十二节

本节介绍用遗传算法求解0-1背包问题的具体实现。基因由7件物品的装入状态（0或1）组成，种群初始化时随机填充基因，不校验是否超重，而是在适应度函数中对非法个体给予惩罚值1……

本节介绍用遗传算法求解0-1背包问题的具体实现。基因由7件物品的装入状态（0或1）组成，种群初始化时随机填充基因，不校验是否超重，而是在适应度函数中对非法个体给予惩罚值1，使其在选择中被淘汰。选择算子采用轮盘赌方法，按个体适应度占种群总适应度的比例计算选择概率，并通过积累概率区间配合随机数来选取个体；交叉算子以一定交叉概率随机选取两个个体，随机交换基因的若干位；变异算子以一定变异概率随机选取个体，随机翻转基因的若干位。将这些模块按流程组织即为遗传算法主体，循环结束后取适应度最高的个体解码。用种群32、进化500代、交叉概率0.8、变异概率0.15运行，得到最大价值170的解，与最优结果一致。总结部分指出遗传算法从大量解并行搜索、有利于全局最优，但效率未必高于穷举；轮盘赌算法存在低概率个体聚集导致的选择误差；本实现经多次模拟，进化代数越大获得最优解的比例越高。