本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
本节展示一个使用遗传算法求解TSP问题的代码示例，
通过本文可以更具体地了解遗传算法的用途以及实现方式
本节展示如何使用遗传算法来解决TSP问题
问题：TSP旅行商问题
什么是TSP问题
有N个城市 ，要求穿过每个城市，最终回到出发城市，
问：寻找一条路径，使旅行总距离最小
TSP问题的数学表述
假设有5个城市，用矩阵D表示城市之间的距离,
代表第i个城市到第j个城市的距离
路径X可以表示为序列形式：
它代表先到城市1，再到城市5，再到3.....最后由4回到1.
而总距离就是按这顺序行走的总距离
即求一 个1到N的组合X,令总距离F最小
✍️TSP问题的经典性
TSP问题有两个特有的经典特点
1. 不能穷举
它的解空间是非常大的，如果有N个城市，那么就会有N！个解
这就不能用一般的穷举法来寻找最优解
2. x与f(x)的非纯数学性
它的目标函数 f(x) 和解 x 而更倾向于一系列描述性计算
而不是一般问题那样具有严格的数值表达式
这导致它不能用梯度下降一类的算法来求解
遗传算法求解TSP-算法设计
用遗传算法，需要设计好该问题的以下三点：
👉1. 染色体交换方式：解与解之间如何进行部分交换
👉2. 基因变异的方式：单个解如何作出随机改变
👉3. 适应度的定义 ：用于评估解的优秀程度
对本问题我们可以设计如下：
(1)染色体交换方式
将解群两两随机配对，每一对之间(设为a,b)以如下方式交换：
设a=[0,1,5,3,2,4]，b=[1,2,5,0,3,4],先随机抽出a的一个片段a_piece，
假设a_piece= [5,3,2],再在b中找出 a_piece 的排序 b_piece=[2,5,3],
将b_piece替换到a,将a_piece替换到b,得到：a=[0,1,2,5,3,4],b=[1,5,3,0,2,4]
(2)基因变异方式
设a=[0,1,5,3,2,4],
先随机抽出a的一个片段a_piece，假设a_piece= [5,3,2],
将a_piece翻转( [2,3,5])后再回代a，得到a=[0，1，2，3，5，4]
(3)适应度设计:
本问题的目标函数一定是大于0的，我们简单的设为
即可（F是目标函数的值），就可以达到函数值越小，适应度越大的效果。
设计完以上三点后，只需按遗传算法的算法流程，实现代码即可
本节按上节设计的算法，编写遗传算法求解TSP问题的代码
遗传算法求解TSP问题-代码实现
根据上述设计，结合遗传算法流程，
编码代码利用遗传算法求解TSP问题如下：
%------代码说明：展示遗传算法求解TSP问题 -----------------
% 来自《老饼讲解神经网络》www.bbbdata.com ,matlab版本：2018a
function gaforTSP()
clc;clear all;close all ;
rng(999)
global distMat;
cityLoc = [3.64,2.68 ;... %beijing
4.18,1.76 ;... %shanghai
3.71,2.60 ;... %tianjin
1.33,3.30 ;... %wulumuqi
4.20,2.96 ;... %shenyang
3.92,1.82 ;... %nanjing
2.55,1.64 ;... %chengdu
2.37,1.02 ;... %kunming
3.43,2.09 ;... %zhengzhou
3.54,0.70 ;... %xianggang
3.51,1.62 ;... %wuhan
3.44,0.80 ;... %guangzhou
3.24,2.77 ;... %huhehaote
2.38,2.32 ;... %xiling
2.56,2.24 ;... %lanzhou
3.01,2.03 ;... %xian
2.79,2.51 ;... %yinchuan
4.03,1.16 ;... %fuzhou
3.47,0.70 ;... %aomen
1.30,1.69] ; %lasha
distMat = dist(cityLoc') ; % 计算城市距离
N = size(cityLoc,1); % 城市个数
rng(888) % 为方便复现结果,设定随机种子
%----------------参数初始化-----------------------
m = 30; %种群规模
t = 5000; %迭代次数
var_rate = 0.2; %变异概率
%--------------初始化种群-------------------------
xg = cell(m,1); % 初始化种群
for i =1:m
xg{i} = randperm(N); % 随机初始化种群
end
h_best_x = xg{1}; % 初始化历史最优个体
h_best_F = calF(h_best_x); % 初始化历史最优个体的目标函数值
F_list = []; % 每代最优函数值记录列表
for i=1:t
% ----种群交换染色体与基因变异-----
xg = exPart(xg); % 交换染色体
xg = genVar(xg,var_rate); % 基因变异
[best_x,best_F] = getBest(xg); % 获取本代最佳个体
if(best_F <h_best_F) % 更新历史最优个体
h_best_F = best_F; % 更新历史最优函数值
h_best_x = best_x; % 更新历史最优个体
end
disp(['第',num2str(i),'代:最优F=',num2str(best_F)]) % 显示当前轮的最优个体
F_list = [F_list,best_F]; % 记录历代最优个体
% 判断是否满足退出迭代条件.
% 退出条件:近20代最优个体变化不大，则退出
last_F = F_list(max(1,end-20):end); % 截取最后20轮的最佳函数值
diff = (max(last_F)-min(last_F))/max(abs(mean(last_F)),1); % 最近20轮的差异
if((i>20) && (diff<0.001)) % 判断没什么差异
break % 则退出迭代
end
%-------------赌轮盘生成下一代---------------------------
PPan = getPPan(xg); % 计算种群的概率轮盘
xg = genChildGroup(xg,PPan,h_best_x); % 根据概率轮盘选出下一代种群
%------------------画图------------------------------------
hold off
plot(cityLoc(:,1),cityLoc(:,2),'o','MarkerEdgeColor','k','MarkerFaceColor','y','MarkerSize',10,'LineWidth',2)
hold on
plot(cityLoc([h_best_x,h_best_x(1)],1),cityLoc([h_best_x,h_best_x(1)],2))
drawnow
end
% 打印最终结果(历史最优)
disp(['h_best_F=',num2str(h_best_F)]) % 打印历史最优目标函数值
disp(['h_best_x=',num2str(h_best_x)]) % 打印历史最优个体
end
%------------目标函数值计算方法------------------------------------------
function d= calF(x)
global distMat;
d = distMat(x(end),x(1)); % 初始化总距离
for i=1:length(x)-1
d = d+ distMat(x(i),x(i+1)); % 累加各个城市之间的距离
end
end
%------------获取种群中目标函数值最好的一个-------------------------------
function [x,F] = getBest(xg)
F_list = inf(length(xg),1); % 初始化各个个体的函数值
for i = 1:length(xg)
F_list(i) = calF(xg{i}); % 计算各个个体的目标函数值
end
[F,best_index] =min(F_list) ; % 获取最优的目标函数值与索引
x = xg{best_index}; % 根据索引获取最优的个体
end
%------------计算种群进入下一代的概率轮盘-----------------
function PPan = getPPan(xg)
F_list = inf(length(xg),1); % 初始化各个个体的函数值
for i = 1:length(xg)
F_list(i) = calF(xg{i}); % 计算各个个体的目标函数值
end
F_list = F_list - min(F_list); % 令函数值全大于0
acp_list = 1./(1+F_list); % 计算适应度
PPan = cumsum(acp_list./sum(acp_list)); % 根据适应度计算轮盘概率
end
%------------染色体交换-------------------------------
function xg = exPart(xg)
m = length(xg); % 种群大小
[vn,n] = size(xg{1}); % 变量个数,编码长度
ex_list = randperm(m); % 随机生成种群排序,用于下面两两匹对交换
for i=1:2:m % 逐对交换
a = xg{ex_list(i)}; % 当前要交换的个体a
b = xg{ex_list(i+1)}; % 当前要交换的个体b
ex_part = randperm(n); % 随机生成1到n的随机整数
ex_part = ex_part(1:2); % 提取前两位作为要交换的起始结束位置
ex_start = min(ex_part); % 小者作为交换的起始位置
ex_end = max(ex_part); % 大者作为交换的结束位置
a_piece = a(ex_start:ex_end); % 提出出a要交换的片段
[~,idx] = ismember(a_piece,b); % 找出a的片段在b中的位置
idx = sort(idx); % 对位置进行排序
b_piece = b(idx); % 提出b中的片段
a(ex_start:ex_end) = b_piece; % 将b的片段赋予a
b(idx) = a_piece; % 将a的片段赋予b
xg{ex_list(i)} = a; % 将个体a重新替换回种群
xg{ex_list(i+1)} = b; % 将个体b重新替换回种群
end
end
%------------基因变异-------------------------------
function xg = genVar(xg,var_rate)
m = length(xg); % 种群大小
[~,n] = size(xg{1}); % 编码长度
for i= 1:m
a = xg{i}; % 提取出当前个体
if(rand()<var_rate) % 判断当前个体是否变异
var_part = randperm(n); % 随机生成变异的位置
var_part = var_part(1:2); % 截断前两位作为变异起始结束位置
var_start = min(var_part); % 小者作为变异起始位置
var_end = max(var_part); % 大者作为变异结束位置
a(var_start:var_end) = flip(a(var_start:var_end)); % 将变异位置翻转
end
xg{i} = a ; % 将变异后的个体替换进种群
end
end
%------------生成下代种群-------------------------------
function child_xg = genChildGroup(xg,PPan,best_x)
m = length(xg); % 种群个数
child_xg = cell(m,1); % 初始化下一代种群
child_xg{1} = best_x; % 最佳的必定选到下一个种群
for i=2:m
select_idx = min(find(rand()<PPan)); % 生成一个随机数,并找到第一个小于该随机数的位置,就是轮盘指向的位置
child_xg{i} = xg{select_idx}; % 将轮盘选出的个体选入下一代种群
end
end遗传算法求解TSP-代码实现
运行结果：
可以看到，在有限的步数内，程序已经能自动找到一条不错的路径了
说明本文设计的遗传算法在解决TSP问题是有效的
End
