（应用数学专业论文）解决单目标和多目标优化问题的进化算法.pdf

摘要 摘要 以进化算法为代表的仿生随机算法由于具有智能性、通用性和全局搜索能 力，以成为求解复杂优化问题的重要工具。本文对于单目标和多目标优化问题进 行了深入的研究，提出了几种求解不同问题的进化算法，本文主要进行了下面几 个方面的工作： 1 将具有任意个约束条件的单目标优化问题转化为双目标优化问题，其中一 个为原目标函数，另一个为违反约束程度最大的约束条件。采用偏好于第二个目 标的粒子比较准则；为了避免算法陷入局部最优，当全局最优解连续几代4 、= 发生 改变时，采用改进的多父体单形杂交算子对其进行扰动，使得产生的新点更好的 继承父代的特性，将扰动后的粒子作为新的寻优方向。数值实验表明：对于某些 特定函数，本算法寻优性能优良。 2 对于较复杂的约束单目标优化问题，提出了模糊粒子群算法。设计了一 个新的扰动算子，使得扰动后的粒子偏向于当前种群中约束违反度小或目标函数 值小的粒子。在此基础上定义了模糊个体极值和模糊全局极值，利用这两个定义 改进了粒子群进化方程，利用该方程更新粒子的速度与位置，可以避免早熟收敛 问题；定义了不可行度阈值，利用此定义给出了新的粒子比较准则，该准则采用 对约束逐个处理的技术，使得一部分性能较优的不可行解微粒得以保留，从而达 到使不可行解向可行解进化的目的。仿真结果表明，对于复杂约束优化问题，算 法寻优性能优良，特别是对超高维约束优化问题，该算法获得了更高精度的解。 3 提出了基于粒子群优化的多目标m e m e t i e 算法。将无约束多目标优化问题 转化成单目标约束优化问题，其中将解的质量度量看作是约束条件，均匀性度量 看作是目标函数。对转化后的问题提出了基于约束主导原理的比较准则；用基于 模拟退火的加权法对非劣解进行局部搜索。算例测试说明该算法寻优性能优良。 4 提出了解决无约束多目标优化问题的模糊粒子群算法。设计了新的扰动算 子，使得扰动后的粒子偏向于当前种群中序值较小或位于目标空间稀疏区域中的 粒子。在此基础上定义了模糊个体极值和模糊全局极值，利用这两个定义改进了 粒子群进化方程；通过改进的进化方程和遗传算法共同作用产生新群体。实验结 果表明，该方法可以求出一组分布均匀且散布广泛的最优解。 5 提出了基于新模型的多目标m e m e t i c 算法。将无约束多目标优化问题转化 为单目标约束优化问题；针对转化后的模型提出了新的选择策略：将目标空间划 分为若干个区域，该选择算子偏好于位于稀疏区域的个体而不考虑该个体序值的 大小。这样，可以保证产生一组分布均匀且更接近真实p a r e t o 前沿的非劣解；新 i i西安电子科技大学博士学位论文：解决单目标和多目标优化问题的进化算法 的多目标m e m e t i c 算法引进了c m e t r i c 将模拟退火算法与遗传算法结合起来， 使得算法能产生质量较好的子种群。仿真结果表明新算法对无约束多目标优化问 题是有效可行的。 6 提出了解决多目标约束优化问题的混合粒子群算法。设计了一个基于阈值 的粒子比较准则，使之适用于处理多目标约束优化问题，该准则可以保留一部分 序值较小且约束违反度在允许范围内的不可行解微粒，从而达到由不可行解向可 行解进化的目的；设计了一个新的拥挤度函数，使得位于稀疏区域和p a r e t o 前沿 边界附近的点有较大的拥挤度函数值，从而被选择上的概率也较大；设计了一个 具有两阶段的变异算子，第一阶段变异：计算出参与变异的粒子所受的合作用力， 在此合力的基础上定义了个体的变异方向，沿着该方向进行变异可能会找到序值 较小或约束违反度较小的粒子。为了避免粒子沿着一个固定的方向进行搜索，保 证算法的全局收敛性，选择一定数目的粒子参与第二次变异。 7 针对多目标约束优化问题提出了基于不可行精英保留策略的粒子群优化 算法。为了保留一部分约束违反度较大、序值较小的不可行粒子，设计了一个不 可行精英保留策略，在进化初期从不可行精英集合中选出一定数目序值较小的不 可行解微粒，而不考虑这些微粒约束违反度的大小，在进化后期从不可行精英集 合中选择一部分约束违反度较小的粒子作为不可行精英粒子的代表参与进化；设 计了一个新的拥挤度函数。该函数只需使用较少的计算量就可以使得位于稀疏区 域和p a r e t o 前沿边界附近的点具有较大的函数值，从而使这些点被选择上的概率 很大。改进了混合粒子群算法中所设计的变异算子，新的变异算子减少了计算量， 只有当粒子的约束违反度小于给定的阈值时才被选择参与变异。 8 针对粒子群算法中线形递减的惯性权重无法适应于复杂的非线性优化搜 索过程的问题，提出了两种改进的粒子群算法：动态改变惯性权重的粒子群算法 及一种简化的粒子群优化算法。第一种算法使得惯性权重与粒子的聚集度及全局 最优值变化的速度有关，第二种算法使得粒子的飞行无记忆性，结合平滑函数和 一维搜索重新生成停止进化粒子的位置。仿真结果表明这两种算法是有效可行的。 关键词：进化算法粒子群优化约束单目标优化多目标优化约束多目标优 化惯性权重p a r e t o 最优解全局收敛性 a b s t r a c t t h ee v o l u t i o n a r ya l g o r i t h mh a sb e c o m eo n eo ft h ei m p o r t a n tt o o l sf o rs o l v i n g c o m ：p l e xo p t i m i z a t i o np r o b l e m s ，b e c a u s eo f i t si n t e l l i g e n c e ，w i d e l yu s e da n dg l o b a l s e a r c ha b i l i t y i nt h i sd i s s e r t a t i o n ，s t u d i e sa r em a i n l yf o c u s e do ns i n g l e - o b j e c t i v e o p t i m i z a t i o na n dm u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s t h e m a i nc o n t r i b u t i o n so ft h i s t h e s i sa r es u m m a r i z e da sf o l l o w s ： 1 ab i o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o nf o rc o n s t r a i n e ds i n g l e o b j e c t i v e o p t i m i z a t i o np r o b l e m si sp r o p o s e d t h et e c h n i q u e t r e a t sc o n s t r a i n e do p t i m i z a t i o nw i t h a n yn u m b e ro fc o n s t r a i n t sa sab i o b j e c f i v eo p t i m i z a t i o n t h e n ，i no r d e r t ok e e pt h e d i v e r s i t yo ft h es w a r ma n de s c a p ef r o mt h el o c a lo p t i m u me a s i l y , w h e n t h eo p t i m u mi s n o ti m p r o v e di ns e v e r a ls u c c e s s i v eg e n e r a t i o n s ，i ti sp e r t u r b e db yu s i n ga ni m p r o v e d s i m p l e xc r o s s o v e ro p e r a t o r i nd o i n gs o ，b e t t e rp a r t i c l e sw i l lb e f o u n d t h es i m u l a t i o n r e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mi se f f e c t i v e 2 af u z z yp a r t i c l es w a r mo p t i m i z a t i o ni sp r o p o s e df o rs o l v i n gc o m p l e x c o n s t r a i n e d s i n g l e o b j e c t i v eo 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 , a n e wp e r t u r b a t i o n o p e r a t o ri sd e s i g n e d ，a n dt h ec o n c e p to ff u z z yp e r s o n a lb e s tv a l u ea n df u z z yg l o b a l b e s tv a l u ea r eg i v e nb a s e do nt h en e wo p e r a t o r p a r t i c l eu p d a t i n ge q u a t i o n sa r er e v i s e d b a s e du p o nt h et w on e wc o n c e p t st od i s c o u r a g et h ep r e m a t u r ec o n v e r g e n c e s e c o n d l y , an e wc o m p a r i s o ns t r a t e g yi sp r o p o s e db a s e do nt h ec o n c e p to fi n f e a s i b l et h r e s h o l d v a l u e t h ec o n s t r a i n t sa y et r e a t e do n eb yo n ei n t h i ss t r a t e g y , s os o m ep a r t i c l e sw i t h g o o dp r o p e r t yw i l lb ep r e s e r v e d i nd o i n gs o ，t h ei n f e a s i b l es o l u t i o n s w i l le v o l v e t o w a r dm ef e a s i b l eo n e s f i n a l l y , t h es i m u l a t i o nr e s u l t ss h o wt h a t t h ep r o p o s e d a l g o r i t h mi se f f e c t i v e ，e s p e c i a l l yf 0 rt h ep r o b l e m s w i t hh i g hd i m e n s i o n s 3 am u l t i 。o b j e c t i v em e m e t i ca l g o r i t h mb a s e do np a r t i c l es w a r mo p t i m i z a t i o nl s p r o p o s e df o rs o l v i n gu n c o n s t r a i n e dm u l t i - o b j e c t i v eo 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 e p r o b l e mi sc o n v e r t e di n t oac o n s t r a i n e ds i n g l e o b j e c t i v eo p t i m i z a t i o np r o b l e m t h e r a n kv a l u e so fa l lp a r t i c l e sa r er e g a r d e da st h ec o n s t r a i n t s ，a n dt h em e a s u r eo ft h e u n i f o r t u i t yo ft h es o l u t i o n si sr e g a r d e da st h eo b j e c t i v ef u n c t i o n s e c o n d l y , f o rt h e c o n v e r t e dp r o b l e m ，an e wc o m p a r i s o ns t r a t e g yb a s e do nt h ec o n s t r a i n td o m i n a n c e p r i n c i p l ei sp r o p o s e d t h i r d l y , as i m u l a t e da n n e a l i n gb a s e dw e i g h t e d 。s u mm e t h o d i s u s e dt op e r f o r ml o c a ls e a r c h t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h m i se f f e c t i v e 4 af u z z yp a r t i c l es w a r mo p t i m i z a t i o ni sp r o p o s e d f o rs o l v i n gu n c o n s t r a i n e d m u l t i o b j e c t i v eo 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 , an e wp e r t u r b a t i o no p e r a t o ri sd e s i g n e d ， t h ep e r t u r b e dp a r t i c l ew i l ll e a nt ot h ep a r t i c l ew i t hs m a l l e rr a n kv a l u eo rt h ep a r t i c l e l o c a t e di nt h es p a r s er e g i o no ft h eo b j e c t i v es p a c e b a s e do nt h e s e ，t h ep a r t i c l e u p d a t i n ge q u a t i o n sa r er e v i s e d s e c o n d l y , t h en e wp o p u l a t i o ni sp r o d u c e dt h r o u g h t h e i m p r o v e dp a r t i c l es w a r mo p t i m i z a t i o na n dg e n e t i ca l g o r i t h m t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h ep r o p o s e da l g o r i t h mc a ng e n e r a t eas e to fw i d e s p r e a da n du n i f o r m l y d i s t r i b u t e ds o l u t i o n s 5 an e wm o d e lb a s e dm u l t i o b j e c t i v em e r n e t i ca l g o r i t h mi sp r o p o s e d f i r s t l y , t h e u n c o n s t r a i n e dm u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e mi sc o n v e r t e di n t o ac o n s t r a i n e d s i n g l e - o b j e c t i v eo p t i m i z a t i o np r o b l e m f o rt h ec o n v e r t e dp r o b l e m ，an e wc o m p a r i s o n s t r a t e g yi sp r o p o s e d ：t h eo b j e c t i v es p a c ei sd i v i d e di n t os o m er e g i o n s ，t h e nt h ep a r t i c l e s l o c a t e di nt h es p a r s er e g i o n sa r ep r e f e r r e dr e g a r d l e s so ft h e i rr a n kv a l u e s i nd o i n gs o ，a s e to fu n i f o r m l yd i s t r i b u t e da n dw i d e s p r e a dn o n d o m i n a t e ds o l u t i o n s a r ef o u n d s e c o n d l y , t h en e wa l g o r i t h mc o m b i n e st h eg e n e t i ca l g o r i t h mw i t ht h e s i m u l a t e d a n n e a l i n ga l g o r i t h mb yi n t r o d u c i n gt h ec m e t r i ct oi m p r o v et h eg l o b a ls e a r c ha b i l i t y , t h e nt h eb e t t e ro f f s p r i n gw i l lb eg e n e r a t e d t h es i m u l a t i o nr e s u l t ss h o wt h a tt h en e w a l g o r i t h mi se f f e c t i v e 6 ah y b r i dp a r t i c l es w a r mo p t i m i z a t i o ni sp r o p o s e df o rs o l v i n gc o n s t r a i n e d m u l t i o b j e c t i v eo p t i m i z a t i o n f i r s t l y , i no r d e rt ok e e ps o m ep a r t i c l e sw i t hs m a l l e r c o n s t r a i n tv i o l a t i o n s ，at h r e s h o l dv a l u ei sd e s i g n e d ，t h ec o m p a r i s o ns t r a t e g yo fp a r t i c l e s i sr e v i s e db a s e do ni t i nd o i n gs o ，t h ei n f e a s i b l es o l u t i o n sw i l le v o l v et o w a r dt h e f e a s i b l eo n e s s e c o n d l y , i no r d e rt of i n das e to fd i v e r s ea n dw e l ld i s t r i b u t e d p a r e t o o p t i m a ls o l u t i o n s ，an e wc r o w d i n gd i s t a n c ef u n c t i o ni sd e s i g n e df o rb i - o b j e c t i v e o p t i m i z a t i o np r o b l e m s i tc a na s s i g nl a r g e rc r o w d i n gd i s t a n c ef u n c t i o nv a l u e sn o to n l y f o r t h ep a r t i c l e sl o c a t e di nt h es p a r s er e g i o n sb u ta l s of o rt h ep a r t i c l e sl o c a t e dn e a rt o t h eb o u n d a r yo ft h ep a r e t of r o n t t h i r d l y , an e wm u t a t i o no p e r a t o ri sp r o p o s e d t h e t o t a lf o r c ei sc o m p u t e df i r s t ，t h e ni ti su s e da sam u t a t i o nd i r e c t i o n ，s e a r c h i n ga l o n gi t ， b e t t e rp a r t i c l e sw i l lb ef o u n d i no r d e rt og u a r a n t e et h ec o n v e r g e n c eo ft h ea l g o r i t h m ， t h es e c o n dp h a s eo fm u t a t i o ni sp r o p o s e d 7 a ni n f e a s i b l ee l i t i s tb a s e dp a r t i c l es w a r mo p t i m i z a t i o n f o rc o n s t r a i n e d m u l t i o b j e c t i v eo p t i m i z a t i o n i s p r o p o s e d f i r s t l y , a n i n f e a s i b l ee l i t i s tp r e s e r v a t i o n s t r a t e g yi sp r o p o s e d ，w h i c hk e e p ss o m ei n f e a s i b l es o l u t i o n sw i t hs m a l l e r r a n kv a l u e sa t t h ee a r l ys t a g eo fe v o l u t i o nr e g a r d l e s so fh o wl a r g et h ec o n s t r a i n tv i o l a t i o n sa r e ，a n d k e e ps o m ei n f e a s i b l es o l u t i o n sw i t hs m a l l e rc o n s t r a i n tv i o l a t i o n sa n d r a n kv a l u e sa tt h e l a t e rs t a g eo fe v o l u t i o n i nt h i sm a n n e r , t h et r u ep a r e t of r o n tw i l lb ef o u n de a s i e r s e c o n d l y , an e wc r o w d i n gd i s t a n c ef u n c t i o ni sd e s i g n e d i tc a na s s i g nl a r g e rc r o w d i n g d i s t a n c ef u n c t i o nv a l u e sn o to n l yf o r t h ep a r t i c l e sl o c a t e di nt h es p a r s er e g i o n sb u ta l s o 内rt h ep a r t i c l e sl o c a t e dn e a rt ot h eb o u n d a r yo ft h ep a r e t of r o n tb yu s i n gl e s s c o m p u t a t i o n a lc o s t t h i r d l y , t h em u t a t i o no p e r a t o ri nt h e h y b r i dp a r t i c l es w a r m o p t i m i z a t i o ni sr e v i s e d t h ep a r t i c l e sw h o s ec o n s t r a i n t v i o l a t i o n sa r el e s st h a nt h e t h r e s h o l dv a l u ew i l lb eu s e dt oc o m p u t et h et o t a lf o r c e ，s ot h a tt h e c o m p u t a t i o n a lc o s t i sr e d u c e di nt h i ss t e p t h ec o m p a r a t i v es t u d ys h o w st h a tt h ep r o p o s e da l g o r i t h mc a n g e n e r a t ew i d e s p r e a da n du n i f o r m l yd i s t r i b u t e dp a r e t of r o n t sa n do u t v e r f o r m st h o s e c o m p a r e da l g o r i t h m s 8 f o rs o l v i n gt h ep r o b l e mt h a tt h el i n e a rd e c r e a s i n gw e i g h tc a nn o te x a c t l yr e f l e c t t h es e a r c h p r o c e s s ，t w oi m p r o v e dp a r t i c l es w a r n lo p t i m i z a t i o ni s p r o p o s e d ：a d y n a m i c a lp a r t i c l es w a r mo p t i m i z a t i o na n das i m p l ep a r t i c l es w a r m o p t i m i z a t i o n i n t h ef i r s ta l g o r i t h m ，t h ei n e r t i aw e i g h ti sc h a n g e dw i t ht h ea c c u m u l a t i o nf a c t o ra n dt h e v e l o c i t yf a c t o r i nt h es e c o n da l g o r i t h m ，t h ei n e r t i aw e i g h ti ss e tt oz e r o ，a n dt h e p o s i t i o no ft h ep a r t i c l ew h o s ee v o l u t i o nh a ss t o p p e di sp r o d u c e db ys m o o t hs c h e m e a n dl i n es e a r c h t h es i m u l a t i o nr e s u l t ss h o wt h a tt h et w o a l g o r i t h m sa r ee f f e c t i v ea n d o u t p e r f o r mt h ec o m p a r e do n e k e y w o r d s ：e v o l u t i o n a r ya l g o r i t h m p a r t i c l es w a r m o p t i m i z a t i o n c o n s t r a i n e d s i n g l e o b j e c t i v e o p t i m i z a t i o n m u l t i - o b j e c t i v eo p t i m i z a t i o n c o n s t r a i n e d m u l t i 。o b j e c t i v eo p t i m i z a t i o n i n e r t i a w e i g h t p a r e t o o p t i m a l s o l u t i o ng l o b a l c o n v e r g e n c e 西安电子科技大学 学位论文独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 本人签名： 导师签名： 日期圣丝8 垒! 刍曰习日 日期幽星：f 墨：颦 第一章绪论 第一章绪论 本文主要是用智能优化技术一进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 来有效 地处理单目标和多目标优化问题。本章首先介绍了进化算法产生的背景，介绍了 进化算法的现状与研究发展。然后介绍了单目标和多目标优化问题的数学描述及 相关概念、进化算法的研究现状。最后，介绍了本文的主要内容及结构安排。 1 1 引言 近3 0 年来，人们从不同的角度对生物系统及其行为特征进行了模拟，产生了 一些对现代科技发展有重大影响的新兴学科。对自然界中动、植物免疫机理的模 拟产生了免疫算法；而对自然界中生物进化机制的模拟就产生了进化计算 ( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 理论。 进化计算最初有三大分支：遗传算法( g e n e t i ca l g o r i t h m ，g a ，由j h h o l l a n d 于1 9 7 5 年提出【i 】) 、进化规：蛇l j ( e v o l u t i o n a r yp r o g r a m m i n g ，e p 由l j f o g e l 等于 1 9 6 6 年提出【2 】) 和进化策略( e v o l u t i o n a r ys t r a t e g y , e s ，由i r e c h e n b e r g 于1 9 7 3 年 提出【3 】) 。9 0 年代初，在遗传算法的基础上又形成了一个分支：遗传程序设计 ( g e n e t i cp r o g r a m m i n g ，g p , 由j k o z a 于1 9 9 0 年提出【4 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 ，由k e n n e d y 和 e b e r h a r t 等于1 9 9 5 年提出【5 1 ) 是继蚁群算法之后提出的又一种新型进化计算技术。 其基本思想来源于对鸟类社会模型的研究及行为模拟。群体中的鸟被抽象为没有 质量和体积的“微粒”，通过这些微粒的相互协作和信息共享，其运动速度受到自 身和群体的历史运动状态信息的影响，能较好的协调微粒本身和群体运动之间的 关系，在复杂的解空间中寻找到最优解。微粒群算法提出后，由于其概念简明， 实现方便，在短期内迅速得到了国际进化计算研究领域的认可，并在算法实现模 式及应用领域得到很大的发展i 1 3 】。目前一般将粒子群算法归纳到进化算法中。 本文主要研究了进化算法在单目标【1 1 郴，5 禾5 7 1 和多目标【1 夺2 5 】优化问题中的应 用。在论文展开前，先对进化算法的现状与发展作一简单回顾。 1 2 进化算法的现状 进化计算是指以进化原理为仿真依据，在计算机上实现的具有进化机制的算 法和程序。目前，进化计算侧重于算法的研究，因此有时也称之为进化算法 西安电子科技大学博士学位论文：解决单目标和多目标优化问题的进化算法 ( e v o l u t i o n a r ya l g o r i t h m s ，e a ) ，若由性质来区分，现有的进化算法可细分如下 【2 6 】： 1 ) 最具有代表性的遗传算法； 2 ) 侧重于数值分析的进化策略； 3 ) 介于数值分析与人工智能间的进化规划； 4 ) 偏向于进化的自组织和系统动力学特性的进化动力学； 5 ) 偏向以程式表现人工智能行为的遗传程序设计； 6 ) 适应动态环境学习的分类系统； 7 ) 用以观察复杂系统交互的各种生态模拟系统； 8 ) 研究人工生命的元胞自动机： 9 ) 模拟蚂蚁群体行为的蚁元系统； 进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索 算法，其求解的一般过程包括以下步唰2 8 】： 1 ) 随机给定一组初始解： 2 ) 评价当前这组解的性能： 3 ) 根据2 ) 的评价结果，从当前解中选择一定数量的解作为基因操作对象： 4 ) 对所选择的基因进行操作( 交叉、变异) ，得到一组新的解： 5 ) 返回到2 ) ，对该组新的解进行评价： 6 ) 若当前解满足要求或进化达到一定的代数，计算结束，否则转向3 ) 继续进 行。 与其它搜索技术( 如梯度搜索技术、随机搜索技术、启发式搜索技术和枚举技 术) 相比，进化算法具有以下特点： ( 1 ) 进化算法的搜索过程是从一群初始点开始搜索，而不是从单一的初始点开 始搜索。这样，其获得全局最优解的概率大大提高了。 ( 2 ) 进化算法使用的是目标函数的评价信息，其具有良好的普适性。 ( 3 ) 进化算法具有显著的隐式并行性。 ( 4 ) 进化算法具有很强的鲁棒性。 目前，进化算法作为一种具有自适应调节功能的寻优技术，其独特的性能已 在众多领域内获得了成功的应用，着重用于解决结构性优化、非线性优化、并行 计算等复杂问题，其中遗传算法的研究最为深入、持久、应用面也最广。下面介 绍几种典型的进化算法： 一、进化策略 2 0 世纪6 0 年代初，柏林工业大学学生l r e c h e n b e r g 和h p s c h w e f e l 等在 进行风洞实验时，由于设计中描述物体形状的参数难以用传统的方法进行优化， 因而利用生物变异的思想来随机改变参数的数值，获得了较好的效果。随后，他 第一章绪论 3 们对这种方法进行了深入的研究和发展【3 】，形成了进化计算的另一个分支一进化 策略( e v o l u t i o n a r ys t r a t e g y , e s ) 。 s c h w e f e l 于1 9 7 7 年提出了( + 兄) 一e s 和( ，兄) 一e s ，其基本做法是：种群 内含有z 个个体，随机选取一个个体进行变异，然后取代种群中最差的个体。假 设组成进化群体的每一个个体有两部分组成，其中一部分是可以连续取值的向量， 另一部分是一个微小的变动量。这个变动量由步长仃r ”( 正态分布的标准差) 和回转角口r 州”1 ) 坨( 正态分布的协方差) 组成的，它们可以来调整对个体进行 变异操作时变异量的大小与方向。因此群体中的每一个个体x 可表示为： x = x ，仃，口) ，这样，对于每一个个体，它就是空间，中的一个点，即： x i = r “”1 ) 坨棚，一般情况下可以不考虑回转角这个参数，则有：x i = r 加， 此时群体中的每一个个体可表示为：x = 而盯) 。在进化策略中，变异操作是产生 新个体的一种主要方法，而交叉操作只是一种辅助的搜索运算。在进化策略中， 选择操作是按一种确定的方式进行。目前进化策略中所适应的选择操作主要有两 种：一类根据种群内的个个体产生五个个体( 用交叉和变异) ，然后将这+ 五个 体进行比较，从中选取“个最优者。这类方法记为( + 力选择。另一类是在新产 生的五个个体中选取个最优者，将它们保留到子代群体中，这类方法记为( ，五) 选择。将这两种进化策略进行比较，( + 五) 一e s 较好的继承了父代的优良特性， 收敛性好，但是易于陷入局部最小。( ，见) 一e s 则易于跳出局部最小，但由于放 弃了上一代的结果，所以收敛较慢。 进化策略的主要特点【2 耻2 9 】：进化策略是直接在解空间上进行操作，它强调 进化过程中从父代到后代行为的自适应和多样性：遗传算法要将原问题的解映射 到位串空间中，然后再实施遗传操作，它强调个体基因结构的变化对其适应度的 影响。 进化策略中的各个个体的适应度直接取自它所对应的目标函数，选择操作 是按照确定的方式来进行的，每次从群体中选择最好的若干个个体，将它们保留 到下一代的群体中：另外，个体的变异运算是进化策略的主要的搜索技术，而个体 之间的交叉只是作为辅助搜索技术。这些均与遗传算法不同。 二、进化规划 进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 的基本思想也源于对自然界中生物 进化的一种模仿，其技术构成与进化策略的构成相类似。此方法最初由l j f o r g c l 等在2 0 世纪6 0 年代提出的，2 0 世纪9 0 年代，d b f o r g c l 借助进化策略方法对 进化规划进行了发展，并在数值优化及人工神经网络的训练等问题的应用中获得 了成功。与遗传算法和进化策略不同的是，进化规划是从整体的角度出发来模拟 生物进化过程，它着眼于整个群体的进化，强调的是物种进化的过程。所以在进 化过程中不使用个体交叉之类的遗传操作，个体的变异操作是唯一的一种最优个 4 西安电子科技大学博士学位论文：解决单目标和多目标优化问题的进化算法 体搜索方法，这是该算法的独特之处。 进化规划的基本思想也是源于对自然界中生物进化过程的一种模仿。其构成 与进化策略相似。在进化规划中搜索空间是一个n 维空间，与此相对应，搜索点 就是一个刀维向量。算法中组成进化群体的每一个个体x 就直接用这个n 维向量 表示：x = x 掣。个体适应度f ( x ) 是由它所对应的目标函数f ( x ) 通过某种比 例转化而得到。 与遗传算法和进化策略不同的是，进化规划是从整体的角度出发来模拟生物 进化过程的，它着眼与整个群体的进化。所以在进化规划中不使用交叉之类的遗 传操作，个体的变异操作是唯一的最优个体搜索方法。 在进化规划中，选择操作是按照一种随机竞争的方式进行的，其基本做法类 似于遗传算法中的排序选择。首先将个个体p ( t ) 和经过一次变异运算后产生的 个子代尸t ( f ) 合并在一起，组成一共含2 个个体的集合 p ( t ) w p ( f ) ) ，对这个集 合中的每一个个体墨，再从这个集合中随机选择q 个个体，比较这g 个个体与五 之间的适应度大小，以其中适应度比五的适应度高的个体的数目作为置的得分 吸，最后对这2 个按降序排列，选择前个个体组成进化过程中的新一代群体。 与遗传算法和进化策略相比，进化规划有如下的特点： 进化规划对生物进化过程的模拟主要着眼于物种的进化过程，算法中不使 用个体交叉算子，而主要依靠变异操作。 进化规划中的选择运算着重于群体中各个体之间的竞争，当竞争数目较大 时，这种选择也就类似于进化策略中的确定选择过程。 进化规划直接以问题的可行解作为个体的表现形式，无需再对个体进行编 码处理，也无需再考虑随机扰动因素对个体的影响，因而便于应用。