（系统工程专业论文）求解最优化问题的类电磁机制算法研究.pdf

摘要最优化是一门应用广泛的学科，类电磁机制算法( 简称e m 算法) 是b i r b i l和f a n g 受电磁场中带电粒子之间互相排斥吸引作用启发，于2 0 0 2 年提出的一种新型的基于种群的启发式算法，其思想是模拟电磁场中带电粒子之间的排斥吸引机制，通过制定一定的准则，使每一个粒子朝着最优解移动，从而求出问题的最优解。本文对类电磁机制算法进行了介绍，在其基本框架上改进了算法的局部搜索方法，重新定义了合力的计算公式，并引入了一个变异算子用来加速算法的收敛。根据标准测试函数的数值试验结果可以看出，这些改进在不影响算法结果的基础上加快了算法的寻优速度，提高了算法寻优效率；另外，对于一般的约束优化问题，使用了极大熵方法简化了约束条件后设计了一个罚函数，将其转化为无约束问题，然后使用改进后的类电磁算法对约束优化标准测试问题进行寻优计算，得到了比较满意的结果，说明改进后的类电磁机制算法也可以用于解决一般约束条件下的优化问题。关键词：类电磁机制算法优化算法极大熵方法a b s t r a c to p t i m i z a t i o ni saw i d e l yu s e ds u b j e c t e 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 m ( e m )m e t h o dw a sb r o u g h tf o r w a r db yb i r b i la n df a n gi n2 0 0 2 ，b e i n gi n s p i r e db ye j e c t - a t t r a c tm e c h a n i s mo fc h a r g e dp a r t i c l e si ne l e c t r o m a g n e t i cf i e l d i ti san e wp o p u l a t i o n - b a s e dh e u r i s t i ca l g o r i t h m i t si d e ai st os i m u l a t et h ee j e c t - a t t r a c tm e c h a n i s mo fc h a r g e dp a r t i c l e si ne l e c t r o m a g n e t i cf i e l da n dm a k ee v e r yp a r t i c l em o v et ot h eo p t i m a ls o l u t i o nb ye s t a b l i s h e ds o m ed e t e r m i n a t er u l e s ，a n dt h e no b t a i nt h eo p t i m a ls o l u t i o no ft h ep r o b l e m i nt h i sp a p e r , e 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 mm e t h o di si n t r o d u c e di nd e t a i l b a s i n go nt h ef u n d a m e n t a lf r a m e w o r ko ft h ee 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 ，t h el o c a ls e a r c hm e t h o do ft h ea l g o r i t h mi si m p r o v e d f o r m u l ao fr e s u l t a n tf o r c ei sr e d e f i n e da n dam u t a t i o no p e r a t o ri si n t r o d u c e dt oa c c e l e r a t et h ec o n v e r g e n c es p e e do ft h ea l g o r i t h m t h er e s u l t so ft h en u m e r i c a le x p e r i m e n t si n d i c a t et h a tt h e s ei m p r o v e m e n t sa c c e l e r a t et h es p e e da n di n c r e a s et h ee f f i c i e n c yo ft h ei m p r o v e da l g o r i t h m o nt h eo t h e rh a n d , w h i l ep e n a l t yf u n c t i o ni sd e s i g n e da f t e ru s i n gt h em a x i m u me n t r o p ym e t h o ds i m p l i f yt h ec o n s t r a i n tc o n d i t i o n s ，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 m sa let r a n s f o r m e di n t on o l l 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 s s a t i s f i e dr e s u l t sa l eo b t a i n e db yu s i n gt h ei 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 mm e t h o dt os o l v es o m ec o n s t r a i n e do p t i m i z a t i o nb e n c h m a r kp r o b l e m s ，i ts h o w e dt h a tc 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 sc a nb es o l v e db yt h ei m p r o v e da l g o r i t h m k e y w o r d ：e 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 mm e t h o do p t i m i z a t i o na l g o r i t h mm a x i m u me n t r o p ym e t h o d西安电子科技大学学位论文创新性声明秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。( 保密的论文在解密后遵守此规定)本学位论文属于保密，在一年解密后适用本授权书。日期丝! ：! ：= !日期z 翌：i ：工第一章绪论第一章绪论1 1 引言最优化是近几十年形成的一门新兴的学科，它主要运用了数学方法来研究各种系统的优化途径，针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，以发挥系统效能及提高系统效益，最终达到系统最优的目标，为决策者提供科学决策的理论依据。最优化的宗旨是追求最优目标，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，其应用领域越来越广泛。在国民经济各个部门和科学技术的各个领域普遍存在着最优化问题，最优化问题的解决就意味着在相同的条件下将获得最优的方案，得到最高的经济效益。目前，最优化已经被人们广泛地应用到公共管理、经济管理、国防、物质调运、自动控制、系统工程等各个领域，发挥着越来越重要的作用。虽然很久以来数学家们就一直在研究求得最优解的方法，或许早在d e s c a r t e s和f e r m a t 时就开始了，他们甚至在十七世纪n e w t o n 建立微积分之前就研究过这样的问题，但一直到了2 0 世纪3 0 年代，最优化的理论和方法才得以迅速发展，并不断完善，逐步形成一门新的、系统的学科1 1 。1 9 4 7 年，数学家g e o r g eb e r n a r dd a n t z i g ( 丹茨格) 提出了一种解决最优化问题的单纯形法，该方法奠定了线性规划的基础，使得经济学、环境科学、统计学应用等学科获得了迅速发展。1 9 5 1 年，k u h n 和t u c k e r 发表的一篇论文首次提出了“非线性规划 ，标志着非线性规划的产生，此后，随着电子计算机技术的飞速发展，最优化的理论和方法，以及应用的深度广度都有了长足的发展。至今已经出现了线性规划、非线性规划、几何规划、动态规划，网络流等等许许多多分支，这些新的优化技术也被迅速大范围的推广和应用到诸多工程领域，如人工智能、生产调度以及系统控制等。1 2 概述一般来说，优化问题就是求解如下的问题：( z )x s蜀珐，j、【关于类电磁机制算法的最优化问题研究s = 【，”】= 缸r ”h h ”i ，七= 1 , 2 ，拧) 是问题的可行域，刀是问题的维数，u i 和，1 分别是可行域第k 维的上边界和下边界，x = ( x i ，x 2 ，x 一) r ”是决策变量，( x ) 是待最小化的目标函数。最优化问题所对应的数学模型由决策变量、约束条件和目标函数构成，意义就是确定一组决策变量在满足约束条件下寻求目标函数的最优。最优化问题按不同的标准可以分为很多类，根据函数的性质划分，如果系统模型和目标函数都是线性式的时候，称之为线性规划( 1 i n e a rp r o g r a m m i n g ) ，否则称之为非线性规划( n o n l i n e a rp r o g r a m m i n g ) ：最优化问题的解如果不随时间变化而变化，称之为静态最优化，如果最优化问题的解是时间的函数，则称这类问题为动态最优化。有约束条件的优化问题我们称之为约束优化问题，约束问题中，系统的数学模型代表约束，按照约束条件式中是出现等号( = ) 、还是不等号( ，) ，又可将约束进一步分成等式约束和不等式约束；在有些情况下不出现约束条件，问题仅由目标函数构成，称之为无约束优化问题。在生产实践中，人们碰到的优化问题绝大部分都是非线性规划问题。此外，根据决策变量，目标函数和约束的不同，最优化问题还可分为整数规划( i n t e g e rp r o g r a m m i n g ) 、随机规划( s t o c h a s t i cp r o g r a m m i n g ) 、非光滑规划( n o n s m o o t hp r o g r a m m i n g ) 、多目标规划( m u l t i - g o a lp r o g r a m m i n g ) 、几何规划( g e o m e t r i cp r o g r a m m i n g ) 、模糊规划( f u z z yp r o g r a m m i n g ) 等等。另外，优化问题也可以由可行域s 来分类，如果j = r “，则问题被称为无约束优化问题，可以写为：m i n 厂( j 【) ，x r “( 1 2 )也就是说无约束优化问题是指在无约束条件下极小化目标函数。另一方面，如果可行域是由等式或不等式约束定义，则问题被称为约束优化问题，一般地，约束优化问题记为：厂( 工)( x ) 0i = 1 ，2 ，q( 1 3 )& ( 石) 毒0i = q + 1 9 - - , 肌这里厂( x ) ，g i ( x ) ，红( x ) 是定义在彤到r 的光滑函数。如果目标函数与约束函数都是线性的，则称问题( 卜3 ) 为线性约束规划：如果目标函数或者约束函数中至少有一个为非线性的，则称问题( 1 - 3 ) 为非线性约束规划。非线性约束规划问题( 简称n l p ) ，在工业，军事，经济以及科学技术领域都有广泛的应用，其求解理论和算法一直是非线性规划研究的重点1 2 1 。优化问题的解的定义以及求解引理有：第一章绪论定义1 1若x r 4 具有性质：vx r “，均有f ( x ) f ( x ) ，则称z 是问题( i - 2 ) 的全局最优解。定义1 2若，er “具有性质：存在f 的某个邻域m ( ，) = 工i i i x - x i l 0 为某个正数，使得vx 占( f ) ，均有f ( x ) f ( x ) ，则称x 是问题( 1 - 2 ) 的一个局部最优解。当目标函数是凸函数时，局部最优解就是全局最优解。但在一般情况下很难找出全局最优解。通常在非线性优化中认为局部最优解即为所求解，在实际计算中，一般是找出满足必要条件的局部最优解。设g ( x ) = vf ( x ) 为f ( x ) 的梯度，g ( x ) = v2f ( x ) 为f ( x ) 的h e s s e 矩阵。引理1 1 ( 无约束优化一阶必要条件)若x 是问题( 1 2 ) 的一个局部最优解，而且在工的某个邻域内( x ) c 1 ，则g ( x ) = 0 。引理1 2 ( 无约束优化二阶必要条件)若x 是问题( 1 2 ) 的一个局部最优解，而且在x 的某个邻域内f ( x ) c 2 ，则g ( x ) = 0 ，g ( x ) 0 。引理1 3 ( k u h n t u c k e r 必要条件)若x 是问题( 1 3 ) 的一个局部最优解，而且正规性假设成立，则一定存在向量，使力= ( 五。，名。：力。) r ：r埘可( x 。) + i = 1 乃_ ( x ) = o五o ，丑& o ) = o ；g ，( x ) o ，i l ，2 ，g ) ，& ( x ) = o ，f g + 1 ，q + 2 ，1 2 1 解决约束优化问题的一些传统方法概述( 1 4 )1 可行方向法f 3 】可行方向法的基本思想是从可行点出发，沿可行方向进行搜索，找出使目标函数值下降的新的可行点，算法主要内容包括选择搜索的方向和确定搜索的步长，不同的可行方向法选择搜索方向和确定搜索步长的方式的不同。比较经典的方法主要有z o u t e n d i j k 法、r o s e n 梯度投影法、w o l f e 简约梯度法、f r a n k w o l f e 法等等，一般来说，使用这些方法求解非线性约束的优化问题的效果都不太理想。2 罚函数法 4 1罚函数法是用于求解约束优化问题的一种重要的方法，它的基本思想是用无约束优化问题替代约束优化问题，将原约束优化问题的目标函数和约束函数进行4关于类电磁机制算法的最优化问题研究组合构成新的无约束优化问题的目标函数，相当于在原目标函数上加上约束函数的一个“惩罚”，迫使迭代的点进入可行域，故称之为罚函数法。罚函数不同的时候，具体的计算方法也不同，罚函数法可以主要分为以下几大类：( 1 ) 外罚函数法对于约束优化问题( 1 3 ) 定义外罚函数为：乞。( x ) = ( x ) + 心 m a x ( o ，& ( x ) ) 】2 + 【岛( x ) 】2( 1 - 5 )、i = 1t = q + l7这里，七为迭代次数，以的值随着k 的不断增大而增大，而且“远远大于l 。于是，当x 是可行点的时候，只。( z ) = ( x ) ；当x 是不可行点的时候，0 。 ) 厂0 ) a而且当x 离可行域越远的时候，兄。( x ) 的值会越大，会远远大于厂( x ) 。( 2 ) 内罚函数法内罚函数法只能解决不等式约束问题，此法从满足约束条件的可行域的内点开始迭代，并在约束区域的边界筑起一道“墙”，对在迭代过程中企图穿越可行域边界的点予以“惩罚”，当迭代点离边界越近，函数值就越大，于是在迭代过程中每个迭代点都趋于位于可行域之内，也就将最优点拦在了可行域之内。对于问题：j 出厂( x ) ( 1 - 6 )l s t g i ( x ) 0i = l ，2 ，q内罚函数定义为：。( 工) = 厂( x ) + 段曰( x )( 1 - 7 )其中段是很小的正数，b ) 是可行域中非负实值连续函数，两种通用的形式是令男( j c ) = 喜i 两1，称为倒数障碍函数，罚函数为。t ( x ) = 厂( x ) + 以b ( x ) ；或令召( x ) ：1 n & ( x ) ，称为对数障碍函数，罚函数为乞。( x ) = 厂( x ) 一心b o ) 。i = 1( 3 ) 混合罚函数法内罚函数法也可以与外罚函数法相结合，称为混合罚函数法，其适用范围更加广泛【5 一。其主要思想就是当初始点给定时，对满足等式约束点使用外罚函数法，而满足不等式约束的点使用内罚函数法，通常使用的罚函数为：第一章绪论讹俨m ，+ 毒 荟c 一 删n ，善，2 )m 8 ，一l n k ( x ) 】( o )其中，瓦= k o 七) o( 1 - 1 1 )q ( 工) ：昙l n 艺，f o ；( 1 - 1 2 )i = q + l这样以来，就可以将原来约束优化问题的众多约束条件式缩并成为少量的约束条件式，减小了求解问题的复杂度。而且极大熵算法可以更加直观的体现函数6关于类电磁机制算法的最优化问题研究的性质，更高效地处理大规模约束，其设计与实现也更加简单。随着科学技术领域不断的发展以及人类对世界认知范围的不断拓宽，在现实中碰到的许多科学、工程、经济和社会等等领域碰到的优化问题越来越复杂，这些问题一般都建模困难，峰值很多，约束条件也很复杂，使用传统的约束优化算法解决起来比较困难，效果也不好，所以寻求新的大规模的智能优化算法已经成为了科学家们新的研究方向和目标。1 2 2 现代启发式算法简介近几十年以来，出现了一系列新颖的优化方法，如遗传算法( g a ) e 7 ，8 ，9 】、模拟退火( s a ) uo 1 1 1 、粒子群算法( p s 0 ) 旧、t a b u 搜索法( t s ) 【”】、蚁群算法( a c o ) 1 4 , 1 5 】等。这些方法与传统的优化方法有很大的区别，它们受到某些自然科学现象和过程启发，通过模拟或揭示其中的规律得到发展，其思想和内容涉及到数学、物理学、生物进化、人工智能、神经科学和统计力学等许多学科，为解决复杂问题提供了新的思路和工具。在优化领域，由于这些算法构造的直观性和自然机理，通常被称为智能优化算法( 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 c t a - h e u r i s t i ca l g o r i t h m s ) 。现代启发式算法往往以一组解为初值，其搜索策略是结构化和随机化的，而且不必用到目标函数的导数信息，所研究的问题不必满足可微性、凸性等条件，其全局优化性强，鲁棒性强，通用性强并且适于进行并行计算。现将其主要几种算法大概介绍如下：1 遗传算法( g a )遗传是一种生物从父代继承特性和性状的现象，生物进化的动力和机制在于自然选择，“物竞天择，适者生存”不仅是生物进化过程中的规则，而且也是自然界一切事物发展所遵循的规律。j h h o l l a n d 于1 9 6 2 年将达尔文“优胜劣汰”的生物进化与遗传思想抽象化，提出了遗传算法的思想，这是一种新的全局并行搜索算法。主要思想为：按某种方式产生一个初始群体，对其中的个体进行编码，编码后的到的形式称为染色体，计算其适应度，然后通过选择、交叉和变异进行进化，产生出具有更好品质的后代，直到得到最优解，最后通过解码获得最优方案。目前在科学家们的研究下g a 已经广泛应用于人工智能、机器学习、函数的优化、自动控制等领域，并取得了丰硕的成果。2 模拟退火( s a )s k i r k p a r i c k 在1 9 8 3 年提出了模拟退火算法，是以马尔科夫链遍历理论和m o n t ec a r l o 模拟法嗍为基础的，这种搜索方法适用于大型组合优化问题，s a 的思想在于模仿热力学中的冷却结晶和退火，采用转换、互换、反演等方法产生新解，第一章绪论7在温度高的时候，接受概率较高，温度降低时接受概率也随之降低，对评价值下降但满足m e t r o p o l i s 接受准则的解予以保留，以避免算法陷入局部最优，直到迭代的最后阶段只接受最优解，从而解决最优化问题。3 t a b u 搜索法1 9 8 9 年g l o v e rf 提出了t a b u 搜索法，这种方法的基本思想是：先产生一个初始解，然后移动这个初始解若干次，在这个初始解的邻域产生一组试验解，选择其中最好的解做为当前解，然后再重复迭代直到满足终止条件为止。在这种方法中，将最近若干次迭代过程中所实现移动的反方向移动记录在t a b u 表中，凡是处于表中的移动，在当前的迭代过程中不能重复再出现，这样就避免了重新搜索已经搜索过的解，可以使算法跳出局部最优。4 粒子群算法( p s o )粒子群算法是k e n n e d y 和e b e r h a r 在1 9 9 5 年提出的一种仿生算法，其原理是模拟鸟类的捕食过程，让每个粒子在解空间运动，记录下自己曾搜索到的最优点，然后再记录下所有粒子运动中所搜索到的全局最优点，再由每个粒子根据自己的曾搜索到的最优点和全局最优点为参数，更新自己的速度和位置，使用这种方法的寻优搜索的效率比较高。5 蚁群算法( a c o )蚁群算法是由d o r i g om 在1 9 9 7 年提出的，其原理是仿照蚂蚁群觅食，构造一组人工蚂蚁，每只蚂蚁以路径上的荷尔蒙强度大小选择前进的路径，并在已经走过的路径上留下一定强度的荷尔蒙，当所有蚂蚁都完成一次搜索时，对所有路径上的荷尔蒙强度进行全局更新，然后进行下一次搜索。经过迭代若干次后，绝大多数蚂蚁将沿同一条路线完成搜索，此路线即为最优路线。6 类电磁机制算法( e 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 mm e t h o d ，e m ) e 1 7 1 8 】类电磁机制算法( 简称e m 算法) 是b i r b i l 和f a n g 根据电磁场中带电粒子之间互相排斥一吸引作用原理，于2 0 0 2 年提出的一种新型的基于种群的启发式算法，其思想是模拟电磁场中带电粒子之间的排斥一吸引关系，通过制定一定的准则，使种群中每一个粒子向最优解移动，经过若干次迭代后从而找到全局最优解。类电磁机制算法是一种新出现的启发式算法，当前的研究还不十分成熟与全面，在许多方面还有待于进一步的研究深入。总而言之，现代启发式算法在结构，研究内容和研究方法上有较大的相似性，寻优机理比较直观简单，而且易于借助计算机来实现，随着计算机技术的不断发展，现代启发式算法在优化领域的发展空间越来越大，但这类方法也有一些缺陷，比如缺乏普遍适用的收敛理论，相关的理论基础比较薄弱等等，还有待于人们对其进行进一步的完善和改良。关于类电磁机制算法的最优化问题研究1 3 本文的工作与安排在本文中，对e m 算法做了一些研究和讨论，所做的主要工作如下：( 1 ) 针对原算法所存在的计算量较大、收敛速度较慢等缺陷，在本文中提出了一种改进的类电磁机制算法。并用标准测试函数对改进后的算法进行了数值试验，试验结果表明，改进后的算法比原算法的优化性能有了明显提高。( 2 ) 利用e m 算法来求解约束优化问题。首先运用极大熵方法和罚函数法，将一般的约束优化问题转换为无约束优化问题。然后在e m 算法的求解实现过程中，改进了原来的局部搜索方法，并对粒子所受的合力计算公式进行了改进，数值试验结果表明，用改进的e m 算法求解约束优化问题的效果也比较好。本文共分为四章：第一章对最优化问题的研究发展的基本状况进行了概述，并对本文工作进行了安排。第二章详细介绍了e m 算法的基本思想以及e m 算法具体实现过程。第三章提出了一种改进的e m 算法，对原标准e m 算法中所存在的问题进行了改进，并用标准测试函数对改进后的算法进行了测试，将数值试验计算结果与对标准e m 算法的结果进行了比较。第四章用e m 算法解决约束优化问题，先用极大熵方法简化了问题的约束条件，然后与罚函数法相结合，将约束优化问题转化为无约束优化问题。然后改进了e m 算法的粒子的局部搜索与合力计算的公式，以使其更适合于约束问题的求解，最后标准测试函数对改进后的算法进行了验证。第二章类电磁机制算法9第二章类电磁机制算法2 1 概述随着科学技术的发展，许多领域出现了学科的互相交叉和融合，在最优化技术领域也不例外。从上个世纪5 0 年代开始，一些科学家受到生物进化的原理以及动物的生活习惯，自然规律、科学规律的启发，提出了很多适合求解现实复杂问题的现代启发式算法，比如遗传算法、蚁群算法、粒子群算法、模拟退火法等等。这些方法原理简单，使用范围广泛，能够解决传统优化算法由于函数不规则或者维数太高而不能解决的复杂优化问题，虽然这些现代启发式算法对计算机的性能、运算速度要求高、依赖性强，但是随着计算机技术的不断飞速发展进步，这些现代启发式算法已经在越来越多的领域得到了广泛的应用。类电磁机制算法就是根据电磁场中带电粒子之间的排斥吸引原理提出来的，是一种新的基于种群的全局随机优化启发式算法。与其它的全局随机优化算法一样，类电磁机制算法也是在可行域中随机确定一组初始解作为初始粒子，然后根据电磁学中带电粒子之间的排斥一吸引原理，将每个初始粒子都当作带电粒子，每个粒子所带电荷大小与其目标函数值有关，目标函数值越优秀的带电粒子，其带的电量就越大，对其它粒子的吸引力和自身受到其它粒子的吸引力也越大；计算完粒子的带电荷量之后，根据电磁场中的带电粒子之间力的计算公式，就可以分别求出每一个带电粒子所受其它各个粒子施加的力的大小和方向，再求这些力的矢量和就得到了该粒子所受其它粒子合力的大小和方向，这样就决定了每个粒子的下一步迭代的移动方向，经过若干次迭代过程后，粒子就会移动收敛到最优点，这样就可以求出优化问题的最优解。2 2 具体步骤对于优化问题( 1 1 ) ，e m 算法的基本步骤有四步：算法的初始化，局部搜索，计算每个带电粒子所受的合力以及带电粒子沿着其所受合力方向移动。2 2 1 初始化首先在n 维可行域中随机选取n 个点作为初始种群，初始种群在可行域中近似于均匀分布，再计算每个点的目标函数值，记x 胁为当前目标函数值最优的点。1 0关于类电磁机制算法的最优化问题研究2 2 2 局部搜索局部搜索过程记录了当前种群中每个粒子的局部信息，对当前种群中的每一个粒子x i o = 1 , 2 ，加进行局部搜索的作用就是在该粒子的邻域范围内寻找目标函数值更优的粒子将当前粒子替代，从而改进当前种群的质量。这里使用的局部搜索是最简单的线性搜索，对每个粒子的每一维根据局部搜索参数万计算粒子的搜索方向和最大可行步长，然后沿着该方向按照该步长进行局部搜索，找到一个更好的解之后搜索就立即终止。局部搜索完毕之后，种群就得到了一次更新，然后再计算更新后种群中每个粒子的目标函数值，最后仍记x 6 e s t 为当前种群中目标函数值最优的粒子。具体公式为：y j ：+ 口( u - - x i ) ， 0 5( 2 1 )。【一一a ( x 1 一，) ，0 5汪l ，n ，u ( o ，1 ) ，a 【o ，l 】。计算f ( y f ) ，如果f ( y ) f ( x 。) ，令z = y 。，搜索终止；否则一= x ；直至达到最大局部搜索次数k 。2 2 3 计算合力对每个粒子所受合力的计算是e m 算法中最为重要的一个过程，这个过程将当前粒子所获得的个体信息与全局信息相结合起来，通过模仿电磁场中带电粒子的力的计算方法以及合力计算的叠加原理，e m 算法对每个粒子用计算其受到合力的方式来确定粒子下一步的寻优前进方向。在e m 算法中，力的计算公式是根据电磁场中的库仑定律得来的，将种群中第f 个粒子的所带的电荷量定义如下：rgf：expiji7：!：!：!j!：盟i，f：l，2，n( 2 2 )l( 厂( ) - - f ( x b e s t ) ) llk = lj由公式( 2 - 3 ) 中可以看出当粒子的目标函数值较优的时候，该粒子将具有较大的电荷量，并且每一个粒子所带的电荷量都是( o ，l l 之间的正数，这一点与真正的带电粒子所带的电荷量有正有负有所区别，因此为了体现出类似于电磁场中带电粒子之间的排斥与吸引作用的关系，并模仿电磁场中带电粒子受力的计算方法以及合力计算的叠加原理，将当前粒子工“= 1 , 2 ，) 受其它粒子的和力的计算公式定义为：第二章类电磁机制算法。l 奶尚 叫d 尚由公式( 2 - 4 ) 可以看出，对于种群中的任意两个粒子来说，目标函数值较优的粒子将会吸引目标函数值较差的粒子，即目标函数值较差的粒子将会排斥目标函数值较优的粒子；也就是说在种群之中，任意两个粒子之间作用力的方向总是指向目标函数值较优的粒子。当前粒子所受合力的方向则是其它粒子对当前粒子所有的各个作用力的矢量和的方向。为了简单说明这个问题，从种群中任意取三个粒子x 1 、x 和x 。为例：在图2 i 中，说明了粒子x 1 所受粒子x 和粒子x 。作用力以及所受合力形成的过程，从中可以看出一个粒子是如何根据排斥与吸引原理来实现该粒子的更新，假设f ( x j ) f ( x 1 ) f ( x z ) ，根据式( 2 - 4 ) 可知，粒子x 与粒子x 1 之间的作用力最1 的方向指向粒子x 1 ，而粒子x 。与粒子x 1 之间的的作用力e 】的方向指向粒子x 。，此时粒子x 1 所受合力f i 是由最1 和b 1 矢量相加得到，根据粒子x 1 所受的合力，i 的方向就确定了其下一步的移动方向。巧lx 2图2 1 粒子间排斥吸引机制示意图图2 1 只是两个粒子对一个粒子作用力的示意图，多个粒子对一个粒子的合力原理也与之相同，也是把每个粒子对该粒子的作用力进行矢量求和得到的。据此可以知道，对于种群中任意一个粒子，其移动方向总是向着目标函数值较优的区域。所以总的来说，任意一个粒子的每一次移动之后的目标函数值都会不差于移动之前的目标函数值，这样算法是有效性就得到了保证。2 2 4 移动粒子计算完当前种群中任意粒子x o ：1 ，2 ，忉的合力e 后，当前粒子x 。( f = 1 , 2 ，) 就将以一个随机步长沿着合力所指的方向移动，粒子移动的公32，l、_ 、- 、xx，l，-， 一、- 、_ 、xx，- ，- ，=e1 2关于类电磁机制算法的最优化问题研究式定义为：，钉见南( 舢_ l ，2 ， ( 2 _ 4 )力u o ，1 ，r n g 是一个，l 维向量，其各个分量是在可行域中各个维上的可行步长。把当前粒子一o = 1 , 2 ，) 按照公式( 2 - 5 ) 的移动后，再计算更新后的新粒子y 的目标函数值厂) ，如果f ( y ) f ( x ) ，令z = y ；否则令x 。= x 。经过这一过程，种群中每个粒子的位置又得到了更新，此时e m 算法就完成了一次迭代。2 2 5 结束准则实现e m 算法时，一般设置一个最大迭代次数来做为算法结束的准则，达到最大迭代次数时算法终止，否则就跳转至局部搜索过程。b i r b i l 、f a n g 的对标准测试函数进行了数值试验，根据试验的测试结果，发现对于一般中等难度、维数为1 1的优化问题，选择每维2 5 次迭代、即最大迭代次数为2 5 n 来实现就基本就可以使算法收敛到最优解，而且可以达到比较令人满意的结果。另一种采用比较多的结束准则是对当前种群中最优粒子变化进行观察，如果在连续迭代若干次，当前种群中的最优粒子一直没有改变，则算法终止，但有时候算法会陷入一个局部最优点，经过若干次迭代没有跳出，这时采用这种结束准则话就可能会导致算法在没有收敛到全局最优解时就提前结束了。文献【1 9 】中也提出了一种算法的结束准则，是当前种群目标函数最优值与已知最优解之差小于占时算法就终止，但是这个准则只能适用于全局最优解已经知道的情况当中。2 2 6 类电磁机制算法的具体流程如下：1 ) 初始化。设置参数( ，l ，口，t ) ，其中为种群规模，k 为每次迭代过程中局部搜索最大次数，口( o ，1 ) 为局部搜索参数，t 为当前迭代次数；从可行域s 中随机产生个点服从均匀分布作为初始粒子构成初始种群p ( 0 ) ，令t = 0 。2 ) 局部搜索。根据式( 2 - 1 ) 对当前种群p ( f ) 中的每个粒子进行局部搜索，使种群得到更新。3 ) 计算合力。依据式( 2 - 3 ) 计算当前种群p ( f ) 中每个粒子所受其它粒子的合力。4 ) 移动粒子。对当前种群p ( f ) 中的每个粒子，按照式( 2 4 ) 对粒子进行移动，完成更新，得到的新粒子构成下一次迭代的种群e ( t + 1 ) 。5 ) 若满足终止条件，则停止运算；否则，令t = t + l ，转2 ) 。第二章类电磁机制算法1 32 3e m 算法的改进及数值试验2 0 0 4 年，b i r b i l 、f a n g 和s h e u 在文献【1 8 】中证明了e m 算法的收敛性，并在算法中引入了“扰动粒子”，以避免算法产生早熟收敛。原来的e m 算法在计算过程中，如果粒子所受的力忽略了某些最优解所在的可行域的时候，早熟收敛就很可能会产生，此时算法就会陷入局部最优。为了避免出现这种情况，取当前种群中离最优粒子最远的粒子为“扰动粒子”，记为z ，扰动粒子的受力计算公式定义为：，f ( x ，) v ，则e 取的方向相反。这样就可以让使扰动粒子移动到被忽略的可行域中，增大了算法搜索到全局最优点的概率。选取离当前最优粒子最远的粒子作为扰动粒子是因为它受当前种群中最优粒子吸引力最小，选择它不会对算法整体的计算结果造成很大的影响。b i r b i l 和f a n g 在文献【17 】中设计了三个不同版本的e m 算法，并用测试函数对三个版本的算法进行了比较计算。三种不同版本的e m 算法如下：( 1 ) 对所有粒子都不进行局部搜索；( 2 ) 对所有粒子都进行局部搜索；( 3 ) 只对当前最优粒子进行局部搜索；数值计算结果表明，只对当前最优粒子进行局部搜索的算法效果最好，这样计算量比较小，能达到比较快的计算速度，而且求解度精也比较高。所以在一般情况下，采取只对当前最优粒子进行局部搜索的方法。只对当前最优粒子进行局部搜索的e m 算法我们称之为标准e m 算法，标准e m 算法对标准测试函数的数值试验模拟结果见表2 1 。表中f u n c t i o n ( 函数名称) 、o p t i m a l ( 已知最优值) 、b e s t ( 算法所得的最优值) 、b e s tm e a n ( 算法运行多次后所得最优值的平均值) 。却=名1 4关于类电磁机制算法的最优化问题研究表2 1 标准e m 算法的函数测试结果【1 7 】f u n c t i o nb e s tm e a nb e s to p t i m a lc o m p l e x0 0 0 0 0o 0 0 0 0o 0d a v i s0 4 0 8 80 1 3 2 2o oe p i s t a c i t y ( 4 )0 0 0 0 30 0 0 0 1o 0e p i s t a e i t y ( 5 )0 0 0 0 l0 0 0 0 lo 0g r i e w a n k0 0 0 0 00 0 0 0 00 oh i m m e l b l a u0 0 0 0 00 0 0 0 00 ok e a r f o t t0 0 0 0 00 0 0 0 0o ol e v y0 0 0 0 10 0 0 0 0o 0r a s t r i g i n2 0 0 0 0- 2 0 0 0 02 os i n ee n v e l o p e0 0 1 1 6o 0 0 0 lo 0s t e n g e ro o o o o0 0 0 0 00 os t e po 0 0 0 00 0 0 0 0o os p i k y3 8 8 0 0 4- 3 8 8 4 9 23 8 8 5t r i d ( 5 )2 9 9 9 7 9- 2 9 9 9 9 93 0s h e k e l s 5 9 7 3 2 01 0 1 5 3 21 0 1 5 3 2s h e k e l s 7 1 0 4 0 2 4- 1 0 4 0 2 91 0 4 0 2 9s h e k e l s10 】1 0 5 1 0 91 0 5 1 0 91 0 5 3 “h a r t m a n h 6 】3 3 0 7 23 3 2 2 4- 3 3 2 2 4g o l d s t e i n3 o o o l3 o o o o3 0 0 0 0b r a n i n b r 0 3 9 8 00 3 9 7 90 3 9 7 9从表中可以看出，对于给出的2 0 个标准测试函数其中的大部分函数，标准e m算法的运算结果都比较令人满意，但是也对于个别几个函数，比如d a v i s 函数、s i n ee n v e l o p e 函数、s p i k y 函数、s h e k e l s 5 函数和h a r t m a n s 6 函数等，e m 算法的寻优结果并不十分理想，还有待于进一步的提高。2 4e m 算法的应用作为一种新出现的现代启发式算法，e m 算法引起了越来越多的研究者的注意，随着对其研究的不断深入，e m 算法现在已经成功应用于其他许多优化领域，p e i t s a n gw u 2 0 , 2 1 等人将e m 算法应用于神经网络训练，成功地解决了纺织零售业中运作问题；袁琨【2 2 1 在e m 算法的基础上，也提出了基于e m 的神经网络算法，并用第二章类电磁机制算法1 5三个模式分类问题i r i s ，i o n o s p h e r e 以及b r e a s t c a n c e r 对其进行了试验，试验结果表明，与b p 算法、遗传算法等算法相比，e m 算法不仅结构简单，而且训练效果比较令人满意；d i e t e rd e b e l s 等人【2 3 “】将e m 算法与分散搜索方法和基于种群的进化搜索方法相结合，成功解决了项目调度问题；魏巍【2 5 】通过引入随机键编码方式，运用e m 算法成功解决了流水车间调度问题，并且选用两个经典的标准问题集( c a r , r e c )进行了测试，表明了用e m 算法解决流水车间调度问题的可行性；程彪2 6 】在魏巍所做工作的基础上，对算法作了些改进，大大提高了算法的求解精度；p e i t s a n gw u ，k u n g - j i u a n y a n g 和h s i n - c h i e hf a n g 2 7 】用e m 算法成功解决了t s p 问题。e m 算法具有结构简单、收敛速度快、易于和其他算法相结合使用的优点。但到目前为止，e m 算法的研究还不十分成熟，其应用领域还比较有限，因此在许多方面还有进一步研究的价值。第三章一种改进的电磁机制算法1 7第三章一种改进的类电磁机制算法3 1 引言类电磁机制算法是一种新型的基于种群的全局优化随机算法，其寻优方法是模拟电磁场中带电粒子之间的排斥吸引作用原理，对种群中的粒子制定一定的准则，使得每次迭代中，粒子都朝着当前最优粒子的方向移动，经过若干次迭代过程从而找到所求优化问题的最优解。算法对许多标准测试函数进行了测试，测试结果显示了类电磁机制算法对低维、简单的测试函数运算效果比较好，但对于高维函数和多峰函数的测试函数，类电磁机制算法的寻优效果并不十分理想。这是因为在算法的实现过程中，对于当前种群中的任意一个粒子，其每一次的局部搜索基本上都是在该粒子的一个很小的邻域内，而且每一次局部搜索都使用了相同的步长。在用类电磁机制算法求解比较复杂的函数时，这样的局部搜索范围太小，而且效果也不好，也就不能快速有效地提高种群的质量；尤其是对于多峰函数，如果当前最优粒子正好处于函数值的某个谷底的话，则在有限的局部搜索次数内，该粒子就很有可能无法从该谷底跳出，于是算法就会陷入局部最优。另一方面，在类电磁机制算法的粒子移动过程中，求合力时是计算其它所有粒子施加给当前粒子的作用力的矢量和，然后根据该合力的方向确定当前粒子的下一步的移动方向，而在实际情况中，与当前粒子距离较远的粒子对当前粒子的作用力是非常小的，即使这些粒子的加入当前粒子的合力计算，对当前粒子的下一步移动方向影响也很小，因此对算法整体的寻优过程影响也很小，但如果在每一次求合力过程中都要计算所有的粒子的话，就会大大的增加算法的计算量，从而影响了算法的整体寻优效率。所以，针对以上标准e m 算法中存在的问题，可以在局部搜索把当前种群中每个粒子的适应度信息考虑进来，改进e m 算法中的局部搜索方法，提高局部搜索过程的效率；另外对单个粒子的求合力的计算方法进行了改进，距离该粒子较远的粒子将不参与该粒子所受合力的计算，这样可以在基本不影响寻优效果的情况下，大大地减少算法的计算量；最后在每一次迭代完成之后，再加入了一个变异操作的过程，用来增强算法的局部搜索能力，使改进后的算法具有更快的收敛速度和更高的运算精度，这样就能提高算法的寻优效率。通过使用改进后的e m 算法对标准测试函数的数值实验，并将求得的试验结果与标准e m 算法的试验结果进行比较可以看出，改进后的e m 算法的优化性能得到了比较大的提高。关于类电磁机制算法的最优化问题研究3 2 改进的类电磁机制算法本节中对类电磁机制算法进行了改进，改进后的算法保留了标准e m 算法的基本思想和步骤，在局部搜索过程中把当前种群中粒子的适应度信息考虑进来，设计了一种新的自适应的局部搜索方法，可以加快算