1 内容介绍
旅行商路径规划问题(GTSP)是一个典型的NP完全问题.文中针对这一困难问题,改进了能够求解GTSP问题的传统帝国企鹅算法算法,这样的做法回避了传统算法的一些缺点.具体而言,GTSP问题可以转化为多段映射问题,而改进帝国企鹅算法可解决这一问题,同时还大幅缩短了整个算法的运行时间.大量实验结果证明,改进帝国企鹅算法能够在更短的时间内收敛,并可得到比传统帝国企鹅算法质量更好的最优解.
2 仿真代码
% This is the direct result of using the original algorithm,
% adding some specific update methods to this problem can further improve the accuracy
clc;
clear;
close all;
warning off
global data
%% 固定随机数种子
noRNG=1;
rng('default')
rng(noRNG)
%% 载入数据
data.maxTraveler=1; %旅行商数量
data.numCity=100; %城市数量
%% 随机生成城市
data.xyCity=rand(data.numCity,2);
for i=1:data.numCity
for j=1:data.numCity
data.D(i,j)=norm(data.xyCity(i,:)-data.xyCity(j,:));
end
end
%%
option.dim=data.numCity;
lb=0;
ub=1;
option.lb=lb;
option.ub=ub;
if length(option.lb)==1
option.lb=ones(1,option.dim)*option.lb;
option.ub=ones(1,option.dim)*option.ub;
end
option.fobj=@aimFcn_TSP;
%option.fobj0=option.fobj;
option.showIter=0;
%% 算法参数设置 Parameters
% 基本参数
option.numAgent=100; %种群个体数
% 帝企鹅算法
option.v_lb=-(option.ub-option.lb)/4;
option.v_ub=(option.ub-option.lb)/4;
option.w2=0.5; %weight of Moving strategy III
option.w4=1;%weight of Moving strategy III
option.w5=1;%weight of Moving strategy III
option.pe=0.01; % rate to judge Premature convergence
option.gapMin=5; % min gap
option.dec=2; % dec of gap
option.L=10; % Catastrophe
%% DE
option.F=0.5;
option.CR=0.5;
%% Imroved AFO
option.P_stratage=[0.05,0.2,0.7];
option.p=0.1;
option.alpha=10;
option.gama=1;
str_legend=[{'IAFO'}];
selectedAlgorithm=[{@IAFO_Final1}];
numCity=30:10:100;
noPro=[1:length(numCity)];
%parpool(8)
j=1;
%% 使用算法求解
for ii=1:length(selectedAlgorithm)
dim=numCity(j);
data.numCity=numCity(j);
option.maxIteration=dim*10000/option.numAgent; %最大迭代次数
option.maxEfs=dim*10000;
option.dim=dim;
option.gap0=ceil(sqrt(option.maxIteration*2))+1;
lb=-ones(1,dim)*0;
ub=ones(1,dim)*1;
option.lb=lb;
option.ub=ub;
disp(noPro(j))
option.fobj=@aimFcn_TSP;
x=ones(option.numAgent,option.dim);
y=ones(option.numAgent,1);
for i=1:option.numAgent
x(i,:)=rand(size(option.lb)).*(option.ub-option.lb)+option.lb;
y(i)=option.fobj(x(i,:),option,data);
end
rng(noRNG)
tic
[bestY(ii,:),bestX(ii,:),recording{ii}]=selectedAlgorithm{ii}(x,y,option,data);
recordingT(ii,j)=toc;
end
%%
figure
hold on
plot(recording{1}.bestFit_EFs(1:option.maxEfs),'LineWidth',2)
legend(str_legend)
set(gca,'LooseInset',get(gca,'TightInset'))
%%
for ii=1:length(selectedAlgorithm)
option.fobj=@aimFcn_TSP;
str=str_legend{ii};
[fit(ii),result(ii)]=option.fobj(bestX(ii,:),option,data);
drawPc_TSP(result(ii),option,data,str)
end
3 运行结果
4 参考文献
[1]周君, 贾昆霖. 求解旅行商路径规划问题的改进模拟退火算法[J]. 电子科技, 2017, 30(7):4.
[2]刘春波, 潘丰, and 杨丹. "基于改进的蚁群算法在中国旅行商问题中的求解." 中国控制与决策学术年会 2007.
