（应用数学专业论文）全局优化中填充函数方法的研究.pdf

论文题目： 专业： 硕士生： 指导教师： 全局优化中填充函数方法的研究 应用数学 张云 王雪峰 摘要 ( 签名) 伴随着计算机的高速发展，涌现出很多全局最优化的理论分析和计算方法，规模越 来越大的优化问题可以得到解决。一般地讲，求解全局优化问题的方法可分为两大类： 随机性算法和确定算法。常用的随机性有随机投点方法、遗传算法、模拟退火算法。经 典的确定性算法有区间算法、分枝定界方法、填充函数法、打洞函数法和积分水平集方 法等。其中1 9 9 0 年，葛仁溥教授等人首先提出填充函数方法，以后有很多学者对此方 法进行了改进，给出了更好的填充函数定义，构造了更简单的填充函数。由于填充函数 法对初始点的选择具有任意性，并且只需要应用成熟的局部极小化方法进行计算，因此 受到大家的欢迎，但是由于填充函数是目标函数的复合函数，且目标函数本身可能很复 杂，所以构造的填充函数形式也可能很复杂；填充函数的参数若过多，便难于调节。构 造形式简单以及较少参数甚至无参的填充函数，并使其具有良好的性质，以便节约计算 步骤和调参时间，提高算法的效率，是研究者继续研究填充函数的目的。 本文简述了全局优化问题及填充函数法的发展和研究现状。讨论了线性约束的凹二 次规划的全局最优条件，并构造了关于二次规划及非光滑规划的单参填充函数，证明该 函数满足填充函数的性质。分别对二次规划和非线性光滑设计填充函数算法，进行了数 据验证。数据结果表明算法是可行有效的，方法是全局收敛的。 关键词：线性二次规划；填充函数；全局优化；非光滑规划；全局极小点 论文类型：理论研究 s u b j e c t ：r e s e a r c h o nt h ef i l l e df u n c t i o nm e t h o d sf o rg l o b a l o p t i m i z a t i o np r o b l e m s s p e c i a l t y ：a p p l i e dm a t h e m a t i c s n a m e ：z h a n gy u n i n s t r u c t o r ：w a n gx u e f e n g a b s t r a c t ( s i g n a t ur e ) ( s i g n a t u r e ) c o m p u t a t i o n a lc o n t r i b u t i o n s h a v eh e l p e dt os o l v eg l o b a lo p t i m i z a t i o nt op r o b l e m s a r i s i n g f r o mi m p o r t a n t p r a c t i c a la p p l i c a t i o n s m a n yn e wt h e o r e t i c a l ，a l g o r i t h m i c a n d c o m p u t a t i o n a lc o n t r i b u t i o n sh a v eh e l p e dt os o l v eg l o b a lo p t i m i z a t i o np r o p o s e di sa m o n gt h e c o n t r i b u t i o nl i s t m a n yo p t i m i z a t i o np r o b l e m so fb i gd i m e n s i o n sc a nb es o l v e d i ng e n e r a l ， g l o b a lo p t i m i z a t i o np r o b l e m sh a v et w os p e c i e sm e t h o d s ：r a n d o ma l g o r i t h m sa n da s c e r t a i n a b l e a l g o r i t h m s r a n d o ma l g o r i t h m si n c l u d er a n d o mt h r o wp o i n t sa l g o r i t h m ，g e n e t i ca l g o r i t h m a n ds i m u l a t e da n n e a l i n ga l g o r i t h m a s c e r t a i n a b l ea l g o r i t h m si n c l u d ei n t e r v a la l g o r i t h m ， b r a n c h - a n d - b o u n da l g o r i t h m ，f i l l e df u n c t i o nm e t h o d ，t h et u n n e l i n ga l g o r i t h ma n di n t e g r a ls e t o fh o r i z o n t a la n ds oo n i n19 9 0 ，f i r s to fa l l ，g er e np up r o f e s s o rg i v et h ef i l l e df u n c t i o n m e t h o d ；t h em e t h o di sm o d i f i e db ym a n yr e s e a r c h e r sl a t e ro n t h eb e t t e rd e f i n i t i o no ft h e f i l l e df u n c t i o ni sg i v e n a n dt h eb e t t e rf i l l e df u n c t i o ni sc o n s t r u c t e d t h ei n i t i a lp o i n to ff i l l e d f u n c t i o nm e t h o dc a nb ea r b i t r a r i l y , a n dt h em e t h o db a s i ci d e ai sb yc o n s t r u c t i n ga u x i l i a r y f u n c t i o n s ，n a m e l yt h ef i l l e df u n c t i o n ，t of i n dg l o b a ls o l u t i o n so fo r i g i n a lo b j e c t i v ef u n c t i o n s t e pb ys t e p i nr e c e n ty e a r s ，m a n yk i n d so ff i l l e df u n c t i o n sw i t hp a r a m e t e r sh a v eb e e n p r e s e n t e d h o w e v e r , t h o s ep a r a m e t e r sa r et o oh a r dt oa d j u s ta n d i ti sm o s tp r o b a b l et h a tg l o b a l o p t i m i z e r sa r el o s to rf a k eb e t t e rm i n i m i z e sa r ef o u n d t h e r e f o r e ，f u r t h e rr e s e a r c hi sw o r t h yo f c o n t i n u i n go nh o ww ec a nc o n s t r u c tf i l l e df u n c t i o n sw i t hs i m p l e rf o r m s ，b e t t e rp r o p e r t i e sa n d m o r ee f f i c i e n ta l g o r i t h m s t h i sd i s s e r t a t i o nm a i n l yc o n c e r n st h em o d i f i e df i l l e df u n c t i o nm e t h o d sf o rn o n - l i n e a r g l o b a lo p t i m i z a t i o np r o b l e m s g l o b a lo p t i m i z a t i o np r o b l e m sa n ds o m eo fi t sm a i nm e t h o d s a r eb r i e f l yi n t r o d u c e d w ef i n d e x p l i c i tg l o b a lo p t i m a l i t yc o n d i t i o n so fl i n e a rc o n c a v e q u a d r a t i cp r o g r a m m i n g ，i n c l u d i n gs u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sa n ds o m en e c e s s a r y c o n d i t i o n s t h ep r o p e r t i e so ft h ep r o p o s e df i l l e df u n c t i o nm e t h o dw i t ho n ea d j u s t a b l e p a r a m e t e ra lec o n s t r u c t e df o rl i n e a rq u a d r a t i cp r o g r a m m i n g t h e o r e t i c a la n a l y s e sa n da l a r g e a m o u n to fn u m e r i c a lr e s u l t ss h o wt h a tt h i sm e t h o di se f f i c i e n t w eb a s e do nt h e o r y o f l i o n 。s m o o t ho p t i m i z a t i o n ；t h ep r o p o s e df i l l e df u n c t i o nm e t h o dw i t ho n ea d j u s t a b l ep a r a m e t e r i sc o n s t r u c t e df o rn o n s m o o t ho p t i m i z a t i o n t h i sm e t h o di ss i m p l ea n df e a s i b l e n u m e r i c a l e x p e r i m e n t ss h o wt h a tt h i sm e t h o di se f f i c i e n t ，a n dt h em e t h o di sg l o b a lc o n v e r g e n c e k e yw o r d s ：l i n e a rq u a d r a t i cp r o g r a m m i n gf i l l e df u n c t i o nm e t h o d g l o b a lo p t i m i z a t i o n n o n s m o o t ho p t i m i z a t i o n g l o b a lm i n i m i z e r t h e s i s ：t h e o r yr e s e a r c h 要料技夫学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：。强苏 日期：研f 酗 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：3 气云 指导教师签名： 之匆峥 弘刁年。e 月f 日 1 绪论 1 绪论 1 1 引言 最优化是- - f q 应用性很强的学科。它研究某些用数学模型表述的问题，并求出其最 优解，即对于给出的实际问题，从众多方案中选出最优方案。具体来说，最优化讨论决 策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质 及其实现。虽然最优化可以追溯到古老的极值问题，然而它成为- - f 7 独立的学科是在上 世纪4 0 年代末，在1 9 4 7 年d a n t z i g 提出求解一般线性规划问题的单纯形法之后。现在， 对线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规 划等各种最优化问题的理论研究发展迅速，新方法不断涌现，实际应用日益广泛。最优 化理论和方法在自然科学、经济计划、工程设计、生产管理、交通运输、网络交通、农 业预测、国防等重要领域的应用，己受到政府部门、科研机构和产业部门的高度重视， 成为一门十分活跃的学科。伴随着计算机的高速发展和优化计算方法的进步，规模越来 越大的优化问题可以得到解决。 非线性最优化问题作为运筹学的一个分支在二十世纪四十年代开始形成。其所研究 的内容包括模型创建、算法设计及收敛性分析、数值试验等。由于非线性最优化问题特 别注重算法的可计算性和实用性，因而现在的非线性规划实质上是传统的运筹学与计算 数学的交叉学科。非线性规划被用来识别和计算多个变量的非线性函数的最优解。如果 这些变量受到一些条件的限制时，称其为约束最优化问题；如果变量可以自由变动不受 约束的限制，则称其为无约束最优化问题。 在自然科学和社会科学的研究中，有大量理论问题和实际问题都与数学规划有关。 其中，全局优化问题又是数学规划理论中的一个重要的而又困难的研究领域。科学研究、 经济领域以及工程技术中的诸多问题都依赖于用数值方法寻求相应问题的全局解。在实 际应用中，尤其是当问题的规模较大时，通常存在多个不同的局部最优解，所以传统的 非线性规划技术不能被应用于求解全局优化问题。长期以来，全局优化问题一直受到研 究人员和工程技术人员的关注。近三十年来，尤其是最近几年，对全局优化问题的研究 在世界范围更受重视，也有了很多新的研究成果。 全局优化问题，一般表达式形式为： 罂 口旺 西安科技大学硕士学住论文 定义1 1 1 设x r ”是一个非空闭集，( x ) r “专r 在j c 上连续。若存在工x ， 使得f ( x ) 厂( x ) ( 厂( 石+ ) o 和善的邻域0 ( 矿，回= 扛置， 厂( 矿) 成立，则称x 是问题( 1 1 1 ) 的严格局部极小点。 定义1 1 。4 设x 互r “，如果函数，：r ”一r 在x 上l i p s c h i t z 连续，则称全局优化 问题( 1 1 1 ) 为l i p s c h i t z 最优化问题。 定义1 1 5 1 1 1 设x r ”为凸集，函数f ：x - - 9 r ，如果存在两个凸函数 p ：x r 和q ：x 寸r ，使得 i 工) = p ( 曲一g ( x ) ，v x x( 1 1 3 ) 则称函数厂是z 上的d c 函数。 定义1 1 6 1 1 在一个凸集上，若约束和目标函数都是d c 函数，则称为全局最优化 问题。 定义1 1 7 1 1 习假设s r ”是一个非空紧凸集，是定义在s 上的一个实值函数，函 数层：s 寸r 称为在s 上的凸包络，当且仅当满足下列条件： 1 ) 疋是定义在s 上的凸函数： 2 ) 对所有的x s ，有正o ) s f ( x ) ； 3 ) 不存在函数g ：s r 满足条件1 ) 和2 ) ，且对某个i s ，有石( 刁 八矿) ， 存在一条从x 到工下降轨迹，则称置称为f ( x ) 在极小点x 的盆谷。若x 是f ( x ) 的局 部极大点，则一，( 功在其局部极小点x 的盆谷称为( x ) 在局部极大点x 处的峰。 定义1 3 2 设x ：和善：都是，( 力的局部极小点，如果八) 以x ；) ( 或 f c x ：- ) ，( z ：) ) ，则称局部极小点工：e x ：低( 或高) 。设研和噬分别是i 和z 的盆谷， 如果局部极小点i 比j ；低( 高) ，则称其盆谷研比题低( 高) 。 填充函数算法由两个阶段组成：极小化阶段和填充阶段。这两个阶段交替进行，直 到找不到更好的局部极小点为止。第一步极小化算法有很多经典算法可以解决，可用拟 牛顿法，罚函数法等，寻找目标函数的一个局部极小点x ：。第二步，以当前极小点x ：为 基础定义一个填充函数，并利用该函数找到x ；，其中，使得f c x 2 ) s ，( i ) 。然 后以x ：为初始点，重复以上的步骤。直到找不到更好的局部极小点。 葛在文献【1 0 】首次给出了填充函数的定义，并构造了如下的填充函数： 5 ，：赤“p f 一学1 m s 川 其中，p 是参数，且满足，+ ，( i ) 0 。 由该函数可以得到求无约束问题( 1 - 3 1 ) 的全局极小点的填充函数法。然而该填充函 数还存在一些航由于撇函数d 一呼 的黼驸斛圳叫船眈 v p ，p ) 几乎都接近于零，从而出现假平稳点。为了克服这个缺陷，葛和秦在文【1 5 】 中给出了七个不同形式的填充函数： 氟机力= 去e 砸一学 o t x , x ；，力= 叩2l n ( r + 八砌一卜玎 6 0 ，i ，p ) = - p 2 l n ( r + ，一忙一x i i 驮工，i ，一) = 1 ( d 一厂( i ) 】铽p ( _ 秘一i8 2 ) 反z ，善：，4 ) = 1 ，j ( 力一八x ：) 】e x p ( 4 8 x x ：l 1 嘣南i ，彳) = - v f ( x ) 一2 a ( f ( x ) 一f ( x ；) x x x ? ) 咄“4 ) - - v ，( x ) - a ( f ( x ) - f ( x 沏嗣 ( 1 3 5 ) ( 1 3 6 ) ( 1 3 7 ) ( 1 3 8 ) ( 1 3 9 ) ( 1 3 1 0 ) ( 1 3 1 1 ) 他们指出后四个填充函数更好一些，参数减少了，当a 足够大时，就不会遗漏函数 ，( 曲的全局极小点。 进一步，葛和秦在文献【l l 冲给出了全局凸的填充函数的定义。一个连续函数u ( 曲 是全局凸的填充函数，必须满足以下的性质： ( 1 ) u ( 力在集合墨= 扛l ，o ) 厂( p ) ，善e q 上，除了初始点s 。，无其它平稳点。 ( 2 ) u ( 力在集合岛= x l 以力 0 其中吼是目标函数的一个二次逼近，瓯是参数。 1 5 非光滑规划 目标函数和约束函数其中有一个是非光滑函数，则优化问题称为非光滑优化。非光 滑问题可写为： n m f i m 。m ) ( 1 钏 虹甄( 工) = 0i = l ， g ，( x ) 0 _ ，= l ，m 其中函数，( x ) ，噍( ，g s o ) ：r 4 斗丑。当其中之一不连续不可微时，称为非光滑优化或 不可微规划问题，若m = ，= 0 ，则称该问题称为无约束问题。 对于非光滑规划，常用的经典优化方法显然是不合用的，它们甚至不可能给出最优 点的一个很粗糙的近似解。这种状况不仅对于梯度型的算法如此，对于无需计算导数的 方法也一样。 非光滑规划是当前数学、应用数学以及工程优化设计中较为活跃的研究领域之一， 很多理论和算法以被提出。主要是把已经发展很成熟的光滑规划中的些算法思想和技 巧拓广并应用到非光滑规划中。近年来提出的算法大致分为：罚函数法，次梯度法，填 充函数法，积分下降算法，不动点法，极大商方法等。 1 6 相关记号 在本论文中，将用到如下假设和定义。设向量x 彤，有删= i # l 。对- - + n x n i - ! 矩阵日，以丑( 日) 表示其最大的特征值，以 ( 日) 表示其最小的特征值，d i a g ( h ) 是一 个撑疗对角矩阵，它的第i 个对角线元素等于日的对角线元素。 本论文主要研究和构造填充函数算法，全文安排如下：第一章绪论，介绍问题的背 景，意义和发展现状。第二章介绍了二次规划问题的全局优化最优条件，构造二次规划 的填充函数，给出算法及数值实验。第三章研究了非光滑规划的全局极小，构造了一个 非光滑规划的填充函数，给出算法及数值实。 8 2 全局优化方法概述 2 1 几种确定算法介绍 2 1 1 积分水平集法 2 全局优化方法概述 总极值问题司表不为： 矿= m 填，( 曲 ( 2 1 1 ) h = 缸e d i ( 曲= 一 ( 2 1 2 ) 作如下假设： ( 1 】厂在d 上是连续的； ( 2 ) 存在一个实数c ，使得水平集日。= 红r ”l ，( x ) c ) 和d 的交集非空。 该方法终止判定准则，算法理论完善。其困难是水平集日。难以精确确定。 算法主要步骤如下： 步1 令k - - - o 。i r x o d ，给定充分小正数s ，令c o = f ( x o ) ，正= 缸i x d ，厂 ) 白 ； 步2 若( 日。) = 0 ，则以为总极值，以为总极值点集，终止； 步3 计算均值： q “2 i 面i 肛( 工) 咖 ( 2 j 3 ) 令日q 。= 伽i i ( e d ，厂( 力c k “ ( 2 1 4 ) 若靠+ = q ，则q + 。为总极值，日。+ 。为总极值点集，转步6 ；否则转下一步； 步4 计算方差 肚志肛嵋) 2 咖 ( 2 1 5 ) 步5 若v e ，令础+ l ，转步2 ；否则转步6 ； 步6 令厂= 气+ ，且日= 日。， 产为_ 厦力在d 中的近似总极值点集，广是近似总 极值，算法终止。 2 i 2 分支界定方法 分支界定方法广泛用于求解许多较复杂的全局问题。其基本思想是对松弛后的可行 域进行剖分，再在每个子区域上确定目标函数的上下界，依次删除不包含全局最优解的 9 西安科技大学硕士学位论文 子域，从而使问题的求解得以简化。该方法已广泛应用于凹规划，d c 规划及l i p s c h i t z i a n 规划。 首先用分支界定方法求解下述全局优化问题： m i n f ( x )( 2 1 6 ) 其中f ：r “哼r ，d c r ”，d 为紧集，在d j = 连续。主要步骤为： 步1 选择初始可行域m 。，d c m 。，把 如划分为有限个子集m ，f ，i 是指标集。 划分要满足条件： m o - - u u m ，n m j = a m 。n a m ，v i ，i , i j e 其中a m ，表示m ，的边界； 步2 对每个子集m 。确定满足下面条件的上，下界口( m 1 ) ，( m j ) ： 夕( m ) i n f f ( m , nd ) 口( m ) 再令= m i l l 侈( m ) i ，j ，口= m a x 缸( m ) i f e ， ，则有m i a f ( o ) 口； 步3 若a 邛或a 一降，为充分小的正数，则算法终止，否则转步4 ； 步4 选择适当的子集m ，作更细的划分，转步2 。 分支界定法的实现主要是划分、选择和定界三个运算步骤。划分、选择和定界不同， 产生对不同的实现算法。分支界定法中一般把剖分集取成简单多面体，如单纯形、长方 形、凸多面锥等。t 分支界定方法的优点是，在每个迭代步总是可以删除d 的那些一定不包含最优解得 子域，从而可以减少迭代步骤；缺点是近似解的精度由当前_ 步的上下界的差0 【一p 来度 量，这样，一个可能早就找到了的“好的”可行点常常要等到好几步以后才会被识别。 2 1 3 打洞函数方法 考虑问题( 1 1 1 ) ，目标函数，( 功是在x = 扛r ”i a x s 6 ，4 ，b r ”上的二次连续 可微函数。设，( 力有有限个极小点，且都是孤立的。 该方法由两个过程组成：极小化过程和“打洞”过程，这两个过程交替进行，以求 得目标函数的全局极小值。具体描述如下： 在极小化过程中，从某个初始点出发，用任何一个有效的局部极小化方法求的 函数触) 的一个局部极小点一； 在“打洞”过程中，构造打洞函数t ( x ，矿) ，a k x 的一个领域中的任意一点出发， 找到某个点p ，满足r o o ，力= 0 f ( x o ) = ，( 妒) 。 1 0 2 全局优化方法概述 咖和删v o 绌的拥函姚= 若器，撕黪数。 由该“打洞”函数的定义，当t 1 充分大时，点矿为极小点：在极小化打洞函数过程 中求到且对所有的x o z = 伽xj ，( 力( 妒) ，p x + ，满足t ( x o ) 0 。于是可求 得孔功的一个非正的极小点。 1 2 4 区间算法 考虑如下全局优化问题： m 啦厂( 工) ( 2 1 7 ) 其中f ：j r ，x r f 龇连续。 区间分析的基本思想是：用区间变量代替点变量进行计算。区间方法是求解问题 ( 2 1 7 ) 种可行的方法。该方法以区间分析为基础，m o o r e s k e l b o e 2 2 j 算法和分支界定的 思想相结合，求出目标函数在x 总极值和总极值点集。 介绍算法之前，先给出所需要的定义、记号和区间运算。记i 为实闭区f s q a ，6 】集合， 其中，口，b e r ，a b 。对v a ，b i 的运算定义为： a b = 口6 i a e a ，b 曰 其中可以是加、减、乘和除运算，对于除法，有o 仨口。 若a = 【l b a ，西伽，其中l b a ，觑4 分别表示a 的上下界。区间宽度为国( ) = b - a 。 如果眶屁，那么j 户 】1 y e , y _ c d ) 。 定义l 2 1 设掣矛嗲r ，且妖1 ) = 妖功辟y ) 表示函数f 在y e i ( x ) 的取值范围，若 函数f ：，( d ) 哼j 满足 o f ( y ) g ，( 1 0 ，v y ，( x ) ( 2 1 8 ) 则称f 是珀q 扩张函数。 m o o r e s k e l b o e 算法： 步l 令l ，i 弘计算尺】，) ； 步2 令尸m i n f ( r ) ，令初始集合肛( ) ； 步3 选择坐标方向七e 甜( y ) = 烈z ) ，其是与子箱y 具有最长的棱平行： 步4 用垂直于方向k 的超平面把y 分成两个子箱n ，圪，使得r - h u 圪。计算 h n ) j 飞圪) ； 步5 对i = l ，2 ，令= t b f ( e ) ，把( y 从集合三中去掉； 步6 把( 巧，v i ) ，( ，v 2 ) 加入到三中，把上从小到大排列，记的第一对为( y ； 步7 若国( f ( l ” 占，则终止，否则转步3 。 注：l b f ( 功表示h 功的上界。 西安科技大学硕士学位论文 算法的主要思想是：先做目标函数f ：x - - 盈石r 4 的扩张函数f ：托r ) 专i ，然 后利用分支界定法的思想，把x 逐步细分，在某个箱子上搜索，最后找到最优值。 2 2 随机性算法 2 2 1 模拟退伙算法 模拟退伙算法多用于复杂的优化组合和n p 问题。基本思想来源于物理上的退伙过 程，数学上有“马尔可夫链”可以对它进行严格的描述。基于马尔可夫过程理论，l u n d y m 和m e s s a 证明了模拟退伙算法以概率1 收敛于全局最优解。在实际应用中许多参数 需要调整，是一个启发式算法。 模拟退伙算法的基本思想如下： 算法的研究对象是由一个参数所确定的某种配置。设计一个基于该配置的价格函数 ( 石) ，对于配置的优化过程就转化为对f ( x ) 的极小化过程，( 工) 的极小化过程模拟自 然界的退火过程，由一个逐步冷却温度t 来控制，对于每一个温度，尝试一定的步骤， 在每一个极小化步骤中，随机地选择一个新的配置并计算价格函数，如果厂( d 的值小 于以前的值，则选择新的配置方案；如果大于以前的值，则计算概率： p = e x p 一觚k 。珂 ( 2 2 1 ) 其中，七是波尔兹曼常数，然后在( o ，1 ) 上产生随机数r a n d ，如果r a n d p ，则选择新的 配置方案，否则仍保留原方案。重复以上步骤，直到系统冷却不再产生更好的配置。 模拟退伙算法的数学模型描述为：在给定邻域结构后，模拟退伙过程是从一个状态 到另一个状态不断地随机游动。把此过程用马尔可夫链来描述。当t 为确定值时，两个 状态的转移概率定义为： i g ，p ) 以( f ) v i _ ， 鳓2 1 1 一量g y ( t ) a y ( t ) 吲 ( 2 2 2 ) 其中俐表示状态集合中状态的个数，q ( f ) 称为从i 至：l j j 的生产概率，瓯( f ) 表示在状态 i 时，状态被选取的概率以( f ) 称为接受概率，表示状态f 产生，后，接受，的概率。 _ ，被选中的概率记为： q 价志，“( f )( 2 2 3 ) 1 0j n ( o 1 2 2 全局优化方法概述 i i 目| | i i | j i i 一 接受，的概率函数为： 纵垆 0 舭，笼三嬲 以( 垆1 晰钙f ) 编 砀 4 ) 模拟退伙算法分为时齐算法和非时齐算法两类。研究表明1 3 5 1 ，按理论要求达到平 稳点分布来应用模拟退伙算法是不可能的。时齐算法要求无穷步迭代后达到平稳分布， 而非时齐要求温度下降的迭代步为指数次的。从应用的角度看，在可接受时间内达到满 意解就可以接受，现有技术很难保证该算法能得到全局最优解。 2 2 2 遗传算法 遗传算法是随机性优化算法，它是模拟自然晃生物进化过程与机制求解极值问题的 一类组织、自适应人工智能技术。它是一种仿生算法，从一个初始种群出发，通过选择 复制和遗传因子的作用，使种群不断进化，最终收敛于最优状态。遗传算法的主要特点 是f 蚓； ( 1 ) 群体搜索； ( 2 ) 针对次数的染色体( 编码) 进行操作，不需要依赖目标函数梯度的信息； ( 3 ) 只利用目标函数作为评优准则 ( 4 ) 使用随机规则，而不是确定规则进行搜索。 基于这些特点，遗传算法十分适合处理带有多参数、多变量、多目标和在多区域的 n p h a r d 问题。并在处理很多组合优化问题时，不需要很强的技巧。遗传算法与其它启 发式算法有较好的兼容性。 遗传算法包括以下主要步骤： ( 1 ) 对优化问题的解进行逐个编码。把优化问题的解的编码称为染色体，每一个解都有 编码，每一个编码都有染色体。组成编码的元素称为基因。 佗1 适应函数的构造和应用。适应函数依据优化问题目标函数而定。当适应函数确定以 后，自然选择规律以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪 些别淘汰。生存下来的染色体组成种群，生成可以繁衍下一代的群体。 ( 3 ) 染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产生。 ( 4 ) 变异。新解产生过程中可能发生基因变异，使某些编码发生变化，使解有更大的遍 历性。 西安科技大学硕士学位论文 3 1 引言 3 线性约束二次规划的填充函数 二次规划问题是数学规划理论的重要组成部分。理论上，二次函数是非线性函数中 较为简单的一类函数。由于很多函数可以用二次函数逼近。所以二次规划问题在非线性 规划理论中占有重要地位。在实际中，二次规划问题也有着广泛的应用背景。 目前为止，二次规划m i n q ( x ) = 妄，h x + g 善的全局优化问题还没有普遍适用的条 z 件和方法。矩阵日为正定、半正定对称阵时，二次规划是凸问题，它的局部极小点也是 全局极小点，有很多方法可以求解，比如积极集法、对偶方法、内点算法等( 详见文献 【2 5 】) 。p a r d a l s 在文献 2 6 】中指出，解不定二次规划问题是n p h a r d 问题。给出一个可行 点，检验其是否为局部解也是n p h a r d 的。并指出对此类问题，一般来说，没有局部的 准则可用于全局问题。如： r 口，1 蛾 ( 扣+ x ? ) - 1 以s l ，f = 1 ，片 ( 3 1 1 ) l l = j 在此例中，共有3 “个k - t 点，2 “个局部极大点。尽管目标函数和约束函数的形式 比较简单，不定二次规划的全局优化问题是非常值得探讨的问题。 首先给出一些基本定义和引理。 假定当j 佃时，f ( x )