改进pso求解动态优化研究.pdf

中山大学 硕士学位论文 改进PSO求解动态优化研究 姓名：梁祥辉 申请学位级别：硕士 专业：软件工程 指导教师：衣杨 20100517 中山大学硕士论文改进P S O 求解动态优化研究 论文题目： 专业： 硕士生： 指导老师： 改进P S O 求解动态优化研究 软件工程 梁祥辉 衣杨副教授 摘要 动态优化问题( D y n a m i cO p t i m i z a t i o nP r o b l e m s ，D O P s ) 是在动态环境 ( D y n a m i cE n v i r o n m e n t s ，D E s ) 下的一类优化问题在最优化领域中，动态环 境指适值函数和约束条件均可能随时间变化的环境背景相对于传统的静态环境， 动态环境在现实的应用场景中更具广泛性进化算法( E v o l u t i o n a r y A l g o r i t h m s ， E A 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 ) 是一种基于群体智能的进化算法。

相对于 其他进化算法，P S O 具有收敛速度快和配置容易的优点求解动态优化问题主要 面临避免收敛成熟以及利用环境信息两点挑战目前，进化算法求解动态优化问 题的基本策略有多样性策略、记忆策略和多种群策略本文主要关注收敛成熟问 题、多样性策略和多种群策略 本文定义粒子搜索范围的有效性规则，并分别使用理论方法和实验方法对不 同P S O 参数选择的粒子搜索范围的有效性进行检验对于符合粒子搜索范围有 效性规则的参数选择，本文分析P S O 在动态环境下的不足，并提出一种新的改 进P S O 算法：带链结构的P S O 算法( P a r t i c l eS w a r mO p t i m i z a t i o nw i t hC h a i n S t r u c t u r e ，P S O C ) P S O C 通过粒子搜索范围对解空间每一维度的覆盖来提高群 体对环境变化的适应能力最后，在静态环境和动态环境下的基准测试问题对选 定的改进P S O 算法进行优化性能的对比研究实验结果说明P S O C 是～种收敛速 度较慢而稳定性较优的进化算法；P S O C 适用于环境变化周期较长的动态环境； P S O C 有效地解决收敛成熟问题和多峰值动态优化问题；多种群策略适用于变化 频率较高的动态环境；静态领域拓扑结构不适用于动态优化问题的求解；变化周 期越长的动态优化问题的求解难度越低。

关键字：人工智能，进化计算，粒子群优化算法，运筹学，动态优化问题 中山大学硕士论文改进P S O 求解动态优化研究 ’I W e ： M a j o r ： N a m e ： S u p e r v i s o r ： AM o d i f i e dP S Of o rD y n a m i cO p t i m i z a t i o nP r o b l e m s S o f t w a r eE n g i n e e r i n g X i a n g h u iL i a n g Y a n gY iA s s o c i a t eP r o f e s s o r D y n a m i co p t i m i z a t i o np r o b l e m s ( D O P s ) a r eo p t i m i z a t i o np r o b l e m si n d y n a m i ce n v i r o n m e n t s ( D Z s ) ．I no p t i m i z a t i o nr e s e a r c h ，D E sc a nb ed e s c r i b e da s t h e o p t i m i z a t i o np r o b l e m s w h o s ef i t n e s sf u n c t i o n sa n dc o n s t r a i n t sa r e t i m e —v a r y i n g ．C o m p a r e dw i t hs t a t i o n a r yo p t i m i z a t i o np r o b l e m s ，D O P sa r em u c h m o r ec o m m o ni nr e a l - w o r l d a p p l i c a t i o n s ．E v o l u t i o n a r ya l g o r i t h m s ( E A s ) p r o p o s e dw i t ht h ei n s p i r a t i o no fb i o l o g i c a le v o l u t i o n i s mi sas u b s e to fi n t e l l i g e n t c o m p u t a t i o n ．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 ) i sa nE Aw h i c hb a s e do ns w a r m i n t e l l i g e n c e ．C o m p a r e dw i t ho t h e rE A s ，P S Oc o n v e r g e sw i t hf a s t e rs p e e d ，a n di ti s s i m p l e rf o rc o n f i g u r a t i o n ．T h e r ea r et w om a i nc h a l l e n g e sf o rE A si nD E s ：t h eo v e r c o n v e r g e n c ep r o b l e ma n dt h eu s a g eo fe n v i r o n m e n ti n f o r m a t i o n ．C u r r e n t l y , d i v e r s i t ym a i n t a i n i n gs c h e m e ，m e m o r ys c h e m ea n dm u l t i —p o p u l a t i o n ss c h e m e a r eb a s i cs t r a t e g i e sf o rE A si nD E s ．T h et h e s i sm a i n l yf o c u s e so nt h eo v e r c o n v e r g e n c ep r o b l e m ，d i v e r s i t ym a i n t a i n i n gs c h e m e a n dm u l t i - p o p u l a t i o n s s c h e m e ． T h et h e s i sd e f i n e st h ev a l i dr u l ef o rs e a r c hr a n g eo fp a r t i c l e ，a n dt h e v a l i d i t i e so ft h er u l ei ns e t so fP S Op a r a m e t e r sa r ee s t i m a t e db yt h et h e o r e t i c a l m e t h o da n de x p e r i m e n t a lm e t h o d ．F o rt h es w a r m sw i t hv a l i dp a r a m e t e r s ．t h e w e a kp o i n t so fP S Oi nD E sa r ed i s c u s s e d ，a n dan o v e lm o d i f i e dP S Oi sp r o p o s e d ， w h i c hi sn a m e dp a r ' t i d es w a r mo p t i m i z a t i o nw i t hc h a i ns t r u c t u r e ( P S O C ) ．P S O C m a k e st h es w a r mm o r ea d a p t i v ef o rd y n a m i ce n v i r o n m e n tb yc o v e r i n ge v e r y 6 + d i m e n s i o no ft h es o l u t i o ns p a c e ．F i n a l l y , s e v e r a li m p r o v e dP S Oa r ec o m p a r e db y b e n c h m a r kp r o b l e m si ns t a t i o n a r ya n dd y n a m i ce n v i r o n m e n t s ．T h ee x p e r i m e n t a l r e s u l t ss h o wt h a tP S O Ci sa nE Aw i t hs l o wc o n v e r g e n c es p e e da n dg o o ds t a b i l i t y , a n dP S O Co u t p e r f o r m si nD Ew i t hl o n gc h a n g i n gp e r i o d ，a n dt h eo v e r c o n v e r g e n c ep r o b l e ma n dm u l t i - p e a k sD O P sc a nb es o l v e dm o r ee f f e c t i v eb y P S O C ，a n dm u l t i - p o p u l a t i o ns c h e m eo u t p e r f o r m si nD Ew i t hh i g hc h a n g i n g f r e q u e n c y , a n ds t a t i o n a r yn e i g h b o r h o o dt o p o l o g yi sn o ts u i t a b l ef o rP S Oi nD E ， a n dt h eD Ew i t hl o n g e rc h a n g i n gp e r i o di se a s i e rf o rE A s 。

K e y w o r d s ：A r t i f i c i a lI n t e l l i g e n c e ，E v o l u t i o n a r yC o m p u t a t i o n ，P a r t i c l eS w a r m O p t i m i z a t i o n ，O p t i m i z a t i o nR e s e a r c h ，D y n a m i cO p t i m i z a t i o nP r o b l e m s ．I I ． 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。