一文让零基础的你轻松理解遗传算法

佐佑思维
关注

?????????????组成:

? 编码 -> 创造染色体

? 个体 -> 种群

? 适应度函数

? 遗传算子

      ? 选择

      ? 交叉

      ? 变异

? 运行参数

      ? 是否选择精英操作

      ? 种群大小

      ? 染色体长度

      ? 最大迭代次数

      ? 交叉概率

      ? 变异概率

编码与解码:

实现遗传算法的第一步就是明确对求解问题的编码和解码方式。
对于函数优化问题,一般有两种编码方式,各具优缺点。

实数编码:直接用实数表示基因,容易理解且不需要解码过程,但容易过早收敛,从而陷入局部最优;

二进制编码:稳定性高,种群多样性大,但需要的存储空间大,需要解码且难以理解。

对于求解函数最大值问题,我一般选择二进制编码:

以目标函数 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 为例。

假如设定求解的精度为小数点后4位,可以将x的解空间划分为 (9-0)×(1e+4)=90000个等分。

2^16<90000<2^17,需要17位二进制数来表示这些解。换句话说,一个解的编码就是一个17位的二进制串。

一开始,这些二进制串是随机生成的。

一个这样的二进制串代表一条染色体串,这里染色体串的长度为17。

对于任何一条这样的染色体chromosome,如何将它复原(解码)到[0,9]这个区间中的数值呢?

对于本问题,我们可以采用以下公式来解码:

x = 0 + decimal(chromosome)×(9-0)/(2^17-1)decimal( ): 将二进制数转化为十进制数

一般化解码公式:

f(x), x∈[lower_bound, upper_bound]x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)f(x), x∈[lower_bound, upper_bound]x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)lower_bound: 函数定义域的下限
upper_bound: 函数定义域的上限
chromosome_size: 染色体的长度

通过上述公式,我们就可以成功地将二进制染色体串解码成[0,9]区间中的十进制实数解。

个体与种群:

『染色体』表达了某种特征,这种特征的载体,称为『个体』。

对于本次实验所要解决的一元函数最大值求解问题,个体可以用上一节构造的染色体表示,一个个体里有一条染色体。

许多这样的个体组成了一个种群,其含义是一个一维点集(x轴上[0,9]的线段)。

适应度函数:

遗传算法中,一个个体(解)的好坏用适应度函数值来评价,在本问题中,f(x)就是适应度函数。

适应度函数值越大,解的质量越高。

适应度函数是遗传算法进化的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。

遗传算子:

我们希望有这样一个种群,它所包含的个体所对应的函数值都很接近于f(x)在[0,9]上的最大值,但是这个种群一开始可能不那么优秀,因为个体的染色体串是随机生成的。

如何让种群变得优秀呢?

不断地进化

每一次进化都尽可能保留种群中的优秀个体,淘汰掉不理想的个体,并且在优秀个体之间进行染色体交叉,有些个体还可能出现变异。

种群的每一次进化,都会产生一个最优个体。种群所有世代的最优个体,可能就是函数f(x)最大值对应的定义域中的点。

如果种群无休止地进化,那总能找到最好的解。但实际上,我们的时间有限,通常在得到一个看上去不错的解时,便终止了进化。

对于给定的种群,如何赋予它进化的能力呢?

首先是选择(selection)

? 选择操作是从前代种群中选择***多对***较优个体,一对较优个体称之为一对父母,让父母们将它们的基因传递到下一代,直到下一代个体数量达到种群数量上限

? 在选择操作前,将种群中个体按照适应度从小到大进行排列

? 采用轮盘赌选择方法(当然还有很多别的选择方法,比如竞标赛法),各个个体被选中的概率与其适应度函数值大小成正比

? 轮盘赌选择方法具有随机性,在选择的过程中可能会丢掉较好的个体,所以可以使用精英机制,将前代最优个体直接选择

其次是交叉(crossover)

? 两个待交叉的不同的染色体(父母)根据交叉概率(cross_rate)按某种方式交换其部分基因
? 采用单点交叉法,也可以使用其他交叉方法

最后是变异(mutation)

? 染色体按照变异概率(mutate_rate)进行染色体的变异

? 采用单点变异法,也可以使用其他变异方法

一般来说,交叉概率(cross_rate)比较大,变异概率(mutate_rate)极低。像求解函数最大值这类问题,我设置的交叉概率(cross_rate)是0.6,变异概率(mutate_rate)是0.01。

因为遗传算法相信2条优秀的父母染色体交叉更有可能产生优秀的后代,而变异的话产生优秀后代的可能性极低,不过也有存在可能一下就变异出非常优秀的后代。这也是符合自然界生物进化的特征的。

图片标题


03

算例代码

上述算例是我学习遗传算法时的算例,比较容易理解,如果还有不懂得可以后台联系我们,这里附上算例的代码(matlab版本):

链接:https://pan.baidu.com/s/1rvhtA4kaxQuJTmndiVS71Q提取码:bfrr


声明: 本文由入驻OFweek维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。
侵权投诉

下载OFweek,一手掌握高科技全行业资讯

还不是OFweek会员,马上注册
打开app,查看更多精彩资讯 >
  • 长按识别二维码
  • 进入OFweek阅读全文
长按图片进行保存