【路径规划-TSP问题】基于改进帝国企鹅算法求解旅行商问题附matlab代码

​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.

博主简介：擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真，相关matlab代码问题可私信交流。

部分理论引用网络文献，若有侵权联系博主删除。