（应用数学专业论文）无约束全局优化算法及复杂性理论探讨.pdf

摘要 本论文的主要内容是关于无约束全局最优化问题的研究 我们对无约束全局优化问题影响算法策略选取的特征进行了分析，在此 基础上对无约束全局优化问题进行了分类，同时指出了各类问题应当采用 的算法策略我们也指出了依概率收敛的结果并不能保证算法的有效性 我们对影响无约束全局优化问题困难程度的各种特征进行了综合分析， 在前人对无约束全局优化问题全局复杂性刻画的基础上，提出了广义各级 吸收域的概念，并进而指出无约束全局优化问题复杂性的刻画应考虑的因 素，给出了几种复杂性刻画的方法。这为设计测试函数、开发算法时利用函 数特征提供了基础。 、1 除了直接算法外，本文中的算法都依赖于最优吸收域的大小及极小点的 多少。 针对最优吸牧域比较大的情况对极小点较少的问题进行了分析，提出 了两种改进的多级单连接方法，数值结果表明我们的改进是有效的；对极小 点较多的问题进行了分析，提出了一种变形的单连接方法，数值结果表明在 此时，对采样点进行归类的方法尽管比模拟退火法好，但是要比受控随机搜 索方法差。 针对最优吸收域比较小的情况在假定函数只有一个广义一级吸收域的 前提下，在极小点比较少时提出了一种采取在小区域上采样单归类转移策 略的算法，数值结果表明了这种方法的有效性；在极小点比较多时提出了一 种偏移采样小区域中心的方法，数值比较结果表明这种策略是有益的 对一般无特别假设的无约束最优化问题，在采用非均匀的卢分布采样的 基础上，提出了一种新的利用插值估计函数形态的方法，同另外一种也用卢 分布、插值的高效受控随机搜索方法相比，我们的插值方法更简单，数值比 较表明，我们的算法可以同它竞争了 i r e s e a r c h o na l g o r i t h m sa n dc o m p e l x i t y a n a i s i s0 fg l o b a l0 p t i m i z a t l 0 nw i t h o u t c o n s t r a i n t s s h a o w e iw a n g ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f y a - x i a n gy u a n a b s t r a c t t h et h e m eo ft h i sd i s s e r t a t i o ni s g l o b a lo p t i m i z a t i o nw i t h o u tc o n s t r a i n t s t h eu n c o n s t r a i n e dg l o b a lo p t i m i z a t i o np r o b l e m sa r ec l a s s i f i e da c c o r d i n gt ot h ec h a r a c t e r s w h i c hu n d e r l i et h ec h o i c eo fs o l u t i o ns t r a t e g y f o re a c hc l a s s ，w ed e t m l e dt h e c o r r e s p o n d i n g s t r a t e g y m e a n w h i l e ，i t sn o t e w o r t h yt op o i n to u tt h a ta na l g o r i t h mc o n v e r g e si np r o b a b i l i t y d o e sn o tg u a r a n t e ei t se f f i c i e n c e a s y s t e m a t i cs t u d yo ft h ef o r e g o i n gc h a r a c t e r si sc a r r i e do u t ，t h e r e b y g e n e r a l i z e dg r a d e d r e g i o no fa t t r a c t i o ni si n t r o d u c e d w e a n a l y z ew h a tc h a r a c t e r ss h o u l db ei n c l u d e di nt 1 1 ec o m p l e x i t yi s s u e s e v e r a lc o m p l e x i t yr u l e sb a s e du p o nt h eg e n e r a l i z e dg r a d e dr e g i o no fa t t r a c t i o n a r ep r e s e n t e d a l lo u ra l g o r i t h m se x c e p tt h ed i r e c tm e t h o dh a n go nt h ew i d t ho ft h eo p t i m a lr e g i o no f a t t r a c t i o na n dt h eq u a n t i t yo ft h el o c a lm i n i m a t w ok i n d so fm o d i f i e dm l s lm e t h o d sa r eg i v e nw h e nt h ew i d t hi sl a r g ea n dt h eq u a n t i t y i sr a t h e rs m a l l s o m en u m e r i c a lr e s u l t si n d i c a t et h a to u rm o d i f i c a t i o ni sr e w a r d i n g w h i l et h ew i d t hi s l a r g ea n dt h eq u a n t i t yi sr a t h e rl a r g e ，am o d i f i e ds lm e t h o di sd e v e l o p e d n u m e r i c a lc o m p a r i s o n si n d i c a t et h es o l u t i o ns t r a t e g yw h i c hc l a s s e st h es a m p l e p o i n t s i n t od i f f e r e n tc l u s t e r sb e h a v e sb e t t e rt h a ns i m u l a t e da n n e a l i n g m e t h o d ，h o w e v e r ，s l i g h t l yw o r s e t h a nt h ec o n t r o l l e dr a n d o ms e a r c hm e t h o d a st op r o b l e m sw i t hn a r r o w w i d t h ，w eo n l yc o n s i d e rt h ec a s ew h e nt h eo b j e c t i v ef u n c t i o n h a sau n i q u eg e n e r a l i z e df i r s tg r a d e d r e g i o no f a t t r a c t i o n w h e nt h eq u a n t i t yo ft h el o c a lm i n i m ai sr a t h e rs m a l l ，w ed e v e l o pam e t h o dw i t hw h i c h as m a l ls a m p l i n g r e g i o ni st r a n s f o r m e da n dau n i q u ec l a s si sm a i n t a i n e d ，w h o s ee f f e c t i v e n e s si s c o n f i r m e db yo u rn u m e r i c a lr e p o r t s w h i l et h eq u a n t i t yo fl o c a lm i n i m ai sr a t h e r l a r g e ，w ed e s i g na m e t i m di nw h i c ht h ec e n t r e o ft i l et r a n s f o r m e ds m a l ls a m p l i n gr e g i o ni si l i a s e d t h i sa l g o r i t h mw o r k sf a i r l yw e l le v e nf o l 8 0 l n et o u g ht e s tp r o b l e m s f i n a l l y ，ad i r e c tm e t h o d i sp r e s e n t e df o rg e n e r a lu n c o n s t r a i n e dg l o b a lo p t i m i z a t i o np r o b 、 l e man e wq u a d r a t i ci n t e r p o l a t i o nt e c h n i q u ea n dn o n u n i f o r m 口d i s t r i b u t i o na r ee x p l o i t e d 、 o u ra l g o r i t h mi sc o m p e t i t i v ew i t hak i n do f h i g he f f i c i e n tc o n t r o l l e dr a n d o m s e a r c hm e t h o d s k e yw o r d s ：g l o b a lo p t i m i z a t i o n ，p r o b l e mc l a s s i f i c a t i o n ，c o m p l e x i t y ，d i r e c t m e t h o d ，s t o c h a s t i ca l g o r i t h m 第一耄绪论 最优化理论与算法是一门应用性很强的年辍学科。最优化问题的 一簸形式灸 翼娶m ) ( 1 - 0 1 ) 菇中。g r n 怒决策燮蹩，( g ) 凳毽棵函数，x c r 8 必约糸集域称搿行 竣。特爨缝，热暴终泉集x = 嚣”，裂凝魏稼游题豁凳茏翁寨最谯讫滔题 。m ，i n f ( 。) 一2 ) 举文主鼹研究无约柬优化问题( 1 0 ，2 ) ，其中目标瞒数，( m ) 为非线性连续 躐数。砖子，和) 只骞令弱薅投小蔗戆祷爨，譬热，国楚产撩蠡蘧数 时，已经有了潍彻的理解，理论及方法也很成熟。在本文我们要考虑 的饯化阔题跑鞋标爨数( 哥舞熟骞多令极小点，这样传缝戆锋黠只骞 个局部极小点的局部最优化算法将力有所不及，这种优化问题即鼹 翡线性优化中的全局优化阏题。零文只考虑茏约束全滕优化闯题。 警然为了便于处理，我们并不象在无约束局部优化理论算法中那样 对可行域仅仅简单设为r n 。因为对有多个极小点的憾况，上述假设 不w 行，薅基辩实琢侥貔阏题我们氇没必要考虑整个舻。本文瑕邂 2e s = f l i “1 ，其中 = ( ! l ，如，! 抖) ，“= ( 抛，。) 为我们关心的区域的下界 鼍羔器，帮瓠强斑b 一1 ，2 ，m 我镶缓定瑟考察运麓鹩赞蠢较小患 均在p ，喇的内郝，这挂就不甄子将惩约束优化蝴题转换为繁约衷的婀 熬。我稻这榉缓设将梵努辑滔蘧翻造条转，舞整这群瓣穰设并不彩璃 阍题懿本矮。荧予极小点搿在融珏| 渡界土熬及其它一般媾约窳静全爆 筑凭离熬露参耀溉，f 2 s ，羚霹，姆罐，鎏l ，f s 透， 全局优纯澍题是饯讫瓣鼹孛羧麓爨港鳇个分支。穗对予局帮津 线性钱纯，它的理论慧算法都稷誉完善毽这势不意辣饕全楚爨纯勰 趱不羹繇。实黼上，裔很多翔局帮优纯方法来瓣淡翡游越并凑证藕游 蹶裁楚仪有爱帮一个援夺煮，耜获，其中毒缀多已涯鳃蒸禽翁多个鼹 稚羧撬点。通常静局部犹能雾法不髓有效遣解决这类闲逶。斑雨获实 溺的聪熙来看，对全羯捷纯阏瑟嚣黉存燹专门、更有效豹方法来处漾 宗。这种需要穗经被试翔，并盈裙不少垒两优纯方法西经被设计蹒 帮一章绪论博士毕业论文 袋。褪楚，对菜一具髂趣蘧泉说，到底郡秘方法遗矮还没有一令较为 明晰的标准。从每篇关于全局优化算法的文章看来，很难下结论到 底郡秘方法更好。慰各秘雾法送行综合浮述无疑会促进对算法的谬 价、开发。首次在这方面的工作当属d i x o n 和s z e 9 6 合编的两卷本t o w a r d s g l o b a lo p t i m i z a t i o n 【1 7 】，f 1 8 3 里西包含了早期关予全局优化方葱的文章。这 两本书使全局优化从零星工作走列了更多人面前，也加快了全局优 化的研究。关予无约束全局优化问题，在f 5 5 】里较为详尽的讨论了当 时的情况，方法等。勇外，在阻6 l 巾对无约束全局优纯的方法也骰了 综述。他们不约而同地指出无约柬全局优化的研究还处在刚起步阶 裁，氇隧开始譬| 起更多静注意，虽然各静浓簿技巧不少，毽美予逮黧 技巧的系统分析与广泛的实验验诞还没有。在【2 8 】中对备类全局优化 瓣蔻佟了一个慧俸奔绥，缀不幸黪楚，对笼约寒全爨臻化海麓，簇了 带有或多或少全局性限制条件的问题( 如l i p c h i t z 常数等) ，分析较为清 淤，理论结果较多之强，其絮一般焉约束全曷拨伍超鬈的理论仍稷不 宪善，算法也依然是各有千秋，缺惹系统分析与比较。近年来的文献 巾对无辫加条传的无约束垒局优化超题的理论工作也不多，虽然瑟 的算法还在不断出现由予缺乏理论分析及客观的比较平台，使得算 法的比较也缺乏客观性。即便是对有附加条件的无约束全局优化， 除了理论分析较多之外，其算法的表现行为也豢剃很大，嚣藏在优张 中，这热附加的全局条件往往很难验证与估计，这也限制了算法开发 巾对这麓分桥缝采静稠震 察 1 1 论文内容 包括此章在内，本文分为八章我们将在文中讨论如下问题； 一无约隶全嚣傀证海题静努炎及冀法毙较溜蘧 二无约柬全局优化问题复杂性分析， 三，壤据爨佐级l | 筻壤鹣耪霹大小，有钤蔻性戆设诗算法+ 四对无特别假设的无约束全局优化问题，设计直接算法 五砖魏谤提取萼裂弱影嚷秃约素龛局砉l 己纯超题瓣特蔹遴行考 2 楚耄绪论博士毕业论文 我们对无约束全局优纯问题影响算法策略选取的特 芷( 如最优吸 收域的大小、极小点静数量、函数是否有一定的整体趋势等) 进行归 纳，并在此基础上对无约束全局优化阔题进行分类，对各类问题应当 采用的算法策略进行分析。通通分类，我们得知现有的测试函数集蹙 不完善、不系统缺乏广泛代表性的我们两时指如对秃约隶全局优化 朗题，依概率收敛的结果并不能保涯算法的有效性，算法的比较应该 对不同的问题，不同的停止准则更公正地加以考虑 我们对影响无约束全局优化简遂困难程度的备种特征进行综合分 析，在考虑其它入结果的基础土，提出广义各级吸收域的概念并进 | 嚣提出几秘亥4 强优化闻题困难程度的度量标准这些缩果将有助予 在算法中更好地利用函数的特征 针对最优吸收域比较大的情况对极小点较少的阂题进程分析， 提出对多级单连接方法改进后的魏秽算法，数值比较的臻果表明我 们的改进是有效的；对极小点较多的问题进行分析，提出一种交形的 荜连接方法，数值院较的结果表裙在极小点很多时，对采样熹进行归 类的方法不是很有效 针对最优吸收域比较小的情况在假定函数只有一个广义级吸 l 叟域的前掇下，在极小点比较少时提出一稀采取在小区域上采样单 扫类转移策略的算法，数值结果表明这种方法的有效性；在极小点比 较多时提出一种偏移溪榉小区域中心的方法，比较绣粜表明这种策 略是有益的 对无特涮假设的无约束最优化闫题，在采用非均匀豹芦分带采样 的基础上，提堪一辨裂用援值估计函数形态的方法，弱另外一秘也 用p 分布、插值的高效受控随机搜索方法相比，我们的插值方法更简 单，数值比较表明。我们的算法冒彗王阔它竞争 对优化闺题中各种特征的提驭与利用傲分析。撂出企图褒算法中 对莱些特征加以摄取并列用是困难的对有些特征，即便是在融知的 情况下，有效和用它们也罴困难的 l 。2 基本知识及记号 给定鳓s ，设y l = y ( z ) ，定义数对忍= ( 轨) 戈一次观测。一个向量 3 第一章绪论博士毕业论文 z ( m ) = ( 钆锄一，z 。) 称为观测向量。则一个优化算法4 可以定义作一族 函数 n 。) 即a = ( ) ，其第i 个观测点是甄= ( ( 乃，j = 研) ，( p ) ) 依 赖于前i 一1 个观测点，其中，( p ) 是除了，( z ) 连续之外函数类p 所具有的 其它可获取的信息( 如l i p s c h i t z 常数) 。从k 个观测来估算全局极小值通常 是取y 。t = m i n - c y ，作为全局极小值的一个近似。优化算法的收敛亦即 y o t _ + 囊，( 2 ) ，- + o 。 ( 12 1 ) 对于局部优化问题，其终止准则是确定的( 梯度等于o ) ，然而对于 全局优化问题，还没有一个通用的准则来断定全局最优已经达到。 事实上，对于一个一般的( 无附加条件如知道l i p s c h i t z 常数) 无约束全 局优化问题，在程序有限执行的情况下，是不可能断定是否达到最 优值的：求得一点a ，使得在该点的函数值f ( a ) 与最优点z + 的值i ( x + ) 之差l ，( o ) 一，( 矿) i 0 为给定的正数如果设某算法a 产生的点列 扛1 ，2 ，在s 上是稠密的，由于，( z ) 的连续性，则显然有 。m i x o s ( z ) + m j g s ( z ) ，”_ + o 。 ( 122 ) 如果算法a 在s 上对任意连续函数，( z ) 均收敛到函数的全局极小，但 是算法所产生的点列x t ，i = 1 ，2 ，在s 上并不稠密，则存在s 上的一点n 及一个正数6 0 ，使得以n 为中心，d 为半径的球内无序列x ，i = 1 ，2 ， 中的点，即i n 一i 6 ，i = 1 ，2 ，则可构造函数 i ，。i 9 ( z ) = m j g s ( z ) 一e + 宁( 搿m ) 一骝m ) + e ) ， ( 1 2 3 ) 其中e 0 ，则对函数f ( z ) = m i n ( f ( x ) ，9 ( 。) ) 与，( z ) ，算法a 产生的点列是一样 的，因为按照嘶的定义，甄仅依赖于x j ，( q ) ，j = 田，但是，m i n l _ o ，e 0 ，使得集合 玛= 和s i ，( z ) s ，( 蛳) + e ，陋一2 ；i isd ) 鹣溅废m ( 玛o ，我稍定义每令稷收域a ；垂孽穗两大小秀： 舻鬻， 寇义每个吸收域a y 的( 相对) 火小为： 矿= 鬻， ( 1 29 ) ( 1 , 2 1 0 ) ( 1 2 1 1 ) 羚疑地，记岔鹣大小必矿，a 戆太小为矿，+ 对一个给定的全局优化问题，p * i 是一个非常重要的特征，因为 一般的米说，缀多全局优化方法都在最后有一局部优他过程以提高 求解质激p + ，的大小在很大程度上影响了局部优化过稷所得的解是 众局最优的概率大的p + 意味着问题容易求解。当然从实际观点来 瓣，若p ，锾小，瓣这梯鲍最傥解瓣稳定往缀差，辩交萤小翡撬秘郄弓l 怒目标函数大的变动而且，从技术上来说，也很难做到这一点。由 予数学模型逶鬻是实耩瓣熬静近歙，在这耱点辫涯模燮往往不麓攫 好地代袋实际闯题的性态。这意味着一个适用的好的极小点的吸收 域应该巍一点蕊不应怒一个尖峰。援步 ，慰比较炎滑豹躅数，霹以设 6 第一直 绪论| 尊士毕业论文 想函数值较小的极小点，其吸收域也相应地较大( 排除尖峰) 。从【1 8 】中 兹测试函数来簧，均有m a x 一如傅p ：= 矿，这榉魏蘧数是较易瓣决豹。熟 果现实中所有问题都有这种性质，则无约束全局优化问题的求解将不 象艨来想象中戆那么嬲难。 另外，在本文中，著不特别说明，我们假定所有局部优化都是成 功的，即可以找到初始点所在吸收域对威的极小点的一个小邻域内 的点。为方便起觅，我们称找蓟全两最优的意思建找列全局极小点和 ( 或) 全局极小值。一个假定是若不特殊说明，对姻数的了解仪能通过 逐点计算函数镳( 以及梯度) 来迸荦亏 7 第二章无约束全局优化问题的分类及算法比较 在这一章我们主要考虑关于无约束全局优化问题的一些分类及 算法比较结果。对于无约束全局优化问题，考虑的较多的是算法的分 类及各类算法对同样测试集的比较。这样做在一定程度上缺乏科学 性。因为对全局优化来说，算法的终止条件、算法所企及的目标等方 面差异很大，种类繁多的各种算法所基于的模型也很不一样，对各种 问题的表现也相当不同。这同局部优化问题有很大差别，在局部优化 里，虽然算法实现不尽相同，但算法所基于的模型大同小异。目前来 说，没有哪一种全局优化算法比其它优化算法出色许多。因此对全局 优化问题本身加以考察，并开发有针对性的算法很有必要。在本章和 下一章，我们将对全局优化问题本身进行分析，以便能够在开发算法 时有的放矢。对优化方法的选择，意味着优化方法的一些可比较性 因而，我们也将对算法的比较做一些探讨，这二者实际上是相符相称 的，单纯的比较问题与单纯的比较方法都是不可取的。 2 1 无约束全局优化问题分类 在本节我们仍然只考虑无约束全局优化问题，也即找到+ s ，= ，( + ) 使得对给定的e 0 ，有i ，+ 一，i r 0 由于几乎所有较好的无约束全局优化方法都包含有随机部分， 即利用随机的方法来对，( z ) 在s 上的形态加以估计。基于这种基本假 定，我们可以把问题依据其函数形态给予分类当然在实际应用时， 应该对所产生的信息加以利用，这样会使初看起来形态很复杂的问 题变得较为容易解决，尽管如此，这种分类还是很有必要的。 当开发出一种新算法后，现行的方法通常是给出对某些测试函数 新算法与已有的算法的比较通常情况下，测试函数除了在维数方面 有系统的选择以外，是相当随机的。现行常用的测试函数通常较为容 易解决，且缺乏代表性。其中有些问题还仅有一个极小点，可用局部优 化方法解决这并非说基于现行测试函数集的比较无意义，而是认为 8 第二章问题分类及算法比较博士毕业论文 公平的测试函数集应该具有足够的代表性，对所有类型问题都应有 所体现。局部优化问题的测试函数已很系统。带约束的有规则的全局 优化问题的测试函数集也已经有很系统的表述。对一般无特定假设的 无约束全局优化问题，测试函数的数量、代表性都很不完善。基于这 样测试函数集的比较结果还不能十分令人信服。当前无约束全局优 化方面测试函数集的不完善，部分原因是因为缺乏对问题依据某种复 杂性度量的很好的分类，部分原因是缺乏对函数本身内在性态的深 刻了结，当然也与其中很多测试函数出现时间较早有关。对算法的分 类在【1 8 ， 5 5 ，【4 6 等中已有了基于不同分类标准的较详尽表述。对问题 本身依据某种复杂度加以刻划，可见【1 6 4 】在【1 6 中，对问题的分类 很有代表性，但并未对分类问题做进一步分析，在【5 4 中，对问题分 类做了较为深刻的分析，但是其分类较为粗糙，还有待进一步的细化 与深化。因而，总的说来，为了公平地比较各种算法，也为了有效地 提供测试函数，对优化问题分类加以研究是很有必要的。这样，当问 题本身的一些特性可以获取时，利用这些特性的优化方法应该具有一 些优越性，这种分类也对有针对性的优化方法的开发也不无裨益。 2 1 1 问题特征与求艉策略 在本小节我们考察无约束全局优化问题的特征及其对优化问题求 解困难程度的影响 当求解一个全局优化问题时，各种方法的求解过程与结果不尽相 同，这除了算法本身的原因外，还取决于问题本身的特性。粗略地 说，求解优化问题的困难程度依赖于问题的如下一些特性： 1 全局最优吸收域的大小p * l ， 2 极小点的数量。 3 极小点的分布，极小点的函数值的分布， 4 函数对各变量的敏感程度。 如果最优值，的吸收域很大，从随机采样的观点来看，采样点落 入这个区域的可能性就大一些，这样的问题应该比具有较小，+ 吸收域 的问题好解决当纯用均匀随机采样的方法时，采样，。次，( 1 一p ) ”，e 是，吸收域内无采样点落入的概率如果，。可以很大，那么即使较 小的广的吸收域，采样点落入其内的概率也将很大如果，。不能很 大，那么对较小的，的吸收域，采样点落入其内的概率将会很小。 9 第二肇 问麒分类及算法比较博士毕业论文 极小点的分布及相成函数值的大小影响全局优化问题的是可否对 全局优化采取某瓣适应性策略，在 5 4 l 中，馋誊引入嵌套性来攒述提似 的观点。嵌套指的是最优点附近是否有一些非全局的极小点，以便 可以通过对这些极小点附近进行采榉，以求得到越来越好的极小值以 至最优。就象一个碗一样，最小点夜碗底，其它极小点在碗的表面。 嵌套意味精即使矿，很小，也可以采用适应性策略使采样点以较大概 率落入广吸收域内嵌套只蔻极小点的分布及相成极小值的大小影响 优化问题的一种特例，即使问题非嵌套，依然有很多信息可以利用。 缀小蠢豹数鬣通常和广吸收区域的大小是福茨的，当稷小点增多 时，通常广吸收区域也将变小。尽管如此，极小点的数凝多寡在本身 也憝税纯游题静一个重要特渡。困为极小点数蟊豹增多将使稀都搜索 变得低效或无效。 葫数对各交囊豹敏感翟澄以及备变量变互作糯辩影稚毽程很大程 度上影响问题的难度，合理的处理将会使问题变得较易求解。 当然实际阕麓中豹倪纯，s 裰霄酉麓并菲是一个n 缨方钵，因而s 的形状也影响问题的困难程度，其像象维数，每个极小值所对应的檄 小煮静多少等都彩璃游题静辩决。另辫，黧莱j 爹 荧心豹嚣域静缩放影 响，+ 吸收域的相对大小( 与整个s 比) p ”，一般来说，p ，较大者较易解 决。 在全局优化照，通常采用的策略有全局策略、局部策略、适应策 略等方法。 企局策略通常用随机的方法来对整个s 进行搜索，以便找到，+ 吸 l 雯域悫豹熹，溺瓣毽缳涯求麟戆残渤。 局部策略通常用常见的局部优化方法来求解一个局部较好的点， 它懿摇楚翔局部缆诧鹣是郝下降策貉纛京姿蔫豢辩透采样荻获取一 个熨好的点的整体下降策略其中局部优化也常在最优化过程之终 采鼷以握囊求戆耱度。姿然不用是郝霞纯方法，露是使翔整体下降繁 略磁某一点找到一个更好的点的方法，在问题有某些嵌套性质时，对 逐步求鼷焱怃也是舂蠡鲍。 屁式的局部壤略的效果也可以通过其宙方法来获得，采用适应性 技搿即可褥到类似的结果。逶应性筑路即怒我们在全鼹搜索懿，在较 好的点的附近进行更多采样。适应性方法在没有局部策略的优化算 第二章问题分类及算法比较博士毕业论文 法中经零采用，这样随着算法的搬移，全局策略逐渐变为局部策略。 其它便厢适应策路的缘由是基于全简极小点有菜些嵌套r 陡。当全局极 小点有嵌套性时，在较好点附近进行适应搜索是有益的。 其它镱略还有如单个工作点策略( 模拟退火法、基因算法) ，工作集 策路( 受控疆枫攫索) ，多点起始策珞，聚类法等。这些方法通常只夜特 定的方法中使用，在讨论涉及到它们方法时我们蒋对它们进行讨论。 2 1 2 问题分类与求瓣策略 我们将闯题分为以下几类： 1 单峰间题，具有单个极小点； 2 多蜂阕题，具蠢为数不多的援小点，p 7 较大； 3 极多鳝简越，箕有为数众多的极小点，p + 7 较大； 4 多蜂厕题，具森为数不多的极小点，p 较小，有嵌套性； 5 多蟓筒磁，其有为数不多翡极小点，p + 7 较小，无嵌套，隧； 6 极多鳋问题，舆有为数众多的极小点，p ，较小，有嵌套性； 7 极多蜂| 薅题，共有戈数众多约极小点，p 7 较小。无嵌套性； 8 复合问题，在s 的不筒子区域上问题表现为上述不同的问题。 对于笈合问题，可能的策略蔻对区域进行箭分，然后对各个子区 域进行处理我们不再对这种情况进行考虑。 一些零见的测试耀题灼上述特性归类见下表，其中加星号的郝分 的绪采取自 5 4 】 常用测试菌数归类 1 1 第二蠢河题分类及算法比较博士毕监论文 函数名1 矿，极小点数来源 p o w e l l0 奄0l f 5 4 + k o w a l i k0 0 01 【5 4 】+ b r a n i n ( b r ) 0 ，0 03 f 5 5 g o l d p r i e e ( g p ) o5 54 55 】 s h e k e l 5 ( s 5 ) 06 5莲 f 5 5 s h e k e l 7 ( s 7 ) o6 57 【5 5 】 s h e k e l l o ( s l o ) 06 51 0 【5 5 l h a r t m a n 3 ( h 3 ) 0 3 04 骚5 3 h a r t m a n 6 ( h 6 ) 0 3 04 【5 5 1 h o s a k i03 52 5 4 ) 4 s i ( b ) ：p 3 0 6 63 7 f 5 4 】4 l e v y l o o 1 51 0 1 0 墨舻 s h u b e r t 3 ( p 鼬 o 6 55 a ? 【删+ 尉f 丑) ：p 4 0 8 ? 阳+ 8 i ( b ) ：p 5 0 9 5c o ? 【5 4 】+ g u i l i n 29 嚣睁61 5 2 t i g u i l i n 3o 9 9 9 9 9 91 5 0 f 2 7 】 g r i e w a n k 20 。9 95 0 0 7 【5 5 1 + g r i e w a n k l o0 9 3 o ( 1 0 3 )【5 5 】+ s h u b e r t 5 ( p 1 6 ) 0 9 51 5 5 7 洚嚷8 s i ( b ) ：p 6 0 9 9 7 o o ? c 5 铲 单峰海越是羼郝捷饯超题，静苓霉要全局搜索，全局蒙略可以搜月 以确保备局部优化算法确实收敛予全局最优，测试函数p o a o e l l ，k o w a t i k 已表明是仅有一个极小点，采用单峰函数作测试函数或者是为了察 孵优化算法是否应对两部优仡阎题也有好的袭现，因为癸际问题中 缀多并不麓遘怒擎峰述是多峰 对予( 极) 多锋耪蘧，置p 。，较大辩，全是策珞、局部策略、与逶塞牲 策曦对闯题戆求解鄯鸯所帮助，视拷擞露定。当极小点很多时，局部 整体下降策略比局部优化销略更为有效当极小点不是很多时，很有 效的算法如多缀单连接( m u t i l e v e l s i n g l el i n k a g e ) 可采用目前相当多的测 试瑙数属予这一类，因而并发其它类鼙的溺试函数禳有必要。 1 2 第二章 阐题分类及算法比较博士毕业论文 对于( 极) 多峰嬲题，p * l 铰小，又无嵌套性的特况，全局投小点是孤 立的，任何适应性的策略( 集中力量于较好点的附谶) 都是不可取的， 阂为这将减少采样点落入，+ 吸收城的概率。因而只能主要采用全局 策略。当稷小熹不是很多辩，遗当戆采爝两部策略墩有爨予海题豹解 决。如果要以大概率找到全局最优，将会耗费太多的资源，因耐对这 类问题，般仅能企及找到一个相对较好的点而已。这类问题有多体 游题( m a n y b o d y ) 等。 砖于( 极) 多峰趣题，p * y 较小，毒嵌囊性的情提，当极小点较多对， 全局下降将有所帮助。当极小点较少时，局部下降将会有所帮助。无 论极小点多少，由于嵌套性，采用适应性策略都将极大提高优化方法 的效率当然全翳策路镄不胃省去。这类瓣瑟有蒂嗓毯数等。 2 。2 优诧方滚毙较 为了公正的比较雾法，测试函数集应该包含有不同类型的测试问 蘧象b r a i n ，s h e k e l 5 ，s h u b e r t 3 ，g r i e w a n k ，多体闻题等。 对毯纯方法戆毙较可以说是一个鼹弱撂超越：褒质麓，低消耗( 戤 间、空间) 对局部优化，其解的质量很容易确定，因而算法的比较也 较为容易，然而对全硒优化其解的质量很难确定，闵而这种比较依赖 于对各种因素酶投饔。 巍某一全局优化算法髑来求解特定阔题时，其求碍灼勰的质量依 赖于停止条件，因此我们先对停止条件加以探讨每种方法都有其终 止性条件，停止礁粥有时麓于一些理论的收敛性质因为一个全局优 亿趣题逶常簌缺乏一些垒是燃条辖( l i p s h i t z 常数钧瓣，只憨褥凄一魑 概率意义上的结果：随算法的推移，全局极小被找到的概率趋予1 然 而算法的有限终j t 性要求算法有有限的收敛性：在有限步内找到，+ 暖毂域离酶一个赢，并获这个点宿动屑部落纯方法，置成功静找鬟满 足一定糖度要求豹全局最优点。因覆，即便是一个方法依概率收敛， 当算法有限步之后终止时，也不可能对全局最优被找到的概率加以 估计。当然如果知道p * l 的大小或它的一个正的下界，当多点越始法 豹每个局部後纯都没有失误( 在一个极夺纛吸收域瓣点不搜索弱另一 个极小点) 时，我们可以估计解被找到的概率【5 5 】 第_ = 二章阃溅分类及算法比较博士毕业论文 再者，对任何无收敛性的算法傲一平凡的变幼，我们都可以便它 以概率1 收敛。铡如每2 螅幂次步对加入一个在s 上鼹于圃一均匀分 布的点。这样做实际上并不影翡算法鹃实繇表现。 这意味着从实用观点来看，优化方法在理论上其有概率收敛的性 质并不能保证算法有好的表现，保证算法成功还需要其它的一冀度 量。例如当知道p ，的一个正的下界时，把解过程中所产生的随机点 的个数作为一个度量哥以计算出算法终止时无点落入吸收域嬲檄 率。这样当算法终止时，我们可潋对解的质量有一个量静估计。 优化算法通常用达列全局罐优所需的函数的计算次数，或c p u 对间来缝量好坏对个具有随机特性的全局优化算法来说，方法m 藏者拜予闰题p 是一个封，功o ( e ，q ) 静映射，其中窘是求解过程中黪使 用的资源( n s ，内存销，q f o ，1 】楚全局最後被找到静概率。当有两种方 法时- ，眦施于问题p 时，要比较的楚，啦) ，( 豌，啦) ，如采有对占绝对优 势( 韪妫，q l q 2 ，( e l ，a 1 ) ( e 2 ，q 2 ) 或相反) 或者是e t = e 2 或者是q l = q 2 时 比较才可褥为了比较溪耪算法，最麓单的方法是固定e ，对每种算法 均遴行若干次来求解蘅一闯惩，然唇求出各音解静质量q l ，妇并进行比 较。这应该在e 具有多个不问值时都进行院较，以便褥矗l 更精确、更 公正的结果当然也可固定q ，对e 进行类似的操作。 从各种文漱来看，算法的比较基本上没有基于上述方法。有的只 是筒单的函数计算次数比较或计算黠阕比较。其中有些的毙较逐 相当经验化，新1 日对比往往基于不同的停止条件，以使新方法摄得更 有效。 1 4 第三章无约束全局优化问题复杂性分析 在这一章我们主要考虑关于无约束全局优化问题的一些复杂性分 析结果。为了能有效地开发算法以处理上一章中介绍的各种类型的 问题，仅有分类这样的定性分析方法还不能满足要求。实践的需求决 定为了开发更有效的算法、设计更具有代表性的测试函数还需要对 问题进行定量的分析。 现在已有很多研究工作对各种优化方法进行对比。然而正如上一 章所述，这些比较中很多要么基于经验、要么其测试集代表性不够。 另外尽管有不少算法的渐进分析结果，然而依概率( i ) 收敛的结果并 不能代表算法的有限行为( 参见上章) 依概率收敛作为一个算法好坏 的衡量标准，其局限性是显见的 由于全局优化问题本身的多变性，好的算法应该能够发现并利用 求解过程中得到的函数影响优化算法的重要特性。并且要想让一种 算法在不同种类的问题中都具有高出一等的表现，似乎是不大可能 的。为了处理不同类型的优化问题，拥有大量的优化算法可供选择是 很有必要的尽管没有一种算法可以在各种类型问题中胜出，但对某 一具体问题来说，还是有一些算法表现要好一些。很不幸的是，目前 并没有一种公认的策略来选择合适的算法上一章我们对问题做了 分类。但对问题本身的影响优化的各因素并没有加以权衡。为了对 某一优化策略在不同情况下的有效性有一个较为清晰的认识，对问 题进行有意义的刻画很有必要。这种刻画可以说是优化问题的复杂 性度量或困难程度的表述。在本章我们将进行一些这样的复杂性分 析当然，我们并不象一般复杂性理论那样给出问题计算次数与问 题的一个关系( 如多项式还是指数关系) 因为已证明对一般的无约束 全局优化问题这样定义的复杂度是指数型的。我们要做的是对影响采 样、影响搜索的因素加以刻画。 3 1 无约束全局优化问题的刻画 对无约束局部优化，算法的好坏通常由收敛速度来描述。对无约 束全局优化问题来说，算法的好坏的评价还没有一个公认的好的评 1 5 第三宣 复杂性分析 博士毕业论文 价标准。当然对算法的评价不能离开它所施于的问题的本身。对无约 束局部优化问题，可以做局部下降和使用二次模型对问题本身影响 优化问题的特性进行刻画。对无约束全局优化问题来说，对上一章所 述的各类问题影响优化的各种因素，目前尚无好的抽取共同的特征 的方法，也使对算法的比较缺乏基础。在本章，我们将试图对问题的 影响优化算法的特性进行描述，同时也将试图建立一个能够代表优 化问题本身复杂程度的的准则。我们希望我们的工作能够在算法开 发、算法比较、测试函数构造方面起到作用。在本章，我们仍不考虑 具体的算法。 从上一章所述，我们可以看到，理解无约束全局优化问题的复杂 性可以从目标函数的地形着手。这在 5 5 中也略有提及。我们可以看 到目标函数的地形形态的代表因素有极值点多少及其大小、位置，极 小( 大) 点的吸收域相对大小，各吸收域的形状以及各吸收域之间的连 接等等。优化问题无外乎对地形信息的利用以得到一个好的点。为了 便于处理，我们假定没有连续的极( 小) 值点，亦即对任一极( 小) 值点 可以找到它的一个小的邻域，在其内只有这一个极( 小) 值点。这样对 任何极( 小) 值点，总有它的一个邻域，在这个邻域内问题成为一个无 约束局部优化问题。这样的假定使得问题便于处理，并且对实际的问 题也已满足要求。 对很多实际应用( 如地震波反演) ，目标函数不能被一些初等的基 本函数的简单运算所表达，只能由计算程序或实验确定每个点的函 数值而且由于缺乏全局的信息，对目标函数性质知道的很少。当自 变量空间的维数较低( 如n 2 ) 时，还可以用不多的点对函数形态进行 较好的估计，然而当维数较高时，即便是对函数很粗糙的估计也需要 很多点。且在高维时，目标函数形态的刻画也很不直观，也更复杂， 有很多因素要考虑s t a d l e r 和s c h a b l 5 2 曾对组合优化中的邮递员问题 的地形进行了刻画，【4 】利用局部极小点及与各局部极小点相邻的两 个鞍点进行分析，通过对极小点及鞍点的一定的排列，对多原子之间 的能势面用一系列的折线来描述用这种方法，一些重要的函数特征 可用初阶、二阶、三阶等吸收域的概念来描述另外。 19 曾通过熵 的方法对高维哈密尔顿系统的复杂性进行了研究对高维哈密尔顿 系统，可以通过一些方法找到