《利用遗传算法解决TSP问题》由会员分享，可在线阅读，更多相关《利用遗传算法解决TSP问题（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 90 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,
3、 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基因序列的初始化1 将这10个基因存放在一个临时数组matrix0 matrix9。 2 随机产生两个09的数，例如产生了 x1=2,x2=7,交换matrix2和matrix7的内
4、容 （利用void swap(int *,int *)实现。） 3 重复过程2多次，得到一个基因序列，作为 一个个体的染色体。 4 产生的基因序列赋值给一个个体的gene0 gene9.一个完整路线的长度例如基因序列为：0 8 2 9 7 5 6 4 1 3，存放 在gene0gene9中。 表示行旅行路线为： 0829756413总路程为：rgene0gene1+rgene1gene2 +rgene9gene0轮盘选择 for(mem=0;memPopSize;mem+) sum+=populationmem.fitness;for(mem=0;memPopSize;mem+) /使小的选中
5、的可能性大 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仿真结果仿真结果
