遗传算法及应用

《遗传算法及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法（GeneticAlgorithm）NaturalComputing•1、算法起源•2、基本术语和遗传算子•3、模式定理•4、遗传算法的应用算法起源•遗传算法（简称GA）的基本思想起源于生物体的遗传进化。生物的进化是发生在作为生物体结构编码的染色体上，染色体主要是由DNA和蛋白质组成，其中DNA又是最主要的遗传物质，它储存着遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成而控制生物的性状。•生物的遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特性，使生物个体产生新的性状，以至于形成了新的物种，推动了生物

2、的进化和发展。•遗传算法正是模拟这一过程，通过向自然学习来求解问题。算法起源•1975年，美国Michigan大学的Holland教授出版了系统论述遗传算法的第一本专著，标志着遗传算法的诞生。•80年代，遗传算法得到了广泛应用与研究。•1989年，D.J.Goldberg出版了他的著作，对遗传算法作了系统的阐述，确立了现代遗传算法的基础。•基本遗传算法是一种概率搜索算法，利用编码技术作用于称为染色体（chromosome）的二进制数串，模拟由这些串组成的群体的进化过程。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求

3、解问题。•遗传算法通过有组织的然而是随机的信息交换来重新结合那些适应性好的串。•虽是一类随机算法，但又不是简单的随机走动，它可以有效利用已有的信息来搜寻那些有希望改善解质量的串。•与自然界相似，遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。基本术语和遗传算子•定义1将待解决问题的解变量用某种编码技术编制成特定形式的数字串，称这个数字串为染色体（chromosome）；数字串的每位数字码称为基因（gene）（基本GA中，采用二

4、进制编码串），串的长度即为染色体的长度•定义2由一定数目的同等长度染色体组成的集合称为一个种群（population）；相应的染色体称为种群的一个个体（individual）•定义3根据拟定的函数对个体性质评价的一种度量，称为个体的适应值或适应度（fitness）基本术语和遗传算子•定义4对两个个体进行部分基因互换，产生两个新个体的操作，称为交叉或杂交运算（crossover）•定义5对个体的某些基因进行改变，产生新个体的操作，称作变异运算（mutation）•定义6从当前种群中选出优良的个体，使之有机会作为父代繁殖下一代的操作，称作选

5、择运算（selection），或复制运算（reproduction）基本遗传算子：以二进制编码为例•单点交叉:(随机投点）X=100110100;X’=010110100;Y=010111011；Y’=100111011；•两点交叉：X=100110100;X’=010110011;Y=010111011；Y’=100111100；或者X”=100111100;Y”=010110011；基本遗传算子：以二进制编码为例•单点变异:(随机投点）X=100110100;X’=101110100;Y=010111011；Y’=110111011

6、；•多点变异：X=100110100;X’=110100101;Y=010111011；Y’=100111111；基本遗传算子：以二进制编码为例•个体选择复制:(赌轮原则）•设种群规模为4个体fitness概率选择选择X1X111/12X2X1X3X2X221/6X3X3X331/4X4X3X4X461/2X4X4RouletteWheelSelection标准遗传算法（SGA）考虑全局优化问题（P）max{f(x)：x∈DRn→R1}遗传算法基于以下两条基本策略求解问题（P）：（a）对于给定的目标函数f，它使用f的任一适应值函数（换言

7、之，一个值域非负、与f有相同极点的函数）；（b）它不直接作用于实向量x，而是作用于x的某种编码（最常见的为定长二进制数串编码）。所以，对于取定f的任一适应值函数F和固定长度为L的二进制数串编码，遗传算法实质上是通过求解组合优化问题（P’）max{F(x)：x∈S}来求解问题（P）的，这里S={0，1}L为D的编码空间（即D中所有实变量的长度为L的二进制数串编码全体）。Step1初始化：1.1指定种群规模N，杂交概率P，变异概率P及终止进化准则；cm1.2随机生成初始种群X(0)=(X(0)，X(0)，…，X(0))∈SN，12N置k=0

8、。Step2种群进化：2.1（选择）依据X(k)的适应值，随机、独立、重复地从X(k)中选i取N个个体为母体；2.2（交叉）依概率P独立地对所选N个母体执行杂交，以产生新c的N个中间个体；2.3（变异）依概