神经网络-一篇入门

【代码】遗传算法-求解TSP问题

作者 : 老饼 发表日期 : 2023-05-21 08:06:18 更新日期 : 2023-11-11 16:41:41
本站原创文章,转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com


本节展示一个使用遗传算法求解TSP问题的代码示例,

通过本文可以更具体地了解遗传算法的用途以及实现方式



  01. 遗传算法求解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是目标函数的值),就可以达到函数值越小,适应度越大的效果。

设计完以上三点后,只需按遗传算法的算法流程,实现代码即可






  02. 遗传算法求解TSP问题-代码实现  



本节按上节设计的算法,编写遗传算法求解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  







联系老饼