遗传算法解决TSP问题

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业遗传算法解决TSP问题TSP问题所谓TSP问题（旅行商问题）即最短路径问题就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。用遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。遗传算法2.1 遗传算法介绍遗传算法是一种模拟生命进化机制的搜索和优化方法，是

2、把自然遗传学和计算机科学结合起来的优化方程，有很强的解决问题的能力和广泛的适应性。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索合适的假设从若干初始假设的群体集合开始。当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。每一步，根据给定的适应度评估当前群体的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子。下面介绍几个遗传算法的基本概念：（1）染色体（Chromosome）：在使用遗传算法时，需要把问题的解编成一个适合的码子。这种具有固定结构的符号串既是染色体，符号串的每一位代表一个基因。符号串的总位数成为染色体的长度，一个染色体就代表问题的一个解，每

3、个染色体也被称为一个个体。（2）群体（Population）：每代所产生的染色体总数成为群体，一个群体包含了该问题在这一代的一些解的集合。（3）适应度（Fitness）：对群体中每个染色体进行编码后，每个个体对应一个具体问题的解，而每个解对应于一个函数值。该函数值即适应函数，就是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数在前一代群体的基础上产生新一代群体的工作成为遗传操作，基本的遗传操作有：（1）选择（Select）：按一定的概率从上代群体中选择M对个体作为双亲，直接拷贝到下一代，染色体不发生变化。（2）交叉（Crossover）：对于选中进行繁殖的两个染色体X，Y，以X，Y为双

4、亲作交叉操作，从而产生两个后代X1，Y1.（3）变异（Mutation）：对于选中的群体中的个体（染色体），随机选取某一位进行取反运算，即将该染色体码翻转。用遗传算法求解的过程是根据待解决问题的参数集进行编码，随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。如果满足收敛条件，此种群为最好个体，否则，对产生的新一代群体重新进行选择、交叉、变异操作，循环往复直到满足条件。2.2 遗传算法原型：GA(Fitness,Fitness_threshold,p,r,m)Fitness:适应度评分函数,为给定假设赋予一个评估分数Fitness_threshold:指定终止判据的阈值p:群体

5、中包含的假设数量r:每一步中通过交叉取代群体成员的比例m:变异率初始化群体:P随机产生的p个假设评估:对于P中的每一个h,计算Fitness(h)当maxFitness(h)Fitness_threshold,做产生新的一代Ps:1.选择:用概率方法选择P的(1-r)p个成员加入Ps.从P中选择假设hi的概率用下面公式计算: QUOTE 2.交叉:根据上面给出的 QUOTE ,从P中按概率选择r(p/2)对假设.对于每对假设,应用交叉算子产生两个后代.把所有的后代加入Ps3.变异:使用均匀的概率从Ps中选择m%的成员.对于选出的每个成员,在它表示中随机选择一个为取反4.更新:PPs5.评估:对

6、于P中的每个h计算Fitness(h)从P中返回适应度最高的假设TSP问题的遗传算法设计与实现3.1 TSP问题的图论描述求最短路径问题，用图论术语描述如下：在图G(V,A)中，V表示顶点集合，V=(v1,v2,vn)对G中的某一边(,)，相应的有一个数d(,)，如果G中不存在边(,)，则令d(,)无穷大，如果把d(,)认为是边(,)的长度，则通路的长度定义为组成路的各条边的长度总和。顶点,之间是否有边相连，由邻接矩阵来决定。邻接矩阵A：对一个具有v个顶点，e条边的图G的邻接矩阵A=是一个vv阶方阵，其中=1，表示和邻接，=0表示vi和vj不相邻接（或i=j）。3.2 染色体编码对于一个给定的

7、图模型，将图中各顶点序号自然排序，然后按此顺序将每个待选顶点作为染色体的一个基因，当基因值为1时，表示相应的顶点被选入该条路径中，否则反之。此染色体中的基因排列顺序即为各顶点在次条通路中出现的先后顺序，染色体的长度应等于该图中的顶点个数。在本程序的TSP问题中一共有20个城市，也就是在图模型中有20个顶点，因此一个染色体的长度为20。3.3 适应函数f(i)对具有n个顶点的图，已知各顶点之间(,)的边长度d(,)，把到间的一条通路的路径长度定义为适应函数： 对该最优化问题，就是要寻找解，使f()值最小。3.4 选择操作选择作为交叉的双亲，是根据前代染色体的适应函数值所确定的，质量好的个体，即从

8、起点到终点路径长度短的个体被选中的概率较大。3.5 交叉与变异操作将被选中的两个染色体进行交叉操作的过程是先产生一个随机数，确定交叉点，位于染色体的第几位基因上.然后在此位置进行部分基因交换。变异操作是将染色体中某位基因逆变，即由1变为0，或反之。变异的意义为在某条路径上去掉或增加某顶点.但这样做的结果并不一定能使路径的长度减少。也就是说有可能使各代中产生的比较好的方案在遗传过程中丢失，迟缓了获得最优解的速度。为了使算法尽可能快地获得更好的解，改善遗传算法的收敛性。在变异操作时，增加了个体求优的自学习过程，即在某位基因变异后.计算新产生的染色体的适应函数值，若适应函数值更小，即获得的路径更短，

9、则保留;否则，保持原来的解不变。如果有连续N/3次没有得到更好的解，则该过程结束。其中N表示从起点到终点的顶点数。3.6 TSP问题的遗传算法的具体步骤解最短路径的遗传算法如下：Generatep(n);表示程序开始时要首先产生一个群体，群体个数为nEvaluatep(h);表示计算每个个体适应度，h是种群中的一个个体Repeat roof Generations times;重复下面的操作，直到满足条件为止Select p(h) from p(n-1);表示从前一代群体中选择一对双亲，用于交叉、变异 操作，P(n)代表第n代群体Crossover and mutation p(n);进行交叉

10、和变异操作Learningp(n);自学习过程Evaluatep(h);计算新生成的种群中每个个体的适应度End;实验测试与结果分析交叉率不可选择过小，否则，延缓获得最优解的过程，本程序选择=0.85。变异率的选择对规模大的优化问题影响很大，本程序选=0.1。 群体中的个体数的选取是算法中一个很重要的参数，群体中的个体数目越大，算法就越能找到更好的解，个体数目过小，有可能找不到最优解。本程序种群大小为300。因为有20个城市，每个城市作为染色体中的一个基因，因此在本程序中染色体的长度为20。本程序的循环终止的条件是迭代次数不大于100，因此，最大迭代次数为100。本程序中总共运行10次，得到每

11、次最好的路径、回路总开销和适应度。程序的运行结果如下：参考文献1 遗传书算法理论、应用与软件实现,王小平、曹立明,西安交通大学出版社,20022 机器学习,Tom M.Mitchell 机械工业出版社,2009源代码清单：#include #include #include #include #include #include #include using namespace std;float pcross = 0.85; /交叉率float pmutation = 0.1; /变异率int popsize = 300; /种群大小const int lchrom = 20; /染色体长度i

12、nt gen; /当前世代int maxgen = 100; /最大世代数int run; /当前运行次数int maxruns =10; /总运行次数float max_var = 9 ; /路径最大连接开销!/基因定义(一个城市)struct Genestring name;map linkCost; /该城市到其它城市的路程开销;/染色体定义(到各城市顺序的一种组合)struct Chromvector chrom_gene; /染色体（到各城市去的顺序）float varible; /路程总开销float fitness; /个体适应度 ;/种群定义struct Popvector p

13、op_chrom; /种群里的染色体组 float sumfitness; /种群中个体适应度累计 ;Pop oldpop; /当前代种群Pop newpop; /新一代种群vector genes(lchrom); /保存全部基因/产生一个随机整数(在low和high之间)inline int randomInt(int low,int high)if(low=high)return low;return low+rand()%(high-low+1);/计算一条染色体的个体适应度inline void chromCost(Chrom& chr)float sum=0;for(int i=0

14、;ilinkCostchr.chrom_genei+1;sum += (chr.chrom_gene.front()-linkCostchr.chrom_gene.back();chr.varible=sum;chr.fitness=max_var*(lchrom) - chr.varible;/计算一个种群的个体适应度之和inline void popCost(Pop &pop)float sum=0;for(int i=0;ipop.pop_chrom.size();i+)sum+=pop.pop_chromi.fitness;pop.sumfitness = sum;void outCh

15、rom(Chrom& chr);/随机初始化一条染色体inline void initChrom(Chrom& chr)vector tmp(lchrom);for(int i=0;i1)choose=randomInt(0,tmp.size()-1);chr.chrom_gene.push_back(&genestmpchoose);tmp.erase(tmp.begin()+choose);chr.chrom_gene.push_back(&genestmp0);chromCost(chr);/随机初始化种群inline void initpop(Pop& pop)pop.pop_chro

16、m.reserve(popsize);Chrom tmp;tmp.chrom_gene.reserve(lchrom);for(int i=0;i pick) | i=pop.pop_chrom.size()-1)return i-1; /?为什么返回29就会出错？elsereturn randomInt(0,pop.pop_chrom.size()-2);/精英策略，返回最优秀的一条染色体inline int chooseBest(const Pop& pop)int choose = 0;float best = 0;for(int i = 0;i best)best = pop.pop_

17、chromi.fitness;choose = i;return choose;/染色体交叉操作,由两个父代产生两个子代(顺序交叉OX)inline void crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2)child1.chrom_gene.resize(lchrom);child2.chrom_gene.resize(lchrom);vector:iterator v_iter,p1_beg,p2_beg,c1_beg,c2_beg,p1_end,p2_end,c1_end,c2_endp1_beg =

18、 parent1.chrom_gene.begin(); p2_beg = parent2.chrom_gene.begin();c1_beg = child1.chrom_gene.begin(); c2_beg = child2.chrom_gene.begin();p1_end = parent1.chrom_gene.end(); p2_end = parent2.chrom_gene.end();c1_end = child1.chrom_gene.end(); c2_end = child2.chrom_gene.end();vector v1(parent2.chrom_gene

19、), v2(parent1.chrom_gene); /用于交叉的临时表/随机选择两个交叉点 int pick1 = randomInt(1,lchrom-3);int pick2 = randomInt(pick1+1,lchrom-2);int dist = lchrom-1-pick2; /第二交叉点到尾部的距离/子代保持两交叉点间的基因不变copy(p1_beg+pick1, p1_beg+pick2+1, c1_beg+pick1); copy(p2_beg+pick1, p2_beg+pick2+1, c2_beg+pick1);/循环移动表中元素rotate(v1.begin()

20、, v1.begin()+pick2+1,v1.end(); rotate(v2.begin(), v2.begin()+pick2+1,v2.end();/从表中除去父代已有的元素for(v_iter = p1_beg+pick1; v_iter!=p1_beg+pick2+1; +v_iter)remove(v1.begin(),v1.end(),*v_iter);for(v_iter = p2_beg+pick1; v_iter!=p2_beg+pick2+1; +v_iter)remove(v2.begin(),v2.end(),*v_iter);/把表中元素复制到子代中copy(v1

21、.begin(), v1.begin()+dist, c1_beg+pick2+1);copy(v1.begin()+dist, v1.begin()+dist+pick1, c1_beg);copy(v2.begin(), v2.begin()+dist, c2_beg+pick2+1);copy(v2.begin()+dist, v2.begin()+dist+pick1, c2_beg);/染色体变异操作,随机交换两个基因inline void mutation(Chrom& chr)vector:iterator beg = chr.chrom_gene.begin();int pic

22、k1,pick2;pick1 = randomInt(0,lchrom-1);dopick2 =randomInt(0,lchrom-1);while(pick1=pick2);iter_swap(beg+pick1, beg+pick2);/世代进化(由当前种群产生新种群)void generation(Pop& oldpop,Pop& newpop)newpop.pop_chrom.resize(popsize);int mate1,mate2,j;float pick;float tmp;Chrom gene1,gene2,tmp1,tmp2;gene1.chrom_gene.resiz

23、e(lchrom);gene2.chrom_gene.resize(lchrom);tmp1.chrom_gene.resize(lchrom);tmp2.chrom_gene.resize(lchrom);/将最佳染色体放入下一代mate1 = chooseBest(oldpop);newpop.pop_chrom0 = oldpop.pop_chrommate1; j = 1;/产生两条新染色体doint count = 0;mate1 = selectChrom(oldpop);mate2 = selectChrom(oldpop);pick = float(randomInt(0,10

24、00)/1000;gene1= oldpop.pop_chrommate1;gene2= oldpop.pop_chrommate1;if(pick gene1.fitness)gene1 = tmp1;flag1 = true;if(tmp2.fitness gene2.fitness)gene2 = tmp2;flag2 = true;if(flag1=true & flag2=true) | count 50)newpop.pop_chromj = gene1; newpop.pop_chromj+1 = gene2;break;count+;elsenewpop.pop_chromj.

25、chrom_gene = oldpop.pop_chrommate1.chrom_gene;newpop.pop_chromj+1.chrom_gene = oldpop.pop_chrommate2.chrom_gene;chromCost(newpop.pop_chromj);chromCost(newpop.pop_chromj+1);pick = float(randomInt(0,1000)/1000;if(pick newpop.pop_chromj.fitness & count 50);pick = float(randomInt(0,1000)/1000;if(pick ne

26、wpop.pop_chromj+1.fitness & count 50);/chromCost(newpop.pop_chromj); /计算适应度/chromCost(newpop.pop_chromj+1);j += 2;while(j popsize-1);popCost(newpop); /计算新种群的适应度之和/输出一条染色体信息inline void outChrom(Chrom& chr)coutendl路径:;for(int i=0;ilchrom;i+)coutname;coutendl回路总开销:chr.varibleendl;cout适应度:chr.fitnessend

27、l;int main()cout*用遗传算法解决TSP(旅行商)问题*endl;stringnameslchrom=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T;/基因（城市）名称/用矩阵保存各城市间的路程开销float distlchromlchrom =0, 1, 4, 6, 8, 1, 3, 7, 2, 9, 7, 3, 4, 5, 8, 9, 2, 8, 2, 8,1, 0, 7, 5, 3, 8, 3, 4, 2, 4, 4, 6, 2, 8, 2, 9, 4, 5, 2, 1,4, 7, 0, 3, 8, 3, 7, 9, 1, 2, 5, 8,

28、1, 8, 9, 4, 7, 4, 8, 4,6, 5, 3, 0, 3, 1, 5, 2, 9, 1, 3, 5, 7, 3, 4, 7, 3, 4, 5, 2,8, 3, 8, 3, 0, 2, 3, 1, 4, 6, 3, 8, 4, 5, 2, 8, 1, 7, 4, 7,1, 8, 3, 1, 2, 0, 3, 3, 9, 5, 4, 5, 2, 7, 3, 6, 2, 3, 7, 1,3, 3, 7, 5, 3, 3, 0, 7, 5, 9, 3, 4, 5, 9, 3, 7, 3, 2, 8, 1,7, 4, 9, 2, 1, 3, 7, 0, 1, 3, 4, 5, 2, 7,

29、 6, 3, 3, 8, 3, 5,2, 2, 1, 9, 4, 9, 5, 1, 0, 1, 3, 4, 7, 3, 7, 5, 9, 2, 1, 7,9, 4, 2, 1, 6, 5, 9, 3, 1, 0, 3, 7, 3, 7, 4, 9, 3, 5, 2, 5,7, 4, 5, 3, 3, 4, 3, 4, 3, 3, 0, 5, 7, 8, 4, 3, 1, 5, 9, 3,3, 6, 8, 5, 8, 5, 4, 5, 4, 7, 5, 0, 8, 3, 1, 5, 8, 5, 8, 3,4, 2, 1, 7, 4, 2, 5, 2, 7, 3, 7, 8, 0, 5, 7, 4

30、, 8, 3, 5, 3,5, 8, 8, 3, 5, 7, 9, 7, 3, 7, 8, 3, 5, 0, 8, 3, 1, 8, 4, 5,8, 2, 9, 4, 2, 3, 3, 6, 7, 4, 4, 1, 7, 8, 0, 4, 2, 1, 8, 4,9, 9, 4, 7, 8, 6, 7, 3, 5, 9, 3, 5, 4, 3, 4, 0, 4, 1, 8, 4,2, 4, 7, 3, 1, 2, 3, 3, 9, 3, 1, 8, 8, 1, 2, 4, 0, 4, 3, 7,8, 5, 4, 4, 7, 3, 2, 8, 2, 5, 5, 5, 3, 8, 1, 1, 4, 0, 2, 6,2, 2, 8, 5, 4, 7, 8, 3, 1, 2, 9, 8, 5, 4, 8, 8, 3, 2, 0, 4,8, 1, 4, 2, 7, 1, 1, 5, 7, 5, 3, 3,