hello,大家好,今天为大家更新一期使用遗传算法(GA)求解旅行商问题(TSP)的推文。
本次推文所编写的代码使用如下进化操作:
1、二元锦标赛选择操作;
2、OX交叉操作;
3、交换、逆转和插入相结合的变异操作。
一 | 旅行商(TSP)问题
假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
二 | 算法设计
01 | 编码
编码采用常规的整数编码,如果城市数目为N,那么解就可以表达为1~N的随机排列,用MATLAB中的randperm(N)进行表示。
02 | 种群初始化
设种群数目为NIND,则初始化种群为NIND个1~N的随机排列。
03 | 目标函数值
一个个体的目标函数值就是该个体的总距离,比如说一个个体为213,那么这个个体的总距离=21之间的距离+13之间的距离+32之间的距离(从3出发还需要返回起始点2)。
04 | 适应度值
一个个体的适应度值是其目标函数值的倒数。因为总距离越小说明这个个体质量越好,所以适应度值越大就说明这个个体质量越好。
05 | 二元锦标赛选择操作
之前更新遗传算法的推文中,都使用的是轮盘赌选择操作,今天来点不一样的,没错就是二元锦标赛选择。
首先需要理解什么是二元锦标赛选择,我们把这个操作拆成两部分,一部分是二元,一部分是锦标赛选择。
首先来看锦标赛选择,锦标赛其实就是一种比赛,有多个选手参加比赛,一般情况下最后只有一个冠军。所以我们在这里可以将多个选手看作多个个体,最后的一个冠军我们可以看作是这些个体中最好的那个个体。
然后再看一下二元是什么意思呢?既然有二元,是否有三元、四元……,对的,确实是有的,二元就相当于有两个选手参加锦标赛,三元就相当于有三个选手参加锦标赛……。
所以,二元锦标赛就是比较两个个体,然后将其中更好的那一个个体选择出来,放到选出的种群当中。其实也可以有三元锦标赛、四元锦标赛……,但这里为了方便我们就选择使用二元锦标赛了。
06 | OX交叉操作
比如说有两个父代个体为
父代1:1 2 3 4 5 6 7 8
父代2:8 7 6 5 4 3 2 1
这时随机选择两个交叉位置a和b,比如说a=3,b=6,那么交叉的片段为:
父代1:1 2 | 3 4 5 6 | 7 8
父代2:8 7 | 6 5 4 3 | 2 1
然后将父代2的交叉片段移动到父代1的前面,将父代1的交叉片段移动到父代2的前面,则这两个父代个体变为:
父代1:6 5 4 3 1 2 3 4 5 6 7 8
父代2:3 4 5 6 8 7 6 5 4 3 2 1
然后从前到后把第2个重复的基因位删除掉,我们先把两个父代个体中重复的基因位标记出来:
父代1:6 5 4 3 1 2 3 4 5 6 7 8
父代2:3 4 5 6 8 7 6 5 4 3 2 1
然后把第2个重复的基因位删除,形成两个子代个体。
子代1:6 5 4 3 1 2 7 8
子代2:3 4 5 6 8 7 2 1
07 | 变异操作
(1)交换操作
比如说有6个城市,当前解为123456,我们随机选择两个位置,然后将这两个位置上的元素进行交换。
比如说,交换2和5两个位置上的元素,则交换后的解为153426。
(2)逆转操作
有6个城市,当前解为123456,我们随机选择两个位置,然后将这两个位置之间的元素进行逆序排列。
比如说,逆转2和5之间的所有元素,则逆转后的解为154326。
(3)插入操作
有6个城市,当前解为123456,我们随机选择两个位置,然后将这第一个位置上的元素插入到第二个元素后面。
比如说,第一个选择2这个位置,第二个选择5这个位置,则插入后的解为134526。
在变异操作中,我们将以上三种操作赋予不同的权重,然后采用轮盘赌的方式选择究竟使用哪个操作。
三 |输入数据
22个城市的xy坐标。
x=[38.24,39.57,40.56,36.26,33.48,37.56,38.42,37.52,41.23,41.17,36.08,38.47,38.15,37.51,35.49,39.36,38.09,36.09,40.44,40.33,40.37,37.57];
y=[20.42,26.15,25.32,23.12,10.54,12.19,13.11,20.44,9.100,13.05,-5.210,15.13,15.35,15.17,14.32,19.56,24.36,23,13.57,14.15,14.23,22.56];
四 |运行效果展示
五 | 问题与思考
可以看出使用同样的数据,GA的优化效果不如模拟退火(SA)算法求解旅行商 (TSP)问题MATLAB代码讲解 这篇推文使用SA的优化效果,各位可以想一下如何可以提高GA的优化效果?
提示:将SA以一定概率接受比当前解更差的解的思想,融入到GA中。