生物第七章 7.4遗传算法

《生物第七章 7.4遗传算法》由会员分享，可在线阅读，更多相关《生物第七章 7.4遗传算法（15页珍藏版）》请在金锄头文库上搜索。

1、7.4 遗传算法,达尔文进化论：“物竞天择、适者生存” 70年代由美国的密执根大学的Holland教授首先提出 近年来，遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。,生物进化与遗传算法,生物进化与遗传算法之间的对应关系,遗传算法的三个主要操作,选择 交配 变异,“轮盘赌”法 ：设群体的规模为N，F(xi)(i=1, ., N)是其中N个染色体的适应值。则第i个染色体被选中的概率由下式给出：,选择,模拟“轮盘赌” 算法,（1）r=random(0, 1)，s=0，i=0； （2）如果sr，则转（4）； （3）s=s+p(xi)，i=i+1, 转（2） （4）xi即为被选中的染色

2、体，输出i （5）结束。,“确定性”法 对于规模为N的群体，一个选择概率为p(xi)的染色体xi被选择次数的期望值e(xi)： 对于群体中的每一个xi，首先选择 次。这样共得到 个染色体。然后按照 从大到小对染色体排序，依次取出 个染色体，这样就得到了N个染色体。,交配,交配发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体。当染色体采用二进制形式编码时，交配过程是以这样一种形式进行的：,a1 a2 . ai ai+1 . an b1 b2 . bi bi+1 . bn,a1 a2 . ai bi+1 . bn b1 b2 . bi ai+

3、1 . an,交配前,交配后,交配位置,变异,变异发生在染色体的某一个基因上，当以二进制编码时，变异的基因由0变成1，或者由1变成0。如对于染色体x=11001，如果变异位发生在第三位，则变异后的染色体变成了y=11101。,遗传算法 （1）给定群体规模N，交配概率pc和变异概率pm，t0； （2）随机生成N个染色体作为初始群体； （3）对于群体中的每一个染色体xi分别计算其适应值F(xi)； （4）如果算法满足停止准则，则转（10）； （5）对群体中的每一个染色体xi计算概率； （6）依据计算得到的概率值，从群体中随机的选取N个染色体，得到种群；,（7）依据交配概率pc从种群中选择染色体进行

4、交配，其子代进入新的群体，种群中未进行交配的染色体，直接复制到新群体中； （8）依据变异概率pm从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体； （9）用新群体代替旧群体，t=t+1，转（3）； （10）进化过程中适应值最大的染色体，经解码后作为最优解输出； （11）结束。,遗传算法的特点,（1）遗传算法是一个随机搜索算法，适用于数值求解具有多参数、多变量、多目标等复杂的最优化问题。 （2）遗传算法对待求解问题的指标函数没有什么特殊的要求，比如不要求诸如连续性、导数存在、单峰值假设等。甚至于不需要显式的写出指标函数。 （3）在经过编码以后，遗传算法几乎不需要任何与问题有关的知识，唯一需要的信息是适应值的计算。也不需要使用者对问题有很深入的了解和求解技巧，通过选择、交配和变异等简单的操作求解复杂的问题，是一个比较通用的优化算法。 （4）遗传算法具有天然的并行性，适用于并行求解。,遗传算法的实现问题,编码 评价 适应函数 交配规则 停止条件,