基于遗传算法的TSP问题解决
—余小欢B07330230
概述：TSP问题是一个经典的运筹学的组合优化问题，针对此问题，研究人员提出了个中各样的算法，主要有贪婪算法，遗传算法，混沌搜索算法等。在本文中分别用贪婪算法和遗传算法去解决30个城市的最短路径问题，并把两者得到了最优解进行比较，发现用遗传算法解决TSP问题非常具有优越性，同时在文章的最后提出了对此遗传算法进行改进的方向。
1.贪婪算法
x=[18 87 74 71 25 58 4 13 18 24 71 64 68 83 58 54 51 37 41 2 7 22 25 62 87 91 83 41 45 44];
y=[54 76 78 71 38 35 50 40 40 40 42 44 60 58 69 69 62 67 84 94 99 64 60 62 32 7 38 46 26 21 35];
a=zeros(30,30);
for i=1:30
for j=1:30
a(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2); %求取距离矩阵的值end
a(i,i)=1000; %主对角线上的元素置为1000作为惩罚
end
b=0;
c=zeros(30);
for j=1:30
[m,n]=min(a(:,j));
b=b+m; %得到的b值即为贪婪最佳路径的总距离
a(n,:)=1000; %已经选择的最小值对应的行的所有值置为1000作为惩罚
c(j)=n;
end
x1=zeros(30);
y1=zeros(30);
for t=1:30
x1(t)=x(c(t));
y1(t)=y(c(t));
end
plot(x1,y1,'-or');
xlabel('X axis'), ylabel('Y axis'), title('ì°à·?·??'); axis([0,1,0,1]);
axis([0,100,0,100]);
axis on
用贪婪算法得出的最佳路径走遍30个城市所走的路程为449.3845km 其具体的路径图如下：
2.遗传算法
1主函数部分
clc;
clear all;
close all;
global x y
cityfile = fopen( 'city30.txt', 'rt' ); %取30个城市的样本
cities = fscanf( cityfile, '%f %f',[ 2,inf] );
fclose(cityfile);
t=30+1; %城市的数目是30个
s=1500; %样本的数目是1400个
G=300; %运算的代数
c=25; %选择算子中每次替代的样本的数量
x=cities(1,:);
y=cities(2,:);
pc=0.10; %交叉的概率
pm=0.8; %变异的概率
pop=zeros(s,t); %得初始的pop矩阵，矩阵的最后一列表示所在行的样本的路径距离
for i=1:s
pop(i,1:t-1)=randperm(t-1); %随机产生1—（t-1）的t-1个数
end
for k=1:1:G %GA开始
if mod(k,50)==1
k
end
pop=distance(pop); %调用距离函数求距离
pop=select(pop,c); %调用选择函数
p1=rand;
if p1>=pc
pop=cross(pop); %调用交叉函数
end
p2=rand;
if p2>=pm
pop=mutate(pop); %调用变异函数
end
end%GA结束%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%
bestL=min(pop(:,t))
J=pop(:,t);
fi=1./J;
[Oderfi,Indexfi]=sort(fi); %对于fi进行排序
BestS=pop(Indexfi(s),:); %得到最短路
I=BestS;
for i=1:1:t-1
x1(i)=x(I(i));
y1(i)=y(I(i));
end
x1(t)=x(I(1));
y1(t)=y(I(1));
cities_new=[x1;y1];
disp('Best Route is:');disp(cities_new);
pos=[cities_new cities_new(:,1)];
lentemp=0;
for i=1:1:t-1
temp=sqrt((pos(1,i)-pos(1,i+1))^2+(pos(2,i)-pos(2,i+1))^2); lentemp=lentemp+temp;
end
disp('Shortest Length is:');disp(lentemp);
figure(1);
subplot(1,2,1); %窗口分割的左边部分
x(t)=x(1);y(t)=y(1);
plot(x,y,'-or');
xlabel('X axis'), ylabel('Y axis'), title('原始路径');
axis([0,1,0,1]);
axis([0,100,0,100]);
axis on
hold on;
subplot(1,2,2); %窗口分割的右边部分
plot(x1,y1,'-or');
xlabel('X axis'), ylabel('Y axis'), title('最新的路径');
axis([0,1,0,1]);
axis([0,100,0,100]);
axis on
2距离函数
function [pop]=distance(pop)
global x y
[s,t]=size(pop);
for i=1:1:s
dd=0;
pos=pop(i,1:t-1);
pos=[pos pos(:,1)];
for j=1:1:t-1
m=pos(j);
n=pos(j+1);
dd=dd+sqrt((x(m)-x(n))^2+(y(m)-y(n))^2);
end
pop(i,t)=dd;
end
3选择函数
unction [pop]=select(pop,c)
[s,t]=size(pop);
m11=(pop(:,t));
m11=m11';
mmax=zeros(1,c);
mmin=zeros(1,c);
num=1;
while num [a,mmax(num)]=max(m11); %选取当前样本的最大值并记录样本编号给mmax(num) m11(mmax(num))=0; num=num+1; end num=1; while num [b,mmin(num)]=min(m11); m11(mmin(num))=a; num=num+1; end for i=1:c pop(mmax(i),:)=pop(mmin(i),:); %用距离小的C个样本替换距离大的C个样本end 4 交叉函数 function [pop]=cross(pop) [s,t]=size(pop); pop_1=pop; n=randperm(s); %将种群随机排序 for i=1:2:s %随机选择两个交叉点 m=randperm(t-3)+1; crosspoint(1)=min(m(1),m(2)); crosspoint(2)=max(m(1),m(2)); %任意两行交叉 x1=n(i); x2=n(i+1); %将x1左边与x2的左边互换 middle=pop(x1,1:crosspoint(1)); pop(x1,1:crosspoint(1))=pop(x2,1:crosspoint(1)); pop(x2,1:crosspoint(1))=middle; %将x1右边与x2的右边互换 middle=pop(x1,crosspoint(2)+1:t); pop(x1,crosspoint(2)+1:t)=pop(x2,crosspoint(2)+1:t); pop(x2,crosspoint(2)+1:t)=middle; %检查x1左边的重复性并得到x1的左边 for j=1:crosspoint(1) while find(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j)) zhi=find(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j)); %确定重复位置 temp=pop(x2,crosspoint(1)+zhi); pop(x1,j)=temp; end end %检查x1的右边的重复性并得到x1的右边 for j=crosspoint(2)+1:t-1 while find(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j)) zhi=find(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j)); %确定重复的位置 temp=pop(x2,crosspoint(1)+zhi); pop(x1,j)=temp; end end %检查x2左边的重复性并得到x2的左边 for j=1:crosspoint(1) while find(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j)) zhi=find(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j)); 确定重复位置 temp=pop(x1,crosspoint(1)+zhi); pop(x2,j)=temp; end end %检查x2的右边的重复性并得到x2的右边 for j=crosspoint(2)+1:t-1 while find(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j)) zhi=find(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j)); %确定重复的位置 temp=pop(x1,crosspoint(1)+zhi); pop(x2,j)=temp; end end end %生成的新的种群与交叉前进行比较，并取两者最优 [pop]=distance(pop); for i=1:s if pop_1(i,t) pop(i,:)=pop_1(i,:); end end 5 变异函数 function [pop]=mutate(pop) [s,t]=size(pop); pop_1=pop; for i=1:2:s m=randperm(t-3)+1; %随机取两个点 mutatepoint(1)=min(m(1),m(2)); mutatepoint(2)=max(m(1),m(2)); %用倒置变异的方法倒置两个点中间部分的位置 mutate=round((mutatepoint(2)-mutatepoint(1))/2-0.5); for j=1:mutate zhong=pop(i,mutatepoint(1)+j); pop(i,mutatepoint(1)+j)=pop(i,mutatepoint(2)-j); pop(i,mutatepoint(2)-j)=zhong; end end [pop]=distance(pop);%生成的新的种群与变异前比较，并取两者最优 for i=1:s if pop_1(i,t) pop(i,:)=pop_1(i,:); end end 用上面的贪婪算法在matlab里运算的结果如下： 30个城市的初始路线和优化后的路线如下： 从上面的结果可以很明显的发现用遗传算法得到的结果远比用贪婪 算法解得的好。 3、上面的算法改进的方向 1 对于TSP, 好的路径中城市一般都和其临近城市相连接, 很少出现直接同较远城市连接的情况。故而可以采用贪婪法生成初始种群: 以每一城市为起点, 选择比较临近城市作为下站, 然后将固定的两城市经过移位操作移动到编码末尾, 这样以提高初始种群质量, 使搜索 的复杂度降低。 2、采用精英保留策略，把当前代中适应度最好的个体保留到下一代群体, 而不被交叉变异算法破坏掉, 从而保证遗传算法的全局收敛性,而且根据精英个体可能产生适应度更高新个体。 实验六：遗传算法求解TSP问题实验 一、实验目的 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。用遗传算法对TSP问题进行了求解，熟悉遗传算法地算法流程，证明遗传算法在求解TSP问题时具有可行性。 二、实验内容 参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。 对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 1. 最短路径问题 所谓旅行商问题(Travelling Salesman Problem , TSP)，即最短路径问题，就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。 在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法，用 遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。 假设平面上有n个点代表n个城市的位置, 寻找一条最短的闭合路径, 使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形, 或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n- 1)!个, 因此解决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。也就是说, 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。 2. 遗传算法 遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。通过模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索合适的假设从若干初始假设的群体集合开始。当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。每一步，根据给定的适应度评估当前群体的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子。 报告题目：基于Matlab的遗传算法解决TSP问题 说明：该文包括了基于Matlab的遗传算法解决TSP问题的基本说明，并在文后附录了实现该算法的所有源代码。此代码经过本人的运行，没有发现错误，结果比较接近理论最优值，虽然最优路径图有点交叉。 因为本人才疏学浅，本报告及源代码的编译耗费了本人较多的时间与精力，特收取下载积分，还请见谅。若有什么问题，可以私信，我们共同探讨这一问题。 希望能对需要这方面的知识的人有所帮助！ 1.问题介绍 旅行商问题(Traveling Salesman Problem，简称TSP)是一个经典的组合优化问题。它可以描述为：一个商品推销员要去若干个城市推销商品，从一个城市出发，需要经过所有城市后，回到出发地，应如何选择行进路线，以使总行程最短。从图论的角度看，该问题实质是在一个带权完全无向图中。找一个权值最小的Hemilton回路。其数学描述为：设有一个城市集合其中每对城市之间的距离(),i j d c c R +∈，求一对经过C中每个城市一次的路线()12,,n c c c ΠΠΠ?使 ()()() 1111min ,,n i n i i d c c d c c ?ΠΠΠΠ+=+∑其中()12,,12n n ΠΠΠ??是，的一个置换。 2.遗传算法 2.1遗传算法基本原理 遗传算法是由美国J.Holland 教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。 2.2遗传算法的流程 标准的遗传算法包括群体的初始化，选择，交叉，变异操作。流程图如图1所示，其主要步骤可描述如下： （1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。 （2）判断算法的收敛准则是否满足。若满足输出搜索结果；否则执行以下步骤。 基于遗传算法的TSP问题研究 摘要：旅行商问题是一个经典的优化组合问题，本文采用遗传算法来求解旅行商问题，深入讨论了遗传算法解决TSP问题的求解过程，并通过MATLAB对算法进行了实现，最后对实验结果进行分析。 关键字：旅行商问题；遗传算法 Abstract:The traveling salesman problem is a classic optimal combination problem. In this paper, we use genetic algorithm to solve the TSP problem.We discusse the solving process, and the algorithm is realized by MATLAB. Finally, the experimental results are analyzed. Key words: Traveling Salesman Problem; Genetic Algorithm 1 引言 旅行商问题（Traveling Salesman Problem,TSP）的原始问题为：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为 ij d，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路线最短。这是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP问题的可行解数目与城市数目N是成指数型增长的，是一个NP-hard问题，即不存在多项式时间算法。因而一般只能近似求解，遗传算法（Genetic Algorithm,GA）是求解该问题的较有效的方法之一，当然还有如粒子群算法，蚁群算法，神经网络算法等优化算法也可以进行求解。遗传算法是美国学者Holland根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文采用MATLAB来实现遗传算法解决TSP问题。 2 旅行商问题 旅行商问题可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n 个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。图论模型如图1所示，构造一个图G=(V,e),顶点V表示城市，边e表示连接两城市的路，边上的权()e W表示距离（或时间或费用）。于是旅行推销员问题就成为在加权图中寻找一条经过每个顶点正好一次的最短圈的问题，即求最佳Hamilton 圈的问题。 A B C D E F 45 26 3839 68 59 92 62 65 73 83 38 93 87 94 图1 TSP问题的图论模型 TSP问题是NP-hard问题，。也就是说,对于大型网络(赋权图),目前还没有一个精确求解TSP问题的有效算法，因此只能找能求出相当好（不一 遗传算法解决TSP问题 姓名： 学号： 专业: 问题描叙 TSP问题即路径最短路径问题，从任意起点出发（或者固定起点），依次经过所有城市，一个城市只能进入和出去一次，所有城市必须经过一次，经过终点再到起点，从中寻找距离最短的通路。 通过距离矩阵可以得到城市之间的相互距离，从距离矩阵中的到距离最短路径，解决TSP问题的算法很多，如模拟退火算法，禁忌搜索算法，遗传算法等等，每个算法都有自己的优缺点，遗传算法收敛性好，计算时间少，但是得到的是次优解，得不到最有解。 算法设计 遗传算法属于进化算法的一种，它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子：选择、交叉和变异。 数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。 生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法。算法中称遗传的生物体为个体，个体对环境的适应程度用适应值（fitness）表示。适应值取决于个体的染色体，在算法中染色体常用一串数字表示，数字串中的一位对应一个基因。一定数量的个体组成一个群体。对所有个体进行选择、交叉和变异等操作，生成新的群体，称为新一代遗传算法计算程序的流程可以表示如下： 第一步准备工作 （1）选择合适的编码方案，将变量（特征）转换为染色体（数字串，串长为m）。通常用二进制编码。 （2）选择合适的参数，包括群体大小（个体数M）、交叉概率PC和变异概率Pm。 （3）确定适应值函数f（x）。f（x）应为正值。 第二步形成一个初始群体（含M个个体）。在边坡滑裂面搜索问题中，取已分析的可能滑裂面组作为初始群体。 第三步对每一染色体（串）计算其适应值fi，同时计算群体的总适应值。 第四步选择 1.遗传算法解决TSP 问题（附matlab源程序） 2.知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市 3.只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其 4.旅行路线的总长度最短？ 5.用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij) 6.是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶 7.点且每个顶点只通过一次的具有最短距离的回路。 8.这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商 9.问题(dij≠dji,,任意i,j=1,2,3，…,n)。 10.若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中 11.ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为： 12.min l=σd(t(i),t(i+1)) （i=1,…,n） 13.旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目 14.与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法 15.求其近似解。 16.遗传算法： 17.初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数 18.，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。 19.适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)). 20.评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中 21.的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被 22.选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=al 23.pha*(1-alpha).^(i-1) 。[随机规划与模糊规划] 24.选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个 25.染色体。赌轮是按每个染色体的适应度进行选择染色体的。 26.step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1, 27.…pop-size. 28.step2、从区间(0,pop-size)中产生一个随机数r； 29.step3、若qi-1 step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。 30.grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的 31.染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现 32.。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如： 33.8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1 34.对应： 35.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。 36.交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到pop-size重复以下过 37.程：从[0，1]中产生一个随机数r，如果r 将所选的父代两两组队，随机产生一个位置进行交叉，如： 38.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 39. 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1 40.交叉后为： 41.8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 42. 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1 43.变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r 选择多个染色体vi作为父代。对每一个 选择的父代，随机选择多个位置，使其在每位置 TSP问题的遗传算法求解 一、问题描述 假设有一个旅行商人要拜访N个城市，要求他从一个城市出发，每个城市最多拜访一次，最后要回到出发的城市，保证所选择的路径长度最短。 二、算法描述 （一）算法简介 遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。（摘自百度百科）。 （二）遗传算子 遗传算法中有选择算子、交叉算子和变异算子。 选择算子用于在父代种群中选择进入下一代的个体。 交叉算子用于对种群中的个体两两进行交叉，有Partial-MappedCrossover、OrderCrossover、Position-basedCrossover等交叉算子。 变异算子用于对种群中的个体进行突变。 （三）算法步骤描述 遗传算法的基本运算过程如下： 1.初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P 2.个体评价：计算种群P中各个个体的适应度 3.选择运算：将选择算子作用于群体。以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代 4.交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉 5.变异运算：在变异概率的控制下，对群体中的个体两两进行变异，即对某一个体的基因进行随机调整 6.经过选择、交叉、变异运算之后得到下一代群体P1。 重复以上1-6，直到遗传代数为T，以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。 三、求解说明 （一）优化目标 给定二维数据int[][]pos用于存储各个城市的坐标，采用欧式距离代表城市之间的距离。利用遗传算法，找到不重复遍历所有城市的路径中，所走距离最短的路径。 （二）选择算子 选择算子采用轮盘赌选择，以每个个体的适应度为基础，为每个个体计算累积概率。 用遗传算法解决旅行商问题 姓名：王晓梅 学号：1301281 班级：系统工程6班 一、问题背景 有一个销售员，要到n 个城市推销商品，他要找出一个包含所有n 个城市的具有最短路程的环路。 现在假设有10个城市，他们之间的距离如下。 { 0, 107, 241, 190, 124, 80, 316, 76, 152, 157}, { 107, 0, 148, 137, 88, 127, 336, 183, 134, 95}, { 241, 148, 0, 374, 171, 259, 509, 317, 217, 232}, { 190, 137, 374, 0, 202, 234, 222, 192, 248, 42}, { 124, 88, 171, 202, 0, 61, 392, 202, 46, 160}, { 80, 127, 259, 234, 61, 0, 386, 141, 72, 167}, { 316, 336, 509, 222, 392, 386, 0, 233, 438, 254}, { 76, 183, 317, 192, 202, 141, 233, 0, 213, 188}, { 152, 134, 217, 248, 46, 72, 438, 213, 0, 206}, { 157, 95, 232, 42, 160, 167, 254, 188, 206, 0} 将这10个城市分别编码为0,1,2,3,4,5,6,7,8,9。要求走完这10个城市，目标是使走的距离最短。 二、建立模型 ),...,1,(1) ,...,1,(1. .)(min 11 11n j j i n i j i t s j i n j ij n i ij ij n i n j ij x x d x =≠==≠=≠∑∑∑∑==== 三、设计算法 1、种群初始化 （1）一条染色体的初始化 10个城市分别对应0~9这十个数，每个染色体代表一个解决方法，即0~9这十个数的一种排序方式，可随机产生一个数，用取余的方法得到一个0~9的数，依次得到与前面不重复的十个数，构成一个染色体。 （2）种群的初始化 这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。 人工智能实验报告 实验六遗传算法实验II 一、实验目的： 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP 问题的流程并测试主要参数对结果的影响。 二、实验原理： 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。 三、实验内容： 1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。 2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 4、上交源代码。 四、实验报告要求： 1、画出遗传算法求解TSP问题的流程图。 开始初始化种群（随机产生城市坐标确定种群规模、迭代次数、个体选择式、交叉概率、变异概率计算染 色体适应度值（城市间的欧氏距离按某个选择概率选择个YE个体交个体变P迭代总次N输入适应度最高的结 基于遗传算法的TSP问题解决 —余小欢B07330230 概述：TSP问题是一个经典的运筹学的组合优化问题，针对此问题，研究人员提出了个中各样的算法，主要有贪婪算法，遗传算法，混沌搜索算法等。在本文中分别用贪婪算法和遗传算法去解决30个城市的最短路径问题，并把两者得到了最优解进行比较，发现用遗传算法解决TSP问题非常具有优越性，同时在文章的最后提出了对此遗传算法进行改进的方向。 1.贪婪算法 x=[18 87 74 71 25 58 4 13 18 24 71 64 68 83 58 54 51 37 41 2 7 22 25 62 87 91 83 41 45 44]; y=[54 76 78 71 38 35 50 40 40 40 42 44 60 58 69 69 62 67 84 94 99 64 60 62 32 7 38 46 26 21 35]; a=zeros(30,30); for i=1:30 for j=1:30 a(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2); %求取距离矩阵的值end a(i,i)=1000; %主对角线上的元素置为1000作为惩罚 end b=0; c=zeros(30); for j=1:30 [m,n]=min(a(:,j)); b=b+m; %得到的b值即为贪婪最佳路径的总距离 a(n,:)=1000; %已经选择的最小值对应的行的所有值置为1000作为惩罚 c(j)=n; end x1=zeros(30); y1=zeros(30); for t=1:30 x1(t)=x(c(t)); y1(t)=y(c(t)); end plot(x1,y1,'-or'); xlabel('X axis'), ylabel('Y axis'), title('ì°à·?·??'); axis([0,1,0,1]); axis([0,100,0,100]); axis on 用贪婪算法得出的最佳路径走遍30个城市所走的路程为449.3845km 其具体的路径图如下： 2.遗传算法 1主函数部分 clc; clear all; 实验题目：的遗传算法解决TSP 问题姓名：谢稳文 班级：智能1001 学号：20100840126 一:问题描述 旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行商问题,货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。 二:遗传算法的基本原理 遗传算法是由美国J. Holland 教授于1975 年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器 学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智一样，都是对今后十年的计算技术有重大影响的关键技术”。 基本步骤为: 标准的遗传算法包括群体的初始化，选择，交叉，变异操作。所示，其主要步骤可描述如下： （1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。 （2）判断算法的收敛准则是否满足。若满足输出搜索结果；否则执行以下步骤。 （3）根据适配值大小以一定方式执行选择操作。 （4）按交叉概率Pc 执行交叉操作。 （5）按变异概率Pm 执行变异操作。 （6）返回步骤（2） 算法流程图为: 遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机 #include "stdio.h" #include "stdlib.h" #include "conio.h" #include "math.h" #include "time.h" #define num_C 10 //城市个数 #define N 100 //群体规模为100 #define pc 0.9 //交叉概率为0.9 #define pm 0.1 //变异概率为10% #define ps 0.6 //进行选择时保留的比例 #define genmax 200 //最大代数200 int RandomInteger(int low,int high); void Initial_gen(struct unit group[N]); void Sort(struct unit group[N]); void Copy_unit(struct unit *p1,struct unit *p2); int search_son(int son[num_C],int k); void Cross(struct unit *p1,struct unit *p2); void Varation(struct unit group[N],int i); void Evolution(struct unit group[N]); void Calculate_cost(struct unit *p); void Print_optimum(struct unit group[N]); /* 定义个体信息*/ typedef struct unit { int path[num_C]; //个体的路径信息 int cost; //个体代价值 }; struct unit group[N]; //种群变量group int num_gen=0; //记录当前达到第几代 /***************************************************************************/ /* 城市间的距离信息：*/ /* 北京天津武汉深圳长沙成都杭州西安拉萨南昌*/ /* (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) */ /* 北京(0) 0 118 1272 2567 1653 2097 1425 1177 3947 1574 */ /* 天津(1) 118 0 1253 2511 1633 2077 1369 1157 3961 1518 */ /* 武汉(2) 1272 1253 0 1462 380 1490 821 856 3660 385 */ /* 深圳(3) 2567 2511 1462 0 922 2335 1562 2165 3995 933 */ /* 长沙(4) 1653 1633 380 922 0 1700 1041 1135 3870 456 */ /* 成都(5) 2097 2077 1490 2335 1700 0 2311 920 2170 1920 */ /* 杭州(6) 1425 1369 821 1562 1041 2311 0 1420 4290 626 */ /* 西安(7) 1177 1157 856 2165 1135 920 1420 0 2870 1290 */ /* 拉萨(8) 3947 3961 3660 3995 3870 2170 4290 2870 0 4090 */ /* 南昌(9) 1574 1518 385 993 456 1920 626 1290 4090 0 */ /***************************************************************************/ 邮局订阅号：82-946360元/年技术创新 博士论坛 《PLC 技术应用200例》 您的论文得到两院院士关注 基于遗传算法的TSP 问题求解算法及其系统 A TSP Solving Algorithm and System Based on Genetic Algorithm (北京工业大学) 代桂平王勇侯亚荣 DAI Gui-ping WANG Yong HOU Ya-rong 摘要:TSP 问题为组合优化中的经典的NP 完全问题。针对这一问题,首先设计了基于遗传算法的求解算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设定、交叉算子设定以及变异算子设定等,给出了基于遗传算法求解TSP 问题的一般性流程,然后设计并实现了基于遗传算法的TSP 问题求解系统,给出了求解系统的体系结构,并给出了求解系统基于Ja -va 语言的实现机制,最后通过实验结果的分析,表明了算法具有较好的寻优性能,系统具有较好的实用性。关键词:遗传算法;旅行商问题;体系结构 中图分类号:TP319 文献标识码:A Abstract:TSP is a representative combinational optimization problem and a NP-hard problem.Solving algorithm based on genetic al -gorithm is designed,including chromosome encoding,fitness function design,end condition design,selection operator design,crossover operator design and mutation operator design et al.Then a solving system is designed and implemented:the architecture of solving system is given and implementation mechanism based on Java language is presented.Finally,it is illustrated that the algorithm has good performance and the system has good practicability through analysis of experimental results.Key words:Genetic Algorithm;TSP Problem;Architecture 文章编号:1008-0570(2010)02-1-0015-02 1引言 TSP 问题为组合优化中的经典问题,已经证明为一NP 完全问题,即其最坏情况下的时间复杂性随着问题规模的扩大按指数方式增长,到目前为止不能找到一个多项式时间的有效算法。TSP 问题可描述为:已知n 个城市相互之间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,如何安排才使其所走路线最短。TSP 问题不仅仅是一个简单的组合优化问题,其他许多的NP 完全问题可以归结为TSP 问题,如邮路问题、装配线上的螺帽问题和产品的生产安排问题等,使得TSP 问题的有效求解具有重要的意义。 遗传算法是一种进化算法,其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体,再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息,最终生成符合优化目标的染色体。实践证明,遗传算法对于解决TSP 问题等组合优化问题具有较好的寻优性能。 许多学者在基于遗传算法求解TSP 问题方面做了很多的工作,这些工作大致可以分为两类:一类是基于经典遗传算法或者遗传算法变种对于TSP 问题进行了求解;一类是采用遗传算法对TSP 问题或者TSP 问题的变种进行了求解。 在第一类中,文献使用一种改进的多搜索方法的遗传算法对TSP 问题进行了求解;文献使用最小约束的编码和交叉的遗传算法求解了TSP 问题;王宇平等人使用量子遗传算法来求解遗传算法;郑立平等人使用混合杂交的遗传算法求解了TSP 问题;戴晓明等人采用混合并行遗传算法对TSP 问题进行了求解。在第二类中,分别利用遗传算法对动态TSP 问题、欧氏平面 TSP 问题、 多目标TSP 问题进行了求解。此外,文献等利用其它优化算法对TSP 问题进行了求解。 上述算法求解TSP 问题都取得较好的效果,但是都没有涉及求解系统的设计与实现;不同的是,本文除了一种整数编码的遗传算法来求解TSP 问题外,还重点给出了求解系统设计与实现,实验结果表明算法具有较好的寻优性能,求解系统具有较好的实用性。本文设计了一个基于遗传算法的TSP 问题求解算法,基于Java 语言设计并实现了求解系统。本文如下组织:在第二节中介绍了相关的研究工作;在第三节中设计了基于遗传算法的求解算法;在第四节设计了求解系统的体系结构和基于Ja －va 语言的实现机制;在第五节给出了实验结果并对实验结果作了分析;最后对全文的内容进行了总结。 3算法设计 1)染色体编码:在遗传算法运算之前,需要针对问题设计染色体,包括基因字串的长度以及基因代表的含义,也就是对要搜索空间的可行解以编码的形式呈现。一般的编码方式采用二进制编码,此外也有整数、实数、文字等编码方式。采用整数编码的方式,对于n 个城市的TSP 问题,染色体分为n 段,其中每一段为对应城市的编号,如对20个城市的TSP 问题{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},则20|18|17|3|5|4|6|1|2|9|8||7|13|12|16|14|15|11|10|19就是一个合法的染色体。在生成染色体时需要进行染色体合法性检查环节,即染色体恰好是n 个城市编码的一个排列,不能有重复的城市代码出现。 2)种群初始化:在完成染色体编码以后,必须产生一个初始种群作为起始解,所以需要首先决定初始化种群的数目。初始化种群的数目一般根据经验得到,如果初始化种群的数目太大,可能会消耗过多的计算时间,但是如果太小可能难以达到预期的效果而导致过早收敛。我们在种群初始化时采用随机方式产生, 代桂平:讲师博士 15-- 遗传算法求解TSP 问题MATLAB 实现 摘要：旅行商问题（TSP ）是一个经典的优化组合问题，本文采用遗传算法来求解TSP 问题，深入讨论了遗传算法解决TSP 问题的求解过程，并通过MATLAB 对算法进行了实现，最后对实验结果进行分析，并与粒子群算法进行对比和分析。 关键字：TSP ；遗传算法；粒子群算法 0.引言 旅行商问题是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP 问题的可行解数目与城市数目N 是成指数型增长的，是一个NP 难问题，因而一般只能近似求解，遗传算法（GA ）是求解该问题的较有效的方法之一，当然还有如粒子群算法，蚁群算法，神经网络算法等优化算法也可以进行求解。遗传算法是美国学者Holland 根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文采用MATLAB 来实现遗传算法解决TSP 问题。 1.旅行商问题 旅行商问题可以具体描述为：已知n 个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n 个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。用图论术语来表示，就是有一个图g=(v,e),其中v 是定点5，e 是边集，设d=(dij)是有顶点i 和顶点j 之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的最短距离的回路。若对与城市v={v1,v2,v3…vn}的一个访问顺序为t=(t1,t2,t3…,tn)，其中ti ∈v(i=1,2,..n),且记tn+1=t1,则旅行上问题的数学模型为式1： min ((),(1))(1,....,)I d t i t i i n δ =+ = （1） 2.遗传算法与粒子群算法 2.1遗传算法 遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。 2.2遗传算法的过程 遗传算法的基本过程是： 1. 初始化群体。 2. 计算群体上每个个体的适应度值 3. 由个体适应度值所决定的某个规则选择将进入下一代个体。 4. 按概率Pc 进行交叉操作。 5. 按概率Pm 进行变异操作。 6. 没有满足某种停止条件，则转第2步，否则进入第7步。 基于遗传算法解决TSP问题 摘要 题目要求给出环游全国全部省会的最短路径方案，是传统的TSP问题，本文将图表数据数字化后，将其转变成为线性规划问题，进而采取遗传算法用Matlab求解出理论上的最短路径与路线图。通过第一问求出的路线顺序结合实际情况求解出实际情况下的最短路径与最短时间。 针对第一问，首先建立基本TSP模型，求出其线性规划方程组，用Matlab 对地图做出基本处理，求出其像素坐标的矩阵。将省会城市初始化为种群数据，用遗传算法求解出模型最优解，即最短路径大小与旅游城市顺序。 针对第二问，由于遗传算法求出的是近似最优解，以及实际道路情况不可能是直线距离，所以理论数据与实际有一定差别。将旅行顺序求解出后，需要根据实际道路情况重新求解出最短路径大小，并根据题目所给条件求解出最短时间。根据实际情况，求得最后的最短路径长度为20402.9公里，时间为45天。 题目中给出城市转化为图集，一共有33个顶点，数据较大，用Dijkstra 算法和Floyd算法虽然答案可能更精确，但数据处理量大，时间复杂度高。采用遗传算法可以得到近似最优解，并且精简了时间复杂度。 关键词：最短路径 TSP问题线性规划遗传算法 一、问题重述 如果从杭州出发，要想开车走遍全国所有的省会城市，而且在到了每个省会城市以后都必须住一晚，第二天早上才能出发，安全起见每天开车时间最多在8小时左右，车速视实际路况而定，一般高速公路可以取平均车速100公里/小时左右，不是高速公路平均车速取60公里/小时左右，从杭州出发要走遍所有省会城市以后回到杭州，开车里程最少需要多少公里？最少需要多少时间？（暂不考虑台湾省） 二、问题分析 题目要求求出最短路径与时间是典型的TSP问题，即要用最短的总路径走遍所有城市，此处需要设立一个二元组)) E V，并且求出一个点的邻接矩阵。 G ( ( ), (G 根据经典的TSP模型，得出一般的线性规划方程组。解TSP模型的一般算法有Dijkstra算法和Floyd算法，由于TSP问题是典型的NP难题，其可能路径数目与城市总数目n是呈指数型增长，并不适合用以上两种算法。另外常用来解决TSP问题的退火算法受概率和退火过程影响，可能运算起来十分缓慢。为了精简时间复杂度，故选取了遗传算法将图形数据初始为种群数据进行计算。并且随着实验六：遗传算法求解TSP问题实验分析
基于Matlab的遗传算法解决TSP问题的报告
基于遗传算法的TSP问题研究
遗传算法解决TSP问题
遗传算法解决TSP问题的matlab程序
TSP问题的遗传算法求解
用遗传算法解决旅行商问题
完整word版遗传算法求解TSP问题实验报告
基于遗传算法的TSP问题解决
基于遗传算法的TSP问题解决【精品毕业设计】(完整版)
遗传算法及其在TSP问题中的应用
遗传算法解决10城市TSP问题程序源代码
基于遗传算法的TSP问题求解算法及其系统
遗传算法求解TSP问题MATLAB实现
基于遗传算法解决TSP问题
相关主题
文本预览