（系统工程专业论文）多模态优化的混合小生境遗传算法.pdf

中文摘要 在现实世界中许多实际问题都是多模态优化( m u l t i m o d a lo p t i m i z a t i o n ) 问题，即问题存在多个最优解，或者存在一个全局最优解以及若干局部最优解； 类似地，数学中也存在具有多个极值点的多峰( m u l t i p e a k e d ) 函数。标准遗传 算法( s g a ) 具有概率选择机制和全局搜索的特点，在解决多模态优化问题中具 有一定的可能性。标准遗传算法由于交叉算子的随机配对机制，可能会使位于不 同峰值附近的个体发生交叉后，双方偏离各自的峰点；而且由于搜索过程中适应 度小的模态不断地被淘汰，因此很难同时搜索出多个极值点，往往仅能收敛到一 个模态。为此，人们提出多模态遗传算法( m g a m u l t i m o d a lg e n e t i ca l g o r i t h m s ) ， 用来寻找多模态函数的多个峰( 或局部极值点) 。 本文提出一种混合小生境遗传算法，这是一种把峰半径自适应控制方法和聚 类算法以及顺序小生境遗传算法相结合的混合小生境遗传算法。本算法可以在无 需提供峰半径或峰个数的前提下，搜索到并维持优化问题解空间中的多个峰。该 方法将峰半径作为决策变量编码为染色体中的一部分，在对决策变量进行优化的 同时，对峰半径进行动态调整。用聚类算法得出每次运行遗传算法结束时的聚类 中心，这样可以减少算法的计算时间( 或计算复杂度) 。 这种算法能够轻易的找出多模态问题的多个解，包括全局最优解和局部最优 解，并且不需要知道所求问题的峰的情况。对于很多实际问题是很有效的。但是 这种算法在求解不知道峰的个数的情况时，到结束时需要进行连续几次迭代才能 判别是否已经求出所有的最优解。目前还没有有效的办法达到一旦找到所有的最 优解算法就能够识别到进而马上终止运算。 关键词：遗传算法顺序小生境技术多模态优化自适应参数调整聚类算法 a b s t r a c t h at h er e a lw o r l d , m a n yp r a c t i c a lp r o b l e m sa r em u l t i m o d a lo p t i m i z i n gp r o b l e m s w h i c hh a v em u l t i p l eo p t i m a ls o l u t i o n s ，o rh a v eag l o b a lo p t i m a ls o l u t i o na n ds e v e r a l l o c a lo p t i m a ls o l u t i o n s i m i l a r l y , t h e r ea r em a n ym u l t i - p e a kf u n c t i o n sw i t hs e v e r a l e x t r e m ev a l u ep o i n t si nm a t h e m a t i c s t h es t a n d a r dg e n e t i ca l g o r i t h m ( s g a ) w i t h p r o b a b i l i t ys e l e c t i o nm e c h a n i s ma n dg l o b a ls e a r c h i n g ，t h e r ei sp o s s i b i l i t yi ns o l v i n g t h em u l t i m o d a lo p t i m i z i n gp r o b l e m s b e c a u s eo ft h er a n d o mm a t i n gm e c h a n i s m ，t h e s t a n d a r dg e n e t i ca l g o r i t h mm a ym a k et h ei n d i v i d u a l sn e a rd i f f e r e n tp e a k sc r o s s e d ， a n db o 血o ft h e md e v i a t ef r o mt h e i rp e a kp 0 血d u et ot h ei n d i v i d u a l sw i t hs m a l l f i t n e s sw i l lt ob ee l i m i n a t e dd u r i n gt h es e a r c h , s oi ti sd i f f i c u l tt os e a r c ho u ts e v e r a l e x t r e m ev a l u ep o i n t ss i m u l t a n e o u s l ya n do f t e no n l yc a nc o n v e r g et oo n ep o i n t a n d m u l t i m o d a lg e n e t i ca l g o r i t h m s ( m g a ) w a sp u t e do u tt os e a r c h i n gf o rt h em u l t i p l e p e a k s ( o rl o c a le x t r e m u r np o i n t s ) o f t h em u l t i m o d a lp r o b l e m s t h i sp a p e rp r o p o s e sak i n do fh y b r i dn i c h eg e n e t i ca l g o r i t h m t h i si sak i n do ft h e p e a kr a d i u sa d a p t i v ec o n t r o l e dm e t h o da n dt h ec l u s t e r i n ga l g o r i t h mw i t hs e q u e n c e n i c h eg e n e t i ca l g o r i t h mc o m b i n i n gi n t oah y b r i dn i c h eg e n e t i ca l g o r i t h m t h i s a l g o r i t h mc a ns e a r c ho u tt h em u l t i p l ep e a k so ft h eo p t i m i z a t i o np r o b l e mi nt h e m u l t i p l es o l u t i o ns p a c ew i t h o u tk n o wt h en u m b e ro fp e a k so rp e a k sr a d i u s t h i s m e t h o dm a k e st h ep e a kr a d i u sa sd e c i s i o nv a r i a b l ea n de n c o d i n gi n t ot h ec h r o m o s o m e w h e no p t i m i z i n gt h ed e c i s i o nv a r i a b l e si nt h ep e a k , d y n a m i c a l l ya d j u s tt h er a d i u s s i m u l t a n e o u s l y w ec a nr e c o r dam a x i m u mb yc l u s t e r i n ga l g o r i t h ma tt h ee n do f e a c h o p e r a t i o no ft h eg e n e t i ca l g o r i t h m ，b e c a u s et h ec l u s t e r i n ga l g o r i t h mc a nr e d u c et h e c o m p u t a t i o nt i m e ( o rc o m p u t a t i o n a lc o m p l e x i t y ) t l l i sa l g o r i t h mc a ne a s i l yf i n da l lt h em u l t i m o d a lp r o b l e m s i n c l u d i n gb o t l lt h e g l o b a lo p t i m a ls o l u t i o na n dl o c a lo p t i m a ls o l u t i o n , a n dd o n tn e e dt ok n o wa n y i n f o r m a t i o na b o u tt h ep e a k s t 1 1 i sa l g o r i t h mi sv e r ye f f e c t i v ef o rm a n yp r a c t i c a l p r o b l e m s w h e nw ed on o tk n o wt h en u m b e ro fp e a k s ，t h i sa l g o r i t h mn e e dt or u ng a f o rs e v e r a lt i m e st oa s kw h e t h e rh a v ef m da l lo p t i m a ls o l u t i o n s b u tt h e r ei sn o e f f e c t i v ew a yt oi d e n t i f yw e t h e rf o u n da l lt h eo p t i m a ls o l u t i o n sa n di m m e d i a t e l y t e r m i n a t e 也er u n k e yw o r d s ：g e n e t i ca l g o r i t h m ，s e q u e n c en i c h e ，m u l t i m o d e lo p t i m i z i n gp r o b l e m s ， s e l f - a d a p t i v ep a r a m e t e rc o n t r o l ，c l u s t e r i n ga l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丢洼太堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：彳孑茁签字日期：2 卯夕年月2 日 学位论文版权使用授权书 本学位论文作者完全了解 丢洼太堂有关保留、使用学位论文的规定。特授权丢洼太堂可以将 学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫 描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送 交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：勇孑嘭 导师签名： 签字日期：少巧车月2 日签字日期：卫矿哆年月上日 天津大学硕 ：学位论文 1 1 引言 第一章绪论 在实际应用问题中优化问题普遍存在，随着生产、经济、技术的发展，工程 技术、管理人才在实际工作中常常会面临这样的一类问题：怎样选取参数使得工 程设计既满足要求又能降低成本；怎样的资源分配方案既能满足各方面的基本要 求，又能获得好的经济效益；选择怎样的生产计划方案才能提高产值和利润，怎 样确定各种原料成分的比例才能提高质量、降低成本；怎样解决控制工程中的稳、 准、快等时域指标与稳定裕度、系统带宽等频域特性的综合问题等。这一类问题 的共同点是选出最合理、达到最优目标的方案，这些都是优化问题。 而且在现实世界中许多优化问题都是多模态优化( m u l t i m o d a lo p t i m i z a t i o n ) 问题，即问题存在多个最优解，或者存在一个最优解以及若干局部最优解；类似 地，数学中也存在具有多个极值点的多峰( m u l t i p e a k e d ) 函数。因而对多模态 优化问题求解方法的研究具有较重要的应用价值。这类问题一般性质十分复杂， 很难用传统的优化方法如线性规划，非线性规划，动态规划之类的方法来求解。 如何构造一种优化算法，使之能够搜索到全部全局最优解和尽量多的局部最优 解，已成为一个持续研究的领域。 自上世纪6 0 年代以来，人们对求解这类难解问题的兴趣日益增加。进化算 法( e v o l u t i o n a r ya l g o r i t h m ) 在解这类优化问题中显示出了优于传统优化算法的 性能。一般认为，进化算法( e v o l u t i o n a r ya l g o r i t h m ) 包括三个组成部分：遗传 算法( 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 yp r o g r a m m i n g ) ，和进化策略 ( e v o l u t i o n a r y s t r a t e g i e s ) 。进化算法是一种基于自然选择和遗传变异等生物进化 机制的全局性概率搜索算法。从整体上讲，遗传算法是进化算法中产生最早，影 响最大，应用也比较广泛的一个研究方向和领域。标准遗传算法( s g a ) 具有概 率选择机制和全局搜索的特点，在解决多模态优化问题中具有一定的可能性。可 是简单遗传算法的选择策略缺乏多样性保护机制，而对于多峰函数优化来说，解 群中解的多样性是保证搜索到最优解的必要条件，为了保证解群中解的多样性， 引入了小生境( n i c h e ) 技术。 第一章绪论 1 2 本文研究的背景和意义 1 2 1 遗传算法的研究概述 遗传算法是生物学，计算机科学，人工智能以及系统科学等学科相结合而产 生的一种全局性概率搜索方法，它是人们认识自然，掌握自然规律并用于解决客 观世界实际问题的产物。遗传算法的基本思想来源于d a r w i n 进化论和m e n d e l 遗传学说。达尔文d a r w i n 的生物进化论其中的自然选择适者生存是遗传算法的 主要指导原则之一【l 3 1 。早在1 9 6 2 年密执安大学的j o h nh o l l a n d 在发表的论文 o u t l i n ef o ral o g i ct h e o r yo f a d a p t i v es y s t e m s 2 】中提出了利用群体进化的思想。他指 出新的群体应当基于当前群体的有效性来产生。尽管他当时没有给出实现这些思 想的具体技术但确实引进了群体适应值，复制，变异，交叉等基本概念。七十年 代中期，j o h nh o l l a n d 和他的同事、学生提出了这一算法，其目的是解释自然的 自适应过程及设计一个体现自然界机理的软件系统。后来这一算法被广泛应用于 各种优化问题和机器学习、模式识别、人工智能等。 遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不 是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻 优点集【5 】。在遗传算法中，问题的解集被定义为种群中的染色体，每个染色体代 表一种可能解。种群中染色体的数量表示种群的规模。染色体在连续的后代中得 到不断进化。子代染色体一般这样产生：通过交叉操作来合并两个父代染色体， 或通过变异操作改变父代染色体。在每一代中都要评价染色体的适应度( 一般根 据目标函数) ，有较高适应度的染色体其存活概率较大。经过数代之后，新生代 中染色体会趋于同样，或者满足某种给定的条件，最终的染色体表示对问题的最 优或接近最优解。遗传算法所涉及的五大要素包括：参数编码，初始群体的设定， 适应度函数的设计，遗传操作的设计和控制参数的设定【5 】。 遗传算法所涉及的要素： ( 1 ) 遗传编码 按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题 实际表示与遗传算法的染色体位串结构之间建立联系，即确定编码和解码运 算【5 】。简单二进制编码的采用得到了h o l l a n d 早期理论结果( 模式定理、最小 字母表原理) 的支持，但它仍有许多不足之处。二进制编码还有一些变种， 如g r a y 编码，二倍体( d i p l o i d ) 编码等克服了二进制编码的一些不足。此 外，序列编码、实数编码、树编码、自适应编码、乱序编码以及将以往的合 成编码分解成多个相对独立编码的编码策略等多种编码方法也都被证明各 天津大学硕士学位论文 有优缺点。 ( 2 ) 适应函数( 评价函数) 遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则，必 须对个体位串的适应性进行评价。因此，适应函数( f i m e s sf u n c t i o n ) 就构成了 个体的生存环境。根据个体的适应值，就可决定它在此环境下的生存能力。般 来说，好的染色体位串结构具有比较高的适应函数值，既可以获得较高的评价， 具有较强的生存能力【5 1 。 ( 3 ) 遗传算子 标准遗传算法的操作算子一般包括选择( s e l e c t i o n ，或复制r e p r o d u c t i o n ) 、 交叉( c r o s s o v e r ，或重组r e c o m b i n a t i o n ) 和变异( m u t a t i o n ) 三种基本形式，它 们构成了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中发 生的繁殖、杂交和突变现象的主要载体。遗传算法利用遗传算子产生新一代群体 来实现群体化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过 程的基本工具。 ( 4 ) 初始群体的设定 遗传算法与传统随机类搜索算法的最大区别之一，在于它的整个算法是在解 的群体上进行的。正是这一特点使g a 具有了搜索过程的并行性、全局性和鲁棒 性，可见群体的设定对整个g a 的运行性能具有基础性的决定作用。根据模式定 理，群体规模对遗传算法的性能影响很大。群体规模越大，群体中个体的多样性 越高，算法陷入局部解的危险就越小。但是随着规模增大，计算量也显著增加。 若规模太小，使遗传算法的搜索空间受到限制，则可能产生未成熟收敛的现象。 初始群体的个体一般是随机产生的【5 】 ( 5 ) 控制参数和选择 在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组 参数在初始阶段或群体进化过程中需要合理的选择和控制，以使g a 以最佳的搜 索轨迹达到最优解。主要参数包括染色体位串长度l ，群体规模1 1 ，交叉概率p c 以及变异概率p m 【5 1 。 基本遗传算法( s g a ) ； s g a 是相当简单的抽象模型。个体用固定长度的串表示，群体大小也是固 定的。按概率选择群体中的个体来生成下代个体，选择的概率正比于个体适应 度大小。通过交叉和变异产生新个体。 算法过程如下： 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 ( 0 ) ： t = 0 ： w h i l e ( t 一 t ) d o f o r l = l t o md o e v a l u a t ef i t n e s so fp ( t ) ： e n d f o r f o r1 = 1t omd o s e l e c to p e r a t i o nt op ( t ) ； e n d f o r f o r1 - 1t om 佗d o c r o s s o v e ro p e r a t i o nt op ( t ) ； e n d f o r f o r l = l t o md o m u t a t i o no p e r a t i o nt op ( t ) ； e n d f o r f o r1 = 1 t omd o p ( t + 1 ) = p ( t ) ： e n d f o r 酣1 ： e n dw h i l e e n d 1 2 2 小生境机制的产生及简介 c a v i c h i o t 6 , 刀于1 9 7 0 年首先提出了基于预选择的小生境实现方法。1 9 7 5 年d e j o n g t 8 1 提出了基于排挤机制的选择策略， 中，各种不同的生物为了能够延续生存， 其基本思想源于在一个有限的生存空间 它们之间必须相互竞争各种有限的生存 资源。共享法的选择策略是g o l d b e r g 和r i c h a r d s o o 9 】于1 9 8 7 年提出的。g o l d b e r g 和r i c h a r d s o o t 9 】利用h o l l a n d s 的共享函判1 0 】的概念，按照个体相似性将种群划分 为不同的子种群小生境机制的另外一个方法是拥挤方法。m a l i f o u d t 】通过引人相 同小生境中父代与子代的竞争，改进了d ej o n g 8 】提出的标准拥挤方法，提出了 确定性拥挤方法。 在生物学中，小生境( n i c h e ) 是指特定的生存环境。生物在其进化过程中， 般总是与自己相同的物种生活在起。在遗传算法中引进小生境的概念，让种 群中的个体在不同特定的生存环境中进化，而不是全部聚集在种环境中。这样 天津大学硕土：学位论文 可以使算法在整个解空间中搜索，以找到更多的最优个体。避免了在进化后期适 应度高的个体大量繁殖，充斥整个解空间，导致算法停止在局部最优解上。在自 然界中，小生境技术( n i c h i n g ) 表现为：生态环境中分享不同资源的物种的形成。 对应于像g a 这样的人工系统，小生环境技术表现为：在一个固定规模的群体中 子群的形成，每个子群体对应问题的一个子任务( 在多峰值优化问题中，每个子 任务对应于找出个山峰) 。小生境技术具有相对简单、有效和通用的特征，因 此，它可作为s g a 强有力的组成部分。 1 2 3 小生境遗传算法在多模态优化问题中的应用 多模态优化( m u l t i m o d a lo p t i m i z a t i o n ) 问题是指解空间中存在多个极值点 的最优化问题。对于多模态优化问题，传统的基于导数或其他启发式信息的搜索 算法，如梯度爬山法，模拟退火方法等，存在着如何避免限于局部极值点的问题。 遗传算法( g a ) 具有空间分布式信息继承与重组的特征，其效果显著好于传统 的单点搜索方法和启发引导方式，其特征是邻域局部性信息继承和逼近【1 2 】。但 是在简单g a 中种群存在向单一模式收敛的性质，不易确保多种模式长期并存 【l3 1 。针对这样的问题在遗传算法中引入了生物学中小生境的概念，让种群中的个 体在不同特定的生存环境中进化。使得算法在整个解空间中进行搜索，找到更多 的全局或局部最优解。所以采用小生境技术的遗传算法是适用于多模态优化问题 的种有效方法。 1 2 4 本文主要解决的问题和研究意义 引入小生境技术的遗传算法是解决多模态优化问题的有效方法，目前直接或 间接的小生境技术已经出现很多种，其中最有代表性的有基于预选择机制的小生 境技术，基于排挤机制的小生境技术，基于适应值共享机制的小生境技术。小生 境遗传算法也具有一些缺陷，如局部搜索能力及搜索效率较差，且小生境参数的 确定主要依赖于问题本身和经验，缺少理论依据，没有一定的准则。还有很多基 于小生境技术的改进算法，例如，隔离小生境技术，克隆小生境技术等。但是这 些研究主要集中在如何确定小生境参数方面 1 3 - 1 5 】或遗传算子的改进。本文主要 任务是把一些已经存在的用于解多模态优化问题的技术引入小生境技术中，例如 迭代( i t e r a t i o n ) ，自适应参数调整，适应值共享机制( f i t n e s ss h a r i n g ) 以及多种 群策略( ( m u l t i p o p u l a t i o ns t r a t e g y ) 和聚类算法( c l u s t e r i n ga l g o r i t h m ) 等，以 提出新的算法。新提出的算法是在不改变的标准遗传算法的基本结构的前提下对 算法进行改进以提高算法的收敛速度，局部搜索能力和尽可能找到所有的峰值， 以及能够应用一些事先对峰的个数，大小不了解的多模态优化问题。顺序小生境 第一章绪论 ( s e q u e n c en i c h e ) 算法通过修改适应值空间在前迭代中找到的解的位置来进 行下一步的运算，在每一迭代过程中都要运用g a 算法进行搜索，用修改的适应 值函数记录下运行中找到的最好的个体，在这期间结合类聚小生境算法识别和跟 踪全局和局部最优解，结合两种方法即局部选择的多种群策略和子群间的交配限 制方法和类聚算法。本文的主要技术问题是基于连续小生境和类聚小生境算法实 现多模态问题的优化，以求在一定程度上减少全局搜索的盲目性，进行有针对的 局部搜索，识别出全局和局部最优解，使得对基本的g a 机制和适应值函数的影 响尽可能的小，要有尽可能少的临界参数使之允许黑箱优化。 在实际工程中，许多问题都可以抽象为对目标函数为多模态函数的优化，如 复杂系统参数及结构辨识问题等。在实际应用中，为了得到多种选择或多方面的 信息，不仅要求获得待求解问题目标函数的全局最优解，而且还要求得到尽可能 多的局部最优解。因此用遗传算法解决多模优化问题在理论和应用方面都具有重 大意义。 1 3 研究思路与论文的组织结构 本文的研究思路如下： ( 1 ) 首先对基本知识进行介绍说明： ( 2 ) 介绍相关的用于求解多模态优化问题的技术； ( 3 ) 提出一种改进的混合小生境遗传算法； ( 4 ) 用g a 性能测试函数对新算法进行测试，对结果进行分析； ( 5 ) 总结与展望。 本文具体的章节内容组织如下： 第一章，绪论，主要对所研究的问题的背景、现状、存在的问题和改进进行 了综述和分析，论述了研究的意义、目的和思路； 第二章，介绍了小生境遗传算法的基本原理、流程及研究现状，分析了小生 境遗传算法的特点； 第三章，介绍本文所需的一些相关的算法和工作； 第四章，提出的改进的混合小生境遗传算法： 第五章，用性能测试函数对算法进行分析； 第六章，总结和进一步的研究。 天津大学硕士学位论文 第二章小生境遗传算法的研究 遗传算法是j o h nh o l l a n d 于1 9 7 5 年受生物进化论的启发而提出的。它在许 多复杂优化问题的应用中提供了鲁棒的寻优技术。但是在用基本遗传算法( g a ) 求解多峰值函数的优化计算问题时，经常收敛于局部最优解，但是引入小生境机 制的遗传算法在解决这类问题时有着良好的性能。 2 1 遗传算法简介 2 1 1 遗传算法的基本原理 遗传算法是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。 在自然界的演化过程中，生物体通过遗传、变异来适应外界环境，一代又一代地 优胜劣汰，发展进化。遗传算法则模拟了上述进化现象，它把搜索空间映射为遗 传空间，即把每一个可能的解编码为一个向量，称为一个染色体，向量的每一个 元素称为基因。所有染色体组成群体，并按预定的目标函数对每个染色体进行评 价，根据其结果给出一个适应度的值。算法开始时先随机地产生一些染色体，计 算其适应度，根据适应度对各染色体进行选择复制、交叉、变异等遗传操作，剔 除适应度低( 性能不佳) 的染色体，留下适应度高( 性能优良) 的染色体，从而 得到新的群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良 性态，因而明显优于上一代。遗传算法就这样反复迭代，向着更优解的方向进化， 直到满足某种预定的优化指标。 2 1 2 遗传算法的基本描述 遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。 在遗传算法中，基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作 和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。它以编 码空间代替问题的解空间，以适应度函数为评价依据，以编码群体为进化基础， 以对群体中个体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程。在 这一过程中，通过随机重组编码位串中重要的基因，使新一代的位串集合优于老 一代的位串集合，群体的个体不断进化，逐渐接近最优解，最终达到求解问题的 第二章小生境遗传算法的研究 目的5 1 。 遗传算法的基本流程如图2 1 所示 图2 1 简单遗传算法基本流程图 遗传算法的基本步骤如下： ( 1 ) 选择编码策略，把参数集合x 和域转换为位串结构空间s ； ( 2 ) 定义适应值函数厂( x ) ； ( 3 ) 确定遗传策略，包括选择群体大小n ，选择，交叉，变异方法，以及 确定交叉概率见，变异概率p 。等遗传参数； ( 4 ) 随机初始化群体p ； ( 5 ) 计算群体中个体位串解码后的适应值厂( 五) ： ( 6 ) 按照遗传策略，运用选择，交叉和变异算子作用于群体，形成下一代 群体； ( 7 ) 判断群体性能是否满足某一指标，或者一完成预定迭代次数，不满足 天津大学硕士学位论文 则返回步骤( 6 ) ，或者修改遗传策略再返回步骤( 6 ) 【5 】。 种群中的每一个体都对应问题的可行解，个体的适应值函数也就对应了问题 的目标函数。 基本遗传算法的主要操作为： 1 ) 编码与译码 g a 的编码就是解的遗传表示，它是应用g a 求解问题的第一步。g a 在进 行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据。这种将解 空间的解数据变换成位串形式编码表示的过程叫做编码；相反地，将位串形式编 码表示成原解空间的解数据的过程叫做译码。 d e j o n g 依据模式定理，提出较为客观明确的编码准则：有意义的积木块编 码规则，即所定编码应当易于生成与所求问题相关的短距和低阶的积木块；最小 字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或描述。 近来一些学者从理论上证明了推导最小字符集编码规则时存在的错误，指出大符 号集编码可提供更多的模式。参考文献 1 6 】研究了二进制编码和十进制编码在搜 索能力和保持群体稳定性上的差异，结果表明二制编码比十进制编码搜索能力 强，但不能保持群体稳定性。 遗传算法中最常用的编码方式有二进制编码、实数编码。遗传算法中进化过 程是建立在编码机制基础上的，编码对于算法的性能如搜索能力和种群多样性等 影响很大。就二进制编码和浮点数编码比较而言，一般二进制编码比浮点数编码 搜索能力强，但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样 性。 2 ) 初始群体的生成 随机产生n 个初始串结构数据，每个串结构数据便是一个个体，n 个个体 构成了一个群体。遗传算法以这n 个串结构数据作为初始点开始迭代。 初始群体中的个体一般是随机产生的。在不具有关于问题解空间的先验知识 的情况下，很难判定最优解的数量及其在可行解空间中的分布状况。因此我们往 往希望在问题解空间均匀采样，随机生成一定数日的个体( 为群体规模的2 倍， 即2 n ) ，然后从中挑出较好的个体构成初始群体。 另外，对于带约束域的问题，还需要判定随机初始化位串所对应的参数点是 否在可行区域范围之内，所以一般必须借助于问题领域知识。 3 ) 个体的适应度评价 遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则。必 须对个体串中的适应性进行评价。因此，适应函数( f i t n e s sf u n c t i o n ) 就构成了 个体的生存环境。根据个体的适应值，就可决定它在此环境下的生存能力。一般 第一章小生境遗传算法的研究 来说，好的染色体位串结构具有比较高的适应函数值，即可以获得较高的评价， 具有较强的生存能力。基本遗传算法按与个体适应度成正比的概率来决定当前群 体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求 所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定 好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数 值为负数时的处理方法。 4 ) 遗传算子 遗传算法的操作算子一般都包括选择、交叉、变异三种基本形式，它们构成 了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中发生的繁 殖、杂交和突变现象的主要载体。遗传算法利用遗传算子产生新一代群体来实现 群体进化。选择也叫复制，其目的是从当前群体中选出优良的个体，使它们有机 会作为父代为下一代繁殖子孙。选择充分体现了达尔文的适者生存的进化原则。 一般地，经过选择操作，适应度较大( 优良) 的个体将有较大的存在机会，而适 应度较小( 低劣) 的个体继续存在的机会较小。交叉操作是遗传算法中最主要的 遗传操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。 交叉体现了信息交换的思想。变异操作首先在群体中随机选择一个个体，对于选 中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，遗 传算法中变异发生的概率很低，通常取值在0 0 0 1 0 0 1 之间，此概率便是变异 概率p 。变异为新个体的产生提供了机会。需要指出的是，当交叉操作产生的 后代个体的适应值不再比它们的父代更好，但又未达到全局最优解时，就会发生 成熟前收敛或早熟收敛。这时引入变异算子往往能产生较好的效果。一方面，变 异算子可以使全体进化过程中丢失的等位基因信息得以恢复，以保持群体中的个 体差异性，防止发生成熟前收敛：另一方面，当种群规模较大时，在交叉操作基 础上引入适度的变异，也能够提高遗传算法的局部收敛效率。 2 1 3 遗传算子 标准遗传算法的操作算子一般包括选择( s e l e c t i o n ，或复制r e p r o d u c t i o n ) 、 交叉( c r o s s o v e r ，或重组r e c o m b i n a t i o n ) 和变异( m u t a t i o n ) 三种基本形式。 1 1 选择( s e l e c t i o n ) 选择即从当前群体中选择适应值高的个体以生成交配池( m a t i n gp 0 0 1 ) 的过 程。目前，主要有适应值比例选择( f i m e s s - p r o p o r t i o n a t es e l e c t i o n ) 、b o l t z m a n n 选择、排序选择( r a n ks e l e c t i o n ) 、联赛选择( t o u r n a m e n ts e l e c t i o n ) 等形式。为 了防止由于选择误差，或者交叉和变异的破坏作用而导致当前群体的最佳个体在 下一代的丢失，d ej o n g 提出了精英选择( e l i t i s ts e l e c t i o n ，o re l i t i s m ) 策略。另 天津大学硕i l ：学位论文 外，g a 在机器学习等领域应用过程中，h o l l a n d 等专家提出了稳态选择方法 ( s t e a d y - s t a t es e l e c t i o n ) 。 2 ) 交叉( c r o s s o v e r ) 交叉操作是进化算法中遗传算法具备的原始性的独有特征。g a 交叉算子是 模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一 代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤： a ) 从交配池中随机取出要交配的一对个体； b ) 根据位串长度l ，对要交配的一对个体，随机选取 1 ，l 1 】中一个或多个 的整数k 作为交叉位置； c ) 根据交叉概率p 。( o 3 还可以由下式逼近( j o l l e y ，1 9 6 1 ) r 7 + l o g p ( 3 - 2 ) 这里y 0 5 7 7 ，这个值是相当小的，如果是p = 1 0 0 0 ，r 仅仅是7 5 。即便所有 最大值被搜索到的概率是不同的，尺的值会更高一些，但是也不会很大。 3 2 适应值共享机制 如第二章所述，g o l d b e r g 和r i c h a r d s o n 在1 9 8 7 年提出了一种基于适应值共 享机制的小生境技术【2 卯。其基本思想是：通过反映个体之间相似程度的共享函数 来调整群体中各个个体的适应度，从而在这以后的进化过程中，能够依据这个调 整后的新适应度来进行选择运算。这种调整适应度的方法能够限制群体内个别个 体的大量增加，以维护群体的多样性，并形成了一种小生境的进化环境。通过定 义群体中个体的共享度，采用适应值非线性标度变换调整个体的适应值，使得群 体同时保持多个高阶模式。共享函数是表示群体中两个个体之间密切关系程度的 一个函数，例如，个体基因型之间的海明距离就可定义为一种共享函数。这里个 天津大学硕t z 学侮论文 体之间的密切程度主要体现在个体基因型的相似性或者个体表现型之间的相似 性上。当个体之间比较相似时，其共享函数值就比较大( 接近于i ) ，反之，当 个体之间不大相似时，其共享函数就比较小( 接近于0 ) 。由于单个个体无限接 近自身，所以它的共享函数是l 。然后确定每个个体在群体中的共享度。一个 个体的共享度等于该个体与群体内的其他个体之间相互的共享函数值的总和。第 二章已经给出了关于适应值共享小生境的相关的一些概念。 共享模型是一种特殊的非线性适应值标度变换，其依据是群体中个体之间的 相似性。在相邻区域内的很多个体相互增加了共享函数值，也就是相互削弱了适 应度。其结果就是，限制了同一“物种”在种群中的无控制的增长，有利于维护 种群的多样性。 该算法计算步骤如下： 步骤l ：初始化( 建立初始种群，确定遗传参数) ； 步骤2 ：计算个体的适应度； 步骤3 ：遗传操作( 选择，交叉，变异) ： 步骤4 ：计算当前群体中每个个体的共享度： 步骤5 ：依据上式重新计算种群个体的适应度； 步骤6 ：比较子代与父代之间的适应度大小； 步骤7 ：用新产生的个体去替换原来种群中的个体，形成新的当前群体； 步骤8 ：如果未满足算法终止条件则返回步骤3 ，否则，算法终止。 但该方法需要事先知道多峰值函数最优解的个数，并且其复杂度达到 o ( n 2 ) 一玎为群体规模。1 9 9 1 年o e i 介绍了几种降低算法复杂度的方法，主要是 以在群体中选取几个个体作为样本代替计算所有个体间的相似度，但每个小生境 都要限定个体的最大数型2 9 1 。 3 3 聚类算法 聚类是人类一项最基本的认识活动。通过适当聚类，事物才便于研究，事物 的内部规律才可能为人类所掌握。所谓聚类就是按照事物的某些属性，把事物聚 集成类，使类间的相似性尽可能小，类内相似性尽可能大【3 0 】。聚类是一个无监督 的学习过程，它同分类的根本区别在于：分类是需要事先知道所依据的数据特征， 而聚类是要找到这个数据特征，因此，在很多应用中，聚类分析作为一种数据预 处理过程，是进一步分析和处理数据的基础。“物以类聚，人以群分”。聚类是一 个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就 必须区分不同的事物并认识事物间的相似性。 第三章多模态优化问题的解决技术 1 ) 分裂法( p a r t i t i o n i n gm e t h o d s ) ：给定一个有n 个元组或者纪录的数据集，分 裂法将构造k 个分组，每一个分组就代表一个聚类，k l 时曲线是凹的，口 1 时曲线是凸的，口= 1 时是一个线性函数) 。，当d ：。= 0 ， g 。( 工，s ) = o 时在等式( 4 3 ) 中m 是递减函数的最小值，在丸= 0 时决定g 的值， ( 即g ( x ，s ) = m ) 。m 的值必须大于0 ，因为。聊的值同时也决定了递减曲线的 向下凹的程度，m 值越小曲线向下凹的程度就越大。对于这两种形式，当d 。， 时，设g ( x ，s ) = 1 。 删= o 甜 2 ， 第四章混台小生境遗传算法 e ( ，j ) 图4 1 和 b l 2 f e x p ( i o g m ( r 一丸) r ) 矿d 。 r 1 1d 抽e n v d e 图4 - 2 表示了几条幂函数和指数函数的递减曲线( ，= 1 图4 - 1 幂甬数适应值递减曲线 舡3 4 - 2 指数函数适戍值递减曲线 j。vgu口ulep口 天律人羊硕 学位论文 g o l d b e t g 和p d c h a r d s o n ( 1 9 8 7 ) ，d e b ( 1 9 8 9 ) 以段d e b 和g o l 曲e r g ( 1 9 8 9 ) 描述的共享适应值函数利用一个个体和种群l 】的其他个体之间的距离来降低个 体的适应值的。而适应值卜降函数是利用个体和之前找到的最优个体之间的距离 来降低个体的适应值的。 用图4 - 3 解释上述说法，原始函数为f c x ) = s i n2 ( 2 y r x ) ，它之后的修正函数是 乘以一个以x = 02 5 为中心的单峰递减函数，这个单峰递减函数用r = 02 5 及 口= 2 的幂曦数， 图4 - 3 用递减函数削去其中的一个峰 我们发现人的峰已经被削去了，取代的是两个小的峰：我们可以用增人a 的 值使引进的峰值变得任意小。但是a 的要是太大的话是会有危险的。 削采用自适麻控制手段确定小生境半径r 的值。将峰半径当作优化变量的一 部分编码到每个个体的染色体中进行演化计算，遗传算法在对多峰问题进行优化 的同时，也埘峰半径进行自适廊调整，从而使得戍1 1 l 适麻值共享遗传算法时不需 要事先给定峰的数目或峰的半径。自适应峰半径控制方法的基本思想是将适应值 共享遗传算法中每个个体的峰半径当作个决策变量，时其进行编码和连接编码 串的工作，使之参与优化的全过程。设峰半径编码长度为4 ，峰半径的定义域是 原决策变量中最大定义