Evolutionary Algorithm(EA)进化算法初探

夜半饿得慌 2019-11-09

算法 函数 Algorithm 多线程

问题

因工作需要,开始向算法的深水区迈进,其中就涉及到一种混合整数优化问题:CVRPTW 问题
1
cvrptw问题示例

顾名思义,CVRPTW 就是指带限制条件和时间窗口约束的车辆路径规划问题,而加入了时间窗口的约束条件后,优化目标已不再是简单的凹凸函数,这就意味着不能使用梯度下降、牛顿法等确定函数方法求解该问题(决策树、神经网络统统用不上了)

如果可以将CVRPTW的问题空间可视化的话,想象一下整个场景就是一个“喀斯特地貌”
1

之前习惯了确定方法求解凹凸问题,突然发现没有“套路”可循后,顿时思维陷入了混乱

而一般的动态规划问题求解器,或者混合整数求解器(google ortools、cplex等),只能处理小规模(<100)的约束优化问题
而市面上能快速处理1000个节点的求解器已经算是优秀了,但往往都是收费且价格不菲

随着节点数的增长,需要探索的路径,也会呈几何级数增长,所以传统的运筹学求解器,已在性能上无法满足需求

进化算法

EA进化算法 是一类算法的统称(包含遗传算法、粒子群算法、蚁群算法、鱼群算法、蝙蝠算法等等)
通过人工产生上千个种群个体、每一个体探索不同的路径,通过上百次迭代,从而找到帕累托最优解(有限组合方案最优)
2
进化算法示例

这种设计模式,充分的利用了分析主机多核并行的能力,加快了求解的速度,在性能上能满足大规模全局优化的需求
在解空间较小时,求解速度也很可观,兼顾了求解的准确性

关于进化算法,网上已经有了很详尽的资料,但信息太多反而容易造成信息过载,说多了等于没说

所以进化算法推荐看如下两篇文章就够了:

http://geatpy.com/index.php/2019/07/28/%e7%ac%ac%e4%b8%80%e7%ab%a0%ef%bc%9a%e6%a6%82%e8%bf%b0/

https://www.jianshu.com/p/8fa044ed9267

其他的文章不是摆公式就是摆代码,没什么意思

如果你觉得看这些文章也太麻烦,那我们就来个极简版的白话进化算法入门:

  这个世界上总有一类很难搞的问题,乍一看没什么规律,但各种限制,数学家称之为NP hard问题

  求解NP hard问题,就只能像探索迷宫一样,在指定的范围内不断探索,速度和方向可能是不断变化的

  指定的范围就是搜索空间

  而探索可以是多线程的

  探索的过程也可以是在之前经验的基础上不断累加的

这就是进化算法最直观的理解

不管它套上什么“遗传”、“粒子群”、“蚁群”等等的现实类比的外衣,都改变不了上述工作原理的本质

这样看来,进化算法的原理其实是很简单的

搜索设计

所以整个进化算法应用的关键,就是如何设计搜索空间和搜索行为

搜索空间设计的大小,直接决定了计算量的大小

搜索行为策略设计的好坏,直接决定了系统的搜索效率

3
搜索设计示例

回到我们最初的话题,CVRPTW 问题该如何设计呢?

谈到具体的问题,网上就很少有相关介绍资料了,设计思想大多隐藏在比较学术论文里,也让我苦恼了一阵子

CVRPTW 搜索设计

有几种主流设计方法:

1.将VRP问题转换为TSP问题,然后所有目标点逐一排列,形成一个庞大的排序空间,例如:[1,2,3,4,5,……],然后不断随机搜索
显然,这样导致的结果就是会有n!种组合方案,n越大越糟糕,而且没有考虑到TW时间窗口的限制

2.将VRP问题转换为QAP问题,通过就近原则等一系列贪婪规则,形成初始可行解,然后不断随机交换
这样导致的问题也是显而易见的,贪婪规则的主观性很强,很有可能漏掉部分解

1
一般设计思路示例

我的设计思路:

1.结合上述两种思想,将CVRPTW问题转换为约束优化问题;

2.最大限度的利用约束条件,形成尽可能小的搜索空间;

3.最大限度的减小系统随机性,搜索的每一步都尽可能的命中可行解;

4.在代价和目标之间做一个相对平衡的取舍;

总结

说了以上一堆,你也许觉得我啥都没说 :-)

是的,遇到NP hard问题,是没有万金油的,只能自己coding去尝试

关键把握住进化的四个阶段,一切就都清洗了:

1.搜索空间设计;2.搜索策略设计;3.评价方法;4.新搜索空间生成;

对应到术语层面就是:

1.种群初始化;2.基因编码、种群选择;3.评价函数设计;4.交换、变异;

最后推荐两款框架,大家可以自行搜索:deap, geat

https://github.com/DEAP/deap

https://github.com/geatpy-dev/geatpy

这两款框架都能很方便的实现你想要的进化算法

个人推荐deap,各个模块的设计相对宽松和灵活

遗留问题

1.进化算法的搜索速度:
迭代次数越多,找到的帕累托最优解更好,但很多生产场景其实是没有足够的时间留给模型慢慢摸索的
我也在不断尝试加速的可能
之前研究了AlphaGo及AlphaZero等技术,发现也是不能应用的,毕竟下棋或游戏是确定性策略的动作,而车辆路径中的上车点却是不确定的

2.进化算法的计算规模:
不管进化算法怎么迭代,总会受到计算规模的限制,缩小计算规模是是重中之重的工作
我也在不断寻找有没有可靠的降维策略理论和依据

以上,大家如有更好的解法,也请不吝赐教!

最后,祝大家在NP hard难搞的世界里好运!;->

登录 后评论
下一篇
云栖号
8111人浏览
2020-03-04
相关推荐
mahout所实现的算法
782人浏览
2017-11-12 11:46:00
架构风格:微服务
768人浏览
2018-11-18 20:18:27
Coding and Paper Letter(四十)
1070人浏览
2018-10-21 23:42:35
0
0
0
539