遗传算法中⼏种不同选择算⼦及Python实现
前⾔
本⽂对遗传算法中的⼏种选择策略进⾏了总结, 其中包括:
1. Proportionate Roulette Wheel Selection
2. Linear Ranking Selection
3. Exponential Ranking Selection
4. Tournament Selection
对于每种选择策略我都使⽤Python进⾏了相应的实现并以内置插件的形式整合进了本⼈所写的遗传算法框架GAFT中。对需要使⽤遗传算法
优化问题以及学习遗传算法的童鞋可以作为参考.
项⽬链接:实例化类和实例化对象
GitHub:
PyPI:
遗传算法中的选择算⼦
遗传算法(genetic algorithms, GAs)是⼀种⾃适应的启发式搜索算法, 它模仿达尔⽂进化论中的“适者⽣存”的原则, 最终获取优化⽬标的
最优解。下图描述了⼀个简单的遗传算法流程:
对于种中需要进⾏杂交的物种选择⽅法有很多，⽽且选择⼀种合适的选择策略对于遗传算法整体性能的影响将是很⼤的。如果⼀个选择算
法选择多样性降低，便会导致种过早的收敛到局部最优点⽽不是我们想要的全局最优点，也就是所谓的”早熟”。⽽选择策略过于发散则
会导致算法难以收敛到最优点。因此在这两点中我们需要进⾏平衡才能使遗传算法以⼀种⾼效的⽅式收敛到全局最优点。
GAFT框架中的算⼦插件
GAFT是我根据⾃⼰需求开发的⼀个遗传算法框架，相关介绍的博客可以参见《》,《》。该框架提供了插件接⼝，⽤户可以通过⾃定义算⼦
以及on-the-fly分析插件来放到gaft框架中运⾏遗传算法流程对⽬标问题进⾏优化。
本部分我稍微介绍下gaft关于遗传算⼦相关接⼝规范，以及编写能⽤于gaft的算⼦的编写⽅法。
在gaft中遗传算⼦的编写都是需要继承框架内置的基类，然后根据基类提供的接⼝，实现⾃⼰的算⼦。其中基类的定义都在⽬录下，下⾯我
以选择算⼦为例，介绍下接⼝。
gaft中选择算⼦的基类为GASelection，其中在遗传算法流程中会调⽤该类实例的select⽅法，进⽽根据算⼦中的相关选择策略完成从种中
选取⼀对物种作为⽗亲和母亲产⽣⼦代。基类的定义为：
class GASelection(metaclass=SelectionMeta):    '''    Class for providing an interface to easily extend the behavior of selection    operation.    '''    def select(self, po
select的⽅法的参数为当前种population以及相应的适应度函数fitness，其中population需要是GAPopulation对象，fitness也必须是
callable的对象。
利⽤Python的元类在实例化类对象的
当然，这些在Python这种动态类型语⾔中貌似看起来有些鸡肋，但是为了能够更加规范使⽤者，我利⽤Python的元类在实例化类对象的
时候对接⼝的实现以及接⼝的参数类型加以限制。具体的实现都在中，有兴趣的童鞋可以看看实现⽅法。
时候对接⼝的实现以及接⼝的参数类型加以限制
具体⾃定义算⼦的编写⽅法我将在下⼀部分同选择策略⼀起贴出来。
不同的选择策略
本部分我主要对四种不同的选择策略进⾏总结并加以gaft插件形式的Python实现。
选择算⼦决定了哪些个体将会从种中被选择出来⽤于繁衍下⼀代种中的新个体。其主要的原则就是:
the better is an individual; the higher is its chance of being a parent
选择算⼦在遗传算法迭代中将适应度函数引⼊进来，因为适应度函数式标定⼀个个体是否⾜够“好”的重要标准。但是选择过程⼜不能仅仅
完全依赖于适应度函数，因为⼀个种中的最优物种并不⼀定是在全局最优点附近。因此我们也应该给相对来说并那么“好”的个体⼀点机
会让他们繁衍后代, 避免“早熟”。
Proportionate Roulette Wheel Selection
此赌选择策略，是最基本的选择策略之⼀，种中的个体被选中的概率与个体相应的适应度函数的值成正⽐。我们需要将种中所有个
体的适应度值进⾏累加然后归⼀化，最终通过随机数对随机数落在的区域对应的个体进⾏选取，类似⾥⾯的旋转的。
每个个体ai被选中的概率为:
好了，下⾯可以将此算法写成⼀个可以gaft中执⾏的算⼦。
from random import randomfrom bisect import bisect_rightfrom itertools import accumulate from ...plugin_interfaces.operators.selection import GASelection class 过程主要分为下⾯⼏个:
1. 继承GASelection类
2. 实现select⽅法
3. select的参数为GAPopulation实例和适应度函数
4. 根据算法选择出两个需要繁衍的物种并返回即可
Tournament Selection
由于算法执⾏的效率以及易实现的的特点，锦标赛选择算法是遗传算法中最流⾏的选择策略。在本⼈的实际应⽤中的确此策略⽐基本的
赌效果要好些。他的策略也很直观，就是我们再整个种中抽取n个个体，让他们进⾏竞争(锦标赛)，
抽取其中的最优的个体。参加锦标赛
的个体个数成为tournament size。通常当n=2便是最常使⽤的⼤⼩，也称作Binary Tournament Selection.
Tournament Selection的优势:
1. 更⼩的复杂度O(n)
2. 易并⾏化处理
3. 不易陷⼊局部最优点
4. 不需要对所有的适应度值进⾏排序处理
下图显⽰了n=3的Tournament Selection的过程:
可以开始写成⾃定义算⼦在gaft运⾏了:
from random import sample from ...plugin_interfaces.operators.selection import GASelection class TournamentSelection(GASelection):    def __init__(self,
Linear Ranking Selection
下⾯两个介绍的选择策略都是基于排序的选择策略，上⾯提到的第⼀种基本赌选择算法，有⼀个缺点，就是如果⼀个个体的适应度值为
0的话，则被选中的概率将会是0, 这个个体将不能产⽣后代。于是我们需要⼀种基于排序的算法，来给每个个体安排相应的选中概率。
在Linear Ranking Selection中，种中的个体⾸先根据适应度的值进⾏排序，然后给所有个体赋予⼀个序号，最好的个体为N, 被选中的
概率为Pmax, 最差的个体序号为1, 被选中的概率为Pmin，于是其他的在他们中间的个体的概率便可以根据如下公式得到:
实现代码:
from random import randomfrom itertools import accumulatefrom bisect import bisect_right from ...plugin_interfaces.operators.selection import GASelectio
Exponential Ranking Selection
类似上⾯的Linear Ranking选择策略，这种指数排序便是在确定每个个体的选择概率的时候使⽤了指数形式的表达式, 其中c为底数，满⾜
0<c<1:
实现代码:
from random import randomfrom itertools import accumulatefrom bisect import bisect_right from ...plugin_interfaces.operators.selection import GASelectio 总结
本⽂对于遗传算法中四种不同的选择策略进⾏了介绍和总结，同时对于本⽂所写的遗传算法框架的⾃定义算⼦接⼝进⾏了简要的介绍，针对本⽂中的选择策略分别根据接⼝的要求实现了相应的算⼦，这些算⼦也作为GAFT框架的内置算⼦放⼊到GAFT中，对于使⽤GAFT的童鞋可以直接拿来使⽤。
参考
Shukla, Anupriya, Hari Mohan Pandey, and Deepti Mehrotra. “Comparative review of selection techniques in genetic algorithm.” Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE), 2015 International Conference on. IEEE, 2015.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。