遗传，模拟退火，蚁群三个算法求解TSP的对比 - 图文(3)

N=length(R); p=num2str(R(1)); for i=2:N

p=[p,'—>',num2str(R(i))]; end disp(p)

PathLength.m

%% 计算各个体的路径长度 % 输入：

% D 两两城市之间的距离 % Chrom 个体的轨迹

function len=PathLength(D,Chrom) [row,col]=size(D); NIND=size(Chrom,1); len=zeros(NIND,1); for i=1:NIND

p=[Chrom(i,:) Chrom(i,1)]; i1=p(1:end-1); i2=p(2:end);

len(i,1)=sum(D((i1-1)*col+i2)); end

Recombin.m %% 交叉操作 % 输入

%SelCh 被选择的个体 %Pc 交叉概率 %输出：

% SelCh 交叉后的个体

function SelCh=Recombin(SelCh,Pc) NSel=size(SelCh,1);

for i=1:2:NSel-mod(NSel,2) if Pc>=rand %交叉概率Pc

[SelCh(i,:),SelCh(i+1,:)]=intercross(SelCh(i,:),SelCh(i+1,:)); end end

%输入：

%a和b为两个待交叉的个体 %输出：

%a和b为交叉后得到的两个个体

function [a,b]=intercross(a,b) L=length(a);

r1=randsrc(1,1,[1:L]);

r2=randsrc(1,1,[1:L]); if r1~=r2

a0=a;b0=b;

s=min([r1,r2]); e=max([r1,r2]); for i=s:e

a1=a;b1=b; a(i)=b0(i); b(i)=a0(i);

x=find(a==a(i)); y=find(b==b(i)); i1=x(x~=i); i2=y(y~=i); if ~isempty(i1) a(i1)=a1(i); end

if ~isempty(i2) b(i2)=b1(i); end end end Reins.m

%% 重插入子代的新种群 %Chrom 父代的种群 %SelCh 子代种群 %ObjV 父代适应度

% Chrom 组合父代与子代后得到的新种群 function Chrom=Reins(Chrom,SelCh,ObjV) NIND=size(Chrom,1); NSel=size(SelCh,1);

[TobjV,index]=sort(ObjV);

Chrom=[Chrom(index(1:NIND-NSel),:);SelCh]; Reverse.m

%% 进化逆转函数 %SelCh 被选择的个体 %D 城市的距离矩阵 %输出

%SelCh 进化逆转后的个体

function SelCh=Reverse(SelCh,D) [row,col]=size(SelCh);

ObjV=PathLength(D,SelCh); %计算路径长度 SelCh1=SelCh; for i=1:row

r1=randsrc(1,1,[1:col]);

r2=randsrc(1,1,[1:col]); mininverse=min([r1 r2]); maxinverse=max([r1 r2]);

SelCh1(i,mininverse:maxinverse)=SelCh1(i,maxinverse:-1:mininverse); end

ObjV1=PathLength(D,SelCh1); %计算路径长度 index=ObjV1

SelCh(index,:)=SelCh1(index,:); Select.m

function SelCh=Select(Chrom,FitnV,GGAP) %% 选择操作 NIND=size(Chrom,1); % Chrom 种群 NSel=max(floor(NIND*GGAP+.5),2); % %GGAP：代沟 ChrIx=Sus(FitnV,NSel); %FitnV 适应度值

SelCh=Chrom(ChrIx,:); %SelCh 被选择的个体 Sus.m

%Nsel 被选择个体的数目

%NewChrIx 被选择个体的索引号

function NewChrIx = Sus(FitnV,Nsel) %FitnV 个体的适应度值 [Nind,ans] = size(FitnV); cumfit = cumsum(FitnV);

trials = cumfit(Nind) / Nsel * (rand + (0:Nsel-1)'); Mf = cumfit(:, ones(1, Nsel)); Mt = trials(:, ones(1, Nind))';

[NewChrIx, ans] = find(Mt < Mf & [ zeros(1, Nsel); Mf(1:Nind-1, :) ] <= Mt); [ans, shuf] = sort(rand(Nsel, 1)); NewChrIx = NewChrIx(shuf);

程序运行结果为:

初始轨迹：

优化过程：

优化后轨迹：