版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

1. 前言

一直对遗传算法非常好奇,它是对自然界生物进化机制的计算机模拟。可以用于对NP问题的最优化求解。
在生活中,可以被用于排班、排课、路径优化,甚至可以被用于歌曲自动编写。

2. 问题分析

遗传算法的一个典型案例是针对旅行商问题。 旅行商问题,一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

我们从一个最简单的情况来说明这个问题。
屏幕快照 2019-02-18 下午3.19.02.png-50.9kB

例1:假定有A、B、C、D四个地点,坐标如上图
假定出发点是A点,那么所有的可能的路径是

  • ABCDA
  • ABDCA
  • ACBDA
  • ACDBA
  • ADBCA
  • ADCBA

由于起点和终点都是A,是完全确定的;所以所有可能的路径就是B、C、D的全排列
共有n!中情况,此处n为3,共有6种情况
我们实际是在解空间中寻找最优解。
当n=20时
20!= 2,432,902,008,176,640,000
当n=21时,解空间的大小已经溢出了int64所能存储的空间
解空间相当大,以至于遍历一遍几乎是不大可能的

3. 遗传算法如何寻找最优解

事实上,遗传算法得到有可能得到最优解,也有可能得到次优解。

下面是遗传算法的完整过程
image_1d3dl5h72fps47oavmb2v5na9.png-164.4kB

3.1 编码

让我们再回到例1,由于只有6种情况,那么解空间的取值范围就是 [0, 5]
假定如下的对应关系

  • BCD — 0 — 000
  • BDC — 1 — 001
  • CBD — 2 — 010
  • CDB — 3 — 011
  • DBC — 4 — 100
  • DCB — 5 — 101

解被转换为数值以后,就可以使用2进制进行表示

3.2 初始化种群

image_1d3vtsnqhogl6kf1p6r11emh7a25.png-99.4kB
如上图所示,X轴是整个解空间(没错,并且还是连续的,不过只能取整数),Y轴是我们期望达到的最短路径值。

初始情况,我们会随机的在解空间挑选几个点。

3.2 评估种群个体的适应度

很明显对于旅行商问题,整个路径越短,适应度越高(Y轴)

3.4 交叉

交叉是为了进行种群的繁殖。并且交叉的过程会保留亲代的特征。通常获得的下一代会在亲代的坐标点附近。

常见的交叉算法
1. 单点杂交
2. 多点杂交
3. 均匀杂交
4. 洗牌杂交
在我的代码实现中,我使用的是单点交叉

3.5 变异

近亲繁殖容易导致畸形儿。近亲的交叉,会使得子代聚集在它们附近,从而收敛在次优解上,而忽略了真正的最优解。
为了避免这个问题,引入变异
变异的具体做法,是对解对应数值的2进制表示的某一位进行翻转,0变成1,1变成0。

变异带来的直接效果是,子代的值会在x轴(解空间)上跳跃,种群中的个体在解空间分布的更加随机,增强了种群的多样性。

3.6 选择

如果不控制种群的数量,在解空间较小的情况下,种群的规模有可能会覆盖整个解空间。

由于每次迭代(交叉和变异)非常耗时,所以有必要限制种群的规模。

希望达到的效果
image_1d429vepttd21ro4ck210ct1su83c.png-28.9kB
经过若干次迭代,种群中的个体,将会大量分布在最优解以及次优解附近。

常见选择算法
1. 轮盘选择算法 roulette wheel selection
2. 锦标赛选择算法 tournament selection
3. 随机遍历抽样算法

需要注意的问题:
选择算法不能简单的将个体的适应度排序,然后剔除适应度最差的节点。这样有可能会导致种群失去多样性,而最终收敛在次优解上。

从人类社会的演化,我们似乎能找到某种共同性。比如如果按照指令性的方式去管理经济,得到的是高效服从命令的企业,但是整个社会又会缺乏创造性。

4. 样例代码

test2.go

...

func main() {
    positions := []string{"北京", "天津", "上海", "重庆", "拉萨", "乌鲁木齐",
        "银川", "呼和浩特", "南宁", "哈尔滨", "长春", "沈阳", "石家庄",
        "太原", "西宁"}
    // 最大迭代次数
    maxIterCount := tsp.MaxIterationCountOption(200)
    // 种群中最大个体数量
    maxPopulationSize := tsp.MaxPopulationSizeOption(1000)
    // 设置选择算法
    selectFunc := tsp.SelectAlgOption(tsp.RandomTraverseSampleSelection)
    //selectFunc := tsp.SelectAlgOption(tsp.RouletteWheelSelection)
    //selectFunc := tsp.SelectAlgOption(tsp.TournamentSelection)

    t := tsp.NewTSP(positions, distance2, maxIterCount, maxPopulationSize, selectFunc)
    result := t.Slove()
    fmt.Println("---result---:", result, "route distance", t.RouteDistance(result))
    // 输入到文件,以便绘图观察
    write2File(result, "/tmp/1.csv")

}
...

5. 绘图

可以使用R语言来绘制路径图

library(ggplot2)
data = read.table("/tmp/1.csv",header=F, sep=",")
traveller_way = read.table("/tmp/1.csv",header=TRUE, sep=",")

m <- ggplot(traveller_way, aes(X, posY))
m + geom_path()

经过200次迭代,花费的时间是6.5秒,就找到15个城市的旅行商问题的解决方案,遗传算法还是非常高效的。
image_1d42blncg1nho1qhds7519q11gns3p.png-32.3kB

6 传送门

项目地址
vearne/tsp

7. 参考资料

  1. 遗传算法
  2. 旅行商问题
  3. 遗传算法详解

如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

1 对 “使用遗传算法来解决旅行商问题”的想法;

  1. 感谢分享!已推荐到《开发者头条》:https://toutiao.io/posts/q28fp8 欢迎点赞支持!使用开发者头条 App 搜索 334598 即可订阅《萌叔》

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据