根据以上几个小节的内容,即可设计出相应于背包问题的遗传算法程序,实验程序 见附录。
第四章 遗传算法的实验
在这一章节中,将使用 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 的收敛结果小于108 ,函数 2 的收敛结果小于104 ,函数 3 的收敛结果小于-2。8。
表 4-1 列出了 20 次计算的平均收敛代数和收敛代数的标准差。实验结果表明,我们所 设计的算法通过了测试。
Matlab遗传算法在背包问题中的应用(9):http://www.youerw.com/zidonghua/lunwen_100127.html