基本遗传算法及改进.doc

《基本遗传算法及改进.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二章基本遗传算法及改进Holland创建的遗传算法是一种概率搜索算法，它利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些串组成的个体进化过程。该算法通过有组织地、然而是随机地进行信息交换，重新组合那些适应性好的串。在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。遗传算法是一类随机优化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解

2、问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来改变染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。2.1遗传算法的运行过程遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群(population)出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体(Individual)，求得问题的最优解。2.1.1完整的遗传算法运算流程交叉遗传算法

3、的一般步骤如图2.1所示。解110010101010110111010011001010101011000111001010101011011101110010111010110110010011001010译码适值计算1100101010101101110100110010101010110001解转轮编码选择评估变异0011011010图2.1遗传算法的一般步骤完整的遗传算法运算流程可以用图2.2来描述。编码成位串实际问题参数集计算适应值种群1统计结果选择与遗传经过优化的一个或多个参数集（由解码得到）多个参数集合种群2改善或解决实际问题群2随

4、机算子1）位串解释得到参数2）计算目标函数3）函数值向适值映射4）适值调整三种基本遗传算子：选择算子交叉算子变异算子种群1种群2图2.2遗传算法运算流程图1.3遗传算法运算流程由图2.2可以看出，使用上述三种遗传算子(选择算子、交叉算子、变异算子)的遗传算法的主要运算过程如下：(1)编码：解空间中的解数据，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。(2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一

5、个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t←0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。(3)适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体P(t)中各个个体的适应度。(4)选择：将选择算子作用于群体。(5)交叉：将交叉算子作用于群体。(6)变异：将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)。(7)终止条件判断：若t≤T，则t←t+1，转到步骤（2）；若tT，则以进化过

6、程中所得到的具有最大适应度的个体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。一个简单的遗传算法被Goldberg用来进行轮廓描述，并用来举例说明遗传算法的基本组成。t代种群用变量P(t)表示，初始种群是随机设计的P(0)。简单遗传算法的伪代码描述如下：2.1.2遗传算法的三个基本操作procedureGAbegint=0;initializeP(t);evaluateP(t);whilenotfinisheddobegint=t+1;selectP(t)fromP(t-

7、1);reproducepairsinP(t);evaluateP(t);endend.遗传算法有三个基本操作：选择(Selection)、交叉(Crossover)和变异(Mutation)。(1)选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。遗传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。这样就体现了达尔文的适者生存原则。(2)交叉。交叉操作是遗传算法中

8、最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体内的各个个体随机搭配成对，对每一个个体，以某个概率(