遗传算法程序设计探讨

1、遗传算法程序设计探讨         摘  要本文通过对基本遗传算法添加初始化启发信息、改进交叉算子和利用本身所固有的并行性构架粗粒度并行遗传算法等方法提高了遗传算法的收敛性及其寻优能力。     关键词  遗传算法；TSP；交叉算子      1  引言    遗传算法是模拟生物在环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不

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

3、60;   1) 遗传算法的执行代码 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、160;   算法 试验结果简单遗传算法分支定界法最佳解时间精确解时间试验12448.6100375s    2448.610037    00：07：30试验22448.61003713s试验32448.6100379s试验42459.54305410s试验52459.5430547s    2.2  初始化时的启发信息对TSP问题解的影响    1) 初始化启发信息     在上述实验算法的基础上，对每一个初始化

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

8、解结果数据    算法交叉操作 次数最优解 出现时间平均 最优解简单遗传算法80244.479.4s1641.8含初始化启发信息的GA79000.237.4s1398.9        从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。 2.3  交叉算子对TSP问题解的影响    1)循环贪心交叉算子的核心代码 for(i=1；i<m_Chrom；i+)   fla

9、g=0；   city=m_newpopfirst.chromi-1；         /确定当前城市   j=0；   while(flag=0&&j<4)         sign=adjcitycityj； /adjcity数组的数据为当前城市按顺序排列的邻接城市       flag=judge(first，i，sign)；  /判断此邻

10、接城市是否已经存在待形成的个体中       j+；     if(flag= =0)       /如果所有邻接城市皆在待扩展的个体中         while(flag= =0)                  sign=(int)rand()/(RA

11、ND_MAX/(m_ Chrom-1)；     /随机选择一城市            flag=judge(first，i，sign)；           if(flag=1)       m_newpopfirst.chromi=sign；       2)问题描述与结果比较  &

12、#160;  下面笔者用经典的测试遗传算法效率的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)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  贪心交叉与部分匹配交叉的比较(Oliver TSP问题的30个城市)    交叉算子交叉操作次数平均时