（模式识别与智能系统专业论文）遗传算法和人工神经网络的分析与改进.pdf

摘要 本文着重对人工智能中两个热门课题遗传算法和人工神经网络进 行分析和改进，并研究这两种方法协同进行的学习技术，然后将其应用到电池荷 电态顸估领域。 研究内容主要包括： ( 1 ) 从概率角度分析遗传操作算子的作用、搜索范围以及种群多样性的影 响，并根据种群多样度对遗传算法的参数进行自动调节，抑制早熟现象。对六个 测试函数优化仿真结果验证了算法的有效性。 ( 2 ) 综合考虑数据类型、学习算法和网络拓扑之间的关系，改进遗传神经 网络，在染色体中加入对学习算法的编码，以适应不同类型的数据。对p r o b e n l 的仿真结果验证了算法的自适应能力。 ( 3 ) 采用数理统计方法分析训练前后神经网络权值的变化情况，改进权连 接剪切算法，并获得适合具体问题的非全连接神经网络。对p r o b e n l 的仿真结果 表明改进算法能够在满足误差要求的前提下，尽可能简化拓扑，提高效率。 ( 4 ) 采用数理统计方法分析性能较好的神经网络权值分布情况，总结出其 基本服从正态分布的规律，并以此指导初始权值的设置。对p r o b e n l 的仿真结果 表明按照正态分布初始化权值能够从定程度上提高训练效率。 ( 5 ) 考虑到激励函数在神经元中的重要作用，在神经网络中引用组合激励 函数的思想，并分析传统遗传编码方式对组合激励函数编码的缺陷，然后对其进 行改进并形成混合编码的遗传神经网络。对p r o b e n l 的仿真结果表明进化得到的 具有组合激励函数的神经网络能够普遍减小输出误差。 ( 6 ) 采用遗传神经网络建立电池荷电态自适应预估模型，通过神经网络的 学习功能分析荷电态同端电压、放电电流的关系，然后利用遗传算法优化网络拓 扑，最终形成适合特定类型电池的神经网络预估模型。对三种不同类型电池的仿 真结果验证了两种方法协同进行的学习技术的自适应性和有效性。 关键词：遗传算法，人工神经网络，荷电态，多样度，数理统计。 a b s t r a c t t h i sp a p e rf o c u s e so na n a l y z i n ga n di m p r o v i n gg e n e t i ca l g o r i t h ma n da r t i f i c i a l n e u r a ln e t w o r k ，a n dc o o p e r a t i n gg e n e t i ca l g o r i t h mw i t ha r t i f i c i a ln e u r a ln e t w o r kt o l e a r nt o g e t h e r f i n a l l y , t h i sc o o p e r a t i v et e c h n i q u ei sa p p l i e dt oe s t i m a t eb a t t e r ys t a t e o f c h a r g e t h em a i nw o r k si n c l u d e ： ( 1 ) a n a l y z et h ef u n c t i o n sa n ds e a r c hs c o p e so fg e n e t i co p e r a t i o n s ，a n da l s ot h e e f f e c to f p o p u l a t i o nd i v e r s i t y , b yp r o b a b i l i t y t h e n , a d j u s tt h ep a r a m e t e r so fg e n e t i c a l g o r i t h md u r i n ge v o l u t i o na c c o r d i n gt op o p u l a t i o nd i v e r s i t y i no r d e rt or e s t r a i n p r e m a t u r ec o n v e r g e n c e t h ee f f i c i e n c yo ft h ei m p r o v e dm g o f i t h mi sv a l i d a t e db y s i m u l a t i o nr e s u l t so f s i xd i f f e r e n tv a l i d a t i o nf u n c t i o m ( 2 ) t a k et h ed i f f e r e n td a ms e t ，l e a r n i n ga l g o r i t h ma n dn e t w o r kt o p o l o g yi n t o a c c o u n tt o i m p r o v eg e n e t i c n e u r a ln e t w o r k p e r f o r m a n c eb ya d d i n gl e a r n i n g a l g o r i t h m sc o d et oc h r o m o s o m e t h ea d a p t a b i l i t yo ft h i sa l g o r i t h mi sp r o v e db y s i m u l a t i o nr e s u l t so f p r o b e n lt e s ts e t ( 3 ) a n a l y z et h ew e i g h t sd i f f e r e n c eo fn e u r a ln e t w o r kb e t w e e np r e - t r a i n i n ga n d p o s t - t r a i n i n gb ys t a t i s t i c s ，i m p r o v et h ec o r m e e t i o np r u n i n ga l g o r i t h mt o c o n s t r u c t n o n 蛐lc o n n e c t i o nn e u r a ln e t w o r k t h es i m u l a t i o nr e s u l t so fp r o b e n lt e s ts e ts h o w t h a tt h ei m p r o v e da l g o r i t h mi s c a p a b l eo fe n h a n c i n gt h en e u r a ln e t w o r ke f f i c i e n c y w i t hm e e t i n gt h er e q u i r e m e n t o f o u t p u t e f r 0 ( 4 ) a n a l y z e t h ew e i g h t sd i s t r i b u t i o ns t a t u so f w e l l - p e r f o r m e dn e u r a ln e t w o r k sb y s t a t i s t i c st o g e n e r a l i z e d i s t r i b u t i v e p r i n c i p l e t h e n b a s e do nt h i s p r i n c i p l e ，w e i n i t i a l i z ew e i g h t sb e f o r et r a i n i n gn e u r a ln e t w o r k t h es i m u l a t i o nr e s u l t so fp r o b e n l t e s ts e ti l l u m i n a t et h a tt h et r a i n i n ge f f i c i e n c yc o u l db ee n h m c e dt os o m ee x t e n tb y i n i t i a t i n gw e i g h t sa c c o r d i n g t on o r m a ld i s t r i b u t i o n ( 5 ) c o n s i d e r i n gt h ei m p o r t a n tr o l e so fa c t i v a t i o nf u n c t i o n so fn e u r a ln o d e ，w e c o m b i n ed i f f e r e n tf u n c t i o n st ot h es a m en e u r a ln e t w o r k , a n da n a l y z et h ed r a w b a c k so f t r a d i t i o n a lc o d em e t h o d s ，t h e nc o n s t r u c th y b r i dc o d em e t h o db a s e dg e n e t i cn e u r a l n e t w o r k t h eo u t p u te r r o rc a nb eg e n e r a l l yd e c r e a s e du s i n gt h en e u r a ln e t w o r kw i t h c o m b i n e da c t i v a t i o nf u n c t i o n sa c h i e v e db ye v o l u t i o nm e t h o d ( 6 ) w e c o n s t l u e ta d a p t i v ee s t i m a t i o nm o d e lo fb a t t e r ys t a t eo fc h a r g eb yg e n e t i c n e u r a l n e t w o r k d u r i n g t h e p r o c e s s o fm o d e l i n g , n e u r a ln e t w o r kt o p o l o g yi s o p t i m i z e db yg e n e t i ca l g o d t h ma f t e r i tl e a r n e dt h er e l a t i o n s h i pb e t w e e ns t a t eo f c h a r g ea n dt e r m i n a lv o l t a g e ，d i s c h a r g ec u r r e n t t h u st h en e u r a ln e t w o r km o d e lf o r b a t t e r yo f c e r t a i nt y p ei sa c h i e v e d t h ea d a p t a b i l i t ya n de f f i c i e n c yo ft h ec o o p e r a t i v e t e c h n i q u ew i t ht w o m e t h o d sf i l ev a l i d a t e db yt h es i m u l a t i o nr e s u l t so ft h r e eb a t t e r i e s o f d i f f e r e n tt y p e k e y w o r d s ：g e n e t i c a l g o r i t h m ，a r t i f i c i a l n e u r a ln e t w o r k ，s t a t eo fc h a r g e ， p o p u l a t i o nd i v e r s i t y , s t a t i s t i c s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果。也不包含为获得盘壅盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意。 学位论文作者签名：庑勇签字日期：2 彩年硐黝e l 学位论文版权使用授权书 本学位论文作者完全了解鑫鲞盘鲎有关保留、使用学位论文的规定。 特授权叁洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：j l 蟛导师签名：考抽弋之倦务薮 签字日期：珈；年垃月z 口日签字日期：哗惕订日 天津大学硕士学位论文 第一章绪论 1 1 人工智能分类及研究背景【1 】【2 【3 】 人工智能是一门新兴学科，至今尚无统一定义，它主要研究用机器来模仿和 执行人脑某些智力功能。人工智能分为符号智能和计算智能两大流派，下面分别 介绍其发展背景。 早在二十世纪三、四十年代，数理逻辑和计算理论领域的许多著名学者就已 经开始了对智能的探索，分析逻辑与计算思想同人工智能之间的关系。1 9 5 6 年 夏，在d a r t m o u t h 大学举行的第一次人工智能研讨会上，诸多知名学者针对机器 模拟人类智能的问题进行了热烈讨论，人工智能这一术语首次被使用。这次会议 标志着人工智能学科的诞生。在随后的几十年里，尽管遇到了许多困难、争议和 挑战，人工智能仍然取得了明显的进展，引起众多学科的日益关注。1 9 6 8 年研 制成功的第一个专家系统d e n d r a l 是人工智能应用领域的重大突破；1 9 7 7 年 知识工程概念的诞生标志着人工智能发展的又一个里程碑；8 0 年代后，专家系 统和知识工程得到了迅速发展，获得许多研究者的共识。上述以数理逻辑为基础 发展起来的人工智能流派被称为符号智能。 同符号智能截然不同的另一派系是计算智能，它主要包括模拟人脑神经元的 人工神经网络和模拟生物种群进化的遗传算法。人工神经网络与计算机的研究几 乎是同步发展的。1 9 4 3 年，心理学家m e c u l l o e h 和数学家p i t t s 提出了神经元学 习准则，为人工神经网络奠定了基础。5 0 年代末，r o s e n b l a t t 提出了感知器模型， 首次把人工神经网络付诸实践。但是1 9 6 9 年，人工智能创始人m i n s k y 和p a p e r t 发表的感知器一书，从数学上分析了感知器的原理和局限性。而当时符号智 能正取得了巨大进展，从而使神经网络的研究热潮低落下来。直到8 0 年代， h o p f i e l d 和r u m e l h a r t 先后提出了联想记忆神经网络和基于反向传播算法的多层 前馈神经网络，克服了阻碍感知器继续发展的障碍；另一方面，自2 0 世纪8 0 年 代以来，符号智能在工程应用中遇到了许多困难，难以解决模式识别等对人来说 非常简单的问题。由于这两方面原因，促使人们重新开始探索人工神经网络。 7 0 年代末至8 0 年代初，遗传算法的出现带给人工智能新的活力。它通过模 仿生物种群进化机制，在遗传过程中不断淘汰劣等个体，提高种群适应度，以达 到优化效果。它经常被用来配合其他算法进行多方法学习。 由此可以看到人工智能不同学派之间的激烈争论，共同推动人工智能的发 展。本文主要对计算智能中多层前馈神经网络和避传算法进行分析和改进。 第一章绪论 1 2 本文主要研究内容【2 】【3 1 4 1 t 5 】嗍 本文主要针对计算智能中的遗传算法和神经网络进行改进，并研究多种学习 方法协同进行的学习技术。 遗传算法是近些年发展起来的一种崭新的全局优化算法，本质是种仿生学 方法。它首先在问题的解空间里进行编码，然后利用选择、交叉、变异操作进化 种群，提高个体的适应性。遗传算法在智能学习中发挥重要的作用：一方面可以 通过自身进化实现目标优化，其简单的计算和内在的并行性表现出很多传统优化 方法难以比拟的优点；另一方面，遗传算法的优化作用可以配合其他算法进行多 方法学习，提高效率，例如遗传神经网络将遗传算法和神经网络结合起来，更有 效的处理数据，发现潜在的规律和信息。 人工神经网络是模拟人脑神经元结构，通过神经网络复杂的黑箱过程，实现 预测、模式判别、联想记忆、聚类等功能。其知识体现在网络分布式矩阵结构的 连接权值上，学习体现在权值调整的逐步计算上。传统的数理统计方法固然也可 以通过回归分析、多元统计分析等方法实现聚类、判别等功能，但是随着维数的 增加，信息爆炸的压力严重削弱了这些传统算法的性能，而神经网络处理较高维 数数据的性能远优于一些传统算法。这也是它在工程中得到广泛应用的主要原因 之一。 本文就上述两方面进行研究分析，包括如下内容： ( 1 ) 遗传算法的改进捌 遗传算法是一种自适应的全局优化概率搜索算法，自从8 0 年代其基本框架 形成以来，以其计算简单、全局寻优的特点得到了广泛的工程应用，并不断改进、 完善，但早熟问题仍然是阻碍其有效利用的瓶颈之一。近年来，混合算法、多种 群进化算法等技术被用来改善简单遗传算法的性质，维持种群的多样性和进化效 率。本文从概率角度分析遗传操作算子的作用、搜索范围以及多样性的影响，并 根据种群的多样度对遗传算法的参数进行自动调节，抑制早熟现象。 ( 2 ) 神经网络拓扑结构的优化州胪 随着人工智能的发展，神经网络在许多应用领域得到了广泛有效的应用。但 是，由于神经网络没有严格的理论基础，神经网络的拓扑优化至今尚无一般化的 理论。工程应用中，通常是依靠经验来选取多种不同的结构，然后采用学习算法 对这些不同结构神经网络的连接权值进行优化，依据各自的误差和所需的时间， 从中选取较优者。对于规模比较庞大的神经网络，这种依靠经验选择拓扑的方法 显然是一个耗费大量人力和时间的过程。为了解决这个问题，学者们提出了多种 神经网络拓扑优化方法，诸如神经网络剪枝算法、最差节点误差增长算法、拓扑 2 天津大学硕士学位论文 结构增长算法( n e a t 算法) 等。本文采用遗传算法和剪枝算法对神经网络的拓 扑进行优化，得到比较简洁有效的结构。 ( 3 ) 神经网络权值分布规律及初始值设置 4 1 1 5 1 在神经网络中，权值的初始化强烈地影响着最终的解。不同的初始权值设置 可能会对训练时间、收敛性、泛化误差造成巨大的差异。研究人员通过大量实践 经验总结出一些设置初始权值的方法。本文从性能较好的神经网络权值分布入手 作统计分析，通过大量实际数据，对较好的网络权值分布总结出经验性的规律， 并以此指导初始权值的设置。 ( 4 ) 神经元激励函数的选择【4 】 目前太多数的学习算法都是基于d e l t a 规则和反向传播算法的，在运算过程 中需要计算每个神经元的输出及神经元激励函数的导数，因此神经元激励函数的 形式是决定整个神经网络训练和最终结果的基本因素之一。早在人工神经元出现 之前，三种基本的神经元激励函数( 1 i n e a r 、s i g m o i d 、t a n s i g ) 就已经在生物学领 域得到了广泛共识。但是随着人工神经网络的发展，这三种基本函数也显现出其 固有的缺点。随后人们研究出一些具有复杂形式的复合函数以克服这些缺点，而 这些复合函数却增大了计算量。同时人们发现并非所有的神经元都处于需要复合 激励函数的位置，在同一神经网络中采取不同的激励函数混合运算，会带来更好 的效果。本文为更好的解决混合激励函数选择搭配的问题，提出基于遗传算法的 函数选择算法。 ( 5 ) 遗传神经网络在电池s o c 预测中的应用 7 1 电池是各种用电设备，如电动汽车、笔记本电脑、移动电话等能量的来源， 对其进行有效的管理具有重要的实际意义。电池管理系统具有数据采集、电控制、 安全控制、电量显示以及温度控制等功能，其中最主要的是能够准确可靠地获得 电池现存的容量状态参数，即对电池剩余容量的预测。电池荷电态( s t a t eo f c h a r g e ) 是放电剩余容量的一个主要指标，即在一定放电电流下，电池剩余电量 同总电量的百分比。电池内部包含复杂的物理化学变化，其容量是放电电流、端 电压、温度等多种因素的复杂的非线性豳数，因此很难对电池荷电态做出比较精 确的预估。另外，电池的种类、特性也是多种多样，这给电池荷电态预估模型的 建立造成了更大的困难。本文在遗传神经网模型上采用变参数遗传算法建立电池 荷电态预估模型，以尽可能提高进化速度，克服了传统建模方法的缺点。 1 _ 3 本课题采用的评价数据和工作平台 1 3 1 评价数据 第一章绪论 如何评价一个遗传算法的性能优劣程度一直是一个比较困难的问题，因为现 实问题种类繁多，影响因素纷杂，如果对各种情况都加以考虑和测试，势必耗费 大量的工作。另一方面，纯数值函数的优化问题不包含某一具体应用领域中的专 门知识- 便于不同领域中的研究人员的相互理解和交流，并能较好地反映算法本 身的特征和实际应用能力。所以研究人员专门设计了一些具有复杂数学特征的纯 数学函数来测试遗传算法对这些函数优化的能力。本文中使用以下六个函数： d ej o n gf u n c t i o n 2 、d e j o l l gf u n c t i o n 3 、s c h a f f e rf u n c t i o n 7 、g o l d s t e i n p r i c e f u n c t i o n 、s h u b e r tf u n c t i o n 、s i x - h u m pc a m e lb a c kf u n c t i o n t 3 j 。函数的具体描述 将在第二章的仿真结果中给出。 对神经网络拓扑优化算法或学习算法进行评价一直也是神经网络研究的重 要问题之一。由于以往有新的算法提出时作者所提供的评价事例非常少，或者仅 仅采用某些经典问题( 如n - b i t p a r i t y 、s p j 捌、s y m m e t r y 等) ，这些经典问题本身 有其弊端，并不能有效全面的评价一个算法；而且，提供这些算法的作者很少能 对所使用的算例、算法运行的环境、对数据的编码方式等诸多影响c p u 时间的 因素提供详细的描述；另外，数据本身也需要花费很多时间搜集和准备，从而使 得研究人员不能完全将注意力放在神经网络算法本身上。为解决这些问题，一些 神经网络的研究人员将一些经过严格挑选和测试的、编码方式既定的、评价标准 详细描述的真实世界实际数据作为评价神经网络算法的标准测试集合 ( b e n c h m a r k ) ，将其作为共享资源提供给所有研究人员，从而使得所有的研究者 都有了一个共同的评价标准来评价神经网络算法。本文采用c a r n e g i em e l l o n u n i v e r s i t y 提供的一套标准测试集p r o b e n lf 8 1 作为标准对神经网络进行测 试。p r o b e n l 共包含1 2 套数据集，其中1 0 套属于模式分类问题，2 套属于函数 逼近问题，各套数据的特点描述如表1 1 。 表1 1 标准测试集p r o b e n l 数据特点描述 p r o b e n l输入输出样本 描述 测试集维数维数数 c a n c e r926 9 9对良性肿瘤和恶性肿瘤分类 c a r d5 126 9 0判断信用卡是否有效 d i a b e t e s827 6 8判断糖尿病是否是阳性 g e l l e1 2 033 1 7 5通过基因序列判断内外基因区的边界 g l a s s962 1 4对玻璃类型分类 h c a r t3 529 2 0预测心脏病 h o r s e5 833 6 4预测马患绞痛病并以此判断其能否存活 4 天津大学硕士学位论文 m u s h r o o m1 2 528 1 2 4区分毒蘑菇和可食用蘑菇 s o y b e a n 3 51 96 8 3识别大豆的1 9 种病变 t h y r o i d 2 137 2 0 0诊断甲状腺正常、机能亢进或机能衰退 b u i l d i n g 1 434 2 0 8预测建筑中居民的电能消耗量 预测2 4 小时内太阳表面某一区域可能发 f i a r e2 431 0 6 6 生闪焰的规模 其中每一套数据集的样本都被分为3 部分，训练集、校验集、测试集，分别 占样本总数的1 1 2 、1 4 、1 4 。训练集的作用是训练神经网络；校验集的作用是在 网络学习过程的每一个训练周期后，检验所得到神经网络的泛化误差，如果连续 几个训练周期内泛化误差与训练误差偏离都很大，那么就停止训练，其目的是防 止过训练导致泛化误差随训练误差降低反而增大的弊端；测试集作用是在学习结 束后测试网络的泛化误差。 由于神经网络本身的不确定性，即使对于相同的数据、相同的网络拓扑，每 一次训练得到的训练误差、校验误差、测试误差以及训练周期几乎都不一样，因 此本文采用多次训练后得到的平均值( m e a n ) 和标准差( s t d d e v ) 作为仿真结果， 以提高结果的可靠性。 另外，本文的第五章电池荷电态预测所使用的数据是实际采集来的数据，并 不属于p r o b e n l 数据集。 1 3 2 工作平台 本文全部工作主要是在m a t l a b 、s p s s 、s l u s 等平台上进行计算机仿真试 验。 第二章基于多样度的变参数遗传算法 第二章基于多样度的变参数遗传算法 2 1 遗传算法概述【3 1 遗传算法实质上体现了仿生学思想，基于达尔文“优胜劣汰，适者生存”的 进化理论，模拟生物在自然环境中遗传和进化的过程。它是一种自适应的全局优 化概率搜索算法。 遗传算法最早由美国密执安大学的h o l l a n d 教授提出，之后经过d ej o n g 等 人的大量工作，8 0 年代由g o l d b e r g 进行归纳总结，形成了遗传算法的基本框架。 2 1 1 基本遗传算法( s g a ) 构成要素 0 1 基本遗传算法的构成要素包括4 方面内容： ( 1 ) 染色体编码方式： 基本遗传算法使用固定长度的二进制符号串表示个体。定义字母表矿= o ，1 ) ， 个体空间s = ( o ，1 ，个体x s ，其中? 是个体j 的长度。初始群体中各个个体 的基因值可用均匀分布的随机值来生成。而在改进的遗传算法中编码方式可以采 用十进制、浮点数、符号等多种方式。 ( 2 ) 个体适应度评价： 基本遗传算法按照与个体适应度成正比的概率来决定当前群体中每个个体 遗传到下一代群体中的机率。因此必须根据不同的问题和目标函数值来确定适应 度评价函数，实现编码串到个体适应度之间的映射。而且适应度函数值必须是正 值，即适应度函数，需满足： f ：s 寸r + ( 3 ) 遗传操作算子： 基本遗传算法包括三种基本算子： a )选择算予t ：s ”一s ，是种群空间到个体空间的映射。常用的选择 规则是概率规则，即 p ( 砰( j ) ：。 ：掣 ( 2 1 ) ，4 ( 以) 其中：i 表示种群( z 。，z ：，x 。) ； 0 口 ，当口= 1 时，称为比例选择算予。 b ) 。交叉算子疋：s 2 斗s ，表示从母体空间到个体空间的映射，其作用 天津大学硕士学位论文 是以交叉概率p ，交换一对个体的部分基因，形成新的个体。其中母体空间由以 下函数生成疋：s ”哼s 2 。常用的交叉算子操作是单点随机交叉：以随机确定一 个基因位置作为交叉点，交换一对母体对应于交叉点的后半部分，形成新的个体。 c )变异算子l ：s 斗s ，是个体空间至u 个体空间的映射，其作用是以变 异概率p 。改变个体分量取值。常用的变异操作是单点变异：对个体的某一分量， 产生随机数，如果这个随机数大于p 。，就将这一分量的值改变。 ( 4 ) 基本遗传算法运行参数： m ：种群大小，即种群中包含的个体的数量。 f ：进化终止的最大代数。 p ，：交叉概率。 p 。：变异概率。 这四个参数对遗传算法的求解效率和结果都有一定影响，但目前尚无选择的 理论依据，因此在实际应用中往往需要多次试探才能确定合适的取值。 2 i 2 基本遗传算法形式化定义研 基本遗传算法可以定义为一个8 元组： s g a = ( c ，e ，e o ，m ，c ，t ，l ，t ) 其中：c 个体编码方式； 个体适应度评价函数； 只初始群体； m 种群大小； r 选择算子； r 交叉算子； 乙变异算子； 丁遗传运算终止条件。 p r o c e d u r es g a ： b e g i n i n i t i a l i z e p ( o ) ； t = 0 ： w h i l e ( t s t ) d o f o ri = 1t o 肘d o e v a l u t ef i t n e s so fp ( f ) ； e n d f o r f o rf = 1t o 膨d o 第二章基于多样度的变参数遗传算法 e n d s e l e c t o p e r a t i o nt op ( t ) ； e n d f o r f o ri = l t o d o c r o s s o v e r o p e r a t i o nt op ( ，) ； e n d f o r f o rf = 1t 0 材d o m u t a t i o n o p e r a t i o nt op ( t ) ； e n d f o r f o rf = 1t omd o p ( t + 1 ) = p ( t ) ； e n d f o r t = t + 1 ： e n dw h i l e 2 2 遗传算法弊端分析 2 2 1 遗传算法弊端分析及参数选择的重要性【3 】【9 1 遗传算法由于其运算简单和解决问题的有效能力而被广泛应用。理论上已证 明：遗传算法从概率意义上以随机方式寻求到问题的最优解。但另一方面，经过 大量的实践，遗传算法在一些应用中会表现出不尽人意的问题，其中最主要的问 题是早熟现象。目前解决这些问题的方法有很多种，比如采用混合算法，使得各 种算法扬长避短，共同产生更佳的优化性能；多种群进化算法，顾名思义，多个 具有不同参数的种群同时进化，并采取迁移的策略，维持种群的多样性和进化效 率。本文主要根据种群的多样度对遗传算法的参数进行自动调节，抑制早熟现象。 遗传算法的参数选择对优化过程的效率和结果有着显著的影响。遗传算法的 主要参数在上面已经提到。m 较小时，运算量相应减小，从而提高了遗传算法 的速度，但是却降低了种群的多样性，可能引起早熟现象。交叉算子是遗传算法 中产生新个体的主要方法，对染色体具有破坏作用，如果p ，较大，则容易破坏 较好的染色体；如果较小，那么产生新个体的速度会减慢，降低优化效率；而且 交叉操作的搜索空间仅局限于初始种群决定的模式空间，可想而知，如果参数m 较小，其搜索范围也会很小，容易陷入局部最优。p 。也是产生新个体的方法， 但它对模式具有破坏作用，取值太大固然会产生较多的新个体，但会破坏掉很多 b 天津大学硕士学位论文 较好模式，使得遗传算法性能接近于随机搜索算法；如果取值太小，则生成新个 体的能力和抑制早熟现象的能力就会较差。因此选择参数是一个很重要的环节， 研究人员经过长期的实践给出了几个参数选择的建议范围，但这个范围仍然很 大，实际应用中依旧需要工程人员对多种可能的参数选择方案进行计算和筛选。 本章提出的算法主要基于种群多样度对交叉概率p 。和变异概率p 。进行自动调 节，以适应不同进化阶段的需要。 2 2 2 基于种群多样度的分析【9 】1 1 0 】【l l 】【1 2 】【1 3 】【1 4 】 定义2 1 ：x 、y 之间的h a m m i n g 距离定义为 ， d ( x ，y ) = k y 。l ( 2 - 2 ) i = l 其中x = ( x l ，石2 ，x ，) ，y = ( y t ，y 2 ，y 1 ) 定义2 2 ：设口。 0 ，1 ，l i k i f ，一个模式是个体空间中的“超平面”， 记作 妒= 【( i k ，a 。) ；o k s k 】= x = ( x l ，一，x f ) s ；x = a k ( k 置) ( 2 3 ) 其中：k 称作模式的阶，记作d ( p ) = k ：( 而，靠) 称为妒的定义分量( 或 定义基因位置) ；巩称作定义分量值( 定义等位基因) ，模式的定义长度定义为 占( 妒) = i 一 ( 2 - 4 ) 在不引起混淆的情况下，将模式妒【( ，a 。) ；o k 捌简记作妒【( ，a 。) ；足】。 定义2 3 ：称映射h ：【0 ，1 】一【0 ，1 为模糊度，若满足： ( 1 ) h ( a ) = 0 当且仅当口= o ，1 ，日( ) = 扬； ( 2 ) 爿( 玎) = h ( 1 一卅； ( 3 ) 日( 口) 在【o ，】上单调递增。 定义2 4 ：设二 ：( x l ，x 。) 为种群，x 。= ( x n ，h ) ，( f 墨) ，日为模糊度， 称 d 正) = 日( 二1 酗n ) ( 2 - s ) 为j 在分量j 处的多样度。称 j r 斗、一1 1 df 磊 ( 2 6 ) d ( j ) 一，二一，( x ) ( 2 - 6 ) 为量的种群多样度。 第二章基于多样度的变参数遗传算法 模糊度是对基因作用的进一步刻画。若在一个种群的某个基因位置上的模糊 度为0 ，该基因位置在交叉作用中不起作用，从而减小了交叉的搜索空间。而变 异算子则有可能破坏算子的优良模式，但从另一方面讲可以提高种群的多样度。 下面的分析将说明这一点。 定理2 1 ：对于选择算子r 及种群并= ( x ，z 2 ，x 。) ，有 尸f 彳( z ) c x ) = 1 ( 2 7 ) 证明： p 巧( x ) c x _ = p 程? t x 、= x | 、 扣1 = 1 得证。 定理2 2 ：设单点交叉算子乏，对于任意( x ，x ：) e s 2 ，y s ，则 p l ( x i ，x 2 ) = r ) = 车 ( 2 - 8 ) 其中；= ； ( 五，x ：，y ) 为单点交叉( 墨，丑) 可以生成y 的基因位置个数。 证明：令l 表示在染色体第f 个基因位置进行单点交叉，则 p t ( z i ，x 2 ) = y ) t = p 既( 五，z ：) = y ) f ；i 七 ， 得证。 定理2 3 ：设选择算予t 、单点交叉算子t 及模式妒= 研纯，吼) ，k ，对于 z c p ，有 p 仉。野( z ) 亡妒) = l ( 2 _ 9 ) 证明：对于任意( x ，y ) c 妒，z 仨伊，( x ，y ) 交叉生成z 的基因位置个数为0 ， 因此有 p 亿( z ，y ) = z = 0 由概率性质及全概率公式得 p t o 。巧( x ) c 奶 1 0 天津大学硕士学位论文 = l 一p 征( 砰( i ) ) = z z t = 1 一p f ( x ，y ) = z ) p f r ( j ) = ( x ，y ) ) z 却( ，r ) c p = 1 得证。 定理2 4 ：任给两个个体x ，i ，s 、变异操作算子l 及变异概率p 。，有 ， 瓦( x ) = y = p ：z ，( 1 一p 。) 。4 丘 ( 2 1 0 ) 证明：将x ，j r 的基因位置分为两种情况；m = x ，与 z ，。x ，的个数为 a ( x ，y ) ，y ，= x ，的个数为卜- d ( x ，的。有 p 已) = n = f ip 。n ( 1 一