遗传算法解决TSP问题

%vision5更新内容

%最大突变概率

%突变概率将随着算法的收敛而增大

%最终增大到最大突变概率

%----------------------- 遗传算法解决TSP 问题 ----------------------- %..................

%******************参数及参数说明******************

%-------nCity：城市数量，参数取值范围，>2 整数；

%-------xyCity：城市二维坐标，本例由计算机随机产生，范围(0,1)，假定起始城市为第nCity 个城市；

%-------dCity：城市间距离矩阵，本例考虑城市间往返距离相等，且定义距离为欧几里德范数；

%-------nPopulation：种群个体数量；

%-------Population：种群，nPopulation*(nCity-1)矩阵，每行由{1,2,...,nCity-1}某一个全排列构成；

%-------generation：算法终止条件一，迭代代数；

%-------nR：算法终止条件二，最短路径值连续nR 代不变；

%-------R：最短路径；

%-------Rlength：最短路径长度。

%-------Shock：当最优个体保持一段时期不变后，产生震荡

function

[R,Rlength]=GA_TSP(xyCity,dCity,Population,nPopulation,pCrossover,percent,pMutation,generation,nR,rr,rangeCity,rR,moffspring,record,pi,Sho ck,maxShock)

clear ALL

%10个城市坐标

%xyCity=[0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;

% 0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634];

%10 cities d'=2.691

%--------------------------------------------------------------------------

%30个城市坐标

xyCity=[25 62;7 64;2 99;68 58;71 44];

xyCity=[41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;

83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50];

%30 cities d'=423.741 by D B Fogel

%--------------------------------------------------------------------------

%50个城市坐标

%xyCity=[31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25

55;16 57;

%17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;

%27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33; %58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67];

%50 cities d'=427.855 by D B Fogel

%--------------------------------------------------------------------------

%75个城市坐标

%xyCity=[48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;

%55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;

%20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50; %45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;

%44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56;

%10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26]; %75cities d'=549.18 by D B Fogel

figure(1)

axis([0 10 0 10]) grid on

scatter(xyCity(:,1),xyCity(:,2),'x')

grid on

nCity=size(xyCity,1);

for

i=1:nCity %计算城市间距离，假设距离为欧几里德范数

for j=1:nCity

dCity(i,j)=((xyCity(i,1)-xyCity(j,1))^2+(xyCity(i,2)-xyCity(j,2))^2)^0.5;

end

end %计算城市间距离，假设距离为欧几里德范数 xyCity %显示城市坐标

dCity %显示城市距离矩阵

%初始种群

k=input('取点操作结束'); %取点时对操作保护

disp('-------------------')

nPopulation=input('种群个体数量：'); %输入种群个体数量

if size(nPopulation,1)==0

nPopulation=20; %默认值

end

for i=1:nPopulation

Population(i,:)=randperm(nCity-1); %产生随机个体

end

%Population %显示初始种群

%

%添加绘图表示

%

pCrossover=input('交叉概率：'); %输入交叉概率

percent=input('交叉部分占整体的百分比：'); %输入交叉比率 pMutation=input('突变概率：'); %输入突变概率

nRemain=input('最优个体保留最大数量：');

pi(1)=input('选择操作最优个体被保护概率：'); %输入最优个体被保护概率

pi(2)=input('交叉操作最优个体被保护概率：');

pi(3)=input('突变操作最优个体被保护概率：');

maxShock=input('最大突变概率：');

if size(pCrossover,1)==0

pCrossover=0.85;

end

if size(percent,1)==0

percent=0.5;

end

if size(pMutation,1)==0

pMutation=0.05;

end

Shock=0;

rr=0;

Rlength=0;

counter1=0;

counter2=0;

R=zeros(1,nCity-1);

[newPopulation,R,Rlength,counter2,rr]=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain);

R0=R;

record(1,:)=R;

rR(1)=Rlength;

Rlength0=Rlength;

figure(2)

subplot(1,3,1)

plotaiwa(xyCity,R,nCity)

generation=input('算法终止条件A. 最多迭代次数：'); %输入算法终止条件 if size(generation,1)==0

generation=50;

end

nR=input('算法终止条件B. 最短路径连续保持不变代数：');

if size(nR,1)==0

nR=10;

end

while counter1

if counter2

Shock=0;

elseif counter2

Shock=maxShock*1/4-pMutation;

elseif counter2

Shock=maxShock*2/4-pMutation;

elseif counter2

Shock=maxShock*3/4-pMutation;

else

Shock=maxShock-pMutation;

end

counter1

%newPopulation

offspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain);

%offspring

moffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain,Shock);

[newPopulation,R,Rlength,counter2,rr]=select(moffspring,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain);

counter1=counter1+1;

rR(counter1+1)=Rlength;

record(counter1+1,:)=R;

end

%R0

%Rlength0

%R

%Rlength

minR=min(rR);

disp('最短路经出现代数:')

rr=find(rR==minR)

disp('最短路经:')

record(rr,:)

mR=record(rr(1,1),:)

disp('终止条件一:')

counter1

disp('终止条件二:')

counter2

disp('最短路经长度:')

minR

disp('最初路经长度:')

rR(1)

subplot(1,3,2)

plotaiwa(xyCity,R,nCity)

subplot(1,3,3)

plotaiwa(xyCity,mR,nCity)

figure(3)

i=1:counter1+1;

plot(i,rR(i))

grid on

%..................

%目标函数为路径长度

%******************参数及参数说明******************

%-------newPopulation：选择后的新种群

%-------Distance：用来存储及计算个体路径长度

%-------Sum：总路径长度

%-------Fitness：每个个体的适应概率

%-------sFitness：累积概率

%-------a：甩随机数

function

[newPopulation,R,Rlength,counter2,rr]=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain)

Distance=zeros(nPopulation,1); %零化路径长度

Fitness=zeros(nPopulation,1); %零化适应概率

Sum=0; %路径长度

for

i=1:nPopulation %计算个体路径长度

for j=1:nCity-2

Distance(i)=Distance(i)+dCity(Population(i,j),Population(i,j+1));

end %对路径长度调整，增加起始点到路径首尾点的距离 Distance(i)=Distance(i)+dCity(Population(i,1),nCity)+dCity(Population(i,nCity-1),nCity);

Sum=Sum+Distance(i); %累计总路径长度

end %计算个体路径长度

if Rlength==min(Distance)

counter2=counter2+1;

else

counter2=0;

end

Rlength=min(Distance); %更新最短路径长度

Rlength

rr=find(Distance==Rlength);

R=Population(rr(1,1),:); %更新最短路径

R

for i=1:nPopulation

Fitness(i)=(max(Distance)-Distance(i)+0.001)/(nPopulation*(max(Distance)+0.001)-Sum); %适应概率=个体/总和。。。已作调整，大小作了调换

end

%Fitness %显示适应概率

sFitness=zeros(nPopulation,1); %累积概率

sFitness(1)=Fitness(1);

for i=2:nPopulation

sFitness(i)=sFitness(i-1)+Fitness(i);

end

%sFitness %显示累积概率

newPopulation=zeros(nPopulation,nCity-1); %零化新种群 for

i=1:nPopulation %甩随机数

a=rand;

%a %显示甩出的随机数

for j=1:nPopulation

if a

newPopulation(i,:)=Population(j,:);

break

end

end

end

for i=1:size(rr,1)

if rand

newPopulation(rr(i,1),:)=Population(rr(i,1),:); end

end

%newPopulation %显示被选中的新种群个体

%..................

%顺序交叉(OX)算子说明：

%步骤：

%--1.从第一双亲中随机选一个子串；

%--2.将子串复制到一个空字串的相应位置，产生一个原始后代；

%--3.删去第二双亲中子串已有的城市，得到原始后代需要的其他城市的顺序； %--4.按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。 %******************参数及参数说明******************

%-------offspring：子代种群

%-------pCrossover：交叉概率

%-------wCrossover：交叉宽度

%-------pointCrossover：交叉点

%-------percent：交叉比例

function

offspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain)

offspring=zeros(nPopulation,nCity-1); %初始化后代 ccc=0;

for i=1:nPopulation

s=find(rr==i);

if size(s,1)~=0&rand

offspring(i,:)=newPopulation(i,:);

ccc=ccc+1;

elseif rand

j=unidrnd(nPopulation); %选择另一参与交叉的个体

while i==j

j=unidrnd(nPopulation); %unidrnd(n)产生{1,2,...,n}里的随机数

end

wCrossover=floor((nCity-1)*percent); %确定交叉宽度

backPopulation=newPopulation(i,:); %%%%%%%%%%%%%%%%%%%%%%%

pointCrossover=unidrnd(nCity-1-wCrossover); %随机产生交叉点，做差确保不溢出

for m=1:wCrossover %OX交叉

offspring(i,pointCrossover+m-1)=newPopulation(j,pointCrossover+m-1); %步骤1~2

end

for n=1:nCity-1

for m=1:wCrossover

if backPopulation(n)==newPopulation(j,pointCrossover+m-1)

backPopulation(n)=0;

end

end

end

for n=1:nCity-1

if backPopulation(n)~=0

for o=1:nCity-1

if offspring(i,o)==0

offspring(i,o)=backPopulation(n);

break

end

end

end

end

else offspring(i,:)=newPopulation(i,:);

end

end

%offspring %显示交叉后子代

%..................

%两点互换变异

%******************参数及参数说明******************

%-------pMutation：突变概率

function

moffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain,Shock)

exchange=0;

ccc=0;

for m=1:nPopulation

moffspring(m,:)=offspring(m,:);

k=find(rr==m);

if size(k,1)~=0&rand

m=rr(k(1,1),1);

moffspring(m,:)=moffspring(m,:);

ccc=ccc+1;

else

for i=1:nCity-1

if rand

j=unidrnd(nCity-1);

while i==j

j=unidrnd(nCity-1); end

exchange=moffspring(m,i);

moffspring(m,i)=moffspring(m,j); moffspring(m,j)=exchange; end

end

end

end

%offspring %显示突变后子代

%..................

function plotaiwa(xyCity,R,nCity)

scatter(xyCity(:,1),xyCity(:,2),'x')

hold on

plot([xyCity(R(1),1),xyCity(nCity,1)],[xyCity(R(1),2),xyCity(nCity,2)])

plot([xyCity(R(nCity-1),1),xyCity(nCity,1)],[xyCity(R(nCity-1),2),xyCity(nCity,2)]) hold on

for i=1:length(R)-1

x0=xyCity(R(i),1);

y0=xyCity(R(i),2);

x1=xyCity(R(i+1),1);

y1=xyCity(R(i+1),2);

xx=[x0,x1];

yy=[y0,y1];

plot(xx,yy)

hold on

end

%vision5更新内容

%最大突变概率

%突变概率将随着算法的收敛而增大

%最终增大到最大突变概率

%----------------------- 遗传算法解决TSP 问题 ----------------------- %..................

%******************参数及参数说明******************

%-------nCity：城市数量，参数取值范围，>2 整数；

%-------xyCity：城市二维坐标，本例由计算机随机产生，范围(0,1)，假定起始城市为第nCity 个城市；

%-------dCity：城市间距离矩阵，本例考虑城市间往返距离相等，且定义距离为欧几里德范数；

%-------nPopulation：种群个体数量；

%-------Population：种群，nPopulation*(nCity-1)矩阵，每行由{1,2,...,nCity-1}某一个全排列构成；

%-------generation：算法终止条件一，迭代代数；

%-------nR：算法终止条件二，最短路径值连续nR 代不变；

%-------R：最短路径；

%-------Rlength：最短路径长度。

%-------Shock：当最优个体保持一段时期不变后，产生震荡

function

[R,Rlength]=GA_TSP(xyCity,dCity,Population,nPopulation,pCrossover,percent,pMutation,generation,nR,rr,rangeCity,rR,moffspring,record,pi,Sho ck,maxShock)

clear ALL

%10个城市坐标

%xyCity=[0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;

% 0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634];

%10 cities d'=2.691

%--------------------------------------------------------------------------

%30个城市坐标

xyCity=[25 62;7 64;2 99;68 58;71 44];

xyCity=[41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;

83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50];

%30 cities d'=423.741 by D B Fogel

%--------------------------------------------------------------------------

%50个城市坐标

%xyCity=[31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25

55;16 57;

%17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;

%27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33; %58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67];

%50 cities d'=427.855 by D B Fogel

%--------------------------------------------------------------------------

%75个城市坐标

%xyCity=[48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;

%55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;

%20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50; %45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;

%44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56;

%10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26]; %75cities d'=549.18 by D B Fogel

figure(1)

axis([0 10 0 10]) grid on

scatter(xyCity(:,1),xyCity(:,2),'x')

grid on

nCity=size(xyCity,1);

for

i=1:nCity %计算城市间距离，假设距离为欧几里德范数

for j=1:nCity

dCity(i,j)=((xyCity(i,1)-xyCity(j,1))^2+(xyCity(i,2)-xyCity(j,2))^2)^0.5;

end

end %计算城市间距离，假设距离为欧几里德范数 xyCity %显示城市坐标

dCity %显示城市距离矩阵

%初始种群

k=input('取点操作结束'); %取点时对操作保护

disp('-------------------')

nPopulation=input('种群个体数量：'); %输入种群个体数量

if size(nPopulation,1)==0

nPopulation=20; %默认值

end

for i=1:nPopulation

Population(i,:)=randperm(nCity-1); %产生随机个体

end

%Population %显示初始种群

%

%添加绘图表示

%

pCrossover=input('交叉概率：'); %输入交叉概率

percent=input('交叉部分占整体的百分比：'); %输入交叉比率 pMutation=input('突变概率：'); %输入突变概率

nRemain=input('最优个体保留最大数量：');

pi(1)=input('选择操作最优个体被保护概率：'); %输入最优个体被保护概率

pi(2)=input('交叉操作最优个体被保护概率：');

pi(3)=input('突变操作最优个体被保护概率：');

maxShock=input('最大突变概率：');

if size(pCrossover,1)==0

pCrossover=0.85;

end

if size(percent,1)==0

percent=0.5;

end

if size(pMutation,1)==0

pMutation=0.05;

end

Shock=0;

rr=0;

Rlength=0;

counter1=0;

counter2=0;

R=zeros(1,nCity-1);

[newPopulation,R,Rlength,counter2,rr]=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain);

R0=R;

record(1,:)=R;

rR(1)=Rlength;

Rlength0=Rlength;

figure(2)

subplot(1,3,1)

plotaiwa(xyCity,R,nCity)

generation=input('算法终止条件A. 最多迭代次数：'); %输入算法终止条件 if size(generation,1)==0

generation=50;

end

nR=input('算法终止条件B. 最短路径连续保持不变代数：');

if size(nR,1)==0

nR=10;

end

while counter1

if counter2

Shock=0;

elseif counter2

Shock=maxShock*1/4-pMutation;

elseif counter2

Shock=maxShock*2/4-pMutation;

elseif counter2

Shock=maxShock*3/4-pMutation;

else

Shock=maxShock-pMutation;

end

counter1

%newPopulation

offspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain);

%offspring

moffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain,Shock);

[newPopulation,R,Rlength,counter2,rr]=select(moffspring,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain);

counter1=counter1+1;

rR(counter1+1)=Rlength;

record(counter1+1,:)=R;

end

%R0

%Rlength0

%R

%Rlength

minR=min(rR);

disp('最短路经出现代数:')

rr=find(rR==minR)

disp('最短路经:')

record(rr,:)

mR=record(rr(1,1),:)

disp('终止条件一:')

counter1

disp('终止条件二:')

counter2

disp('最短路经长度:')

minR

disp('最初路经长度:')

rR(1)

subplot(1,3,2)

plotaiwa(xyCity,R,nCity)

subplot(1,3,3)

plotaiwa(xyCity,mR,nCity)

figure(3)

i=1:counter1+1;

plot(i,rR(i))

grid on

%..................

%目标函数为路径长度

%******************参数及参数说明******************

%-------newPopulation：选择后的新种群

%-------Distance：用来存储及计算个体路径长度

%-------Sum：总路径长度

%-------Fitness：每个个体的适应概率

%-------sFitness：累积概率

%-------a：甩随机数

function

[newPopulation,R,Rlength,counter2,rr]=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain)

Distance=zeros(nPopulation,1); %零化路径长度

Fitness=zeros(nPopulation,1); %零化适应概率

Sum=0; %路径长度

for

i=1:nPopulation %计算个体路径长度

for j=1:nCity-2

Distance(i)=Distance(i)+dCity(Population(i,j),Population(i,j+1));

end %对路径长度调整，增加起始点到路径首尾点的距离 Distance(i)=Distance(i)+dCity(Population(i,1),nCity)+dCity(Population(i,nCity-1),nCity);

Sum=Sum+Distance(i); %累计总路径长度

end %计算个体路径长度

if Rlength==min(Distance)

counter2=counter2+1;

else

counter2=0;

end

Rlength=min(Distance); %更新最短路径长度

Rlength

rr=find(Distance==Rlength);

R=Population(rr(1,1),:); %更新最短路径

R

for i=1:nPopulation

Fitness(i)=(max(Distance)-Distance(i)+0.001)/(nPopulation*(max(Distance)+0.001)-Sum); %适应概率=个体/总和。。。已作调整，大小作了调换

end

%Fitness %显示适应概率

sFitness=zeros(nPopulation,1); %累积概率

sFitness(1)=Fitness(1);

for i=2:nPopulation

sFitness(i)=sFitness(i-1)+Fitness(i);

end

%sFitness %显示累积概率

newPopulation=zeros(nPopulation,nCity-1); %零化新种群 for

i=1:nPopulation %甩随机数

a=rand;

%a %显示甩出的随机数

for j=1:nPopulation

if a

newPopulation(i,:)=Population(j,:);

break

end

end

end

for i=1:size(rr,1)

if rand

newPopulation(rr(i,1),:)=Population(rr(i,1),:); end

end

%newPopulation %显示被选中的新种群个体

%..................

%顺序交叉(OX)算子说明：

%步骤：

%--1.从第一双亲中随机选一个子串；

%--2.将子串复制到一个空字串的相应位置，产生一个原始后代；

%--3.删去第二双亲中子串已有的城市，得到原始后代需要的其他城市的顺序； %--4.按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。 %******************参数及参数说明******************

%-------offspring：子代种群

%-------pCrossover：交叉概率

%-------wCrossover：交叉宽度

%-------pointCrossover：交叉点

%-------percent：交叉比例

function

offspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain)

offspring=zeros(nPopulation,nCity-1); %初始化后代 ccc=0;

for i=1:nPopulation

s=find(rr==i);

if size(s,1)~=0&rand

offspring(i,:)=newPopulation(i,:);

ccc=ccc+1;

elseif rand

j=unidrnd(nPopulation); %选择另一参与交叉的个体

while i==j

j=unidrnd(nPopulation); %unidrnd(n)产生{1,2,...,n}里的随机数

end

wCrossover=floor((nCity-1)*percent); %确定交叉宽度

backPopulation=newPopulation(i,:); %%%%%%%%%%%%%%%%%%%%%%%

pointCrossover=unidrnd(nCity-1-wCrossover); %随机产生交叉点，做差确保不溢出

for m=1:wCrossover %OX交叉

offspring(i,pointCrossover+m-1)=newPopulation(j,pointCrossover+m-1); %步骤1~2

end

for n=1:nCity-1

for m=1:wCrossover

if backPopulation(n)==newPopulation(j,pointCrossover+m-1)

backPopulation(n)=0;

end

end

end

for n=1:nCity-1

if backPopulation(n)~=0

for o=1:nCity-1

if offspring(i,o)==0

offspring(i,o)=backPopulation(n);

break

end

end

end

end

else offspring(i,:)=newPopulation(i,:);

end

end

%offspring %显示交叉后子代

%..................

%两点互换变异

%******************参数及参数说明******************

%-------pMutation：突变概率

function

moffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain,Shock)

exchange=0;

ccc=0;

for m=1:nPopulation

moffspring(m,:)=offspring(m,:);

k=find(rr==m);

if size(k,1)~=0&rand

m=rr(k(1,1),1);

moffspring(m,:)=moffspring(m,:);

ccc=ccc+1;

else

for i=1:nCity-1

if rand

j=unidrnd(nCity-1);

while i==j

j=unidrnd(nCity-1); end

exchange=moffspring(m,i);

moffspring(m,i)=moffspring(m,j); moffspring(m,j)=exchange; end

end

end

end

%offspring %显示突变后子代

%..................

function plotaiwa(xyCity,R,nCity)

scatter(xyCity(:,1),xyCity(:,2),'x')

hold on

plot([xyCity(R(1),1),xyCity(nCity,1)],[xyCity(R(1),2),xyCity(nCity,2)])

plot([xyCity(R(nCity-1),1),xyCity(nCity,1)],[xyCity(R(nCity-1),2),xyCity(nCity,2)]) hold on

for i=1:length(R)-1

x0=xyCity(R(i),1);

y0=xyCity(R(i),2);

x1=xyCity(R(i+1),1);

y1=xyCity(R(i+1),2);

xx=[x0,x1];

yy=[y0,y1];

plot(xx,yy)

hold on

end


相关文章

  • 遗传算法应用

    • 遗传算法应用 1 遗传算法概述 遗传算法(Genetic Algorithm)是一种通过模拟自然进化过程搜索最优解的方法,它是由美国 Michigan大学J．Holland教授于1975年首先提出来的,并出版了颇有影响的专著<Adap ...查看


  • 基于遗传算法解决TSP问题

    • 基于遗传算法解决TSP 问题 摘要 题目要求给出环游全国全部省会的最短路径方案,是传统的TSP 问题,本文将图表数据数字化后,将其转变成为线性规划问题,进而采取遗传算法用Matlab 求解出理论上的最短路径与路线图.通过第一问求出的路线顺序 ...查看


  • 基于遗传算法的TSP问题解决

    • 基于遗传算法的TSP 问题解决 -余小欢 B07330230 概述:TSP 问题是一个经典的运筹学的组合优化问题,针对此问题,研究人员提出了个中各样的算法,主要有贪婪算法,遗传算法,混沌搜索算法等.在本文中分别用贪婪算法和遗传算法去解决30 ...查看


  • 遗传算法求解TSP问题实验报告

    • 人工智能实验报告 实验六 遗传算法实验II 一.实验目的: 熟悉和掌握遗传算法的原理.流程和编码策略,并利用遗传求解函数优化问题,理解求解TSP问题的流程并测试主要参数对结果的影响. 二.实验原理: 旅行商问题,即TSP问题(Traveli ...查看


  • 具有变异特征的蚁群算法

    • JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT 1999年 第36卷 第10期 Vol.36 No.10 1999 具有变异特征的蚁群算法 吴庆洪 张纪会 徐心和 摘 要 蚁群算法是一种新型的模拟进 ...查看


  • 遗传算法解决TSP问题 1

    • 遗传算法解决TSP 问题 1. TSP 问题 所谓TSP 问题(旅行商问题)即最短路径问题就是在给定的起始点S 到终止点T 的通路集合中,寻求距离最小的通路,这样的通路成为S 点到T 点的最短路径. 在寻找最短路径问题上,有时不仅要知道两个 ...查看


  • 模拟退火算法的旅行商问题的实现

    • 基于模拟退火算法的旅行商问题的实现 摘 要: 主要介绍了模拟退火算法的原理以及应用,并且将遗传算法应用于解决旅行商问题. 关键词:模拟退火算法 旅行商问题 中图分类号: 文献标识码:A 文章编号:1006-7043 (2004) xx-xx ...查看


  • 旅行商问题描述及其蚁群优化算法

    • 计算机研究与发展 JournalofComputerResearchandDevelopment ISSN 1000-1239/CN11-1777/TP 47(3):434-444．2010 基于多粒度的旅行商问题描述及其蚁群优化算法 冀俊 ...查看


  • 智能优化算法求解TSP问题

    • 第21卷第3期 Vol.21No.3 控 制 与 决 策 ControlandDecision 2006年3月 Mar.2006 文章编号:100120920(2006)0320241207 智能优化算法求解TSP问题 高海昌a,冯博琴a, ...查看


热门内容