bp算法运行太慢_遗传算法（GA）求解旅行商问题（TSP）附MATLAB代码

​hello&＃xff0c;大家好&＃xff0c;今天为大家更新一期使用遗传算法&＃xff08;GA&＃xff09;求解旅行商问题&＃xff08;TSP&＃xff09;的推文。

本次推文所编写的代码使用如下进化操作&＃xff1a;

1、二元锦标赛选择操作&＃xff1b;

2、OX交叉操作&＃xff1b;

3、交换、逆转和插入相结合的变异操作。

一 | 旅行商&＃xff08;TSP&＃xff09;问题

假设有一个旅行商人要拜访n个城市&＃xff0c;他必须选择所要走的路径&＃xff0c;路径的限制是每个城市只能拜访一次&＃xff0c;而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

二 | 算法设计

01 | 编码

编码采用常规的整数编码&＃xff0c;如果城市数目为N&＃xff0c;那么解就可以表达为1~N的随机排列&＃xff0c;用MATLAB中的randperm(N)进行表示。

02 | 种群初始化

设种群数目为NIND&＃xff0c;则初始化种群为NIND个1~N的随机排列。

03 | 目标函数值

一个个体的目标函数值就是该个体的总距离&＃xff0c;比如说一个个体为213&＃xff0c;那么这个个体的总距离&＃61;21之间的距离&＃43;13之间的距离&＃43;32之间的距离&＃xff08;从3出发还需要返回起始点2&＃xff09;。

04 | 适应度值

一个个体的适应度值是其目标函数值的倒数。因为总距离越小说明这个个体质量越好&＃xff0c;所以适应度值越大就说明这个个体质量越好。

05 | 二元锦标赛选择操作

之前更新遗传算法的推文中&＃xff0c;都使用的是轮盘赌选择操作&＃xff0c;今天来点不一样的&＃xff0c;没错就是二元锦标赛选择。

首先需要理解什么是二元锦标赛选择&＃xff0c;我们把这个操作拆成两部分&＃xff0c;一部分是二元&＃xff0c;一部分是锦标赛选择。

首先来看锦标赛选择&＃xff0c;锦标赛其实就是一种比赛&＃xff0c;有多个选手参加比赛&＃xff0c;一般情况下最后只有一个冠军。所以我们在这里可以将多个选手看作多个个体&＃xff0c;最后的一个冠军我们可以看作是这些个体中最好的那个个体。

然后再看一下二元是什么意思呢&＃xff1f;既然有二元&＃xff0c;是否有三元、四元……&＃xff0c;对的&＃xff0c;确实是有的&＃xff0c;二元就相当于有两个选手参加锦标赛&＃xff0c;三元就相当于有三个选手参加锦标赛……。

所以&＃xff0c;二元锦标赛就是比较两个个体&＃xff0c;然后将其中更好的那一个个体选择出来&＃xff0c;放到选出的种群当中。其实也可以有三元锦标赛、四元锦标赛……&＃xff0c;但这里为了方便我们就选择使用二元锦标赛了。

06 | OX交叉操作

比如说有两个父代个体为
父代1&＃xff1a;1 2 3 4 5 6 7 8
父代2&＃xff1a;8 7 6 5 4 3 2 1
这时随机选择两个交叉位置a和b&＃xff0c;比如说a&＃61;3&＃xff0c;b&＃61;6&＃xff0c;那么交叉的片段为&＃xff1a;
父代1&＃xff1a;1 2 | 3 4 5 6 | 7 8
父代2&＃xff1a;8 7 | 6 5 4 3 | 2 1
然后将父代2的交叉片段移动到父代1的前面&＃xff0c;将父代1的交叉片段移动到父代2的前面&＃xff0c;则这两个父代个体变为&＃xff1a;
父代1&＃xff1a;6 5 4 3 1 2 3 4 5 6 7 8
父代2&＃xff1a;3 4 5 6 8 7 6 5 4 3 2 1
然后从前到后把第2个重复的基因位删除掉&＃xff0c;我们先把两个父代个体中重复的基因位标记出来&＃xff1a;
父代1&＃xff1a;6 5 4 3 1 2 3 4 5 6 7 8
父代2&＃xff1a;3 4 5 6 8 7 6 5 4 3 2 1
然后把第2个重复的基因位删除&＃xff0c;形成两个子代个体。
子代1&＃xff1a;6 5 4 3 1 2 7 8
子代2&＃xff1a;3 4 5 6 8 7 2 1

07 | 变异操作

&＃xff08;1&＃xff09;交换操作

比如说有6个城市&＃xff0c;当前解为123456&＃xff0c;我们随机选择两个位置&＃xff0c;然后将这两个位置上的元素进行交换。

比如说&＃xff0c;交换2和5两个位置上的元素&＃xff0c;则交换后的解为153426。

&＃xff08;2&＃xff09;逆转操作

有6个城市&＃xff0c;当前解为123456&＃xff0c;我们随机选择两个位置&＃xff0c;然后将这两个位置之间的元素进行逆序排列。

比如说&＃xff0c;逆转2和5之间的所有元素&＃xff0c;则逆转后的解为154326。

&＃xff08;3&＃xff09;插入操作

有6个城市&＃xff0c;当前解为123456&＃xff0c;我们随机选择两个位置&＃xff0c;然后将这第一个位置上的元素插入到第二个元素后面。

比如说&＃xff0c;第一个选择2这个位置&＃xff0c;第二个选择5这个位置&＃xff0c;则插入后的解为134526。

在变异操作中&＃xff0c;我们将以上三种操作赋予不同的权重&＃xff0c;然后采用轮盘赌的方式选择究竟使用哪个操作。

三 |输入数据

22个城市的xy坐标。

四 |运行效果展示

五 | 问题与思考

可以看出使用同样的数据&＃xff0c;GA的优化效果不如模拟退火&＃xff08;SA&＃xff09;算法求解旅行商 &＃xff08;TSP&＃xff09;问题MATLAB代码讲解 这篇推文使用SA的优化效果&＃xff0c;各位可以想一下如何可以提高GA的优化效果&＃xff1f;提示&＃xff1a;将SA以一定概率接受比当前解更差的解的思想&＃xff0c;融入到GA中。

六 |MATLAB源代码

关注微信公众号&＃xff1a;优化算法交流地&＃xff0c;后台回复 GATSP&＃xff0c;点开推文&＃xff0c;即可提取代码

往期精选

• 车辆路径问题&＃xff08;VRP&＃xff09;合集
• 遗传算法求解0-1背包问题&＃xff08;附matlab源代码&＃xff09;
• 模拟退火&＃xff08;SA&＃xff09;算法求解旅行商 &＃xff08;TSP&＃xff09;问题MATLAB代码讲解
• 多目标优化 | 基于NSGA-II的多目标0-1背包问题求解&＃xff08;附matlab代码&＃xff09;
• 多目标优化 | NSGA-II进阶教程&＃xff08;全网首个三目标优化教程&＃xff09;
• 机器学习 | 基于遗传算法的BP神经网络优化算法&＃xff08;附MATLAB代码&＃xff09;
• 遗传算法求解车间调度问题&＃xff08;附MATLAB代码&＃xff09;
• 多目标优化 | NSGA-II
• word转换为pdf后图片失真的解决办法&＃xff08;全网首发&＃xff09;
• 机器学习 | 简单实现Bp神经网络
• 二维装箱问题之BL法修正版&＃xff08;附MATLAB代码&＃xff09;
• 快速入门文献管理软件-EndNote X9
• 最小二乘法&＃xff08;附MATLAB代码&＃xff09;
• NSGA-II多目标优化算法讲解&＃xff08;附MATLAB代码&＃xff09;
• 基于人工势场法的机器人二维路径规划&＃xff08;附MATLAB代码&＃xff09;
• 基于粒子群算法的多目标搜索算法讲解&＃xff08;附MATLAB代码&＃xff09;
• 蚁群算法通俗讲解&＃xff08;附MATLAB代码&＃xff09;
• 混合粒子群算法通俗讲解&＃xff08;附MATLAB代码&＃xff09;

知乎 | bilibili&＃xff1a;随心390