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

m??bi(t)i?1n是t时刻集合C中元素（城市）两两连接lij上残留信息量的集合，在初始时刻各条路径上的信息量相等，并设τij(0)=const, 基本蚁群算法的寻优是通过有向图g=(C, L, Γ)实现的。 蚂蚁k(k=1,2,…,m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk来记录蚂蚁k当前所走过的城市，集合随着tabuk进化过程做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率： ?[?ij(t)]??[?ik(t)]?, if j?allowedk????k[?(t)]?[?(t)] p(t)??isis(1)?s?allowedijk? ??0 elsewise 其中allowedk={C-tabuk}表示蚂蚁k下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态状态转移概率越接近于贪心规则；ηij(t)为启发函数， ηij(t) =1/dij式中dij表示相邻两个城市之间的距离。对蚂蚁k而言，dij越小，则ηij(t)越大，pijk也就越大。显然，该启发函数表示蚂蚁从元素（城市）i转移到元素（城市）j的期望程度。 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存人大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i, j)上的信息量可按如下规则进行调整 式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限积累， ρ的取值范围为[0，1), Δτij(t)表示本次循环中路径(i, j)上的信息素增量，初始时刻Δτij(t) =0, Δτijk(t) 表示第k只蚂蚁在本次循环中留在路径(i, j)上的信息量。 根据信息素更新策略的不同，Dorigo M提出了三种不同的基本蚁群算法模型，分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差别在于Δτijk(t)求法的不同。 ?ij(t?n)?(1??)??ij(t)???ij(t) (2)??ij(t)????ijk(t) (3)k?1m程序

遗传算法：

clear clc

close all %% 加载数据 %load data

X=[1304 2312;3639 1315;4177 2244;3721 1399;3488 1535;3326 1556;3238 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367;3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975]; D=Distanse(X); %生成距离矩阵 N=size(D,1); %城市个数 %% 遗传参数

NIND=100; %种群大小 MAXGEN=200; %最大遗传代数 Pc=0.9; %交叉概率 Pm=0.05; %变异概率 GGAP=0.9; %代沟 %% 初始化种群

Chrom=InitPop(NIND,N); %% 画出随机解的路径图 DrawPath(Chrom(1,:),X) pause(0.0001)

%% 输出随机解的路径和总距离

disp('初始种群中的一个随机值:') OutputPath(Chrom(1,:));

Rlength=PathLength(D,Chrom(1,:)); disp(['总距离：',num2str(Rlength)]);

disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~') %% 优化 gen=0; figure;

hold on;box on xlim([0,MAXGEN]) title('优化过程') xlabel('代数') ylabel('最优值')

ObjV=PathLength(D,Chrom); %计算路径长度 preObjV=min(ObjV); while gen

ObjV=PathLength(D,Chrom); %计算路径长度 % fprintf('%d %1.10f\\n',gen,min(ObjV))

line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001) preObjV=min(ObjV); FitnV=Fitness(ObjV); %% 选择

SelCh=Select(Chrom,FitnV,GGAP); %% 交叉操作

SelCh=Recombin(SelCh,Pc); %% 变异

SelCh=Mutate(SelCh,Pm); %% 逆转操作

SelCh=Reverse(SelCh,D); %% 重插入子代的新种群

Chrom=Reins(Chrom,SelCh,ObjV); %% 更新迭代次数 gen=gen+1 ; end

%% 画出最优解的路径图

ObjV=PathLength(D,Chrom); %计算路径长度 [minObjV,minInd]=min(ObjV); DrawPath(Chrom(minInd(1),:),X) %% 输出最优解的路径和总距离 disp('最优解:')

p=OutputPath(Chrom(minInd(1),:));

disp(['总距离：',num2str(ObjV(minInd(1)))]);

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

Distanse.m

%% 计算两两城市之间的距离 %输入 a 各城市的位置坐标 %输出 D 两两城市之间的距离 function D=Distanse(a) row=size(a,1); D=zeros(row,row); for i=1:row

for j=i+1:row

D(i,j)=((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5; D(j,i)=D(i,j); end end

DrawPath.m %% 画路径函数 %输入

% Chrom 待画路径 % X 各城市坐标位置 function DrawPath(Chrom,X)

R=[Chrom(1,:) Chrom(1,1)]; %一个随机解(个体) figure; hold on

plot(X(:,1),X(:,2),'o','color',[0.5,0.5,0.5])

plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20) for i=1:size(X,1)

text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]); end

A=X(R,:);

row=size(A,1); for i=2:row

[arrowx,arrowy] = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2));%坐标转换 annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]); end

hold off

xlabel('横坐标') ylabel('纵坐标') title('轨迹图') box on

dsxy2figxy.m

function varargout = dsxy2figxy(varargin)

if length(varargin{1}) == 1 && ishandle(varargin{1}) ...

&& strcmp(get(varargin{1},'type'),'axes') hAx = varargin{1};

varargin = varargin(2:end); else

hAx = gca; end;

if length(varargin) == 1 pos = varargin{1}; else

[x,y] = deal(varargin{:}); end

axun = get(hAx,'Units');

set(hAx,'Units','normalized'); axpos = get(hAx,'Position'); axlim = axis(hAx);

axwidth = diff(axlim(1:2)); axheight = diff(axlim(3:4)); if exist('x','var')

varargout{1} = (x - axlim(1)) * axpos(3) / axwidth + axpos(1);

varargout{2} = (y - axlim(3)) * axpos(4) / axheight + axpos(2); else

pos(1) = (pos(1) - axlim(1)) / axwidth * axpos …… 此处隐藏：3093字，全部文档内容请下载后查看。喜欢就下载吧 ……