求解多目标旅行商问题的混合遗传算法

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

1、522011，47（7）ComputerEngineeringandApplications计算机工程与应用求解多目标旅行商问题的混合遗传算法1，2122朱云飞，蔡自兴，袁琦钊，郑金华1，2122ZHUYufei，CAIZixing，YUANQizhao，ZHENGJinhua1.中南大学信息科学与工程学院，长沙4100832.湘潭大学信息工程学院，湖南湘潭4111051.CollegeofInformationScienceandEngineering，CentralSouthUniversity，Changsha410083，China2.I

2、nstituteofInformationEngineering，XiangtanUniversity，Xiangtan，Hunan411105，ChinaZHUYufei，CAIZixing，YUANQizhao，etal.Hybridgeneticalgorithmformultiple-objectiveTSP.ComputerEngineeringandApplications，2011，47（7）：52-56.Abstract：GeneralTSPproblemisasingletarget，onlythepursuitofaperfo

3、rmanceindex：Theshortestpathtogo.However，theTSPforspecificproblems，inpracticeoftenneedstoconsider：Theshortestdistance，thetimeatleast，costtheprovince，theriskofthesmallest，andsoanumberoffactors.Inthetext，agreedycompositeoperatorandclimboperatorareintro-ducedforincreasingtheMTSPs

4、earchingability.Theexperimentresultdemonstratesthatthemethodisvalidandeffective.Keywords：TravelingSalesmanProblem（TSP）；multiple-objectivetravellingsalesmanproblem；geneticalgorithm；multiple-ob-jectivegeneticalgorithm；greedycompositeoperator；climb摘要：一般TSP问题是单目标的，只追求一个性能指标：所走路径最

5、短。然而对于具体的TSP问题，实际中常常需要考虑：路程最短、时间最少、费用最省、风险最小等等多方面的因素。设计了贪婪的复合变异算子（GCM），引入隔代爬山法算子来提高多目标TSP问题的搜索能力。实验结果表明该算法是有效的。关键词：旅行商问题；多目标旅行商问题；遗传算法；多目标遗传算法；贪婪的复合变异算子；爬山法DOI：10.3778/j.issn.1002-8331.2011.07.016文章编号：1002-8331（2011）07-0052-05文献标识码：A中图分类号：TP301.61引言设计高效的混合多目标遗传算法；二是从改进多目标遗传算遗

6、传算法[1]是由Michigan大学JohnHolland提出的一种法本身的操作算子入手来实现提高算法运行效率和求解质量概率搜索算法，其基本思想是模拟自然界生物进化过程，通过这一目的。设计了贪婪的复合变异算子（GCM），引入隔代爬交叉变异的进化操作和优胜劣汰的自然选择来寻求最优解。山法算子（Climb）来提高多目标TSP问题的搜索能力。遗传算法采纳了自然进化模型，如选择[1]、交叉[2]、变异[3]等。计算开始时，产生一定数目的初始化种群，并计算每个个体的适2旅行商问题简介应度。如果不满足终止条件，则产生新一代种群。为了产生旅行商问题（Trave

7、lingSalesmanProblem，TSP）也称货担下一代，需按照适应度选择父个体，父代经过基因重组而产生郎问题，是一个著名的NP难问题，具有广泛的应用背景和重子代。所有的子代再按一定概率变异，然后重新计算子代的要的理论价值。适应度[4]，优秀的子代将被插入到种群中并取代差的父代，构2.1旅行商的定义成新的一代。循环执行这一过程，直到满足终止条件为止。对旅行商问题的一般描述：旅行商从某城市出发，遍历n因为遗传算法不受连续性，可导性等条件的约束，并以其固有个城市后返回到出发城市，设从城市i到城市j的距离为d（i，j），的并行性以及使用方便和鲁棒

8、性强等特点，在许多领域得到如何选择旅行路线使得该旅行商此趟旅行的总距离最小。用广泛应用（如组合优化[4]、图像处理、通信工程等）。特别是