基本遗传算法

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

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

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

3、．完整的遗传算法运算流程完整的遗传算法运算流程可以用图1来描述。由图1可以看出，使用上述三种遗传算子（选择算子、交叉算子和变异算子）的遗传算法的主要运算过程如下：（1）编码：解空间中的解数据x，作为遗传算法的表现形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。（2）初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。

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

5、体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。实际问题参数集编码成位串种群1计算适应值选择与遗传统计结果种群2经过优化的一个或多个参数集（由解码得到）改善或解决实际问题1．位串解释得到参数2．计算目标函数3．函数值向适值映射4．适值调整三种基本遗传算子：选择算子交叉算子变异算子随机算子种群1←种群2图1遗传算法运算流程一个简单的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成。t代种群用变量P(t)表示

6、，初始种群P(0)是随机设计的，简单遗传算法的伪代码描述如下：produreGAbegint=0;initializeP(t);evaluateP(t);whilenotfinisheddobegint=t+1;selectP(t)fromP(t-1);reproducepairsinP(t);evaluateP(t);endend一．遗传算法的基本操作遗传算法有三个基本操作：选择(Selection)、交叉(Crossover)和变异(Mutation)。（1）选择。选择的目的是为了从当前群体中选出优良

7、的个体，使它们有机会作为父代为下一代繁殖子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。遗传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。这样就体现了达尔文的适者生存原则。（2）交叉。交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体内的各个个体随机搭配成对，对每一个个体，以某个概率（称为交叉概率，CrossoverRate）交换它们之间的部分染色

8、体。交叉体现了信息交换的思想。（3）变异。变异操作首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机改变串结构数据中某个串的值，即对群体中的每一个个体，以某一概率（称为变异概率，MutationRate）改变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一样遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会。三．基本遗传算法的数学模型基本遗传算法可表示为SGA=(C,E,P0,M,,,,T)式中：C