利用遗传算法解决tsp问题

《利用遗传算法解决tsp问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、利用遗传算法解决TSP问题TSP问题，又称旅行商问题,旅行推销员问题,是指对于给定的n个城市,旅行商从某一城市出发不重复的访问其余城市后回到出发的城市,要求找出一条旅行路线,是总的旅行路程最短.遗传算法（GeneticAlgorithms，GA）是一种基于自然群体遗传演化机制的算法,它模拟自然界生物进化过程,采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的个体,并将个体编码成符号串形式(即染色体),模拟生物进化过程,对群体反复进行杂交等操作,根据预定的适应度函数对每个个体进行评价,依据优胜劣汰的进化规则,不断得到更优的群体,同时搜索优化群体中的最优个

2、体,求得满足要求的最优解。编码方式给每个城市一个固定的基因编号，例如10个城市为0123456789，随机地组成一个染色体（以下所有情况都以10个城市为例说明）。约定这10个城市之间的行走路线为：0123456789(其余基因序列的路线同样道理)两个城市间的距离（用r[i][j]表示）012345678901234567890,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、,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个基因存放在一个临时数组matrix[0]～matrix[9]。2随机产生两个0～9的数，例如产生了x1=2,x2=7,交换matrix[2]和matrix[7]的内容（利用voidswap(int*,int*)实现。）3重复过程2多次，得到一个基因序列，作为一个个体的染色体。4产生的基因序列赋值给一个个体的gene[0]～gene[9].一个完整路线的长度例如基因序列为：0829756413，存放在g

4、ene[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]]轮盘选择for(mem=0;mem

5、Calculaterelativefitness*/for(mem=0;mem