第七章-遗传算法简介

《第七章-遗传算法简介》由会员分享，可在线阅读，更多相关《第七章-遗传算法简介（111页珍藏版）》请在金锄头文库上搜索。

1、第七章 遗传算法与控制简介,模拟进化计算（Simulated Evolutionary Computation)是近十几年来信息科学、人工智能与计算机科学的一大研究领域，由此所派生的求解优化问题的仿生类算法（遗传算法、演化策略、进化程序），由于其鲜明的生物背景、新颖的设计原理、独特的分析方法和成功的应用实践，正日益形成全局搜索与多目标优化理论的一个崭新分支。 遗传算法（Genetic Algorithm,简称GA）是通过模拟生物进化过程来完成优化搜索的。,科学研究、工程实际与国民经济发展的众多问题可归结为“最大效益、最小代价”这类典型的优化模型。求解这类模型导致寻求某个目标函数（有解析表达式或

2、无解析表达式）在特定区域上的最优解，传统的建立在梯度计算基础上的非线性规划类方法，当目标函数仅具有单极点时，通常表现出较高的计算效率，但当目标函数具有多极值点时，由于其本身固有的局部优化性及不稳健等缺陷，而被广泛认为不适于全局优化问题的求解。近二十年来，人们相继发展了许多求解全局优化问题的方法，一般可分为确定型与非确定型（如随机搜索）算法。Monto-Carlo方法及模拟退火算法都归属后者。当目标函数具有为数不多的极值点时，确定型算法常表现出较高的计算效率，但同时也暴露出算法复杂、对目标函数的性质要求高、可靠性差等缺点。相比而言，随机搜索方法具有较强的鲁棒性，算法容易实现，但常有计算效率低的缺

3、点。,仿生类算法是近十几年来才发展起来的一类新型全局优化搜索技术，它们通过向自然界学习，借鉴生物进化机制求解问题。这类算法的主要优点在于其本质上的并行性、广泛的可适用性（如对目标函数的性态无特殊要求，特别可以没有明确的表达式）和较强的鲁棒性、简明性与全局优化性能。虽然从基本思想的产生至今已有二、三十年的历史，但广泛用于求解优化问题还是近十几年的事。初步研究及广泛的应用实践已显示出它们作为可靠、有效的全局优化算法的巨大潜力和诱人前景。 仿生类算法，就其目前发展而言，可分为仿生过程算法与仿生结构算法两大类，前者以模拟进化算法为代表，后者以神经网络为典型。,遗传算法的生物学背景,适者生存：最适合自然

4、环境的群体往往产生了更大的后代群体。 生物进化的基本过程：,染色体(chromosome)：生物的遗传物质的主要载体。 基因(gene)：扩展生物性状的遗传物质的功能单元和结构单位。 基因座（locus）：染色体中基因的位置。 等位基因（alleles）：基因所取的值。,遗传算法的基本思想： 在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。,遗传算法的发展历史,1962年，Fraser提出了自然遗传算法。 1965年，Holland首次提出了人工遗传操作的重要性。 1967年，Bagley首次提出了遗传算法这一术语。 1970年，Cavicchio把遗传算法应用于模式识别

5、中。 1971年，Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。 1975年，美国J. Holland出版了自然系统和人工系统的适配；DeJong完成了重要论文遗传自适应系统的行为分析。 20世纪80年代以后，遗传算法进入兴盛发展时期。,设计遗传算法的基本原则与内容,设计的基本原则：,设计的基本内容：,设计遗传算法的基本原则与内容,遗传算法的搜索机制,遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一

6、代的候选解群，重复此过程，直到满足某种收敛指标为止。,基本遗传算法,基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。,基本遗传算法的组成,遗传算法的五个基本要素： 参数编码 初始群体的设定 适应度函数的设计 遗传操作设计 控制参数设定,编码,位串编码,一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。,二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间 B=0，1上，然后在位串空间

7、上进行遗传操作。,（1） 二进制编码,编码,(1) 二进制编码（续）,优点： 类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。,缺点： 相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。 15：01111 16： 10000 要先给出求解的精度。 求解高维优化问题的二进制编码串长，算法的搜索效率低。,编码,（2） Gray 编码,Gray编码:将二进制编码通过一个变换进行转换得到的编码。,编码,2. 实数编码,采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。 多参数映射编码的基本思想：把每个

8、参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。 多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。,编码,3. 有序串编码,有序问题：目标函数的值不仅与表示解的字符串的值有关，而且与其所在字符串的位置有关。,4结构式编码,Goldberg等提出MessyGA(mGA)的遗传算法编码方法。,初始种群的产生,群体设定,（1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。 （2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规

9、模。,2. 种群规模的确定,群体设定,模式定理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。,群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。 群体规模太大，计算复杂。,将目标函数映射成适应度函数的方法,适应度函数,若目标函数为最大化问题，则 若目标函数为最小化问题，则,将目标函数转换为求最大值的形式,且保证函数值非负！,若目标函数为最大化问题，则 若目标函数为最小化问题，则,将目标函数映射成适应度函数的方法(续）,适应度函数,存在界限值预选估计困难或者不能精确估计的问题！,若目标函数为最大化问题，则 若目

10、标函数为最小化问题，则 ：目标函数界限的保守估计值。,适应度函数的尺度变换,在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题（deceptive problem）。,过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。,停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。,适应度函数的尺度变换（fitness scaling）或者定标：对适应度函数值域的某种映射变换。,适应度函数,适应度函数的尺度变换(续）,（1）线性变换：,满足,适应度函数,适应度函数的尺度变换(续）,（2）幂函数变换法：,（3）指数变换法：,适应度函数,选择,个体选

11、择概率分配方法 选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。 判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。,个体选择概率分配方法 （1）适应度比例方法（fitness proportional model）或蒙特卡罗法（Monte Carlo）,各个个体被选择的概率和其适应度值成比例。,个体 被选择的概率为：,选择,1. 个体选择概率分配方法 （2） 排序方法 （rank-based model）, 线性排序：J. E. Baker,群体成员按适应值大小从好到坏依次排列：

12、个体 按转盘式选择的方式选择父体,选择,1. 个体选择概率分配方法 （2） 排序方法 （rank-based model）, 非线性排序： Z. Michalewicz,将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：,选择,1.个体选择概率分配方法 （2） 排序方法 （rank-based model）,可用其他非线性函数来分配选择概率，只要满足以下条件：,选择,2. 选择个体方法 （1）转盘赌选择（roulette wheel selection）,按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。 产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。,

13、第1轮产生一个随机数：0.81,第2轮产生一个随机数：0.32,选择,2. 选择个体方法 （2）锦标赛选择方法（tournament selection model）,锦标赛选择方法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。,随机竞争方法（stochastic tournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。,选择,2. 选择个体方法 （3） 和 选择,从规模为 的群体中随机选取个体通过重组和变异生成 个后代， 再选取 个最优的后代作为

14、新一代种群。,从 个后代与其父体共 中选取 个最优的后代。,选择,2. 选择个体方法 （4）Boltzmann锦标赛选择,最佳个体（elitist model）保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。,（5）最佳个体保存方法,随机选取两个个体 ，若 则选择适应值好的作为胜者，否则计算概率 ，若 ，选择差解，否则选择好解。,选择,交叉,1. 基本的交叉算子 （1）一点交叉（single-point crossover）,一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进

15、行互换，并生成两个新的个体。,二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。,（2）二点交叉 （two-point crossover）,交叉,基本的交叉算子（续）,均匀交叉：按照均匀概率抽取一些位，每一位是否被选取都是随机的，并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。,（3）均匀交叉（uniform crossover）或一致交叉,交叉,2. 修正的交叉方法 （1）部分匹配交叉PMX：Goldberg D. E.和R. Lingle(1985),2. 修正的交叉方法(续） （2）顺序交叉OX：Davis L. (1985),（3） 循环交叉CX：Smith

16、D. (1985),交叉,3. 实数编码的交叉方法 （1）离散交叉（discrete crossover）,部分离散交叉：在父解向量中选择一部分分量，然后交换这些分量。 二进制的点式交叉,整体离散交叉：以0.5的概率交换父体 的所有分量。 二进制编码的均匀性交叉,交叉,3. 实数编码的交叉方法（续） （2）算术交叉（arithmetical crossover）,部分算术：先在父解向量中选择一部分分量，如第 个分量以后的所有分量，然后生成 个0，1区间的随机数，并将两个后代定义为：,交叉,3. 实数编码的交叉方法（续） （2）算术交叉（arithmetical crossover）,整体算术交叉：先生成 n 个区间的随机数，则后代分别定义为：,交叉,1. 整