基于改进的遗传算法求解旅行商问题

《基于改进的遗传算法求解旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于改进的遗传算法求解旅行商问题【摘要】论文提出了一种改进的遗传算法求解旅行商问题（TSP）。该算法结合TSP的特点，采用实数编码方式减少算法计算复杂度；等位交叉方式扩大算法的搜索空间，改善寻优能力；轮盘赌选择策略加快算法的收敛速度。通过30个城市的benchmark实例进行仿真试验，试验结果表明，改进的遗传算法改善了全局搜索能力，具有较快的收敛速度和较高的收敛精度。中国3/vie　　【Abstract】Inthispaper，animprovedgeicalgorithmfortravelingsalesmanproblem（TSP）isproposed

2、.ThealgorithmbinesthecharacteristicsofTSP，usingrealnumberencodingtoreducetheputationalplexityofthealgorithm，acrossprovesearchingability，rouletteselectionstrategytoacceleratetheconvergenceofthealgorithm.Inthispaper，ithassimulatedbenchmarkexamplesinthirtycities.Thesimulationresultss

3、hoprovedgeicalgorithmcanimprovetheglobalsearchability，anditsconvergencespeedandtheconvergenceprecisionishigher.　　【关键词】旅行商问题；遗传算法；收敛速度　　【Key；geicalgorithm；convergenceprecision　　【中图分类号】TP18【文献标志码】A【】1673-1069（2017）03-0096-03　　1引言　　旅行商问题（TSP）也称货郎担问题，它旨在寻求旅行商在遍历诸多城市一次最后回到起点城市的最短路径，是数学

4、图论中的经典问题。在实际生活中，像物流路径优化、车间调度和网络路由选址等都可归结为TSP，因此，TSP的研究具有重要的理论意义和实际价值。　　Karp[1]证明了TSP是一个NP难问题，传统的优化算法在求解TSP问题时往往会陷入局部最优，尤其随着城市数量的增加，计算量也急剧增加，致使很多算法瘫痪。因此智能优化算法强的搜索效率、快速的收敛速度在求解TSP中得到了广泛应用。Aziz[2]提出了广义的蚁群算法，算法中融合了局部和全局两种信息素更新机制，提高全局迅游能力。何湘竹[3]将混沌搜索机制融入基于教与学的优化算法求解TSP，通过benchmark实例仿真试

5、验显示，新算法性能更优越。段艳明[4]将果蝇优化算法的连续空间对应到离散规划，利用了遗传算法的交叉、变异操作进行路径的寻优，加快局部搜索能力和收敛速度。　　遗传算法是一种模拟生物进化过程的随机搜索优化方法，与其他的局部搜索算法相比，遗传算法具有更强的鲁棒性，隐形的并行搜索机制增强了算法寻优能力，但遗传算法也存在缺陷，例如：种群常常会出现早熟收敛、易陷入局部最优的问题，使算法的搜索性能大大降低[5]。针对这些问题，学者提出了许多解决方法，如参数控制、多种群的运用和交配限制[6-8]等。　　2求解TSP的改进遗传算法　　鉴于目前遗传算法在优化领域的优越性能，论

6、文以TSP为例，提出了改进的遗传算法。　　2.1实数编码　　对包含n个城市的TSP问题，我们提出一种新的有效编码方法――实数编码。它是指整数1到的一个全排列所构成的实数序列a1，a2，…，an，其中a∈[1，n）之间的整数，编码中ai表示编号为的城市排在路径上的第ai个位置。　　2.2轮盘赌选择　　轮盘赌选择法是遗传算法中常用的选择方式，首先计算每个个体的适应度值fi，i∈[1，ps），ps为种群规模。这里fi的值越大，说明这个个体越优秀；其次，计算每个个体的选择概率pi=fi/（∑fi）和累积概率Pi=∑■■pi；最后，随机产生一个实数num∈[0，1]

7、，选取满足num

8、离，初始生成ps个个体，即ps个城市路线；　　步骤3计算每条路线的