遗传算法概述.docx

遗传算法概述.docx

《遗传算法概述.docx》由会员分享，可在线阅读，更多相关《遗传算法概述.docx（13页珍藏版）》请在冰点文库上搜索。

遗传算法概述

适应度函数（fitnessfunction）

个体（individuals）

种群（population）

代（generations）

多样性或差异（diversity）

适应度值（fitnessvalues）

父辈和子辈（parentsandchildren）

最佳适应度值（bestfitnessvalues）

遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。

遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的群体。

遗传算法的三个基本操作：

选择、交叉和变异。

遗传算法是模拟自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传叙说。

其本质是以汇总高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。

遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案，在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。

这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境，就像自然界中的改造一样。

个体或当前近似解被编码为由字母组成的串，即染色体，使基因能在（表现）域决策变量上被惟一地描述。

交叉算子并不是必须在种群的所有串中执行的。

当一对个体被选中培育下一代，代替的是应用一个概率P。

进一步的遗传算法称为变异，再次使用一个概率P应用到新染色体上。

变异能根据一些概率准则引起个体基因表现型变化，子啊二进制表现型中，变异引起单个位的状态变换，即0变1,或者1变0。

在重组和变异后，如果需要，这些个体串随后被解码，进行目标函数评估，计算每个个体的适应度值，个体根据适应度被选择参加交配，并且这个过程继续指导产生子代。

在这种方法中，种群中个体的平均性能向得到提高，好的个体被保存并且相互产生下一代，而低适应度的个体则消失。

当一些判定条件满足后，遗传算法则终止，例如，一定的遗传代数，种群的均差或遇到搜索空间的特殊点。

遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。

它与传统的算法不同，大多数传统的优化算法是基于一个单一的度量函数（评估函数）的梯度或较高此估计，以产生一个确定性的试验概率序列；遗传算法不依赖于梯度信息，二是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的串，生成新的串的群体。

遗传算法的优点：

1）对可行解表示的广泛。

遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码得到的基因个体。

此编码操作使得遗传算法可以直接对结构对象进行操作。

所谓结构对象，繁殖集合、序列、矩阵、树、图、链和表等各种一维和二维甚至多维结构形式的对象。

这一特点使得遗传算法具有广泛的应用领域。

2）群体搜索特性。

许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。

相反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。

这一特点使遗传算法具有较好的全局搜索心梗，也使得遗传算法本身易于并行化。

3）不需要辅助信息。

遗传算法仅用适应度函数的数值来评估基因个体，并在此基础上进行遗传操作。

更重要的是，遗传算法的适应度函数不仅不受连续可微的约束。

而且其定义域可以任意设定。

对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。

由于限制条件的缩小，使得遗传算法的应用范围大大扩展。

4）内在启发式随机搜索特性。

遗传算法不是采用确定性规则，二是采用概率的变迁规则来指导它的方向。

概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。

虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内在的秉性搜索机制。

5）遗传算法在搜索过程中部容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很到的概率找到全局最优解。

6）遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题。

7）遗传算法具有固定的并行性和并行计算的能力。

8）遗传算法具有可扩展性，易于同别的技术混合。

遗传算法的不足之处：

1）编码不规范及编码存在表示的不准确性。

2）单一的遗产算法编码不能全面地将优化问题的约束表示出来，考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

3）遗传算法通常的额效率比其他传统的优化方法低。

4）遗传算法容易出现过早收敛。

5）遗传算法对算法的精度、可行度、计算复杂度等方面，还没有有效的定量分析方法。

求最优解或近似最优解的传统方法主要有解析法、随机法和穷举法。

解析法主要包括爬山法和间接法。

随机法主要包括导向随机方法和盲目随机方法。

而穷举法主要包括完全穷举法、回溯法、动态规划法和限界剪枝法。

1.遗传算法与启发式算法的比较

启发式算法是指通过寻求一种能产生可行解的启发式规则，找到问题的一个最优解或近似最优解。

该方法求解问题的效率较高，但是它对每一个所球

复数个基因组成染色体，染色体中基因的位置称为基因座，而基因所取得值叫做等位基因。

基因和基因座决定了染色体的特征，也就决定了生物个体的性质状态。

自然遗传算法

人工遗传算法

染色体（Chromosome）

解的编码（数据、数组、位串）

基因（Gene）

解中每一个分量的特征（特性、个性、探测器、位）

等位基因（Allele）

特性值

基因座（Locus）

串中位置

基因型（Genptype）

结构

表现型（Phenotype）

参数集、解码结构、候选解

遗传隐匿

非线性

个体（Individual）

解

适者生存

在算法停止时，最优目标值的解有最大的可能被留住

适应性（Fitness）

适应度函数值

群体（Population）

选定的一组解（其中解的个数为群体的规模）

复制（Reproduction）

根据适应函数选取的一组解

交配（Crossover）

通过交配原则产生一组新解的过程

变异（Mutation）

编码的某一个分量发生变化的过程

遗传算法的研究方向：

1）基础理论。

遗传算法的数学理论并不完善，张玲等对遗传算法的“模式定理”和“隐性并行性”进行了分析研究，之处其不足并之处遗传算法本质上是一个具有定量制导的随机搜索技术。

在遗传算法中，群体规模和遗传算子的控制参数的选取是非常困难，但它们又是必不可少的实验参数，在这方面，已有一些具有指导性的实验结果。

遗传算法还有一个过早收敛的问题，如何组织过早收敛也是人们正在研究的问题之一。

2）分布并行遗传算法。

遗传算法的并行性主要从三个方面考虑，即个体适应度评价的并行性、整个群体各个个体适应度评价的并行性及子代群体产生过程的并行性。

3）分类系统。

分类系统属于基于遗传算法的机器学习中的一类，包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。

4）遗传神经网络。

遗传神经网路包括连接级、网络结构和学习规则的进化。

遗传算法与神经网络相结合，成功地用于从分析时间序列来进行财政预算。

5）进化算法。

模拟自然进化过程可以产生鲁棒的计算机算法——进化算法。

遗传算法是其三种典型的算法之一，其余两种算法是进化规划和进化策略，这三种算法是独立发展起来的。

6）人工生命与遗传算法。

基于遗传算法的应用：

信息战。

遗传算法在信息战领域得到了初步应用。

使用遗传算法能够进行雷达目标识别、数据挖掘、作战仿真、雷达辐射源识别、雷达天线优化设计、雷达目标跟踪。

盲信号处理、空间谱估计、天线设计、网络入侵检测、情报分析中的数据挖掘和数据融合、信息战系统仿真、作战效能评估、作战辅助决策等。

图像处理

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

信号处理

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

机器人

路径规划

人工生命

生命的遗传进化

第二章基本遗传算法及改进

Holland创建的遗传算法是一种概率搜索算法，它利用某种编码极化作用于称为染色体的数串，其基本思想是模拟由这些串组成的个体进化过程。

该算法通过有组织的、然而是随机的信息交换，重新组合那些适应性好的串。

在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。

遗传算法是一种随机优化算法，它可以有效地利用已有的信息来搜索那些有希望改善解质量的串。

类似于自然进化，遗传算法通过作用于染色体上的基因，需找好的染色体来求解问题。

与自然界相似，遗传算法对待求解问题本身已无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来改变染色体，使实用性好的染色体比适应性差的染色体有更多的繁殖机会。

遗传算法欧尼了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群（population）出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断地繁衍进化，最后收敛到一群最适应环境的个体（individual），求得问题的最优解。

完整的遗传算法运算流程参见上图，

1）编码：

解空间中的解数据x，作为遗传算法的表现形式。

从表现型到基因型的映射称为编码。

遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。

2）初始群体的生成：

随机产生N各初始串结构数据，每个串结构数据称为一个个体，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）；若t>t,则以进化过程中所得到的最大是适应度的个体作为最优解输出，终止运算。

遗传算法的基本操作：

1）选择：

选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。

根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。

遗传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。

这样就体现了达尔文的适者生存原则。

2）交叉。

交叉操作是遗传算法中最主要的遗传操作。

通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。

将群体内的各个个体随机搭配成对，对每一个个体，以某个概率（称为交叉概率，crossoverrate）交换它们之间的部分染色体。

交叉体现了信息交换的思想。

3）变异。

变异操作首先在群体中随机选择一个个体，对于选中的个体以一定的概率即改变串结构数据中的某个串的值，即对群体中的每一个个体，以某一概率（称为变异概率，mutationrate）改变某一个或某一些基因座上的基因值为其他的等位基因，。

同生物界一眼，遗传算法中变异发生的概率很低。

变异为新个体的产生提供了机会。

基本遗传算法（simplegeneticalgorithm,SGA）

基本遗传算法的数学模型

式中：

——个体的编码方法；

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

——初始种群；

——种群大小；

——选择算子；

——交叉算子；

——变异算子；

——遗传运算终止条件；

基本遗传算法的流程图，

基本遗传算法的步骤：

1）染色体编码（chromosomecoding）与解码（decode）

解码公式:

2）个体适应度的检测评估

基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会多少。

3）遗传算子

A.选择运算使用比例选择算子。

比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。

若设种群数为

，个体

的适应度为

，则个体

被选取的概率为

当个体的概率给定后，产生之间

的均匀随机数来决定哪个个体参加交配。

若个体的选择概率大，则能被多次选中，它的遗传基因会在种群中扩大；若个体的选择概率小，则被淘汰。

b.交叉运算使用单点交叉算子。

只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体。

c.变异运算使用基本位变异算子或均匀变异算子。

为了避免问题过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1,1变为0。

4）基本遗传算法的运行参数

基本遗传算法那有些列4个运行参数需要余弦设定，即

。

为群体大小，即群体中所含个体的数量，一般取为20~100；

为遗传算法的终止进化代数，一般取为100~500；

为交叉概率，一般取为0.4~0.99；

为变异概率，一般取为0.0001~0.1。

改进的遗传算法

遗传算法目前存在的问题：

1）适应度值标定方式多种多样，没有一个简洁、通用的方法，不利于对遗传算法的使用。

2）遗传算法的早熟现象（即很快收敛到局部最优解而不是全局最优解）是迄今为止最难处理的关键问题。

3）快要接近最优解时在最优解附近左右摆动，收敛较慢。

自从1975年J.H.Holland系统提出遗传算法的完整结构和理论依赖，众多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定和交叉机理等进行了深入的研究，提出了各种变形的遗传算法。

其基本途径概括起来主要有下面几个方面：

1）改进遗传算法的组成成分或使用极化，如选用优化控制参数、适合问题特性的编码技术等。

2）采用混合遗传算法（hybridgeneticalgorithm）。

3）采用动态自适应技术，子啊进化过程中调整算法控制参数和编码精度。

4）采用非标准的遗传操作算子

5）采用并行算法。

七种改进的遗传算法：

1）分层遗传算法（hierarchicgeneticalgorithm）

2）CHC算法

3）Messy遗传算法

4）自适应遗传算法（adaptivegeneticalgorithm）

5）基于小生境技术的遗传算法（nichedgeneticalgorithm,NGA）

6）并行遗传算法（parallelgeneticalgorithm）;

7）混合遗传算法：

遗传算法与最速下降法相结合的混合遗传算法；遗传算法与模拟退火法（simulatedannealing）相结合的混合遗传算法。

早熟问题是遗传算法中不可忽视的现象，其具体表现为：

1）群体中所有的个体都陷于同一极值而停止进化；

2）接近最优解的个体总是被淘汰，进化过程不收敛。

对此可以采用以下方法来解决：

1）动态确定变异概率，既可以防止有两基因因为变异而遭破坏，又可在陷于局优解时为种群引入新的基因。

2）改进选择方式，放弃赌轮选择，以避免早期的高适应度个体迅速占据种群和后期的种群中因个体的适应度相差不大而导致种群停止进化。

未成熟收敛现象主要表现在两个方面：

1）群体中所有的个体都陷入同一极值而停止进化。

2）接近最优解的个体总是被淘汰，进化过程不收敛。

遗传算法工具箱