实验9-2 高级搜索技术2

一、实验目的
（1）掌握高级搜索技术的相关理论，能根据实际情况选取合适的搜索方法；
（2）掌握遗传算法的基本思想，能根据实际问题选择种群数量、选择方法、交叉与变异方法；
（3）运用遗传算法解决TSP问题，并分析遗传算法的优缺点。
二、实验内容
1、现有一个商人，准备从广州出发，经过广东省的各个城市再回到广州，每个城市只经过一次，城市分布情况见图1所示。请使用模拟退火搜索算法和遗传算法寻找一条线路，使得商人按上述要求走过的路径之和最短，并比较两种方法所使用的时间和最终的行走路径的优越性。各个城市之间的距离请通过上网搜索确定。

图1 广东省市级城市分布图
各城市距离表示方法一：

  String[] citys={"广州","佛山","东莞","中山","珠海","深圳","惠州","河源","汕尾","梅州","潮州","汕头","揭阳","清远","韶关","云浮","茂名","湛江","阳江","江门","肇庆"};int[][] Dist={{max ,22  ,90  ,86  ,133 ,147 ,148 ,228 ,272 ,426 ,490 ,527 ,465 ,63  ,180 ,145 ,371 ,488 ,225 ,102 ,109 },//广州到各市距离{22  ,max ,112 ,78  ,128 ,169 ,170 ,250 ,286 ,456 ,520 ,557 ,495 ,85  ,229 ,132 ,349 ,466 ,198 ,66  ,87  },//佛山到各市距离{90  ,112 ,max ,92  ,132 ,57  ,162 ,134 ,207 ,340 ,404 ,441 ,379 ,153 ,297 ,202 ,461 ,578 ,274 ,122 ,199 },//东莞到各市距离{86  ,78  ,92  ,max ,25  ,121 ,161 ,240 ,265 ,409 ,420 ,425 ,385 ,158 ,309 ,191 ,317 ,396 ,201 ,43  ,144 },//中山到各市距离{133 ,128 ,132 ,25  ,max ,162 ,195 ,282 ,307 ,452 ,462 ,467 ,427 ,202 ,354 ,230 ,328 ,407 ,199 ,87  ,193 },//珠海到各市距离{147 ,169 ,57  ,121 ,162 ,max ,90  ,177 ,169 ,343 ,351 ,333 ,317 ,198 ,324 ,265 ,420 ,499 ,303 ,144 ,218 },//深圳到各市距离{148 ,170 ,162 ,161 ,195 ,90  ,max ,87  ,130 ,259 ,284 ,289 ,249 ,188 ,271 ,278 ,452 ,531 ,335 ,180 ,231 },//惠州到各市距离{228 ,250 ,134 ,240 ,282 ,177 ,87  ,max ,219 ,190 ,269 ,286 ,246 ,211 ,251 ,335 ,534 ,613 ,418 ,266 ,288 },//河源到各市距离{272 ,286 ,207 ,265 ,307 ,169 ,130 ,219 ,max ,221 ,200 ,182 ,165 ,317 ,400 ,407 ,568 ,647 ,452 ,293 ,360 },//汕尾到各市距离{426 ,456 ,340 ,409 ,452 ,343 ,259 ,190 ,221 ,max ,135 ,155 ,110 ,398 ,360 ,522 ,708 ,787 ,592 ,436 ,475 },//梅州到各市距离{490 ,520 ,404 ,420 ,462 ,351 ,284 ,269 ,200 ,135 ,max ,49  ,29  ,421 ,439 ,545 ,718 ,797 ,601 ,446 ,498 },//潮州到各市距离{527 ,557 ,441 ,425 ,467 ,333 ,289 ,286 ,182 ,155 ,49  ,max ,46  ,426 ,466 ,550 ,723 ,802 ,606 ,450 ,503 },//汕头到各市距离{465 ,495 ,379 ,385 ,427 ,317 ,249 ,246 ,165 ,110 ,29  ,46  ,max ,387 ,413 ,511 ,684 ,763 ,567 ,412 ,464 },//揭阳到各市距离{63  ,85  ,153 ,158 ,202 ,198 ,188 ,211 ,317 ,398 ,421 ,426 ,387 ,max ,168 ,171 ,379 ,463 ,286 ,151 ,123 },//清远到各市距离{180 ,229 ,297 ,309 ,354 ,324 ,271 ,251 ,400 ,360 ,439 ,466 ,413 ,168 ,max ,323 ,531 ,615 ,436 ,301 ,293 },//韶关到各市距离{145 ,132 ,202 ,191 ,230 ,265 ,278 ,335 ,407 ,522 ,545 ,550 ,511 ,171 ,323 ,max ,244 ,328 ,182 ,148 ,56  },//云浮到各市距离{371 ,349 ,461 ,317 ,328 ,420 ,452 ,534 ,568 ,708 ,718 ,723 ,684 ,379 ,531 ,244 ,max ,96  ,130 ,275 ,267 },//茂名到各市距离{488 ,466 ,578 ,396 ,407 ,499 ,531 ,613 ,647 ,787 ,797 ,802 ,763 ,463 ,615 ,328 ,96  ,max ,208 ,354 ,348 },//湛江到各市距离{225 ,198 ,274 ,201 ,199 ,303 ,335 ,418 ,452 ,592 ,601 ,606 ,567 ,286 ,436 ,182 ,130 ,208 ,max ,158 ,201 },//阳江到各市距离{102 ,66  ,122 ,43  ,87  ,144 ,180 ,266 ,293 ,436 ,446 ,450 ,412 ,151 ,301 ,148 ,275 ,354 ,158 ,max ,104 },//江门到各市距离{109 ,87  ,199 ,144 ,193 ,218 ,231 ,288 ,360 ,475 ,498 ,503 ,464 ,123 ,293 ,56  ,267 ,348 ,201 ,104 ,max }//肇庆到各市距离};

各城市距离表示方法二：

# 21个城市的坐标
city_location = [(113.28, 23.12, '广州市'),(113.59, 24.80, '韶关市'),(114.08, 22.54, '深圳市'),(113.55, 22.22, '珠海市'),(116.70, 23.37, '汕头市'),(113.12, 23.02, '佛山市'),(113.09, 22.59, '江门市'),(110.36, 21.27, '湛江市'),(110.91, 21.65, '茂名市'),(112.47, 23.05, '肇庆市'),(114.41, 23.07, '惠州市'),(116.11, 24.29, '梅州市'),(115.36, 22.77, '汕尾市'),(114.69, 23.74, '河源市'),(111.97, 21.85, '阳江市'),(113.05, 23.68, '清远市'),(113.74, 23.04, '东莞市'),(113.38, 22.52, '中山市'),(116.63, 23.66, '潮州市'),(116.35, 23.54, '揭阳市'),(112.04, 22.92, '云浮市')]

主要代码：
存储广东省内各城市之间的距离：

计算路径长度

随机创建一个种群

获取种群中的精英

交叉

变异

遗传算法

结果：

3、实验体会与总结
结果分析：
遗传算法在给定的问题规模（即广东省的各个城市）内，能够在合理的时间内找到一个较好的解。路径长度2614是这些城市之间的一个相对较短的旅行距离，而310毫秒的执行时间表明算法在计算上是高效的。
运用遗传算法解决TSP问题，并分析遗传算法的优缺点：
优点：全局搜索能力强，能够找到较好的解；适用于大规模搜索空间。
遗传算法可以采用并行计算来加快算法运行。
缺点：计算量大，参数选择（如种群大小、交叉率、变异率等）对性能有较大影响；容易早熟收敛。
与模拟退火算法相比：
（1）两种算法在相近的运行时间内，模拟退火的误差维持在5%左右，稍差于遗传算法。
（2）模拟退火是采用单个个体进行优化，遗传算法是一种群体性算法。
（3）模拟退火与遗传算法都对初解有一定的依赖性，好的初解有利于最终解。