编码与解码
实现遗传算法的第一步就是明确对求解问题的编码和解码方式。
对于函数优化问题,一般有两种编码方式,各具优缺点
实数编码:直接用实数表示基因,容易理解且不需要解码过程,但容易过早收敛,从而陷入局部最优二进制编码:稳定性高,种群多样性大,但需要的存储空间大,需要解码且难以理解个体与种群
『染色体』表达了某种特征,这种特征的载体,称为『个体』。
对于本次实验所要解决的一元函数最大值求解问题,个体可以用上一节构造的染色体表示,一个个体里有一条染色体。
许多这样的个体组成了一个种群,其含义是一个一维点集(x轴上[0,9]的线段)。
适应度函数
遗传算法中,一个个体(解)的好坏用适应度函数值来评价,在本问题中,f(x)就是适应度函数。
适应度函数值越大,解的质量越高。
适应度函数是遗传算法进化的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。
遗传算子
我们希望有这样一个种群,它所包含的个体所对应的函数值都很接近于f(x)在[0,9]上的最大值,但是这个种群一开始可能不那么优秀,因为个体的染色体串是随机生成的。
如何让种群变得优秀呢?
不断的进化。
每一次进化都尽可能保留种群中的优秀个体,淘汰掉不理想的个体,并且在优秀个体之间进行染色体交叉,有些个体还可能出现变异。
种群的每一次进化,都会产生一个最优个体。种群所有世代的最优个体,可能就是函数f(x)最大值对应的定义域中的点。
如果种群无休止地进化,那总能找到最好的解。但实际上,我们的时间有限,通常在得到一个看上去不错的解时,便终止了进化。
对于给定的种群,如何赋予它进化的能力呢?
首先是选择(selection)
选择操作是从前代种群中选择***多对***较优个体,一对较优个体称之为一对父母,让父母们将它们的基因传递到下一代,直到下一代个体数量达到种群数量上限在选择操作前,将种群中个体按照适应度从小到大进行排列采用轮盘赌选择方法(当然还有很多别的选择方法),各个个体被选中的概率与其适应度函数值大小成正比轮盘赌选择方法具有随机性,在选择的过程中可能会丢掉较好的个体,所以可以使用精英机制,将前代最优个体直接选择其次是交叉(crossover)
两个待交叉的不同的染色体(父母)根据交叉概率(cross_rate)按某种方式交换其部分基因采用单点交叉法,也可以使用其他交叉方法链接:https://www.zhihu.com/question/23293449/answer/120220974