实验五用遗传算法解决旅行商问题

--好好学习，每天向上--2试验五：用遗传算法解决旅行商问题MPI编写一个并行程序，利用遗传算法来解决旅行商问题。旅行商问题概述旅行商问题，即TSP问题〔TravelingSalesmanProblem〕是数学领域中著名问题之一。假设有一个旅行商人要访问N个城市，他必需选择所要走的路径，路径的限制是每个城市只能访问一次，而且最终要回到原来动身的城市。路径的选择目标是要求得的路径路程为全部路径之中的最小值。旅行商问题可以归纳为查找加权图中的最短回路问题。TSPNP问题，我们无法对该问题查找多项式时间算法，因此只能构造一些启发式近似算法来求得问题的较优解。在这里，我们承受遗传算法来找出近似最正确路径。遗传算法概述〔GeneticAlgorithm〕是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜寻最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群〔population〕开头的，而一个种群则由经过基因〔gene〕编码的肯定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现〔即基因型〕是某种基因组合，它打算了个体的外形的外部表现。初代种群产生之后，依据适者生存和优胜劣汰的原理，逐代〔generation〕〔fitness〕selection〔genetic进展组合穿插crossove〕和变异〔mutatio，产生出代表的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码〔decoding，可以作为问题近似最优解。遗传算法并行化MPI进展并行化程序设计。三．实现方法设计思路程序开头初始化种群进化完毕？Y程序开头初始化种群进化完毕？YN输出最优解突变进程完毕进化次数是 10的倍数？Y给其它进程N接收其它进程发来的个体产生下一代种群--好好学习，每天向上--3图3-1 每个进程的根本流程实现细节种群：每个种群由一个链表表示，每个结点表示一个个体，个体的构造如下：structgroup_member{intorder[node_num+1]; //首元素记录回路的路径长度，1为起始结点group_member*pointer;}存储空间，操作敏捷，缺点在于与数组相比其访问速度较慢。适应度：长度越短，其适应度就越强。的设计承受由DavisOX另一个亲体的城市相对次序来构造后代。例如，两个亲体〔|”标记par=〔123|4567|89〕1par=〔452|1876|93〕2将依据下面的方式产生后代。首先，切割点之间的片段被拷贝到后代里：chd=〔xxx|4567|xx〕1chd=〔xxx|1876|xx〕2o

4、5、671 2 12—1—8—9—3chd中：1chd

=〔218|4567|93〕1相像地，我们可以得到另一个后代：chd

=〔234|1876|59〕2〔不是它们的位置〕是重要的，即两个旅行5—1—7—8—9—4—6—2—38—9—4—6—2—3—5—1—7--好好学习，每天向上--5是一样的。的设计将两点间的子串反转。说明如下：原个体：〔123456789〕随机选择两点：〔12|3456|789〕倒置后的个体：〔12|6543|789〕四．结果分析运行结果如下所示：4-1第一次运行结果4-2其次次运行结果4-3