第七章-遗传算法简介

第七章遗传算法与控制简介模拟进化计算（SimulatedEvolutionaryComputation)是近十几年来信息科学、人工智能与计算机科学的一大研究领域，由此所派生的求解优化问题的仿生类算法（遗传算法、演化策略、进化程序），由于其鲜明的生物背景、新颖的设计原理、独特的分析方法和成功的应用实践，正日益形成全局搜索与多目标优化理论的一个崭新分支。遗传算法（GeneticAlgorithm,简称GA）是通过模拟生物进化过程来完成优化搜索的。科学研究、工程实际与国民经济发展的众多问题可归结为“最大效益、最小代价”这类典型的优化模型。求解这类模型导致寻求某个目标函数（有解析表达式或无解析表达式）在特定区域上的最优解，传统的建立在梯度计算基础上的非线性规划类方法，当目标函数仅具有单极点时，通常表现出较高的计算效率，但当目标函数具有多极值点时，由于其本身固有的局部优化性及不稳健等缺陷，而被广泛认为不适于全局优化问题的求解。近二十年来，人们相继发展了许多求解全局优化问题的方法，一般可分为确定型与非确定型（如随机搜索）算法。Monto-Carlo方法及模拟退火算法都归属后者。当目标函数具有为数不多的极值点时，确定型算法常表现出较高的计算效率，但同时也暴露出算法复杂、对目标函数的性质要求高、可靠性差等缺点。相比而言，随机搜索方法具有较强的鲁棒性，算法容易实现，但常有计算效率低的缺点。仿生类算法是近十几年来才发展起来的一类新型全局优化搜索技术，它们通过向自然界学习，借鉴生物进化机制求解问题。这类算法的主要优点在于其本质上的并行性、广泛的可适用性（如对目标函数的性态无特殊要求，特别可以没有明确的表达式）和较强的鲁棒性、简明性与全局优化性能。虽然从基本思想的产生至今已有二、三十年的历史，但广泛用于求解优化问题还是近十几年的事。初步研究及广泛的应用实践已显示出它们作为可靠、有效的全局优化算法的巨大潜力和诱人前景。仿生类算法，就其目前发展而言，可分为仿生过程算法与仿生结构算法两大类，前者以模拟进化算法为代表，后者以神经网络为典型。遗传算法的生物学背景适者生存：最适合自然环境的群体往往产生了更大的后代群体。生物进化的基本过程：染色体(chromosome)：生物的遗传物质的主要载体。基因(gene)：扩展生物性状的遗传物质的功能单元和结构单位。基因座（locus）：染色体中基因的位置。等位基因（alleles）：基因所取的值。生物遗传概念遗产算法中的应用适者生存目标值比较大的解被选择的可能性大个体（Individual）解染色体（Chromosome）解的编码（字符串、向量等）基因（Gene）解中每一分量的特征适应性（Fitness）适应函数值群体（Population）根据适应函数值选定的一组解（解的个数为群体的规模）婚配（Marry）交叉（Crossover）选择两个染色体进行交叉产生一组新的染色体的过程变异（Mutation）编码的某一分量发生变化的过程遗传算法的基本思想：在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。最优化问题遗传算法目标函数可行解一组解适应度函数染色体种群遗传算法的发展历史1962年，Fraser提出了自然遗传算法。1965年，Holland首次提出了人工遗传操作的重要性。1967年，Bagley首次提出了遗传算法这一术语。1970年，Cavicchio把遗传算法应用于模式识别中。1971年，Hollstien在论文《计算机控制系统中人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法。1975年，美国J.Holland出版了《自然系统和人工系统的适配》；DeJong完成了重要论文《遗传自适应系统的行为分析》。20世纪80年代以后，遗传算法进入兴盛发展时期。设计遗传算法的基本原则与内容设计的基本原则：适用性：算法所能适用的问题种类。可靠性：算法对于所设计的问题，以适当的精度求解其中大多数问题的能力。收敛性：算法能否收敛到全局最优。稳定性：算法对其控制参数及问题数据的敏感度。生物类比：通过类比的方法引入在生物界被认为是有效的方法及操作。设计的基本内容：设计遗传算法的基本原则与内容编码方案：编码表示方式。适应度函数：目标函数。选择策略：优胜劣汰。控制参数：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等。遗传算子：选择(selection)；交叉(crossover)；变异(mutation)。算法的终止准则：规定一个最大的演化代数，或算法在连续多少代以后解的适应值没有改进。遗传算法的搜索机制遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。基本遗传算法基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成遗传算法的五个基本要素：参数编码初始群体的设定适应度函数的设计遗传操作设计控制参数设定编码1.位串编码一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间B={0，1}上，然后在位串空间上进行遗传操作。（1）二进制编码编码(1)二进制编码（续）优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。缺点：①相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：0111116：10000②要先给出求解的精度。③求解高维优化问题的二进制编码串长，算法的搜索效率低。编码（2）Gray编码Gray编码:将二进制编码通过一个变换进行转换得到的编码。二进制串n...21Grayn...21二进制编码Gray编码1111kkkkkGray编码二进制编码)2(mod1kiik编码2.实数编码采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。编码3.有序串编码有序问题：目标函数的值不仅与表示解的字符串的值有关，而且与其所在字符串的位置有关。4．结构式编码Goldberg等提出MessyGA(mGA)的遗传算法编码方法。1.初始种群的产生群体设定（1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。2.种群规模的确定群体设定模式定理表明：若群体规模为M，则遗传操作可从这M个个体中生成和检测个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。3M群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复杂。1.将目标函数映射成适应度函数的方法适应度函数若目标函数为最大化问题，则若目标函数为最小化问题，则)())((xfxfFit)(1))((xfxfFit将目标函数转换为求最大值的形式,且保证函数值非负！若目标函数为最大化问题，则若目标函数为最小化问题，则minmin()()(())0fxCfxCFitfx其他情况maxmax()()(())0CfxfxCFitfx其他情况1.将目标函数映射成适应度函数的方法(续）适应度函数存在界限值预选估计困难或者不能精确估计的问题！若目标函数为最大化问题，则若目标函数为最小化问题，则：目标函数界限的保守估计值。1(())0()01()Fitfxccfxcfx，1(())0()01()Fitfxccfxcfx，c2.适应度函数的尺度变换在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题（deceptiveproblem）。过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。适应度函数的尺度变换（fitnessscaling）或者定标：对适应度函数值域的某种映射变换。适应度函数2.适应度函数的尺度变换(续）（1）线性变换：baffminfffaavgavgminminffffbavgavgavgavgmultfffCamax)1(avgavgavgmultffffCfbmaxmax)(,avgavgffavgmultfCfmax满足满足最小适应度值非负适应度函数2.适应度函数的尺度变换(续）（2）幂函数变换法：Kffaffe（3）指数变换法：适应度函数选择1.个体选择概率分配方法选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。1.个体选择概率分配方法（1）适应度比例方法（fitnessproportionalmodel）或蒙特卡罗法（MonteCarlo）Miiisiffp1各个个体被选择的概率和其适应度值成比例。个体被选择的概率为：i选择个体ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.091.个体选择概率分配方法（2）排序方法（rank-basedmodel）①线性排序：J.E.Baker群体成员按适应值大小从好到坏依次排列：个体按转盘式选择的方式选择父体Nxxx,,,21iipx分配选择概率)1(MMbiapi选择1.个体选择概率分配方法（2）排序方法（rank-basedmodel）②非线性排序：Z.Michalewicz将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：MiMiqqqpMii1,,2,1)1()1(11选择1.个体选择概率分配方法（2）排序方法（rank-basedmodel）可用其他非线性函数来分配选择概率，只要满足以下条件：Miip11)2(满足则且若iMMpxfxfxfxxxP),(...)()(,)1(212,1Mppp21选择2.选择个体方法（1）转盘赌选择（roulettewheelselection）按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。第1轮产生一个随机数：0.81第2轮产生一个随机数：0.32选择2.选择个体方法（2）锦标赛选择方法（tournamentselectionmodel）锦标赛选择方法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。随机竞争方法（stochastictournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。选择2.选择个体方法（3）和选择),(选择),(从规模为的群体中随机选取个体通过重组和变异生成个后代，再选取个最优的