（计算数学专业论文）最优化问题的几种网格型算法.pdf

s e v e r a lg r i d b a s e da l g o r i t h m sf o ro p t i m i z a t i o np r o b l e m s l i uq u n f e n g b s ( h u a z h o n gu n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y ) 1 9 9 9 m s ( h u a z h o n gu n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y ) 2 0 0 2 ad i s s e r t a t i o ns u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f d o c t o ro fs c i e n c e l n c o m p u t a t i o n a lm a t h e m a t i c s i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rz e n g j i n p i n g j u n e ，2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 成果。除了义中特另1 d n 以标注引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均乙在 文中以明确方式标明。本人完全意识到奉声明的法律后果南本人承担。 名：历懈峰慨加钿研a 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，i 刊意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被贪阅和借阕。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行榆索， 可以采川影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属十 l 、保密口，在年解密后试用本授权书。 2 、不保密吵 ( 请在以上相应方框内打“”) 作者签 导师签 臼期：必年月l oe 日期：加f 年月i 口日 博士学位论文 摘要 本文着重研究了求解最优化问题的两种网格型算法一类是求解局部最优化 问题的直接搜索算法，另一类是求解有界约束的全局最优化问题的d i r e c t ( d i v i d i n g r e c t a n g l e ) 算法 在第2 章，我们在c o o p e - p r i c e 直接搜索算法框架下，提出了一种混合非单调下 降条件，并针对该条件提出一种网格步长的分区域更新策略在此基础上提出m i x - d s c g 算法，该算法在数值表现上比原始的d s c g 算法更可靠( r e l i a b l e ) ，在收敛理 论上需要的条件更简洁具体来说，m 谗d s c g 算法使用混合非单调下降条件，不 允许网格步长增加，从而不需要假设网格步长的极限为0 就能保证收敛性 在第3 章，我们以最小正基为基础，引进单纯形梯度和下降型无导数共轭梯度 方向，在c o o p e - p r i c e 直接搜索框架内构建了m d s c g 算法在通常的条件下可以证 明m d s c g 算法的收敛性数值结果表明，m d s c g 算法对使用最大正基的d s c g 算 法以及著名的n e l d e r m e a d 单纯形法等算法具有优势 在第4 章，我们将多重网格思想应用到求解全局最优化问题的d i r e c t 算法 中，提出了一种基于多重网格搜索的全局优化算法，称为m g g o 算法迄今为 止，我们尚未见到有关的研究工作，我们所做的工作是将多重网格思想应用到全 局最优化问题中的首次尝试在仅假设目标函数l i p s c h i t z 连续的条件下，我们证明 了m g g o 算法的全局收敛性与原始d i r e c t 算法和其他一些相关算法的数值比 较表明，m g g o 算法是一种很有效的确定性全局最优化算法同时，数值实验结果 也表明，m g g o 算法对参数比较敏感，这一点非常类似于求解线性方程组的几何 多重网格法 在第5 章，本文还研究了带残差校正的多重网格法的收敛性我们把多重网格 方法看成是一种扰动的两重网格方法，得到了一个描述多重网格方法的收敛因子与 两重网格的收敛因子的不等式该不等式表明，对于带残差校正的多重网格法、 循环，存在收敛因子的一个与网格层数无关的一致上界a ( 1 一盯) ：其中盯 0 5 是 两重网格法的收敛因子的上界我们证明无论残差校正发生在哪些层上，o ( 1 一 盯) 始终是带残差校正的多重网格、循环的收敛因子的一致上界同时我们还证明， 当0 5 盯 1 时，只要适当选取循环系数，带残差校正的多重网格法的收敛因子总 存在一个与层数无关的一致上界，且该上界总小于w 循环的上界a l ( 1 一口) 这一 结果表明，即使两重网格法收敛得不是很好，只要适当选取循环次数，多重网格的 总体收敛因子仍存在较小的与层数无关的一致上界所做的数值实验验证了适当 的残差校正对多重网格法的收敛加速，并验证了两重网格法收敛得更快时多重网 格法也收敛得更快 此博士论文得到了国家自然科学基金( 1 0 9 7 1 0 5 8 ，1 1 0 7 1 0 8 7 ) 的咨助 i i 最优化问题的几种嘲格型算法 此博士论文用l a t e x 2 。软件打印 关键词：数值最优化；直接搜索算法；d i r e c t 算法；多重网格法；共轭梯度方向； 最小正基；单纯形梯度 博士学 奇论文 a b s t r a c t t h i st h e s i ss t u d i e st w oc l a s s e s o fg r i d - b a s e d a l g o r i t h m s ，t h ec o o p e - p r i c e f r a m e w o r kb a s e dd i r e c ts e a r c ha l g o r i t h m sf o rf i n d i n gal o c a ls o l u t i o no fa nu n c o n o 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 ，a n dt h ed i r e c t ( d i v i d i n gr e c t a n g l e ) a l g o r i t h m f o rf i n d i n gag l o b a ls o l u t i o no fab o u 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 i nc h a p t e r2 ，w ep r o p o s ean e ws t r a t e g yf o ru p d a t i n gt h eg r i ds i z eb a s e do n t h em i x e dn o n - m o n o t o n ed e c r e a s ec o n d i t i o ni nt h ec o o p e - p r i c ef r a m e w o r k t h e n w ep r o p o s ead i r e c ts e a r c ha l g o r i t h mc a l l e dt h em i x - d s c ga l g o r i t h m ，w h i c hc a l l b er e g a r d e da sa ni m p r o v e m e n to ft h eo r i g i n a ld s c ga l g o r i t h m t h em i x - d s c g a l g o r i t h mp o s s e s s e st h ef o l l o w i n ga d v a n t a g e sc o m p a r e dw i t ht h ed s c ga l g o r i t h m f i r s t ，w i t h o u tt h er e q u i r e m e n tt h a tt h el i m i t a t i o no ft h eg r i ds i z ei sz e r o ，t h e g l o b a lc o n v e r g e n c eo ft h ea l g o r i t h mi sa c h i e v e d s e c o n d ，t h em i x - d s c ga l g o r i t h m i sm o r er e l i a b l et h a nt h eo r i g i n a ld s c ga l g o r i t h m i nc h a p t e r3 ，w ec h o o s et h em i n i m a lp o s i t i v eb a s i st ob u i l dt h ec o o p e - p r i c e d i r e c ts e a r c hf r a m e w o r k b yt h eu s eo ft h ef u n c t i o nv a l u ei n f o r m a t i o ng a t h e r e d d u r i n gt h ed i r e c ts e a r c hp r o c e s s ，w eg e te s t i m a t i o nt ot h es i m p l e xg r a d i e n to ft h e o b j e c t i v ef u n c t i o n w et h e nf o r mad e r i v a t i v e - f l e ec o n j u g a t eg r a d i e n td i r e c t i o n a n dp r o p o s ead i r e c ts e a r c ha l g o r i t h mc a l l e dt h em d s c ga l g o r i t h m t h eg l o b a l c o n v e r g e n c eo ft h em d s c ga l g o r i t h mi sp r o v e du n d e rm i l dc o n d i t i o n s o u re x t e n - s i v en u m e r i c a lr e s u l t ss h o wt h a tt h em d s c ga l g o r i t h mp e r f o r m sb e t t e rt h a ns o m e e x i s t i n gd i r e c ts e a r c ha l g o r i t h m s ，s u c ha st h ed s c ga l g o r i t h ma n dt h ep o p u l a r n e l d e r - m e a ds i m p l e xm e t h o d i nc h a p t e r4 w ei n t r o d u c et h ei d e ao ft h em u l t i g r i dm e t h o dt ot h ed i r e c t a l g o r i t h ma n dt h e np r o p o s eam u l t i g r i d - b a s e dg l o b a lo p t i m i z a t i o n ( m g g o ) a l g o - r i t h m s of a r ，t h e r es e e m sn or e l a t e dr e s e a r c h t h ep r o p o s e dm g g oa l g o r i t h m m a yb et h ef i r s ta l g o r i t h mt h a ta d o p t st h ei d e ao ft h em u l t i g r i dm e t h o dt os o l v et h e g l o b a lo p t i m i z a t i o np r o b l e m s t h eg l o b a lc o n v e r g e n c eo ft h ep r o p o s e da l g o r i t h m i sp r o v e du n d e rt h ec o n d i t i o nt h a tt h eo b j e c t i v ef u n c t i o ni sl i p s c h i t zc o n t i n u o u s o u rn u m e r i c a lr e s u l t ss h o wt h a tt h em g g o a l g o r i t h mi sc o m p e t i t i v ed e t e r m i n i s t i c g l o b a lo p t i m i z a t i o ns o l v e r n u m e r i c a lr e s u l t sa l s os h o wt h a tt h em g g oa l g o r i t h m i ss e n s i b l et oa l g o r i t h mp a r a m e t e r s ，w h i c hi ss i m i l a rt ot h eg e o m e t r i cm u l t i g r i d ( g m g ) m e t h o d f o rl i n e a rs y s t e m s i nc h a p t e r5 ，w ea n a l y z et h ec o n v e r g e n c eo ft h em u l t i g r i dm e t h o d sw i t hr e s i d - u a ls c a l i n gt e c h n i q u e ，w h e r et h es c a l i n gf a c t o ri sap o s i t i v ec o n s t a n t t h em u l t i g r i d i v 最优化i l 口j 题的几种m 格型算法 m e t h o di st r e a t e da sap e r t u r b e dt w o - g r i dm e t h o d ，a n dt h e nw eo b t a i na ni n e q u a l - i t yw h i c hm e a s u r e st h er e l a t i o n s h i pb e t w e e nt h ec o n v e r g e n c ef a c t o ro ft h em u l t i g r i d m e t h o da n dt h ec o n v e r g e n c ef a c t o ro ft h et w o - g r i dm e t h o d t h ei n e q u a l i t ys h o w s 盯( 1 + 仃) i sa nu p p e rb o u n df o rt h ec o n v e r g e n c ef a c t o ro ft h em u l t i g r i dw - c y c l e w i t hr e s i d u a ls c a l i n gt e c h n i q u e s w h e r e0 仃 0 5i st h eu p p e rb o u n df o rt h e c o n v e r g e n c ef a c t o ro ft h et w o - g r i dm e t h o d t h i su p p e rb o u n di si n d e p e n d e n to f t h el e v e l w ep r o v et h a to ( 1 十盯) i sa l w a y sa i lu p p e rb o u n dw h a t e v e rt h er e s i d - u a li ss c a l e da ta l ll e v e l so ra ts o m el e v e l s f u r t h e r m o r e i ti sp r o v e dt h a tw h e n 0 5 0 ，则网格定义为如下的点集 本文的网格定义1 1 3 与文献 8 e p 的n 格定义的唯一区别是本文的定义中用p 的 地方文献 8 】中用n 本文定义的好处是避免了用线性基张成正基这一点类似于文 献 3 】的做法，但是本文的网格定义也有别于文献 3 】如果对每个迭代点构建一 个本文意义下的网格，则文献 3 】的网格定义可以看成是本文定义的网格的并集 按照定义1 1 3 ，图1 1 就是一个以z o 为中心点的二维网格，这个网格可以用二 维最大正基u = ( 1 ，o ) ，( 0 ，1 ) ，( 一1 ，o ) ，( o ，一1 ) ) 来生成，也可以用最小正基u = ( 1 ，0 ) ，( 0 ，1 ) ，( - 1 ，一1 ) 来生成 网格是直接搜索中的重要概念，因为它描述了对搜索空间的一种规则抽样实 际上，直接搜索算法一般要求在网格点上进行搜索，而不是在整个搜索空间中搜索 如果需要搜索到网格之外的点，则需要加上一定的条件( 如定义1 1 6 定义的充分下 降条件) 才能保证收敛性p 一1 网格概念在直接搜索中的重要性还体现在算法收敛性的证明中网格步长的 极限行为在直接搜索算法收敛性的证明中起关键作用当搜索失败( 在当前迭代点 的周围没有找到函数值更小的点) 时，网格步长必须减小从而，在一定的条件下， 网格会变得越来越细，最终趋于0 这一点对于直接搜索算法的收敛性是很重要的 下面的定义描述了网格的单元框( f r a m e ) ，这一概念首先在文献9 1 中提出网 格单元框以网格的中心点为中心，但只包含最邻近中心点的网格点 定义1 1 4 给定一个中心点z 胀，一个舯中的正基u 和网格步长h 0 ，则网 格单元框定义为如下的点集 垂( z ，1 7 + ，h ) = z + h v ：口1 ，+ ) ( 1 1 3 ) 网格单元框提供了当前迭代点( 网格中心点，也即网格单元框的中心点) 附近 的信息，特别是，利用单元框点的函数值可以构建当前迭代点处的梯度信息有了 一4 一 、， z 仇 忱 仇 p 试 + 0 z r l = 9 n 2 0 ，如果搜索到了点z 满足条件 ，( 2 ) 一e ，( z ) ， 则称在迭代点z 处实现了充分下降 在定义1 1 5 和定义1 1 6 中，通常是h 的增函数，这样做可以把充分下降量与网 格步长挂起钩来 对比定义1 1 5 和定义1 1 6 可以发现，如果当前迭代点是一个拟最小点，则在该 单元框中不可能搜索到能实现充分下降( 下降量超过e ) 的点反之，如果在当前的 网格单元框中实现了充分下降，则该网格单元框不可能是拟最小的 1 1 3几种主要的直接搜索算法框架 目前，直接搜索仍然处在算法框架时代对各种算法框架进行精炼以得到高效 的算法仍是目前直接搜索领域的研究重点剐本小节简要介绍c o o p e - p r i c e 直接搜 索算法框架及其主要特点，其他三种直接搜索算法框架( g p s ，g s s ，m a d s ) 的介绍 可参见本文附录b 和相关文献，如文献 2 ，3 ，1 2 ，1 3 ，3 7 】 c o o p e - p r i c e ：直接搜索算法框架由文献8 - 1 0 ，3 5 1 建立，又叫做以网格单元框为 基础( 抒a m 争b a s e d ) 的直接搜索算法框架该框架包含内外两个循环：内循环用于寻 找拟最小单元框，而外循环用来更新参数 算法1 1 1 ( c o o p e p r i c e 算法框架j 初始化：给定初始点z o 瞅，令k = 1 ，m = 1 外循环：选择如 0 ，0 一5 一 最优化问题的几种嗍格帮算法 一内循环? 选择一个正基修j , a y t h 七和e 七使满足? h 七h m ，e 七岛 一执行任意的有限搜索过程，该搜索过程必须包含以当前迭代点为中心的网 格单元框取z t 帆p 为已知的函数值最小的点 一内循环检验：如果z t 。m p 满足充分下降条件，则令z 七+ 1 = x t e m p ，k = k + 1 ， 回到内循环 外循环检验? 令乙n = z 凫俾录拟最小点j ，m = m + 1 执行任意的有限搜索过 程，取z 知+ 1 为已知的函数值最小的点，k = 七+ 1 如果停止条件不满足回到外 循环 在适当的条件下，可以证明f l 习c o o p e - p r i c e 的直接搜索框架生成的由拟最小点 组成的迭代子列的任意极限点必是稳定点即有 l i l 。l li n fl i v ，( z 七) i l = 0 t w c o o p e - p r i c e 直接搜索框架是一个非常一般的算法框架，主要有以下特点： ( 1 ) 利用正基来定义网格，在一定的条件下( 如满足结构性等价条件) 正基可以比较 自由地选取，从而使网格能比较自由地变化( 即可以对搜索空间比较自由地进 行抽样) ( 2 ) 网格步长的更新非常灵活，比如，成功搜索后网格步长可以增加 ( 3 ) 包含两个任意的有限搜索过程这意味着只要满足充分下降条件就可以在网 格之外进行搜索 以上特点有些被后来的直接搜索算法框架( 如g s s ，m a d s ) 所吸收，如在搜索 方向集中引进由正基定义的网格并使网格的选取尽可能地灵活等不过，c o o p e - p r i c e 直接搜索框架并没有完全被后来的框架所吸收，它仍然保持了自身的独特特 点，如充分下降条件下的任意有限搜索过程等因此，c o o p e - p r i c e - 卣接搜索框架仍 作为一个一般的框架而存在 1 2求解全局最优化问题的d i r e c t 算法 全局最优化问题以寻找目标函数的全局最小值为目标，一般来说这是一个困 难的任务目前，求解全局最优化问题的数值算法主要有两大类4 0 i ：一类是启发 式( h e u r i s t i c ) 算法，如演化类算法( 模拟退火( s i m u l a t e da n n e a l i n g ) 算法 n s l ，基因( g e n e t i c ) 算法m 1 等) 和随机搜索算法，这一类算法通常以概率1 保证收敛到全局 最小值另一类是确定性( d e t e r m i n i s t i c ) 算法，这类算法通常保证确定性地收敛到 一6 一 博上学位论文 全局最小值如分枝定界( b r a n c ha n db o u n d ) 算法m 1 以及以直接搜索思想为基础 的d i r e c t 算法卜2 删等分枝定界算法一般用于处理离散优化问题，而d i r e c t 算 法处理连续优化问题本文第四章将研究基于多重网格思想的d i r e c t 算法本节 主要介绍d i r e c t 算法的发展概况，其他确定性全局优化算法可参阅文献f 4 7 1 ，启 发式算法的发展请参阅文献4 8 】 d i r e c t 算法的名称来自于矩形分害l j ( d i v i d i n gr e c t a n g l e s ) 这一算法描述 该算法最初由文献4 2 1 提出，用于求解如下有界约束的全局优化问题： f ( x ) = ，+ m 锄i n m ) ， 其中q = z r n 恢耽1 1 , i ) ，一o 。 如i l l 0 ，执行以下操作j 一前光滑：对a u f = b t 进行若干次光滑，得到近似值忱和残差n = b t a f v l ； 一限制到粗网格：把a 及残差n 限制到f 一1 层j 一粗网格求解? 以o ) b 初值，利用本算法本身，y 次递归求解a f _ 1 e l - l = n 一1 i 一延拓回细网格：把e z 一1 延拓回2 层； 一校正：耽：= v l + e l 一后光滑? 以叻为初值对a f u l = b t 进行若干次光滑 在上面的多重网格法的框架中，参数1 表示循环次数，即用上述算法本身7 次 来求解粗网格子问题在实际使用中，y 等于1 或2 是最常用的方法，它们分别对应 着多重网格v 循环和、循环图1 4 是这两种循环的实现示意图其中，虚线表示 网格层数( 从上n - v 层数递减，最下面一条虚线表示第0 层网格，即最粗的网格) ，向 下的箭头表示限制，向上的箭头表示延拓 以上介绍的多重网格法依赖于偏微分方程的背景，又叫做几何多重网格法( g e o m e t r i cm u l t i g r i d ，g m g ) 后来，一种不需要偏微分方程背景的代数多重网格 一1 0 博上学位论文 法( a l g e b r a i cm u l t i g r i d ，a m g ) 也被提了出来有关多重网格法的发展可参阅文 献【4 9 - 5 5 二r 二二7 。弋1 。显。 iiii|iiiiiiiiiiiii|iiiiiiiiiiiiiiill7 图1 4 多重网格法的两种循环形式：v - 循环和、- 循环 1 4比较数值算法优劣的常用方式 本文后面的几章会提出一些数值算法( 主要是数值最优化算法) ，这些算法将 与现有的一些相关算法进行比较因此j 需要选择适当的方法来区分不同算法的 优劣比较数值算法优劣的方法有很多，选择不同的比较方法可能得到不同甚至 相反的结论本节首先介绍怎样选择测试函数，然后，介绍几种常用的方法来从测 试得到的大量数据中提取出有用信息，利用这些信息可以对算法的优劣做出某种 判断( 基于已做的数值试验) 根据算法的类型( 是否有约束，是否使用梯度等) 选择适当的测试函数是比较算 法优劣的第一步为了公平起见，测试函数一般从公共测试函数库中去选择在数值 最优化研究中，常用的公共测试函数库主要有两个，一个是m o r 6 - g a r b o w - h i u s t r o m ( m g h ) 测试函数库唧1 ，另一个是它的扩充版c u t e r 钡i j 试函数库p “m g h 测试函 数库发表于1 9 8 1 年，有3 5 个测试函数，全部采用s o s ( s u m o f - s q u a r e ) 格式生成这 个函数库至今仍使用的非常广泛，特别是在无约束最优化算法和直接搜索( 无导 数) 算法的比较中c u t e r 函数库比m g h 函数库要大得多( 超过1 0 0 0 个测试函数) ， 既适合无约束最优化算法的比较，也适合有约束的最优化算法的比较为了方便 选择测试函数，c u t e r 使用了一种专门的分类系统，详情请参见文献f 5 7 由于本 文的算法主要是直接搜索型的算法，所以本文使用的测试函数大部分来自m g h 函 数库，但也有一些测试函数来自于c u t e r 函数库 用需要比较的算法去求解选取好的测试函数，将得到大量的测试数据重要 的数据主要包含迭代次数、c p u 时间、梯度的范数、函数值以及函数值计算次数 1 1 最优化问题的几种网格型算法 等怎样从这些数据提取出有效的信息是比较算法优劣的关键步骤下面介绍四 种常用的方法 1 4 1呈现原始数据 这种方法指的是把测试得到的重要数据直接用表格等形式呈现出来通常，这 些原始数据反映了程序终止时参数和所测试函数的状态比如，需要的迭代次数、 目标函数值的大小、梯度的大小、所用的c p u 时间、函数值的计算次数以及其他 的一些参数状态表1 1 就是一个简单例子 呈现原始数据的好处是给出了具体的原始数据，有利于其他研究人员进行验 证以及用于跟其他算法的比较但是，这种方法的缺陷也是很明显的一方面，当 测试函数很多时( 目前数值最优化领域的研究经常需要测试大量的函数) ，原始数 据太多，不便于直接呈现出来另一方面也是更重要的方面是，不同的算法往往对 一些函数测试效果好，而对另一些函数测试效果差，怎样比较综合的效果呢? 呈现 原始数据的方法无法回答这个问题当比较的算法较多时，这个问题会更加严重 1 4 2l 型曲线 这种方法为每个测试函数画一条曲线，横轴通常是函数值计算次数或者迭代 次数，纵轴是函数值或残差( 一般取对数) 由于这种曲线通常是l 型的：最初的少 量函数值计算或者迭代使得函数值或者残差下降很多，而后期的大量函数值计算 或者迭代只产生了很少的下降量，所以这种方法叫做l 型曲线方法图1 3 就是一个 典型的l 型曲线图 显然，l 型曲线方法只适用于测试函数很少的情形在需要测试大量函数的时 候，这种方法很少使用但是，l 型曲线方法在数值计算的其他领域仍然广泛使用 在数值最优化研究中，当没有更好的处理方法时，l 型曲线方法也是很好的选择p 咧 本文在第五章的多重网格法数值试验中使用了l 型曲线方法，例如，图5 1 和 图5 2 都是l 型曲线的例子 以上介绍的两种方法都没有很好地解决以下问题：当测试函数很多时，怎么比 较不同算法的综合效果? 显然，要解决这个问题需要利用一定的统计方法2 0 0 2 年， j o r g ejm o r 6 等人提出t p e r f o r m a n c ep r o f i l e s 方法删2 0 0 8 年，又提出了更适合于 比较直接搜索( 无导数) 算法的d a t ap r o f i l e s 方法归叫这两种方法比较有效地解决了 在大量测试中综合比较多个算法的问题下面分别介绍这两种方法 1 4 3p e r f o r m a n c ep r o f i l e s 这种方法可以在一幅图中直观地比较多个算法求解多个测试函数的综合效果 在文献 5 8 】中，用s 表示多个算法的集合，用尸表示多个测试函数的集合对s 中的 任意算法s 以及尸中的任意测试函数p ，用p ，。表示用算法s 求解函数p 的成本，该成本 一1 2 博上学位论文 可以是函数值计算次数或者c p u 时间，也可以是任意的其他度量标准定义 。一t p ，s ”一m i n t p ，：s ) 为p e r f o r m a n c er a t i o ，它描述算法8 求解函数p 时产生的成本距离最小成本有多远 算法s s 的p e r f o r m a n c ep r o f i l e 被定义为r ”的“经验分布函数” 1 p s ( q ) = 高p ：r p ，。茎a 扎 1 1l 其中，i i 表示集合的元素个数显然，给定q ，陆( q ) 越大，表示算法8 能求解( 成 本在q 内) 的函数越多，从而算法s 越好值得指出的是，风( 1 ) 表示算法s 能最有效求 解( 在s 的所有算法中，s 最快求出) 的测试函数的比例当q 充分大时，风( q ) 表示算 法s 能求解的测试函数的比例，这个值可能小于l ，它度量了算法s 的稳健性( r e l i a b i l i t y ) 求出所有风( q ) ，8 s ，并把它们放在同一副图中就得到t p e r f o r m a n c ep r o - f i l e s 曲线图图2 3 和图3 2 都是p e r f o r m