一种改进并行遗传算法解决TSP

《一种改进并行遗传算法解决TSP》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、622008，44(27)ComputerEngineeringandApplications计算机工程与应用一种改进并行遗传算法解决TSP陈妍峰，田有先CHENYan-feng，TIANYou—xian重庚邮电大学计算机科学与技术学院，重庆400065CollegeofComputerScienceandTechnology，ChongqingUniversityofPostsandTelecommunications。Chongqing400065，ChinaE—mail：chenyfen92004@126．cornCHENYan-

2、feng。T]魄NYou-xian．TravelllngSalesmanProblembasedOn_reformedparallelgeneticalgorithm．ComputerEngineeringandApplications，2008．44(27)：62-64．Abstract：TheoperationofthegeneticalgorithmofTravellingSalesmanProblem(倦P)needslotsoftimeanditiseasytofallin—tothelocaloptima[solution．

3、Inordertoavoidtheproblem，theparallelcompoundgeneticalgorithmisproposed．田论method，whichavoidsthelocaloptimalproblemandreducesthetimeoftheoperation，makesuseoftheparalleloftheselection，tIIecross，thevariation．TheamountofspeciesdistributestheaveragetOtheCPUforoperatingintheenv

4、ironmentofMPI．Theexperienceprovesthetimeoftheoperationlessthanthesimplegeneticalgorithmandstrengthenstheabilityoftheglobaloptimalsolution．Keywor凼：parallel；geneticalgorithm；MessagePassingInterface(MPI)；TravellingSalesmanProblem(偈P)摘要：针对旅行商问题(TraveUingSalesmanProblem，TSP)的

5、遗传算法的大规模操作，需要大量运算时间而且容易造成局部最优解，提出一种并行混合遗待算法。该方法基于MP!并行环境，利用秤群中选择、交叉、变异徭作的并行化，将种群中个体平均的分配到处理器中进行操作。有效地避免局部最优解的出现和减少算法的运行时问。实验证明该方法相对于简单遗传算法具有更强全局寻优能力以及耗费更少的操作时间。关键词：并行；遗传算法；消息传递接口；旅行商问题DOhtO．3778，i．i铀n．1002—8331．2008．27．020文章编号：1002—833I‘2008)27-0062-03文献标识码：A中图分类号：TP301．

6、61孽l言旅行商问题(TravellingSalesmanProblem，TSP)是一个具有重要理论意义和广泛应用价值的组合优化难题，由于在工业、农业、国防、商业，特别是交通路线等方面的大量运用，因此引起了数学、物理、计算机等诸多领域研究者的关注。由于可能的路径总数与城市数目N是成指数增长的。所以一般很难精确地求出其最优解，因此寻求—个有效的近似求解算法是十分必要。目前求解这个问题主要有模拟退火算法、蚂蚁算法、遗传算法等，其中运用得最为广泛的就是遗传算法。目前求解TSP问题的遗传算法主要是混合遗传算法。但是由于混合遗传算法需要引入局部搜

7、索。造成局部最优解，而且增加编码变换操作，造成了运行时l'日J的增加。为了避免以上的缺陷，许多学者作了大量的工作。如文献ll堤出了=进制编码改进遗传算法，文献【2】提出了量子遗传算法，文献f3l提出了离散赌轮选择算法EPMX交叉算子和Dmutation变异算子，对遗传算法的各个算子进行改进。本文在文献【3m基础上，进一步改进运行的结构，提出并行混合遗传算法。该算法结合混合遗传算法，基于^I耽的并行环境，通过各个个体选择、交叉、变异算子nl的并行化。有效地保证全局最优解和减少算法所消耗时间。2问题的搽述TSP问题的数学模型：设有城市y={

8、y。，V∥～，y。}的访问顺序为乃{孔，死，⋯，蹦，其中‰l-五(正∈V，i=l—N)，则问题就化为求min(艺盔一。)．其中口是表示经过城市走一次且仅一次，再回到原点的所有不重复回路。本文解决TsP问题用