遗传算法报告ppt课件.ppt

遗传算法及
其MATLAB实现
遗传的生物学基础
遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。 Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承,但后代又会产生一些异于父代的新变化。在环境变化时,只有那些能适应环境的个体特征方能保留下来。 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中,并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质;所以,每个基因产生的个体对环境具有某种适应性。因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来。
遗传算法的概念
遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法。
简单遗传算法有编解码、个体适应度评估和遗传算法三大模块组成,而遗传运算又包括染色体复制、交叉变异等。
遗传算法的实现步骤







遗传算法基本操作流程图
开始
产生初始种群(编码、解码)
计算个体适应度值
复制
交配
变异
满足终止条件?
输出最优解
结束
Y
N
。二进制编码符合计算机处理信息的原理,能对染色体进行遗传,编译和突变等操作。
设某一参数的取值范围为(L,U),长度为k,则它共有
种不同的编码。
00000000000000=0→L
00000000000001=1→ L+δ
00000000000010=2→L+2δ
00000000000011=3→L+3δ
……
111**********= -1→U
复制运算把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。
若设种群众个体总数为N,个体i适应度为fi:
•先计算出群体中所有个体的适应度的总和∑fk ( k=,…,N ); •其次计算出每个个体的相对适应度的大小 fI/ ∑fK,它即为每个个体被遗传到下一代群体中的概率。 •每个概率值组成一个区域,全部概率值之和为1; •最后再产生一个0到1之间的随机数,依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。

对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交配概率P。在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交配时,可实行单点交配或多点交配。

例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交配操作,则有 S1=010101 S2=100111 一般而言,交配概率P。—。