遗传算法程序设计探讨VIP

1、word遗传算法程序设计探讨穆艳玲(北京联合大学 电工电子技术实验实训基地，北京 100110)     摘  要本文通过对根本遗传算法添加初始化启发信息、改良交叉算子和利用本身所固有的并行性构架粗粒度并行遗传算法等方法提高了遗传算法的收敛性及其寻优能力。    关键词  遗传算法；TSP；交叉算子 1  引言    遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题

2、。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点1。    根本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。2 遗传算法程序设计改良比拟2.1 根本遗传算法对TSP问题解的影响    本文研究的遗传算法及改良算法的实现是以C+语言为根底，在Windows2000的版本上运行，其实现程序是在Microsoft Visual Stadio 6.0上编写及运行调试的。    1)

3、 遗传算法的执行代码m_Tsp.Initpop()；            /种群的初始化for(int i=0；i<m_Tsp.ReturnPop()；i+)         m_Tsp.calculatefitness(i)；  /计算各个个体的适应值m_Tsp.statistics()；         /

4、统计最优个体while(entropy>decen|variance>decvar)/m_Tsp.m_gen<100)/将新种群更迭为旧种群，并进行遗传操作m_Tsp.alternate()；         /将新种群付给旧种群m_Tsp.generation()；        /对旧种群进行遗传操作，产生新种群m_Tsp.m_gen+；m_Tsp.statistics()；    &

5、#160;   /对新产生的种群进行统计    2) 简单的遗传算法与分支定界法对TSP问题求解结果的比照    遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但随着城市个数的增加，已没有精确解，无法确定遗传算法求解的精度有多高。一般情况下，当迭代代数增大时，解的精度可能高，但是时间开销也会增大。因此可以通过改良遗传算法来提高搜索能力，提高解的精度。表1  10个城市的TSP问题求解结果数据算法试验结果简单遗传算法分支定界法最正确解时间精确解时间试验12448.6100375s 

6、0;2448.610037  00：07：30试验22448.61003713s试验32448.6100379s试验42459.54305410s试验52459.5430547s2.2  初始化时的启发信息对TSP问题解的影响    1) 初始化启发信息    在上述实验算法的根底上，对每一个初始化的个体的每五个相邻城市用分支界定法寻找最优子路径，然后执行遗传算法。    2) 遗传算法与含有启发信息的遗传算法求解结果的比照    当城市数增至2

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

8、同时缩短了遗传算法的寻优时间和问题的求解精度。2.3  交叉算子对TSP问题解的影响    1)循环贪心交叉算子的核心代码for(i=1；i<m_Chrom；i+)  flag=0；  city=m_newpopfirst.chromi-1；         /确定当前城市  j=0；  while(flag=0&&j<4)        sign=

9、adjcitycityj； /adjcity数组的数据为当前城市按顺序排列的邻接城市      flag=judge(first，i，sign)；  /判断此邻接城市是否已经存在待形成的个体中      j+；    if(flag= =0)       /如果所有邻接城市皆在待扩展的个体中        while(flag= =0) 

10、                sign=(int)rand()/(RAND_MAX/(m_ Chrom-1)；     /随机选择一城市           flag=judge(first，i，sign)；          if(flag=1)

11、      m_newpopfirst.chromi=sign；      2)问题描述与结果比拟    下面笔者用经典的测试遗传算法效率的Oliver TSP问题来测试循环贪心交叉算子的解的精度和解效率。Oliver TSP问题的30个城市位置坐标如表3所示2。表3  Oliver TSP问题的30个城市位置坐标城市编号坐标城市编号坐标城市编号坐标1(87，7)11(58，69)21(4，50)2(91，83)12(54，62)22(13，40)3(83，46)1

12、3(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  贪心交叉与局部匹配交叉的比拟(Oliver TSP问题的30个城市)交叉算子交叉操作次数平均时间平均最优解局部匹配交叉5976031.2s517.0贪心交叉1577428.6

13、s433.4    从表4、图1中可以看到，贪心交叉算子大大提高了遗传算法的寻优能力，同时也降低了交叉操作次数。在屡次试验中，贪心交叉算子找到的最优解与目前记载的最正确数据的误差率为2.7%。而局部匹配交叉算子找到的最优解与目前记载的最正确数据的误差率高达7%。从而可以得到交叉算子对于遗传算法的计算效率和计算结果起主导性作用3。 图1  遗传算法的收敛过程2.4  并行遗传算法消息传递实现的核心代码     1)主程序代码/接收各个从程序的最优个体for(i=0；i<slave；i+)MPI_Rec

14、v(Rchromi，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；/计算接收各个从程序的最优个体的回路距离for(i=0；i<slave；i+)        fitnessi=0.0；        for(int j=0；j<chrom-1；j+)        fitnessi=fit

15、nessi+distanceRchromijRchrom ij+1；        fitnessi=fitnessi+distanceRchromi0Rchrom ichrom-1；            /找到最优的个体并把它记录到文件里        for(i=0；i<slave；i+)    

16、                if(1/fitnessi>min)                             sign=i；   

17、0;             min=1/fitnessi；                            fwrite(&gen，sizeof(int)，1，out)；   

18、0;    for(i=0；i<chrom；i+)        fwrite(&Rchromsigni，sizeof(unsigned)，1，out)；        fwrite(&fitnesssign，sizeof(double)，1，out)；        /每九代向从程序发送一个最优个体   

19、     if(gen%9=0)        MPI_Bcast(Rchromsign，chrom，MPI_ UNSIGNED，0，MPI_COMM_WORLD)；    2)从程序代码/将上一代的最优个体传回主程序MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；/每九代接收一个最优个体并将其参加种群中替换掉最差个体if(gen%9=0)    PI_Bca

20、st(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；    Tsp.IndiAlternate(Rchrom2)；/进行下一代的计算Tsp.Aternate()；Tsp.Generation()；     Tsp.Statistics()；             3)并行遗传算法的性能    笔者在MPI并行环境下，用C语言实现了一个解决TSP问题的粗粒度模型的并行遗传算法。该程序采用的是主从式的MPI程序设计，通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数。试验环境为曙光TC1700机，测试的对象是Oliver TSP问题的30个城市的TSP问题。    正如在测试串行遗传算法所提到的数据结果，并行遗传算法也没有到达目前所记录的最好解，