遗传算法.ppt

遗传算法
遗传算法(ic Algorithm,GA)是一种模拟达尔文自然选择和遗传机制,在计算机上进行自适应概率性全局寻优搜索算法,,是近些年来发展起来的一种新型的优化算法。
遗传算法基本结构
(“染色体”),每一串代表问题的一个可行解。
***op0,该种群就是问题可行解的一个集合。
“环境”当中,并给出种群每一个体串码适应问题环境的适应值(评价)。
***op0(或popk)执行选择操作(selection),随机选取父本种群Fk,优良的个体被大量复制,而劣质的个体复制的少,甚至被淘汰掉。
(crossover)产生种群Ck。
(mutation)操作得新的种***op ( k+1)。
这样反复执行3步到6步,使码串群体一代一代不断进化,最后搜索到最适应问题环境的个体,求得问题最优解。
一个基本的遗传算法可以用下面的伪码描述
Procedure ic Algorithm
Begin
K=0;{k为群体代数}
初始化P(k);{p(k)为第k代群体}
计算P(k)的适应值;
While{不满足停止准则}do
Begin
K=k+1
从P(k-1)中选择p(k);{复制算子作用}
重组P(k);{杂交和变异算子作用}
计算P(k)的适应值
End
End

可以看到,遗传算法是个迭代过程,在迭代中,算法保持一个定常规模的群体,每一迭代步(称为步)包括计算出当前群体中个体的适应值,以及基于适应值形成一个新的解群体。
遗传算法的常见编码方法
二进制编码:它是将十进制数或实际应用中所遇到的问题的解转换成二进制的表现形式,即由0或1组成的字符串。其长度要由具体问题的要求来定,例如解的精度要求等。但这样就会有一定的量化误差产生,则只适用于一般的遗传算法。
遗传算法主要包括选择、交叉和变异三个基本操作:
(1)选择(又称繁殖):选择操作是根据其编码串的目标函数的适应度值大小来进行的,是一种从旧种群中选择生命力强的个体产生新种群的过程。一般说来,一个码串的适应值越高,则它在种群中生存繁殖的几率也越大,即适合于生存环境的优良个体具有更多繁殖后代的机会,从而使优良特性得以代代遗传。
按照概率规则
来选择个体。

(2)交叉:交叉是两个码串重组的操作,是遗传算法区别于其它传统优化方法的重要标志。交叉分两步进行,首先随机地从操作种群中取出要匹配的两个码串;然后以一定的交叉方式互换这两个码串中的信息,从而产生一对新的码串。
交叉:
单点交叉:前