文档介绍：基本遗传算法
Holland创建的遗传算法是一种概率搜索算法,它利用某种编码技术作用于称为染色体的数串,其基本思想是模拟由这些串组成的个体进化过程。该算法通过有组织的、然而是随机的信息交换,重新组合那些适应性好的串。在每一代中,利用上一代串结构中适应性好的位和段来生成一个新的串的群体;作为额外增添,偶尔也要在串结构中尝试用新的位和段来替代原来的部分。
遗传算法是一类随机优化算法,它可以有效地利用已有的信息处理来搜索那些有希望改善解质量的串。类似于自然进化,遗传算法通过作用于染色体上的基因,寻找好的染色体来求解问题。与自然界相似,遗传算法对待求解问题本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,并基于适应度值来改变染色体,使适应性好的染色体比适应性差的染色体有更多的繁殖机会。
遗传算法的运行过程
遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象,从任一初始种群(Population)出发,通过随机选择、交叉和变异操作,产生一群更适应环境的个体,使群体进化到搜索空间中越来越好的区域,这样一代一代地不断繁衍进化,最后收敛到一群最适应环境的个体(Individual),求得问题的最优解。
完整的遗传算法运算流程
完整的遗传算法运算流程可以用图1来描述。
由图1可以看出,使用上述三种遗传算子(选择算子、交叉算子和变异算子)的遗传算法的主要运算过程如下:
编码:解空间中的解数据x,作为遗传算法的表现形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合就构成了不同的点。
初始群体的生成:随机产生N个初始串结构数据,每个串结构数据称为一个个体,N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t←0;设置最大进化代数T;随机生成M个个体作为初始群体P(0)。
适应度值评价检测:适应度函数表明个体或解的优劣性。对于不同的问题,适应度函数的定义方式不同。根据具体问题,计算群体P(t)中各个个体的适应度。
选择:将选择算子作用于群体。
交叉:将交叉算子作用于群体。
变异:将变异算子作用于群体。
群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)。
终止条件判断:若t≤T,则t←t+1,转到步骤(2);若t>T,则以进化过程中所得到的具有最大适应度的个体作为最优解输出,终止运算。
从遗传算法运算流程可以看出,进化操作过程简单,容易理解,它给其他各种遗传算法提供了一个基本框架。
实际问题参数集
编码成位串
种群1
计算适应值
选择与遗传
统计结果
种群2
经过优化的一个或多个
参数集(由解码得到)
改善或解决实际问题
位串解释得到参数
计算目标函数
函数值向适值映射
适值调整
三种基本遗传算子:
选择算子
交叉算子
变异算子
随机算子
种群1←种群2
图1 遗传算法运算流程
一个简单的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成。t代种群用变量P(t)表示,初始种群P(0)是随机设计的,简单遗传算法的伪代码描述如下:
produre GA
begin
t=0;
initialize P(t);