（计算机软件与理论专业论文）实值演化算法投资组合研究.pdf

i - _ _ _ _ _ _ _ _ j u n i v e a e v o l u t i o n a r ya l g o r i t h m p o r t f o l i o s f o rr e a l p a r a m e t e ro p t i m i z a t i o n a u t h o r ： s p e c i a l i t y ： f e ip e n g c o m p u t e rs o f t w a r ea n dt h e o r y s u p e r v i s o r ：p r o f g u o l i a n g c h e np r o f x i ny a o p r o f k et a n g f i n i s h e dt i m e ：a p r i l2 7 t h ，2 0 11 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入 中国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的 内容相一致。 保密的学位论文在解密后也遵守此规定。 作者签名：兰!垒 签字e l 期：乏芝! ! ：压：2 导师签名一盔亟 签字日期：! l f gj 摘要 摘要 实值优化问题普遍存在于工业与工程实践中，具有广泛的应用背景。演化 算法是从自然界的进化与自适应机制中获得启发而发展起来的求解问题的计算 方法，具有简单、易于操作和通用性强等特性，在实值优化领域取得了广泛的 成功，受到了人们越来越多的重视。数十年间，演化实值优化获得了飞速的发 展，各种各样的实值演化算法不断涌现。这些算法的提出一方面促进了实值演 化优化的发展，但同时也给实践人员带来了如何选择算法的问题。实际中，人 们所能提供的计算时间通常是有限的。因此，怎样在有限时间内为给定问题找 到尽可能好的解，具有十分重要的现实意义。 对于一个给定的问题，人们常常事先并不知道选择何种算法才能有效地进 行求解。由于计算时间有限，一旦所选择的算法表现不佳，则很难再有足够的 时间选择下一个算法进行有效求解。因此，对算法的选择是有风险的。针对这 一问题，我们提出了一个用于比较两个算法风险程度的度量标准，并讨论了 该标准的合理性。在定义了风险度量标准之后，我们还面临怎样减小已有算 法的风险程度这一问题。我们建议，相对于将所有计算时间都“投注”在单个 算法上，将时间分配在多个算法上将能够获得更优的整体性能。基于这一思 想，我们设计出一种演化算法的投资组合设计框架( p o p u l a t i o n b a s e da l g o r i t h m p o r t f o l i o s ，p 舯) 。它将计算时间预先分配到多个子算法上，子算法并行进行搜 索。此外，p a p 通过周期性地激活迁移机制以促进子算法间的信息交流。该框 架能够将任意实值演化算法组合在一起，具有简单、易实现等优点。我们通过 理论与实验相结合的方式。全面分析了p a p 框架在提升子算法整体性能、减小 子算法风险方面的潜力。 接下来，我们进一步讨论了如何在有限时间内最有效地求解一组实值优化 问题。而对于实值优化问题，通常存在若干演化算法可以对其进行求解。通过 第二章的研究成果可以看出。相对于简单地将计算时间平均分配到各个候选算 法上，或者任意选择一个算法并将所有计算时间分配给该算法，更好的做法是 在求解问题之前先进行算法选择。基于这样的考虑，我们提出了以演化算法投 资组合作为基本搜索算法的解决方案。该方案能够为一个给定的问题集自动地 找出最优p a p 实例，具有简单易用的优点。此外，它对问题问的联系不作任何 假设，并且利用了所有算法在所有问题上的性能信息。p a p 作为该解决方案的 基本搜索算法，具有提升其子算法在给定问题集上整体性能的潜力。然而，怎 样选择一个最优的算法子集来进行投资组合设计，在此前的工作中并没有提及。 我们第一次将这一选择任务形式化为一个优化问题，并提出两个选择方法，试 摘要 图尽可能高效地找出最优的p a p 实例。实验结果表明，该解决方案在解决一组 问题时具有十分优异的性能。 最后，我们将演化算法投资组合应用于非均匀间隔对称天线阵列综合问题。 由于差分演化算法和粒子群算法在该问题上都已表现出良好的性能，因此，我 们相应地选择了差分演化算法的一个变体，和粒子群算法的一个变体，作为子 算法进行投资组合设计。为了评估该投资组合实例的整体性能，我们将其与非 均匀天线阵列综合领域代表目前最新水平的算法进行全方面的比较。实验表明。 该投资组合实例在所有4 个优化问题上都获得了最低的优化目标值，并且算法 在求解问题时具有更高的可靠性。此外，当我们对解的质量要求更高时，该投 资组合实例具有更高的求解效率。 关键词：演化算法，实值优化，演化算法投资组合，算法选择，非均匀间隔天 线阵列综合设计，非均匀对称天线阵列优化设计 i i a b s t r a c t a b s t r a c t r e a l 。p a r a m e t e ro p t i m i z a t i o nh a sw i d e s p r e a da p p l i c a t i o n si nt h er e a lw o r l d i n s p i r e df r o mt h ee v o l u t i o na n ds e l f - a d a p t a t i o nm e c h a n i s mf r o mn a t u r e ，e v o l u t i o n a r ya 1 g o r i t h m sa r eac l a s so fg e n e r a lp u r p o s ep r o b l e ms o l v i n gp r o c e d u r e s d u et ot h e i re a s e o f i m p l e m e n t a t i o na n dc a p a b i l i t yo f g l o b a lo p t i m i z a t i o n ，t h e yh a v es u c c e s s i v e l ya p p l i e d t ov a r i o u sr e a l p a r a m e t e ro p t i m i z a t i o np r o b l e m s ，a n dg a i n e dm o r ea n dm o r e a t t e n t i o n d u r i n gp a s td e c a d e s ，n u m e r o u se v o l u t i o n a r ya l g o r i t h m sa n dt h e i rv a r i a n t sh a v eb e e n p r o p o s e df o rr e a l - p a r a m e t e ro p t i m i z a t i o n o no n eh a n d , t h ee m e r g e n c eh a sb o o s t e dt h e d e v e l o p m e n to f t h ee v o l u t i o n a r yr e a l p a r a m e t e r o p t i m i z a t i o na r e a o nt h eo t h e rh a n d ， i th a sa l s om a d ei tm o r ed i f f i c u l tf o rp r a c t i t i o n e r st oc h o o s ea na p p r o p r i a t e a l g o r i t h mf o r t h e i rp r o b l e m s i np r a c t i c e ，t h e r ei su s u a l l yau s e r - d e f i n e dt i m eb u d g e t ，w i t h i nw h i c h s o l u t i o n sn e e d st ob ep r e s e n t e d i nc o n s e q u e n c e ，t h ep r o b l e mo fh o wt of i n da sg o o da s p o s s i b l es o l u t i o n sw i t h i nat i m eb u d g e ti so fg r e a tp r a c t i c a li m p o r t a n c e f o rag i v e np r o b l e m ，t h e r ea r eu s u a l l yan u m b e ro fe v o l u t i o n a r ya l g o r i t h m st h a t a r ea p p l i c a b l e ，h o w e v e r , t h e i rp e r f o r m a n c em a yv a r ys i g n i f i c a n t l yf r o mp r o b l e mt o p r o b l e m i ti su s u a l l yt h ec a s et h a tp e o p l ed on o tk n o ww h i c ha l g o r i t h mc o u l ds o l v et h e p r o b l e mw e l li np r i o r o n c et h ec h o s e na l g o r i t h md o e sn o tw o r kw e l l ，t h el i m i t e dt i m e b u 起e tm i g h tn o ta l l o wt r y i n ga n o t h e ro n e t h i si m p l i e st h a tt h e r ei sa ni n h e r e n tr i s ka s s o e i a t e dw i t ht h es e l e c t i o no f a l g o r i t h m s w ep r o p o s e dam e t r i cf o r c o m p a r i n gt h er i s k s o fa n yt w oa l g o r i t h m so n a p r o b l e ms e t ，a n dd i s c u s s e dt h er a t i o n a l i t y f o rr e d u c i n gt h e r i s ko f a l g o r i t h m s ，w ef u r t h e rs u g g e s t e dt h a t ，i n s t e a do f “b e t t i n g t h ee n t i r et i m eb u d g e t o n a s i n g l ea l g o r i t h m ，i tw o u l db el e s sr i s k yt od i s t r i b u t et h et i m ea m o n gm u l t i p l ed i f f e r - e n ta l g o r i t h m s b a s e do nt h ei d e a ，an e wa p p r o a c hn a m e dp o p u l a t i o n - b a s e da l g o r i t h m p o r t f o l i o ( p a p ) w a sp r o p o s e d i tt a k e sm u l t i p l ea l g o r i t h m sa si t sc o n s t i t u e n ta l g o r i t h m s ， a n da l l o c a t et i m ea m o n gt h e m a l lt h ec o n s t i t u e n t a l g o r i t h m sc o n d u c ts e a r c hi np a r a l l e l i n t e r a c t i o na m o n gt h ec o n s t i t u e n ta l g o r i t h m sw a s e n c o u r a g e dw i t ham i g r a t i o ns c h e m e a sa g e n e r a lf r a m e w o r kr a t h e rt h a nas p e c i f i ca l g o r i t h m ，p a pi se a s yt oi m p l e m e n t ，a n d c a l la c c o m m o d a t ea n y e x i s t i n ge v o l u t i o n a r ya l g o r i t h m s b yt h e o r e t i c a la n a l y s i sa n de x - p e r i m e n t s ，w ec o m p r e h e n s i v e l ye v a l u a t e di t sc a p a b i l i t yo fl e v e r a g i n gt h ep e r f o r m a n c e o fi t sc o n s t i t u e n ta l g o r i t h m sa n dr e d u c i n gt h er i s k a f t e rt h a t , w ef u r t h e rd i s c u s s e dh o wt oo b t a i na sg o o da sp o s s i b l es o l u t i o n sf o ra s e to f p r o b l e m s ，w i t h i nau s e r - d e f m e dt i m eb u d g e t f o rap r o b l e ms e t ，n u m e r o u sa l g o r i t h m sc a nb ea p p l i e da st h ec a n d i d a t es o l v e r s i n s t e a do fm a n u a l l yp i c k i n go n ef r o m i i i t h ec a n d i d a t ea l g o r i t h m sa n d a s s i g n i n gt h ee n t i r et i m eo ni t ，i tw o u l db ed e s i r a b l et o a p p e n da na l g o r i t h ms e l e c t i o np h a s eb e f o r es o l v i n gt h ep r o b l e m s b a s e d 蚰t h ec o n s i d e r a t l o i l ，w ep r o p o s e dan o v e la p p r o a c h ，w h i c ht a k e sp a p a st h eb a s i cs e a r c hp r o c e d u r e i tc a na u t o m a t i c a l l yf i n dab e s tp a p i n s t a n t i a t i o nf o rt h ew h o l ep r o b l e ms e t ，a v o i d i n g f i n d 。t u n i n gas p e c i f i ca l g o r i t h mf o ras p e c i f i cp r o b l e m f u r t h e r m o r e ，i td o e sn o ta s s u m e a n yc o r r e l a t i o nb e t w e e np r o b l e m sa sw e l la sc a n d i d a t ea l g o r i t h m s ，a n d u t i l i z e st h ep e 卜 f 0 册a n c ei n f o r m a t i o no nt h ew h o l e p r o b l e ms e t t h o u g hp a ph a ss h o w e dp o t e n t i a li i l i e v e r a g i n gt h eo v e r a l lp e r f o r m a n c eo fi t sc o n s t i t u e n ta l g o r i t h m s ，n ow o r ko nh o w t o s e j e c ta na l g o r i t h ms u b s e tt oc o n s t r u c tt h eb e s tp a p i n s t a n t i a t i o nh a sb e e nr e p o r t e dv e t w e ，f o rt h ef i r s tt i m e ，f o r m a l i z et h es e l e c t i o nt a s ka sa n o p t i m i z a t i o np r o b l e m ，a n dt h e n p r e s e n tt w 0s e l e c t i o nm e t h o d st oa c c o m p l i s ht h et a s ke f f i c i e n t l y e x p e r i m e n t a lr e s u i t s s n o w e dt h a t ，0 1 1 1 a p p r o a c hi sq u i t ee f f e c t i v ef o r s o l v i n ga s e to f p r o b l e m s i nt h el a s t ，w ea p p l i e dt h ep a p f r a m e w o r kt os y n t h e s i z eu n e q u a l l ys p a c e da n t e n n aa 盯a y s s i n c eb o t hd i f f e r e n t i a le v o l u t i o na n d p a r t i c l es w a r mo p t i m i z e rh a v es h o w e d e f i e c t i v e n e s si nt h es y n t h e s i sp r o b l e m ，w ec h o o s e o n ev a r i a n to fd i 疏r e n t i a le v o l u t i o n a n do n ev a r i a n to f p a r t i c l es w a r mo p t i m i z e ra st h ec o n s t i t u e n ta l g o t l 皿s ，t 0c o n s t l l l c t p a p i n s t a n t i a t i o n b yc o m p a r i n gt ot h es t a t e o f - t h e a r ta l g o 打t h mi i lt h e1 i t e r a m r e0 f s y n t h e s i z i n gu n e q u a l l ys p a c e da n t e n n aa r r a y s ，w ec o m p r e h e n s i v e l ye v a l u a t e dt h ep e r - i o m a n c eo fo b r a p p r o a c h o na l lt h ef o u rs y n t h e s i sp r o b l e m s ，o u ra p p r o a c hf o u 王l dt h e b e s to b j e c t i v ef u n c t i o nv a l u e s ，a n da l s os h o w e dt h eb e s t r e l i a b i l i t y i na d d i t i o n ，h e n w en e e ds o l u t i o n sw i t hh i g h e rq u a l i t y , o u r a p p r o a c hi sm o r ee 伍c i e n t 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 s ，r e a i p a r a m e t e ro p t i m i z a t i o n , e v o l u t i o n a r ya i g o r i t h mp o r t f o l i o s ，a l g o r i t h ms e l e c t i o n ，s y n t h e s i so f u n e q u a l l ys p a c e da n t e i l aa r - r a y s ，o p t i m a ld e s i g no fs y m m e t r i cn o n u n i f o r ma n t e n n a a r r a y s i v 1 2 1 微观层次方法综述 6 1 2 2 宏观层次方法综述7 1 3 工作概述1 0 1 4 本文原创性贡献1 l 第二章一种用于减小算法风险的实值演化算法投资组合框架1 3 2 1 问题描述与研究思路1 3 2 2 实值演化算法投资组合框架1 5 2 2 1 算法框架1 5 2 2 2 算法分析1 6 2 2 3 相关工作1 7 2 2 4 实现细节1 9 2 3 算法风险的度量标准2 0 2 3 1 算法风险度量的基本思路2 0 2 3 2 算法风险度量介绍2 i 2 3 3 讨论2 2 2 4 实验分析2 3 2 4 1 测试函数与实验设置2 3 2 4 2 实验结果与分析2 6 2 4 3 实验结果总结4 1 v 目录 2 5 本章小结4 2 第三章选择最优实值演化算法投资组合方案4 5 3 1 问题描述与求解思路4 5 3 2 基于实值演化算法投资组合的求解方案4 9 3 2 1 选择最优实值演化算法投资组合方案的基本框架4 9 3 2 2 目标函数5 0 3 2 3 投资组合方案的选择方法5 2 3 2 4 讨论5 3 3 3 相关工作5 4 3 4 实验分析5 9 3 4 1 测试函数与实验设置6 0 3 4 2 实验结果与分析6 2 3 4 3 实验结果总结6 8 3 5 本章小结6 8 第四章实值演化算法投资组合在天线阵列优化设计中的应用7 1 4 1 问题描述7 2 4 2 算法设计7 3 4 2 1 改进的差分演化算法7 4 4 2 2 基于投资组合的解决方案7 5 4 3 实验分析7 6 4 3 1 实验设置7 7 4 3 2 实验结果与分析7 8 4 3 33 7 阵元仅位置非均匀天线阵列综合7 8 4 3 43 7 阵元位置一相位非均匀天线阵列综合8 0 4 3 53 2 阵元仅位置非均匀天线阵列综合8 l 4 3 63 2 阵元位置一相位非均匀天线阵列综合8 2 4 3 7 实验结果总结8 4 4 4 本章小结8 5 第五章结论8 7 5 1 工作总结8 7 v i v i i 表格 表格 2 1实验中选取的1 3 个经典测试函数，以及关于这些函数特征的介 绍。更多细节可以参见【7 0 1 2 4 2 2 实验中选取的1 4 个c e c 2 0 0 5 测试函数，以及关于这些函数特征 的介绍。更多细节可以参见【7 2 5 2 31 1 个p a p 实例各自子算法的子种群大小。d e 、p s o 、p c x 和e s 分别代表s a n s d e 、w p s o 、g 3 p c x 和c m a e s 。2 5 2 4 s a n s d e ，w p s o ，g 3 p c x ，c m a e s ，g c m a e s ，以及所有11 个 脚实例在 一局( d = 3 0 ) 上所取得的最优解的目标函数值。 b e s t ，“m e d i a n ”和“w o r s t ”分别表示3 0 次独立运行后所得的解中 最优值、中值和最差值。对每一列，最好的解用黑体标注。2 7 2 5 s a n s d e ，、p s o ，g 3 p c x ，c m a e s ，g c m a e s ，以及所有11 个 p a p 实例在 o 也c 5 ( d = 3 0 ) 上所取得的最优解的目标函数值。 “b e s t ”，“m e d i a n ”和“w o r s t ”分别表示3 0 次独立运行后所得的解中 最优值、中值和最差值。对每一列，最好的解用黑体标注。2 8 2 6 s a n s d e ，w p s o ，g 3 p c x ，c m a e s ，g c m a e s ，以及所有11 个 p a p 实例在允。6 一允c 1 4 ( d = 3 0 ) 上所取得的最优解的目标函数 值。“b e s t ”。“m e d i a n ”和“w o r s t ”分别表示3 0 次独立运行后所得的 解中最优值、中值和最差值。对每一列。最好的解用黑体标注。 2 9 2 7 在三种阈值设定情况下，p a p 与其子算法以及g c m a e s 的双尾 威尔科克森秩和检验结果比较。检验显著水平为o 0 5 。31 2 8 在三种阈值设定情况下，p a p 与其子算法以及g c m a e s 的风险 度量值比较。 。3 2 2 91 6 个不同的迁移参数设置所取得的结果没有统计显著差异的函数 个数。 。3 6 2 1 0p a p 与分布式s a n s d e ( d d e ) 、分布式w p s o ( a p s o ) 、分布式 g 3 p c x ( d p c x ) 和分布式c m a e s ( d e s ) 之间的比较。3 7 2 1 13 个p a p 实例、d e 、p s o 、p c x 、e s 以及g c m a e s 在所有2 7 个函数上找到优于阈值的解的概率。3 9 3 1 实验中选取的1 3 个经典测试函数，以及关于这些函数特征的介 绍。更多细节可以参见【7 0 】6 0 i x 表格 3 2 实验中选取的1 4 个c e c 2 0 0 5 测试函数，以及关于这些函数特征 的介绍。更多细节可以参见【7 1 】6 l 3 3e p m p a p 与所有候选算法、b f 方法、f r a c e 和i n t r a - a o t a 的威 尔科克森秩和检验结果比较。检验显著水平为0 0 5 。6 2 3 4e p m p a p 与所有候选算法、b f 方法、f r a c e 和i n t r a a o t a 的风 险度量值比较。6 3 3 5 所有包含两个子算法的p a p 实例在2 7 个函数上的整体性能，用 公式( 3 4 ) 进行衡量。在每种时间设定下的最大值用黑体标注。 6 5 3 6 所有包含三个子算法的p a p 实例在2 7 个函数上的整体性能，用 公式( 3 4 ) 进行衡量。在每种时间设定下的最大值用黑体标注。 6 5 3 7e p m p a p 选择方法的选择准确率。 6 6 4 1d e + p s o 以及此前研究成果所获得的最优p s l l 值，表中每个数 值的单位是d b 。7 7 4 2 在3 7 阵元p o 问题上，d e + p s o 与d d e b o r l 在不同的阈值下， 所取得的s r 、f 上l 。、f 点 f e ，。z ，以及d e + p s o 获得的 f e 蹦。7 9 4 3 在3 7 阵元p p 问题上，d e + p s o 与d d e b o r 1 在不同的阈值下， 所取得的s r 、f 既。、f 互 f 至口霉，以及d e + p s o 获得的 f 忍t d o 8 1 4 4 在3 2 阵元p o 问题上，d e + p s o 与d d e b o r 1 在不同的阈值下， 所取得的s r 、f e o p g 、f n 、f 日一，以及d e + p s o 获得的 f e 础o 。8 3 4 5 在3 2 阵元p p 问题上，d e + p s o 与d d e b o r 1 在不同的阈值下， 所取得的s r 、f 民9 、f n 、f 霉，以及d e + p s o 获得的 f 玩坩。8 4 x 3 2 e p m p a p i m 3 、f r a c e 、i n t r a a o t a 和b f 方法在k c 4 上独立运 行2 5 次获得的解，总计算时间为丑。 6 7 3 3e p m p a p i m 3 、f r a c e 、i n t r a - a o t a 和b f 方法在凫c 4 上独立运 行2 5 次获得的解，总计算时间为乃。 6 7 4 1非均匀阵列天线示意图7 2 4 2d e + p s o 在3 7 阵元p o 问题上所取得的最优解对应的方向图7 8 4 3d e + p s o 在3 7 阵元p p 问题上所取得的最优解对应的方向图8 0 4 4d e + p s o 在3 2 阵元p o 问题上所取得的最优解对应的方向图8 2 4 5d e + p s o 在3 2 阵元p p 问题上所取得的最优解对应的方向图8 3 x l 第一章 绪论 第1 章绪论 演化算法( e v o l u t i o n a r y a l g o r i t h m ，e a ) 又称进化算法，是指从自然界的进 化与自适应机制中获得启发而发展起来的求解问题的计算方法【1 1 。大自然可以 作为我们解决问题时获取灵感的源泉。自从电子计算机发明以来，从研究生物 界的系统出发，探索其内在的微观机理，然后设计成具有一定智能的模拟系统 以解决实际问题，已经被证明是一个成功的方法。 演化算法以其简单、易于操作和通用性强等特性，在工程优化、过程控制、 经济预测以及模式识别等诸多领域取得了广泛的成功，受到人们越来越多的青 睐。其中，演化实值优化是演化计算领域最经典也最重要的研究分支之一。实 值优化问题广泛存在于工程实践与科学研究中。随着技术的进步，这些问题也 变得越来越复杂，往往具有非线性、不可微、多极值等特点，甚至有时候无法 得到优化目标的具体数学形式，从而使得传统的优化方法难以进行有效求解。 演化算法由于具有良好的通用性和很强的鲁棒性，并且不苛求任何与问题相关 的领域知识，因而在实值优化领域取得了广泛而成功的应用。 过去的数十年中，学者们相继提出了众多的演化算法，包括遗传算法 ( g e n e t i ca l g o r i t h m s ，g a ) 【2 】【3 】、演化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 4 i f 5 1 、演 化策略( e v o l u t i o ns t r a t e g i e s ，e s ) 【6 】一 9 1 、差分演化( d i f f e r e n t i a le v o l u t i o n ，d e ) t l 】 以及粒子群算法( p a t i c l es w a m io p t i m i z a t i o n ，p s o ) 【1 0 】等。这些研究成果从一方 面来说大大促进了演化计算领域的发展，从另一方面来说，也给从业者们带来 了如何选择合适算法的问题。实际应用中，用户提供的求解时间通常是有限的， 而各个算法的性能也各不相同。因此，在有限的时间内选择一个有效的算法是 有风险的【4 5 】。 本论文的主要工作目标是研究怎样对现有的演化算法进行投资组合设计， 从而使得在有限的时间内对给定的实值优化问题进行最佳的求解，并将其应用 于一个具体的工业设计问题上。 本章内容规划如下：首先，我们在1 1 节中对研究的问题进行详细的介绍。 接下来，在1 2 节中，我们对该研究问题的研究发展现状进行全面的回顾。然 后，在1 3 节对我们的研究工作进行了概述。最后，在1 4 节中列举了本文的主 要原创性贡献。 第一章 绪论 1 1 研究课题的背景与意义 实值优化问题广泛存在于工业与工程实践中，如结构优化设计、系统参数 识别、数据挖掘、人工神经网络的权值调整等等。作为最优化问题的一个重要 分支，实值优化问题一般包括决策变量、约束条件和目标函数三要素。不同的 是，实值优化问题的决策变量取值于实数域。不失一般性，考虑最小化问题， 可以表示成如下的数学形式 1 8 1 ： m i n i m i z e 厂( x ) ，x = ( z 1 ，2 ：2 ，x d ) s s u b j e c tt o ：g j ( x ) 0 ，j = 1 ，2 1( 1 1 ) 其中，x = z 。，z 2 ，x d 是一个d 维实值决策变量，搜索空间s 是d 维 实数空间r d 上的子集，目标函数f ：s 一酞是一个d 维实值映射。约束函数 g j ( x ) 定义了对变量的某些限制，包括技术上的约束、资源上的约束和时间上的 约束等。 根据优化问题的约束、目标、问题性质、时间因素和函数关系等不同情况， 实值优化问题存在多种不同的分类方法。例如根据有无约束条件的特性可分为 无约束和有约束优化问题：根据目标函数的个数可分为单目标优化问题和多目 标优化问题；根据目标函数是否与时间有关可分为静态优化问题和动态优化问 题，等等。本论文中我们的研究对象是单目标无约束静态优化问题这类最基础 的实值优化问题，如无特殊说明，下文中提到的实值优化问题都是指这类问题。 伴随着科学技术的不断进步，优化问题的复杂程度也越来越高，往往具有 非线性、不可微、多极值等特性，甚至无法得到优化目标的具体数学形式。因 此，基于迭代原理的各种传统数值方法，如单纯形法、梯度下降法、共轭方向 法等都很难对其进行有效求解。近年来，一些基于自然法则而提出的随机搜索 算法如演化算法等，由于具有良好的通用性和很强的鲁棒性，并且不苛求任何 与问题相关的领域知识，因而在实值优化领域取得了广泛而成功的应用。 演化算法是借鉴于自然界的进化与自适应机制而建立起来的一种通用问题 求解方法。它采用编码技术表示问题相关的复杂结构，通过对编码表示施加演 化算子和自然选择来指导和确定搜索方向。在问题求解过程中，演化算法通常 会维持多个个体( 即一个种群) 来组织搜索，并行搜索解空间内的多个区域， 通过不断迭代( 类似于自然界的进化过程) ，逐步获得质量更优的解。演化算法 不仅具有自组织、自适应、自学习、高度可并行化等优点，而且简单的遗传操 作和自然选择机制使其在求解传统算法难以解决的问题( 如非线性、不可微、 2 第一章绪论 多极值等) 时具有明显的优势。这些特点使得演化算法受到人们越来越多的关 注。 演化算法的起源可以回溯到2 0 世纪5 0 年代，当时b r e m e r m a n n 、f r i e d b e r g 、 b o x 等人在各自研究领域试图将自然界的演化过程引入到工程设计领域来设计 方法以解决工程中的优化问题f 1 9 l 【2 2 】。然而，一方面由于当时计算机还不够普 及且计算能力的不足，另一方面其方法研究本身也不够成熟，所以并未受到普 遍的重视。 6 0 年代起，由于诸多著名学者如h o l l a n d 、r e c h e n b e r g 、s c h w e f e l 以及f o g e l 等人在基础理论与算法设计方面作出的巨大贡献，演化算法得到了根本性的发 展。其中，h o l l a n d 于6 0 年代初提出遗传算法，并由d ej o n g 、g o l d b e r g 等人进 一步推广。与此同时，r e c h e n b e r g 提出按照自然突变和自然选择的生物进化思 想，对物体的外形参数进行随机变化并进行优化，演化策略的思想由此诞生。 后来，s c h w e f e l 将演化策略研究的成果作了归纳整理。1 9 6 6 年，l j f o g e l 等出 版了基于模拟演化的人工智能，系统地阐述了演化规划的思想。他将给定问 题描述成有限状态机，通过对其施加演化算子达到优化的目的。到了8 0 年代， 由于计算机性能的提高和并行计算机的逐渐普及，演化算法对计算机性能的要 求已不再是其发展的瓶颈。也由于其在众多实际应用中取得的成果，世界上很 多国家都掀起了演化计算的研究热潮。 由于早期对演化算法的研究是不同领域的研究人员独立开展的，在相当长 的时期内他们彼此之间并没有正式沟通，当时也没有“演化算法”这一名称。 直到9 0 年代。遗传算法、演化策略与演化规划的研究人员才开始逐步接触并了 解到对方的研究成果。通过深入交流，他们发现彼此的研究成果所依赖的基本 原理都是基于自然界演化操作和自然选择等生物进化思想，具有惊人的相似之 处。于是他们提出将这类算法统称为“演化算法”。 作为一种迭代算法，演化算法在求解问题时一般是从多个解开始的，这多 个个体的集合称为一个种群，记为p ( 9 ) = x 。，x 2 ，x n p ) 。这里夕表示迭代步， 称为演化代；是对一个解的编码表示，通常也称为个体；尸是种群大小， 一般在整个演化过程中保持不变。当演化开始时，算法对当前个体施加演化算 子以产生新的个体，再对新个体进行适应度评估和选择操作，不断迭代而逐步 改进解的质量，并期望最终收敛到最优解。这些当前个体称为父亲或父个体， 产生的新个体称为儿子或子个体。由此可见，编码机制、演化算子和选择机制 是演化算法的三大核心要素，其中演化算子又主要包括交叉( 重组) 和变异两 3 第一章绪论 种。演化算法的基本框架可参加算法1 。 算法1 演化算法的基本流程 x t ：第i 个个体； n p ：种群大小； p o p ( g ) = x 1 ，x 2 ，x n p 第g 代种群； 算法：