智能优化理论-第3章遗传算法

遗传算法目录contents遗传算法寻优的基本思路遗传算法的理论基础遗传算法的实现及改进算法遗传算法寻优的基本思路01遗传算法是一种基于自然选择和基因遗传学原理的搜索算法，将“适者生存”这一基本的达尔文进化原理引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着算法的运行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。好的特征被不断地继承下来，坏的特性被逐渐淘汰。新一代个体中包含着上一代个体的大量信息，新一代的个体不断地在总体特性上胜过旧的一代，从而使整个群体向前进化发展。遗传算法寻优的基本思路研究遗传算法的目的主要有两个：一是通过它的研究来进一步解释自然界的适应过程；二是为了将自然生物系统的重要机理运用到人工系统的设计中。遗传算法的中心问题是鲁棒性，它能在许多不同的环境中通过效率及功能之间的协调平衡以求生存。人工系统很难达到如生物系统那样的鲁棒性。遗传算法正是吸取了自然生物系统“适者生存”的进化原理，使它能够提供一个在复杂空间中进行鲁棒搜索的方法。遗传算法寻优的基本思路输入标题02010403遗传算法寻优的基本思路遗传算法具有计算简单及功能强的特点，它对于搜索空间基本上不需要什么限制性的假设（如连续、导数存在及单峰等）。枚举法最大缺点是计算效率太低，对于一个实际问题，常常由于太大的搜索空间而不可能将所有的情况都搜索到。枚举法可以克服上述解析法的两个缺点，即它可以寻找到全局的极值，而且也不需要目标函数是连续光滑的。常规的寻优方法主要有3种类型：解析法、枚举法和随机法。解析法寻优通过让目标函数的梯度为零，进而求解一组非线性方程来寻求局部极值。遗传算法的理论基础0203表现型生物个体表现出来的性状，即具有特定基因型的个体在一定环境条件下表现出来的性状特征的总和。01基因是DNA分子片段，含有大量遗传信息，是控制生物体性状的基本遗传单位。02染色体包含一定数目的基因，是基因的物质载体，也是细胞中遗传信息的物质载体。遗传算法的基本概念遗传算法的基本概念01种群：每个物种由一定数量的个体组成，所有个体的总和称为种群。02适应度：用于衡量种群中每个个体的优劣程度，是度量每个个体对其生存环境的适应能力的标准。03遗传算法中，适应度函数根据目标函数设定，它的大小直接影响到种群中每个个体的生存概率。04一种群为遗传算法提供了搜索解的遗传进化搜索空间。010203通过一个简单的例子详细描述遗传算法的基本操作过程，目的在于清晰地展现遗传算法的理论基础。设需要求解的优化问题为寻找当自变量x在0-31之间取整数值时函数的最大值。枚举的方法是将x取尽所有可能值，观察是否得到最高的目标函数值。尽管对如此简单的问题该法是可靠的．但这是一种效率很低的方法。下面运用遗传算法来求解这个问题。遗传算法的基本操作针对本例中自变量的定义域，可以考虑采用二进制数来对其编码，这里恰好可用5位数来表示，如01010对应11111对应。许多其他的优化方法是从定义域空间的某个单个点出发来求解问题，并且根据某些规则，它相当于按照一定的路线，进行点到点的顺序搜索。遗传算法的第一步是将x编码为有限长度的串。编码的方法很多，这里仅举一种简单易行的方法。遗传算法的基本操作对于多峰值问题的求解很容易陷入局部极值。而遗传算法则是从一个种群（由若干个串组成，每个串对应一个自变量值）开始，不断地产生和测试新一代的种群。这种方法一开始便扩大了搜索的范围，因而可期望较快地完成问题的求解。初始种群的生成往往是随机产生的。对于本例，若设种群大小为4，即含有4个个体，则需按位随机生成4个5位二进制串，如可以通过掷硬币的方法来生成随机的串。遗传算法的基本操作若用计算机，可考虑首先产生0-l之间均匀分布的随机数．然后规定产生的随机数在0-0.5之间代表0，0.5-1之间的随机数代表1。若用上述方法，随机生成以下4个位串：01101，11000，01000，10011。位串1-4可分别解码为如下十进制的数遗传算法的基本操作位串1位串3位串2遗传算法的基本操作这样便完成了遗传算法的准备工作。位串4选择、交叉和变异。下面来介绍遗传算法的3个基本操作步骤遗传算法的基本操作01适应度越大，被选中的概率就越大．从而遗传到下一代的概率越大。优良个体在种群中具有较强的繁殖能力，而适应度较差的个体会受到排挤，甚至被淘汰。在选择算子的作用下，种群的整体质量得到逐步提高。在遗传算法中，以适应度为指标，把当前种群中适应度较高的个体选择出来，为下一步遗传操作做准备。020304遗传算法的基本操作123遗传算法的特点之一是它不对实际决策变量直接进行操作，而是对表示解的个体编码进行选择、交叉、变异等遗传运算。编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。好的编码方法可以使得交叉运算、变异运算等遗传操作简单易行，而差的编码方法则可能使得这些操作难以实现。遗传个体编码遗传个体编码假设某一个体的编码是则对应的解码公式为进制编码方法有下述一些优点：编码、解码操作简单易行。遗传个体编码03便于利用模式定理对算法进行理论分析。01交叉、变异等遗传操作便于实现。02符合最小字符集编码原则。遗传个体编码遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数(fitnessfunction)为依据，利用种群中每个个体的适应度值来进行搜索。适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数转换而成的。对目标函数值域的某种映射变换称为适应度的尺度变换。几种常见的适应度函数：直接以待求解的目标函数转化为适应度函数，改进的“界限构造法”和保守估计法。适应度函数的作用：在选择操作时会出现一些问题，如超常个体和种群中个体适应度差异较小的情况。适应度函数的设计：通常，适应度函数设计主要满足以下条件：单值、连续、非负和最大化；合理性和一致性；计算量小；通用性强。适应度函数及其尺度变换遗传算法的实现及改进算法03遗传算法需要提前设定控制参数，包括种群大小、交叉概率、变异概率和终止条件。种群大小影响算法效率，太小会降低多样性，太大则会影响收敛速度。交叉概率一般为0.400～0.990，变异概率在0.001～0.100范围内。遗传算法的实现终止条件分为两类：一类是预先设定的最大函数评价次数NFE，另一类是未找到最优解则终止算法。交叉操作借鉴生物进化中两性繁殖的作用方式，对两个个体进行基因对换操作产生新个体。变异操作通过对染色体的某些基因位点进行突变来产生新的个体，变异的主要作用在于保持种群的多样性。010203遗传算法的实现遗传算法的实现在种群中多数个体趋同的情况下，交叉操作能够产生的不同于父代个体的数量非常有限，甚至重复产生相同的解，而变异操作可以较为有效地异化种群中的个体，增加多样性，从而在一定程度上避免算法陷入早熟收敛。遗传算法的改进研究编码策略是遗传算法的基础工作之一，在问题求解中扮演着重要的角色。实际工程优化问题中的变量往往不能直接被遗传算法作用，需要采用编码策略将实际变量转化为可以被遗传算法直接操作的对象。编码过程实质上是一种“映射”过程，即在优化问题与算法涉及的操作对象之间建立一个一一对应法则。遗传算法的改进研究针对不同的问题，人们提出了不同的编码方式，包括二进制编码、格雷编码和实数编码等。格雷码克服了二进制码的不足，连续两个整数对应的编码之间仅有一个码位不同，其余完全相同。二进制编码具有最小字符编码原理和模式定理，但存在局部搜索能力不强、连续函数离散化误差大、不能反映问题固有结构等缺点。实数编码则针对多维、高精度要求的连续变量优化问题，将每个基因值用实数表示，提高了编码的精度和运行效率。自适应遗传算法中，交叉概率和变异概率的选择是影响算法行为和性能的关键所在。交叉概率越大，新个体产生的速度就越快。然而，当交叉概率过大时，遗传模式被破坏的可能性也会变大。如果交叉概率过小，会使搜索过程变得缓慢，甚至停滞不前。遗传算法的经典变体遗传算法的经典变体变异概率太小，不易产生新的个体结构；太大则变成随机搜索算法。02Srinivas等首次提出一种自适应遗传算法(AdaptiveGeneticAlgorithm，AGA)，其中交叉概率与变异概率能够随着适应度的大小而改变。03当群体中各个个体的适应度值趋于一致或者趋于局部最优时，增加交叉和变异概率；而当群体适应度值比较分散时，减小交叉和变异概率。01遗传算法的经典变体种群中具有最大适应值的个体的交叉概率和变异概率为零，这增大了进化趋向局部最优解的可能性。对适应度值高于群体平均适应度值的个体，给予较低的交叉和变异概率，使该个体得以保护进入下一代；而低于平均适应度值的个体，基于较高的交叉和变异概率，使该个体被淘汰。改进的自适应遗传算法使种群中具有最大适应值的个体的交叉概率和变异概率不为零。VS一个刻画种群多样性的函数，在此基础上提出交叉和变异算子的点数随种群多样性而变化。混合遗传算法的实质是将不同算法的优点有机结合，改善单纯遗传算法的性能。遗传算法的经典变体改进的遗传算法举例01改进的遗传算法在一个高低不同的层次上都使用了遗传算法。02生物模型中，遗传算法是对一个群体进行操作，该群体相当于自然界中的一群人。第一步的选择是以现实世界中的优胜劣汰现象为背景的。03010203第二步的交叉则相当于人类的结婚和生育。第三步的变异则与自然界中偶然发生的变异是一致的。包含着对模式的操作，遗传算法不断地产生