《遗传算法综述》word版

《《遗传算法综述》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、遗传算法综述太原理工大学刘晶学号：s20091056摘要：遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获得和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优的方案。遗传算法作为一种实用、高效、鲁棒性强的优化技术，有着广泛的应用前景。关键词：遗传算法数学模型优点流程一，概述。遗传算法（GeneticAlgorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发，创

2、造了一种基于生物遗传和进化机制的适应于复杂系统优化的自适应概率优化技术———遗传算法。二，基本遗传算法的数学模型。基本遗传算法可表示为：SGA=（C，E，P0，M，Φ，Γ，Ψ，T）式中，C为个体的编码方法；E为个体适应度评价函数；P0为初始种群；M为种群大小；Φ为选择算子；Γ为交叉算子；Ψ为变异算子；T为遗传运算终止条件。三，遗传算法的优点。3.1对可行解的广泛性表示。遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码得到的基因个体。次编码操作使得遗传算法可以直接对结构对象进行操作。（1）通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优

3、化。（2）通过对集合的操作，遗传算法可实现对规则集合和知识库的精炼而达到高质量的机器学习目的。（3）通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树。（4）通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，可自动构造的顺序控制系统。3.2群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点，相反，遗传算法采用的是同时处理群体中多个个体的方法。3.3不需要辅助信息。遗传算法仅用适应度函数的数值来评估基因个体，并在此基础上进行遗传操作。更重要的是，遗传算法的适应度函数不仅不受连续

4、可微的约束，而且某定义域可以任意设定。对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。3.4内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内在并行搜索机制。3.5遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。3.6遗传算法采用自然进化机制

5、来表现复杂的现象，能够快速可靠的解决求解非常困难的问题。3.7遗传算法具有固有的并行性和并行计算的能力。3.8遗传算法具有可扩展性，易于同别的技术混合使用。四，遗传算法流程。遗传算法的主要运算过程如下：4.1编码：解空间的解数据，作为遗传算法的表现型形式，从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构的数据的不同组合就构成了不同的点。4.2初始群体的生成：随即产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t←0；设

6、置最大进化代数T；随机生成M个个体作为初始群体P(0)。4.3适应度值评价检测：适应度函数表明个体的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体P(t)中各个个体的适应度。4.4选择：将选择算子作用于群体。4.5交叉：将交叉算子作用于群体。4.6变异：将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)。4.7终止条件判断：若t≤T，则t=t＋1，转到步骤4.2；若t>T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。五，遗传算法的发展方向5.1遗传算法自身的优化算法在各种问题中得到广泛的

7、应用以来，遗传算法的优化问题就成了人们研究的焦点。专家学者们从各个方面，在各种细节上采用各种方法试图来改进遗传算法。从编码方法，控制种群，控制交叉，控制变异等来改进遗传算法。根据不同问题的需要来选择编码方案，是改进遗传算法最初的手段。随着编码方案的不断完善，现在从编码方案上来改进遗传算法的意义已经很小。目前对遗传算法的优化主要有两大手段。一是利用对种群的控制，在选取种群的时候，在种群的规模，种群的多样性上下功夫。有的是利用加入种间竞争的手段。另一种是通过控制交叉方法和变异的概率，根据问题的实际情况来设定一个线性或非线性的函数来