【元启发式算法】基于序列优化的遗传算法常用变异算子

问题描述

很多问题的优化可以建模为基于序列的优化，如旅行商问题（TSP）,排产问题，各类资源分配问题等，不同的序列有不同的优度。寻找最优序列的问题是NP难问题（其解空间为N!）。

解决方法

常用两种方法解决这类问题：一种是启发式算法，基于问题本身的规则得到较好的可行解，本质是贪心算法，这种方法速度较快，但因与问题本身联系紧密（problem-specific）,导致其通用性较差。

另一种方法是元启发式算法，例如遗传算法、禁忌搜索算法、蚁群算法、模拟退火算法等。这类方法从进化，物理等过程中受到启发，得到一种解空间的搜索策略，因其搜索策略独立于问题本身（problem-independent）,因此通用性强。这类方法有两个最本质的操作：

选择

改变

选择

选择的策略基本分为三类：

选择最优解（遗传算法常选择前N个最优解，防止进入局部极小值；禁忌搜索选择1个最优的解，通过禁忌策略跳出局部极小值）。

轮盘赌选择（根据每个解的评价值S，通过某种映射F（线性、指数等），得到每个解的概率P，然后根据概率选择解），公式：P = F(S)，从而避免选择最优解，陷入局部极小值。

锦标赛选择（从所有解中随机抽取N个，再从N个中找最优解），有点神经网络中dropout的思想，也是种避免陷入局部极小值的策略。

改变

常用的改变策略有交叉和变异，但本质都是从一个解改变为另一个解，如基于序列优化的问题，就是从一个序列，变为另一个序列（1,2,3 -> 2,1,3）,改变策略要兼顾保留原始解已有的良好结构，同时高效的探索新的结构。改变策略对于元启发式算法的效果和效率起到决定性作用，因此本文主要重点介绍几个变异算子。

Swap(交换算子)

基本操作：随机交换序列中的一对（或多对）数字，形成新序列。

Cross(交叉算子)

基本操作：序列自交叉，将序列分组，随机按组打乱重排。

Flip(翻转算子)

基本操作：将序列分组，每组翻转后重组。

Untie(结结算子)

基本操作：将序列分为三段，对中间一段翻转，形成新序列。

Shift(转移算子)

基本操作：将序列中的一个数字转移到序列中的另一个位置。

Cross_and_untie(组合算子)

基本操作：交叉算子和解锁算子的组合操作。

graft(嫁接算子)

基本操作：将序列中的某段截取后，随机嫁接到剩余序列。

总结：

第一代：swap, 第二代：cross, flip, 第三代：untie, shift, graft

shift: 能找到接近最优值的算子, 但不稳定

untie: 能在最快时间找到接近最优解的算子， 稳定性很强

cross_and_untie: 种群数量足够大时，效果优于untie算子

运筹优化

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。