（计算机应用技术专业论文）求解单目标全局优化问题的改进类电磁机制算法.pdf

摘要摘要全局优化问题是现代优化设计的一个重要独立分支，它在科学、工程、生活等众多领域有着广泛应用。近几年，启发式优化算法以其通用性、智能性等显著优势，得到了极大地研究和发展。本文针对单目标全局优化中无约束和有约束问题进行了深入研究，提出了基于电磁场中吸引排斥机制的启发式方法一改进的类电磁机制算法。本文主要工作如下：1 对无约束优化问题，根据标准类电磁机常i j ( e m ) 算法的寻优机制及针对其电荷溢出和参数敏感问题，改进了e m 算法。首先，引入函数值下界改进粒子电量计算公式；然后改善合力计算公式，减少计算量、改善数据溢出问题；最后加入步长变异，将算法陷入局部最优的可能性降到最低，据此，设计改进的e m 算法u e m 算法。2 对于有约束单目标全局优化问题，首先将违反约束条件的粒子用外点法处理，将问题转化为无约束问题；然后采用正交设计产生初始种群，使初始粒子更均匀的分布在解空间；进一步改进粒子电量计算公式，最大限度的减少计算量，提高效率，设计了c e m 算法。3 对两个改进后的算法进行数值模拟。u e m 算法采用1 0 个标准测试函数进行测试，并与标准e m 算法、遗传算法进行相同参数下的比对，证明新算法提高了最优解的精度，对标准e m 算法的改进是有效的。对于求解约束问题的c e m 算法经数值仿真对6 个标准函数进行测试，并与模拟退火算法进行比对，验证了算法通用性强、高效稳健，有较快的收敛速度，具有一定的竞争力。关键词：单目标全局优化吸引排斥机制类电磁机制算法a b s t r a c ta b s t r a c tg l o b a lo p t i m i z a t i o ni sa l li m p o r t a n ti n d e p e n d e n tb r a n c ho fm o d e r no p t i m i z a t i o nd e s i g n s i th a sb e e nw i d e l yu s e di nm a n yf i e l d ss u c ha ss c i e n c e ，e n g i n e e r i n g ，r e a ll i f ea n ds oo n i nr e c e n ty e a r s ，h e u r i s t i co p t i m i z a t i o na l g o r i t h mh a sb e e ns t u d i e da n dd e v e l o p e dg r e a t l yd u et oi t si n t e l l i g e n c ea n dw i d ea p p l i c a t i o n s u n c o n s t r a i n e da n dc o n s t r a i n e do p t i m i z a t i o np r o b l e m so fs i n g l eo b j e c t i v eg l o b a lo p t i m i z a t i o na r es t u d i e da n dt w oh e u r i s t i cm e t h o d sb a s e do na t t r a c t i o n - r e p u l s i o nm e c h a n i s mi ne l e c t r o m a g n e t i s m - i m p r o v e de l e c t r o m a g n e t i s m l i k em e c h a n i s ma l g o r i t h m sa r ep r o p o s e di n t h i sp a p e r t h em a i nc o n t r i b u t i o n so ft h i st h e s i sc a r lb es u m m a r i z e da sf o l l o w s ：1 t os o l v eu n c o n s t r a i n e do p t i m i z a t i o np r o b l e m sa c c o r d i n gt oe l e c t r o m a g n e t i s m 1 i k em e c h a n i s m ( e m ) ，a l li m p r o v e de ma l g o r i t h mi sp r o p o s e d f i r s t , t h el o w e rb o u n do fo b j e c t i v ef u n c t i o ni si n t r o d u c e dt ot h ef o r m u l ao f t h ep a r t i c l ec h a r g ei no r d e rt oa v o i di t sp a r a m e t e rs e n s i t i v i t y , t h e nt h ef o r m u l ao ft h et o t a lf o r c ev e c t o ri sa l s oi m p r o v e di no r d e rt or e d u c et h ea m o u n to fc o m p u t a t i o na n dc o m p u t e ro v e r f l o w , f i n a l l yt h es t e p s i z ei sa d d e dt ot h em u t a t i o ni no r d e rt oa v o i dt r a p p i n gi n t ol o c a ls o l u t i o n b a s e do i lt h e s e ，a nu n c o n s t r a i n e de mo p t i m i z a t i o na l g o d t h m ( u e m ) i sd e s i g n e d 2 a ni m p r o v e de ma l g o f i t h r n ( c e m ) i sp r o p o s e df o rc o n s t r a i n e do p t i m i z a t i o np r o b l e m s f i r s t l y , t h ec o n s t r a i n e do p t i m i z a t i o np r o b l e mi st r a n s f o r m e di n t oa nu n c o n s t r a i n e do p t i m i z a t i o np r o b l e mb ye x t e r n a lp o i n tm e t h o d s e c o n d l y , t h eo r t h o g o n a ld e s i g ni sa d o p t e dt op r o d u c eu n i f o r m l yd i s t r i b u t e di n i t i a lp o p u l a t i o n t h e n ，t h ef o r m u l ao ft h ep a r t i c l ec h a r g ei sr e d e f i n e dt od e c r e a s et h ea m o u n to fc o m p u t a t i o nc a l c u l a t i o na n di m p r o v et h ee f f i c i e n c y f i n a l l y , t h ec e mi sp r o p o s e d 3 t h en u m e r i c a ls i m u l a t i o n sa r em a d eo nt w oi m p r o v e de ma l g o r i t h m s u e mi se x e c u t e do n10s t a n d a r dt e s tf u n c t i o n s ，a n dt h er e s u l t sa r ec o m p a r e d 诵t ht h o s eo fb o n le ma l g o r i t h ma n dg e n e t i ca l g o r i t h mb yu s i n gt h es a m ep a r a m e t e r s t h er e s u l t si n d i c a t et h a tu e mi m p r o v e dt h ep r e c i s i o no ft h eo b t a i n e ds o l u t i o na n dt h eu e ma l g o r i t h mi se f f e c t i v e c e mi se x e c u t e do n6s t a n d a r dt e s tf u n c t i o n s ，a n dt h er e s u l t sa r ec o m p a r e dw i t l ls i m u l a t e da n n e a l i n ga l g o r i t h m t h er e s u l t sd e m o n s t r a t et h a t t h ep r o p o s e da l g o r i t h mi sc o m p e t i t i v e ，e f f i c i e n t ，r o b u s ta n df a s tc o n v e r g e n c e k e y w o r d s ：s i n g l eo b j e c t i v eg l o b a lo p t i m i z a t i o na t t r a c t i o n - r e p u l s i o nm e c h a n i s me l e c t r o m a g n e t i s m l i k em e c h a n i s ma l g o r i t h m西安电子科技大学学位论文独创性( 或创新性) 声明本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容外，论文中不包含他人已经发表或撰写的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所作过的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：尚云日期咿鼻西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用复印、影印、缩印或其它手段保存论文。( 保密的论文在解密后遵守此规定)本学位论文属于保密在一年解密后适用本授权书。本人签名： 向云导师虢掐季日期：ol o f f 刁日期：一圣垒1 9 ：圭? ?第一章绪论第一章绪论1 1 研究的背景和意义日常生活、科学技术各个领域中普遍存在着优化问题。优化问题的解决方法就是从所有可能的有限或无限种方案中选择出最合理的，能达到最优目标的方案。优化的基本思想是选择。大约公元前3 0 0 年，我国战国时期庄周所著的庄子一书的“天下篇”中，记有“一尺之棰，日取其半，万世不竭。这就是最朴素、最典型的极限概念，是优化问题的雏形。1 7 世纪，英国伟大的科学家牛顿( i s a a cn e w t o n , 1 6 4 2 1 7 2 7 ) 发明微积分的时代，伴随着微积分的发明，就提出了函数的极值问题。1 7 5 5 年，1 9岁的法国数学家拉格朗h ( j o s e p h - l o u i sl a g r a n g e ，1 7 3 6 1 8 1 3 ) 的第一篇论文“极大和极小的方法研究 ，提出了关于一个函数在一组等式约束条件下的极值问题。1 8 4 7年，法国数学家柯西( a u g u s t i n l o u i sc a u c h y , 1 7 8 9 1 8 5 7 ) 提出了用最速下降法来求解无约束优化问题，后来又提出了用拉格朗日乘数法( l a g r a n g em u l t i p l i e r ) 解决约束优化问题【l 】。1 9 4 7 年，3 3 岁的美国数学家丹茨格( g e o r g eb e r n a r dd a n t z i g ，1 9 1 4 2 0 0 5 )提出了求解线性规划问题的单纯形法，为线性规划的理论和算法奠定了基础，自此，优化理论和优化算法才成为一门独立的学科。1 9 5 1 年，库恩( h w g u b _ n ) 和塔克( a w t u c k e r ) 发表的关于最优性条件的论文是非线性规划诞生的一个重要标志。随着生产、经济、技术的发展，工程、技术、管理人员在实际工作中，越来越多的面临这样一类问题：工程设计中，怎样配置参数，使得设计既满足需求又降低成本；资源分配中，怎样设计分配方案，既能满足各方面的基本要求又能得到很好的经济效益；生产计划安排中，怎样选择计划方案，才能提高产值和利润；城建规划中，怎样安排工厂、机关、商店、学校、医院、住宅和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展。在各个领域中，诸如此类问题，不胜枚举。这一类问题的共同特点，就是要在所有可能的方案中，选出最合理的，达到事先规定的最优目标的方案，寻找最优方案的方法称为最优化方法1 2 j 。随着计算机科学的发展和应用，应用最优化方法解决问题的领域不断扩大，解决问题的深度不断深化，最优化的理论和方法也不断得到普及和发展。优化问题分为有约束和无约束两大类。约束优化包含：线性和非线性；整数型和混合型以及多目标型。在经典的优化理论中，拉格朗日乘子法则、库恩塔克条件、庞特里雅金极大值原理、贝尔曼最优化方程，奠定了优化理论研究发展的里程碑【3 1 。著名的求解算法有变尺度法( d a c i d o n - f l e t c h e r - p o w e r , d f p ) 、无约束变尺2求解单目标全局优化问题的改进类电磁机制算法度法( b r o g d e w - f l e t c h e r - g o l d f a r b s h a n n o b f g s ) 、广义乘子法( h e s t e n e s p o w e l l ，i - w )和约束尺度法( w i l s o n h a n p o w e l l ，w h p ) 等t 4 1 。2 0 世纪6 0 年代，研究现在称为全局优化的问题，关注点主要集中在线性规划和非线性规划局部优化数值算法方面。非线性规划模型在实际应用中是普遍存在的，例如：科学模型，数据分析，工程设计，金融计划，环境管理，生物技术，过程控制，风险管理等。从2 0 世纪7 0 年代中后期开始，经过近3 0 年的发展，全局优化才发展为最优化学科中的一个独立的分支。全局最优化问题由于目标函数和约束条件的复杂性，目标函数在可行域中往往是一个多峰值函数，这使得全局优化问题变得较为困难，尤其是高维复杂函数的全局最优解的求解对优化界来说是一个公开的难题【5 j 。目前求解局部最优的方法相对成熟，而求解全局优化问题的方法在理论上、算法上都远远没有得到完善。多数全局优化算法要不是对目标函数的要求比较高，要不就是用速度变慢来换取全局收敛，而随着科学技术的飞速发展，全局优化在经济、金融、核能、生物、网络、运输、环境、化工等众多领域应用的越来越广，因此，全局优化理论、方法都值得深入研究。本文提出了一种基于类电磁机制，利用启发式算法的思想求解全局优化问题的新算法。类电磁机f l ；j j ( e l e c t r o m a g n e t i s m 1 i k em e c h a n i s m ，e m ) 算, 法t 6 , t j 是一种基于种群的启发式全局优化算法，由s 1 b i r b i l 和s c f a n g 于2 0 0 2 年提出。本文改进了标准e m 算法中电量的计算方法，防止数据溢出问题；改进合力计算公式，减少考虑所有粒子的大运算量等问题；结合局部搜索策略，以求解无约束优化问题及约束优化问题；且针对初始种群的优劣直接影响后代的搜寻范围问题，改进初始种群产生方式，采用正交设计，大大提高种群质量；在约束优化问题中引入外点法将约束问题转化为无约束问题，得到有效求解。数据仿真验证了改进的e m算法的有效性。1 2 全局优化问题1 2 1 全局优化问题的数学模型几乎所有的优化问题都可以概括为数学模型：给定一个集合( 称为可行集或可行域) 和定义在该集合上的实值函数( 目标函数) ，求函数在该集合上的最大( 或最小)值。最优化问题的一般形式8 1 是m i n f ( x ) 或者m a x f ( x )s 1 x s第一章绪论3其中s ( 可行域或容许域) 是尺”中的一个集合，厂( z ) ( 目标函数) 是定义在s 上的实值函数。令i i j i 表示欧几里得范数。如果存在某个 0 ，对于所有满足峙一x l | s 的x s ，有f ( x ) f ( x ) ，称点x s 称为一个相对极小点( r e l a t i v em i n i m u m ) ，或者局部极小点( 1 0 c a lm i n i m u m ) 。如果对于所有的x s ，有f ( x ) f ( x ) ，则称x 是一个全局极d 点( g l o b a lm i n i m u m ) 。同理，点x s 称为一个局部极大( 或者全局极大)点，如果对于所有的xes n x x x i i - - 占 ( 或者x s ) ，有厂( x ) 厂( x ) 。本文所说的全局优化问题特指全局最小化问题，形如minf(x)(1-2)xes，的最优化问题，其中s = x 尺”：( x ) o ，i = 1 ，p ，岛：彳寸r 定义在一个适当的集合么2 s 上( 通常4 ：r 一) 。因为m a ) 【 厂( x ) ：x s = 一m i n 一厂( x ) ：x s ，所有极大化问题包含在模型( 1 2 ) 中。进而，由于g ，( x ) o 等价于一g ，( x ) o ，g ，( x ) = o等价于g ，( x ) o 和一g ，( x ) o ，模型( 1 2 ) 包含了许多其他类型的约束。1 s = r “时，问题为无约束( u n c o n s t r a i n e d ) 优化问题2 s 是一个多面体时，问题为线性约束( 1 i n e a r l yc o n s t r a i n e d )3 满足条件2 并且目标函数也是线性的，问题为线性规划( 1 i n e a r p r o g r a m m i n g )( 或者线性优化( 1 i n e a ro p t i m i z a t i o n ) i h 题)4 函数至少有一个是非线性的，问题称非线性规划( n o n l i n e a rp r o g r a m m i n g )( 或者非线性优化( n o n l i n e a ro p t i m i z a t i o n ) i h - j 题)1 2 2 全局优化问题的研究现状及进展2 0 世纪6 0 年代，线性规划和非线性规划的局部优化方面的研究推进了优化的发展。从2 0 世纪7 0 年代中后期开始，国内学者从事全局优化领域问题的研究，提出的填充函数法、水平集上的积分法等全局优化算法在国际上产生了一定的影响。2 0 0 3 年9 月，国内出版了第一本专门讨论确定性全局优化的翻译论著全局优化引论i s 。全局优化算法，较典型的算法汇总1 9 1 ，方法大致可以分为三大类【1 0 】：确定性方法、随机性方法( 包括启发式方法( h e u r i s t i ca l g o r i t h m ) ) 以及它们的混合方法。4求解单目标全局优化问题的改进类电磁机制算法1 确定性方法是当目标函数和约束函数都是某些特定要求的函数，直接利用现有的优化方法来解决最优问题。例如：d c 规划问题【l ，任何一个连续规划问题可以化为一个具有线性目标函数，或不超过一个凸和一个反凸约束的d c 规划问题；外逼近法【1 2 】，最初是用来解凸规划的，后来被推广到凹极小问题，以及反凸规划问题；填充函数法【l3 1 ，要求目标函数二阶可微，基于当前的最好点，根据该点建立一个相应的辅助函数，该函数能够填平当前最好点所在的深谷，帮助搜索跳出局部极小，转移到一个“地势更低的深谷 ，获取该深谷的一个点，从该点重新搜索，希望能找到比当前点更好的点。每一种确定性全局优化方法都分别有它的一些优点和缺点，所以研究不同的优化方法得以持续。2 随机性方法处理许多实际问题时通常可以在合理时间内得到不错的答案。重要分支为启发式算法，该类算法大都是受自然规律的启发，从中找到了许多解决实际问题的方法。当然，现在流行的启发式算法也不是全部来自自然的规律，也有许多是来自人类积累的工作经验。确定性方法和启发式方法之间的差别很微妙，它们之间的差别在于其距离最终解决办法的间接程度：确定性方法直接给出解决问题的指导，而启发式方法则告诉我们该如何发现这些指导信息，或者至少到哪里去寻找它们，这也是其难点，建立符合实际问题的一系列启发式规则。启发式算法的优点在于它比盲目型的搜索法要高效，一个经过仔细设计的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解，对于n p 问题，亦可在多项式时间内得到一个较优解。典型的随机性方法有纯随机算法【1 4 1 ( p r s ) 、多点出发算法【l 习( m s ) 、演化规划、遗传算法( g e n e t i ca l g o r i t h m ，g a ) 【1 6 1 、粒子群算法( p s o ) 【1 7 1 、进化策叫1 引、模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ，s a ) u 刿等。3 混合方法是根据实际问题的需要，将确定性方法和启发式方法结合使用，从而得到更高效的最优解。实际问题中，无论是确定性优化方法还是随机性优化方法，在求解复杂全局优化问题时，均易陷入问题的局部极小点，即使某个方法没有陷入局部极小点，其求出全局极小点的速度通常也是很慢的。造成这种现象的主要原因是，目前的优化方法寻找全局极小点的基本原理是设法从一个局部极小点跳到另一个局部极小点。如确定性方法中的填充函数法；启发式方法中的遗传算法，采用群体的进化策略，用随机的方法以一定的概率在当前局部极小点所处的深谷之外保留一定数量的点，以期种群中的点在进化过程中移动到另一个局部极小点。而如何有效的从一个局部极小点跳到另一个更小的局部极小点，是优化方法中急需解决的一个难点。依据全局优化问题的特点，使其研究方法不同于传统的局部优化方法，因此对复杂优化问题中摆脱局部最优的研究一方面具有重要的理论意义、应用价值，另一方面又极具挑战性。第一章绪论5m u r t y 7 阳k a b a d i 例在1 9 8 7 年指出了非线性二次无约束优化问题是n p 一难问题，不存在多项式时间内的精确算法；r i n o o y 和t i m r n e r 2 1 1 证明了无约束优化问题在有限次迭代内无法求得其全局最优解，从理论上说明了无约束优化问题的复杂性。1 2 3 启发式算法的现状本文所讨论的方法类电磁算法属于启发式算法，启发式算法的计算量都比较大，所以启发式算法是伴随着计算机技术的发展而迅速发展的，并取得了巨大的成就。优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。选择是优化的基本思想，变异( 多样化) 是随机搜索或非确定搜索的基本思想，优胜劣汰是算法搜索的核心。根据“优胜劣汰，适者生存”的自然法则，总结提取出不同策略，可以获得不同的启发式算法。启发式算法的主要思想是来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得到的。启发式算法于2 0 世纪4 0 年代，因实际需要提出；5 0 年代，逐步繁荣，其中贪婪算法和局部搜索得到人们的关注；6 0 年代，启发式算法被反思，发现以前提出的算法速度很快，但是解的质量不能保证，而且对大规模问题仍然无能为力，且收敛速度慢成了他的一个巨大问题；7 0 年代，计算复杂性理论的提出，n p 问题，许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，得到的解没有全局最优性。由此必须引入新的搜索机制和策略。h o l l a n d 的遗传算法出现，再次引发了人们研究启发式算法的兴趣。8 0 年代以后，模拟退火算法，人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k , a n n ) 瞄】，禁忌搜索( t a b us e a r c h ，t s ) 等算法相继出现。最近比较热或刚热过去的：演化算法( e v o l u t i o n a r ya l g o r i t h m ) ，蚁群算法( a n ta l g o r i t h m s ) ，拟人拟物算法，量子算法等。启发式算法快速发展。启发式算法的特点是对目标函数没有太高的要求，不需要函数的导数，甚至不要求目标函数是显式，更灵活，解决问题的范围更广，具有良好的适应性，这使得在工程设计中有着很大的应用空间，对那些传统的优化方法无能为力的复杂无约束优化问题，仍能在比较合理的时间内给出问题的满意解。同时，信息处理的隐式并行性，使自然启发的优化方法很容易与其他的算法相结合，取长补短，产生更好的优化效率。但是，与传统方法相比，他们收敛速度慢，计算量大。自2 0 世纪8 0 年代以来，针对优化问题中的n p h a r d 问题，自然启发的优化算法( 如遗传算法、神经网络算法、类电磁机制算法等) 开始得到了蓬勃迅速的发展。这类算法多采用群体的进化策略，用随机的方法以一定的概率在当前局部最优解所处的深谷之外保留一定数量的粒子，以期这些粒子在进化过程中能找到比当前局6求解单目标全局优化问题的改进类电磁机制算法部极小点更好的点。简单介绍以下几种启发式算法：模拟退火算法，遗传算法，禁忌搜索算法，神经网络算法。这几种算法在解决全局最优解的问题上有着独到的优点，并且，它们有一个共同的特点：都是模拟了自然过程。模拟退火思路源于物理学中固体物质的退火过程，它是模拟统计物理中固体物质的结晶过程，在退火过程中，如果搜索到好的解接受；否则，以一定的概率接受不好的解( 即实现多样化或变异的思想) ，达到跳出局部最优解得目的。遗传算法借鉴了自然界优胜劣汰的进化思想，它是根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异得到的算法，在进化过程中，较好的个体有较大的生存机率。禁忌搜索模拟了人类有记忆过程的智力过程，它模拟人的经验，通过禁忌表记忆最近搜索过程中的历史信息，禁忌某些解，以避免走回头路，达到跳出局部最优解的目的。神经网络更是直接模拟了人脑，模拟大脑神经处理的过程，通过各个神经元的竞争和协作，实现选择和变异的过程。以上几种算法之间的联系也非常紧密，比如模拟退火算法和遗传算法为神经网络算法提供更优良的学习算法提供了思路。把它们有机地综合在一起，取长补短，性能将更加优良。这几种智能算法有别于一般的按照图灵机进行精确计算的程序，尤其是人工神经网络算法是对计算机模型的一种新的诠释，跳出了冯诺依曼机的圈子，按照这种思想来设计的计算机有着广阔的发展前景。这些方法通过模拟现实或者揭示某些现象和过程得到发展，其思想和内容涉及到数学、物理学、生物进化、人工智能、神经科学和统计力学等学科，为解决复杂问题提供了新的思路和工具。在优化领域，由于这些算法构造的直观性和自然机理，通常被称为智能优化算法( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) 或称为现代启发式算法( m e t a - h e u r i s t i ca l g o r i t h m s ) 。启发式算法的基本流程为图1 1 。自然启发的算法都是具有一定的自组织、自适应和自学能力的智能优化算法，在求解一些用传统方法难以得到满意解的复杂问题时，自然启发式优化算法具有自己独特的优势。b i r b i l 和f a n g 于2 0 0 2 年根据电磁场中带电粒子之间的吸引一排斥机制，提出了求解无约束优化问题的类电磁机制( e m ) 算法。该算法是有效结合传统优化方法和随机性优化方法而产生的一种新型的自然启发式优化算法，已经成功的用于求解无约束优化问题。与传统的优化方法相似，它也是为问题的求解寻找下降方向的方式产生新的个体，因而，具有收敛速度快、计算精度高的优点；而在求解过程中，不需要利用函数的数学性质，可以用于求解所有的无约束优化问题；且群体的搜索策略使算法得以突破邻域搜索的限制，可以实现整个解空间上的分布式信息搜索、采集和继承，从而保证了解的全局性，克服了传统的优化算法对初始点的依赖。c h i n g - s t s o u 和c h i a - h u n gk a o 于2 0 0 6 年改进类电磁机制算法幽j ，第一章绪论7解决了多目标问题。a r i am a f i aa c r o c h a 和e d i t em c l e f e r n a n d e s 于2 0 0 8 年改进类电磁机制算法【2 4 1 解决了有约束问题，但算法还存在不足之处。本文针对这些不足，提出改进措施。图1 1 启发式算法流程图1 3 本文的主要工作与结构本文研究类电磁机制算法求解全局优化问题。在无约束问题中，对e m 算法的电量计算和合力计算公式做了改进；在求解约束问题时，对e m 算法的电量公式改进后，采用外点法将约束条件化解，且采用正交设计产生初始种群。最后通过数据仿真证明改进后的算法求解精度和收敛速度较原有算法都有了很大提高，取得很好效果。本文的内容安排如下：第一章描述了全局优化问题的研究背景和意义、数学模型、研究现状及进展，且详细介绍了启发式算法，最后简要介绍了本文的主要工作内容和安排。第二章描述了类电磁机制算法的理论基础，包含磁场原型和数学模型，详细介绍了算法基本步骤并进行了算法分析及数值模拟。第三章描述了求解无约束优化问题的改进类电磁机制算法，针对e m 算法所存在的计算量过大、收敛速度不够快、对高维多峰函数求解效果不够理想等缺陷进行改进，重新定义了粒子的电量和合力的计算公式，并加入步长变异，设计出8求解单目标全局优化问题的改进类电磁机制算法了求解无约束问题的新类电磁机制算法( u e m ) 。第四章描述了求解约束优化问题的改进类电磁机制算法，采用外点法转化约束条件，正交设计产生初始种群，进一步改进电量计算公式，设计出了求解约束问题的新类电磁机制算法( c e m ) 。第五章针对求解约束和无约束优化问题的两个新算法，使用m a t l a b 进行数值模拟，通过测试标准测试函数并与其它算法结果进行比对，数值模拟结果表明，新算法用于求解全局优化问题是可行有效的。第六章为全文总结工作，并简要介绍进一步可展开的工作。第二章类电磁机制算法9第二章类电磁机制算法2 1 引言启发式算法的特点是从随机可行初始解出发，采用迭代改进的策略，去逼近问题的最优解。启发式优化方法是基于种群，其寻优过程是先从可行域中选取一些点作为初始点，根据这些点的目标函数值确定吸引区域，然后利用某种机制对这些区域进行进一步的搜索，再重复这个过程直至得到满意的解。类电磁机制( e m ) 算法就是一种基于种群的启发式优化算法，是b i r b i l 和f a n g受电磁场中带电粒子之间的吸引与排斥机制的启发，于2 0 0 2 年提出的一种新型的全局启发式优化算法。电磁场的库仑定律是该算法的理论依据，其中包括：每个具有一定电荷量的带电粒子受到来自其它粒子的力；根据“同号排斥，异号吸引的原则，决定两个粒子之间作用力的方向；两个粒子之间作用力的大小由库仑定律确定，与两粒子电荷的乘积成正比，与粒子之间距离的平方成反比；每个粒子在其他粒子施加给其的合力下进行移动。在通常情况下初始种群中的粒子是随机产生的，问题的每个可行解都是带有一定电荷的粒子，粒子所带电荷的大小与待优化的目标函数有关，同时决定着该粒子对其他粒子吸引力或排斥力的强弱；粒子之间作用力的方向是基于“优质解吸引劣质解，劣质解排斥优质解”的吸引一排斥原则来确定的，使得粒子可以朝着有利的方向移动；然后通过将来自其他粒子的力进行矢量叠加而得到种群中每个粒子所受的合力，为粒子下一步的移动寻找方向；最后粒子在合力的作用下移动到新的位置，产生下一代种群。按照如此的循环，产生一代代的种群，逐渐逼近问题的全局最优解。该思想考虑到与电磁理论中吸引一排斥机制的异同，因此该机制称为类电磁机制。更重要的是e m 算法的收敛性已经得到了证明【2 5 1 ，证明结果表明当迭代趋于极限时，种群中至少有一个粒子以概率1 移动到全局最优附近。2 2 1 电磁场原型2 2 类电磁机制算法理论库仑定律【2 6 1 ：真空中两个静止的点电荷之间相互作用力的大小与这两个电荷所带电量g l 和g ：的乘积成正比，与它们之间距离r 的平方成反比。作用力的方向沿1 0求解单目标全局优化问题的改进类电磁机制算法着两个点电荷的连线，同号电荷相斥，异号电荷相吸。这一规律可用矢量式表示为te 1 2 = kq ，1 q _ _ _ _ 。l 之l ( 2 - 1 )式( 2 1 ) 中e ：表示g ：对g 。的作用力，杰。表示由q 2 到9 1 方向的单位矢量，ky 可l - t ；例系数。受力如图2 1 所示：晶 _图2 1 电磁场中两电荷受力图当吼，q ：同号时互：为排斥力沿之，的方向；当9 1 ，q 2 异号时，g lq 2 的乘积为负，巧：为吸引力沿- 杰。的方向。当脚标l ，2 对调时；i ：= - 之。，吼对吼的作用力e 1 = - 互：。通过实验测试真空中的库仑定律可以表示为式( 2 - 2 ) ：肚去4 r m 等砖去4 h e 等，弘2 ，o，上o，j以电磁场中库仑定律为原型，b i r b i l 和f a n g 将其吸引排斥机制应用于求解全局优化问题当中，自定义粒子所受电量，模拟电磁中的合力计算公式，参照吸引排斥机制，设计产生e m 算法，成功求解了无约束优化问题。2 2 2 类电磁机制算法数学模型e m 算法最初是针对变量有界的最小化问题提出的，问题形式如下：f m i n ( x )1 盯x s( 2 - 3 )其中：s = ，甜】- 厶 x k ，k = l ，2 ，胛 ，刀为问题的维数，和厶分别为第k 维的上下边界，x = ( 五，x 2 ，而) r ”为决策变量，厂 ) 为目标函数。2 3 类电磁机制算法2 3 1 类电磁机制算法流程e m 算法解决优化问题( 2 3 ) 的主要框架如下：第二章类电磁机制算法1 1参数设置( s i z e n ，m a x i ，m a x s ，6 ) ：s i z e n 为种群规模即粒子数，m a x i 为最大迭代次数，m a x s 为每次迭代过程中局部搜索的最大搜索次数，6 ( o ，1 ) 为局部搜索参数。i n i t i a l i z e oi t e r a t i o n - - - 1w h i l ei t e r a t i o n m a x id ol o c a l s e a r c h ( m ax s ，6 )f - - c a l c u l a t i o n 0m o v e ( f )i t e r a t i o n 4 - - i t e r a t i o n + 1e n dw h i l ee m 算法的实现主要由五个阶段完成，分别是粒子的初始化、局部搜索、每个粒子所受合力的计算、粒子的移动、满足条件终止。具体流程如图2 2 。开始随机产生初始种群对种群中粒子进行局部线性搜索计算粒子所带电荷、所受合力移动粒子到新位置，产生下一代种群翌一 满足终止条件y结束图2 2 e m 算法流程图粒子的初始化就是从可行域中选取一组初始粒子的过程，一般情况，种群中的粒子都是随机产生的，以这些粒子为种群基础进行下一步的搜索；局部搜索是对单个粒子进行的，来改进种群中单个粒子的质量，以加快算法的收敛速度，使得算法既具有全局搜索能力，又具有局部区域精细搜索的能力；计算合力是类电磁机制算法中最关键的一步，它将粒子所获得的局部信息与全局信息结合起来，1 2求解单目标全局优化问题的改进类电磁机制算法粒子电量和粒子所受合力均模拟电磁理论中的计算公式，力的方向模拟电磁理论中的叠加原理，为粒子的下一步搜索提供方向；计算完合力向量后，各个粒子将沿着合力的方向移动，这样粒子的位置得到更新，至此完成了算法的一次迭代；直到满足终止条件时，得到最优解，终止条件采用规定迭代次数的方式，当迭代次数大于最大迭代次数时，终止循环。2 3 2 类电磁机制算法基本步骤标准e m 算法主要由5 个基本的步骤组成，即初始化、局部搜索、计算合力、移动粒子、终止条件。下面将对每一步做一详细介绍。1 初始化初始化是生成初始种群的过程，从已知可行域s 中服从均匀分布的随机选取s i z e n 个点作为初始粒子，这些初始粒子构成初始种群，然后计算出每个粒子的目标函数值，并将当前目标函数值最优的粒子记为。后面的步骤中以这些粒子为基础来进行更进一步的搜索。2 局部搜索在e m 算法中，局部搜索起着非常重要的作用，为种群的全局搜索提供有效的局部信息，这样使算法不仅具有全局搜索能力，又具有局部精细搜索的能力。该搜索是针对种群中的每一个粒子薯( 待1 ，2 ，瓯琵) 进行的，用来在单个粒子的邻域范围内寻找更好的粒子将之替代，以改进种群的质量。标准e m 算法使用的局部搜索是最简单常用的线性搜索，对每个粒子的每一维根据局部搜索参数6 ，计算最大的可行步长，然后按照该步长进行搜索，找到一个更好的解后搜索就立即终止。每次搜索之后，产生新的种群，需重新计算种群中每个粒子的目标函数值厂( 薯) ( 扛1 ，2 ，s i z e n ) ，并找到当前目标函数值最优的粒子仍记为。3 计算合力计算合力是e m 算法最重要的一步，这一步将粒子所获得的局部信息与全局信息结合起来了。基本电磁理论里的叠加原理是：一个粒子受到的其它粒子施加的电磁力与粒子之间的距离成反比且与它们所带电荷数的乘积成正比，如式( 2 1 ) 。从这个角度出发，e m 算法定义合力公式( 2 5 ) ，通过计算合力来为下一步的搜索提供信息。粒子f 的电荷量吼决定了粒子f 所受的吸引力或者排斥力的大小。定义电荷f 所带电荷量吼为下式：吼：e x p i - s i z e n 高篮型( 厂( ) 一厂( ) )k = l，i = 1 ，2 ，s i z e n( 2 - 4 )第二章类电磁机制算法1 3这样，式( 2 4 ) 指数函数参数非正，依据单调增的函数特性，目标函数值较优的粒子将拥有较大的电荷数，具有更强的吸引力，且g ，( o ，1 】。而粒子f 的电荷量吼并不同于真正的电荷，因为式( 2 4 ) 中各粒子的电荷都是没有正负号的，因此，我们在比较两粒子的目标函数值后决定两粒子间作用力的方向，作用在粒子f 上的合力只由下式计算：s f z e nf = y一j l盱尚m 小尥)，f = 1 ，2 ，s i z e n( 2 5 )”踟尚m 班胞)根据公式( 2 5 ) ，对于两个粒子而言，目标函数值较优( 即较小) 的粒子将吸引另一个粒子，反之，目标函数值较差( 即较大) 的粒子将排斥另一个粒子，也就是说两个粒子之间作用力的方向总是指向目标函数值较优的粒子，这也保证了算法的有效性。由于x b 。甜的目标函数值最小，它充当着一个绝对吸引的粒子，即它吸引着种群中的其它所有粒子。4 移动粒子对于当前粒子( f = l ，2 ，s i z e n ) ，计算完合力f 后，该粒子将沿着合力的方向以一个随机步长移动，步长移动公式如下：f毫。而+ a 氚( 舢)( 2 _ 6 )上叫i其中：f - 1 ，2 ，s i z e n ，允u ( o ，1 ) ，r n g 为一个向量，其分量表示对应的上边界或者下边界移动的可行步长。按照式( 2 6 ) 移动后，计算新粒子的目标函数值厂( z ) ，如果厂( z ) ( 葺) ，则数据溢出，无法得到有效的粒子电量；3 ) 该算法在计算合力时将所有粒子的作用力都考虑了，会产生较大运算量；当两粒子距离相当近时，则在按公式( 2 5 ) 计算合力过程中势必会造成溢出。这种模拟电磁场中带电粒子的吸引一排斥机制的做法已经使得e m 算法具有比较优异的优化性能，但这种简单地、直接地模拟中还有可以改进的空间，可以进一步提高e m 算法的收敛速度，扩大应用范围。本章针对e m 算法存在的问题进行了如下改进：首先，在规定粒子电量时，考虑了粒子最优值反复计算问题，引入了函数值下界，以增强算法的有效性，且防止了数据溢出的可能；其次，对单个粒子的合力计算方法进行了修正，重新定义了粒子电量公式、粒子合力公式，在不影响寻优效果的情况下，有效地减少了算法的计算量，提高了算法的效率；最后，改变了e m 算法中粒子的移动方法，并增加步长变异，使其避免易于陷入局部最优的麻烦。数值实验结果表明，改进后算法求解无约束全局优化问题时的性能得到了提高，具有更快的收敛速度和更高的解的精度。3 2 类电磁机制算法的改进解决优化问题( 2 3 ) ，无约束类电磁机制算法c l i e m ) 仍保留标准e m 算法的基本框架，改进了电量的计算公式，在计算粒子电量时规定目标函数值下界，杜绝溢出可能性；改进了合力计算过程中，过虑掉受力较小的粒子，有效减少计算量，加快算法的收敛速度；改进移动步长公式，从局部最优中走出；增加步长变异，增强算法的局部搜索能力，使算法更快的收敛到全局最优。下文中约定，刀为问题的维数，朋为种群规模( 粒子数) 。3 2 1 计算电量标准e m 算法中电量的产生算法如下，算法3 1 ：f o