遗传算法求解TSP问题PPT课件

组长：林志青组员：赵昊罡、韩会雯,基于遗传算法求解TSP问题,1,.,遗传算法：,遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解,2,.,TSP问题：,旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。,3,.,遗传算法主要步骤：,选择、交叉、变异交叉：部分匹配交叉法顺序交叉法循环交叉法两交换启发式交叉法三交换启发式交叉法,4,.,部分匹配交叉算法：,先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。父代A：872|130|9546父代B：983|567|1420变为：tempA:872|567|9546tempB:983|130|1420对于TEMPA、TEMP中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1子代：802|567|9143子代：986|130|5427,5,.,顺序交叉算法：,从父代随机选一个编码子串，放到子代的对应位置；子代空余的位置从父代中按的顺序选取（与己有编码不重复）。同理可得子代。父代A:872|139|0546父代B:983|567|1420交叉后：子代A:856|139|7420子代B:821|567|3904,6,.,循环交叉算法：,CX同OX交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：OX中来自第一个亲代的编码子串是随机产生的，而CX却不是，它是根据两个双亲相应位置的编码而确定的。父代A：123456789父代B：546923781可得循环基因：1-5-2-4-9-1用循环的基因构成子代，顺序与父代一样12459用父代剩余的基因填满子代：126453789子代的编码同理。（循环基因5-1-9-4-2-5）,7,.,二（三）交叉启发式交叉法：,设N个城市为1,2,3,4,5,6,7,8随机选出一对未匹配的双亲如下:A=37264815B=48321756随机选出初始城j=1(位置号),Sj=1(城市号),右转动使1成为两双亲的第一位置城市如下:A1=15372648B1=17564832O1=1判断因为d(1,5)d(1,7)则A1以