根据以上几个小节的内容，即可设计出相应于背包问题的遗传算法程序，实验程序 见附录。

第四章 遗传算法的实验

在这一章节中，将使用 Matlab 对设计的遗传算法进行仿真实验。首先使用测试函 数初步测试算法的性能；然后用通过测试的算法先解决一个简单的背包问题，保留结果； 接着用控制变量法对算法的参数进行实验比较，寻找出一组最佳参数，作为算法最后的 参数；最后使用最佳参数下的算法对不同维度的背包问题进行求解，观察算法解决不同 复杂度的背包问题时的性能情况。

4。1 算法测试实验

4。1。1 测试函数选择

在进行背包问题的实验之前，需要使用测试函数对遗传算法进行测试。这里我使用 的是由 De Jong 于 1975 年提出的三个测试函数：

函数 F 是一个简单的平方求和函数，当 x 0 时，此时函数的值最小且等于零； F

1 i 2

是一个二维的 Rosenbrock 函数，在 x1 = x2 =1 时有最小值，虽然它是单峰值函数但它极 难最小化，；F3 是含有噪声干扰的四次函数，前半部分是在 xi 0 的时候有极小值，但后 半部分加了一个高斯正态分布作为噪声干扰。

4。1。2  测试结果

测试实验中，以函数值作为适应度值，这里需要寻找值域中的极小值点。实验记录 下每一代中的最优解，即适应度最小值的解，以及每一代中整个种群的平均适应度值。 图中所示的，点划线是平均适应度值的变化曲线，加粗实线是最优解适应度值的变化曲 线。通过图形可以发现，最优解适应度值在遗传算法进行几十代之后就开始接近于 0， 最终收敛。而平均适应度值也随着代数的增加也渐渐趋近于 0，而它的波动的原因是因 为算法中存在变异操作，保持了种群的多样性，但总体是越来越接近 0，说明了种群的质量在不断提升。来,自.优;尔:论[文|网www.youerw.com +QQ752018766-

使用不同的测试函数分别测试 20 次，得到了算法每次达到收敛时所需的代数，计 算 20 次结果，取得平均值，结果见下表 4-1。

F1  函数测试结果

通过 20 次试验测试结果发现，目前我们所设计的算法能够在 1000 代以内达到收敛，

函数 1 的收敛结果小于108 ，函数 2 的收敛结果小于104 ，函数 3 的收敛结果小于-2。8。

表 4-1 列出了 20 次计算的平均收敛代数和收敛代数的标准差。实验结果表明，我们所 设计的算法通过了测试。