遗传算法中几种不同选择算子及如何用Python实现
这篇文章将为大家详细讲解有关遗传算法中几种不同选择算子及如何用Python实现，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
遗传算法中的选择算子
遗传算法(genetic algorithms, GAs)是一种自适应的启发式搜索算法, 它模仿达尔文进化论中的“适者生存”的原则, 最终获取优化目标的最优解。下图描述了一个简单的遗传算法流程:
对于种群中需要进行杂交的物种选择方法有很多，而且选择一种合适的选择策略对于遗传算法整体性能的影响将是很大的。如果一个选择算法选择多样性降低，便会导致种群过早的收敛到局部最优点而不是我们想要的全局最优点，也就是所谓的”早熟”。而选择策略过于发散则会导致算法难以收敛到最优点。因此在这两点中我们需要进行平衡才能使遗传算法以一种高效的方式收敛到全局最优点。
| 不同的选择策略 |
本部分我主要对四种不同的选择策略进行总结并加以gaft插件形式的Python实现。
选择算子决定了哪些个体将会从种群中被选择出来用于繁衍下一代种群中的新个体。其主要的原则就是:
the better is an individual; the higher is its chance of being a parent
选择算子在遗传算法迭代中将适应度函数引入进来，因为适应度函数式标定一个个体是否足够“好”的重要标准。但是选择过程又不能仅仅完全依赖于适应度函数，因为一个种群中的最优物种并不一定是在全局最优点附近。因此我们也应该给相对来说并那么“好”的个体一点机会让他们繁衍后代, 避免“早熟”。
ai被选中的概率
好了，下面可以将此算法写成一个可以gaft中执行的算子。
Python
|
from random import random from bisect import bisect_right from itertools import accumulate
from ...plugin_interfaces.operators.selection import GASelection
class RouletteWheelSelection(GASelection): def __init__(self): ''' Selection operator with fitness proportionate selection(FPS) or so-called roulette-wheel selection implementation. ''' pass
def select(self, population, fitness): ''' Select a pair of parent using FPS algorithm. ''' # Normalize fitness values for all individuals. fit = [fitness(indv) for indv in population.individuals] min_fit = min(fit) fit = [(i - min_fit) for i in fit]
# Create roulette wheel. sum_fit = sum(fit) wheel = list(accumulate([i/sum_fit for i in fit]))
# Select a father and a mother. father_idx = bisect_right(wheel, random()) father = population[father_idx] mother_idx = (father_idx + 1) % len(wheel) mother = population[mother_idx]
return father, mother |
过程主要分为下面几个:
继承GASelection类
实现select方法
select的参数为GAPopulation实例和适应度函数
根据算法选择出两个需要繁衍的物种并返回即可
| Linear Ranking Selection |
下面两个介绍的选择策略都是基于排序的选择策略，上面提到的第一种基本轮盘赌选择算法，有一个缺点，就是如果一个个体的适应度值为0的话，则被选中的概率将会是0, 这个个体将不能产生后代。于是我们需要一种基于排序的算法，来给每个个体安排相应的选中概率。
在Linear Ranking Selection中，种群中的个体首先根据适应度的值进行排序，然后给所有个体赋予一个序号，最好的个体为N, 被选中的概率为Pmax, 最差的个体序号为1, 被选中的概率为Pmin，于是其他的在他们中间的个体的概率便可以根据如下公式得到:
实现代码:
Python
|
from random import random from itertools import accumulate from bisect import bisect_right
from ...plugin_interfaces.operators.selection import GASelection
class LinearRankingSelection(GASelection): def __init__(self, pmin=0.1, pmax=0.9): ''' Selection operator using Linear Ranking selection method. Reference: Baker J E. Adaptive selection methods for genetic algorithms[C]//Proceedings of an International Conference on Genetic Algorithms and their applications. 1985: 101-111. ''' # Selection probabilities for the worst and best individuals. self.pmin, self.pmax = pmin, pmax
def select(self, population, fitness): ''' Select a pair of parent individuals using linear ranking method. ''' # Individual number. NP = len(population) # Add rank to all individuals in population. sorted_indvs = sorted(population.individuals, key=fitness, reverse=True)
# Assign selection probabilities linearly. # NOTE: Here the rank i belongs to {1, ..., N} p = lambda i: (self.pmin + (self.pmax - self.pmin)*(i-1)/(NP-1)) probabilities = [self.pmin] + [p(i) for i in range(2, NP)] + [self.pmax]
# Normalize probabilities. psum = sum(probabilities) wheel = list(accumulate([p/psum for p in probabilities]))
# Select parents. father_idx = bisect_right(wheel, random()) father = population[father_idx] mother_idx = (father_idx + 1) % len(wheel) mother = population[mother_idx]
return father, mother |
cdn2.b0.upaiyun.com/2017/09/eff96de9a902d02b9f89266bd3adbdba.png" alt="WX20170919-222353@2x" br="" table="" tbody="" tr="" td="" data-settings="show" eeeeee="">
|
文中的选择策略分别根据接口的要求实现了相应的算子，这些算子也作为GAFT框架的内置算子放入到GAFT中，对于使用GAFT的童鞋可以直接拿来使用。 <h3 id="参考" color:#2E2E2E;white-space:normal;background-color:#FFFFFF;"> 参考
|
关于遗传算法中几种不同选择算子及如何用Python实现就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。