（控制理论与控制工程专业论文）进化——专家控制系统的研究.pdf

谧传算法是一种新型高效搜索方法，其优良的寻优性能在机器 学习等许多学科的成功应用中得到了证实。近几年来，遗传算法在 控制领域中也得到了越来越广泛的应用，己成为提高系统自学习、 自适应能力的有力工具。 进化控制是根据将自然界存在的两种基本调节机制一进化与反 馈控制有机结合的思想，在遗传算法的基础上提出的一种新的智能 控制方法。该方法为复杂系统的控制提供了一种新的思路和视角。j 本文主要针对智能控制中主要存在的知识获取困难的问题，将 专家控制系统与进化控制相结合，提出了进化一专家控制系统，并 给出了控制器的具体设计方案。该系统能够在没有先验知识的情况 下，自动地获取控制规则，对对象进行控制。另外，在原系统的基 础上增加了前馈补偿，提高了系统的抗干扰能力。 嗵过对大量的工业对象的仿真表明，系统能较快地获取规则， 并且该控制器具有较好的动态特性和鲁棒性弋 关键词：遗传算法进化控制进化一专家控制 第i 页 奎墨里三查堂堡圭堂垡笙茎 a b s t r a c t g e n e t i ca l g o f i t h m ( g a ) i san e w p o w e r f u ls e a r c ht e c h n i q u e i t sh i g h s e a r c h p e r f o r m a n c eh a sb e e np r o v e di nm a n ya p p l i c a t i o n s i nt h ef i e l do fm a c h i n e l e a r n i n ga n d s oo i lg ah a sb e e nu s e di nt h ea u t o n l a t i o nf i e l dm o t ea n dm o r e w i d e l y i nt h e r e c m l y a n di th a sb e c o m et h e p o w e r f u lt o o lw h i c h c a n i m p r o v et h e s y s t e mp 砌o r m a n c eo f s e l f - l e a r n i n ga n ds d f - a d a l a i v e b yi m m i g r a t i n g t w oo f t h eb a s i cw g u l a t i n gm e c h a n i s mi nt h en a t u r e it h a ti s ， e v o l u t i o na n df e e d b a c ki n t oo n eo r g a n i cc o n t r o lp a r a d i g m an e w i n t e l l i g e n t c o n t r o lm e t h o dt h a tb a s e do ng ah a sb e e n p r o p o s e d , t h a ti s ，e v o l u t i o n a r yc o n l r 0 1 i tb r i n g s 叩an e w i d e o l o g y t ot h er e s e a r c ho f c o m p l e x s y s t e m c o n t r o lp r o b l e m i n t h i s 牟i p l 匮e v o l u t i o n a r y - e x p e r t c o r m f ls y s t e mh a sb e e n p r o p o s e d a c c o r d i n gt ot h ep r o b e n lo f t h ed i f f i c a f l t yi nk n o w l e d g ea c t u i s t t i o nt h a th a v e e x i s t e dg e n e r a l l yi ni n t e u i g c a tc o a t r o l , a n dt h ec o n c r e t ed e s i g n h e m eo ft h e c o n t r o l l e ra t eg i v e n t h es y s t e mc a n a c q u i r ec o n t r o lr u l e sa u t o m a t i c a l l y0 1 1t h e c o n d i t i o n so f n oo q 田z r ta 甲盯i 魄嘲h a v eb e e np r o v i d e d m o t e o v e r , t t 黼l f o r w a r d c o m p e n s a t i o nh a sb e e na d d e d t ot h es y s t e n lt oi m p r o v et h es y s t e m a b a i t yo f a n t i j a m m i n g t h es i m u l a t i o n so f m a n y i n d u s t r i a lo b j e c t ss h o wt h a tt h ec o n t r o l l e rh a sa g o o dd y n a m i c c h a r a c t e r i s t i ca n dr o b u s t n e s s k e y w o r d ：g e n e t i ca l g o r i t h m ；e v o l u t i o n a r yc o n t r o l ；e v o l u t i o n a r y - e x p e r t c o n t r o l 第赶页 太原理工大学硕士学位论文 第一章绪论 长期以来，自动控制已对整个科学技术的理论和实践做出了重要 贡献，并为人类社会带来了巨大利益。然而，现代科学技术的迅速发 展和重大进步，对控制和系统科学提出了更新、更高的要求，自动控 制理论和工程正面临新的发展机遇和严峻挑战。传统控制理论，包括 经典反馈控制、现代控制和大系统理论等，在应用中遇到了不少难题 它难于表达和处理有关被控对象的一些不确定信息，不能利用专家的 经验知识、技巧和直觉推理，所以不能对复杂系统进行有效控制。而 解决这些问题的出路之一就是实现控制系统的智能化。其中优化与自 适应等问题是控制系统智能化的主要研究方向之一。 遗传算法( g a ) 作为一种新型的搜索算法，近年来得到了人们越 来越广泛的重视。同传统的基于微积分和穷举法等算法相比，g a 是 一种成熟的具有高鲁棒性和广泛实用型的全局优化方法。由于g a 具 有不受问题的性质( 如连续性、可微性) 的限制，能够处理传统优化 算法难以解决的复杂问题等优点，显示了它在解决控制系统优化方面 的巨大潜力。 本章主要在引用大量文献的基础上，概括介绍了遗传算法在控制 领域中的一些应用现状，并在此基础上，提出了本文的理论依据和学 术思想。 1 1 遗传算法在控制理论发展中的贡献 遗传算法是新兴起的智能计算技术，是一种借鉴生物界自然选择 和自然遗传机制的高度并行、随机自适应搜索算法，具有快速地搜索 复杂、高度非线性和多维空间等特点。其优良的寻优性能，显示了它 筹i 页 太原理工大学硕士学位论文 在解决控制系统优化方面的巨大潜力，因而引起控制领域的极大关注， 近年来在控制领域，g a 在p i d 控制、线性和非线性、最优、鲁棒、 自适应、模糊、神经网络、系统辨识和机器人控制等方面得到了广泛 的应用。 根据近几年遗传算法的文献，将遗传算法在控制领域的应用分为 以下几部分。 l 系统辨识 系统辨识是控制系统设计的基础，有许多有效的方法。但这些技 术所处理的绝大多数都是参数的线性模型，并且基于搜索空间是连续 和可微的假设。目前在线辨识方法都是离线方法( 如最小二乘法、极 大似然法等) 的递归实现。这些递归方法本质上都是使用梯度技术的 局部搜索方法，在搜索空间不可微或参数非线性时，这些方法不易找 到全局最优解。另外传统的辨识方法往往要经历从确定结构到确定参 数的多次反复。 遗传算法不需要假设搜索空间是连续或可微的。在每一代，它同 时搜索参数空间的不同区域，同时处理搜索空间的多个点，增加了搜 索到全局最优解的可能性。g a 为非线性系统的辨识提供了一种简单而 有效的方法。k r i s t i n n 阳将g a 分别用于连续和离散时间系统的辨识， 并将辨识结果用于极点配置自适应控制器的设计。它对遗传辨识和传 统辨识方法进行了比较研究，说明了基于遗传辨识的自适应控制方法 具有较为突出的优点。 t a n 和l i 以一个实验室内的液位控制实验装置为例研究了时域 系统的遗传辨识方法。他们将模拟退火算法用于g a 的精细调整，提高 了算法的收敛速度。 a l o n g e 啪3 描述用g a 进行感应电机参数辨识的实验研究，辨识结 囊瓿； 第2 页 赶原理工大学硕士学位论文 果的输入输出特性与实际系统非常吻合，他指出遗传算法可以同时估 计库仑摩擦力，便于补偿。黄炯阳7 3 等讨论了g a 在线辨识的实现问题， 研究结果表明g a 能在线辨识时滞并收敛到全局最优。 2 最优控制 许多控制问题都可以归结为求解对应不同系统状态的一组最优控 制作用，传统的寻优方法通常都是沿着指标函数的梯度方向搜索，普 遍存在对输入初值敏感、迭代收敛速度慢、容易陷入局部最小等缺点。 遗传算法在最优控制方面也得到了广泛的应用。k r i s h n a k u m d “】 将g a 设计的两个反馈控制系统与传统设计方法的结果进行了比较， 说明g a 的结果是好的。m i c h a l e w i c z t s 5 1 应用改进的浮点数编码g a 对 离散时间最优控制问题进行了研究。陈根社提出用g a 求解r i c c a t i 方 程，并将该方法用于飞船控制系统的最优设计之中。g e t 嘲将g a 与 l y a p u n o v 方法相结合，设计出了稳定的闭环系统，同时又达到了满意 的性能指标。王豪和邵惠鹤提出了一种基于遗传算法和受控随机搜 索的系统优化策略，可用于解决较大规模的系统优化问题。 3 非线性系统控制 在控制系统设计中，许多控制问题可以包括在优化的框架内，通 常这种优化任务需要在多维空间中同时确定若干参数。由于实际问题 往往带有严格的非线性，同时指标函数可能既不连续又不可微。遗传 算法为非线性控制系统的优化提供了一种有效的途径。 甘俊英【7 4 1 提出种基于遗传算法的非线性控制系统参数优化方 法。金希东旧针对遗传算法的早熟问题，提出进一步模拟自然界中的 灾变现象，以提高遗传算法的性能，并将遗传灾变算法应用于非线性 系统p i d 控制器的参数优化。陈根社呻1 将g a 用于综合飞行控制系统 的参数设计中，在某高速歼击机数学模型的基础上，采用g a 自动调 第3 页 太原理工大学硕士学位论文 节参数获得了满意的性能。 因为g a 不需要指标函数的微分，所以基于遗传算法和性能分析 的设计自动化方法，能够考虑实际系统的许多性能要求，并可直接设 计非线性对象的控制器，而不需要先将对象进行线性化。实践证明这 是控制系统设计的一种有效方法。 4 鲁棒控制器设计 自从1 9 9 1 年m u r d o c k 应用g a 对控制系统的鲁棒稳定性进行分析 以来，g a 在直接鲁棒控制器设计、h m 次优控制器设计、h m 权函数 设计等方面得到了应用。 传统日。控制器的阶次要远高于被控对象的阶次，在实际工程应用 不易实现。为了缩短日。控制建论与实际工程应用的差距，c h e n t 8 9 1 研 究了具有参数摄动和外部干扰系统的确定结构控制器的日。优化设计问 题，设计过程和系统性能表明该遗传搜索方法非常适用于实际工程应 用。基于同样的思想，c h e n t “1 研究用g a 调节p i d 控制器参数以获得 h 。h ，优化性能。 d a k e v t ”1 在回路整形过程中应用g a 寻找多输入多输出鲁棒控制器 的适合的权函数矩阵。d o n h a i ”1 也研究了鲁棒控制器设计中权函数的优 化问题。 特征结构配置是一种鲁棒控制系统设计方法。对于多变量系统， 无论是连续还是离散控制系统的品质很大程度上取决于系统的特征结 构配置。p a t t o n t ”1 将一种混合策略应用到飞机的纵向控制系统特征结构 配置设计中，用实值表示的g a 最小优化闭环系统的灵敏度函数。 5 模糊控制系统 模糊推理方法是控制系统设计的有力工具之一。这种基于规则的 系统将模糊语言变量引入规则集合中，用以对人的经验方法建模。影 痞 第4 页 太原理工大学硕士学位论文 响模糊逻辑控制器性能的因素有很多，如规则的完整性、模糊子集的 定义、隶属函数的形状和参数、模糊推理机制和反模糊化方法等。在 大多数情况下，这些因素都需要由领域专家的经验确定。模糊规则的 确定和调整通常时非常困难和耗时的，而且模糊控制器的规则和隶属 函数的选取由很大程度的主观性，当输入、输出数目和语言变量划分 的等级增大时，模糊规则的数目是以级数的平方关系迅速增加，这都 给模糊控制器的设计带来了困难。 为了解决这一困难，许多学者利用g a 进行模糊系统的辅助设计 和自动化设计。许多研究工作可归纳为图1 1 所示的遗传模糊控制框 图，他们完全或部分采用这一框架，利用g a 调整规则集合、调整隶 属函数、或两者同时调整。 图1 - 1 遗传模糊控制系统框架 利用g 调整规则 由于模糊控制在噪声条件下能够很好地工作，因此精调最优性能 第5 页 太原理工大学硕士学位论文 的f l c 集合具有重要意义。f r e e m a n 提出应用g a 调整模糊集合的概 念。p e d r y c z t 驯用遗传算法优化模糊关系矩阵，获得了用关系矩阵描述 的模糊关系结构。张晓缋【2 8 1 提出用g a 解决模糊控制中模糊矩阵的抽 取和过滤问题。c h i n t 2 ”用g a 优化模糊规则集，将无用的规则删除， 改善有用的规则，实现了从基于知识的模糊规则子集中寻找最少数量 的规则以使f l c 的性能和结构达到最佳化，他以倒立摆为例，给出了 使用原始规则集和简化规则集对系统进行控制的效果比较。w a n g t 4 1 1 通 过辨识系统的输入输出数据，以g a 自动抽取模糊规则，这种方法 同时减少模糊规则的数目。程启明【7 5 】提出了一种规则自校正模糊控制 器，使系统具有一定的学习功能。 利用g 调整隶属函数 由于隶属函数代表了领域专家对模糊语言变量的理解，隶属函数 的形状和参数对模糊控制系统具有很大的影响，因此优化隶属函数是 提高系统性能的一种有效途径。b u c k l e y t ”1 指出可以先确定隶属函数的 形状然后对这些形状的参数进行优化。p a t r i c k t 4 6 研究了用g a 调节t s 模糊模型隶属函数参数的优化能力。张毅研究了用g a 对模糊变 量的各个子集的隶属度函数进行寻优，给出了二级倒立摆的设计例子 和实际控制曲线。 同时调整 l s h i g a m i l 4 8 和l i n k e n s t 4 9 用g a 同时调整隶属度函数和规则实现了 结构最小、性能最优的模糊神经网络控制器。张彤i ”1 将g a 与梯度算 法结合用于模糊逻辑系统的辨识问题，取得了较好的效果。d a n u t a 5 0 】 不但用g a 同时调整隶属函数和规则，而且将调整结果用梯度方法进 一步优化。 6 神经网络控制 第6 页 太原理工大学硕士学位论文 遗传算法在神经网络优化方面的应用，是近年来的一个非常重要 的研究方向。由于神经网络所具有的能充分逼近任意复杂的非线性关 系、很强的鲁棒性和容错性、大规模并行性和能学习与适应严重不确 定系统的动态特性等优势，从而引起了控制领域的极大关注。神经网 络应用于控制领域，采用最普遍的是多层前馈神经网络模型，它具有 广泛的从输入到输出的映射能力。但由于采用反向传播算法常常需要 很长的时间才能收敛，而且不可避免地会遇到局部极小问题。 同优化模糊控制系统类似，用g a 对神经网络进行优化可以分为： 优化网络结构、优化权系数、和同时优化结构和系数等三个方面。s t e v e t 5 9 1 将g a 应用于神经网络中，通过g a 对神经网络的权值进行训练。刘 宝坤 6 0 1 研究了用改进的g a 来优化神经网络辨识器和控制器的参数， 以期提高控制系统的性能。廖俊【6 2 】应用先验指是确定参数变化范围， 针对t s 模糊模型的神经网络表示，用g a 进行模糊神经网络权值的 优化。王强、邵惠鹤i 删采用遗传算法生成前向神经网络，可同时得到 网络的最佳结构和权值。 7 实时和自适应控制 将遗传算法用于实时控制所遇到的两个最主要的问题是f 每一 代的执行时间是否能够足够短；是否能保证在每一代产生稳定的控 制律。执行时间问题可以通过并行g a 、增量g a 、ug a 部分解决。 增量g a 每一代只产生一个或两个新个体，因而可以缩短每代的循环 时间以及内存需求，但是可能产生不了满意的新个体。t lg a 使用很 小的种群，能产生更多的个体，但缺乏基因的多样性。保证每一代都 形成满意的控制律是一个更难于解决的问题。 尽管如此，仍然涌现了一些基于g a 的成功策略。遗传自适应控 制一般有两种方案：一种方案使用g a 作为对象参数估计器，而使用 极点配置等方法在线调整控制器，文献】就属于这种情况；另一种方 第7 页 太原理工大学硕士学位论文 案是由传统方法辨识系统状态，使用g a 对控制器进行在线优化，以 构成一类性能逐渐优化的自适应控制器，或者干脆不辨识而是直接应 用某种性能准则来在线优化控制器的结构和参数。p o r t e 一9 4 】研究了g a 调整数字p i d 参数，指出g a 比传统的约束优化技术更容易实现。 z u o ”1 采用同样的多变量数字p i d 控制器，研究了大规模空间飞行器 的姿态控制和动量管理系统的自适应控制策略。其算法由带有遗忘因 子的最小二乘构成的快速在线递推辨识器和g a 在线调节控制参数矩 阵的遗传算法调节器两部分组成。实验结果表明系统对于较大转动惯 量变化具有良好的鲁棒稳定性和设定点跟踪性。 g a 的另一类在线应用是模糊控制。k a r r 展示了如何将g a 用于动 态系统的自适应和非自适应模糊控制器。在其应用中，控制规则趋于 保持不变，g a 被用来优化控制器的隶属度函数，以适应当前工作环 境的变化。相反，l i n k c n s 4 ”将隶属度函数的优化离线进行，而采用模 糊分类系统在线调整规则集合。他们的方案不需要显式地辨识对象模 型，通过规则集合满足系统动态变化实现自适应控制。 此外，遗传算法在多目标优化等方面也已有了许多研究及成功的 应用。 遗传算法是一种非常有效的优化求解方法。对于控制领域中某些 控制结构和控制作用的求取，g a 可以提供比传统优化方法更快更好 的结果。可以说将g a 与c a d 软件包智能连接而进行系统建模和控制 器的自动化设计及参数优化是一种行之有效的新方法。使用g a 进行 控制系统优化的主要缺点是需要很大的计算量，但这一切都是由计算 机辅助设计完成的。由于提高了设计自动化程度，因而基于g a 的控 制系统设计仍不失为复杂系统设计的一种有力工具。 瓢一 第8 页 _ 太原理工大学士学位论文 1 2 立论依据和主要工作 1 21 本文的立论依据 智能控制不仅无需精确的数学模型，而且在控制中要具备为完成 给定目标而进化、主动学习和适应的机制和能力。进化计算从大自然 的进化中受到启迪，是一种独特的优化方法。特别是近十几年来，被 广泛用于优化组合、生产调度、图像处理、机器学习等各个领域，其 优良的寻优性能也得到了认可。在控制领域，进化计算特别是其中的 遗传算法在神经网络权值、模糊控制器的隶属函数、模糊规则等的优 化与学习中均取得了良好的效果，在上一节我们己介绍了遗传算法在 控制领域中的许多成功应用，进化计算为智能控制注入了新的活力。 将进化计算理论与传统的反馈控制理论相结合，诞生了进化控制， 可以很好的弥补现有智能控制方法的不足，使机器具有更加自主的学 习能力。在此思想上，本文对进化控制进行了深入的探讨，并且针对 智能控制中知识学习的“瓶颈”问题，提出了进化一专家控制系统， 此系统可以在没有任何先验知识的情况下，通过完全的自学习而得到 一套完整、并且有较好控制效果的控制规则。 1 2 2 本文的主要内容及内容安排 本文首先介绍了遗传算法在控制理论发展中所作的贡献，接着， 简要介绍了遗传算法的一些基础知识与理论，指出了其优良的寻优性 能。进而，介绍了进化计算与控制理论的结合一进化控制的思想，并 与专家控制系统结合形成进化一专家控制系统。在系统的设计中，根 据系统的特征对系统中遗传算法部分进行了改进：采用浮点编码方式； 采用双层评价方式；增加诸如移民、合并等遗传算子等等。最后，通 过进行仿真研究来对系统的各项性能进行论证。 本章主要介绍了遗传算法近几年来与控制领域的关系，指出遗传 第9 页 太原理工大学硕士学位论文 算法在控制系统研究中的重要作用，并在此基础上提出了本文的理论 根据。 第二章首先阐述了进化计算和遗传算法的基本知识，随后着重介 绍了遗传算法的三个重要的数学理论：模式定理、隐含并行性、收敛 性。这些定理与性质对于遗传算法的分析起着重要的作用。 第三章首先提出了进化控制的概念，并对进化控制的思想与理论 作了简要的分析，接着在对专家控制系统进行分析的前提下提出了解 决知识获取问题的方案：将进化控制入专家控制系统，用以解决专家 控制系统中知识获取的“瓶颈”问题，并给出进化一专家控制系统的 结构。 第四章介绍了s a m u e l 系统的运行过程，在此系统的启发下，给 出了进化一专家控制器的设计方案：将进化控制与专家控制有机地结 合在一起，根据给定的任务与目标，完成对对象的控制。 第五章通过大量的仿真实例，论证了此系统的可行性、鲁棒性等 特点，并且针对系统抗干扰性差的特点，引入了前馈控制方案，提高 了系统的抗干扰性。 第六章对本文的工作作了总结，提出了今后需进一步研究的问题。 & “ 第1 0 页 奎垦堡三查堂堡主兰堡丝兰 第二章进化计算及遗传算法 2 1进化计算 进化计算( e c - - e v o l u t i o n a r yc o m p u t a t i o n ) 是一门新兴学科，它 是研究仿照生物进化自然选择过程所表现出来的优化规律和方法，对 复杂的工程技术领域或其他领域提出的而传统优化理论和方法又难以 解决的优化问题，进行优化计算、预测和数字寻优等方面的一种计算 方法，这类算法又称进化算法 总的来说，基于对生物进化机制的模仿，共产生了三种典型的优 化计算模型，它们分别是： ( 1 ) 遗传算法( g a - - - g e n e t i ca l g o r i t h m ) 遗传算法是建立在自然选择和自然遗传学机理基础上的迭代自适 应概率性搜索算法。该算法最早是由美国密执安大学j h h o l l a n d 在 1 9 7 5 年发表的论文“自然和人工系统的适配”中提出的。同年，在该 校的k e n n e t h 的博士论文中，将g a 用于解决优化问题。目前，遗传 算法正在受到人们极大的关注。 ( 2 ) 进化规划( e p - - e v o l u t i o n a r yp r o g r a m m i n g ) 进化规划方面的论文是美国j e l a w r e n e e 等人在1 9 6 6 年发表的， 这种方法主要用于预测和数值优化计算。 ( 3 ) 进化策略( e s - - - e v o l u t i o n a r ys t r a t e g y ) 进化策略主要是研究经验性寻优过程，以便获得一个最优策略。 这方面的研究工作是由德国学者i r e c h e n b e r g 等人在1 9 7 3 年最先提出 的，近期这种算法在计算机中获得了较多的应用。 第1 l 页 太原理工大学硕士学位论文 遗传算法、进化策略、进化规划这三种典型的进化算法都以自然 界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以三 者之间有较大的相似性，它们在计算中的迭代过程大体相同，都包含 了编码、复制、交叉、变异等过程，在交换和变异方面都是随机的， 一般发生率取较低值。另一方面，这些方法各自有不同的侧重点，但 它们都能产生一种鲁棒性较强的计算机算法，适用面较广。随着各种 进化计算方法之间相互交流的深入，以及对各种进化算法机理研究的 进展，使得它们之间的区别正逐渐减小，所以从总体的含义上统称它 们为进化计算。其中遗传算法最为活跃，也反映出遗传算法在进化计 算中占有重要的地位。 2 2 遗传算法简介 遗传算法的常用形式是g o l d b e r g 提出的【2 2 】。遗传算法是从一组随 机产生的初始解，称为“群体( p o p u l a t i o n ) ”，开始搜索过程。群体中 每个个体是问题的一个解，称为“染色体( c h r o m o s o m e ) ”。这些染色 体在后续迭代中不断进化，称为遗传。在每一代中用“适应度( f i t n e s s ) ” 来测量染色体的好坏。生成下一代的染色体，称为“后代( o f f s p d n g ) ”。 后代是由前一代染色体复制、交叉、变异形成。经过若干代后，算法 收敛于最好的染色体，它可能就是问题的最优解或次优解。 遗传算法的一般结构可描述如图2 1 。 第1 2 页 太原理工大学硕士学位论文 图2 - 1 遗传算法的一般结构 2 3 遗传算法的特点 为解决各种优化问题，人们提出了各种各样的优化算法，如单纯形 第1 3 页 太原理工大学硕士事位论文 法、梯度法、动态规划法等。这些优化算法各有各的长处，各有各的 适用范围，也各有各的限制。遗传算法是一种可用于复杂系统优化计 算的鲁棒搜索算法，与其它一些优化算法相比，它由下述几个特点： ( 1 )遗传算法是对参数的编码进行操作，而不是对参数本身； ( 2 )遗传算法是从许多初始点开始并行操作，而不是从一个点 开始。因而可以有效地防止搜索过程收敛于局部最优解； ( 3 )遗传算法通过目标函数来计算适配值，而不需要其它的推 导和附属信息，从而对问题的依赖性较小； ( 4 )遗传算法使用概率的转变规则，而不是确定性的规则： ( 5 )遗传算法在解空间内不是盲目地穷举或完全随机测试，而 是一种启发式的搜索，其搜索效率往往优于其它方法； ( 6 )遗传算法对于待寻优的函数基本无限制，它既不要求函数 连续，更不要求函数可微，既可是数学解析式所表达的显函数，又可 是映射矩阵甚至神经网络等隐函数，因而应用范围较广； ( 7 ) 遗传算法具有并行计算的特点，因而可通过大规模并行计 算来提高计算速度。 2 4 遗传算法的发展 遗传算法和遗传规划的历史过程，大致可分为三个时期：萌芽 期、成长期和发展期。 ( 1 ) 萌芽期( 5 0 年代后期7 0 年代中期) 早在5 0 年代后期及6 0 年代初期，一些生物学家就着手采用电子 计算机模拟生物的遗传系统。例如，美国a s f r a s e r 于1 9 6 0 年为了建 立生物的表现型方程，用3 组5 位( 共1 5 位) 长的o 一1 字符来表示 ! ”孵 第1 4 页 太原理工大学硕士学位论文 方程的三个参数。 1 9 6 2 年，美国jhh o l l a n d 教授在研究适应系统时，提出系统本 身与外部环境的相互作用与协调，涉及到进化算法的思想。1 9 6 8 年他 又提出模式理论，它是遗传算法的主要理论基础。 第一次正式使用遗传算法这个术词是出现在1 9 6 7 年美国 j d b a z a a 关于博奕论的论文中。他采用复制、交换、突变等手段 研究国际象棋的对奕策略。 1 9 7 5 年，美国芝加哥大学j h h o l l a n d 教授的专著自然界和人 工系统的适应性( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a l s y s t e m ) ) ) 2 1 】问世， 比较全面地介绍了遗传算法，人们常常把这一事件视作遗传算法得到 正式承认的标志，h o l l a n d 也被视作遗传算法的创始人。 ( 2 ) 成长期( 7 0 年代中期到8 0 年代末) 在7 0 年代末至8 0 年代初，许多研究工作者从事遗传算法的研究。 1 9 8 7 年，美国的d l a w r e n c e 总结人们长期从事遗传算法的经验，公 开出版遗传算法与模拟退火( g e n e t i ca l g o r i t h ma n ds i m u l a t e d a n n e a l i n g ) 一书，以论文集形式用大量的实例介绍遗传算法的使用 技术。1 9 8 9 年，作为j h o l l a n d 教授的学生，d e g o l d b e r g 博士出版专 著遗传算法一搜索、优化及机器学习( g e n e t i ca l g o r i t h m s - - i n s e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ) ) 【，全面、系统地介绍 了遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法 的基础教科书。 至此，遗传算法已广泛用于生物、工程技术、运筹学、计算机科 学、图像处理、模式识别、社会科学等领域。 ( 3 ) 发展期( 9 0 年代) 9 0 年代以后，遗传其法不断地向广度和深度发展。1 9 9 1 年， 第1 5 页 太原理工大学硕士举位论文 i ) l a w r e n c e 公开发行遗传算法手册( h a n d b o o k o fg e n e t i c a 1 9 。r io h m s ) 】一书，该书除了介绍遗传算法原理和实例外，还介 绍用l i s p 语言表达的遗传算法和用c 语言编写的遗传算法计算机程 序。1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优化程序自动生成， 提出了遗传编程的概念口1 ，并将此方法应用于人工智能、机器学习、 符号处理等方面。 自1 9 8 5 年以来，已经召开了多次遗传算法的学术会议，为研究和 应用的思想、进展和经验提供了国际交流的机会，并促进了理论与实 际工作者之间的相互理解和合作，其中主要会议有：i c g a ( i n t e r n a t i o n a l c o n f e r e n c eo ng e n e t i ca l g o r i t h m s ) 、p p s n ( i n t e m a t i o n a lc o n f e r e n c eo n p a r a l l e lp r o b l e m s o l v i n g f r o m n a t u r e ) 、f o g a ( w o r k s h o p o nf o u n d a t i o no f g e n e t i ca l g o r i t h m ) 、i c e c ( i e e ei n t e r n a t i o n a lc o n f e r e n c eo n e v o l u t i o n a r y c o m p u t a t i o n s ) 等。一些杂志，如e v o l i l t i o n a r yc o m p u t a t i o n ( d ej o n g 主 编，m i tp r e s s 出版，1 9 9 3 年开始发行) ，为遗传算法理论出版提供了 论坛。许多著名的网站，如g a a r c h i v e ( h t t p ：w w w , a i c n r l n a v y m i l g a l i s t ) 笠，更为遗传算法的探讨与研究提供了广阔的天地。 2 5 遗传算法的基本实现技术 遗传算法的实现主要是通过编码、计算适应度函数及遗传操作等实 现的。 25 1 编码 编码是应用遗传算法是要解决的首要问题，它决定了个体的染色 体排列形式以及个体从搜索空间的基因型变换到解空间的表现型时的 解码。d ej o n g 曾提出两条操作性较强的实用编码原则【3 1 1 ： l 原则一l 应使用易于产生与所求问题相关的且具有低阶、短定义 莲曩 第1 6 页 太原理工大学硕士学位论文 长度模式的编码方案。 【原则二l 应使用能使问题得到自然表示或描述的具有最小编码字 符集的编码方案。 下面是一些较常用的编码方案。 ( 1 ) 二进制编码法。它使用的编码符号集是由二进制符号0 和l 所组成 的二值符号集f o ，l ，二进制编码方法以其具有下述特点而成为最常 用的编码方法：编码、解码操作简单：遗传操作便于实现；易于利用 模式定理对算法进行理论分析。 ( 2 ) 格雷码编码法。此方法为连续两个整数对应的编码值之间仅有一个 码位是不同的。格雷编码法可以增强遗传算法的局部搜索能力。 ( 3 ) 浮点数编码法。个体的每个基因值用某一范围内的一个浮点数表 示，个体的编码长度等于其决策变量的个数。编码所使用的是决策变 量的真实值。此方法适于表示范围较大的数以满足较高的精度要求； 提高运算效率；便于应用专门知识。 此外，还有符号编码法、多参数编码法等等。 2 5 2 适应度函数 度量个体适应度的函数称为个体的适应度。它是群体进化的依据。 遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到 下一步的有关搜索信息。而对目标函数的使用是通过评价个体的适应 度来实现的。评价的一般过程为：对仓体编码串进行解码处理后， 可得到个体的表现型；由个体的表现型可计算出对应个体的目标函 数值；由目标函数值按一定的转换规律求出个体的适应度。 2 5 3 复制算子 复制操作( 选择操作) 是建立在对个体适应度进行评价的基础上。 第1 7 页 太原理工大学赢士孚位论文 丰要目的是为了避免基因缺失、提高全局收敛性和计算效率。常用的 有： ( i ) 比例选择。是一种回放式随机采样的方法。基本思想是1 ：各个体 被选中的概率与其适应度大小成正比。即： 仇：形 o = 1 ，2 ，盯) ( 2 1 ) f i l = l 其中，n 为群体大小，e 为个体i 的适应度，风为个体f 被选中的概率。 这种算法是复制操作中的最基本算法，但是由于随机操作的原因，误 差比较大。 ( 2 ) 无放回随机选择。它的基本思想是根据每个个体在下一代群体中的 生存期望值来进行随机选择运算【3 2 】：第i 个个体被选中的概率同样如式 ( 2 1 ) 所示，如果它参与交叉运算，则在下一代中生存期望数减小， 反之，增加。此方法可降低一些误差，但操作不太方便。 ( 3 ) 排序选择。它的基本思想是：对群体中所有个体按其适应度大小进 行排序，基于此排序再采用比例选择的方法来分配各个个体被选择的 概率【”】。 另外还有确定式采样选择、无回放余数随机选择等选择方法。 2 5 4 交叉算子 交叉是遗传算法中产生新个体的主要方法。其设计包括以下两方 面内容：如何确定交叉位置。如何进行部分基因交换。 ( j ) 单点交叉。是指在个体编码中只随机设置一个交叉点，然后在该点 相互交换两个配对个体的部分染色体【3 l l 。是最常用的交叉算子。这种 算子破坏个体性状或降低个体适应度的可能性最小。 莲i 第1 8 页 太原理工大学硕士学位论文 ( 2 ) 双点交叉与多点交叉。双点交叉是指个体编码串中设置两个交叉 点，然后再进行部分基因交换【3 4 1 。将单点交叉与双点交叉的概念予以 推广，便可得到多点交叉的概念f 3 l 】。 ( 3 ) 均匀交叉。是指两个配对个体的每一个基因座上的基因都以相同的 概率进行交换，从而形成两个新个体。属于多点交叉的范畴。 交叉的位置越多，产生新个体的能力越强，但个体结构被破坏的 可能性也越大，较好的模式很难被保存。 2 5 5 变异算子 变异算子的作用主要是改善遗传算法的局部搜索能力以及维持群 体的多样性。其设计包括以下两方面内容：如何确定变异点的位置。 如何进行基因值替换。 ( 1 ) 基本位变异。这是最简单最常用的变异方法。是指对个体编码串中 以变异概率p 。随机指定的某一位或某几位基因座上的基因值作变异运 算i3 1 】。 ( 2 ) 均匀变异。是指分别用符合某一范围内均匀分布的随机数，以某一 小概率来替换个体编码串中各个基因座上的原有基因值】。 ( 3 ) 高斯变异。是改进遗传算法对重点搜索区域的局部搜索性能的一种 操作方法。所谓高斯变异操作是指进行变异操作是，用符合均值为、 方差为盯2 的正态分布的一个随机数来替换原有的基因值【3 6 】。 其余变异方法还有边界变异、非均匀变异等。 编码方法以及各遗传算子的选择要根据具体情况，根据每种方法 的特点，具体分析，具体应用。 2 6 遗传算法的数学理论 第1 9 页 太原理工大学硕士学位论文 2 6 1 模式定理 2 6 1 1 模式 【定义2 1 】模式表示一些相似的模块， 有相似结构特征的个体编码串的一个子集。 例如，模式h = 1 1 + l 描述了长度为5 ， “1 ”的所有字符串的集合。 它描述了在某些位置上具 且在位置1 、2 、5 取值为 一般地，定义在含有 个基本字符的字母表上长度为，的字符串中 的模式共有( + 1 ) 。个，在长度为，、规模为 的二进制编码字符串群体 中，一般包含有2 7 到玎2 。个模式。 遗传算法的本质是对模式所进行的一系列运算，即通过选择算子 将当前群体中的优良模式遗传到下一代群体中，通过交叉算子进行模 式的重组，通过变异算子进行模式的突变。通过这些遗传运算，一些 较差的模式逐步被淘汰，而一些较好的模式逐步被遗传和进化，最终 可以得到问题的最优解。 定义2 2 j 在模式中具有确定基因值的位置数目称为该模式的 模式阶( s c h e m ao r d e r ) ，记为口( 1 - 1 ) 。 例如，可记口( 0 1 l + 1 + + ) = 4 。 定义2 3 】模式日中的一个确定基因值的位置和最后一个确定基 因值的位置之间的距离称为该模式的模式定义长度( s c h e m ad e f i n i n g l e n g t h ) 。记为6 ( h ) 。 例虫口：占( 0 l l + 1 + ) = 5 1 = 4 。占( + 1 + + ) = 1 。 2 6 1 2 模式定理 假设在进化过程中的第t 代时，当前群体p ( t ) 中能与模式日匹配 的个数( 样本数) 记为m ( n ，t ) 下一代群体p ( t + 1 ) 中能与模式h 匹配 第2 0 页 太原理工大学硕士学位论文 的个体数记为m ( y ，f + 1 ) 。下面对基本遗传算法在选择算子、交叉算子 和变异算子的连续作用下，模式h 的样本数m ( h ，t ) 的变化情况进行分 析。 ( 1 ) 选择算子的作用 基本遗传算法中的选择运算使用的是比例选择算子。将当前群体 中适应度的总和记为f ( f ) = f ( a ，) ，群体的规模为”。在这个算子的 作用下，与模式h 所匹配的各个个体a ，能够平均复制聍f ( a 。) f ( t ) 个个体到下一代群体中，即： 峭川) = a j c i h p ( t ) 掣 o v ， ：v 竺! 塑：堕 ；舌辱( 。)f ( f ) 硼c u ，铲 钏( 町) 等 ( 2 - z ) 其中f ( h ，0 是第t 代群体中模式日所含个体的平均适应度； f ( t ) = f ( t ) n 是第t 代群体的平均适应度。 若再假设模式日的平均适应度总高出群体的平均适应度的c 倍， 则式( 2 1 ) 可改写为： m ( h ，t + 1 ) = m ( h ，f ) ( 1 + c ) ( 2 3 ) 由此可见，脚( 1 4 ，0 为一等比级数，其通项公式为： m ( h ，f ) = m ( h ，0 ) ( 1 + c ) ( 2 4 ) 第2 l 页 太原理工大学硕士学位论文 ( 2 ) 交叉算子的作用 假如有如下图所示的一个模式： 一剧 6 ( h ) 图2 - 2 模式及其定义长度 隐含在该模式中的样本与其它个体进行交叉操作时，根据交叉点 的位置不同，有可能破坏也有可能不破坏该模式而是其继续生存到下 一代群体中。下面估算该模式生存概率p ，的下界。 当随机设置的交叉点在模式的定义长度之内时，将有可能破坏模 式；而当随机设置的交叉点在模式的定义长度之外时，肯定不会破坏 该模式。再考虑到交叉操作本身是以交叉概率以发生的，所以模式h 的生存概率下界为： 列p 篱 ( 2 _ 5 ) ( 3 ) 变异算子的作用 若某一模式被破坏，则必然是模式描述形式中通配符”之外的 某一基因值发生了变化，其发生概率是： 1 一( 1 一p 。) 4 8 当p 。1 时有： 1 一( 1 一p 。) 4 ”盯( 日) 。p 。 由此可知，在变异算子作用下，模式h 的生存概率大约是： 魄。 第2 2 页 太原理工大学硕士学位论文 p 。“1 一o - ( h ) o p 。 ( 2 6 ) 这样，综合上述式( 2 2 ) 、( 2 5 ) 、( 2 6 ) ，并忽略一些极小项，则 在比例选择算子、交叉算子、变异算子的连续作用下，群体中模式h 的子代样本数为： 螂圳孙c 即，竽卜箬可帅江，、 由式( 2 - 7 ) 就可以得到下述定理： 【模式定理】遗传算法中，在选择、交叉和变异算子的作用下，具 有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式 将按指数级增长。相反，凡是长度长、阶次高、平均适应度低于群体 平均适应度的模式将呈指数形式消失。 模式定理深刻地阐明了遗传算法中发生“优胜劣汰”的原因。在 遗传过程中能够存活的优良模式又被称为积木块( b u