遗传算法即模拟自然界中种群优胜劣汰的过程,通过种群不断迭代之后找到最优解。其实现步骤可分为:编码、解码、个体适应度评估、复制、交叉、变异。 编码: 常见的编码方式为二进制编码,其目的是便于进行后续的复制、交叉、变异,也符合了计算机处理信息的原理。设某一参数的取值范围为(L,U),使用了k位二进制来编码此数,则它有2^k种编码方式,该参数的对应关系如下所示:
000……000=0---------L 000……001=1---------L+α 000……010=2---------L+2α ………………………… 111……111=2^k-1-----U容易看出α=(U-L)/(2^k-1)。
解码: 即将编码的二进制数还原为十进制数。
个体适应度评估: 把x的值带入到目标函数得到个体适应度值,把所有个体的个体适应度求和得到适应度总和,将个体适应度与适应度总和相比得到个体被复制的概率,最后计算出个体被复制累计的概率。
复制: 采用轮盘赌法,转动轮盘n次(n为种群中个体的个数),每次选中一个个体保留到下一代。选择的依据是产生随机数,若数值落入t4~t5的复制累计概率,则选择t5作为下一代的个体。
交叉: 人为的设置交叉概率,概率乘以种群个体数量得到交叉的染色体的个数(若得到的是小数,则取小于该数的最大整数)。把每一个种群个体都随机产生一个随机数,小于交叉概率的染色体进行交叉。用随机数产生0~k(二进制编码位数)的随机数,作为染色体进行交叉的位数。 变异 人为的设置突变概率,种群个体数乘以k(得到种群个体所有基因的总数)乘以突变概率得到需要突变的染色体数量。种群内每个基因都随机产生0~1的随机数,把小于突变概率的基因选出进行突变。这里需要注意一个问题,如果第L个数产生的随机数小于突变概率,用L/k的结果表示突变染色体的位置,余数表示突变基因的位置。
至此,已经完成了种群的一次迭代过程。依次不断迭代,直到结果达到设定条件或者迭代次数达到设置得到最大迭代次数。
遗传算法使用总结: 大范围广度搜索-前期设置种群数量(随机样本) 小范围精度搜索-交叉、变异 有跳出局部最优的能力(突变)