（应用数学专业论文）非线性全局优化问题的填充函数算法研究.pdf

分类号 u d c 密级 学校代码 1 0 4 9 7 武多凄理歹大潭 学位论文 题 目韭垡：些全鱼垡垡闻塑丝堕壅垂垫笠鎏堑窒 英文基曼墨星i 目匮塾q 坠! 鱼星i ! ! 星鱼e 坠塾堡垒q 坠! g q 照! 垒堡墨鱼! 题目 s q ! y i 坠g 丛q 坠! i 堕曼丛鱼! q 坠垒! ! 独! i 堡i 圣垒! i q 垒! 旦垫! 殳堡墨一一一 研究生姓名堕盘盔 指导教师 姓名j 叠整l 职称型塑堑学位堂堕- _ 一 申请学位级别 硕士 4 3 0 0 7 0 论文提交日期2 q ! q 生! q 且论文答辩日期2 q ! q 生! ! 且 学位授予单位盍垫墨墨垄鲎学位授予日期 答辩委员会主席固挝氐评阅入周挝氐 三垄生 2 0 1 0 年11 月 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：隘盔塞日期：碰：丛篓 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：琳 导师( 签名) ：磕姜责日期渺j a 2 9 中文摘要 填充函数算法是求解非线性全局优化问题的一种确定型算法，它成功地解 决了如何从当前局部极小解出发找到更好的局部极小解的问题本文对已有填 充函数算法作了进一步的推广和应用，具体研究了求解无约束和带有一般约束 全局优化问题的填充函数算法本文的主要内容如下： 第一章，主要介绍了当前国内外几种典型的求解非线性全局最优化问题的 算法，重点对填充函数算法的基本思想到相关的理论进行了全面深入的分析， 在此基础上，分析了已有填充函数的优缺点，为进一步的构建和研究新的填充 函数算法，提供了思路 第二章，构造了一个新的求解无约束全局优化问题的单参数填充函数，该 函数形式简单，便于计算在几种假设条件下，分析并证明了该填充函数的性 质，并建立了相应的填充函数算法最后，对算法进行了大量的数值实验，数 值实验的结果表明，该算法是有效的 第三章，将第二章中求解无约束全局优化问题的填充函数拓展到带有一般 约束条件的全局最优化问题中构造了一个新的单参数填充函数该函数避免 了原有函数的指数或分数形式的弱点，且参数容易选取在无强制性条件下， 讨论了该填充函数的性质，并建立了相应的填充函数算法用该算法对一些经 典的算例进行了数值实验，数值结果表明该算法对于解决有约束全局优化问题 是有效的 第四章，对本文所做的工作进行了总结，并对填充函数算法中有待研究的 问题进行了展望 关键词：填充函数算法，无约束优化问题，有约束优化问题，全局极小点，数 值结果 a b s t r a c t t h ef i l l e df u n c t i o na l g o r i t h mi so n eo ft h ed e t e r m i n i s t i cm e t h o d sf o rs o l v i n g n o n l i n e a rg l o b a lo p t i m i z a t i o np r o b l e m i ts u c c e s s f u l l ys o l v e dh o wt os t a r tf r o mt h e c u r r e n tl o c a lm i n i m a ls o l u t i o nt of i n db e t t e rl o c a lm i n i m a ls o l u t i o no ft h ep r o b l e m t h i sp a p e rs t u d i e dt h en e wf i l l e df u n c t i o na l g o r i t h mo fu n c o n s t r a i n e dg l o b a l o p t i m i z a t i o np r o b l e m s a n dc o n s t r a i n e d 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 e i r p r o p e r t i e sa r ed i s c u s s e do ne m p h a s i s t h em a i nw o r k i ss u m m a r i z e d 嬲f o l l o w s c h a p t e ro n em a i n l yi n t r o d u c e dt h ec u r r e n td o m e s t i ca n df o r e i 班s e v e r a lk i n do f c l a s s i cm e t h o d sf o rs o l v i n gn o n l i n e a rg l o b a lo p t i m i z a t i o np r o b l e m f o rt h ef i l l e d f u n c t i o na l g o r i t h m ，f r o mt h ei d e ao ft h ea l g o r i t h mt ot h er e l a t e dt h e o r yt h a tg i v e nt h e e x p l a n a t i o n b a s e do nt h i s ，h a sa n a l y z e dt h er e s p e c t i v ea d v a n t a g e s f o rt h ef u r t h e r p r o m o t i o na n dc o n s t r u c tan e wf i l l e df u n c t i o na l g o r i t h m ，p r o v i d e ss o m eg u i d e l i n e s a n dm e t h o d s c h a p t e rt w op r o p o s e dan e wf i l l e df i m c t i o nw i t l lo n ep a r a m e t e rf o rs o l v i n g c o n t i n u o u s l yu 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 s ，w h i c hw a ss i m p l ea n de a s y 1 0b ec a l c u l a t e d h a sa n a l y z e da n dp r o v e nt h i sf i l l e df u n c t i o n sp r o p e r t yu n d e rs e v e r a l k i n do fs u p p o s i t i o nc o n d i t i o n s ac o r r e s p o n d i n gf i l l e df u n c t i o na l g o r i t h mi s e s t a b l i s h e d a tl a s t ，n u m e r i c a lr e s u l t sa r eg i v e nt os h o wt h a tt h en e wf i l l e df u n c t i o n a l g o r i t h mi se f f e c t i v ef o rs o l v i n gg l o b a lo p t i m i z a t i o np r o b l e m s c h a p t e r t h r e e e x p a n d e d t h ef i l l e df u n c t i o ni n c h a p t e r t w of o r s o l v i n g u n c o n s t r a i n e dg l o b a l o p t i m i z a t i o np r o b l e m st o t h e g e n e r a l c o n s t r a i n e dg l o b a l o p t i m i z a t i o np r o b l e m s an e wf i l l e df u n c t i o nw i t ho n ep a r a m e t e ri sp r o p o s e dw i t h o u t t h ec o e r c i v ec o n d i t i o n ，i nw h i c hh a so n l yo n ea d j u s t a b l ep a r a m e t e r , c o n t a i n sn e i t h e r e x p o n e n t i a lt e r mn o rf r a c t i o n a lt e r m ，a n dt h ep a r a m e t e re a s yt ob es e l e c t b a s e do n d i s c u s s i o no nt h ep r o p e r t i e so ft h ef u n c t i o n ，ac o r r e s p o n d i n gf i l l e df u n c t i o na l g o r i t h m i se s t a b l i s h e d a tl a s t ，w ep e r f o r m e dn u m e r i c a le x p e r i m e n t su s i n gt h ea l g o r i t h mo n 8 0 m ec l a s s i ce x a m p l e s ，a n dt h ed e t a i l e dn u m e r i c a lr e s u l t ss h o wt h a tt h ea l g o r i t h mf o r s o l v i n gc 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 mi sa l s oe f f e c t i v e t h el a s tc h a p t e rd r a wc o n c l u s i o n so ft h i sp a p e ra n dt h ed e v e l o p m e n td i r e c t i o no f f i l l e df u n c t i o na l g o r i t h mi sp r o s p e c t e d i i k e yw o r d s ：f i l l e df u n c t i o na l g o r i t h m ，u n c o n s t r a i n e x to p t i m i z a t i o np r o b l e m s ， 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 ，g l o b a lm i n i m i z e r ，n u m e r i c a lr e s u l t s i i i 目录 中文摘要i a b s t r a c t i i 第一章绪论1 1 1 全局最优化问题概述1 1 2 全局优化算法的研究现状。5 1 2 1 分支定界法6 1 2 2 区间算法7 1 2 3 随机搜索法。8 1 2 4 打洞函数法9 1 2 5 其它全局最优化方法1 0 1 3 填充函数算法的研究现状l l 1 4 本文的研究目的和主要工作。1 9 第二章一个新的求解无约束优化问题的单参数填充函数算法2 1 2 1 引言。2 1 2 2 无约束优化问题填充函数的基础知识2 2 2 3 一个新的求解无约束优化问题的填充函数及其性质。2 3 2 4 无约束填充函数算法和数值实验2 5 2 4 1 填充函数算法2 5 2 4 2 数值实验2 5 2 5 小结3 0 第三章一个新的求解约束优化问题的单参数填充函数算法3 l 3 1 引言3l 3 2 有约束优化问题填充函数的基础知识3 2 3 3 一个新的求解有约束优化问题的填充函数及其性质3 3 3 4 有约束填充函数算法和数值实验3 5 3 4 1 填充函数算法3 5 3 4 2 数值实验3 6 3 5 小结4 0 第四章总结与展望4 1 4 1 总结4 l 4 2 展望4 1 致 射4 2 参考文献7 4 3 在读期间的主要研究成果4 8 i v 武汉理工大学硕士学位论文 第一章绪论 在本章的开头部分，对全局最优化问题的理论及研究方向进行了简要的介 绍在此基础上对非线性全局优化问题的具体算法做了介绍，其中重点介绍了 填充函数算法的国内外研究现状和意义最后，在他人的研究基础之上确定出 本文的研究目的和主要工作 1 1 全局最优化问题概述 关于全局最优化的问题研究由来已久，最早可以追溯到上世纪7 0 年代初期， 对它的研究涉及到社会生活的方方面面，国内外的诸多学者在不同的学科和领 域上都分别对这一问题展开相关的分析和研究作为非线性科学研究中的一个 非常活跃的数学分支，全局优化的理论和算法从一出现便备受关注全局最优 化问题的形式多种多样，其应用涉及自然科学和社会科学的每个领域而大多 数问题需要求相应优化问题的全局最优解，但是实际的优化问题常常存在着多 个局部最优解，然而传统的非线性规划技术通常只可以求解出局部最优解，因 此求解全局最优化是一个非常困难的领域，但是通过国内外学者的不懈努力， 经过几十年的深入研究，对于全局最优化的问题，涌现出许多新算法与新理论， 极大地丰富了这一问题的研究，也为研究工作找到了突破口 最优化问题的一般表达形式为： r a 硝i n 厂( x ) ( 1 1 ) 其中z x 为决策变量，xcr ”为约束集或称为可行域，f ( x ) 为目标函数 其中，若约束集z = r ”，那么上述最优化问题就是无约束最优化问题： m 础i n 。f ( x ) ( 1 2 ) 约束最优化问题通常写为： m i n f ( x ) 砒( x ) - o ，涎m( 1 3 ) 【( x ) 0 ，i - 武汉理工大学硕士学位论文 上式中，m 与分别为等式约束的指标集和不等式约束的指标集， 盔( x ) ，汪1 ，2 ，以为约束函数 下面对最优化问题的分类进行简要的阐述 ( 1 ) 根据可行域来划分如果x = r ”，即x 是自由变量，那么称问题( 1 1 ) 是无约束优化问题；否则xcr ”，称问题( 1 1 ) 是约束优化问题 ( 2 ) 根据可行域的性质来划分如果可行域内的点是有限的，那么称问题 ( 1 3 ) 是离散最优化问题；如果可行域内的点能够连续变化，并且可行域内含有 无穷多个不可数的点，那么称问题( 1 - 3 ) 是连续最优化问题关于离散优化问 题，如果变量都是整数，那么称问题( 1 3 ) 是整数规划问题；如果部分变量是整 数，但是另一部分变量连续变化，那么称问题( 1 3 ) 是混合整数规划问题 ( 3 ) 根据函数的性质来划分如果目标函数与约束函数都是线性的，那么称 问题( 1 3 ) 是线性规划；如果目标函数与约束函数中至少有一个不是线性的( 即 是非线性的) ，那么称问题( 1 3 ) 是非线性规划再进一步划分，如果目标函数 是二次的，约束条件是线性的，那么称问题( 1 3 ) 是二次规划；如果目标函数是 凸的，且可行域是非空凸集，那么称问题( 1 3 ) 是凸规划 ( 4 ) 根据函数的向量性质来划分如果目标函数是向量函数，那么称问题 ( 1 3 ) 是多目标规划问题；如果目标函数是数量函数，那么称问题( 1 3 ) 是单目 标规划问题 ( 5 ) 根据函数的可微性质来划分如果目标函数和约束函数都是连续可微 的，那么称问题( 1 3 ) 是光滑优化问题；相应地，如果目标函数和约束函数中至 少有一个不是连续可微的，那么称问题( 1 3 ) 是非光滑优化问题 ( 6 ) 根据规划问题有关信息的确定性来划分如果目标函数和约束函数具 有随机性，即问题的表述形式随时间的变化而变化，具有不确定性，像这样的 优化问题称为随机规划问题；相反地，如果目标函数和可行域都是确定的，像 这样的规划问题称为确定性规划问题 另外根据决策变量及目标函数的要求不同，最优化还分为网络规划、整数 规划、多目标规划、几何规划、非光滑规划等分支本文主要研究求解无约束全 局最优化问题( 1 2 ) 及带有一般约束的全局最优化问题( 1 3 ) 的填充函数算法 本文中，为了研究方便，称问题( 1 2 ) 与问题( 1 3 ) 为原问题如果不另外特 别地说明，i i i | 始终表示欧几里得范数；v f ( x ) 表示f c x ) 在点工处的梯度；v 2 f ( x ) 表示厂( x ) 在点x 处的h e s s e 矩阵 定义1 1 1 假设x x ，若对于任意的x x ，都有 2 武汉理工大学硕士学位论文 ( 工) f ( x + ) 成立，那么称x 是问题( 1 1 ) 的全局极小点若对于所有工x ，x x ，都有 厂( x ) f ( x ) 成立，那么称x + 是问题( i 1 ) 的严格全局极小点 关于算法的搜索方向有下面定义： 定义1 1 2 n 3 设x o x ，若有方向d r ”且d 0 ，使得d7 町( x o ) 0 ，使得对于所有五，x 2 s ，有 i f ( x 2 ) - f ( x 。) i 忙一五l 其中称为李普希兹常数，则称厂为李普希兹函数 定义1 1 4 瞻3 如果s 包含所有收敛点列 而lc s 的极限点，则称scr ”为闭 集；如果s 是闭的有界集，则称scr ”为紧集 从函数在紧集上的连续性可以得到著名的魏尔斯特拉斯定理，定理如下t 定理1 1 1 口3 若s 是彤中一个非空紧集，且f ( x ) 是s 上的连续函数，那么 厂( 工) 在s 上至少有一个全局极小( 极大) 点 定义1 1 5 口3 定义在r ”中的函数f ( x ) 满足强制性条件，如果当叫l 0 0 时， 有f ( x ) 一十 在讨论无约束最优化问题时，如果厂是强制的，并且s = r ”，那么可以借助 定理1 1 1 来讨论全局极小点的存在性问题 定理1 1 2 口3 如果f ( x ) 是强制的，并且连续，那么f ( x ) 在尺”中至少存在一 个全局极小点 对于局部和全局极小点的问题，常有下面一些相关的定义、定理和结论 定义1 1 6 口1 向量d r ”称为点石s 处的可行方向，如果存在名 0 ，使 武汉理工大学硕士学位论文 得对于每个0 五 力，有x + + 2 , d s ( s 是问题的可行域) 假设函数厂在点x 的一个邻域内是可微的，不妨使得d r “满足条件 d r 町( x ) o ，其中表达式d r v f ( z + ) 是在x 处沿方向d 的方向导数对于固定x + 和d ，函数f ( x + 2 d ) 描述了厂沿射线 x = x + 2 d ，2 0 ) 的情况因为 f ( x 。+ 名d ) = f ( x + ) + 五d7 v f ( x + 0 2 d ) ， 这罩0 0 1 是某个确定的数所以d r v f ( x + ) 0 ，使得对 于每个0 a a ，有f ( x + + 五d ) f ( x + ) 换句话说，可以使厂沿方向d 局部地下 降从而可以得到下面的定理： 定理1 1 3 n 3 假设函数f ( x ) 在一个包含scr ”的开集内连续可微若 x + s 是一个局部极小点( 相对于s ) ，则对于每个可行方向d ，都有 d 7 v f ( x 。) 0 定义1 - 1 7 “。如果对于每一个可行方向d ，其中x s ，都有d7 v f ( z ) 0 ， 那么点x 称为平稳点 一般的全局优化问题的平稳点并不一定就是其极小点，然而对于凸规划的优 化问题来说，可以有下面的定理： 定理1 1 4 h 1 若厂是一个在包含s 的开集内连续可微的凸函数，并且s 是一 个凸集，则x s 是一个全局极小点，当且仅当x 。是一个平稳点 定理1 1 5 h 1 对于凸集s r 上的函数厂( x ) 的任意局部极小点是全局极小 点当且仅当该函数为凸函数 定义l - 1 8 晦1 研c 7 r ”称为函数f ( x ) 在一极小值点处的盆谷( b a s i n ) ，若它 是一个连通的区域并满足下列三条性质： ( 1 ) i 研； ( 2 ) 对任意x 研，f ( x ) 从x 出发沿下降路径收敛到x ，f ( x ) = 厂( ) ； ( 3 ) 对任意x 萑研，f ( x ) 从x 出发沿下降路径不收敛到x 定义1 1 9 晴1 如果i 是f ( x ) 的局部极小点，那么一f ( x ) 在局部极大点i 处 的山头称为f ( x ) 在局部极小点i 的盆谷 定义1 1 1 0 蹄1 对于函数f ( x ) 的不同的局部极小点矸与五，如果 厂( 蔓) 厂( i ) ，则称在i 处的盆谷研比蔓的盆谷砑高，或称鼋比研低如果 厂( i ) = 厂( 葛) ，则称在蔓的盆谷鼋和i 处的盆谷研具有同样高度 随着科学技术的不断进步，特别是计算机的应用，使得最优化理论不断地 进步与完善，而且求解目标函数极小解的方法日益成熟如牛顿法、拟牛顿法、 信赖域法、共轭梯度法、最速下降法等方法是最常用的方法由于人们在实际 4 武汉理工大学硕士学位论文 问题中经常使用这些常用的算法，所以这些算法在不断地被检验并逐渐地完善 人们重视和研究局部优化的原因主要有两个方面：一是局部信息的获取并不是 特别困难；二是在点x 处约束函数与目标函数的局部最优性条件可以被定量表 示与局部信息相比较，要想获取全局信息并不是件容易的事因此，至今为 止，我们面临的一个急需解决的问题是尽快建立全局最优性的判定条件 在全局优化问题中，由于没有全局最优性条件来判断计算过程中什么时候 停止，也就是没有终止判别准则，这样计算过程中效率就会大大降低，从而严 重地影响了全局优化算法的进一步研究虽然有全局最优性条件的影响，但是 这并没有阻止优化算法本身的发展经过国内外众多学者几十年的不懈努力， 至今，对于全局优化问题中形式特殊的规划问题，例如网络规划、一般凹规划、 非凸二次规划、d c 规划以及l i p s c h i t z 规划等，都已经有了分支定界法、区间 算法、随机搜索法、打洞函数法等许多有效的算法这使得全局优化问题不断的 向前发展 1 2 全局优化算法的研究现状 本节简述几种典型的求解全局优化问题的算法，并分析其优缺点 因为自然和社会科学中的大多数实际问题大多数可以抽象成求解全局最优 化问题，众多学者经过几十年的深入研究，对于全局最优化的问题，不断地有 新算法与新理论出现，极大地丰富了这一问题的研究由于在实际的优化问题 中大不多数情况下都不止一个局部极小点这就使得面对这类型的全局优化问 题时，我们不能用简单的、笼统的、常用的局部极小解的思想方法去求解全局 优化问题然而有两个难题使得求解含有多个极小值点的函数难以解决：第一 个困难是求解过程中如何从一个局部极小值点跳到另一个更小的极小值点；第 二个困难是如何判断当前的极小值点是否为全局最优解在这两个难题中，第 一个难题已经成功的得以解决，并且目前已经有了许多方法，如区间搜素法等； 而第二个关于全局最优性条件的难题仍然没有解决，还需要更进一步研究 因为全局最优化问题通常含有多个极小值点，这一特点使得我们不能用以 前求解局部优化问题的算法来解决全局优化问题全局优化问题按照信息的确 定性与否来分类，可以分为随机型算法和确定性算法两大类 所谓的随机型算法，是指其迭代过程主要是利用概率机制而不是确定性的 点列遗传算法，模拟退火算法，随机投点算法，m o n t o c a r l o 方法等是常用的 5 武汉理工大学硕士学位论文 随机型算法这些方法与禁忌搜索算法、人工神经网络等统称为现代优化计算 方法而所谓的现代优化算法( 也叫做启发式算法) 常常是通过模拟生物进化， 人工智能，神经系统，数学与物理科学，统计力学等，并且以直观为基础构造 的算法由于随机型算法有其独特随机性的优点，使得它对目标函数解析性态 差，或者没有解析式的问题也是可行的，由此看来，随机型算法具有简明性以 及适用性等优点因此，随机型算法受到了人们的关注并得以广泛应用 对于问题的解析性质，生成无限或有限的点序列，且该序列满足一定的确 定性，如果它收敛于全局最优解，那么这一方法被称为确定性算法常用的确 定性算法有分枝定界方法、区间算法、打洞函数法、积分一水平集方法 6 、填 充函数法等其中，单调性、凸性、稠密性、水平集、李普希兹常数、等度连 续性、高阶导数一致性等都是全局性的解析性质 按照如何利用目标函数的局部信息来研究，间接方法与直接方法是全局最 优化算法的两种分类间接方法主要是想办法利用已经知道的局部信息，例如 可以通过构造水平集或目标函数的全局模型来研究问题通常情况下，间接方 法的优点是其通常具有良好的理论性质，不足之处是，算法的实现是相当地困 难甚至是没有办法实现的因此，应用间接方法时只可以用近似的方法去逼近 理论上的最优而所谓的直接方法，通常是利用目标函数的局部信息如单调性、 导数以及最值等来研究问题的，这种方法虽然很简单，但是通常情况下是不知 道目标函数的局部信息的，因此在研究全局优化问题时直接方法不常用 本节将逐一介绍求解全局优化问题的分支定界法、区间算法、随机搜索法、 打洞函数法 1 2 1 分支定界法 用分支定界方法求解下述全局优化问题： m i n f c x ) j d 。 其中f ( x ) ：r 专r ”，dcr ”为紧集，f ( x ) 在d 上连续 在文献 7 中t u y 等人将单纯形的划分进行讨论了，然而用得最多的方法是 二等分，见文献 8 ， 9 ， 1 0 在分支定界算法中，首先是分支，可行域在分 支定界算法中没有了以前严格的约束，且在分支定界算法中，将原来的可行域 逐步分割，变成越来越多的小可行域；然后是定界，分支后，在这些已经被分 成很小的区域上，求出目标函数的上、下界接下来就是剪支，在算法的经行 6 武汉理工大学硕士学位论文 的某个阶段内，如果发现在其区域内最小上界小于当前下界，那么在这个小区 域内，就明显没有最优解，于是将这个小区域删除经过这三个过程，发现分 支变得越来越细，并且在这个过程中最大的下界在逐渐变大，最小的上界在逐 渐变下，当最小上界与最大下界的差越来越接近于零，也即是被分得很小的区 域逐渐趋于一个点的时候，我们就认为目标函数的全局极小解已经找到了因 此，分支定界法很受欢迎，这种方法在d c 规划，凹规划以及l i p s c h i t i a n 规划 中已经有着广泛的应用 从分支定界法的思想中可以发现，在每次迭代过程中都能够删除区域中一 些小区域，其中这些小的区域中一定不包含全局最优解，因此迭代步骤就可以 大大减少，这是分支定界法的一大优点然而，分支定界法也有自身的不足之 处，得到的近似解的精度要由目前进行步骤的上下界的差来衡是其缺点是正 因为这个缺点，使得可能存在这样一种情况，即最终被识别的点其实很早就已 经被找到了分支定界法的思想已经得到了广泛的应用，许多组合优化问题中 已经应用了分支定界法的思想，应用分支定界法解决了很多计算问题目前， 分支定界的思想已经成为求解全局优化问题的一种重要工具 1 2 2 区间算法 1 9 6 6 年m o o r e 在文献 1 1 中首先提出了区间算法，并且利用了区间分析成 功的计算了一个函数在子箱x 上的下界区间算法是一种非常有效的算法，应 用该方法基本上就能够求得目标函数的全局最优解区间算法可以分为定界、 分支、终止、删除、分裂五个步骤这五个步骤中包含了区间的三种规则：分 裂规则、删除规则和区间选择规则s k e l b o e 在1 9 7 4 年首先将分支定界原理和 m o o r e 的部分思想相结合起来，见文献 1 2 之后，m o o r e 又经过了修改，最终 在1 9 7 6 年得到m o o r e s k e l b o e 算法 下面的全局优化问题能够应用区间算法解决： m i n f ( x ) t 上式中，x r “是可行域，f ：x r 是目标函数，且f ( x ) 在可行域x 上连续 区间算法是求解上述问题的一种有效的方法，用区间变量来代替点变量进 行计算是区间算法的基本思想 区间算法可以分为三个步骤： 构造目标函数f ( x ) 的扩张函数f ( x ) ：x ( x ) 专，； 7 武汉理工大学硕士学位论文 利用分支定界的基本思想，也即是将可行域x 逐渐划分成小的区域； 在某个小区域上进行搜索，最终得到全局极小点z 和全局极小值f ( x ) 从上面区间算法的步骤中可知，区间算法是以区间分析作为基础的，并且 将分支定界的思想与m o o r e - s k e l b o e 算法结合起来，从而求解出目标函数f ( x ) 在 可行域上的全局极小点与全局极小值 1 2 3 随机搜索法 全局最优化问题中广泛采用随机搜索法的思想，这是因为随机搜索法具有 某些独特的优点：首先，一方面随机算法的形式非常简单，使得计算起来很方 便，并且在计算机上实现也是非常容易的，另一方面通过变换，一种随机搜索 算法非常容易的就能改进成另一种不同的算法其次，我们知道确定性算法的 使用对目标函数大都有限制，即很多问题不能够用确定性算法解决，然而随机 算法的使用范围很广，应用它能够解决一般的优化问题再次，除了求解无约 束的优化问题外，随机搜索方法对于求解带有约束的优化问题也比较容易 然而，随机搜索方法也有自身的不足例如，对于随机数的搜索，实现其 算法需要满足一定的条件，即随机数服从一定的分布，然而要找到服从一定分 布的随机数是件很难的事情 将局部寻优与随机取样两种方法放在一起使用是随机搜索法的基本方法 由于局部寻优和随机取样的方法很多，所以两种方法结合使用时，结合的方式 不同生成的算法也就会不同随机搜索法中，原始随机搜索法与单起点搜索法 以及多起点搜索法是最简单的三种随机搜索法这三种算法的相同点是，都是 要求随机产生的个点五，i = l ，2 ，要服从均匀分布不同的是，以函数值取得 最小值时的点作为最优解的是原始随机搜索法，而一般情况下，以概率l 获取 全局最优解的是单起点搜索法或是多起点搜索法 随机搜索法的思想在一些算法中也得到了应用，如聚类法就是在随机搜索 法的基础上建立起来的一种求解全局优化问题的算法聚类法的目的是在每个 极小点的区域内尽可能少的进行局部寻优，最好只进行一次，这样就避免了在 多起点搜索法中可能多次得到的局部极小点是同一个的情况节约了算法的执 行时间，从而提高了算法的效率 武汉理工大学硕士学位论文 1 2 4 打洞函数法 1 9 8 5 年l e v y 和m o n t a l v o 在文献 1 7 中首次提出打洞函数法 其考虑的优化问题如下所示： m ，。i x nf ( x ) 上式中目标函数厂( x ) 在x 上连续可微，可行域x 彤是有界闭箱 从上面的优化问题可知，对于打洞函数法，二次可微性是目标函数f ( x ) 在 可行域x = 缸r “l a 石 b ) ，其中口，b r ”上必须满足的条件，并且目标函数 f ( x ) 满足假设性条件，即极小点都是孤立的极小点，并且个数有限 打洞函数法由极小化阶段和打洞阶段两个阶段组成这两个阶段交替使 用，循环进行，直到目标函数的全局最优解被找到为止算法的具体过程是：首 先，在极小化阶段中，从可行域中某一初始点出发，应用任何一种已有的局部 极小化方法，得到函数目标函数f ( x ) 的一个局部极小点工其次，在打洞阶段 中，在x 处构造打洞函数t ( x , x ) ，并从x + 的某个领域中的任意一点出发，得到 点石o ，要求满足条件丁( 石，x o ) = 0 f ( x o ) = f ( x + ) l e v y 和m o n t a l v o 提出的打洞函数为： 肌垆黼 l ( z x ) 1 ( x x ) i 。 其中矽是( x - - 石) t 一x ) 的强度参数按照打洞函数的具体描述，上式中参数7 7 取较大值时，如果点x 为函数的极小点，那么可以得到点，使得对任意的 石o z = 缸x i 厂( x ) f ( x ) ) ，x o ，有t ( x o ) o 成立基于此，即可求出一 个关于函数r ( x ) 的极小点 l e v y 和m o n t a l v o 之后，许多学者对打洞函数法进行了更深入的研究，并且 取得了良好的效果y a o 在文献 1 8 中首次提出了动态打洞算法，这样就避免去 求r ( x ，x ) = 0 的解，并定义能量函数 e ( x ，x ) = r ( ) + kr t u ( t ) d t 其中夕( 工) = ( z ) 一( 石) ，“( ，) = ：三三 从上面的式子可知，要计算目标函数的极小值，必须首先求解常微分方程 组，但是这也是比较困难的工作后来，随着人们研究的深入，随机打洞算法 9 武汉理工大学硕士学位论文 及变形打洞函数法等方法也被发现 填充函数算法与打洞函数方法相似，也是一种常用的求解全局最优化问题 的算法，其基本思路也分为极小化阶段和填充阶段两部分，由此可看出，填充 函数法和打洞函数法在第一阶段是相同的对于填充函数算法，在下面的章节 中将进行详细的介绍 1 2 5 其它全局最优化方法 上一节介绍了四种常用的求解全局优化问题的算法，而求解全局优化问题 的算法有很多，如模拟退火算法、遗传算法、启发式算法也是常用的优化算法 模拟退火算法 1 9 是一种随机算法，是局部搜索算法的拓展，常用来求解 复杂的组合优化及n p 问题，与局部搜索不同之处是，它以选择邻域中值大的情 形是以一定的概率理论上来讲，模拟退火算法是一种从一个局部最优解跳到 另一个值更小的解，从而求出全局最优解的算法1 9 5 3 年m e t r o p o l i s 最早提出 模拟退火算法的思想，k i r k p a t r i c k 于1 9 8 3 年将这其思想应用到了组合最优化问 题时齐算法和非时齐算法是模拟退火算法的两种算法从理论研究可以发 现，模拟退火算法中按理论要求达到平稳点的分布几乎不可能的对于时齐算 法，经过无穷步的迭代后，要求最后要形成一个平稳分布，但是对于非时齐算 法，温度下降的迭代次数要求是指数次的但是就应用角度来说，只要是在能 够接受的时间内达到满意的解就行了所以，要利用模拟退火算法求解优化问 题的全局最优解，就目前的技术来说是很难实现的可参见文献 2 0 等 遗传算法起源于上世纪6 0 年代对自然及人工自适应系统的研究，最早由美 国的h o l l a n d 教授提出的模拟生物在自然中的遗传与进化，在这个过程中形成 的一种自适应全局随机优化搜索算法早在7 0 年代时，d ej o n g 就利用遗产算法 的思想，通过计算机做了很多纯数值函数优化计算的试验后来，g o l d b e r g 经过 大量的研究工作，在此基础上进行了系统的总结归纳，使得遗传算法的基本框 架最终形成在处理多个变量的n p 问题或多可行域中有多参数的问题时，遗传 算法非常有效的遗传算法的另外一个优点是和其它启发式算法的兼容性很 好，这样在处理复杂的优化问题时就能够使用其形成的混合算法 启发式算法就是求解全局最优化问题的另外一种有效的算法它包括模拟 退火，遗传算法，神经网络法和禁忌搜索法等方法启发式算法的思想是试图 模拟自然界的规律及人类的行为方式与常见的一些算法相比较，不同的是， 1 0 武汉理工大学硕士学位论文 启发式算法中具体的计算步骤是没有的，通常情况下它仅是整个运算过程中的 一个提纲，很多情况下，连数学上常用的收敛性和最优性的证明都没有给出， 由于这些缺陷的影响，使得很多实际问题都不能解决，故依然不被多数人所接 受因此，启发式算法一般不会用来解决像线性规划这样具有较好形式的优化 问题，它只是在解决没有很好算法的问题时才使用，如n p 问题 1 3 填充函数算法的研究现状 本节将重点介绍求解全局优化问题的填充函数算法 填充函数算法最早是由西安交通大学葛仁溥教授提出，见文献 2 1 ， 2 2 ， 2 3 ， 2 4 ， 2 5 等之后，许多学者对该算法进行了深入的研究，做了大量的 改进并逐渐完善参见文献 2 6 ， 2 7 ， 2 8 ， 2 9 ， 3 0 ， 3 1 ， 3 2 ， 3 3 等 五而 图1 工 z 填充函数算法的基本思路如图1 呻3 所示：用构造的填充函数逼目标函数走出 盆地，走近最优点具体步骤是： ( 1 ) 任取而为初始点，首先使用任意一种已有的局部极小化算法去极小化 目标函数f ( x ) ，从而得到局部极小点i ； ( 2 ) 在局部极小点i 处构造一个叫做填充函数的辅助函数f ( x ) ，以点i 为 武汉理t 大学硕士学位论文 初始点，用任意一种已有的局部极小化算法，极小化填充函数，( z ) ，得到点石； ( 3 ) 以工为初始点用局部极小化算法极小化f ( x ) ，得到另一个更好的局部极 小点x 。，也就是重复步骤( 1 ) 循环进行上述步骤，直到找不到更好的局部极小点为止，最终目标函数 厂( x ) 的全局极小点将会被找到 下面考虑问题( 1 2 ) ，为了方便研究，不妨将问题( 1 2 ) 的局部极小点的集 合用( 竹表示，将问题( 1 2 ) 的全局极小点的集合用g ( p ) 表示 在用填充函数法解决全局优化问题时，一般需要对目标函数f ( x ) 作如下的 假设瞄： 。 假设1 1 函数f ( x ) 在可行域x 上具有二次连续可微性 假设1 2 函数f ( x ) 满足强制性条件，即当删_ 佃，有f ( x ) 4 - 0 0 假设1 2 的成立是建立在存在一个有界闭集xcr ”的基础上的，且x 的内 部含有厂o ) 的所有全局极小点，这些所有的全局极小点就是我们所要研究的， 且这些极小点处的函数值都是比较小的那么无约束全局最优化问题( 1 2 ) 等 价于 m i n f ( x ) x e x 假设1 3目标函数f ( x ) 在可行域x 上的极小值点的个数是有限个的 假设1 4目标函数f ( x ) 在可行域x 上的极小值是有限个 填充函数算法是由极小化阶段和填充阶段两个阶段组成这两个阶段循环 进行，直至没有更好的局部极小点被找到在极小化阶段中，可以选取任意一 种有效的极小化算法去寻找目标函数的一个局部极小点，常用的方法有共扼梯 度法 3 9 ，梯度投影法 3 7 ， 3 8 以及拟