ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 遗传算法的概念、算法描述及理论基础

遗传算法的概念、算法描述及理论基础

原创 Linux操作系统 作者:gvora 时间:2009-09-26 21:28:33 0 删除 编辑

1 遗传算法概述

1.1 遗传算法的基本概念

遗传算法是模拟生物界的遗传和进化过程而建立起来的一种高度并行的全局性概率搜索算法,体现着“优胜劣汰、适者生存”的竞争机制。由于遗传算法是由进化论和遗传学机理产生的直接搜索优化方法,所以在这个算法中要用到各种进化和遗传学的概念。这些概念介绍如下:

1.编码(Coding):DNA中遗传信息在一个长链上按一定的模式排列,这一操作就是遗传编码。遗传编码可以看作从表现型到遗传型的映射。

2.染色体(Chromosome):遗传物质的主要载体,由多个遗传因子——基因组成。

3.个体(Individual):指染色体带有特征的实体,遗传算法所处理的基本结构。

    4.种群(Population):每代所产生的染色体总数称为种群,一个种群包含了该问题在这一代的一些解的集合。

    5.种群大小(Population Size):在种群中个体的数量称为种群的大小。

    6.基因(Gene):基因是染色体中的元素,基因用于表示个体的特征。

    7.基因位置(Gene Position):一个基因在染色体中的位置称为基因位置。

    8.基因特征值(Gene Feature):在用染色体表示整数时,基因的特征值与二进制数的权一致。

    9.适应度(Fitness):表示某一个体对于环境的适应程度,或者在环境压力下的生存能力。

1.2 遗传算法的基本思想

遗传算法是一种宏观意义下的仿生算法,它的机制是模仿一切生命与智慧的产生与进化过程。通过模拟达尔文的“优胜劣汰,适者生存”原理,激励好的结构,通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构,同时寻找更好的结构。因此,遗传算法具有如下显著特点:

1.遗传算法的处理对象不是参数本身,而是对参数集进行编码的个体。这种对决策变量的编码处理方法使得遗传算法具有良好的可操作性与简单性。

2.遗传算法直接以目标函数值作为搜索信息,仅使用由目标函数值得来的适应度函数值,就可以确定下一步的搜索方向和搜索范围,不要求目标函数值连续可微。

3.遗传算法采用自适应概率搜索技术,增加了其搜索过程的灵活性。实践证明,随着进化过程的进行,新的群体中总会产生更多优良的个体。

4.遗传算法采用同时处理群体中多个个体的方法,同时对搜索空间中的多个解进行评价。这一点使遗传算法具有较好的全局搜索性能,减少了陷于局部最优解的风险。

5.在遗传算法中,个体的重组技术使用交叉操作算子,这种交叉操作算子是遗传算法所强调的关键技术,它是遗传算法中产生新个体的主要方法,也是遗传算法区别于其他算法的一个主要特点。

1.3 遗传算法的应用

遗传算法提供了一种求解复杂系统问题的通用框架,它不依赖于问题的具体领域,对问题的求解有很强的鲁棒性,所以遗传算法在函数和组合优化、生产调度、自动控制、智能控制、机器学习、数据挖掘、图像处理以及人工生命等领域得到了成功而广泛的应用,成为21世纪的关键技术之一。

从表2.1可见,遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新、更工程化的应用方面。

2.1遗传算法的主要应用领域

应用领域

例子

控制

瓦斯管道控制,防避导弹控制,机器人控制

规划

生产规划,并行机任务分配

设计

VLSI布局,通信网络设计,喷气发动机设计

组合优化

TSP问题,背包问题,图划分问题

图像处理

模式识别,特征提取,图像恢复

信号处理

滤波器设计,目标识别,运动目标分割

机器人

路径规划

人工生命

生命的遗传进化

2 基本遗传算法

基本遗传算法(Simple Genetic Algorithm,简称SGA)是一种群体型操作,该操作以群体中的所有个体为对象,只使用基本遗传算子:选择算子、交叉算子和变异算子,其遗传进化操作过程简单,容易理解,是其它一些遗传算法的基础,它不仅给各种遗传算法提供了一个基本框架,同时也具有一定的应用价值。

2.1 基本遗传算法描述

基本遗传算法可表示为:

式中:  ———个体的编码方法

        ———个体适应度评价函数

        ———初始种群

        ———种群大小

        ———选择算子

        ———交叉算子

        ———变异算子

        ———遗传运算终止条件

下面给出基本遗传算法的伪代码描述:

Procedure SGA

begin

     initialize P(0)

     t=0

     while (t T) do

          for i=1 to M do

                Evaluate fitness of P(t)

          end for

          for i=1 to M do

                Select operation to P(t)

          end for

          for i=1 to M /2 do

                Crossover operation to P(t)

          end for

          for i=1 to M do

                Mutation operation to P(t)

          end for

          for i=1 to M do

                P(t+1)=P(t)

end for

t=t+l;

end while

end

2.2 基本遗传算法运算流程

基本遗传算法的运算流程如图2.1所示,从图2.1可以看出,基本遗传算法的主要运算过程如下:

1.编码:解空间中的解数据 ,作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合就构成了不同的点。

2.初始群体的生成:随机产生 个初始串结构数据,每个串结构数据称为一个个体, 个个体构成了一个群体。遗传算法以这 个串结构作为初始点开始迭代。设置进化代数计数器 ;设置最大进化代数 ;随机生成 个个体作为初始群体

3.适应度值评价检测:适应度函数表明个体或解的优劣性。对于不同的问题,适应度函数的定义方式不同。根据具体问题,计算群体 中各个个体的适应度。

4.选择:将选择算子作用于群体。

5.交叉:将交叉算子作用于群体。

6.变异:将变异算子作用于群体。

7.群体 经过选择、交叉、变异运算后得到下一代群体

8.终止条件判断:若 ,则 ,转到步骤(2);若 ,则以进化过程中所得到的具有最大适应度的个体作为最优解输出,终止运算。

 

3 遗传算法的理论基础

3.1 模式定理

模式(schema)是一个描述字符串集的模板,该字符串集中串的某些位置上存在着相似性。不失一般性,我们以二进制串作为编码方式来讨论模式定理。

定义2.1 基于三值字符集{0,1,*}所产生的能描述具有某些结构相似性的01字符串集的字符串称作模式。

以长度为5的串为例,模式0001*描述了在位置1234具有形式“0001”的所有字符串,即{0001000011}。由此可以看出,模式的概念为我们提供了一种简洁的用于描述在某些位置上具有相似性的01字符串集合的方法。在引入模式的概念后,我们看到一个串实际上隐含了多个模式(长度为n的串隐含着2n个模式),一个模式可以隐含在多个串中,不同的串之间通过模式而相互联系。遗传算法中串的运算实际上就是模式的运算,因此,通过分析模式在遗传操作下的变化,从而把握遗传算法的实质,这正是模式定理所要揭示的内容。

定义2.2 模式H中确定位置的个数称作该模式的阶数,记作

比如模式 。显然,一个模式的阶数越高,其样本数就越少,因而确定性就越高。

定义2.3 模式H第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距,记作

比如,模式011*1*的定义距为4,模式0*****的定义距为0

定理2.1(模式定理) 在遗传算子选择、交叉和变异的作用下,具有阶数低、长度短、平均适应度高于群体平均适应度的模式在子代中将以指数级增长。

3.2 积木块假设

定义2.4 阶数低、长度短、适应度高的模式称为积木块。

假设2.1 (积木块假设(Building Block Hypothesis))阶数低、长度短、适应度高的模式(积木块)在遗传算子作用下,相互结合,能生成阶数高、长度长、适应度高的模式,可最终生成全局最优解。

与积木块一样,一些好的模式在遗传算法操作下相互拼搭、结合,产生适应度更高的串,从而找到更优的可行解,这正是积木块假设所揭示的内容。

定义2.5 (隐含并行性)在算法的运行过程中,每代都处理了 个个体,单由于一个个体编码串中隐含了多种不同的模式,所以算法实质上却处理了更多的模式,这种并行处理过程有别于一般意义下的并行算法的运行过程,是包含在处理过程内部的一种隐含并行性,通过这种隐含并行性,使得我们可以快速地搜索出一些比较好的模式。

3.3 欺骗问题

在遗传算法中,将所有妨碍评价值高的个体生成从而影响遗传算法正常工作的问题称为欺骗问题(Deceptive Problem)。遗传算法运行过程具有将高于平均适应值、低阶和短定义距的模式重组成高阶模式的趋势。如在低阶模式中包含了最优解的话,则遗传算法就可能找出它来;但积木块的模式可能没包含最优串的具体取值,于是遗传算法就会收敛到一个次优解。

的最大值对应的X的集合为 H为包含 m阶模式,H的竞争模式为 ,而且 ,则 m阶欺骗。在欺骗问题中,为了造成骗局所需设置的最小问题规模(即阶乘)称为最小欺骗性。其主要思想是最大限度违背积木块假设,是优于由平均的短积木块生成局部最优解的方法。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/15203236/viewspace-615603/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2008-12-30

  • 博文量
    62
  • 访问量
    288010