《利用遗传算法解决TSP问题.ppt》由会员分享，可在线阅读，更多相关《利用遗传算法解决TSP问题.ppt（12页珍藏版）》请在三一办公上搜索。
1、利用遗传算法解决TSP问题,TSP问题，又称旅行商问题,旅行推销员问题,是指对于给定的n 个城市,旅行商从某一城市出发不重复的访问其余城市后回到出发的城市,要求找出一条旅行路线,是总的旅行路程最短.,遗传算法（Genetic Algorithms，GA）是一种基于自然群体遗传演化机制的算法,它模拟自然界生物进化过程,采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的个体,并将个体编码成符号串形式(即染色体),模拟生物进化过程,对群体反复进行杂交等操作,根据预定的适应度函数对每个个体进行评价,依据优胜劣汰的进化规则,不断得到更优的群体,同时搜索优化群体中的最优个体,求得
2、满足要求的最优解。,编码方式,给每个城市一个固定的基因编号，例如10个城市为 0 1 2 3 4 5 6 7 8 9，随机地组成一个染色体（以下所有情况都以10个城市为例说明）。约定这10个城市之间的行走路线为：0123456789(其余基因序列的路线同样道理),两个城市间的距离（用rij表示）,0 1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8 9,0,1,4,6,8,1,3,7,2,9,1,0,7,5,3,8,3,4,2,4,4,7,0,3,8,3,7,9,1,2,6,5,3,0,3,1,5,2,9,1,8,3,8,3,0,2,3,1,4,6,1,8,3,1,2,0
3、,3,3,9,5,3,3,7,5,3,3,0,7,5,9,7,4,9,2,1,3,7,0,1,3,2,2,1,9,4,9,5,1,0,1,9,4,2,1,6,5,9,3,1,0,基因序列的初始化,1 将这10个基因存放在一个临时数组matrix0matrix9。2 随机产生两个09的数，例如产生了x1=2,x2=7,交换matrix2和matrix7的内容（利用void swap(int*,int*)实现。）3 重复过程2多次，得到一个基因序列，作为一个个体的染色体。4 产生的基因序列赋值给一个个体的gene0gene9.,一个完整路线的长度,例如基因序列为：0 8 2 9 7 5 6 4 1
4、 3，存放在gene0gene9中。表示行旅行路线为：0829756413总路程为：rgene0gene1+rgene1gene2+rgene9gene0,轮盘选择,for(mem=0;memPopSize;mem+)sum+=populationmem.fitness;for(mem=0;memPopSize;mem+)/使小的选中的可能性大xmem=sum-populationmem.fitness;sum=0.0;for(mem=0;memPopSize;mem+)sum+=xmem;/*Calculate relative fitness*/for(mem=0;memPopSize;mem+)populationmem.rfitness=xmem/sum;,交叉,例如一个基因序列为：0 2 5 6 9 8 1 3 4 7 产生两个09的int型随机数，如得到2和6，将gene2和gene6之间的基因反序，得到：0 2 1 8 9 6 5 3 4 7,变异,例如一个基因序列为：0 2 5 6 9 8 1 3 4 7产生两个09的int型随机数，如得到2和6，将gene2和gene6 的基因交换，得到：0 2 1 6 9 8 5 3 4 7,仿真结果,仿真结果,Thanks,
