表2 20个城市的TSP问题求解结果数据 算法 交叉操作 次数 最优解 出现时间 平均 最优解 简单遗传算法 80244.4 79.4s 1641.8 含初始化启发信息的GA 79000.2 37.4s 1398.9
从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。
2.3 交叉算子对TSP问题解的影响
1)循环贪心交叉算子的核心代码 for(i=1；i<m_Chrom；i++) { flag=0； city=m_newpop[first].chrom[i-1]； //确定当前城市 j=0； while(flag==0&&j<4) { sign=adjcity[city][j]； //adjcity数组的数据为当前城市按顺序排列的邻接城市 flag=judge(first，i，sign)； //判断此邻接城市是否已经存在待形成的个体中 j++； } if(flag= =0) //如果所有邻接城市皆在待扩展的个体中 { while(flag= =0) { sign=(int)rand()/(RAND_MAX/(m_ Chrom-1))； //随机选择一城市 flag=judge(first，i，sign)； } } if(flag==1) m_newpop[first].chrom[i]=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) 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个城市) 交叉算子 交叉操作次数 平均时间 平均最优解 部分匹配交叉 59760 31.2s 517.0 贪心交叉 15774 28.6s 433.4
从表4、图1中可以看到，贪心交叉算子大大提高了遗传算法的寻优能力，同时也降低了交叉操作次数。在多次试验中，贪心交叉算子找到的最优解与目前记载的最佳数据的误差率为2.7%。而部分匹配交叉算子找到的最优解与目前记载的最佳数据的误差率高达7%。从而可以得到交叉算子对于遗传算法的计算效率和计算结果起主导性作用[3]。