前言本文总结了遗传算法中的几种选择策略，包括：ProportionateRouletteWheelSelectionLinearRankingSelectionExponentialRankingSelectionTournamentSelection对于每一种选择策略我都用Python进行了相应的实现和以内置插件的形式集成到我写的遗传算法框架GAFT中。可以作为需要用到遗传算法优化问题和学习遗传算法的童鞋们的参考。项目链接：GitHub：https://github.com/PytLab/gaftPyPI：https://pypi.python.org/pypi/gaft遗传算法中的选择算子遗传算法（geneticalgorithms，GAs）是一种自动自适应启发式搜索算法，它模仿达尔文进化论中“适者生存”的原理，最终得到优化目标的最优解。下图描述了一个简单的遗传算法过程：需要在种群中进行交叉的物种选择方法有很多，选择合适的选择策略将对遗传算法的整体性能产生很大的影响。如果一个选择算法降低了选择多样性，就会导致种群过早地收敛到局部最优而不是我们想要的全局最优，这就是所谓的“过早”。但是，如果选择策略过于发散，算法将难以收敛到最优点。因此，我们需要平衡这两点，使遗传算法能够高效地收敛到全局最优。GAFT框架中的算子插件GAFT是我根据自己的需要开发的一个遗传算法框架。相关博客请参考《GAFT-一个使用Python实现的遗传算法框架》、《使用MPI并行化遗传算法框架GAFT》。该框架提供了插件接口，用户可以使用自定义算子和on-the-fly分析插件将它们放入GAFT框架中运行遗传算法过程来优化目标问题。这部分我会简单介绍一下gaft中遗传算子相关的接口规范，以及如何编写gaft中可以使用的算子。在Gaft中编写遗传算子，需要继承框架内置的基类，然后根据基类提供的接口实现自己的算子。基类的定义都在/gaft/plugin_interfaces/operators/目录中。下面我就以选择算子为例介绍一下接口。gaft中选择算子的基类是GASelection，在遗传算法过程中调用该类实例的select方法，然后根据运算符中的相关选择策略。基类的定义为：classGASelection(metaclass=SelectionMeta):'''Classforprovidinganinterfacetoeasilyextendthebehaviorofselectionoperation.'''defselect(self,population,fitness):'''Calledwhenweneedtoselectparentsfromapopulationtolaterbreeding.:parampopulation:Thecurrentpopulation.:typepopulation:GAPopulation:returnparents:Twoselectedindividualsforcrossover.:typeparents:TupleoftowGAIndividualobjects.'''raiseNotImplementedErrorselect方法的参数为当前种群种群和对应的适应度函数fitness，这里population需要是一个GAPopulation对象，fitness也必须是一个可调用对象。当然，这些在Python这样的动态类型语言中显得有些鸡肋，但是为了更规范的给用户使用，我在实例化类对象时，使用Python的元类来限制接口的实现和接口的参数类型.具体实现在/gaft/plugin_interfaces/metaclasses.py，感兴趣的童鞋可以看看实现方法。具体的自定义算子的写法和选择策略我会在下篇贴出。不同的选择策略这部分我主要总结了四种不同的选择策略，并以gaft插件的形式在Python中实现。选择算子决定了从种群中选出哪些个体来繁殖下一代种群中的新个体。主要原则是：个人越好；选择算子在遗传算法的迭代中引入了适应度函数，因为适应度函数是标定一个个体是否足够“好”的重要标准。但是选择过程不能完全依赖于适应度函数，因为种群中的最优物种不一定在全局最优点附近。因此，我们也应该给相对不那么“好”的个体一个繁衍的机会，避免“早熟”。选择算子在遗传算法的迭代中引入了适应度函数，因为适应度函数是标定个体是否“足够好”的重要标准。但是选择过程不能完全依赖于适应度函数，因为种群中的最优物种不一定在全局最优点附近。因此，我们也应该给相对不那么“好”的个体一个繁衍的机会，避免“早熟”。ProportionateRouletteWheelSelection这种轮盘选择策略是最基本的选择策略之一。种群中个体被选中的概率与个体对应的适应度函数值成正比。我们需要对种群中所有个体的适应度值进行累加归一化，最后用随机数选择随机数落在区域对应的个体，类似于赌场中的旋转轮盘赌。每个单独的ai被选中的概率是：那么，这个算法可以写成一个可以在gaft中执行的运算符。fromrandomimportrandomfrombisectimportbisect_rightfromitertoolsimportaccumulatefrom...plugin_interfaces.operators.selectionimportGASelectionclassRouletteWheelSelection(GASelection):def__init__(self):'''Selectionoperatorwithfitnessproportionateselection(FPS)或者所谓的轮盘赌轮盘选择实现。'#Normalizefitnessvaluesforallindividuals.fit=[fitness(indv)forindvinpopulation.individuals]min_fit=min(fit)fit=[(i-min_fit)foriinfit]#Createroulettewheel.sum_fit=sum(fit)wheel=list(accumulate([i/sum_fitforiinfit]))#Selectafatherandamother.father_idx=bisect_right(wheel,random())father=population[father_idx]mother_idx=(father_idx+1)%len(wheel)mother=population[mother_idx]returnfather,mother进程主要分为以下：继承GASelection类实现select方法。select的参数是GAPopulation实例和适应度函数。根据算法选择两个需要繁殖的物种归还。锦标赛选择由于算法执行效率高和易于实现的特点，锦标赛选择算法是遗传算法中最流行的选择策略。在我的实际应用中，这个策略确实比基本轮盘赌更有效。他的策略也很直观，就是我们从整个种群中抽取n个个体，让他们进行比赛（锦标赛），抽取其中最好的个体。参加比赛的个人人数成为比赛规模。通常n=2时最常用的大小，也称为BinaryTournamentSelection。TournamentSelection的优点：复杂度O(n)较小，易于并行化处理，不易陷入局部最优，不需要所有适应度值被排序。下图展示了n=3的TournamentSelection的流程：你可以开始写一个自定义算子，在Gaft上运行：fromrandomimportsamplefrom...plugin_interfaces.operators.selectionimportGASelectionclassTournamentSelection(GASelection):def__init__(self,tournament_size=2)：'''SelectionoperatorusingTournamentStrategywithtournamentsizeequalstotwobydefault.'''self.tournament_size=tournament_sizedefselect(self,population,fitness):'''SelectapairofparentusingTournamentstrategy.'''#Competitionfunction.complete=lambdacompetitors:max(competitors,key=fitness)#Checkvalidityoftournamentsize.ifself。tournament_size>=len(population):msg='Tournamentsize({})islargerthanpopulationsize({})'raiseValueError(msg.format(self.tournament_size,len(population)))#Pickwinnersoftwogroupsasparent.competitors_1=sample(population.individuals,self.tournament_size)competitors_2=sample(population.individuals,self.tournament_size)father,mother=complete(competitors_1),complete(competitors_2)returnfather,mother下面两种选择策略都是基于排序的选择策略。上面提到的第一种基本轮盘赌选择算法有一个缺点，即如果一个个体的适应度值为0，那么被选中的概率就会为0，这个个体将无法产生后代。因此，我们需要一种基于排序的算法来为每个个体安排相应的选择概率。在线性排序选择中，种群中的个体首先根据适应度值进行排序，然后为所有个体分配一个序号，最好的个体为N，被选中的概率为Pmax，最差的个体为1，而被选中的概率为Pmin，所以其中其他个体的概率可以根据以下公式得到：实现代码：fromrandomimportrandomfromitertoolsimportaccumulatefrombisectimportbisect_rightfrom...plugin_interfaces.operators.selectionimportGASelectionclassLinearRankingSelection(GASelection):def__init__(self,pmin=0.9,pmax=0.):'''SelectionoperatorusingLinearRankingselectionmethod.Reference:BakerJE.Adaptiveselectionmethodsforgeneticalgorithms[C]//ProceedingsofanInternationalConferenceonGeneticAlgorithmsandtheirapplications.1985:101-111.'''#Selectionprobabilitiesfortheworstandbestindividuals.self.pmin,self.pmaxulation=self.pmin,pop.pmaxulation国际会议论文集,健身):'''选择一对父个体使用线性排名方法。'''#Individualnumber.NP=len(population)#Addranktoallindividualsinpopulation.sorted_indvs=sorted(population.individuals,key=fitness,reverse=True)#Assignselectionprobabilitieslinearly.#NOTE:Heretorankibel{1..,N}p=lambdai:(self.pmin+(self.pmax-self.pmin)*(i-1)/(NP-1))概率=[self.pmin]+[p(i)foriinrange(2,NP)]+[self.pmax]#Normalizeprobabilities.psum=sum(probabilities)wheel=list(accumulate([p/psumforpinprobabilities]))#Selectparents.father_idx=bisect_right(wheel,random())father=population[father_idx]mother_idx=(father_idx+1)%len(wheel)mother=population[mother_idx]returnfather,mother类似于上面的LinearRanking选择策略，这种索引排序在确定每个个体的选择概率时使用索引的表达式形式，其中c为基数，满足0
