1 算法介绍

遗传算法在 TSP 问题的解决过程中发挥着较为重要的作用。本文从遗传算法的基本原理与算法步骤入手，简述遗传算法的基本原理及遗传算法的基本步骤，然后对基于遗传算法的 TSP 问题解决方式进行了分析，包括 TSP 问题建模、TSP 问题遗传算法设计、编码方式、算子选择、单点交叉、变异算子、其他参数等，最后从选择因子分析和算法测试分析两方面对基于遗传算法的 TSP 问题实验进行了探究。

旅行商问题（TSP 问题）是诸多领域中存在的、多种复杂问题的集中概括。在解决此类问题的过程中，研究者不能借助全局搜索算法确定此类问题的最优解。为确定此类算法的最优解与次优解，一些研究者开始将遗传算法应用于 TSP问题的解决过程之中。遗传算法是建立在自然界生物适者生存、优胜劣汰的遗传机制基础之上的全局优化算法。这一算法具有良好的自组织性、自适应性与自学习性。现阶段遗传算法已经开始在组合优化问题、机器学习问题及自适应控制问题等问题的解决过程中得到应用。利用遗传算法的基本思想与优化原理，构建解决 TSP 问题的遗传算法程序，有助于降低 TSP 问题的解决难度。

2 部分代码

clear
clc
close all
X=load('eil51.txt');
%% 初始化参数
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('最优值')
img =gcf;  %获取当前画图的句柄
print(img, '-dpng', '-r600', './运行结果.png')         %即可得到对应格式和期望dpi的图像
ObjV = PathLength(D,Chrom);  %计算路线长度
preObjV = min(ObjV);
while gen < MAXGENgen = 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('-------------------------------------------------------------')
img =gcf;  %获取当前画图的句柄
print(img, '-dpng', '-r600', './运行结果2.png')         %即可得到对应格式和期望dpi的图像

3 仿真结果

4 参考文献

[1]谢胜利, 唐敏, 董金祥. 求解TSP问题的一种改进的遗传算法[J]. 计算机工程与应用, 2002, 38(008):58-60.

[2]文艺, and 潘大志. "用于求解TSP问题的改进遗传算法." 计算机科学 43.0z1(2016):90-92.

​