利用遗传算法解决TSP问题

TSP(traveling salesman problem,旅行商问题)是典型的 NP 完全问题,即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长,到目前为止还未找到一个多项式时间的有效算法。

TSP 问题可描述为:已知n个城市相互之间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,如何安排才使其所走路线最短。 即寻找一条最短的遍历n个城市的路径，对自然子集X={1,2,3,...n}（X中的元素为对n个城市的编号）进行搜索排序使得M(X)={V1,V2,V3,...Vn}，使得

Td取得最小值，d(Vi,Vi+1)表示城市Vi到Vi+1的距离。

TSP问题并不仅仅是旅行商问题,其他许多的NP完全问题也可以归结为 TSP 问题,如邮路问题、装配线上的螺母问题和产品的生产安排问题等,使得TSP问题的有效求解具有重要的意义。

以14个城市为例,假定14个城市的位置坐标如表1所列。寻找出一条最短的遍历 14 个城市的路径。

表1 4个城市的位置坐标

算法流程：

图1 遗传算法TSP问题求解流程图

遗传算法：

(1)采用整数排列编码方法：对于n个城市的TSP问题，染色体分为n段，其中每一段为对应城市的编号，如对10个城市的TSP问题{1,2,3,4,5,6,7,8,9,10},则|1|10|2|4|5|6|8|7|9|3就是一段正常的染色体

(2)种群初始化：在完成染色体编码以后，必须产生一个初始种群作为起始解，所以首先需要决定初始化种群的数目。初始化种群的数目一般根据经验得到，一般情况下种群的数量视城市规模的大小而确定，其取值在 50~200 之间浮动。

(3)适应度函数：设 k1|k2|…|ki|…|kn|为一个采用整数编码的染色体，Dkikj为城市ki到城市kj的距离，则该个体的适应度为

即适应度函数为恰好走遍n个城市,再回到出发城市的距离的倒数。优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质。

(4)选择操作：选择操作即从旧群体中以一定概率选择个体到新群体中，个体被选中的概率跟适应度值有关,个体适应度值越大，被选中的概率越大。

(5)交叉操作：采用部分映射杂交,确定交叉操作的父代，将父代样本两两分组，每组重复以下过程(假定城市数为 10):

① 产生两个[1,10]区间内的随机整数r1和r2确定两个位置，对两位置的中间数据进行交叉，如r1=4,r2=7

交叉为：

②交叉后，同一个个体中有重复的城市编号,不重复的数字保留，有冲突的数字(带*位置)采用部分映射的方法消除冲突,即利用中间段的对应关系进行映射。结果为

(6)变异操作：变异策略采取随机选取两个点,将其对换位置。产生两个[1,10]范围内的随机整数r和r2，确定两个位置，将其对换位置,如r=4,r=7

9  5  1  |6|  3  8  |7|  10  4  2

变异后：

9  5  1  |7|  3  8  |6|  10  4  2

(7)进化逆转操作：为改善遗传算法的局部搜索能力,在选择、交叉、变异之后引进连续多次的进化逆转操作，这里的“进化”是指逆转算子的单方向性,即只有经逆转后,适应度值有提高的才接受下来,否则逆转无效。产生两个[1,10]区间内的随机整数,和,确定两个位置,将其对换位置,如r1=4，r2=7。

9  5  1  |7  3  8  |6  10  4  2

进行逆转后：

9  5  1  |8  3  7  |6  10  4  2

主函数：

%遗传算法求解TSP问题(为选择操作从新设计后程序)
%输入：
%D       距离矩阵
%NIND    为种群个数
%X       参数是中国34个城市的坐标(初始给定)
%MAXGEN  为停止代数，遗传到第MAXGEN代时程序停止,MAXGEN的具体取值视问题的规模和耗费的时间而定
%m       为适值淘汰加速指数,最好取为1,2,3,4,不宜太大
%Pc      交叉概率
%Pm      变异概率
%输出：
%R       为最短路径
%Rlength 为路径长度
clear
clc
close all
%% 加载数据
load('CityPosition1.mat')
% X=load('CityPosition1.mat');
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<MAXGEN
    %% 计算适应度
    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('-------------------------------------------------------------')

初始化代码：

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

结果：

初始种群中的一个随机值:

8—>13—>3—>1—>12—>11—>5—>9—>6—>4—>7—>2—>10—>14—>8

总距离：74.8833

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

69  ObjV=PathLength(D,Chrom);  %计算路径长度

最优解:

5—>4—>3—>14—>2—>1—>10—>9—>11—>8—>13—>7—>12—>6—>5

总距离：29.3405

随机生成的路线图

迭代后生成的路线图

迭代曲线图

详细代码请关注微信公众号：