人工智能实验三-TSP问题.doc

【实验名称】 人工智能实验三：遗传算法求解TSP问题遗传算法参数（SGA）=（C，E，P0，M，）C 个体的编码方法；E 个体的适应度评价函数；P0初始群体；M 群体大小，一般取20100；选择算子，SGA使用比例算子；交叉算子，SGA使用单点交叉算子；变异算子，SGA使用基本位变异算子；算法终止条件，一般终止进化代数为100500；实验代码：#include #include #include #include #include #include #include using namespace std;float pcross = 0.80; /交叉率float pmutation = 0.1; /变异率int popsize = 300; /种群大小const int lchrom = 20; /染色体长度int 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 pop_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;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 outChrom(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_chrom.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_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_end;p1_beg = 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), 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(), 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.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 pick1,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.resize(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,1000)/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.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 newpop.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.fitnessendl;int main()cout*用遗传算法解决TSP问题*endl;cout* E01114336 朱蓉蓉*endl; string nameslchrom=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, 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, 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, 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, 3, 5, 4, 4, 7, 6, 4, 0; /初始化基因(所有基因都保存在genes中)int i,j;for(i=0;ilchrom;i+) =namesi;for(j=0;jlchrom;j+)genesi.linkCost&genesj = distij;/输出配置信息coutn染色体长度:lchromn种群大小:popsizen交叉率:pcrossn变异率:pmutation;coutn最大世代数:maxgenn总运行次数:maxrunsn路径最大连接开销:max_varendl;/输出路径信息coutendl ;for(i=0;ilchrom;i+)