利用遗传算法解决TSP问题.pptxVIP

利用遗传算法解决TSP问题第1页/共13页 利用遗传算法解决TSP问题第2页/共13页 TSP问题，又称旅行商问题, 旅行推销员问题,是指对于给定的n 个城市,旅行商从某一城市出发不重复的访问其余城市后回到出发的城市,要求找出一条旅行路线,是总的旅行路程最短. 遗传算法（Genetic Algorithms，GA）是一种基于自然群体遗传演化机制的算法, 它模拟自然界生物进化过程, 采用人工进化的方式对目标空间进行随机化有哪些信誉好的足球投注网站。它将问题域中的可能解看作是群体的个体, 并将个体编码成符号串形式( 即染色体) , 模拟生物进化过程, 对群体反复进行杂交等操作, 根据预定的适应度函数对每个个体进行评价, 依据优胜劣汰的进化规则, 不断得到更优的群体, 同时有哪些信誉好的足球投注网站优化群体中的最优个体, 求得满足要求的最优解。第3页/共13页 编码方式 给每个城市一个固定的基因编号，例如10个城市为 0 1 2 3 4 5 6 7 8 9 ，随机地组成一个染色体（以下所有情况都以10个城市为例说明）。 约定这10个城市之间的行走路线为： 0?1?2?3?4?5?6?7?8?9(其余基因序列的路线同样道理)第4页/共13页 两个城市间的距离（用r[i][j]表示） 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, 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第5页/共13页 基因序列的初始化1 将这10个基因存放在一个临时数组matrix[0]～matrix[9]。2 随机产生两个0～9的数，例如产生了x1=2,x2=7,交换matrix[2]和matrix[7]的内容（利用void swap(int *,int *)实现。）3 重复过程2多次，得到一个基因序列，作为一个个体的染色体。4 产生的基因序列赋值给一个个体的gene[0]～gene[9].第6页/共13页 一个完整路线的长度例如基因序列为：0 8 2 9 7 5 6 4 1 3，存放在gene[0]～gene[9]中。表示行旅行路线为：0?8?2?9?7?5?6?4?1?3总路程为： r[gene[0]][gene[1]]+r[gene[1]][gene[2]]~+r[gene[9]gene[0]]第7页/共13页 轮盘选择 for(mem=0;memPopSize;mem++) sum+=population[mem].fitness; for(mem=0;memPopSize;mem++) //使小的选中的可能性大 x[mem]=sum-population[mem].fitness; sum=0.0; for(mem=0;memPopSize;mem++) sum+=x[mem]; /* Calculate relative fitness */ for(mem=0;memPopSize;mem++) population[mem].rfitness=x[mem]/sum;第8页/共13页 交叉 例如一个基因序列为： 0 2 5 6 9 8 1 3 4 7 产生两个0～9的int型随机数，如得到2和6，将gene[2]和gene[6]之间的基因反序，得到： 0 2 1 8 9 6 5 3 4 7第9页/共13页 变异例如一个基因序列为： 0 2 5 6 9 8 1 3 4 7产生两个0～9的int型随机数，如得到2和6，将gene[2]和gene[6] 的基因交换，得到： 0 2 1 6 9 8 5 3 4 7第10页/共13页 仿真结果第11页/共13页 仿真结果第12页/共13页 感谢您的欣赏第13页/共13页