姜堰 做网站,芜湖做网站都有哪些,app是什么软件,广西网站建设推广大概需要多少钱问题定义#xff1a;巡回旅行商问题给定一组n个城市和俩俩之间的直达距离#xff0c;寻找一条闭合的旅程#xff0c;使得每个城市刚好经过一次且总的旅行距离最短。TSP问题也称为货郎担问题#xff0c;是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1… 问题定义巡回旅行商问题给定一组n个城市和俩俩之间的直达距离寻找一条闭合的旅程使得每个城市刚好经过一次且总的旅行距离最短。TSP问题也称为货郎担问题是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年由美国兰德公司推动TSP成为近代组合优化领域的典型难题。TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。近年来有很多解决该问题的较为有效的算法不断被推出例如Hopfield神经网络方法模拟退火方法以及遗传算法方法等。TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解对于常规方法和现有的计算工具而言存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题是很自然的想法。基本遗传算法可定义为一个8元组(SGA)(CEP0MΦГΨΤ)C ——个体的编码方法SGA使用固定长度二进制符号串编码方法E ——个体的适应度评价函数P0——初始群体M ——群体大小一般取20—100Ф——选择算子SGA使用比例算子Г——交叉算子SGA使用单点交叉算子Ψ——变异算子SGA使用基本位变异算子Т——算法终止条件一般终止进化代数为100—500问题的表示对于一个实际的待优化问题首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决TSP一个旅程很自然的表示为n个城市的排列但基于二进制编码的交叉和变异操作不能适用。路径表示是表示旅程对应的基因编码的最自然最简单的表示方法。它在编码解码存储过程中相对容易理解和实现。例如旅程(5-1-7-8-9-4-6-2-3)可以直接表示为(5 1 7 8 9 4 6 2 3)。产生初始种群一是完全随机产生它适合于对问题的解无任何先验知识的情况。随机性较强因而也较公正。二是某些先验知识可转变为必须满足的一组要求然后在满足这些要求的解中在随机地选取样本。这样选择初始种群可使遗传算法更快的达到最优解。种群有一定的目标性和代表性但取例不如完全随机的广泛而且先验知识是否可靠也是一个问题。适应度函数遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。TSP的目标是路径总长度为最短路径总长度的倒数就可以为TSP的适应度函数选择一般地说选择将使适应度较大(优良)个体有较大的存在机会而适应度较小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制令Σfi表示群体的适应度值之总和fi表示种群中第i个染色体的适应度值它产生后代的能力正好为其适应度值所占份额fiΣfi。交叉基于路径表示的编码方法要求一个个体的染色体编码中不允许有重复的基因码也就是说要满足任意一个城市必须而且只能访问一次的约束。基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件。部分匹配交叉操作要求随机选取两个交叉点以便确定一个匹配段根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体。变异遗传算法解决TSP 问题基于二进值编码的变异操作不能适用不能够由简单的变量的翻转来实现在TSP问题中个体的编码是一批城市的序列随机的在这个序列抽取两个城市然后交换他们的位置。这样就实现了个体编码的变异算法如下产生两个0到1之间的随机实数将这两个随机实数转化为0到n(城市数)-1之间的随机整数将这两个随机整数指代的城市进行交换流程图代码主函数代码clear;clc;tStart tic;% 算法计时器%%%%%%%%%%%%自定义参数%%%%%%%%%%%%%[cityNum,cities] Read(dsj1000.tsp);cities cities;%cityNum100;maxGEN 1000;popSize 100; % 遗传算法种群大小crossoverProbabilty 0.9; %交叉概率mutationProbabilty 0.1; %变异概率%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%gbest Inf;%随机生成城市位置%citiesrand(2,cityNum)*100;%100是最远距离%计算上述生成的城市距离distances calculateDistance(cities);%生成种群每个个体代表一个路径pop zeros(popSize, cityNum);for i1:popSize pop(i,:) randperm(cityNum);endoffspring zeros(popSize,cityNum);%保存每代的最小路劲便于画图minPathes zeros(maxGEN,1);%GA算法for gen1:maxGEN % 计算适应度的值即路径总距离 [fval, sumDistance, minPath, maxPath] fitness(distances, pop); % 轮盘赌选择 tournamentSize4; %设置大小 for k1:popSize % 选择父代进行交叉 tourPopDistanceszeros( tournamentSize,1); for i1:tournamentSize randomRow randi(popSize); tourPopDistances(i,1) sumDistance(randomRow,1); end % 选择最好的即距离最小的 parent1 min(tourPopDistances); [parent1X,parent1Y] find(sumDistanceparent1,1, first); parent1Path pop(parent1X(1,1),:); for i1:tournamentSize randomRow randi(popSize); tourPopDistances(i,1) sumDistance(randomRow,1); end parent2 min(tourPopDistances); [parent2X,parent2Y] find(sumDistanceparent2,1, first); parent2Path pop(parent2X(1,1),:); subPath crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉 subPath mutate(subPath, mutationProbabilty);%变异 offspring(k,:) subPath(1,:); minPathes(gen,1) minPath; end fprintf(代数:%d 最短路径:%.2fKM \n, gen,minPath); % 更新 pop offspring; % 画出当前状态下的最短路径 ifminPath gbest gbest minPath; paint(cities,pop,gbest,sumDistance,gen); endendfigureplot(minPathes,MarkerFaceColor,red,LineWidth,1);title(收敛曲线图(每一代的最短路径));set(gca,ytick,500:100:5000);ylabel(路径长度);xlabel(迭代次数);gridontEnd toc(tStart);fprintf(时间:%d 分 %f 秒.\n,floor(tEnd/60),rem(tEnd,60));function[distances] calculateDistance(city)%计算距离 [~,col] size(city); distances zeros(col); fori1:col forj1:col distances(i,j) distances(i,j) sqrt((city(1,i)-city(1,j))^2 (city(2,i)-city(2,j))^2 ); end endendfunction[childPath] crossover(parent1Path,parent2Path,prob)%交叉 random rand(); ifprob random [l,length] size(parent1Path); childPath zeros(l,length); setSize floor(length/2)-1; offset randi(setSize); forioffset:setSizeoffset-1 childPath(1,i) parent1Path(1,i); end iterator i1; j iterator; whileany(childPath 0) ifj length j 1; end ifiterator length iterator 1; end if~any(childPath parent2Path(1,j)) childPath(1,iterator) parent2Path(1,j); iterator iterator 1; end j j 1; end else childPath parent1Path; endendfunction[fitnessvar,sumDistances,minPath,maxPath] fitness(distances,pop)%计算整个种群的适应度值 [popSize,col] size(pop); sumDistances zeros(popSize,1); fitnessvar zeros(popSize,1); fori1:popSize forj1:col-1 sumDistances(i) sumDistances(i) distances(pop(i,j),pop(i,j1)); end end minPath min(sumDistances); maxPath max(sumDistances); fori1:length(sumDistances) fitnessvar(i,1)(maxPath- sumDistances(i,1)0.000001)/ (maxPath-minPath0.00000001); endendfunction[mutatedPath] mutate(path,prob)%对指定的路径利用指定的概率进行更新 random rand(); ifrandom prob [l,length] size(path); index1 randi(length); index2 randi(length); %交换 temp path(l,index1); path(l,index1) path(l,index2); path(l,index2)temp; end mutatedPath path;endfunction[output_args] paint(cities,pop,minPath, totalDistances, gen) gNumbergen; [~,length] size(cities); xDots cities(1,:); yDots cities(2,:); %figure(1); title(GA TSP); plot(xDots,yDots,p,MarkerSize,14,MarkerFaceColor,blue); xlabel(经度); ylabel(纬度); axisequal holdon [minPathX,~] find(totalDistancesminPath,1,first); bestPopPath pop(minPathX,:); bestX zeros(1,length); bestY zeros(1,length); forj1:length bestX(1,j) cities(1,bestPopPath(1,j)); bestY(1,j) cities(2,bestPopPath(1,j)); end title(GA TSP); plot(bestX(1,:),bestY(1,:),red,LineWidth,1.25); legend(城市,路径); axisequal gridon %text(5,0,sprintf(迭代次数: %d 总路径长度: %.2f,gNumber, minPath),FontSize,10); drawnow holdoffendfunction[n_citys,city_position] Read(filename)fid fopen(filename,rt);location[];A [12];tline fgetl(fid);whileischar(tline) if(strcmp(tline,NODE_COORD_SECTION)) while~isempty(A) Afscanf(fid,%f,[3,1]); ifisempty(A) break; end location[location;A(2:3)]; end end tline fgetl(fid); if strcmp(tline,EOF) break; endend[m,n]size(location);n_citys m;city_positionlocation;fclose(fid);end结果测试数据初始态终态收敛曲线可以看到当城市数量适中时迭代500次最短路径长度有收敛的趋势。当城市数目较多时迭代500次仍然不收敛可能的问题是陷入了局部最优解。总结与观点难点是交叉算法的设计由于TSP问题和一般的NP问题不一样每个个体的每个维度具有唯一性因此在交叉的时候要注意不能有重复的值。本次实验采用的是部分匹配交叉先从第一个父代选出一个偏移量从偏移量后的部分点加入到子代接下来从第二个父代选择第一代没有选择的部分点移到子代中。当城市数量较多时大于50个城市迭代多次GA仍然不收敛可能的问题是陷入了局部最优解因此对GA算法进行改进怡跳出局部最优解可以采用类似于PSO或者蚁群算法的思想。数据集下载https://github.com/xyjigsaw/Dataset转载自https://www.omegaxyz.com/2019/01/21/matlab-tsp-all/作者OmegaXYZhttps://www.omegaxyz.com
