（计算机软件与理论专业论文）现代智能优化方法研究与应用.pdf

中山大学博士学位论文 现代智能优化方法研究与应用 专业：计算机软件与理论 博士生：周雅兰 指导老师：印鉴教授 摘要 最优化技术在科学、工程等领域都有极广泛的运用，受到了理论界和工程界 的广泛关注和深入研究，优化理论与算法的研究已成为一个具有理论意义和应用 价值的重要热点课题。现代智能优化方法模仿自然现象运行机制而产生，它们的 出现为解决复杂工程问题提供了新的思路和手段。 现代智能优化方法可以分为基于群体搜索和基于单点搜索两大类，本文从这 两大类中各选出一种有代表性的算法进行研究，这两种算法分别是粒子群优化算 法和h o p f i e l d 神经网络。 粒子群优化算法已经成功用于解决连续优化问题，但是一直未能有效地解决 组合优化问题。为此，本文基于分布估计算法的思想，提出了两种离散粒子群优 化算法：一种是基于分布估计的离散粒子群优化算法，一种是基于分布估计的离 散量子行为粒子群优化算法。此外，还在基于分布估计的离散粒子群优化算法中 引入混沌离散h o p f i e l d 神经网络，来进一步提高算法的性能。提出的新算法被用 于解决理论上的经典组合优化问题，如二分图问题、无约束二进制二次规划问题， 并设计了应用于特征选择问题的框架。仿真结果显示了新算法的良好性能。 随着实际优化问题的复杂度越来越大，对优化算法的性能要求越来越高。最 优化理论领域的“无免费午餐”定理说明算法的混合是提高性能的有效手段，因 此有机地结合各种算法的优点提出高效的优化算法是值得重视的有价值的课题。 本文提出了三种不同混合策略的粒子群优化算法：具有通用局部搜索的量子行为 粒子群优化算法、量子协同进化粒子群优化算法和基于多智能体的遗传粒子群优 化算法。用这三种混合算法分别解决连续函数优化问题、背包问题和二分图问题， 来验证算法的优化性能。 h o 叩e i d 神经网络采用的梯度下降法本质上是一种局部搜索方法，网络常常 中山大学博士学位论文 陷入局部最小值，所以网络的稳定状态并不一定对应于问题的最优解。本文为了 更好地解决聚类划分问题，提出了一种随机竞争h o p n e i d 神经网络。提出的算法 其网络能量不仅能依据梯度下降的方法从整体上保证减小的趋势，而且由于引入 的随机动态，使得网络能量也有增加的可能性，从而使网络有能力跳出局部最小 值。本文详细分析了引入的随机动态性对算法性能的影响，通过有效地控制随机 动态的运行机制使算法获得了良好的性能。在聚类划分问题上的应用结果，显示 了提出算法的良好性能。本文还提出了一种混合随机竞争h o p f i e i d 神经网络应用 于解决系统工程领域中的可靠性优化问题，实验结果证明了算法的良好性能。此 外本文还分析了前人提出的正自反馈h o p f i e l d 神经网络，指正了其理论与实验结 果解释不一致的错误并在c r o s s b a r 互连问题上验证了我们的分析结论。 关键字：智能优化方法，组合优化问题，分布估计算法，粒子群优化算法， 混合算法，h o p n e i d 神经网络 i i i 中山大学博士学位论文 r e s e a r c ha n da p p i i c a t i o no nm o d e r ni n t e i l i g e n t o p t i m i z a t i o nm e t h o d s m a j o r ：c o m p u t e rs o r w a r ca n dt h e o 哆 n a m e ：y a i a nz h o u s u p e r v i s o r ：j i a ny i n ( p r o f e s s o r ) a b s t r a c t t | h eo p t i m i z a t i o nt c c h n i q u e sh a v e b e c na p p l i e dt oaw i d er a n g e o fs c i e n c e ， e n g i n e e r i n gf i e l d sa n ds oo n t h e s et e c h ni q u e sh a v ea t t r a c t e dal o to fa t t e n t i o n s6 o m t h er e s e a r c h e r si nb o t ht h e o 叫a n de n g i n e e r i n gf i e l d s t h eo p t i m i z a t i o nt h e o 呵a n d a l g o r i t h m sh a v eb e e nah o tr e s e a r c ht o p i c i nb o t ht h e o r ya n da p p l i c a t i o na r e a s t h e m o d e mi n t e l l i g e n t o p t i m i z a t i o nm e t h o d sh a v ei n s p i r e db yn a t u r e ， w h i c hh a v e s u p p l i e dw a y sf o rs o l v i n gm a n yc o m p l e xp r o b i e m si ne n g i n e e r n gn e l d s t h em o d e mi n t c l l i g e n to p t i m i z a t i o nm e t h o d sc a nb ec a t e g o r i z e di n t ot 、】 r ok i n d s ： p o p u l a t i o n b a s e ds e a r c ha l g o r t h m s ，a n dp o i n t b a s e ds e a r c ha l g o r i t h m s t h ep a p e r c o n c e n t r a t e st h er e s e a r c ho nt w or e p r e s e n t a t i v ea l g o r i t h m s 仔o mt h et w oc a t c g o r i e s ： p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a n dh o p f i e l dn e u i o nn e t w o r k ( h n n ) t h ep s oh a l sb e e na p p l i e ds u c c e s s m i i yt oc o n t i n u o u so p t i m i z a t i o np r o b l e m ，b u t i th a ss o m ed i f n c u l t i e si ns o l v i n gc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m 。s ot h ep a p e r p r o p o s e st 、 ，o d i s c r e t ep s o sc o m b i n e dw i t h e s t i m a t i o no fd i s t r i b u t i o na i g o r i t h m ( e d a ) ：o n ei sd i s c r e t ep s ob a s e do ne s t i m a t i o no fd i s t r i b u t i o n ( d e d p s 0 ) ，t h eo t h e r i sd i s c r e t eq u a n t u m - b e h a v e dp s o b a l s e do ne s t i m a t i o n o fd i s t r i b u t i o n ( d q b p s 0 - e d a ) m o r e o v e r ，t h ep a p e ri n c o r p o r a t e sac h a o t i cd i s c r e t eh n n ( c d h n n ) i n t ot h ed e d p s ot oi m p r o v ei t sp e r f - o r m a n c e t h e s ep r o p o s e da l g o r i t h m sa r ea p p i i e d t os o l v et h et h e o r e t i c a lc i a s s i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ， s u c ha s b i p a n i t es u b g r a p hp r o b l e m ，u n c o n s t r a i n e db i n a 叫q u a c l r a t i cp r o g r a m m i n gp r o b l e m ， a n da r ed e s i g n e di n t of e a t u r es e l e c t i o np r o b i e m t h es i m u i a t i o nr e s u i t ss h o wt h e s e p r o p o s e da i g o r i t h m sh a v eg o o dp e r f o n n a n c e i v 中山大学博士学位论文 a st h ec o m p l e x i 够o fp r a c t i c a io p t i m i z a t i o np r o b l e mi n c r e a s e ，t h ei m p r o v e m e n t r c q u i r e m e n to fa l g o r i t h m sp e r f o r m a n c e h a sb e c o m e m u c hm o r eu 唱e n t i ti s c o n c i u d e df 幻m “n o 仔e el u n c h t h e o r e mi no p t i m i z a t i o nf i e i dt h a tt h eh y b r i d i z a t i o n o no p t i m i z a t i o na i g o r i t h m si sav e 呵e f r e c t i v ew a yt oi m p r o v et h ea l g o r i t h m s p e r f o r m a n c e t h e r e f o r ei t i sas i g n i f i c a n tt o p i cb yr e a s o n a b i yc o m b i n i n gt h ev i r t u e s 锄o n gd i f | f e r e n ta l g o r i t h m s t h ep a p e rp r o p o s e st h r e ep s o sw i t hd i f f e r e n c eh y b r i d s t r a t e g i e s ：q b p s 0w i t hg e n e r a i i z e dl o c a ls e a r c ho p e r a t o r ，q u a n t u mc o e v o l u t i o np s 0 a n dg e n e t i cp s ob a s e do nm u l t i a g e n t 1 od e m o n s t r a t et h e i rp e r f o r m a n c e ，t h r e e a i g o r i t h m s a r ea p p l i e dt oc o n t i n u o u sf u n c t i o n o p t i m i z a t i o np r o b i e m ，k n a p s a c k p r o b l e ma n db i p a r t i t es u b g r a p hp r o b i e m ，r e s p e c t i v e l y t h eh n ni sai o c a is e a r c hi ne s s e n c eb yu s i n gg r a d i e n td e s c e n tw a y a n di th a s n om e c h a n i s mt oe s c a p ef 两ml o c a lm i n i m a t h e r e f o r e ，t h es t a b l es t a t eo ft h en e t w o r k d o e sn o tn e c e s s a r i l yc o l t e s p o n dw i t ht h eo p t i m a is o l u t i o no ft h ep r o b l e m t h ep a p e r p r e s e n t s as t o c h a s t i c o p t i m a lc o m p e t i t i v eh o p f i e i d n e t w o r k( s o c h o m )f o r p a r t i t i o n a lc l u s t e r i n gp r o b i e m t h en e t w o r ke n e r g yo ft h ep r o p o s e da i g o r i t h mi s n o t o n i yd e s c e n to ng r a d i e n td e s c e n tw a ya n dg u a r a n t e e6 n a l i yd e c r e a s e ，b u ta s c e n to nt h e s t o c h a s t i cd y n a m i c s t h e r e f o r e ，t h en e t w o r kh a v ec h a n c et oe s c a p ef r o mal o c a l m i n i m u m t h ep a p e ra n a l y s e st h ed y n a m i c so ft h eh i l i - c l i m b i n gd y n a m i c sa n ds h o w s h o wt h eh i l l c l i m b i n gd y n a m i c sh a se f r e c t so nt h ep e r f o r m a n c eo ft h ea i g o r i t h m ，t h e n g e t sg o o ds i m u l a t i o nr e s u l t sb yc o n t r o l l i n ge f r e c t i v e l yt h eh i i l c i i m b i n gd y n a m i c s t h ea p p i i c a t i o nr e s u l t so np a r t i t i o n a ic i u s t e r i n gp r o b i e ms h o wt h ep r o p o s e da i g o r i t h m h a sg o o dp e r f o r m a n c e t h ep a p e ra i s op r o p o s e dah y b r i ds o c h o mt os o i v et h e r e l i a b i i i t yo p t i m i z a t i o np r o b l e m i n s y s t e m se n g i n e e r i n g f i e i d s t h ep r o p o s e d a l g o r i t h mh a sg o o dp e r f o m l a n c ei nt h es i m u l a t i o n s b e s i d e s ，w ba i s oa n a l y s i st h e p o s i t i v e l y s e l g f e e d b a c ki _ 玎、f n p r o p o s e db yo t h e rr e s e a r c h e r s ，p o i n to u tt h a t t h e i r t h e o 叫a r ei n c o n s i s t e n tw i t ht h es i m u l a t i o nr e s u i t s ，a n dv e r i f yo u ra n a i y s i sr e s u i to n c r o s s b a rs w i t c h i n gp r o b l e m k e y w o r d s ： m o d e mi n t e i l i g e n to p t i m i z a t i o nm e t h o d ， c o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m ，e s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m ，p a r t i c l es w a r mo p t i m i z a t i o na i g o r i t h m ， h y b r i da l g o r i t h m ，h o p f i e l dn e u r o nn e t w o r k v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：碌堆琶 日期：z n 秒年6 月 五日 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定， 即：学校有权保留学位论文并向国家主管部门或其指定机构 送交论文的电子版和纸质版，有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以 采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：懈 日期：冲8 年i 占月日 导师签名： 日期：舻多月日 中山大学博士学位论文 1 1 研究背景及意义 第一章绪论 在人类几乎所有的社会实践活动中都有“寻优 的需求，所谓“寻优一就是 指在满足一定的约束条件下，寻找一组参数值，以使系统的某些性能指标达到最 大或者最小。在工业、社会、经济、管理、军事等各个领域都大量存在着这种最 优化问题。优化方法是一种以数学为基础，用于求解各种工程最优化问题的应用 技术，因此优化方法的理论和技术研究受到人们的广泛重视。最优化问题根据优 化变量的取值类型不同可以分为连续优化问题和组合优化问题两大类。随着科学 技术的日益发展，组合优化问题与日俱增，越来越受到运筹学、应用数学、计算 机科学及管理科学等诸多学科领域研究的高度重视。虽然某些组合优化问题有悠 久的历史渊源，被费马( f e r m a t ) 、欧拉( e u l e r ) 等众多著名数学家研究过，但作为 运筹学的一个独立分支而发展壮大起来还是近几十年的事。 众所周知，在计算机科学、工程学和管理科学等学科以及许多实际应用领域 都不断涌现出许多复杂的组合优化问题。在面对一些大型问题时，传统的优化方 法如牛顿法、共轭梯度法、模式搜索法、单纯形法、r o s e n b r o c k 法和p o w e l l 法， 需要遍历整个搜索空间，从而会产生搜索的组合爆炸，即无法在多项式时间内完 成搜索。也就是说，对于这些问题，不存在多项式时间复杂性的算法以获取最优 解，属于n p _ 难优化问题。因此，鉴于实际工程问题的复杂性、约束性、非线性、 建模困难等特点，寻求具有高效的优化算法已成为有关学科的一个主要研究目标 和引人注目的研究方向。 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络 1 2 、遗传 算法 3 及群体智能算法 4 5 等，通过模拟或揭示某些自然现象或过程而得到 发展，其思想和内容涉及数学、生物进化、人工智能、神经科学和量子统计学等 方面，为解决复杂工程问题提供了新的思路和手段。这些算法独特的优点和机制， 引起了国内外学者的广泛重视并掀起了该领域的研究热潮。在优化领域，由于这 些算法构造的直观性与自然机理，被统称为现代智能优化方法。它们的出现孕育 了许多新的计算机技术和解决问题的方法，对于无法用数学模型精确描述的问 中山大学博士学位论文 题，或有些参数事先无法知道的情况，也有较好的应用效果。这些性质是所有传 统最优化方法都缺乏的，因而现代智能优化方法的出现大大地丰富了最优化技 术，也为那些用传统的最优化技术难以处理的组合优化问题提供了切实可行的解 决方案。 目前对现代智能优化方法的研究集中在三个方面：一是对现有智能优化算法 的改进和广泛应用，以及对其理论的深入、广泛研究；二是开发新的智能优化工 具，拓宽其应用领域，并对其寻求理论基础；三是各种现有智能优化算法的混合。 至今已涌现出许多智能优化算法，涉及的应用领域也不断增多，如模式识别、智 能控制、计算机安全、计算机网络、投资组合等等，而对于算法性能( 精度和速 度) 提高的追求永远是无止境的，因此提高现有智能优化算法处理各种工程问题 的性能，以及对其进行理论研究便成为当前智能优化算法研究的首要任务，也是 现代智能优化方法研究的热点。 1 2 组合优化问题 不失一般性，设所考虑的最优化问题为： m i n ( x ) s t x s = x ig ( x ) o 其中，厂( x ) 为目标函数，g ( ) 为约束函数，s 为约束域，x 为优化变量。当 优化变量取离散值时，上述最优化问题为组合优化问题或离散优化问题，特 别地当x 取值为0 或l 时，上述优化问题为0 1 整数规划问题。 组合优化是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序 或筛选等，是运筹学中的一个经典且重要的分支 6 。它的应用包括诸如资源分 配，生产安排，资金预算，空间计算，证券组合分析以及诸如通讯，运输网络设 计，超大规模集成电路设计等问题。最近，它还被应用到分子生物学，高能物理 等尖端科技领域。而在数学上，它可应用到组合学，图论，逻辑等分支。如今， 组合优化技术已渗透到工商企业管理，工程技术等众多领域 7 。 以前对于一般性的组合优化问题求解方法的研究进展很慢。但是，当今社会 经济和科技日新月异的发展生产的急剧扩大与全球化，各种企业、组织在规模 中山大学博士学位论文 和复杂性上的迅速增长与变化，使得人们必须开发一些新的优化技术与方法，来 精确或者妥善的处理实际当中面临的日益复杂的各种大规模优化问题以及实时 优化问题。因此，对组合优化问题在理论、方法和应用上的进一步深入研究就越 来越显示出其重要性。所以，无论是从理论研究还是从实际工程应用的角度来看， 组合优化问题现在已经逐渐成为最优化领域的一个研究热点 7 。 本文求解的典型组合优化问题有二分图问题、无约束二进制二次规划问题、 特征选择问题、背包问题、聚类划分问题、可靠性优化问题和c r o s s b a r 互连问题。 1 3 本文的工作 现代智能优化方法的种类繁多，根据不同的性质可以给出不同的分类，按照 搜索方式的不同可以分为基于群体搜索和基于单点搜索两大类。本文在这两大类 中各选一种有代表性的算法进行了研究，这两种算法是粒子群优化算法和 h o p f i e l d 神经网络算法。本文的工作如图卜1 所示，对这两种算法的具体研究成 果如下： 算法的应用 无的柬二进制二次规划 群鬻器 问韪 i 特征选择问置 i 二分圈向量 l 1 1 ”4 “1 ”“6 l 。一- 背包问置 i 网 粒 。 。7 | 贿鸯幽嚣| 罕协同排拈越芊群桡北篁法 1 子 群 爿羹 优 化 算 现 l 一法 _ 代 1 智 、基于多智甓茬鐾篓传粒子群 连续优化阔量 能 优 化 ； 随机竞争h 。p n e l d 神经同绻 i i 聚类划分问息 l 方 法 ； 虽 点 h o p - 搜- 厅e i d 混和随机竞争h 叩f i e l d 神经网络1可靠性优化问置 神经 索 一绻 分析前人提出的正自反馈h o p f i c i dl c m s s b a r 互连目量 神经网络 图卜l 本文工作 中山大学博士学位论文 一、提出了一种基于分布估计的离散粒子群优化算法。 粒子群优化算法已经成功地应用于求解连续优化问题，但是一直未能有效地 解决组合或离散优化问题。提出的离散粒子群优化算法基于分布估计算法的思 想，突破了传统粒子群优化算法速度一位移搜索模型的局限，有效地把粒子群优 化算法拓展到解决组合优化问题的领域。 二、在基于分布估计的离散粒子群优化算法中引入神经网络。 由基于分布估计的离散粒子群优化算法进行全局搜索产生优质解，再由混沌 离散h o p f i e l d 神经网络对产生的优质解的邻域进行局部开采。算法既利用了混沌 离散h o p f i e l d 神经网络的混沌动态性来脱离局部极小值，又利用了h o p f i e l d 神 经网络梯度下降的特性来加快算法的收敛速度。实验结果表明引入神经网络后提 高了算法的性能。 三、提出了一种基于分布估计的离散量子行为粒子群优化算法。 好的进化算法是既能利用搜索空间的全局信息又能利用至今发现的局部信 息。提出的算法产生新解的机制既依据分布估计算法统计得到的全局信息，又依 据离散量子行为粒子群优化算法搜索获得的局部信息，从而使算法能获得更优质 的解。应用于无约束二进制二次规划问题的实验结果表明提出的算法具有比其他 进化算法更好的性能。 四、提出了一种具有通用局部搜索的量子行为粒子群优化算法。 算法具有的全局搜索能力使得算法能广泛地搜索新的可行解区域，有助于保 持解的多样性，避免发生早熟收敛；算法具有的局部开采能力使得算法能在优质 解的邻域进行细搜索，提高了算法的收敛性和解的质量。因此，一个好的优化策 略是维持算法全局搜索能力和局部开采能力之间的某种平衡。提出的新算法遵循 均衡全局搜索和局部开采能力的思路，首先由主量子行为粒子群优化算法进行全 局搜索产生当前代种群的最优解，再在当前代最优解的邻域内用微型量子行为粒 子群优化算法进行局部细搜索。新算法应用于求解连续函数优化问题，求解结果 显示新算法比其他几种算法具有更好的性能。 五、提出了一种量子协同进化粒子群优化算法。 现有的量子粒子群优化算法，用于评估量子个体适应度的二进制个体信息没 有被充分利用，算法很容易陷入局部最小值或达到早熟状态。提出的新算法利用 中山大学博士学位论文 了二进制个体的信息，在量子个体进化的同时，采用遗传粒子群优化算法使个体 在二进制空间进行三路均匀交叉和按位方式变异操作，使种群在量子空间和二进 制空间协同进化，是一种微空间( 量子空间) 和宏空间( 二进制空间) 的混合搜索 策略。新算法应用于理论上的典型组合优化问题背包问题，显示了良好的性能。 六、提出了一种基于多智能体的遗传粒子群优化算法。 多智能体系统主要研究在逻辑或物理上分离的多个智能体如何能并发计算、 相互协作地实现问题求解。粒子群优化算法是对生物群体内各个体之间的交互和 协作的建模，因此粒子群优化算法能被看成是一个多智能体系统。但是种群中每 个粒子自身的智能特性，还没有完全被利用。提出的新算法中一个智能体代表遗 传粒子群优化算法中的一个粒子，同时也代表优化问题的一个候选解，粒子( 智 能体) 通过相互竞争、相互合作以及自我学习，来达到个体行为的优化，从而能 更快地获得问题的最优解。实验结果表明了利用粒子群优化算法中粒子的竞争、 合作及自学习的智能特性对于提高算法性能的潜力。 七、提出了一种求解聚类划分问题的随机竞争h o p f i e l d 神经网络。 聚类划分问题已经被证明是一个n p 难优化问题，本文研究用h o p f i e l d 神经 网络对该问题进行求解。但是由于h o p f i e l d 神经网络采用的梯度下降法本质上是 一个局部搜索方法，网络常常陷入局部极小值，所以网络的稳定状态并不一定对 应于问题的最优解。本文改进h o p f i e l d 神经网络，在网络中增加了随机动态特性， 形成了随机竞争h o p f i e l d 神经网络。这个提出的新算法能克服h o p f i e i d 神经网 络容易陷入局部极小值的问题，因为其网络能量不仅能依据梯度下降的方法从整 体上保证减小的趋势，而且由于随机动态特性，使得网络能量也有增加的可能性， 从而使网络能够有能力跳出局部最小值。本文详细地分析了随机动态特性对算法 性能的影响，从而能够通过有效地控制该特性使算法拥有良好的性能。实验结果 表明提出的新算法在求解聚类划分问题时能得到良好的聚类效果。 八、提出了一种混合随机竞争h o p f i e l d 神经网络求解可靠性优化问题。 可靠性优化问题是指在满足一定可靠性要求的条件下，如何尽可能降低成 本，取得最大经济效益的问题，它是系统设计、研究和运行过程中必须考虑的关 键因素之一。本文把随机竞争h o p f l e l d 神经网络和具有迟滞特性的量化h o p f i e l d 神经网络相结合，提出了一种混合随机竞争h o p f i e i d 神经网络求解可靠性优化问 中山大学博士学位论文 题。首先用具有两类神经元的神经网络构造该问题的目标函数：一类是具有随机 竞争机制的二进制神经元；另一类是具有迟滞特性的量化神经元，然后按照两类 神经元各自的演化方式对目标函数进行优化。最后求解了成本约束条件下、和成 本以及权重约束条件下的两种可靠性优化问题，实验结果显示了算法的良好性 能。 九、分析了前人提出的正自反馈h o p f i e l d 神经网络，指正了其理论与实验结 果解释不一致的错误。 2 0 0 5 年，l i 等人在h o p f i e l d 神经网络中增加了一个取正值的自反馈项，提 出了一种正自反馈h o p f i e l d 神经网络，并且在c r o s s b a r 互连问题上进行了实验， 证明了其提出算法的良好性能。本文经过理论分析证明，l i 等人提出的算法能 取得良好性能的原因，并不是因为l i 等人所分析的这个正自反馈的计算属性， 而是因为这个正自反馈在求解c r o s s b a r 互连问题时碰巧与该问题能量函数中固 有的负反馈适度中和，产生了轻微振荡，成为了具有脱离局部极小值能力的迟滞 神经网络。基于我们的理论分析，考虑到c r o s s b a r 互连问题能量函数中固有的负 反馈强度，给这个正自反馈设置更加适当的值，在求解c r o s s b a r 互连问题时取得 了更好的结果。 1 4 本文的组织结构 本文共分为六章，章节组织如下： 第1 章介绍相关研究背景和意义，包括对组合优化问题的介绍，以及本文 的工作和本文的组织结构。 第2 章介绍四种典型的现代智能优化方法：遗传算法、差分进化、粒子群 优化算法和神经网络。 第3 章研究离散粒子群优化算法。提出了两种离散粒子群优化算法：一种 是基于分布估计的离散粒子群优化算法，一种是基于分布估计的离散量子行为粒 子群优化算法，并在基于分布估计的离散粒子群优化算法中引入神经网络来进一 步提高算法的性能。同时把提出的新算法分别应用于不同的理论上的经典组合优 化问题，来显示提出算法的良好性能。 第4 章研究混合粒子群优化算法。有机地结合不同算法的优点提出了三种 中山大学博士学位论文 不同混合策略的混合粒子群优化算法：具有通用局部搜索的量子行为粒子群优化 算法、量子协同进化粒子群优化算法和基于多智能体的遗传粒子群优化算法，并 分别应用于求解连续函数优化问题、背包问题和二分图问题。 第5 章研究h o p f i e l d 神经网络。提出了求解聚类划分问题的随机竞争 h o p f i e l d 神经网络，同时提出混合随机竞争h o p 行e l d 神经网络应用于可靠性优化 问题，并分析了前人提出的正自反馈h o p f i e l d 神经网络，指正了其理论与实验结 果解释不一致的错误，在c r o s s b a r 互连问题上验证了分析的结论。 第6 章总结本文研究的主要内容以及对今后研究工作的展望。 最后是参考文献，博士期间发表( 录用) 的论文以及致谢。 中山大学博士学位论文 2 1 引言 第二章现代智能优化方法概述 现代智能优化方法的主要思想来自于人类经过长期对物理、生物、社会的自 然现象仔细的观察和实践，以及对这些自然现象的深刻理解，并逐步向大自然学 习，模仿其中自然现象的运行机制而得到的。因此，现代智能优化方法的特点就 是仿自然，如仿人类思维( 神经网络、禁忌搜索等) 、仿生物行为( 粒子群优化、 蚁群优化等) 和仿物理原理( 模拟退火、微正则退火等) 。这些算法从随机的可行 初始解出发，采用优胜劣汰的策略，在可接受的计算成本内去搜寻最好的解。虽 然这些算法不能保证最终一定能求得问题的精确最优解，但是它们能在搜索精度 和算法复杂度之间达到某种平衡，因此这些算法成为了解决优化问题特别是n p 难组合优化问题的一种有力工具，在优化领域得到了广泛地应用。 接下来的四个小节分别综述四种典型的现代智能优化方法：遗传算法、差分 演化、粒子群优化算法和神经网络。 2 2 遗传算法 近年来，基于自然选择和遗传学的进化计算方法在人工智能的研究中取得了 令人瞩目的成果。进化计算的典型算法就是遗传算法( g e n e t i ca i g o r i t h m ，g a ) 3 。 g a 是1 9 7 5 年由美国m i c h i g a n 大学的j h o i l a n d 博士首先提出的 3 ，在他 的研究中g a 的操作对象是一组二进制串，即种群。每一个二进制串称为一个染 色体或个体，每个染色体或个体对应于问题的一个解。从初始种群出发，采用某 种选择策略在当前种群中选择个体，并使用交叉和变异来产生下一代种群，如此 一代一代进化下去，直至满足期望的终止条件。 图2 一l 是g a 的基本流程图。 中山大学博士学位论文 图2 一l 遗传算法的基本流程图 g a 的基本设计步骤如下： ( 1 ) 确定问题的编码方式； ( 2 ) 确定适应度函数； ( 3 ) 遗传算子的设计； ( 4 ) 算法参数的选择； ( 5 ) 确定算法的终止条件。 下面按照设计步骤来介绍遗传算法。 ( 一) g a 的编码方式 按照g a 的设计步骤，当用g a 求解问题时，首先必须在目标问题实际表示 与g a 的染色体位串结构之间建立联系，即采用某种编码方式将解空间映射到编 码空间。目前g a 的主要编码方式有；二进制编码、实数编码、有序列编码、一 般数据结构编码等方式 8 。 二进制编码：将原问题的解映射到0 ，l 组成的编码串的表达空间，求解的 结果通过解码过程还原成原问题解空间的解，然后再计算其适应度值。 实数编码：将一个实参数矢量对应成一个染色体，一个实数对应一个基因， 一个实值对应成一个等位基因。十进制是连续优化问题直接的自然描述，当直接 9 中山大学博士学位论文 采用十进制的实数编码时，不再需要编码和解码过程。 有序列编码：整数和字母排列编码，互换编码可以用来解决排序问题，对于 组合优化问题最为有效。 一般数据结构编码：用合适的数据结构来表示基因的等位基因，适用于解决 复杂的现实问题，在这种情况下，基因可能是竹维数组或者更为复杂的数据结构。 g a 的编码方式遵循如下五个方面的原则 8 ： 1 完备性：对问题空间中的任何一个点有表达空间中的一个点与之对应，即问 题空间中的所有可能解都能表示为所设计的基因编码形式。 2 合法性：对表达空间中的任何一个点有问题空间中的一个点与之对应，即任 何一个基因编码都对应于一个可能解。 3 非冗余性：问题空间和表达空间一一对应。 4 l a m a r c k i a n 性质：某个基因的等位基因的含义不依赖于其他基因，即后代能 够从其父代继承优秀的品质。 5 因果性：表达空间中小的扰动在问题空间中也对应着小的扰动。 ( 二) g a 的适应度函数 适应度函数是评价个体适应环境的能力，是选择操作的依据，它由问题的目 标函数变化而成。g a 将问题空间表示为染色体位串空间，为了执行适者生存的 自然选择原则，必须对个体位串的适应性进行评价。适应度函数的值是群体中个 体获得生存机会的唯一确定性指标，因此适应度函数的形式直接决定着群体的进 化行为。一般来说，好的染色体结构可以获得较高的评价，具有较高的适应度函 数值，即具有较强的生存能力。为了能够直接将适应度函数与群体中的个体优劣 度量相联系，对适应度函数唯一的要求是：结果为非负值，这使得g a 能够应用 于不连续，不能求导的情况，大大增加了它的适用性。 ( 三) 遗传算子 遗传算法常用的遗传算子是：选择、交叉和变异三种算子，其中交叉和变异 是g a 中两个最基本的算子，决定着g a 的性能好坏。 选择算子 选择是根据达尔文的进化论，选择适应环境的( 好的) 基因生存下来，选择出 来的这些基因作为父代种群，用于交叉产生新的一代。选择算子的作用是使高性 l o 中山大学博士学位论文 能的个体有较大的概率生存从而提高全局收敛性和计算效率。 常用的选择方法有： 1 轮盘赌选择方法。轮盘赌选择方法是最知名的选择方式，其基本原理是每个 个体的选择概率和其适应度值成正比例。建立一个轮盘赌模型来表示这些选择概 率，选择的过程就是旋转轮盘若干次( 次数等于种群规模) ，每次为新种群选出 一个个体，适应度值越大的个体被选中的概率越高，因此也被称为适应度比例方 法。轮盘赌选择方法是随机采样过程。 2 ( + a ) 选择方法。( + 旯) 选择方法或( ，名) 选择方法是从父代和子代中 选择最好的个体，但是禁止该方法从种群中选取相同个体，因此常用于处理组合 优化问题，它是一种确定性选择过程。截断选择和区域选择也是确定性选择过程， 这两种方法根据适应度值对个体进行排序并从中选出最好的父代。 3 联赛选择方法。联赛选择方法同时包含随机和确定性特征，也称为竞争方法， 该方法从群体中任意选择一定数目的个体( 称为联赛规模) ，其中适应度最高的 个体保存到下一代，这一个过程反复执行，直到保存到下一代的个体达到预先设 定的数目为止。联赛规模一般取2 。 4 稳态选择方法。稳态选择方法是另一种方式的确定性选择，在这种方法中，玎 个最差的父代被子代替换( 以是子代个数) 。 5 最佳个体保存方法精英主义。每一次产生新一代时，不对群体中适应度最高 的最优个体进行交叉变异操作，而是首先把这个当前最优解原封不动的复制到新 的一代中，它可以确保最优秀的个体能够在新一代中得到保留。此方法一般和其 他方法结合使用。 6 比例变换与排序选择方法。最早提出的比例变换方法是将原始目标函数值映 射为正实数，每个个体的生存概率就根据这些正实数进行计算。目前已经有若干 种比例变换方法，根据将原始适应度值变换到比例变换适应度值的函数类型不 同，可以分为线性比例变换、s i g m a 截断、幂比例变换、对数比例变换等。排序 选择方法是一种直接基于适应度值的方法，这种方法对种群进行从好到差的排 序，然后根据每个个体的排序( 而不是原始适应值) 确定其选择概率。 7 共享选择方法。共享选择方法的目的是为了维持种群的多样性。共享函数是 一种用于根据个体在某个距离内与其他个体相邻的程度来确定该个体适应度值 中山大学博士学位论文 下降多少的方法。在求解多峰函数优化时，由于适应度值的下降，在拥挤的峰周 围的个体复制概率受到抑制，而其他个体则易产生后代。 交叉算子 交叉是把选择出来的两个父代个体的部分结构加以替换重组而生成新个体 的操作。交叉算子的作用是组合出新的个体，在串空间进行有效搜索，同时降低 对有效模式的破坏概率。交叉算子在g a 中起核心的作用，是g a 区别于其他进 化算法的重要特征。交叉操作的类型和实现是由编码方式和问题本身决定的。 下面按照不同的编码方式列出可采用的交叉操作： 1 二进制编码：可采用单点交叉、多点交叉、均匀交叉和算术交叉。单点交叉 指随机确定一个交叉位置，然后对换相应的变量；多点交叉指随机确定多个交叉 位置，然后对换相应的变量，产生两个新的后代，但在第一位变量与第一个交叉 点之间的一段不做对换：均匀交叉是单点和多点交叉的广义化；算术交叉是对父 代基因做个代数运算从而产生一个新的基因。 2 实数编码：可采用的交叉操作与二进制编码的一样。 3 有序列编码：可采用单交叉点交叉操作，即选择一个交叉点，子代从初始位 置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代 中没有，就把它添加进去。这种交叉操作的交叉点后面的部分可以有很多种具体 的方法。 变异算子 交叉重组之后是子代的变异，它是对群体中个体串的某些基因座上的基因值 作变动。变异本身是一种局部随机搜索，与选择交叉产生后代的方法结合在一起， 保证了g a 的有效性，使得算法具有局部搜索能力，同时使g a 保持种群的多样 性，以防止出现早熟收敛的情况。 下面按照不同的编码方式列出可采用的变异操作： 1