simulink与遗传算法结合求解TSP问题

news/2024/5/17 10:12:52

前言：刚开始入门学习simulink，了解了基本的模块功能后想尝试从自己熟悉的领域入手，自己出题使用simulink搭建模型。选择的是TSP问题的遗传算法，考虑如何用simulink建模思想来实现一个简单TSP问题的遗传算法。

TSP问题描述

一个配送中心，8个需求点，各个需求点间的距离以及需求点离配送中心的距离已知，车辆从配送中心出发遍历每个需求点有且仅有一次，最后又回到配送中心，求最短的配送路线。

在这里插入图片描述

处理输入数据

万事开头难，从输入参数的配置开始吧。

主要是处理各个节点（配送中心+需求点）间的距离矩阵。

第一种方案：直接在查表模块中填写数据

在这里插入图片描述

第二种方案：也可以将excel表格中记录距离矩阵的数据导入.m文件，最后生成可以供查表模块使用的.mat文件数据

参考文章：Simulink仿真中将工作空间中的数据变量保存成.mat文件
https://blog.csdn.net/jk_101/article/details/120019475

在这里插入图片描述

本人采用的是第二种方案实现输入距离矩阵的处理。

用.m文件存储数据

clc;
clear;%% 处理各节点间的路线距离输入数据
%读取excel中，第一个sheet，B2-J10之间的内容
distance_data_file = 'distance_data.xlsx';
curr_path = matlab.desktop.editor.getActiveFilename;  % 获取当前.m脚本的工作路径
[pathstr, name, suffix] = fileparts(curr_path);  % 获取文件的上层父节点路径、文件名称、文件后缀
full_distance_path = fullfile(pathstr, distance_data_file);  % 拼接文件路径
distance_cube = xlsread(full_distance_path, 1, 'B2:J10');
save('distance_cube.mat', 'distance_cube');

9个节点（包括配送中心节点0）的距离数据存储在一个9*9的矩阵中，命名为distance_cube，使用save(‘distance_cube.mat’, ‘distance_cube’); 这条语句将从excel读取的距离矩阵存入distance_cube.mat供Simulink模型使用。

生成单条染色体

染色体编码方式采用整数编码方式，每一条染色体代表一种可行解，染色体中的每个基因位数字代表一个节点。

首先思考一条染色体在simulink中应该怎么表示？
假设：染色体A：0 1 2 3 4 5 6 7 8 0，可以直接使用constant模块表示

在这里插入图片描述

也可以使用Constant模块随机产生1-8的一维数组。

在这里插入图片描述

再使用Mux模块合并输入数据，得到一个以配送中心编号0开头和结尾的序列，这个序列就表示问题的一个可行解。

在这里插入图片描述

计算可行解的适应度函数

假设可行解为[0,1,2,3,4,5,6,7,8,0]

从基本单元“基因”开始处理

在这里插入图片描述

按照上面两个基因（节点）查表确认距离的思想，将基因使用Constant模块重组为一条染色体，计算单条染色体的适应度函数（总配送路线长度），备注：本博客提到的适应度函数不是真正意义上遗传算法要求的总运输距离的倒数，Simulink建模计算的染色体的适应度就是指代的总运输距离（车辆从配送中心出发依次经过8个需求点再返回配送中心的总路线长度）。

在这里插入图片描述

确定种群结构

假设染色体种群规模为10，采用Constant产生1-8个需求节点的随机序列，使用自定义的模块封装车辆从配送中心出发依次经过8个需求节点最后返回配送中心的过程。

自定义封装好的模块如下：

在这里插入图片描述

使用Mux模块合并输入数据（即10条染色体）组成形式上的种群，将输出结果采用To File模块存入initpopout.mat。

在这里插入图片描述

计算种群的适应度函数

将上一章节“确定种群结构”得到的输出序列存入Simulink的.mat文件，使用From File模块从initpopout.mat提取生成的种群结构作为输入，计算种群适应度函数的基本思想：使用Demux模块将1010的矩阵拆解成一维的110的列表，使用已经封装好的计算单条染色体的功能模块计算这个一维的1*10的列表，得到所有10条染色体的适应度函数（总运输距离的倒数）之后，再使用Mux模块合并列表作为一个输出信号，并且使用Min模块计算此时种群的最小运输距离。

在这里插入图片描述

主函数

本博客针对TSP问题只进行到种群生成及种群染色体的适应度函数计算，不涉及遗传算法进化迭代的选择、交叉及变异算子。

总结以上求解TSP问题的分解步骤，可以得到下图所示的总的模型：

在这里插入图片描述

参考文献：

1.Matlab读取excel文件中的数据
https://blog.csdn.net/qq_38826019/article/details/81184811
2.MATLAB-获取正在执行的m文件路径的方法
https://blog.csdn.net/qq_43278043/article/details/115922597
3.matlab函数-fullfile-将字符合并成路径
https://blog.csdn.net/weixin_37724055/article/details/109952562
4.matlab的输出(命令窗口、fprint函数、disp函数)
https://blog.csdn.net/caomin1hao/article/details/83996365
5.matlab 分割字符串、提取文件路径及文件名
https://blog.csdn.net/u012189747/article/details/86504693