遗传算法基础知识

《遗传算法基础知识》由会员分享，可在线阅读，更多相关《遗传算法基础知识（19页珍藏版）》请在金锄头文库上搜索。

1、遗传算法(GENETIC ALGORITHM, GA) 一、遗传算法的特点：1、遗传算法的操作对象是一组可行解，而非单个可行解；搜索 轨道有多条，而非单条，因而具有良好的并行性。2、遗传算法只需要利用目标的取值信息，而无需梯度等高价值 信息，因而适用于任何大规模、高度非线性的不连续多峰函数的优化 以及无解析表达式的目标函数的优化，具有很强的通用性。3、遗传算法择优机制是一种软选择，加上其良好的并行性，使 它具有良好的全局优化和稳健性。4、遗传算法操作的可行解是经过编码化的(通常采用二进制编 码)，目标函数解释为编码化个体(可行解)的适应值，因而具有良 好的可操作性和简单性。二、遗传算法的发展与

2、现状遗传算法的产生归功于美国的Michigan大学的Holland在20世 纪 60 年代末、70 年代初的开创性，其本意是在人工适应系统中设计 的一种基于自然演化原理搜索机制。大约在同一时代，Foegl和 Rechenberg及Schwefel,引入了另两种基于自然演化原理的算法，演 化程序(evolutionary programming ) 和演化策略(evolution strategies). 这三种算法构成了目前演化计算(evolutionary computation)领域的三 大分支，它们从不同层次、不同角度模拟自然演化原理，以达到求解 问题的目的。Holland不仅设计了遗传

3、算法的模拟与操作原理，更重 要的是他运用统计策略理论对遗传算法的搜索机理进行了理论分析，建立了著名的Schema定理和隐含并行(implicit parallelism)原理，为遗传算法奠定了基础。遗传算法应用于函数优化始于De Jone的在 线(one-line)和离线(off-line)指标仍是目前衡量遗传算法性能的 主要手段。1、 遗传算法在神经网络、模糊系统和机器学习中的应用 神经网络的学习包含两个优化过程，分别是网络连接权重的优化和网络拓扑结构的优化。优化连接权重最著名的方法是Rumelhart提 出的基于梯度下降法的反向传播法(backpropagation,BP)。BP算法的 最

4、大弱点是局部极小问题和无法学习网络拓扑结构。作为一种通用性 和全局性良好的优化技术，遗传算法用于神经网络的训练就是很自然 的事情。遗传算法用于神经网络的学习可分为三个不同的层次：连接 权重的学习规则的学习。目前遗传算法已经广泛用于前向网络(feedward networks)、径向基网络(radial basis function networks)、Kohonen 特征映射及 Recurrent 网络等各种人工神经网络的训练与设 计中。演化神经网络(evolutionary artificial neural networks、作为一 种一般的自适应学习模型加以研究。被Zedeh称作软计算(

5、soft computing、的两大组成部分遗传算法与模糊系统的相互融合也是近年人们关注的话题。模糊系统是 对人类处理模糊性概念极其推理机制的模拟。最初，在模糊系统设计 中，推理方法的选取、隶属函数形状及参数的选取、相关权重的确定 以及规则的确定，均是由专家根据实际经验经验指定的。模糊神经网 络(fuzzy neural networks).遗传算法已成功应用于隶属函数形状与参 数优化，系统相关权重的优化以及推理规则的选取。此外，模糊集技 术也被用于遗传算法的某些 GA 的新型遗传算法，以达到改进经典遗 传算法的目的。大多数机器学习系统都有一个共同的特征，即具备对自身结构进 行调整的能力，从而

6、达到改进性能的、发现并利用有意义的概念，或 改进其内部知识结构的一致性和通用性。分类系统(classifer system) 是遗传算法与机器学习经典的生产系统(production system )相结合 的产物。遗传算法也用于导师概念学习(supervised concept learing)、 特征选取与重构及强迫学习(reinforcement learing)等机器学习领域。 2、遗传算法设计与执行策略遗传算法操作的是一群编码化的可行解，称作种群。它通过种群 的更新与迭代来搜索全局最优解。种群的迭代是通过选择、杂交和变 异等具有生物意义的遗传算子来实现的。在Holland的最初模型中

7、采 用的是二进制定长编码和固定种群，遗传算法的主要形式为比例选 择、单点杂交和位变异。近年的发展：( 1 )编码方法灰色编码可用于克服二进制编码映射的不连续问题(即欧氏空间 中邻近点的二进制编码在 Hamming 距离下并不邻近)。动态参数编码 (dynamic parameter encoding )提出是为了克服搜索效率与表示时间 精度间的矛盾，同时对克服过早收敛现象。此外，多值编码、实值编 码、区间编码、 Delta 编码等多种编码方法也各有优缺点。( 2)选择机制选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要 的因素。选择压(selective pressure)描述了选择机

8、制挑选种群中不同个 体做母体的概率大小的差异。选择压过大，会造成几个较好可行解(不 一定是近似全局最优解)迅速抢占了整个种群；选择压过小，则会使 算法呈现出纯粹的随机徘徊行为。秩选择、适应值函数的尺度变换均 是为了克服经典的比例选择所造成的选择压过大或过小而设计的。杰 出者选择(elitist selection)则通过无条件地保留每代种群中最优者而 克服选择下遗传算法不能依靠概率收敛到全局最优解的问题。杂交和 变异是遗传算法最具争议的两种机制。争论的焦点是：单点杂交、多 点杂交的优劣；杂交机制与变异机制的优劣。经典的观点强调杂交的 作用，而认为变异只是一个背景机制，并认为在杂交机制中强度最弱

9、 的单点杂交是最好的。强调杂交作用的观点是基于遗传算法中著名的 建筑块假设(building block hypothesis),而这一假设并末得到证明。 (3)杂交与变异机制除了关于世代 GA (generation GA)和稳定状态 GA(steady stateGA)的比较仍在研究。( 4 )执行策略的改进1、遗传算法与模拟退火算法的结合模拟退火(simulated annealing)是一种基于热力学理论的优化方 法，并有着完善的全局收敛理论。在遗传算法中已各种形式融入 模拟退火思想，从而使得遗传算法在理论上具有全局收敛次性。2、遗传算法与局部优化方法的结合把遗传算法与局部搜索方法有机

10、结合起来，是改进遗传算法性能 的一个卓有成效的方法。这种混合型遗传算法不但模拟了生物种 群的学习过程，而且事实上还模拟了种群中的个体在生命周期内 具有学习行为这一生物现象。这在生物学中称作 lamarckian evolution 和 baldwin effect。3、并行遗传算法(parallel genetic algorithm) 并行遗传算法是在遗传算法的实施中加入自然生物种群中的空 间因素，它的目的是可以在大规模并行机上运行，即使是序列实 施并行遗传算法，也可以克服经典遗传算法性能上的不足，从而 提高算法的效率。并行遗传算法大致分为两种：一种是岛模型(island model),称作

11、粗粒并行遗传算法(coarse-grained PGA);另 一种是细胞模型(cellular model),称为细粒并行遗传算法(finegrained PGA)。岛模型的实施方法是在几个独立按经典GA方法 运行的种群(称作子种群)中加入迁移(migration)因素；而细 胞模型的实施是在一个单一种群中，通过对经典整体性选择与杂 交机制的局部化来达到并行的目的。岛模型考虑的是种群的空间 结构，而细胞模型考虑的是一种群中个体的空间结构。4、共存演化遗传算法(cooperative co-evolutionary GA) 这一方法的思想是生物个体间不但有竞争，而且还具有合作行 为。CCGA通过

12、把复杂问题分解为数个子问题，通过代表这些子 问题的个体间既合作又竞争的演化过程，达到求解问题的目的。5、混乱遗传算法( messy genetic algorithm)三、遗传算法的基础理论研究目前的工作主要集中在遗传算法的欺骗函数(decetive function)研究。 所谓欺骗函数就是那些对遗传算法进行误导，使期错误地收敛到非全 局最优解状态的函数。1、遗传算法的马氏链分析种群马氏2、遗传算法的收敛理论四、遗传算法基本的基本概念选择、交叉、突然变异(Selection, Crossover, Mutation )组成， 称为遗传操作(Genetic Operator).GA空间中的个体

13、(Individual)就 是染色体，个体的基本构成要素是遗传基因(Gene)，个体上遗传基 因所在的位置称为基因座( Locus )，一组个体的集合称为种群(Population)o个体对环境适应能力的评价用适应度(Fitness)表示， 适应度大的个体，是优质个体，表征其在此环境下的生存能力强。定义1.1 (个体和个体空间)所谓L长度的个体X,即是长度为L的 0和1字符串，简称个体。L称为个体的链长，L长度的个体的全体 记为S = 0，1L，称为个体空间。按照遗传学的术语，个体也称为染 色体(chromosome)，个体的分量称为基因(gene)，分量的取值称为 等位基因( allele)

14、。例 1 对一个饭店的经营决策，考虑三个因素：价格、饮料与服务速度。 三个因素称为变量。对于价格，用0 表示价格高，用1 表示价格低； 对于饮料，用0 表示啤酒，用1 表示可乐；对于服务速度，用0 表示 慢，用1表示快。那么个体如：X= （0 1 1）的链长L=3, S=0, 13 有8个个体。定义1.2 （种群和种群空间）所谓N-种群是N个个体组成的集合（个 体允许重复），简称种群。N称为种群规模，称S N = X =（ X , X X ）, X e s （i N ）为 N-种群空12NI间。齐次种群例 2 （续例 1）如对于一个饭店的经营策略，一个个体表示一种经营 决策，则 X1=（0 1

15、 1），X2=（0 0 1）X3=（1 1 0） X4=（0 1 0）表 示四种经营决策。于是X = （X 1，X2，X3，X4）为种群规模N=4的种群。可以用矩阵形式表示X10111X2001X = =X4010 编码方式o 普通二进制编码算法的个体是一个由0和1 组成的没有次序的二进制串 o 串长由变量的个数、精度、上下界决定；o总串（长）=所有变量的串（长）相加；len = log 捕度o 一个变量对应的串长计算o解析一个变量串对应的实际值X = min +串的结果*精度； 目标函数值根据用户输入的目标函数表达式计算o 转为规范的目标函数值 ；平移，使之全部为正数；scale，重新刻度，避免局部收敛；初始化o按用户指定群体大小随机初始化每个个体，如:血如010100101叽01110110f2I叽01011111 复制o 从群体中按某一概率成对选择个体放到个体样本池中，某个体被选择复制的 概率与其适应度值成正比。尸2Mo复制的概率计算方法：Z 。o 本平台用的方法是轮盘赌(roulette wheel)模型方法。 杂交o 杂交将被选中的两个随机个体的作为父母个体，按杂交概率判断是否进行交叉，如交叉，生成两个新的个体，交叉位置也是随机的，如： 变异o 变异将新个体的基因串的各位按变异概率判断是否进行变异