Python手把手构建遗传算法(GA)实现最优化搜索

《Python手把手构建遗传算法(GA)实现最优化搜索》

简介

遗传算法(Genetic Algorithm)顾名思义,是一种基于自然选择原理和自然遗传机制的启发式搜索算法。该算法通过模拟自然界中生物遗传进化的自然机制(选择、交叉和变异操作),将好的遗传基因(最优目标)不断遗传给子代,使得后代产生最优解的概率增加(后代还是会有一些差的结果)。它的整个算法流程如下:

《Python手把手构建遗传算法(GA)实现最优化搜索》

  1. 首先根据具体问题确定可行解域和编码方式,用数值串或字符串的形式表示可行解域中的每一个可行解;
  2. 构建适应度函数度量每一解,该函数为非负函数;
  3. 确定种群的大小、选择、交叉和变异的方式、交叉和变异的概率,判断终止条件(可以是某一阈值或者是指定进化的代数)。

在这个过程当中,交叉操作是优化的主要操作,而变异操作可以看成对种群的扰动。根据具体的问题我们构建适应度函数,并优化极值(可以是求最大值,也可以求最小值)。

名词解析

生物遗传概念在遗传算法中的对应关系如下:

生物遗传概念 遗传算法中的作用
适者生存 算法停止时,最优目标值的解大概率被找到
个体 每个可行解
染色体 对每个可行解的编码
基因 可行解中的每个组成部分
适应性 适应度函数的函数值
种群 可行解域,根据适应度函数选择的一组解
选择 保留适应度函数的函数值优的解
交叉 将两个可行解内的组分随机交叉,产生新解
变异 随机变异可行解中的某些组分

算法步骤

我们还是以一个简单的例子来讲解整个算法的流程。比如,我们需要寻找函数y=x12+x22+x33+x44[1,30]之间的最大值。我们很容易就知道,当x1=x2=x3=x4=30时,该函数能取到最大值。

首先我们构建一个叫Gene的类:

这个类只有一个初始化方法,该方法就是获得基因里面的内容和大小,在这个例子中,内容就是[1,30]之间的任意4个数字组成的列表。

接着构建一个叫GA的类,这个类包括算法的所有操作方法:

使用__init__()方法初始化参数,包括自变量可取的最大值,最小值,种群大小,交叉率,变异率和繁殖代数;使用evaluate()方法作为适应度函数评估该个体的函数值,在这里就是函数y的值;使用selectBest()方法挑选出当前代种群中的最好个体作为历史记录;使用selection()方法按照概率从上一代种群中选择个体,直至形成新的一代;使用crossoperate()方法实现交叉操作;使用mutation()方法实现变异操作;使用GA_main()方法实现整个算法的循环。

接下来我们会一一对其进行解析。

__init__()方法

__init__()方法的代码如下:

初始化方法接受传入的参数,包括最大值,最小值,种群大小,交叉率,变异率和繁殖代数。通过这些参数随机产生一个种群的列表pop作为首代种群,里面的每一条染色体是一个字典,该字典有两个内容,分别是包含基因的Gene类和适应度函数值fitness

evaluate()方法

在初始化方法中,要用到适应度函数计算函数值,它的定义如下:

selectBest()方法

在初始化方法中,需要先将首代中最好的个体保留作为记录,它的定义如下:

对整个种群按照适应度函数从大到小排序,返回最大值的个体。

selection()方法

按照概率从上一代种群中选择个体,直至形成新的一代。我们需要适应度函数值大的个体被选择的概率大,可以使用轮盘赌选择法。该方法的步骤如下:

《Python手把手构建遗传算法(GA)实现最优化搜索》

它的代码实现如下:

在这里我们对种群按照概率进行选择后代,适应度函数大的个体大概率被选择到下一代,最后我们对重新生成的新一代种群按照适应度从小到大进行排序,方便接下来的交叉操作。

crossoperate()方法

交叉是指将两个个体的基因片段在某一点或者某几点进行互换,常用的有单点交叉和双点交叉。它的过程如下:

《Python手把手构建遗传算法(GA)实现最优化搜索》

从图中可以看出,无论是单点交叉还是双点交叉都很大的改变了原来的基因序列,它是实现优化的重要手段。具体的实现代码如下:

上面的代码实现了双点交叉,其中为了防止只有一个基因的存在,我们使用一个判断语句。

mutation()方法

变异在遗传过程中属于小概率事件,但是在种群数量较小的情况下,只通过交叉操作并不能产生优秀的后代,此时变异就显得非常重要了。通过适当的变异甚至能够产生更优秀的后代。变异的方式有很多种,常规的变异有基本位变异和逆转变异。它的过程如下:

《Python手把手构建遗传算法(GA)实现最优化搜索》

在这里我们实现单点变异:

同样为了防止只有一个基因的情况,使用判断语句。

GA_main()方法

遗传算法所有的轮子都写好后,我们接下来将它们整合到流程中。代码实现如下:

在这个流程当中需要注意的是,经过selection()方法产生的新种群selectpop是按照适应度从小到大排列的,通过列表的pop()方法能够优先选择适应度大的两个个体进行后续的交叉操作;因为是pop()两次,所以种群的大小必须是偶数个。

完整代码如下:

if __name__ == "__main__":语句后面,我们设定所有的参数。在这里交叉概率CXPB为0.8,变异概率MUTPB为0.1,总共跑NGEN=1000代,每代的种群大小为100。

得到结果如下:

《Python手把手构建遗传算法(GA)实现最优化搜索》

事实上按照目前的参数,在第342代的时候已经找到最优解。如果使用枚举法需要30*30*30*30=810000次才能寻找到最优解,通过遗传算法只计算了34200次,大大缩短最优解的搜索空间。

总结

在本文中通过遗传算法实现求解一个简单的函数,当然该函数最优解的寻找是比较快的,代码实现其实并不需要这么复杂。本文的代码能够快速运用到其他问题中,可供借鉴和参考。

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

8 + 16 =