原创 基于遗传算法的TSP(旅行商问题)解决方法

TSP(旅行商问题)

1 参数设置

设置30个城市：

x坐标：x=[87 91 83 71 64  68 83 87 74 71   58 54 51 37 41  

2 7 22 25 18   4 13 18 24 25  41 45 44 58 62];

y坐标：y=[7  38 46 44 60  58 69 76 78 71   69 62 67 84 94 

  99 64 60 62 54  50 40 40 42 38  26 21 35 35 32];

2 设计步骤

2.1 第1步：参数编码和初始群体设置

对于TSP问题，采用访问城市序列排列组合的方法编码，而不采用传统的二进制编码.如图1所示，为30进制，每个个体有30位，每位取值范围为1到30.

图 1  个体

设置一个s行t列的矩阵D=，其中，s为个体数，t=31. 到（i=1，2，……，s）为2个城市之间的距离，为每个个体中30个城市距离的总和.

2.2 第2步：适应度函数设计

，其中j=1，2，……，31.

目标函数，自适应函数.

2.3 第3步：计算选择算子

选择是从群体中选择优胜个体，淘汰劣质个体. 它通过评估个体自适应函数，将适应度最大的c个个体直接替换适应度最小的c个个体. 仿真程序中c=15.

2.4 第4步：计算交叉算子

图 2  交叉

如图2所示，假设为10位个体，随机选择两个交叉点cp1和cp2，X1'为X1的子代，X2'为X2的子代. 子代中cp1与cp2之间的部分直接从双亲复制而来，其它部分取双亲中另一个的，遇到与已确定段中雷同的数字时，取双亲中对应位置非雷同的数字为子代数字.例如X1'中的第2为，应该对应X2中第2位对应的7，但是X1'的第6位已经有了7，所以按照X1中第6位7对应X2的位置确定为数字3.

仿真程序中交叉概率.

2.5 第5步：计算变异算子

随机确定两个交叉点cp1和cp2，将cp1与cp2之间的字符串前后颠倒，如图3所示，74805变为50847.仿真程序中变异概率.

图 3   变异

3 仿真程序

主程序如下：

clear all;

close all;

t=31;     %城市数=t-1

s=10000;    %个体数

pc=0.90;

pm=0.20;

pop=zeros(s,t);

for i=1:s

   pop(i,1:t-1)=randperm(t-1);

end

for k=1:1:500

if mod(k,10)==1

    k

end

pop=chap10_1dis(pop);

c=15;

pop=chap10_1select(pop,c);

p=rand;

if p>=pc

   pop=chap10_1cross(pop);

end

if p>=pm

   pop=chap10_1mutate(pop);

end

end

pop 

min(pop(:,t))

J=pop(:,t);

fi=1./J;

[Oderfi,Indexfi]=sort(fi);

BestS=pop(Indexfi(s),;

I=BestS;

x=[87 91 83 71 64  68 83 87 74 71   58 54 51 37 41  2 7 22 25 18   4 13 18 24 25  41 45 44 58 62];

y=[7 38 46 44 60  58 69 76 78 71   69 62 67 84 94  99 64 60 62 54   50 40 40 42 38  26 21 35 35 32];

for i=1:1:t-1

    x1(i)=x(I(i));

    y1(i)=y(I(i));

end 

x1(t)=x(I(1));

y1(t)=y(I(1));

figure(1);

plot(x1,y1,'-or');

4 仿真结果

如图4所示，距离d=449.5.

图 4  仿真结果