（计算机应用技术专业论文）动态概率粒子群优化算法研究.pdf

东南大学博士学位论文 摘要 最优化问题在人类社会的诸多领域普遍存在，随着科学研究和应用需求的不断发展，在工程实践和 科学研究中涌现出很多复杂的最优化问题，同时最优化问题的规模也在不断扩大，传统的最优化方法在 求解这类问题时往往具有较大的局限性，而随着计算技术的不断进步，求解复杂优化问题的各种智能优 化方法应运而生。 粒子群优化( p s 0 ) 算法作为一种较新的智能优化方法，其思想主要来源于两方面，一是人工生命 的研究，特别是对鸟群、鱼群等群体行为机制的研究：二是进化计算的思想，p s o 算法与其它经典的进 化算法一样，均为基于种群的方法，通过种群的不断进化寻找最优解。p s o 算法的优势在于，其基本概 念较为简单，采用实数值编码，没有复杂的数学操作，对计算机的硬件速度和存储要求并不高，易于在 计算机中编程实现。p s o 算法以其优势吸引了大批研究者对其开展了理论和应用方面的探索，目前p s o 算法作为优化工具已被引入诸多工程领域。然而，p s o 算法作为一种较新的算法，在应用于工程实践的 过程中仍然有很多值得改进和提高之处，比如算法的执行性能、稳定性、并行机制、粒子群邻域拓扑等 等，同时，p s o 算法作为一种仿生进化算法，其工作机制和理论基础也有待深入的研究。本文结合一类 新的p s o 算法变体动态概率粒子群优化( d p p s o ) 模型，对算法的参数设置、改进策略、多种群策 略、粒子群邻域拓扑以及理论基础等多方面进行了深入细致的研究。论文的主要研究成果如下： ( 1 ) 结合新的种群产生方式，抽象出动态概率粒子群优化( d p p s o ) 模型，给出了该模型的形式 化描述，分析了d p p s o 模型的特点，并提出了d p p s o 模型可以采用的动态概率进化算子，通过在标准 测试函数上的实验验证了d p p s o 模型及所提出的动态概率进化算子的有效性，同时根据实验结果给出 了动态概率进化算子设计与选择的指导建议。 ( 2 ) 对基于d p p s o 模型的算法( d p p s o 算法) 进行了理论分析，第一，基于差分方程理论对d p p s o 算法中粒子的轨迹进行了分析，讨论了粒子轨迹的稳定性；第二，基于种群适应度值标准差、种群位置 标准差和种群熵等概念刻画了d p p s o 算法中粒子群的种群多样性，分析了d p p s o 算法运行时种群多样 性的变化情况，进而对影响种群多样性的因素进行了讨论。 ( 3 ) 对d p p s o 算法的参数设置和种群设定进行了讨论，并提出了基于d p p s o 算法的三种改进策 略。具体地，第一，结合对d p p s o 算法中粒子轨迹分析所得到的结论，给出了d p p s o 算法中一些重要 控制参数设置的参考建议；第二，讨论了初始种群的几种产生方式，并对种群规模的取值作了相应的分 析；第三，结合d p p s o 算法的特点，提出了三种可行的改进策略，分别是基于变异策略的改进、基于 选择策略的改进和基于混合优化策略的改进，并分别通过实验验证了三种改进策略的有效性。 ( 4 ) 提出了两种基于d p p s o 算法的多种群策略，分别是异构多种群策略和基于群体重组的多种群 策略，两种策略分别适用于不同的应用场合，实验结果验证了两种多种群策略的有效性。 ( 5 ) 对粒子群的邻域拓扑结构进行了较为深入的研究，针对d p p s o 算法的特点，引入了一种新的 邻域拓扑结构多簇结构，并基于多簇结构提出了可变拓扑策略用以协调勘探和开采，实验表明采用 基于多簇结构的可变拓扑策略的d p p s o 算法优势明显，同时还从理论上分析了最优信息在各种邻域拓 扑结构中的传播，最后从图论角度分析了各种粒子群邻域拓扑的统计特性。 最后，对本文的工作进行了总结，提出了值得进一步研究的内容和方向。 本文的研究成果丰富了p s o 算法研究领域的内容，理论方面的研究成果有助于深刻理解p s o 算法 的工作机制和理论基础，很多研究结论可以为p s o 算法应用于工程实践提供有益的参考。 关键词：粒子群优化；动态概率粒子群优化；粒子轨迹；种群多样性；混合优化；多种群；邻域拓扑 东南大学博士学位论文 a b s t r a c t o p t i m i z a t i o np r o b l e m s a r e u b i q u i t o u s i nt h ev a r i o u sf i e l d so fs o c i e t y a n dm a n yn e wc o m p l e x o p t i m i z a t i o np r o b l e m se m e r g e dw i t ht h ei n c r e a s i n gr e q u i r e m e n t so fs c i e n t i f i cr e s e a r c ha n da p p l i c a t i o n w h e n s o l v i n gt h e s ep r o b l e m s ，t r a d i t i o n a lo p t i m i z a t i o nm e t h o d so f t e nh a v es o m el i m i t a t i o n s c o n s e q u e n t l y , a l o n gw i t h t h ed e v e l o p m e n to f c o m p u t e rt e c h n o l o g y , s e v e r a li n t e 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 m ei n t ob e i n g 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 l g o r i t h mi sar e l a t i v e l yn e wi n t e l l i g e n to p t i m i z a t i o nm e t h o d ，w h i c hi s i n s p i r e db ya r t i f i c i a ll i f ea n de v o l u t i o n a r yc o m p u t a t i o n t h em a i na d v a n t a g eo fp s ol i e si nt h a ti ti se a s yt o d e s c r i b e ，s i m p l et oi m p l e m e n ta n dt h e r ea r ef e wp a r a m e t e r st oa d j u s t c u r r e n t l y , p s oh a sb e e na p p l i e dt om a n y a r e a s h o w e v e r , t h e r ea r es t i l lr o o m sf o ri m p r o v e m e n tw h e na p p l y i n gp s ot oe n g i n e e r i n gp r a c t i c e ，s u c ha s p e r f o r m a n c e ，s t a b i l i t y , p a r a l l e lm e c h a n i s ma n dn e i g h b o r h o o dt o p o l o g y m e a n w h i l e ，t h ew o r k i n gm e c h a n i s m a n dt h e o r e t i c a lf o u n d a t i o no fp s oa l s on e e dt ob ef u r t h e ri n v e s t i g a t e d i nt h i sp a p e r , v a r i o u sa s p e c t sa r e i n v e s t i g a t e ds y s t e m a t i c a l l yb a s e do nan e wv a r i a n to fp s o d y n a m i cp r o b a b i l i s t i cp a r t i c l es w a r mo p t i m i z a t i o n ( d p p s o ) ，w h i c hi n c l u d ep a r a m e t e rs e t t i n g , i m p r o v e m e n ts t r a t e g y , m u l t is w a r ms t r a t e g y , n e i g h b o r h o o dt o p o l o g y a n dt h e o r e t i c a la n a l y s i s t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： ( 1 ) t h ed y n a m i cp r o b a b i l i s t i cp a r t i c l es w a r mo p t i m i z a t i o nm o d e l ( d p p s o ) i sc o n s t r u c t e db a s e do nt h e n e wp o p u l a t i o ng e n e r a t i o nm e t h o da c c o r d i n gt oh i s t o r i c a li n f o r m a t i o na b o u tp a r t i c l e s ，a n dt h ef o r m a l d e s c r i p t i o no fd p p s om o d e li sp r o p o s e d ，s e v e r a ld y n a m i cp r o b a b i l i s t i ce v o l u t i o no p e r a t o r sa r ea l s od e s i g n e d f o rr e a l i z a t i o no fd p p s om o d e l e x p e r i m e n tr e s u l t so nb e n c h m a r kf u n c t i o n sd e m o n s t r a t et h ee f f e c t i v e n e s so f d p p s om o d e la n dt h ep r o p o s e de v o l u t i o no p e r a t o r s a n dt h es u g g e s t i o no nd e s i g n i n ge v o l u t i o no p e r a t o r si s p r o v i d e da sw e l l ( 2 ) t h et h e o r e t i c a la n a l y s i si sp r e s e n t e dt oi n v e s t i g a t ed p p s om o d e l f i r s t l y , t h es t a b i l i t yo fp a r t i c l e t r a j e c t o r yi nd p p s oa l g o r i t h mi sa n a l y z e db a s e do nd i f f e r e n t i a le q u a t i o nt h e o r y ；s e c o n d l y ，p o p u l a t i o nd i v e r s i t y i nd p p s oa l g o r i t h mi sd e t a i l e dd i s c u s s e d ，w h i c hi sm e a s u r e db yt h es t a n d a r dd e v i a t i o no ff i t n e s sv a l u e s ，t h e s t a n d a r dd e v i a t i o no fp o s i t i o n sa n dp o p u l a t i o ne n t r o p y ( 3 ) p a r a m e t e rs e t t i n ga n dp o p u l a t i o ns e t t i n go fd p p s oa l g o r i t h ma r ed i s c u s s e d ，a n dm o r e o v e r s e v e r a l i m p r o v e m e n ts t r a t e g i e sa r ep r o p o s e d m o r es p e c i f i c a l l y , a tf i r s t , t h es u g g e s t i o no np a r a m e t e rs e t t i n go fd p p s o i sp r o v i d e db a s e do nt h ea n a l y s i sr e s u l t so fp a r t i c l et r a j e c t o r y ；s e c o n d l 5p o p u l a t i o ni n i t i a l i z a t i o nm e t h o da n d p o p u l a t i o ns i z ea r ed i s c u s s e d ；t h i r d l y , t h r e ee f f e c t i v ei m p r o v e m e n ts t r a t e g i e sa r ep u tf o r w a r d ，w h i c hi n c l u d e m u t a t i o n b a s e di m p r o v e m e n t , s e l e c t i o n b a s e di m p r o v e m e n ta n dh y b r i do p t i m i z a t i o ns t r a t e g y ( 4 ) t w om u l t is w a r ms t r a t e g i e sa r ep r e s e n t e db a s e do nd p p s oa l g o r i t h m ，w h i c hi n c l u d eh e t e r o g e n e o u s m u l t is w a r ms t r a t e g ya n dm u l t is w a r ms t r a t e g yb a s e do np o p u l a t i o nr e c o m b i n a t i o n a n dt h et w os t r a t e g i e sa r e s u i t a b l ef o rd i f f e r e n ta p p l i c a t i o nf i e l d s t h es i m u l a t i o nr e s u l t sv e r i f i e dt h ee f f e c t i v e n e s so f t h et w os t r a t e g i e s ( 5 ) ad e e pr e s e a r c hi sd o n eo nt h en e i g h b o r h o o dt o p o l o g yo fp a r t i c l es w a n n m o r ep r e c i s e l y , a c c o r d i n gt o t h ec h a r a c t e r i s t i co fd p p s oa l g o r i t h m ，an o v e ln e i g h b o r h o o dt o p o l o g ys t r u c t u r ei si n t r o d u c e d ，c a l l e dm u l t i c l u s t e rs t r u c t u r e m o r e o v e r av a r y i n gn e i g h b o r h o o ds t r a t e g yb a s e do nm u l t ic l u s t e ri sp r o p o s e dt oc o o r d i n a t e e x p l o r a t i o na n de x p l o i t a t i o n a n de x p e r i m e n t a ls i m u l a t i o nr e s u l t sd e m o n s t r a t et h a td p p s oa l g o r i t h mw i t ht h e v a r y i n gn e i g h b o r h o o dt o p o l o g yc a n s o l v e c o m p l e xo p t i m i z a t i o np r o b l e m se f f i c i e n t l y f u r t h e r m o r e ，t h e i n f o r m a t i o nd i s s e m i n a t i o ni ns e v e r a ln e i g h b o r h o o dt o p o l o g i e si sa n a l y z e dt h e o r e t i c a l l y , a n dt h es t a t i s t i c a l p r o p e r t i e so fs e v e r a ln e i g h b o r h o o dt o p o l o g i e sa r ea n a l y z e db a s e do ng r a p ht h e o r y f i n a l l y , as u m m a r yo fc o n t r i b u t i o n so ft h et h e s i sa r ep r e s e n t e d ，s o m et o p i c sf o rf u t u r er e s e a r c ha r ea l s o p o i n t e do u t t h er e s e a r c hr e s u l t so ft h i st h e s i sw i l lc o n t r i b u t et od e e p l yu n d e r s t a n dt h ew o r k i n gm e c h a n i s ma n d t h e o r e t i c a lf o u n d a t i o n ，a n ds o m er e s u l t sw i l lp r o v i d eu s e f u lr e f e r e n c ef o ra p p l y i n gp s ot oe n g i n e e r i n gp r a c t i c e k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ；d y n a m i cp r o b a b i l i s t i cp a r t i c l e $ w a r n lo p t i m i z a t i o n ；t r a j e c t o r yo f p a r t i c l e ；p o p u l a t i o nd i v e r s i t y ；h y b r i do p t i m i z a t i o n ；m u l t is w a r m ；n e i g h b o r h o o dt o p o l o g y n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 期：垃，潞 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 期：、甘- 够 第l 章前言 1 1 研究背景 第1 章前言 群智能( s w a r l l ii n t e l l i g e n c e ) 方法作为近年来新兴的一种计算智能方法，目前正成为人工智能研究 中的热点。群智能方法源于对自然界中鸟类、鱼类、蚂蚁、蜜蜂等生物群体行为机制的研究，生物个体 的行为较为简单，但大量简单个体之间通过协作可以表现出复杂的行为特性，完成复杂的任务。群智能 方法中最具代表性的是j a m e sk e n n e d y 和r u s s e l le b e r h a r t 1 ，2 j 提出的粒子群优化算法以及m a r c od o r i g o 等 人p 1 提出的蚁群优化算法。 粒子群优化算法( 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 算法) 是j a m e sk e n n e d y 和 r u s s e l le b e r h a r t 于1 9 9 5 年提出的一种仿生进化算法i l 2 j ，目前作为一种良好的优化方法已经被广泛地应 用到工程优化领域1 4 j 。 p s o 算法根源于人工生命的研究，特别是受到了鸟群、鱼群等群体行为机制的启发，并借鉴了生物 学家以及计算机专家所提出的生物群体模型1 5 鲥，同时也融入了进化计算的思想。最初p s o 算法被用于 函数优化以及神经网络的训练【l 】，此后研究者们采用不同的策略对基本p s o 算法进行改进，开发了不同 版本的p s o 算法作为优化工具并成功地应用于诸多领域。 p s o 算法问世十多年来，吸引了国内外很多研究者和研究机构对p s o 算法的理论和应用进行了多方 面的探索。近年来与计算智能相关的国内国际会议都将p s o 算法作为重要的主题之一，关于p s o 算法 的研究成果也越来越多地发表在国内外高水平学术刊物上。从1 9 9 8 年开始，进化计算领域的著名会议 i e e ec e cf c o n g r e s s0 ne v o l u t i o n a r yc o m p u t a t i o n ) 开始设置了p s o 算法的专题讨论会。与计算智能相关 的重要国际会议p p s n ( p a r a l l e lp r o b l e ms o l v i n gf r o mn a t u r e ) 和g e c c o ( g e n e t i ca n de v o l u t i o n a r y c o m p u t a t i o nc o n f e r e n c e ) 都将p s o 算法作为会议的重要主题之一，并对其最新的研究成果进行报道。2 0 0 1 年以后，相继有关于粒子群优化算法的专著问世，比如2 0 0 1 年的4 ( s w a r mi n t e l l i g e n c e ) ) 1 7 j 以及2 0 0 6 年 的( p a r t i c l es w a r mo p t i m i z a t i o n ) ) i s j 。2 0 0 3 年，第一届群智能研讨会i e e es w a r mi n t e l l i g e n c es y m p o s i u m 在美国的i n d i a n a p o l i s 召开，此后每年召开一次，而p s o 算法作为群智能方法中的典型代表，是会议所 讨论的主要内容。2 0 0 4 年，进化计算领域的权威学术刊物i e e et r a n s a c t i o n so ne v o l u t i o n a r y c o m p u t a t i o n ) ) 出版了p s o 算法特刊，报道了p s o 算法研究的阶段性重要研究成果。国内的研究者在p s o 算法研究领域也取得了很多优秀的研究成果，这些成果发表在国内外的高等级学术期刊以及相关的学术 会议上，近期国内也有关于粒子群优化算法研究的中文专著p j 出版。至此，p s o 算法已经成为计算智能 领域中的重要研究课题。 p s o 算法基本概念较为简单，算法需要调整的参数不多，易于在计算机中编程实现，而且算法本身 没有复杂的数学操作，对计算机硬件的速度和存储要求不高。已有的关于p s o 算法的理论和应用研究成 果说明p s o 算法可以有效解决很多复杂优化问题，p s o 算法作为一种仿生算法，目前还没有形成系统的 分析方法和坚实的理论基础，但其作为一种新兴的最优化方法已经在工程优化领域展现了良好的应用前 景。因此，无论在理论研究还是应用研究方面，p s o 算法的理论和应用研究都具有重要的学术意义和现 实价值。 本章首先介绍与最优化相关的一些知识背景，包括最优化问题和最优化方法，蚁群优化算法和粒子 群优化算法的基本原理，其次分析p s o 算法的研究现状以及p s o 算法研究面临的问题，最后是本文的 研究思路和研究内容，以及本文的章节组织。 东南大学博士学位论文 1 2 知识背景 p s o 算法主要用于求解复杂优化问题，本节主要介绍一些与p s o 算法研究相关的背景知识，内容主 要包括最优化问题数学模型的一般形式、最优化问题的分类、传统的最优化方法以及几种典型的智能优 化算法。 1 2 1 最优化问题 人们一直以来都对“极致”、“最优”有着不懈的追求，“尽善尽美”、“止于至善”这些古老的词汇无 不闪耀着人们追求完美，寻求最优的理想和信念，而与这些追求相关的事物或问题则存在于人类社会的 方方面面。工程问题中设计参数的选择，要求设计方案满足各种要求又要使成本最低；有限资源的合理 分配，要求满足多方面的需求又能产生最大的收益；车间作业调度，要求完工时间最短；物流调度，要 求设计最优配送路径；交通系统的规划，要求交通的合理布局；等等，诸如此类的问题不胜枚举。 最优化问题则是从人们所追求的这些极致的事物或问题中抽象出来的数学模型，自然科学以及社会 实践中的很多问题都可以归结为最优化问题，最优化问题因此与人类的日常生活、生产实践以及社会经 济等各个领域息息相关。 1 2 1 1 最优化问题的一般形式 下面给出最优化问题数学模型的一般形式【l o l ，如公式( 1 1 ) 所示。 i r a i n 厂( x ) ， j ，e ( 工) = o ，f = l ，2 ，p ， ( 1 1 ) 【 q ( 工) 0 ，f = p + 1 9 * o o ，7 在公式( 1 1 ) 中，f 缸l ，x 2 ， ，砌) 矿，乒妒- r 1 ，c i ：妒一r 1 ( f _ l ，2 ，肌) 。工是决策变量，触) 为 目标函数，c ， ) 则是约束函数。c ， ) = 0 ( i = 1 ，2 ， ，p ) 称为等式约束，c ，0 ) 0 ( 昀升1 ，m ) 称为不等式约束。 决策变量x 的取值受到约束条件以) = 0 和c 舡) 邳的限制。 若令集合忙驯c 肛) = 0 ，i = i ，2 ，p ，c 肛) i 0 ，昀时l ，朋，x 妒) ，最优化问题的形式又可写为 r a i 。n 厂( x )( 1 2 ) j e j 在公式( 1 2 ) 中，s 为可行域。如果向量x s ，则称x 为可行解。 最优化问题就是在约束条件c 删( i = l ，2 ， ，p ) 和c 肛) 之0 ( 昀时l ，肌) 下，目标函数舡) 的极值求 解问题。 1 2 1 2 最优化问题的分类 最优化问题根据其约束、目标函数、变量等情况，一般有以下几种分类方法： 1 按有无约束条件分类 在最优化问题模型( 1 1 ) 中，如果没有约束条件，即可行域肛妒，则最优化问题( 1 1 ) 称为无约束最优 化问题；如果含有约束条件，则最优化问题( 1 1 ) 称为约束最优化问题。 具体地，对于约束最优化问题，如果模型( 1 1 ) 中只有等式约束，没有不等式约束，则称模型( 1 1 ) 为 等式约束最优化问题：如果模型( 1 1 ) 中没有等式约束，只有不等式约束，则称模型( 1 1 ) 为不等式约束最 优化问题；如果模型( 1 1 ) 中既含有等式约束，又含有不等式约束，则称模型( 1 1 ) 为混合约束最优化问题。 2 第1 牵前言 2 按目标函数和约束函数的特性分类 在最优化问题模型( 1 1 ) 中，如果目标函数舡) 以及约束函数c ，0 ) 均为线性函数，则称模型( 1 1 ) 为线性 规划；如果目标函数触) 以及约束函数c 舡) 中至少有一个是非线性函数，则称模型( 1 1 ) 为非线性规划。 在非线性规划中，如果约束函数c 均为线性函数，则称模型( 1 1 ) 为线性约束非线性规划问题；更 为特别地，如果目标函数触) 为二次函数，而约束函数c 均为线性函数时，称模型( 1 1 ) 为二次规划； 如果目标函数触) 以及约束函数c 舡) 均为决策变量x 的广义多项式，则称模型( 1 1 ) 为几何规划。 3 按照目标函数的个数分类 在最优化问题模型( 1 1 ) 中，如果目标函数r x ) = q l 伍) ，五 ) ，石) 1 ，p 2 _ 2 ，即目标函数r x ) 是决策变 量工的一个向量函数，则称模型( 1 1 ) 为多目标规划问题，否则模型( 1 1 ) 为单目标规划问题。很多实际问 题可以归结为多目标规划问题。 4 按决策变量的情况分类 在最优化问题模型( 1 1 ) 中，如果决策变量x 的分量只能取某些离散值，则称模型( 1 1 ) 为离散优化问 题；否则称为连续优化问题。对于离散优化问题，如果要求决策变量工的取值为整数值，则称模型( 1 1 ) 为 整数规划问题。 在最优化问题模型( 1 1 ) 中，如果决策变量x 是时间的函数，则称模型( 1 1 ) 为动态规化问题：否则称 为静态优化问题。 1 2 1 3 凸集和凸函数 凸集和凸函数是最优化理论中的基本概念，在最优化理论和方法的研究中起着重要的作用，下面给 出凸集和凸函数的定义1 1 0 】。 定义1 1 ( 凸集) 设集合s cr ”，如果垤，y s ，并且v 盯( 0 ，1 ) ，有 口x + ( 1 - a ) y s 则称集合s 是凸集。 定义1 2 ( 凸函数) 设集合s 为非空凸集，厂为定义在尺上的实函数。 有 f ( a x + ( 1 - a ) y ) 口，( _ x ) + ( 1 - a ) f ( y ) ( 1 3 ) 如果垤，y s 以及v 口( 0 ，1 ) ， ( 1 4 ) 则称触) 是凸集s 上的凸函数。 凸集和凸函数具有良好的分析性质，这些性质以及和凸集、凸函数相关的定理对最优化方法的理论 分析有着非常重要的意义。 1 2 1 4 全局最优解和局部最优解 下面给出最优化问题的全局最优解和局部最优解【1 0 l 的定义。 定义1 3 ( 全局最优解) 设s 为最优化问题的可行域，工+ s ，如果垤s ，都有触) 狐) 成立，则 称f 是最优化问题的全局最优解( 极小点) 。 定义1 4 ( 局部最优解) 设s 为最优化问题的可行域，工+ s ，如果存在，的一个万( 万 o ) 邻域 以( x ) = 圳i i x - z o o ) ，称集合a = x e s l l 俺) 次如l 占) 为可接受解的集合。 从全局最优解和局部最优解的定义可知，全局最优解一定是局部最优解，但局部最优解不一定是全 局最优解。求解最优化问题，就是要得到最优化问题的全局最优解。然而在求解实际问题时，人们往往 3 东南大学博士学位论文 期望在可接受的时间内求得全局最优解，但在实际的计算中，一般不太可能在有限的时间内求解得全局 最优解，而对于一些工程问题而言，可接受解已经满足了问题的要求，因此可接受解的概念在最优化方 法的研究中非常重要。 1 2 2 最优化方法 为求解最优化问题，研究者们开发了各种不同的求解方法，这些方法称为最优化方法。最优化方法 本质上是一种搜索策略，它基于某种思想或机制，通过搜索解空间来获得满足要求的最优化问题的解。 最早的最优化方法可以追溯到1 7 世纪时，求解函数极值问题所提出的l a g r a n g e 乘数法；1 8 4 7 年法国数 学家c a u c h y 提出了最速下降法；而直到2 0 世纪三四十年代k a n t o r o v i c h 和d a n t z i g 提出线性规划问题的 求解方法之后，最优化才逐步成为- - f 7 独立的学科。其后关于最优化问题的理论研究发展迅速，新的求 解方法不断出现，针对线性规划、动态规划、整数规划等最优化问题提出了很多经典的最优化方法；而 随着应用需求的不断扩展，在工程实践和科学研究中出现了许多更为复杂的最优化问题，这些问题往往 具有多约束、非线性、多局部极小、建模困难等特点，且最优化问题的问题规模也在不断扩大，因此探 求适合大规模复杂优化问题的算法成为最优化方法研究领域的重要课题。而2 0 世纪后半页以来出现的一 些新颖的优化算法，比如禁忌搜索、遗传算法、人工神经网络、模拟退火、蚁群优化算法及粒子群优化 算法等，这些智能优化算法在求解复杂优化问题时展现了特殊的优势，智能优化算法的工作机制一般受 到自然现象或生物智能行为的启发，为求解最优化问题提供了新的思路和手段。 下面给出求解几类最优化问题的传统算法，并对几种典型的智能优化算法的工作原理作简要的介绍。 1 2 2 1 经典的最优化方法 对于不同类型的最优化问题，有对应的不同的最优化方法。针对研究较多的几类最优化问题，图1 1 列出了这些最优化问题以及求解相应问题时常用的经典最优化方法【1 1 ，12 1 。 砷9 ， 单纯形法 大m 法 ， j，7 0 一一一 悻 j i、 可行方向法 j 梯度方法 罚函数法 乘子法 最速下降法 9 - 牛顿法 共轭梯度法 变尺度法 睁砂 - 约束法 评价函数法 查多 分支定界法 割平匝法 隐枚举法 圈1 1 几类经典最优化问题及对应的经典最优化方法 这些经典最优化方法一般只适合求解规模较小的问题，其计算复杂性一般较高，在求解大规模复杂 优化问题时有较大的局限性。 4 第l 章前言 1 2 2 2 智能优化算法 随着科学研究与工程应用需求的不断发展，传统的最优化方法在求解新出现的复杂优化问题时往往 具有较大的局限性，研究者们开始寻求适合大规模复杂优化问题的最优化方法。人们从一些自然现象和 过程以及生物学现象中受到启发，提出了许多用以求解复杂优化问题的智能优化方法。图1 2 给出了较 为常用的一些智能优化算法，这些算法的工作原理与机制涉及生物学、物理学、社会学和神经科学等多 个学科领域，为求解复杂优化问题提供了新的角度。智能优化算法的优势和独特的工作机制也引起了国 内外学者的广泛关注和研究，并且在诸多领域都获得了成功应用。 图1 - 2 常用的智能优化算法 以下介绍几种典型的智能优化算法l l3 ，1 4 】，包括模拟退火算法、遗传算法、进化策略、进化规划、文 化算法以及群智能方法。 1 模拟退火算法 模拟退火( s i m u l a t e da n n e a l i n g ，简称s a ) 算法是k i r k p a t r i c k 等i l 纠于1 9 8 3 年研究组合优化问题时提 出的，其求解最优化问题的思路源于物理学中固体物质的退火过程与最优化问题之间存在的相似性。退 火是指将固体材料加热后再以一定速度冷却，在固体加热的过程中，粒子的热运动加剧，而当温度足够 高时，固体将熔解为液体，这时粒子处于高能态，粒子可以自由运动，然后再缓慢冷却，在冷却的过程 中粒子渐趋有序，并在每个温度都达到平衡态，最后粒子热运动减弱，在常温时粒子形成低能态的晶格。 退火使得粒子有可能找到系统能量比原先更低的位置。固体在等温下热平衡的过程可以用m o n t ec a r l o 方法模拟，但计算量非常大。m e t r o p o l i s 等【l6 j 在1 9 5 3 年提出了重要性采样法，以概率接受新状态，称为 m e t r o p o l i s 准则，计算量相对m o n t ec a r l o 方法显著减少。k i r k p a t r i c k 等所提出的模拟退火算法中，其对 等温过程的模拟正是受到了m e t r o p o l i s 准则的启发。 在s a 算法中，固体的退火过程对应于最优化问题的求解过程，解对应于粒子的状态，内能对应于 目标函数值，温度可以作为控制参数。求解最优化问题时，从初始解和初始温度开始，基于m e t r o p o l i s 抽样方法在解空间中进行随机搜索，同时随着温度的不断降低重复抽样过程，直至获得最优化问题的全 局最优解。 s a 算法的求解过程简单描述如下： ( 1 ) 确定初始温度靠( 令脚) ，随机产生初始状态( 初始解) ： ( 2 ) 在温度时，重复以下操作，直至满足抽样稳定准则： 由当前状态产生新状态； 基于m e t r o p o l i s 准则依照概率接受新状态； ( 3 ) 更新温度，砭+ l - - - - u p d a t e ( 哟，令t = - c + 1 ，判断是否满足算法终止条件，如果满足，则退火过程 结束，输出最优解；否则转步骤( 2 ) 。 5 东南大学博士学位论文 从s a 算法的步骤可以看出，新状态的产生、新状态的接受、初始温度和退温函数、抽样稳定准则 以及算法终止条件是直接影响算法性能的主要环节，对s a 算法的改进可以从这些环节入手。s a 算法目 前在理论上被证明以概率l 收敛于全局最优解，而且已经在工程中获得了较为广泛的应用。 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是h o l l a n d 【1 1 于1 9 7 5 年受生物进化论思想的启发而提出的一种最 优化方法。进化论认为生物的进化是“适者生存，优胜劣汰”的自然选择过程，环境适应能力强的物种 个体更容易生存下去并繁衍后代；遗传学方面的成就也揭示了进化的某些特征，染色体存在复制、交叉、 变异等行为特性。遗传算法融入了进化论和遗传学中的这些概念，并将其引入到最优化问题的求解过程， 算法开始时随机初始化一组个体( 每个个体都是最优化问题的候选解) ，然后通过评价函数评价每一个个 体的“优劣”，一般评价函数和最优化问题的目标函数相关，再对群体中的个体执行选择、交叉和变异操 作，通过迭代寻找最优值。 遗传算法求解最优化问题时，一般步骤描述如下： ( 1 ) 随机产生一组个体，构成初始种群； ( 2 ) 用评价函数计算每一个个体的适应度值； ( 3 ) 判断是否满足算法终止条件，如果满足则输出最优解，否则执行以下步骤； ( 4 ) 根据个体适应度值按照某种特定规则在群体中执行选择操作； ( 5 ) 按交叉概率肼在群体中执行交叉操作； ( 6 ) 按变异概率砌在群体中执行变异操作； ( 7 ) 执行步骤( 3 ) 。 遗传算法和模拟退火的单个初始解迭代不一样，它是一种基于种群的方法，群体中的每一个个体都 是候选解，一般采用二进制编码；评价函数则与最优化问题的目标函数存在对应关系，用以评价群体中 每一个个体的适应度值；选择操作一般按照一定比例进行，而个体被选择的概率则和个体的适应度值相 关，一般适应度值较优的个体被选择在下一代中复制自身的概率比较大，从而可以提高整个种群的质量； 交叉操作通过交换父代个体的信息构成新的后代个体，使得后代个体可以继承父代的有效模式，从而有 可能产生新一代的优良个体；变异操作通过随机改变个体中的某些基因位从而产生新的个体，这样可以 有效增强种群的多样性，避免算法的早熟收敛现象。 在遗传算法中，种群规模，选择、交叉、变异操作的具体工作方式等都会对算法的效率与性能产生 影响。种群规模太小，则不足以在解空间中提供足够的采样点，种群规模太大则会增加计算量，增加实 际应用时算法所需的时间耗费：选择策略一般包括：轮盘赌策略，比例选择，竞争选择，最优个体选择 等：交叉操作的方式一般有单点交叉、两点交叉、多点交叉、均匀交叉和算术交叉等，交叉操作对前代 基因进行重新组合并产生新的个体，可以在解空间中进行有效搜索；变异操作的方式一般是将个体的某 些基因位按一定的概率作变动，对于二进制编码的遗传算法来说就是取反操作，变异操作可以作为控制 算法早熟收敛的有效手段，因此变异策略的选择对算法性能有很大的影响。 目前遗传算法已经被应用到多个工程领域【l4 1 ，当前对遗传算法的研究主要集中在算法的收敛性分 析，算法关键参数的设置