遗传算法程序设计

1、遗传算法程序设计     摘  要本文通过对基本遗传算法添加初始化启发信息、改进交叉算子和利用本身所固有的并行性构架粗粒度并行遗传算法等方法提高了遗传算法的收敛性及其寻优能力。     关键词  遗传算法；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、     /对新产生的种群进行统计     2) 简单的遗传算法与分支定界法对TSP问题求解结果的对比     遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但随着城市个数的增加，已没有精确解，无法确定遗传算法求解的精度有多高。一般情况下，当迭代代数增大时，解的精度可能高，但是时间开销也会增大。因此可以通过改进遗传算法来提高搜索能力，提高解的精度。    表1  10个城市的TSP问题求解结果数据   

6、60;算法 试验结果    简单遗传算法    分支定界法    最佳解    时间    精确解    时间    试验1    2448.610037    5s       

7、 2448.610037        00：07：30    试验2    2448.610037    13s    试验3    2448.610037    9s    试验4    2459.543054

8、60;   10s    试验5    2459.543054    7s    2.2  初始化时的启发信息对TSP问题解的影响     1) 初始化启发信息     在上述实验算法的基础上，对每一个初始化的个体的每五个相邻城市用分支界定法寻找最优子路径，然后执行遗传算法。     2) 遗传算法与含有启发

9、信息的遗传算法求解结果的对比     当城市数增至20个时，用分支定界法已经不可能在可以接受的时间内得到精确的解了，只能通过近似算法获得其可接受的解。试验设计中算法的截止条件：固定迭代1000代。表2中的平均最优解为经过多次试验(10次以上)得到的最优解的平均值，最优解的出现时间为最优解出现的平均时间，交叉操作次数为最优解出现时交叉次数的平均值。    表2  20个城市的TSP问题求解结果数据    算法    交叉操作 次数

10、0;   最优解 出现时间    平均 最优解    简单遗传算法    80244.4    79.4s    1641.8    含初始化启发信息的GA    79000.2    37.4s    139

11、8.9        从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。 2.3  交叉算子对TSP问题解的影响     1)循环贪心交叉算子的核心代码 for(i=1；i<m_Chrom；i+)   flag=0；   city=m_newpopfirst.chromi-1；         /确定当前城市 

12、0; j=0；   while(flag=0&&j<4)         sign=adjcitycityj； /adjcity数组的数据为当前城市按顺序排列的邻接城市       flag=judge(first，i，sign)；  /判断此邻接城市是否已经存在待形成的个体中       j+；     if(flag= =0)    

13、;   /如果所有邻接城市皆在待扩展的个体中         while(flag= =0)                  sign=(int)rand()/(RAND_MAX/(m_ Chrom-1)；     /随机选择一城市         

14、;   flag=judge(first，i，sign)；           if(flag=1)       m_newpopfirst.chromi=sign；       2)问题描述与结果比较     下面笔者用经典的测试遗传算法效率的Oliver TSP问题来测试循环贪心交叉算子的解的精度和解效率。Oliver TSP问题的30个城市位置坐标如表3所示2。 

15、0;  表3  Oliver TSP问题的30个城市位置坐标    城市编号    坐标    城市编号    坐标    城市编号    坐标    1    (87，7)    11  

16、  (58，69)    21    (4，50)    2    (91，83)    12    (54，62)    22    (13，40)    3    (83，46

17、)    13    (51，67)    23    (18，40)    4    (71，44)    14    (37，84)    24    (24，42)  

18、60; 5    (64，60)    15    (41，94)    25    (25，38)    6    (68，58)    16    (2，99)    26 &

19、#160;  (41，26)    7    (83，69)    17    (7，64)    27    (45，21)    8    (87，76)    18    (

20、22，60)    28    (44，35)    9    (74，78)    19    (25，62)    29    (58，35)    10    (71，71) 

21、0;  20    (18，54)    30    (62，32)   表4  贪心交叉与部分匹配交叉的比较(Oliver TSP问题的30个城市)    交叉算子    交叉操作次数    平均时间    平均最优解    部分匹配交叉

22、    59760    31.2s    517.0    贪心交叉    15774    28.6s    433.4     从表4、图1中可以看到，贪心交叉算子大大提高了遗传算法的寻优能力，同时也降低了交叉操作次数。在多次试验中，贪心交叉算子找到的最优解与目前记载的最佳数据的误差

23、率为2.7%。而部分匹配交叉算子找到的最优解与目前记载的最佳数据的误差率高达7%。从而可以得到交叉算子对于遗传算法的计算效率和计算结果起主导性作用3。      图1  遗传算法的收敛过程 2.4  并行遗传算法消息传递实现的核心代码     1)主程序代码 /接收各个从程序的最优个体 for(i=0；i<slave；i+) MPI_Recv(Rchromi，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；

24、 /计算接收各个从程序的最优个体的回路距离 for(i=0；i<slave；i+)         fitnessi=0.0；         for(int j=0；j<chrom-1；j+)         fitnessi=fitnessi+distanceRchromijRchrom ij+1；       

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

26、#160;   if(1/fitnessi>min)                              sign=i；               

27、0;  min=1/fitnessi；                             fwrite(&gen，sizeof(int)，1，out)；         for(i=0；i<chrom；i+)    &#

28、160;    fwrite(&Rchromsigni，sizeof(unsigned)，1，out)；         fwrite(&fitnesssign，sizeof(double)，1，out)；         /每九代向从程序发送一个最优个体         if(gen%9=0)     

29、;    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_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；     Tsp.IndiAlternate(Rchrom2)； /进行下一代的计算 Tsp.A