遗传算法程序设计探讨

1引言

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点[1]。基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。

2遗传算法程序设计改进比较

2.1基本遗传算法对TSP问题解的影响本文研究的遗传算法及改进算法的实现是以C++语言为基础，在Windows2000的版本上运行，其实现程序是在MicrosoftVisualStadio6.0上编写及运行调试的。

1)遗传算法的执行代码m_Tsp.Initpop();//种群的初始化for(inti=0;idecen||variance>decvar)//m_Tsp.m_gen<100){//将新种群更迭为旧种群，并进行遗传操作m_Tsp.alternate();//将新种群付给旧种群m_Tsp.generation();//对旧种群进行遗传操作，产生新种群m_Tsp.m_gen++;m_Tsp.statistics();//对新产生的种群进行统计}

2)简单的遗传算法与分支定界法对TSP问题求解结果的对比遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但随着城市个数的增加，已没有精确解，无法确定遗传算法求解的精度有多高。一般情况下，当迭代代数增大时，解的精度可能高，但是时间开销也会增大。因此可以通过改进遗传算法来提高搜索能力，提高解的精度。表110个城市的TSP问题求解结果数据算法试验结果简单遗传算法分支定界法最佳解时间精确解时间试验12448.6100375s2448.61003700：07：30试验22448.61003713s试验32448.6100379s试验42459.54305410s试验52459.5430547s

2.2初始化时的启发信息对TSP问题解的影响

1)初始化启发信息在上述实验算法的基础上，对每一个初始化的个体的每五个相邻城市用分支界定法寻找最优子路径，然后执行遗传算法。

2)遗传算法与含有启发信息的遗传算法求解结果的对比当城市数增至20个时，用分支定界法已经不可能在可以接受的时间内得到精确的解了，只能通过近似算法获得其可接受的解。试验设计中算法的截止条件：固定迭代1000代。表2中的平均最优解为经过多次试验(10次以上)得到的最优解的平均值，最优解的出现时间为最优解出现的平均时间，交叉操作次数为最优解出现时交叉次数的平均值。表220个城市的TSP问题求解结果数据算法交叉操作次数最优解出现时间平均最优解简单遗传算法80244.479.4s1641.8含初始化启发信息的GA79000.237.4s1398.9从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。

2.3交叉算子对TSP问题解的影响

1)循环贪心交叉算子的核心代码

2)问题描述与结果比较下面笔者用经典的测试遗传算法效率的OliverTSP问题来测试循环贪心交叉算子的解的精度和解效率。OliverTSP问题的30个城市位置坐标如表3所示[2]。表3OliverTSP问题的30个城市位置坐标城市编号坐标城市编号坐标城市编号坐标1(87，7)11(58，69)21(4，50)2(91，83)12(54，62)22(13，40)3(83，46)13(51，67)23(18，40)4(71，44)14(37，84)24(24，42)5(64，60)15(41，94)25(25，38)6(68，58)16(2，99)26(41，26)7(83，69)17(7，64)27(45，21)8(87，76)18(22，60)28(44，35)9(74，78)19(25，62)29(58，35)10(71，71)20(18，54)30(62，32)表4贪心交叉与部分匹配交叉的比较(OliverTSP问题的30个城市)交叉算子交叉操作次数平均时间平均最优解部分匹配交叉5976031.2s517.0贪心交叉1577428.6s433.4从表4、图1中可以看到，贪心交叉算子大大提高了遗传算法的寻优能力，同时也降低了交叉操作次数。

3)并行遗传算法的性能笔者在MPI并行环境下，用C++语言实现了一个解决TSP问题的粗粒度模型的并行遗传算法。该程序采用的是主从式的MPI程序设计，通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数。试验环境为曙光TC1700机，测试的对象是OliverTSP问题的30个城市的TSP问题。正如在测试串行遗传算法所提到的数据结果，并行遗传算法也没有达到目前所记录的最好解，但是它提高了算法的收敛性，并行遗传算法的收敛趋势如图2所示[4]。图2遗传算法的收敛过程3结束语本文通过对基本遗传算法的不断改进，证明了添加启发信息、改进遗传算子和利用遗传算法固有的并行性都可以提高遗传算法的收敛性，其中对遗传算法交叉算子的改进可以大大提高遗传算法的寻优能力。