基于改进差分进化算法的最小完成时间MTSP优化

《基于改进差分进化算法的最小完成时间MTSP优化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于改进差分进化算法的最小完成时间MTSP优化摘要：旅行商问题是一个经典的NP问题，对多人旅行商问题的求解则更具有意义。以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准，而对最小完成时间的多旅行商一类问题研究的相对较少。为了解决所有旅行商最小完成时问的多旅行商一类问题，提出一种编码方法和改进的差分进化算法优化此类问题。该方法适于距离对称和非对称的多旅行商问题求解。以距离非对称的多旅行商问题的实例进行了仿真和比较，可以看出文中提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的。关键词：差分进化算法：多旅

2、行商问题；离散组合问题：优化OptimizationofMinimumCompletionTimeMTSPBasedonImprovedDifferentialEvolutionAlgorithmAbstract:Travelingsalesmanproblemisaclassicalnondeterministicpolynomialproblem.Itissignificancetosolvemultipletravelingsalesmanproblems(MTSP).Previousresearchonmultipletr

3、avelingsalesmanproblemsismostlylimitedtothekindthatemployedtotal-path-shortestastheevaluatingrule,butlittlenoticeismadeonthekindthatemployedcompletion-tinie-shortestastheevaluatingrule・Inordertosolvetravelingsalesmanproblemthatemployedcomplction-timc-shortcstastheeval

4、uatingrule,anencodingmethodandimproveddifferentialevolutionalgorithmareusedtooptimizeit.Itisfitforsolvingsymmetricandasymmetricmultipletravelingsalesmanproblem.Thispaper,asymmetricmultipletravelingsalesmanproblemsaresimulated.Itisshownthatimproveddifferentialevolution

5、algorithmisefficienttosolvethekindofdiscretecombinatorialproblem,suchasmultipletravelingsalesmanproblems.Keywords:differentialevolutionalgorithm;multipletravelingsalesmanproblem;discretecombinatorialproblem;optimization0引言旅行商问题(TravelingSalesmanProblem,TSP)是一个典型的组合优化难

6、题，它在许多领域都有着广泛的应用，已被证明属于NP-hard问题2】。所谓TSP问题是指：有N个城市，要求旅行商到达每个城市各一次，且仅一次，并冋到起点，且要求旅行路线最短。而多旅行商问题(multipletravelingsalesmanproblem,MTSP)是指M个旅行商从同一个城市(或不同城市)出发，分别走一条旅行路线，使得每个城市有且仅有一个旅行商经过(出发城市除外)，且总路程最短。有关TSP问题的研究在现实问题中有很大的使用价值。诸如：交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等，都可抽象成TS

7、P或MTSP问题"J。在实际问题中，由于各个旅行商旅行的速度可能不同，研究旅行商的完成吋间是有一定的实际意义的。差分进化算法(DifferentialEvolutionAlgorithm,简称DEA)是一种新兴的基于实数编码的进化计算技术，它是由Stom和Price于1995年提出的⑺，最初的设想是用于解决切比雪夫多项式问题，后来发现DEA也是解决复杂优化问题的有效技术。DEA是一种基于种群优化的新智能优化方法，它已被证明在求解过程中具有高效性、收敛性、鲁棒性等优点。目前，DEA已经在许多领域得到了广泛应用，譬如人工神经元网络、化

8、工、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业、食品安全、环境保护和运筹学等。然而，尽管DEA获得了广泛研究，但相对其它进化算法而言，其研究成果还相对分散，缺乏系统性，尤其在理论方面还没有重大突破冈。目前，DEA在解决离散组合优化