（计算机软件与理论专业论文）一种结合混沌搜索的自适应遗传算法.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名：问的日期： 论文使用授权声明 s 巧 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者虢喁咋导师签名：巨卢绽嗍个堪 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 摘要 基于群体搜索的遗传算法是在i ) a r w i n 的进化论和m e n d e l 的遗传学说的基 础上产生和发展起来的一类全局优化概率搜索算法。近3 0 年来已被广泛应用于 计算机科学、工程技术、管理科学和社会科学等许多领域，成为2 1 世纪智能计 算的核心技术之一。在基本遗传算法中，由于交叉概率( p c ) 和变异概率( p m ) 取为 恒定值，因此用于复杂的多变量优化问题时效率不高，并且存在“早熟”的可能 性。基手上逑原因，自造应遗传算法应用而生在自适应遗传算法中，交叉概率 ( p c ) 和变异概率( p i t l ) 基于个体的适应度值而自适应地改变。从而使算法在保持群 体多样性的同时，也保证了算法的收敛能力在实际应用中，由于问题本身的复 杂性，目标函数经常会出现高维、多峰、多变量以及非连续情况，此时在综合考 虑“快速收敛”和“全局最优”的条件下，应用基本遗传算法或自适应遗传算法， 都未必能取得理想效果。为此，在分析和研究自适应遗传算法特点的基础上，依 据混合优化策略及混合遗传算法的构造原则，将混沌优化搜索技术引入到自适应 遗传算法中，提出了一种结合混沌搜索的自适应遗传算法。该算法保持了自适应 遗传算法的所有特点，进一步改善了其全局寻优能力并有效克服局部收敛现象， 提高了算法的收敛速度和计算精度。测试函数仿真结果表明，该算法的性能优于 自适应遗传算法。 关键词：遗传算法自适应遗传算法快速收敛全局最优混合优化混沌搜索 局部收敛 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 a b s t r a c t p o p u l a t i o n b a s e dg e n e t i ca l g o r i t h mi sak i n do fg l o b a lo p t i m i z a t i o np r o b a b i l i t y s e a r c h i n gm e t h o d ，w h i c hi s o nt h eb a s i so fd a r w i n se v o l u t i o n a r y t h e o r ya n d m e n d e l st h e o r yo fg e n e t i cm u t a t i o n s g e n e t i ca l g o r i t h m ( g a ) h a sb e e nw i d e l y a p p l i e d t o m a n yf i e l d s ，s u c h a sc o m p u t e r s c i e n c e ，e n g i n e e r i n gt e c h n o l o g y , m a n a g e m e n ts c i e n c ea n ds o c i a ls c i e n c e ，e t c a n di tg r a d u a l l yb e c o m e so n e o ft h ek e y t e c h n o l o g i e so fi n t e l l i g e n tc o m p u t a t i o ni nt h e2 1 s tc e n t u r y d u et ot h ep r o b a b i l i t i e so f c r o s s o v e r a n d m u t a t i o n ( p , ) a r e c o n s j a n t s , i n t h e s t a n d a r d g e n e t i c a l g o r i t h m ( s g - a ) ，s oi t sn o tv e r ye f f i c i e n tw h e na p p l i e dt ot h eo p t i m i z a t i o np r o b l e m so fc o m p l e x m u l t i - v a r i a b l e a tt h es a m et i m e ，t h e r ee x i s t sp r e m a t u r ec o n v e r g e n c ep r o b a b l y b e c a - u s eo ft h er e a s o ng i v e na b o v e ，a d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) h a sb e e np r o p o s e d n a t u r a l l y , i nw h i c hp ca n dp ma d a p t i v e l yc h a n g ea c c o r d i n gt ot h ei n d i v i d u a l sf i t n e s s s ot h a tt h ea l g o r i t h mc a nk e e pt h ep o p u l a t i o nd i v e r s i t y , m e a n w h i l e ，g u a r a n t e et h e c o n v e r g e n c eo fa l g o r i t h m i np r a c t i c e ，d u et ot h ec o m p l e x i t yo fp r o b l e mi t s e l f , o b j e c t i v ef u n c t i o nu s u a l l ya p p e a r s a st h ef o r mo fh i g h d i m e n s i o n ，m u l t i p e a k ，m n l t i v - a r i a b l ea n dn o n c o n s e c u t i v e a tt h i st i m e ，u n d e rt h ec o n s i d e r a t i o no ff a s tc o n v e r g e n c e a n d g l o b a lo p t i m i z a t i o n ，i t sh a r dt oo b t a i ns a t i s f a c t o r yr e s u l t se i t h e rb yu s i n gg e n e t i c a l g o r i t h mo rb yu s i n ga d a p t i v eg e n e t i ca l g o r i t h m t h e r e f o r e ，o nt h eb a s i so fa n a l y s i s a n ds t u d yo f c h a r a c t e r i s t i c so f a g a , a c c o r d i n gt ot h eh y b r i do p t i m i z a t i o ns t r a t e g ya n d t h er u l e so fh y b r i dg a s ，t h ep a p e ri n c o r p o r a t e sc h a o so p t i m i z a t i o na l g o r i t h mi n t ot h e a g a , a n dp r o p o s e san e wa d a p t i v eg e n e t i ca l g o r i t h mc o m b i n e dw i t hc h a o s s e a r c h i n g ( a g a c c s ) t h ep r o p o s e da l g o r i t h mn o to n l yh a sa l lt h ef e a t u r e so fa g a , b u ta l s of u r t h e ri m p r o v e st h eg l o b a ls e a r c h i n ga b i l i t y , p r e v e n t si tf r o mp r e m a t u r e c o n v e r g e n c e ，o b t a i n sf a s tc o n v e r g e n c e a n dh i g h c o m p u t a t i o n a lp r e c i s i o n t h e c o m p u t a t i o n a lr e s u l t so ns e v e r a lb e n c h m a r kf u n c t i o n sh a v es h o w nt h a tt h ep r o p o s e d a l g o r i t h mi ss u p e r i o rt oa d a p t i v eg e n e t i ca l g o r i t h m k e y w o r d s ：g e n e t i ca l g o r i t h m ( g a ) ；a d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) ；f a s t c o n v e r g e n c e ；g l o b a lo p t i m i z a t i o n ；h y b r i do p t i m i z a t i o n ；c h a o ss e a r c h i n g ； l o c a lc o n v e r g e n c e 2 一种结合混沌搜索的白适应遗传算法上海师范大学硕士学位论文 第一章绪论 1 1 立题背景和意义 遗传算法是新兴发展起来的一类随机搜索与全局优化仿生算法自2 0 世纪 7 0 年代美国m i c h i g a n 大学h o l l a n d 教授及其学生创建以来“1 ，遗传算法引起了 国内外学术界和产业界的广泛关注，已成为2 l 世纪智能计算的核心技术之一。 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体 领域，故对问题的种类具有很强的鲁棒性”目前，遗传算法已被广泛应用于计 算机科学。工程技术、管理科学和社会科学等许多重要领域。 在基本遗传算法中，由于交叉概率( p c ) 和变异概率( 嘲取为恒定值，因此用 于复杂的多变量优化问题时，效率不高，并且存在“早熟”的可能性。基本遗传 算法可以用极快的速度达到最优解的9 0 左右，但要达到真正的最优解则要花费 很长的时间“1 。由此可见，基本遗传算法在理论和应用方法上仍有许多亟待完善 之处。 在自适应遗传算法中，由于交叉概率( p c ) 和变异概率( p r o ) 基于个体的适应度 值自适应地改变，从而使算法在保持群体多样性的同时，也保证了算法的收敛能 力，在一定程度上改进了基本遗传算法中存在的问题。“快速收敛”和“全局最 优”是一对相互矛盾的要求，对遗传算法而言，为了保证“快速收敛”，就希望 群体尽快地向最优态转移，这就势必减少了群体的多样性，容易使算法“早熟”； 为了保证“全局最优”，就要维持群体的多样性，以避免陷入局部极值，但这样 做势必又是以牺牲收敛速度为代价的。在该问题的处理上，自适应遗传算法仍存 在不足因此，如何改进自适应遗传算法，使其在“快速收敛”和“全局最优” 之间获得较好的平衡”，以高效和快速地解决实际工程中出现的复杂优化，是一 个迫切需要解决的问题，也是提高和改进自适应遗传算法优化性能的关键所在。 l 2 国内外研究现状 从上世纪7 0 年代以来，国内外学者对遗传算法进行了大量的研究，并提出 了许多改进方法。 k o z a 首先提出遗传编程概念眠”。他把遗传算法应用在计算机程序的优化设 计及自动生成中，并将其成功地应用于人工智能，机器学习和符号处理等方面； s r i n v a s 提出了自适应遗传算法嘲，自适应地调整交叉率和变异率，从而提高遗 6 - 二种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 传算法的优化性能；h e r r e r a 提出了基于模糊逻辑控制的自适应遗传算法，以改 进其收敛性能；e i b e n 提出了进化算法中参数的自适应控制方法和策略；s m i t h 提出了遗传算法中参数和操作算子自适应变化的一类新的自适应遗传算法： a c k l e y 提出了混合遗传爬山法；m a t h e f o u d 提出了混合遗传模拟退火法；m i l l e r 提出采用遗传算法中增加局部改善运算对于n p 难问题的优化求解问题。y o u n g s u y u n 提出了基于模糊逻辑控制器的自适应遗传算法。1 ，其核心思想主要体现在以 下四方面：首先计算出模糊逻辑控制器的输入变量，它是遗传算法中连续两代个 体平均适应度值的增量；其次归一化该变量并将它分配给反模糊化表中的相应分 。 。 r 量；再次是计算交叉概率和变异概率的增量；最后计算出相应的交叉概率和变异 概率，以对算法实现性能优化 中国科学院智能机械研究所唐玉珏、李淼提出了混合g p - g a “”，并将其用于 信息系统建模预测；西安交通大学系统工程研究所郝翔、李人厚提出了基于信息 熵的自适应遗传算法n 1 1 ，采用熵来估计群体的分散程度，并得出熵和收敛程度的 关系，进而改进自适应遗传算法的收敛性能；西安交通大学孙建永、申建中提出 了基于徐宗本教授新近提出的可分解可拼接遗传算法编码( s d 编码) ，动态选 择和动态变异的_ 类全新的自适应遗传算法“；南京大学熊军、高敦堂提出了变 异率和种群数且自适应的遗传算法“”，并通过在不同尺度n k l a n d s c a p e 上的应 用，显示了算法寻优能力的改进效果；南开大学刘洪杰、王秀峰提出了基于多峰 搜索的自适应遗传算法“”，通过变换函数将多峰问题中的所有峰变成“等高”峰， 并在子群中实施“梯度操作”，从而改进自适应遗传算法的收敛性能。清华大学 张良、王凌提出了含多种遗传算子的自适应遗传算法用于作业调度“”，该文主要 通过以一种自适应的混合方式引入了四种交叉算子( l o x ，p m x ，c 1 x & n a b e l ) 和 三种变异算子( s w a p ，i n v i n s ) ，从而有效地提高和改善了算法在进化过程中的 “开发”和“探测”性能 自适应遗传算法在进化初期并不理想。因为在进化初期的群体中，较优个体 几乎处于一种不发生变化的状态，而此时的优良个体不一定是全局最优解，从而 容易使进化走向局部收敛的可能性增加；自适应遗传算法在进化后期，由于初期 难以跳出局部最优解，进而导致算法最终陷入局部收敛。针对自适应遗传算法这 一缺点，本文将易跳出局部极小、搜索速度快和计算精度高“”“”的混沌优化算 7 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 法引入到自适应遗传算法中，提出了一种结合混沌搜索的自适应遗传算法，以实 现两者的优势互补和完美结合。这是一个很有意义的研究方向。 1 3 本文的主要工作 。 针对上述研究背景，根据国内外研究现状，在课题研究过程中，本文作者主 要做了以下工作： ( 1 ) 基于广泛的文献阅读，系统地探讨了自适应遗传算法，并在此基础上指出了 现有自适应遗传算法存在的缺点：进化初期停滞不前；进化末期极易陷入局 部收敛 ( 2 ) 学习混沌优化搜索算法，在研究之后发现：混沌优化算法具有对初值敏感、 易跳出局部极小，搜索速度快、计算精度高和全局渐近收敛的特点。 ( 3 ) 学习混合遗传算法的基本构造原则：尽量采用原有算法的编码；利用原有算 法的优点；改进遗传算子。 ( 4 ) 依据混合优化策略，将自适应遗传算法与混沌优化算法相结合，以实现两者 优势互补 ( 5 ) 应用基准函数对本文所提出的算法进行测试，实验结果表明该算法的性能优 于自适应遗传算法。 1 4 论文的结构分布 本文共分为6 章。 第1 章主要介绍课题的背景和研究意义、国内外的研究现状，并提出本文的 研究目标和所做的主要工作 第2 章主要介绍遗传算法的基本原理，包括其起源、数学理论及基本实现技 术，是全文的基础和铺垫 第3 章主要介绍混沌优化搜索技术，分别论述了混沌运动的基本性质、混沌 的基本特征及混沌优化算法。 第4 章是本文的重点，论述了自适应遗传算法的数学模型和研究策略、混合 优化算法的构造原则及混合优化策略的关键问题，并在此基础上实现了混合优化 算法：结合混沌搜索的自适应遗传算法。具体包括参数编码、适应度函数的选取、 操作算子的改进以及算法实现中有关问题的具体处理 第5 章是测试函数与结果分析部分。通过对4 个基准测试函数分别运用基本 8 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 遗传算法、自适应遗传算法及本文所提出的算法的计算，对比和分析了各算法的 优化性能。 第6 章对本课题的主要研究成果和未完善的问题进行了总结，并针对存在的 问题指出了下一步的工作重点。 9 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 第二章遗传算法原理与实现 2 1 遗传算法概述 2 1 1 遗传算法的生物学基础 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应 全局优化概率搜索算法。基于对生物遗传和进化过程的计算机模拟，遗传算法使 各种人工系统具有优良的自适应能力和优化能力。它所借鉴的生物学基础是生物 的遗传和进化，其理论基础是d a r w i n 的进化论和m e n d e l 的遗传变异学说。其中， 自然选择学说构成了现代进化论的主体“”它认为：通过不同生物间的交配以及 其他原因，生物的基因有可能发生变异而形成一种新的生物基因，这部分变异了 的基因也将遗传到下一代。虽然这种变化的概率是可以预测的，但具体哪一个个 体发生变化却是偶然的。这种新的基因依据其与环境的适应程度决定其增殖能 力，有利于生存环境的基因逐渐增多，而不利于生存环境的基因逐渐减少。通过 这种自然选择方式。物种将逐渐向适应于生存环境的方向进化，从而产生出优良 的物种。 2 1 2 遗传算法的发展历史 遗传算法起源于对生物系统所进行的计算机模拟研究。自从其诞生后，它在 不同历史阶段的发展情况如下： ( 1 ) 2 0 世纪4 0 年代，就有学者开始研究如何利用计算机进行生物模拟的技术， 他们主要从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工 作。 。 ( 2 ) 2 0 世纪6 0 年代，一些生物学家开始利用计算机对遗传系统进行仿真模拟 在此期间，美国m i c h i g a n 大学h o l l a n d 教授正在从事自适应系统的研究，受生 物学家们模拟结果启发，h o l l a n d 和他的学生首次将模拟遗传算子应用于自适应 系统的研究和开发 ( 3 ) 2 0 世纪7 0 年代，h o l l a n d 出版了他的第一本颇具影响的专著a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ，全面系统地论述了遗传算法和人i - 自适应 系统。 ( 4 ) 2 0 世纪8 0 年代，h o l l a n d 教授实现了第一个基于遗传算法的机器学习系统， 即分类器系统( c l a s s i f i e rs y s t e m s ) ，开创了基于遗传算法的机器学习的新概 l o 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 念在此期问，6 0 l d b e r g 出版了专著( g e n e t i ca l g o r i t h mi ns 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 ，系统总结了遗传算法的主要研究成果，全面而 完整地论述了遗传算法的基本原理及其应用，为现代遗传算法的发展奠定了坚实 的科学基础。 ( 5 ) 2 0 世纪9 0 年代，d a v i s 出版了专著( h a n d b o o ko fg e n e t i ca l g o r i t h m s ， 主要论述了遗传算法在科学计算、工程技术和社会经济中的大量应用实例。与此 同时，k o z a 提出了遗传编程( g e n e t i cp r o g r a n n i n g ) 概念他把遗传算法应用在 计算机程序的优化设计和自动生成中，并将其成功地应用于人工智能、机器学习 - r _ 和符号处理等方面。 2 ，1 3 遗传算法的特点 遗传算法利用了生物进化的思想，所以它有许多与传统优化算法不同的特点： ( 1 ) g a 是对问题参数的编码( 染色体) 群进行进化，而不是参数本身； ( 2 ) g a 是在优化问题的决定因素和控制参数的编码串上进行操作，来找出高适应 值的串，而不是对函数和它们的控制参数直接操作。所以用传统方法很难解决的 问题，g a 都能解决，因为g a 不受函数约束条件( 如连续性、导数存在、单极值 等) 的限制； ( 3 ) g a 的搜索是从问题解的串集开始搜索，而不是从单个解开始，因而大大减少 了算法陷入局部解的可能性； ( 4 ) g a 使用适应度函数这一信息进行搜索，而不需导数等其他信息。传统搜索方 法如“梯度算法”需要导数，当这些信息不存在时，算法就失败了，而g a 只需 适应度函数和编码串，因此，g a 几乎可以处理任何问题： ( 5 ) g a 使用的遗传算子都是随机操作，而不是确定规则。g a 使用随机操作，但 并不意味着g a 是简单的随机搜索，g a 是使用随机工具来指示搜索向着一个最优 解方向前进； ( 6 ) g a 具有隐含并行性即g a 在搜索空间里使用相对少的个体，就可以检验表 示数量极大的区域。若每一代对n 个个体操作，实际上算法处理了大约0 ( n 3 ) 个 模式。此外，g a 的隐含并行性有助于处理非线性问题： ( 7 ) g a 在解空间内进行充分的搜索，但不是盲目的穷举或试探，因为选择操作是 以适应度为依据的，因此它的搜索时耗和效率往往优于其他优化算法 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 2 1 4 遗传算法的机理 ， 遗传算法的数学定理是模式定理，即s c h e m e 定理。遗传算法的组成和执行 过程表明这是一种和具体领域无关的算法。算法本身并未解释这种搜索技术的合 理性和有效性。h o l l a n d 教授用定长字符串的数学技巧奠定了遗传算法的理论基 础。通过加入了一个元符号( 丰) ，h o l l a n d 教授引入了“模式”的概念，“模式” 是代表相似染色体串的模板：即除 之外其他位置都匹配的所有串。例如，模式 1 1 1 匹配两个串1 1 1 0 和1 1 1 l ；。模式l l 料匹配四个串1 1 0 0 ，1 1 0 1 ，1 1 1 0 和1 1 1 1 不同的模式具有不同的特性。通过数学的推导得出如下的模式定理：具有短 _ 距、低阶和平均适应值高于群体平均适应值的模块，在遗传算法的后续代中以指 数方式增加它的实验次数。 模式定理保证了较优模式的样本数呈指数增长，使遗传算法寻找全局最优解 有了数学上的依据。 2 1 5 遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的 具体领域，故对阿题的种类具有很强的鲁棒性。目前已被广泛应用于许多领域。 ( 1 ) 函数优化 函数优化是g a 的经典应用领域，也是对g a 进行性能评价的常用算例。尤其 是对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法很难求解， 而用g a 却可以方便地得到较好的结果。 ( 2 ) 组合优化 随着问题规模的增大，组合优化问题的搜索空间也会急剧扩大，很难甚至不 可能用枚举法进行求解。而人们意识到用g a 可以找到其满意解。如目前在t s p 问题、背包问题和图形划分问题中的成功应用。 ( 3 ) 生产调度 生产调度问题在许多情况下所建立起来的数学模型难以精确求解。即使获得 结果，也会因简化太多而与实际问题的结果相差甚远。目前，g a 已成为解决这 类复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产 规划和任务分配等方面都得到了成功应用。 ( 4 ) 自动控制 1 2 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 在自动控制领域中有很多与优化相关的问题，g a 在其中已得到了初步的应 用并显示出了良好的效果。如目前g a 用在航空控制系统的优化、设计空间交会 控制器、设计模糊控制器、进行人工神经网络结构优化等方面。 ( 5 ) 机器人学 机器人是一类复杂的难以精确建模的人工系统，而g a 的起源就来自于对人 工自适应系统的研究，所以机器入学理所当然地成为g a 的一个重要应用领域。 如目前g a 已经用在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆 运动学求解和细胞机器人结构优化等方面。 - ( 6 ) 图像处理 图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，由于扫 描、特征提取、图像分割等操作不可避免地会存在一些误差，致使影响图像处理 效果。而g 可以使这些误差变为最小，从而使计算机视觉达到实用化的要求。 目前已在模式识别、图像恢复和图像边缘特征提取方面得到了成功应用。 ( 7 ) 人工生命 人工生命是用计算机、机械等人工媒体模拟或构造出具有自然生物系统特有 行为的人造系统。基于g a 的进化模型是研究人工生命现象的重要基础理论虽 然人工生命的研究尚处于启蒙阶段，但g a 已在其进化模型、学习模型、行为模 型和自组织模型等方面得到了初步的应用。可以预见，g a 在人工生命及复杂自 适应系统的模拟与设计和复杂系统突现性理论研究中，必将会得到更为深入的应 用和发展。 ( 8 ) 遗传编程 k o z a 发展了遗传编程概念，他使用以l i s p 语言所表示的编码方法，基于对 一种树型结构所进行的遗传操作来自动生成计算机程序 ( 9 ) 机器学习 学习能力是高级自适应系统所应具备的能力之一。基于g a 的机器学习，特 别是分类器系统，在很多领域中都得到了应用。如目前6 a 在被用于学习模糊控 制规则、学习隶属度函数和调整人工神经网络的连接权等方面都得到了成功应 用。 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 2 2 遗传算法的数学理论 2 2 1 模式定理 2 2 1 1 模式 定义2 1 群体中的个体即基因串中的相似样板称为模式。模式是基于三元集 0 ，1 ， 的字符串。其中计表任意字符，即0 或1 。例如，模式$ l 奉描述了子 集 0 1 0 ，0 1 l ，1 1 0 ，1 1 - 1 模式表示基因串中基些特征位相同的结构i 它描述的是_ 令串眵子集对于 二进制编码串，当串长为m 时，共有3 - 个不同的模式。遗传算法中串的运算实 际上是模式的运算。如果各个串的每一位按等概率生成0 或1 ，则规模为n 的群 体模式总数的期望值为： 芝a 2 i 6 一l 一删y ) ， 群体最多可以同时处理n 2 - 个模式。 2 2 1 2 模式阶 定义2 2 模式h 中确定位置的个数称为模式h 的模式阶，记作o ( h ) 例如， 0 ( 0 1 i * 1 柏= 4 模式阶用来反映不同模式问确定性的差异。模式阶数越高，模式的确定性就 越高，所能匹配的样本个数就越少 2 2 1 3 定义距 定义2 3 模式h 中第一个确定位置与最后一个确定位置之间的距离称为模 式的定义距，记作6 ) 。例如，6 ( 0 1 1 + 1 ) = 4 。 在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距 正是反映这种性质差异的数学量所在。 2 2 1 4 模式定理 对于某一种模式，在下一代串中将有多少串与这些模式匹配呢? 模式定理 ( s c h e m at h e o r e m ) 给出了这一问题的解答。模式定理可表示为： 也) 胁帆) x 掣卜掣卸k 】 z ， 1 4 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 式( 2 - 2 ) 中，m ( h ，t + 1 ) 表示在l 代群体中存在模式抒的个体数目；m ( n ，f ) 表 示在t 代群体中存在模式h 的个体数目；i ( h 1 表示在f 代群体中包含模式日的个 体平均适应度；7 表示在f 代群体中所有个体的平均适应度；f 表示个体的长度； p 。表示交叉概率；p 脚表示变异概率。 定理2 1 在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以 及平均适应度高于群体平均适应度的模式在子代中呈指数增长。 模式定理是g a 的基本理论，保证了较优模式的数目呈指数增长，为解释g a 的机理提供了一种数学工具。但是，它们仍存在以下缺点： ( 1 ) 模式定理只对二进制编码适用，对其他编码方案尚没有相应的结论成立； ( 2 ) 模式定理只给出了在下一代中包含模式h 的个体数的下限，我们无法据此推 断算法的收敛性； ( 3 ) 模式定理没有解决算法设计中控制参数的选取等问题。 2 2 2 积木块假设 2 2 2 1 积木块 定义2 4 在模式定理中所指的具有低阶、短定义距以及平均适应度高于群 体平均适应度的模式称为积木块( b u i l d i n gb l o c k ) 。 积木块在g a 中非常重要，在子代中将呈指数增长，在遗传操作下相互结合， 产生适应度更高的个体，从而找到更优的可行解 2 2 2 2 积木块假设 积木块假设( b u i l d i o gb l o c kh y p o t h e s i s ) ：低阶、短距、低平均适应度的模 块( 积木块) 在遗传算子作用下相互结合，能生成高阶、长距、高平均适应度的 模式，最终可生成全局最优解。 目前大量的实践证据支持积木块假设，它在许多领域中都取得了成功地应 用。例如平滑多蜂问题、带干扰多峰问题以及组合优化问题等。 综上所述，模式定理保证了较优模式( g a 的较优解) 的样本数呈指数增长， 从而满足寻找最优解的必要条件，即g a 存在着寻找到全局最优解的可能性；而 积木块假设指出，6 a 具备寻找到全局最优解的能力，及积木块在遗传算子的作 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 用下，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。上述结 论是基于模式定理对g a 的全局收敛性问题进行的定性分析。 2 2 3 隐含并行性 在g a 的运行过程中，每代都处理了m 个个体。但由于每个个体编码串中隐 含有多种不同的模式，所以算法实质上却是处理了更多的模式。下面以二进制编 码符号串为例，通过计算来定量分析g a 的隐含并行性( i m p l i c i tp a r a l l e l i s m ) 。 由于_ 些定义长摩较长的模式极易被交叉蚕算破坏掉，故在此估算群体中定 义长度在也一1 ) 以下的模式个数( 其中l 。，且为一常数) 假设群体中的某一 个体a 和某一模式h 如图2 - 1 所示： a a l a 2 4 i q + 1 a j + 2 a i + i , f i t l + + 1 a i h j + + s l s 2 s + + + 图2 - 1 个体及模式 这样的子串s ，屯的起始位置共有( ，一+ 1 ) 个，并且每个s ；一屯表示长度 在纯一1 ) 以下的模式，则其中至少有一个是0 或l ，最多全部是固定的。显然这 种长度在( f ，一1 ) 以下的模式共有2 种。由此可知，与一个个体所对应的模式数 应该为：和一f j + 1 ) 2 。进而可知，在群体的全部嬲个个体中所隐含的模式数 为：m 0 一l + 1 ) 2 。 若肘较大，则对一些低阶的模式肯定会有一些重复。为排除这些重复部分， 可取群体规模数为m 一2 “此时，模式阶高于或等于f ，2 的模式最多只重复计 数一次。由此可估计出排除重复模式后的模式数量n ，约为： 炉业等唑- 掣 即有：_ 。c m3 一d 3 ) 通过式( 2 - 3 ) 、( 2 - 4 ) ，我们可以得出如下结论： 群体规模m 的立方成正比m 州。 1 6 ( 2 3 ) ( 2 4 ) g a 所处理的有效模式总数约与 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 2 2 4 收敛性 基本遗传算法可描述为一个齐次m a r k o v 链只= p ( f l f 2o 因为其中的选 择、交叉和变异操作都是独立随机进行的，新群体仅与其父代群体及遗传操作算 子有关，而与其父代群体之前的各代群体无关，即群体无后效性，并且各代群体 之间的转换概率与时间的起点无关。因此，运用m a r k o v 链可方便地对g a 的收敛 性进行理论分析。在此主要给出两个重要定理，其详细证明过程，可参阅文献 2 2 、 2 3 。 _ 定理2 2 基本g a 收敛于最优解的概率小于l 。 定理2 3 使用保留最佳个体策略的g a 能收敛于最优解的概率为1 2 3 遗传算法的实现技术 2 3 1 编码方法 2 3 1 1 编码 定义2 5 在g a 中，把一个问题的可行解从其解空间转换到g a 所能处理的 搜索空间的转换方法称为编码 编码是应用g a 时需解决的首要问题，也是设计g a 时的一个关键步骤。编码 方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化计算的效 率。 2 3 1 2 编码原则 作为参考，d ej o n g 提出了两条操作性较强的实用编码原则汹1 ： 编码原则一( 有意义积木块编码原则) ：应使用能易于产生与所求问题相关的 且具有低阶、短定义长度模式的编码方案。 编码原则二( 最小字符集编码原则) ：应使用能使问题得到自然表示或描述的 具有最小编码字符集的编码方案。 2 3 1 3 常用编码方法 ( 1 ) 二进制编码 二进制编码是g a 中最常用的一种编码方法。它使用二值符号集 o 1 l 进行 编码，个体是由0 和l 组成的二值符号串，串的长度与问题所要求的求解精度有 一种结合混沌搜索的自适应遗传算法上海师范大学硕士学位论文 关假设问题某一参数的取值范日为k 。，。】，用长度为，的二进制符号串来表 示该参数，贝i j 它总共能够产生2 。种不同的编码，若使参数编码时的对应关系如下： 0 0 0 0 0 0 - 0 _ “m 0 0 0 0 0 1 1 一珥。，自+ 6 1 1 1 1 1 1 2 一1 。一 则二进制编码的编码精度为j ，旨，若某一个体的二进制编码是 岛6 l 一1 6 ，- 2 6 3 6 2 岛，则其对应的解码公式为：x 暑“呐+ 旨x 骞6 j x 2 扣1 二进制编码方法的优点是编码、解码操作简单易行；交叉、变异等遗传操作 容易实现；符合最小字符集编码原则以及便于利用模式定理对算法进行理论分 析。 二进制编码方法的缺点是在求解多目标、高精度的连续函数优化问题时，其 中出现的海明悬崖( h a m m i n gc l i f f s ) 会影响连续的搜索空问中的局部搜索；最优 解不能达到任意的精度，若要求的精度越高，需要的字符串就越长，增加了算法 的计算复杂性及时空开销；二进制编码不便于反映所求问题的特定知识，不便于 开发针对问题专门知识的遗传算子。 ( 2 ) g r a y 码编码 g r a y 码编码是二进制编码方法的一种变形，其编码精度与相同长度的二迸 制编码精度相同。在求解连续优化问题中，它能改进二进制编码由于遗传运算的 随机特性而使其局部搜索能力较差的特性g r a y 码编码方法为其连续的两个整 数所对应的编码值之间仅仅只有一个码位是不相同的，其余码位都完全相同 假设有一个二进制编码为b 一扫以一，b 2 b 。，其对应的g r a y 码为 g g g “9 2 9 l 。则由二进制编码到g r a y 码转换满足：g 。b m 且 g ；皇6 i + ，0 良，i m1 , m2 , - - 2 ，1 ；由g r a y 码编码到二进制转换满足：吒= g ，且 包- b , + 。o 岛，i = 小一1 ，册一2 , - - , 2 j 其中。表示异或运算符 g r a y 码编码方法的优点是便于提高g a 的局部搜索能力；交叉、变异等遗传 1 8 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 操作容易实现；符合最小字符集编码原则以及便于利用模式定理对算法进行理论 分析 ( 3 ) 实数编码 实数编码是指个体的每个基因值用某一范围内的一个实数来表示，个体的编 码长度等于其决策褒量的个数。在实数编码的g a 中个体的基因值采用的是决策 变量的真实值，故其必须满足问题参数的取值范围。例如，若某一优化问题含有 5 个变量 g i ( f 一1 ，2 ，5 ) ，每个变量都有其对应的上下限k 二，n 0j ，则： x ；冬3 0 , 4 7 叩4 0 , 4 8 晒7 0 ) 就表示一个体的基因型，其对应的表现型是： 工= 5 3 0 , 4 7 叩4 0 ，4 8 0 ，5 7 0 】r 实数编码是g a 中在解决连续参数优化问题时普遍使用的一种编码方式，具 有较高的精度；在表示连续渐变问题方面具有优势；不存在海明悬崖( h a m m i n g c l i f f s ) 问题；便于较大空间的遗传搜索；便于g a 与经典优化方法的混合使用； 便于设计针对问题的专门知识的知识型遗传算子；便于处理复杂的决策变量约束 条件。 ( 4 ) 符号编码 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只 有代码含义的符号集例如，整数和字母排列编码( 1 i t e r a lp e r m u t a t i o n e n c o d i n g ) 对于组合优化问题非常有效。对于使用符号编码的g a ，需要认真设计 交叉、变异等遗传操作，以满足问题的各种约束要求，方能提高算法的搜索性能。 2 3 1 4 特殊编码方法 有关g a 的特殊编码方法，诸如排列编码、二倍体编码、d n a 编码、混合编 码或多参数编码、二维染色体编码或矩阵编码、树结构编码、m e s s yg a 可变长 编码、基于相似度的可变染色体编码、a g e n t 编码等编码方法的具体实现，可参 阅文献 2 5 2 3 2 适应度函数 定义2 6 度量个体适应度的函数称为适应度函数( f i t n e s sf u n c t i o n ) 定义2 7 对个体适应度所做的扩大或缩小变换称为适应度尺度变换( f i t - 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 2 3 2 1 常见适应度函数 ( 1 )直接以待求解目标函数的转化形式作为适应度函数，即：若目标函数为 最大化问题f f f ( ，g ) ) 一，g ) ：若目标函数为最小化问题朋( ，g ) ) ，0 ) 。 由这种方法确定的适应度函数简单直观，但存在两个缺点：其一是可能不满 足概率非负的要求：其二是求解所得函数值分布相差甚大，不利于群体的优化性 能。 ( 2 ) 屏限构造法 若目标函数为最大化问题，贝l j f i t ( i ( x ) ) 一，0 ) 一c 曲，0 b c 曲，否则为0 ， 其中c 曲为，g ) 的最小值估计；若目标函数为最小化问题，则 f f f ( 厂g ) ) = c 一一厂b x ，b ) c c ，否则为0 ，其中c 。为，g ) 的最大值估计。 该方法是对第一种方法的改进。其缺点：有时存在界限值预先估计困难，不 可能做到精确的问题。 ( 3 )分数构造法 若目标函数为最大化问题，则： ，f f ( ，。硼1 ，c z o ，c 一，b ) 之o ( 2 5 ) 若目标函数为最小化问题，则： 肋( 厂仁) ) 2 硼1 肚0 ，c + ，仁) 2 0 ( 2 6 ) 式( 2 5 、( 2 6 ) 中c 均为目标函数界限的保守估计值。 2 3 2 2 适应度函数尺度变换 ( 1 ) 线性尺度变换 设原始适应度函数为，比例适应度函数为“，则线性比例变换满足下面的 关系式：“( ，) = n 厂+ 6 ( 2 7 ) 式( 2 - 7 ) 中，口和6 可用许多方法选择，但必须满足下面两个条件：第一，平 均比例适应度i 要等于其原平均适应度7 ，e p u 一；7 ；第二，最大比例适应度“一 一种结合混沌搜索的自适应遗传算法 上海师范大学硕士学位论文 要等于其原平均适应度7 的指定倍数，即“一c x 7 其中，c 一般取值为2 这两个条件保证平均群体个体和最优个体的期望复制数分别为1 和c 。在应用线 性比例变换方法时，当出现负的比例适应度时，解决方法是：把原最小适应度，二 影射到比例适应度”。= o ，并且保持原平均适应度7 与新平均适应度，相等 线性尺度交换图像如下所示： ( a ) 适应度正常情况 b )