【TSP问题】基于遗传算法实现TSP问题

2021-12-20 09:38:01

文章目录

一、理论基础
二、案例背景
- 1，问题描述
- 2，解决思路和步骤
- - (1).算法流程
  - (2).遗传算法实现
三、MATLAB程序实现
- (1).种群初始化
- (2).适应度函数
- (3).选择操作
- (4).交叉操作
- (5).变异操作
- (6).进化逆转操作
- (7).画路线轨迹图
- (8).遗传算法主函数
- (9).结果分析
四、遗传算法的改进
- 1. 使用精英策略
- 2. 使用进化逆转操作
五、算法的局限性
六、参考文献

一、理论基础

二、案例背景

1，问题描述

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

表1 14个城市的位置坐标

2，解决思路和步骤

(1).算法流程

遗传算法TSP问题的流程图如图1所示。

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

(2).遗传算法实现

三、MATLAB程序实现

(1).种群初始化

种群初始化函数InitPop的代码：

function Chrom = InitPop(NIND,N)
%% 初始化种群
% 输入：
% NIND：种群大小
% N：   个体染色体长度（这里为城市的个数）  
% 输出：
% 初始种群
Chrom = zeros(NIND, N);         % 用于存储种群
for i = 1:NIND
    Chrom(i, :) = randperm(N);    % 随机生成初始种群
end

(2).适应度函数

求种群个体的适应度函数Fitness的代码：

function FitnV = Fitness(len)
%% 适应度函数     
% 输入：
% 个体的长度（TSP的距离）
% 输出：
% 个体的适应度值
FitnV = 1./len;

clear
clc
close all
load CityPosition1.mat
%% 初始化参数
NIND = 100;                  % 种群大小
MAXGEN = 200;            % 最大遗传代数
Pc = 0.9;                          % 交叉概率
Pm = 0.05;                       % 变异概率
GGAP = 0.9;                     % 代沟(Generation gap)
D = Distance(X);                 % 生成距离矩阵
N = size(D, 1);                     % (14*14)
%% 初始化种群
Chrom = InitPop(NIND, N);
%% 在二维图上画出所有坐标点
% figure
% plot(X(:,1),X(:,2),'o');
%% 画出随机解的路线图
DrawPath(Chrom(1,:), X)
%% 输出随机解的路线和总距离
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)]);
    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('-------------------------------------------------------------')

结果分析

优化前的一个随机路线轨迹图如图2所示。

图2 随机路线图

初始种群中的一个随机值:
10—>4—>8—>11—>9—>13—>3—>12—>14—>6—>1—>5—>2—>7—>10
总距离：70.3719
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

优化后的路线图如图3所示。

图3 最优解路线图

最优解:
5—>4—>3—>14—>2—>1—>10—>9—>11—>8—>13—>7—>12—>6—>5
总距离：29.3405
-------------------------------------------------------------

优化迭代图如图4所示。

图4 遗传算法进化过程图

由优化图可以看出，优化前后路径长度得到很大改进，接近40代以后路径长度已经保持不变了，可以认为是最优解了，总距离由优化前的70.3719变为29.3405，减为原来的41.7%。

四、遗传算法的改进

上述程序中，对遗传算法做了以下两处改进。

1. 使用精英策略

子代种群中的最优个体永远不会比父代最优的个体差，这样使得父代的好的个体不至于由于交叉或者变异操作而丢失。

2. 使用进化逆转操作

同交叉算子相比较，逆转算子能使子代继承亲代的较多信息。

五、算法的局限性

当问题规模n nn比较小时，得到的一般都是最优解；当规模比较大时，一般只能得到近似解。这时可以通过增大种群大小和增加最大遗传代数使得优化值更接近最优解。

六、参考文献

[1] 储理才. 基于MATLAB的遗传算法程序设计及TSP问题求解[J]. 集美大学学报:自然科学版, 2001.
[2] 郁磊等. MATLAB智能算法30个案例分析(第2版)[M].北京航空航天大学出版社.2015年.

码农公寓