遗传算法基础知识.doc

遗传算法（GENETIC ALGORITHM，GA）一、遗传算法的特点：1、 遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有多条，而非单条，因而具有良好的并行性。2、 遗传算法只需要利用目标的取值信息，而无需梯度等高价值信息，因而适用于任何大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。3、 遗传算法择优机制是一种软选择，加上其良好的并行性，使它具有良好的全局优化和稳健性。4、 遗传算法操作的可行解是经过编码化的（通常采用二进制编码），目标函数解释为编码化个体（可行解）的适应值，因而具有良好的可操作性和简单性。二、遗传算法的发展与现状遗传算法的产生归功于美国的Michigan大学的Holland在20世纪60年代末、70年代初的开创性，其本意是在人工适应系统中设计的一种基于自然演化原理搜索机制。大约在同一时代，Foegl和Rechenberg及Schwefel,引入了另两种基于自然演化原理的算法，演化程序（evolutionary programming）和演化策略(evolution strategies).这三种算法构成了目前演化计算(evolutionary computation)领域的三大分支，它们从不同层次、不同角度模拟自然演化原理，以达到求解问题的目的。Holland不仅设计了遗传算法的模拟与操作原理，更重要的是他运用统计策略理论对遗传算法的搜索机理进行了理论分析，建立了著名的Schema定理和隐含并行（implicit parallelism）原理，为遗传算法奠定了基础。遗传算法应用于函数优化始于De Jone的在线（one-line）和离线（off-line）指标仍是目前衡量遗传算法性能的主要手段。1、 遗传算法在神经网络、模糊系统和机器学习中的应用神经网络的学习包含两个优化过程，分别是网络连接权重的优化和网络拓扑结构的优化。优化连接权重最著名的方法是Rumelhart提出的基于梯度下降法的反向传播法（backpropagation,BP）。BP算法的最大弱点是局部极小问题和无法学习网络拓扑结构。作为一种通用性和全局性良好的优化技术，遗传算法用于神经网络的训练就是很自然的事情。遗传算法用于神经网络的学习可分为三个不同的层次：连接权重的学习规则的学习。目前遗传算法已经广泛用于前向网络（feedward networks）、径向基网络（radial basis function networks）、Kohonen特征映射及Recurrent网络等各种人工神经网络的训练与设计中。演化神经网络（evolutionary artificial neural networks）作为一种一般的自适应学习模型加以研究。被Zedeh 称作软计算（soft computing）的两大组成部分遗传算法与模糊系统的相互融合也是近年人们关注的话题。模糊系统是对人类处理模糊性概念极其推理机制的模拟。最初，在模糊系统设计中，推理方法的选取、隶属函数形状及参数的选取、相关权重的确定以及规则的确定，均是由专家根据实际经验经验指定的。模糊神经网络（fuzzy neural networks）.遗传算法已成功应用于隶属函数形状与参数优化，系统相关权重的优化以及推理规则的选取。此外，模糊集技术也被用于遗传算法的某些GA的新型遗传算法，以达到改进经典遗传算法的目的。大多数机器学习系统都有一个共同的特征，即具备对自身结构进行调整的能力，从而达到改进性能的、发现并利用有意义的概念，或改进其内部知识结构的一致性和通用性。分类系统（classifer system）是遗传算法与机器学习经典的生产系统（production system）相结合的产物。遗传算法也用于导师概念学习（supervised concept learing）、特征选取与重构及强迫学习(reinforcement learing)等机器学习领域。2、 遗传算法设计与执行策略遗传算法操作的是一群编码化的可行解，称作种群。它通过种群的更新与迭代来搜索全局最优解。种群的迭代是通过选择、杂交和变异等具有生物意义的遗传算子来实现的。在Holland的最初模型中采用的是二进制定长编码和固定种群，遗传算法的主要形式为比例选择、单点杂交和位变异。近年的发展：（1） 编码方法灰色编码可用于克服二进制编码映射的不连续问题（即欧氏空间中邻近点的二进制编码在Hamming距离下并不邻近）。动态参数编码（dynamic parameter encoding）提出是为了克服搜索效率与表示时间精度间的矛盾，同时对克服过早收敛现象。此外，多值编码、实值编码、区间编码、Delta编码等多种编码方法也各有优缺点。（2） 选择机制选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。选择压(selective pressure)描述了选择机制挑选种群中不同个体做母体的概率大小的差异。选择压过大，会造成几个较好可行解（不一定是近似全局最优解）迅速抢占了整个种群；选择压过小，则会使算法呈现出纯粹的随机徘徊行为。秩选择、适应值函数的尺度变换均是为了克服经典的比例选择所造成的选择压过大或过小而设计的。杰出者选择(elitist selection)则通过无条件地保留每代种群中最优者而克服选择下遗传算法不能依靠概率收敛到全局最优解的问题。杂交和变异是遗传算法最具争议的两种机制。争论的焦点是：单点杂交、多点杂交的优劣；杂交机制与变异机制的优劣。经典的观点强调杂交的作用，而认为变异只是一个背景机制，并认为在杂交机制中强度最弱的单点杂交是最好的。强调杂交作用的观点是基于遗传算法中著名的建筑块假设(building block hypothesis),而这一假设并末得到证明。（3） 杂交与变异机制除了关于世代GA（generation GA）和稳定状态GA(steady state GA)的比较仍在研究。（4） 执行策略的改进1、 遗传算法与模拟退火算法的结合模拟退火(simulated annealing)是一种基于热力学理论的优化方法，并有着完善的全局收敛理论。在遗传算法中已各种形式融入模拟退火思想，从而使得遗传算法在理论上具有全局收敛次性。2、 遗传算法与局部优化方法的结合把遗传算法与局部搜索方法有机结合起来，是改进遗传算法性能的一个卓有成效的方法。这种混合型遗传算法不但模拟了生物种群的学习过程，而且事实上还模拟了种群中的个体在生命周期内具有学习行为这一生物现象。这在生物学中称作lamarckian evolution 和baldwin effect。3、 并行遗传算法(parallel genetic algorithm)并行遗传算法是在遗传算法的实施中加入自然生物种群中的空间因素，它的目的是可以在大规模并行机上运行，即使是序列实施并行遗传算法，也可以克服经典遗传算法性能上的不足，从而提高算法的效率。并行遗传算法大致分为两种：一种是岛模型（island model），称作粗粒并行遗传算法(coarse-grained PGA);另一种是细胞模型(cellular model),称为细粒并行遗传算法(fine- grained PGA)。岛模型的实施方法是在几个独立按经典GA方法运行的种群（称作子种群）中加入迁移（migration）因素；而细胞模型的实施是在一个单一种群中，通过对经典整体性选择与杂交机制的局部化来达到并行的目的。岛模型考虑的是种群的空间结构，而细胞模型考虑的是一种群中个体的空间结构。4、 共存演化遗传算法(cooperative co-evolutionary GA)这一方法的思想是生物个体间不但有竞争，而且还具有合作行为。CCGA通过把复杂问题分解为数个子问题，通过代表这些子问题的个体间既合作又竞争的演化过程，达到求解问题的目的。5、 混乱遗传算法（messy genetic algorithm）三、遗传算法的基础理论研究目前的工作主要集中在遗传算法的欺骗函数（decetive function）研究。所谓欺骗函数就是那些对遗传算法进行误导，使期错误地收敛到非全局最优解状态的函数。1、 遗传算法的马氏链分析种群马氏2、 遗传算法的收敛理论四、遗传算法基本的基本概念选择、交叉、突然变异（Selection, Crossover, Mutation）组成，称为遗传操作（Genetic Operator）.GA空间中的个体（Individual）就是染色体，个体的基本构成要素是遗传基因（Gene），个体上遗传基因所在的位置称为基因座（Locus ），一组个体的集合称为种群（Population）。个体对环境适应能力的评价用适应度（Fitness）表示，适应度大的个体，是优质个体，表征其在此环境下的生存能力强。定义1.1（个体和个体空间）所谓L长度的个体X，即是长度为L的0和1字符串，简称个体。L称为个体的链长，L长度的个体的全体记为S=0，1L，称为个体空间。按照遗传学的术语，个体也称为染色体（chromosome）,个体的分量称为基因（gene）,分量的取值称为等位基因（allele）。例1对一个饭店的经营决策，考虑三个因素：价格、饮料与服务速度。三个因素称为变量。对于价格，用0表示价格高，用1表示价格低；对于饮料，用0表示啤酒，用1表示可乐；对于服务速度，用0表示慢，用1表示快。那么个体如：X=（0 1 1）的链长L=3，S=0，13有8个个体。定义1.2（种群和种群空间）所谓N-种群是N个个体组成的集合（个体允许重复），简称种群。N称为种群规模，称为N-种群空间。齐次种群例2 （续例1）如对于一个饭店的经营策略，一个个体表示一种经营决策，则X1=（0 1 1），X2=（0 0 1）X3=（1 1 0） X4=（0 1 0）表示四种经营决策。于是为种群规模N=4的种群。可以用矩阵形式表示 编码方式 o 普通二进制编码算法的个体是一个由0和1组成的没有次序的二进制串； o 串长由变量的个数、精度、上下界决定； o 总串（长）所有变量的串（长）相加； o 一个变量对应的串长计算； o 解析一个变量串对应的实际值X min + 串的结果*精度； 目标函数值 o 根据用户输入的目标函数表达式计算； o 转为规范的目标函数值 ； 平移，使之全部为正数； scale，重新刻度，避免局部收敛； 初始化 o 按用户指定群体大小随机初始化每个个体，如： 复制 o 从群体中按某一概率成对选择个体放到个体样本池中，某个体被选择复制的概率与其适应度值成正比。 o 复制的概率计算方法： 。 o 本平台用的方法是轮盘赌(roulette wheel)模型方法。 杂交 o 杂交将被选中的两个随机个体的作为父母个体，按杂交概率判断是否进行交叉，如交叉，生成两个新的个体，交叉位置也是随机的，如： 变异 o 变异将新个体的基因串的各位按变异概率判断是否进行变异，如变异，其变度从0，1中选取，即由1变成0，由0变成1。 1、 选择选择也称复制或繁殖（Reproduction），它的主要思想是个体的选择概率正比于其适应度。下面介绍四种选择方法（或称选择策略）。（1） 轮盘赌法轮盘赌选择法(Roulette Wheel Selection)采用下式计算种群个体i的选择概率：个体i的适应度。：种群的总适应度。：个体i的选择概率。可见适应度大的个体，被选择的概率大，因此也称为基于适应度比例的选择策略。在第t代，设种群为P1，分别求和。产生0，1的随机数，求。求中最小的k，则第k个个体被选择。进行N次步骤，的操作，得到N个个体，成为第代的种群P2。（2） 期待值法期待值法（Expected Value Selection）采用下式求个体的期待值：将期待值四舍五入，得到个体i被选择的次数，从而种群由P1成为P2。（3） 两两竞争法两两竞争法（Tournamement）是指每次随机地在种群P1中取两个个体，选择适应度大的个体；若二者相同，只取其一，直到选出的个数为N，得到种群P2。（4） 保留最优法保留最优个体法（Elitist Preserving）是将这一代适应度高的个个体不进行交叉、变异操作，直接保留一代中。2、 交叉交叉是将选择后代的种群P2中的个体放入交配池（Mating Pool）随机地配对，称之为父代，按照交叉方式及交叉概率把成对个体的基因部分地交换，形成一代子代。交叉操作后，种群由P2变为P3。交叉方法包括一点交叉、多点交叉和均匀交叉。3、 变异突然变异是按设定的变异率，在种群个体的基因座上，用其对立基因进行置换（对于二进制位串），得到新的个体。4、 适应度及调整适应度就是适应环境的能力。在GA中用适应度f来描述个体的适应能力，f一定是非负的，即。寻优问题可归结为求目标函数的极小值或极大值问题。用GA寻优，可将目标函数进行变换，得到相应的，但必须满足两个条件：变换要保证。目标函数的优化方向对应于适应度的增大方向。（1） 极小值问题若目标函数为，可设（2） 极大值问题 若目标函数为，可设2、适应度的调整为了避免早期收敛（Premature Convergence），需要进行适应度的调整，在后期，即使保持了种群中个体的多样性，但若与很接近，则的个体与附近的个体被选中的概率相差无几，使选择趋于随机化，适应度减少，搜索趋于停顿，因此也需进行适应度的调整。（1） 线性调整式中，a， b：常系数。调整前后的关系应为：式中，分别为调整前后种群的平均适应度及调整后的最适应度，他们是为了平均使每一个个体在下一代有一个后代，并且限制最优个体到下一代的数量。为了避免以上问题，可采用如下算法：求种群平均适应度、最大和最小适应度若求解求解（2） 预处理（3） 乘幂调整五、模式定理模式（Schema）定理是由Holland提出的，是遗传算法的基础理论，是解释基本遗传算法（SGA）寻优机理的一种数学方法。模式也称积木块（Building Block），是描述位串子集的相似性模板，表示基因串中某些特征位相同的结构。遗传算法的基本流程遗传算法所涉及的五大要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。简单遗传算法的基本流程和结构如图：1） 选择编码策略，把参数集合X和域转换位串结构空间2） 定义适应值函数;3） 确定遗传算法策略，包括选择群体大小N，选择、交叉、变异方法，以及确定交叉概率、变异概率等遗传参数；4） 随机初始化生成群体P；5） 计算群体中个体位串解码后的适应值；6） 按照遗传算法策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；7） 判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回步骤6，或者修改遗传策略再返回步骤6。五、遗传算法与函数优化GA的典型应用之一就是求解最优问题。函数最优化问题，是指有制约地把目标函数最小化或最大化，一般可用下式表示：式中，x：变量xV。U：基本空间，解空间VU。V：U的部分空间的解空间。应用GA，结合最优化的要求，求解步骤如下：（1）设定解空间V与GA搜索空间S，选择VS之间的转换，也就是编码与译码方式。（2）目标函数及与适应度之间变换的模型。（3）确定GA算子以及有关运算参数。（4）在GA空间随机产生初始种群，译码至问题空间。（5）求最大适应度、平均适应度。（6）评价。若满足要求，是适应度，即为所求的解，计算结束；否则，至下一步。（7）在GA空间进行GA操作，生成下一代种群，译码至问题空间。（8）至步骤5。如一个简单的遗传算法SGA的参数由5项组成； N：种群的规模，一般N=20150。 ：交叉概率，。 ：变异概率，。 L：0，1二进制位串长度，即链长。 T：迭代结束代数。结束对参数集进行编码初始化种群P(t)GA操作确定实际问题参数集条件？种群P(t)种群P(t+1)评价群体（1） 位串编码；（2） 计算目标函数；（3） 函数值向适应值映射；（4） 适应值调整三个基本算子：1、 选择；2、 交叉；3、 变异；其他高级算子图1-1 简单遗传算子基本流程框图例3：实数向量函数最优化（1）解空间VGA搜索空间S之间的转换为：x=（x,y）s=（x,y）（2）用d-bit二进制代码表示（转换为十进制整数）x1，y1，二者关系的模型为（以x为例）：取d=10，则有（3）确定目标函数。本例是求目标函数z的极大值，因此适应度与z确定相同，f= z。（4）确定GA参数：（N=40，L=20，T=180，pc=0.5）（5）确定GA操作：轮盘赌+保留最优个体法选择，每代保留一个最优个体直接到下一代；两点交叉和变异率可变。（6）用线性调整法对适应值进行调整，抑制早期收敛。（7）在GA空间，随机产生初始种群：t=0，N=40，继续上述步骤六、GA的特点 GA不是一点搜索，而是在群体中一代一代搜索，取得最优解或准最优解。 GA 是对积木块操作，是在群体中并行进行的，这就是其内在的并行性。 GA运用随机搜索技术，对所需求解的问题无连续性、可微性要求。 GA迭代过程模拟了生物的遗传和进化过程，与达尔文生物进化论所述“适者生存，优胜劣汰”是一致的。 GA的不足SGA是早期的遗传算法，求解效率不高，也就是在搜索的快速性、全局收敛性方面还不能达到较好的效果。遗传算法与神经网络控制引言神经网络在控制中的应用面临两大问题，即神经网络拓扑结构的优化设计和高效的学习算法。由于遗传算法（GA）具有群体寻优和天然的增强式学习能力，使其具有全局性、并行性、快速性和自适应性，成为解决上述两大问题的有力工具，用于优化神经网络控制器与辨识器的结构权系和学习规则。GA是模拟生物的遗传和长期进化过程而发展起来的一种搜索和优化算法。它模拟生物界的生存竞争，优胜劣汰，适者生存的机制，用逐次迭代法搜索、寻优。由于遗传算法：对所要求的问题无连续性和无可微性要求，只需要知道目标函数的信息。借鉴生物遗传学研究成果，GA的寻优过程始终保持整个种群的进化，不是一点，而是整个群体的搜索寻优。一般认为GA是进化算法（EA, Evolutionary Algorithms）的三个组成部分之一。EA包括遗传算法、进化规划（EP, Evolutionary Programming）和进化策略（ES, Evolutionary Strategies）。2.1 遗传算法与神经控制神经控制就是由神经网络作为控制器与（或）辨识器