遗传算法原理以及matlab实现
1.概述
遗传算法,模拟达尔文进化论的自然选择和遗传学机理的生物进化过程的计算模型,一种选择不断选择优良个体的算法。谈到遗传,想想自然界动物遗传是怎么来的,自然主要过程包括染色体的选择,交叉,变异,这些操作后,保证了以后的个体基本上是最优的,那么以后再继续这样下去就可以一直最优了。
解决的问题:
主要还是解决优化类问题,尤其是那种不能直接解出来的很复杂的问题
2.技术
2.1编码
(1)二进制编码
二进制编码的字符串长度与问题所求解的精度有关。需要保证所求解空间内的每一个个体都可以被编码。
优点:编、解码操作简单,遗传、交叉便于实现
缺点:长度大
(2)其他编码方法
格雷码、浮点数编码、符号编码、多参数编码等
2.2适应度函数
适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。
2.3选择算子
通过选择算子模拟“优胜劣汰”,适应度高的个体被遗传到下一代的概率较大,适应度低的算子被遗传到下一代的概率较小。
常用的选择算法:
轮盘赌选择法,即令
表示群体的适应度函数值的总和,fi表示群体中第i个染色体的适应度值,则它产生后代的能力刚好为其适应度值所占的份额
2.4交叉算子
交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体;
交叉运算是遗传算法区别于其他进化算法的重要特征,是产生新个体的主要方法。
在交叉之前需要将群体中的个体进行配对,一般采取随机配对原则。
常用的交叉方式:
- 单点交叉
- 双点交叉(多点交叉,交叉点数越多,个体的结构被破坏的可能性越大,一般不采用多点交叉的方式)
- 均匀交叉
- 算术交叉
2.5变异算子
遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新的个体。
就遗传算法运算过程中产生新个体的能力方面来说,交叉运算是产生新个体的主要方法,它决定了遗传算法的全局搜索能力;而变异运算只是产生新个体的辅助方法,但也是必不可少的一个运算步骤,它决定了遗传算法的局部搜索能力。交叉算子与变异算子的共同配合完成了其对搜索空间的全局搜索和局部搜索,从而使遗传算法能以良好的搜索性能完成最优化问题的寻优过程。
1)二进制编码
基因突变过程:基因突变是染色体的某一个位点上基因的改变。基因突变使一个基因变成它的等位基因,并且通常会引起一定的表现型变化。正如上面所说,二进制编码的遗传操作过程和生物学中的过程非常相类似,基因串上的“ 0”或“ 1”有一定几率变成与之相反的“ 1”或“ 0”。例如下面这串二进制编码:
101101001011001
经过基因突变后,可能变成以下这串新的编码:
001101011011001
(2)浮点型编码
浮点型编码的基因突变过程一般是对原来的浮点数增加或者减少一个小随机数。比如原来的浮点数串如下:
1.2,3.4,5.1, 6.0, 4.5
变异后,可能得到如下的浮点数串:
1.3,3.1,4.9, 6.3, 4.4
2.6运行参数
- 编码长度。编码长度取决于问题解的精度,精度越高,编码越长;
- 种群规模。规模小,收敛快但降低了种群的多样性,N=20-200;
- 交叉概率。较大的交叉概率容易破坏种群中已形成的优良结构,使搜索具有太大随机性;较小的交叉概率发现新个体的速度太慢,一般取值为P_c=0.4-0.99
- 变异概率。变异概率太小,则变异操作产生新个体的能力和抑制早熟现象的能力会较差;变异概率过高随机性过大,一般建议取值范围为0.005~0.01
- 终止进化代数。算法运行结束的条件之一,一般取100~1000
3.基本流程
- 通过随机方式产生若干由确定长度(长度与待求解问题的精度有关)编码的初始群体;
- 通过适应度函数对每个个体进行评价,选择适应度值高的个体参与遗传操作,适应度低的个体被淘汰;
- 经遗传操作(复制、交叉、变异)的个体集合形成新一代种群,直到满足停止准则(进化代数GEN>=?);
- 将后代中变现最好的个体作为遗传算法的执行结果。
其中,GEN是当前代数;M是种群规模,i代表种群数量。