（应用数学专业论文）求解约束优化问题的几种智能算法.pdf

摘要 摘要 智能计算也称为“软计算”，是人们受自然( 生物界) 规律的启迪，根据其原 理，模仿其某些规律而设计的求解实际问题的一类算法。它将复杂任务交给大量 的群体合作完成，具有概念简单、实现方便的特点。由于群体智能优化算法具有 的分布性、简单性、灵活性和健壮性，已在计算机科学、知识发现、通信网络、 机器人等研究领域显示出潜力和魅力，成为智能算法领域一个研究热点。 实际遇到的数值优化问题绝大多数是有约束的，我们求解约束优化问题时首 先必须处理好约束。罚函数法是处理约束最常用的方法之一，罚函数法简单易行， 但困难在于实际操作时要仔细调整罚因子，用以确定对不可行个体的合适的惩罚 力度，才能使进化算法获得好的效果。 为了有效解决约束优化问题，本文分别研究用进化算法与粒子群算法两种智 能算法来处理约束优化问题。从约束优化智能算法= 约束处理技术+ 智能算法的研 究框架出发，对约束处理技术和智能算法分别进行改进，从而设计出几种新的智 能算法。本文的主要工作如下： 1 罚函数法是进化算法中解决约束优化问题最常用的方法之一，它通过对不可 行解进行惩罚使得搜索逐步进入可行域。罚函数常定义为目标函数与惩罚项之和， 其缺陷一方面在于罚因子难以控制，另一方面当目标函数值与惩罚项的函数值的 差值很大时，此模型不能有效地区分可行解与不可行解，从而不能有效处理约束。 为了克服这些缺点，首先引入了目标满意度函数与约束满意度函数，前者是根据 目标函数对解的满意度给出的一个度量，而后者是根据约束违反度对解的满意度 给出的一个度量。然后定义了一种新的罚函数建立新罚函数模型。并且设置了自 适应动态罚因子，其随当前种群的质量及进化代数的改变而改变。进一步，设计 了新的杂交和变异算子。在此基础上，提出了解决约束优化问题的一种新的进化 算法。 2 首先，为了利用可行域附近的不可行点的信息，构造了自适应动态的扩展可 行域，不仅包括所有可行点，还包括可行域附近的不可行点。其次，为了使得不 同约束优化问题采取统一比较标准，提出了以个体序值构造适应度函数，即以个 体序值代替个体适应度值评价个体。最后，提出了改进的算术杂交算子，但比杂 交算子能产生更多的好点。 3 首先提出了不带参数的罚函数，它能有效处理约束，由目标函数和罚函数 构造一个双适应度函数。此双适应度函数能有效区分可行解与不可行解。而且还 能合理评价可行解和不可行解。同时提出了单纯形杂交算子和p s o 变异算子，两 类新算子能更有效地开发搜索空问，从而有利的搜索方向，因此更易产生好解。 求解约束优化问题的儿种智能算法 4 粒子群算法是解决优化问题的有效工具，但是用其解决约束优化问题时， 容易产生早熟问题，从而得到局部最优解而非全局最优解。根据约束优化问题的 特点，本文提出的双粒子群算法可以克服这一缺陷。首先为了挖掘较好非可行解 ( 违反度较小且目标值很好) 的信息，提出扩展的动态优化域( 在可行域中添加 高质量的不可行点的同时抛弃低质量的可行点形成的区域) ，使得搜索从可行域内 外两个方向进行，从而增强算子的搜索最优解的能力。其次为了增强种群多样性， 产生更多好解以避免早熟，本算法设计了两个进化方向，依据个体可行与否而采 取不同的进化方向。 关键词：智能算法进化算法粒子群算法约束优化罚函数 a b s t r a c t a bs t r a c t i n t e l l i g e n tc o m p u t i n go r i g i n a t e df r o mn a t u r a l ( b i o l o g i c a l ) r u l e s ，a l s ok n o w na s s o f tc o m p u t i n g ”i sak i n do fc o m p u t a t i o n a la l g o r i t h m ss i m u l a t i n gt h e s er u l e sf o r s o l v i n gp r a c t i c a lp r o b l e m se f f i c i e n t l y i t sr e l a t e dc o n c e p t sa r ee a s yt ou n d e r s t a n da n di t i su s u a l l yc o n v e n i e n tt oe x e c u t e m o r e o v e r , i ti su s u a l l ye f f i c i e n tb e c a u s eap o p u l a t i o n o fi n d i v i d u a l sc o o p e r a t et oc o m p l e t et h et a s k d u et ot h ea d v a n t a g e so fi t ss i m p l i c i t y , f l e x i b i l i t ya n dr o b u s t n e s s ，i n t e l l i g e n tc o m p u t i n gh a sb e c o m eah o tr e s e a r c ha r e aa n dh a s b e e nw i d e l yu s e di nm a n yf i e l d ss u c ha sc o m p u t e rs c i e n c e ，t e l e c o m m u n i c a t i o nn e t w o r k ， k n o w l e d g ed i s c o v e r y , r o b o t sa n ds oo n m o s tr e a l - w o r l do p t i m i z a t i o np r o b l e m si n v o l v ec o n s t r a i n t s i ti sn e c e s s a r yf o ru s t od e a lw i t hc o n s t r a i n t s f i r s t l yw h e nw ea r ef a c e dw i t hac o n s t r a i n e do p t i m i z a t i o n p r o b l e m t h em e t h o d sb a s e do np e n a l t ya r eo n eo ft h em o s tc o m m o na p p r o a c h e st od e a l w i t hc 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 i ns p i t eo ft h e i rs i m p l i c i t yt h e yh a v es e v e r a l d r a w b a c k si nw h i c ht h em a i no n ei st h ed i f f i c u l t yt ot u n et h ep e n a l t yp a r a m e t e r s a c a r e f u lt u n i n gs c h e m ei sr e q u i r e dt ot h ep e n a l t yp a r a m e t e r st h a tc a na c c u r a t e l ye s t i m a t e t h ed e g r e eo fp e n a l i z a t i o ns ot h a tt h ea p p r o a c hc a ng e ta p r o p e rb a l a n c eb e t w e e nt h e f e a s i b l es o l u t i o n sa n di n f e a s i b l es o l u t i o n sa n db e c o m em o r ee f f i c i e n t i no r d e rt os o l v ec 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 se f f e c t i v e l y , e v o l u t i o n a r y a l g o r i t h m sa n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m sa r ea p p l i e dt od e a lw i t ht h e m s t a r t i n gf r o mt h ef r a m e w o r kt h a tt h ec o n s t r a i n e do p t i m i z a t i o na l g o r i t h m = c o n s t r a i n t p r o c e s s i n gt e c h n o l o g y + i n t e l l i g e n ta l g o r i t h m s ，s o m ei m p r o v e da p p r o a c h e so nb o t h b a s i ca s p e c t s ：c o n s t r a i n th a n d l i n gt e c h n o l o g ya n di n t e l l i g e n ta l g o r i t h m s ，h a v eb e e n p r o p o s e d t h em a i nc o n t r i b u t i o n so ft h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s ： 1 p e n a l t yf u n c t i o nm e t h o di so n eo ft h em o s tw i d e l yu s e dm e t h o d sf o r 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 si ne v o l u t i o n a r ya l g o r i t h m s i tm a k e st h es e a r c h a p p r o a c ht ot h ef e a s i b l er e g i o ng r a d u a l l yb yt h ew a yt op u n i s ht h ei n f e a s i b l es o l u t i o n s t h ep e n a l t yf u n c t i o n sa r eu s u a l l yd e f i n e da st h es u mo ft h eo b j e c t i v ef u n c t i o na n dt h e p e n a l t yt e r m s t h i sk i n do ft h em e t h o d sa r eo ft w om a i nd r a w b a c k s f i r s t l y , i ti s d i f f i c u l tt oc o n t r o lp e n a l t yp a r a m e t e r s s e c o n d l y , w h e nt h ed i f f e r e n c eb e t w e e nt h e o b j e c t i v ef u n c t i o nv a l u ea n dt h ec o n s t r a i n e df u n c t i o nv a l u ei sg r e a t t h ea l g o r i t h mc a l l n o te f f e c t i v e l yd i s t i n g u i s hf e a s i b l es o l u t i o n sf r o mi n f e a s i b l eo n e s 。a n dt h u sc a nn o t h a n d l et h ec o n s t r a i n t s e f f e c t i v e l y t oo v e r c o m et h es h o r t c o m i n g s ，t w os a t i s f a c t i o n d e g r e ef u n c t i o n sd e f i n e db yt h eo b j e c t i v ef u n c t i o na n dt h ec o n s t r a i n t sf u n c t i o na r e d e s i g n e d ，r e s p e c t i v e l y an e wp e n a l t yf u n c t i o ni sc o n s t r u c t e db yt h e s et w os a t i s f a c t i o n d e g r e ef u n c t i o n s m o r e o v e r , a l la d a p t i v e p e n a l t yp a r a m e t e ri s d e s i g n e d ，w h i c hi s v a r y i n gw i t ht h eq u a l i t yo ft h ep o p u l a t i o na n dt h en u m b e ro ft h eg e n e r a t i o n s a sar e s u l t ， t h ep e n a l t yp a r a m e t e rc a nb ee a s i l yc o n t r o l l e d b a s e do nt h e s e ，an e w p e n a l t yf u n c t i o n o p t i m i z a t i o nm o d e li sp r o p o s e d f u r t h e r m o r e ，an e wc r o s s o v e ro p e r a t o ra n dan e w 求解约束优化问题的儿种钾能算法 m u t a t i o no p e r a t o ra r ed e s i g n e d f i n a l l y , an e we v o l u t i o n a r ya l g o r i t h mf o rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m si sp r o p o s e d 2f i r s t l y , i no r d e rt om a k eu s eo ft h ei n f o r m a t i o no ft h ei n f e a s i b l es o l u t i o n sn e a rt h e f e a s i b l er e g i o n ，as e l f - a d a p t i v e l ye x t e n d e d f e a s i b l er e g i o ni sc o n s t r u c t e d t h i sr e g i o n i n c l u d e sn o to n l ya l lf e a s i b l es o l u t i o n s ，b u ta l s os o m ei n f e a s i b l es o l u t i o n sn e a rt h e b o u n d a r yo ft h ef e a s i b l er e g i o n f u r t h e r m o r e ，i no r d e rt od e s i g nau n i v e r s a la n df a i r s o l u t i o nq u a l i t ym e a s u r ef o rd i f f e r e n tc 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 ，an e wf i t n e s s f u n c t i o nb a s e do ns t o c h a s t i cr a n k i n gi sc o n s t r u c t e d f i n a l l y , an e wc r o s s o v e ro p e r a t o r , w h i c hi st h ei m p r o v e m e n to ft h ea r i t h m e t i cc r o s s o v e ro p e r a t o r , i sp r o p o s e d i tc a n p r o d u c ei n d i v i d u a l sw i t hb e t t e rd i v e r s i t yt h a n t h ea r i t h m e t i cc r o s s o v e ro p e r a t o rc a n 3f i r s t l y , an e wp e n a l t yf u n c t i o nw h i c hh a sn op a r a m e t e ra n dc a ne f f e c t i v e l yh a n d l e c o n s t r a i n t si sp r o p o s e d ，t h e nah y b r i df i t n e s sf u n c t i o nd e f i n e db yt h ep e n a l t yf u n c t i o n a n do b j e c t i v ef u n c t i o ni sd e s i g n e d t h en e wf i t n e s sf u n c t i o nn o to n l yc a nd i s t i n g u i s h f e a s i b l ei n d i v i d u a l sf r o mi n f e a s i b l eo n e s ，b u ta l s oc a ne v a l u a t eb o t hf e a s i b l ea n d i n f e a s i b l ei n d i v i d u a l sr e a s o n a b l y m o r e o v e r , an e wc r o s s o v e ro p e r a t o rb a s e do ns i m p l e x s c h e m ea n dap s om u t a t i o no p e r a t o ra r e a l s op r o p o s e d t h e s en e wo p e r a t o r sc a n e x p l o i tt h es e a r c hs p a c em o r ee f f i c i e n t l y , a n dc a np r o v i d ep o t e n t i a ls e a r c hd i r e c t i o n a s ar e s u l t ，t h eb e r e ri n d i v i d u a l sc a no f t e nb eg e n e r a t e d 4p a r t i c l es w a r ma l g o r i t h mi se f f i c i e n tt os o l v eo p t i m i z a t i o np r o b l e m s h o w e v e r , f o r 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 ，i tu s u a l l yc a u s ep r e m a t u r ea n dc a nt r a pi n t oal o c a l o p t i m u me a s i l y t oo v e r c o m et h i ss h o r t c o m i n g ，ab i - p a r t i c l es w a r ma l g o r i t h mf o r 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 si sp r o p o s e d f i r s t l y , i no r d e rt ou s et h ei n f o r m a t i o n o ft h eg o o di n f e a s i b l es o l u t i o n s ( i e w i t hl o wc o n s t r a i n e dv i o l a t i o na n dg o o do b j e c t i v e f u n c t i o nv a l u e ) ，ad y n a m i ce x t e n d e do p t i m i z a t i o nr e g i o n ( d e l e t i n g p o o rf e a s i b l e s o l u t i o n sa n da d d i n gg o o di n f e a s i b l es o l u t i o n si nf e a s i b l er e g i o n ) i sd e s i g n e dw h i c hc a n s e a r c hf r o mb o t ht h ef e a s i b l er e g i o na n dt h ei n f e a s i b l er e g i o n s e c o n d l y , t w os e a r c h d i r e c t i o n sa r ed e s i g n e df o rf e a s i b l ea n di n f e a s i b l es o l u t i o n s ，r e s p e c t i v e l y t h e ya r e e f f i c i e n tt oe x p l o i tt h es e a r c hs p a c ea n di n c r e a s ed i v e r s i t yo ft h ep o p u l a t i o n k e y w o r d s ：i n t e l l i g e n ta l g o r i t h m s p a r t i c l es w a r ma l g o r i t h m se v o l u t i o n a r y a l g o r i t h m s c o n s t r a i n e do p t i m i z a t i o n p e n a l t yf u n c t i o n 独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 日期鲨理：垦! 一卑 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 1 1 引言 大自然是人类获得灵感的源泉。从远古时代的单细胞形成到人类这种有思维， 有智慧的高级生物体的产生，经历了复杂的进化道路。事实证明，人类找到了生 命的最佳结构与形式，它不仅可以被动地适应环境，更重要的是，它能够通过学 习、模仿与创造，不断提高自己适应环境的能力。几百年来，模拟生物界所提供 的答案来解决实际问题己经被证明是一个成功的方法。 随着计算机技术的飞速发展，智能算法【i 1 2 】的应用领域也越来越广泛。智能 算法也有人称之为“软计算”，是人们受自然( 生物界) 规律的启迪，根据其原理， 模仿其某些规律而设计的求解实际问题的一类算法。 进化计算【1 3 19 】是一种模拟生物进化过程与机制求解问题的自组织、自适应人 工智能技术。生物进化过程是一个从简单到复杂、从低级到高级的自然的、并行 发生的、稳健的优化过程，这一优化过程的目标是能够适应环境的要求。而这正 是进化计算理论的思想起源。进化计算中以生物界的“优胜劣汰、适者生存”作 为算法的进化规则。 进化算法之所以能够增强解决问题的能力，是因为自然演化过程本质就是一 个学习与优化的过程。该算法的核心思想是：生物进化过程( 从简单到复杂，从低 级到高级) 本身是一个自然的，并行发生的，稳健的优化过程，其目的就是要适应 环境。生物种群通过“优胜劣汰”及遗传变异来达到进化，生物的进化通过繁殖， 变异，竞争和选择实现的。进化算法通过模拟“优胜劣汰，适者生存”的规律激 励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程中保持己有的结构，同 时寻找更好的结构。 作为随机优化与搜索算法，进化算法不是盲目式的乱搜索，也不是穷举式的 全面搜索，它根据个体生存环境即目标函数来进行有指导的搜索。它使用种群搜 索技术，通过对当前种群施加选择、交叉、变异等一系列遗传操作从而产生出新 一代的种群，并逐渐使得种群进化到包含或接近最优解的状态。进化算法只需利 用目标的取值信息，不受其搜索空问限制性条件( 如可行域的凸性等) 约束，也 不需要梯度、连续性、凸性等信息，因而适用于大规模、高度非线性的不连续、 多峰函数的优化以及无解析表达式的目标函数优化，具有很强的通用性。进化算 法擅长全局搜索以避免在局部最优附近徘徊，由于算法的操作对象是一组个体， 而非单个个体，具有多条搜索轨迹，因而具有隐并行性。 粒子群优化算法i z 0 川( p s o ) 是一种进化计算技术( e v o l u t i o n a r yc o m p u t a t i o n ) ， 由e b e r h a r t 博士和k e n n e d y 博士发明。粒子群优化算法( p s 0 1 也是起源对简单社 求解约束优化问题的儿种智能算法 会系统的模拟，最初设想是模拟鸟群觅食的过程。 p s o 同进化算法类似，是一种基于迭代的优化工具。系统初始化为一组随机 解，通过迭代搜寻最优值。但是并没有进化算法用的交叉( c r o s s o v e r ) 以及变异 ( m u t a t i o n ) 算子。而是粒子在解空间追随最优的粒子进行搜索。同进化算法比较， p s o 的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函 数优化，神经网络训练，模糊系统控制以及其他进化算法的应用领域【3 2 3 3 。 约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题【3 丌。 近年来，约束优化问题己成为智能算法研究的一个重要方向。处理约束优化问题 的关键在于如何有效处理约束条件。使用罚函数思想来处理约束优化问题是一种 最常用的方法，该方法通过给目标函数增加惩罚项，把约束优化问题转化为无约 束问题，以无约束优化问题的目标函数作为适应值函数来引导搜索。但是此类方 法的困难之处在于难以设置合适的罚因子以平衡目标与约束两者的关系。 本文分别应用进化算法与粒子群算法两种智能算法来处理约束优化问题。从 约束优化智能算法= 约束处理技术+ 智能算法的研究框架出发，从约束处理技术和 智能算法两个基本方面对约束优化智能算法进行改进。 1 2 约束优化问题综述 现实世界中存在的大多数问题都有好几个解，有些还可以有无限多个解，最 优化的目的是：对于一个给定问题，在这些可能的解中，按某种有效性或可使用 性的准则来找到最好的解。由于利用了高效率的数字计算机，人们发展了许许多 多的数学最优化方法l 弘j 。 数学规划【3 州o 】就属于这些最优化方法，而非线性规划是数学规划中的一种特 殊情况。非线性规划【4 1 5 3 】研究非线性或线性函数在线性与( 或) 非线性约束条件下的 最优化问题。典型的应用领域是预报、生产流程的安排、库存控制、质量控制、 保养和维修、过程设计、会计过程以及资金预算等。全由线性函数组成的最优化 问题，即线性规划问题。在过去几十年中，数学规划领域中大部分研究工作集中 在线性规划范围内。这方面的研究非常成熟，所以当时的技术水平能很好的解决 大多数的线性规划问题。而且，对于线性规划问题，总有单纯形算法来求解它们， 从这个意义上说，对非线性规划的最优化问题则没有普遍适用的解法。虽然非线 性规划的问题越来越受到大家的重视，而且已经提出了解决非线性规划问题的许 多策略，但是有效的方法并不多。现行的非线性规划算法的适用范围是有限的， 随着科技的不断发展以及人类对现实世界进行数字描述的迫切要求，我们需要应 用范围更广泛、更有效的求解非线性规划问题的方法【5 5 州】。 第章绪论 一非线性约束优化问题模型及其基本概念【6 ”3 】 非线性约束优化问题可归结为求解如下形式的数学模型( n l p ) ： r a i nf ( x ) j t 吕( j ) 0 汪l ，2 ，川 ( 1 2 1 ) 蜀( x ) = 0i = m + l ，m + p 求解最优化问题( n l p ) ，就是要求目标函数f ( x ) 在约束条件下的极小点，即求 出其全局最优解，但在一般情况下，我们往往只能求出它的一个局部最优解。 当约束优化问题( 1 2 1 ) 只有一个或两个决策变量时，全局最优解及局部最优解 具有直观的几何意义。图1 2 1 给出了决策变量维数为一维时，约束优化问题的全 局及局部最优解的直观图示。 从图1 2 1 可以看出，工1 ，茗2 和x 3 均是局部最优解，而x 2 还是全局最优解。在 约束优化问题中，局部最优解不一定是全局最优解，而全局最优解一定为局部最 优解。 厂 图1 2 1 一元函数的全局及局部最优解图不 最优化问题的求解，通常用迭代算法 7 4 7 5 1 。常用的迭代算法的基本格式包含 以下两个主要步骤： 1 用某种方式确定当前点x k 处的迭代方向。 2 求出由出发沿方向d 。的一维线性搜索的步长吒，令晚+ 。= x k + q 以。 方向矾的不同选择与初始点是否可行构成不同的算法及其分类。 一般说束，非线性约束优化问题比起线性规划无论从理论还是到算法的研究 都要困难些【7 6 1 。不论何种情形，在讨论算法得到的点列 毛) 的收敛性及收敛速度 时，都放宽到求得问题的k k t 点。 我们称x r ”为问题( n l p ) 的一个k k t 点，如果x x 且存在向量( 五，) r 肿p 使下面的关系式成立： m所+ p 夥( x ) + 乃( 工) + “，小) = o ，五o ，2 i g i ( x ) = 0 ，i - - 1 ，m ； ，刮l j = m + l 4 求解约水优化问题的儿种智能算法 二求解非线性规划问题的经典方法及其弊端7 7 娟】 在数学模型建立以后，剩下的任务就是寻找一种优化这个模型的策略。最优化 问题可以通过许多策略来实现，包括从非常复杂的解析的和数值的数学方法到简 单算术的巧妙应用。目前常用的解决方法是解析法和数值澍8 7 1 。 1 解析法【8 8 曲2 】 解析法是利用微分学和变分法的经典方法，通过寻找使函数f ( x ) 对x 的导数 等于零的x 的值来求函数的极值。如果欲求函数在约束条件下的极值，那么就利用 拉格朗同乘子法及约束变分法。解析法要用到目标函数在当前迭代点的梯度值。 也就是说对于一个目标函数厂( 石) ，工s 在某一点的梯度值为： v f ( 加( 等，等，等) 我们要根据这个梯度的值决定下一次迭代的方向。当目标函数不可导或是不 连续时，解析法不能保证找到最优解。最为著名的解析法是牛顿法 ( n e w t o n r a p h s o n ) ，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲 线的极小点来近似原目标函数的极小点，并逐次逼近该点。 其迭代步骤如下【9 3 】： s t e p l 给定初始点x o ，允许误差占，令k = 0 ； s t e p2 计算盯( ) ， h ( x ) 】； s t e p3 检验是否满足0 w ( x 。) i b 占，若满足则停止迭代，否则进行步骤4 ； s t e p 4 令s = 1 日( ) - i v 厂( ，) ； s t e p5 令x “1 = x + s ，k = k - i - l 转s t e p2 ； 牛顿法的缺点是需要计算二阶偏倒数矩阵，特别是还需要求逆矩阵，计算较 繁，当目标函数的维数较高时，计算量和存储量都以n 2 比例增加，而且当h e s s i a n 矩阵h ( x ) 是奇异矩阵时，其逆矩阵 ( x ) 】- l 不存在，使得方法失效。这个方法的 另一个问题是，目标函数的最大值和最小值都满足迭代终止条件0 w ( z ) 忙g ，因 此，我们最后得到的结果有可能是最大值，也可能是最小值。 虽然牛顿法的改进算法d f p 变尺度法在函数f ( x ) 的梯度向量容易求出的情况 下是非常有效的，对于多维( 甩1 0 0 ) 问题，由于收敛快，效果也很好。但是计算程 序复杂，且需要较大的存贮量，在有舍入误差时，还存在数值稳定性不够理想的 情况。最重要的是，对于大多数问题，我们并不能很容易地求出其在一点的梯度 值。因此，对于非线性规划问题，解析法是不令人满意的，我们一般不用解析法 解决非线性规划问题。 第一章绪论 2 数值法 9 4 曲7 】 数值法利用已有的信息，通过迭代程序来产生最优化问题的最好解。数值法能 解决解析法所不能解决的问题，实际问题也证明容易用数值法处理，因而非线性 规划的数值法一直是现在解决这类问题的重要方法。目前己经提出了许多数值法， 如单纯形( ( s i m p l e x ) 【9 8 】法，h o o k e j e e v c s 方法【9 9 0 2 1 、改进的p o w e l l 方法【1 0 3 1 0 7 】等。 这些方法各有自己的特点，他们与解析法的区别在于不用计算函数的导数。我们 从改进的p o w e l l 法可以看出这个特征。p o w e l l 方法不需要对目标函数进行求导的 计算，但是每次迭代中仍然要产生一个下次搜索的共扼方向，对于一个行维问题， p o w e l l 的迭代计算过程如下： 每一轮的搜索都从前一轮最后求得的最优点出发，并沿n 个有序的线性独立方 向：s ? ，s ：k ，磊k ，进行一维搜索。第一轮搜索可由任意一点出发，取x o l = x o ， 而方向可取为k 个坐标轴的方向，即： = q = o ，1 ，0 ，0 1 r 式中第f 个单位坐标方向取1 ，其余为0 ，当然第一轮也可以任意取k 个线性独立 的方向组成方向组，第k 轮的迭代步骤如下： s t e p l 初始点取前一轮迭代最后猫5 川k - i 方向求得的最优点z ，然后由初始点 出发沿s ? 方向进行一维最优化搜索，使函数厂( 菇+ q s ： ) 为最小，求得a 。，并令 x ：= 菇+ 口：s ：。再由出发沿s ：方向使厂( 群+ 口：s ：) 最小，求得a ：，并令 = 彳+ 口：k j ：。如此依次沿每个方向进行一维搜索，直至求得全部的 a ? ( f _ l ，2 ，行) ，令# = j + 口，k j ? ； s t e p 2 取共扼方向：s ：+ 。= - 4 ，并计算反映点。= 2 一菇； s t e p 3 令彳= 厂( ) ；五= 厂( ) ；石= ( ：+ 。) = f ( 2 x k , 一菇) ； 其中：菇x k - i ，。k = k 一。+ 口：s ：= 式+ 口：； ，= i s t e p 4 计算第k 轮迭代各方向上目标函数下降值厂( 。) 一厂( # ) ( f = 1 ，2 ，咒) ， 并找出其中的最大值：，即：= h m a x ， f ( x ：_ t ) 一厂( # ) ，：相应的方向为： s ：= 一l ； s t e p 5 若以 z 且( z - 2 l + 六) z - l a 。k ( 石- a ) 2 o 5 ：( z - l ) 2 ，则转入下 一步，否则在第k + l 轮迭代中仍用第七轮迭代用的同一方向组，即 6 求解约束优化问题的儿种智能算法 “= 霉( 江l ，2 ，1 ) 。关于迭代初始点，当石 六时，取第k + l 轮迭代的初始点 x 0 ”= ，否则取菇“= + l ，然后转回第一步； s t e p 6 如果步骤5 中的两个不等式同时得到满足，则从出发沿s ：+ 。方向进行 一维最优搜索求得口，得+ 。方向的最优点为工= k + 口吱。； s t e p 7 取第k + l 轮迭代方向组为【i ，曼k + l ，k “】= 【，& k9 j o 斗+ ，k ，】。 也就是说，在新的方向组中去掉了原方向组中具有最大下降值的方向s ：，并将方 向+ 作为新方向组中的第n 个方向，即k ”= j 基。，初始点菇”= x ，然后转第一步； s t e p 8 每轮迭代结束时，都要按收敛条件进行检查。若满足收敛条件则迭代结 束，否则进行下一轮迭代。收敛条件为： 忖- g i - ( i = 1 ，2 ，刀) 或 岛。 p o w e l l 方法与牛顿方法相比，收敛速度较慢，但是适用的范围更加广泛。试 验证明，p o w e l l 方法在求解二次问题时，有很快的收敛性。但是p o w e l l 方法不适 应于维数大于2 0 的问题。 其他经典的数值方法大都和上述方法类以，就是从一点出发，根据一定的方 法产生到下一个点的方向和步长。这样经过多次迭代搜索后，找到一个最优的解。 虽然数值方法在过去的研究中得到了很大发展，有很多实际问题己经用这些方法 得到了解决，但是仍然有许多复杂的问题，传统的方法是无法解决的。 3 经典优化算法的弊端【1 0 8 1 1 7 】 我们知道求解非线性规划问题的最大困难在于目标函数通常存在许多局部最 优，也就是说我们通常会得到一个在局部区域内的最优解，而不是整个解空i 日j 上 的最优解。这种解仅仅只是满足函数导数的要求。我们可以想象在一个平面上有 许多突起的山峰，如果我们只沿着山峰的方向向上寻找是不可能从一个山峰到另 一个山峰的。传统的求解非线性规划的方法就存在这样的局限性，很容易陷入局 部最优。总的来一说传统方法存在以下的弊端： ( 1 ) 一般对目标函数都有较强的限制性要求，如连续、可微、单峰等； ( 2 ) 多数优化方法都是根据目标函数的局部展丌性质来确定下一步搜索的方向，这 与求函数的整体最优解的目标有一定的抵触； ( 3 ) 在实现算法之前，要进行大量的准备工作，如求函数的一阶和二阶导数，某些 矩阵的逆等。在目标函数较为复杂的情况下，这一工作是很困难的，有时甚至是 不可能的； 第一章绪论 ( 4 ) 算法结果一般与初始值的选取有较大关系，不同的初值可能导致不同的结果。 初始值的选取较大地依赖于优化者对问题背景的认识及所掌握的知识； ( 5 ) 算法缺乏简单性和通用性。针对一个问题，优化方法的使用者需要有相当的知 识去判定使用哪一种方法较为合适。这困难是使优化方法得到更为广泛应用的 主要障碍之一。因此，我们必需用全新的思路去求解非线性规划问题，才有可能 使非线性规划问题的求解得到较大的发展。 三处理约束优化问题的现代优化算法 l 启发式算法1 1 1 8 1 1 9 】 随着2 0 世纪8 0 年代初禁忌算、法【1 加12 4 1 、模拟退火算法【1 2 5 1 2 9 1 、进化算法【1 3 1 4 3 】 和人工神经网络【1 似1 4 8 】等算法的兴起，非线性规划问题又增添了些新的解决方 案。这些算法涉及生物进化、人工智能、数学和物理学、神经系统和统计力学等 概念，都是以一定的直观基础而构造的算法，我们称之为启发式算法( h e u r i s t i c a l g o r i t h m ) 。 启发式算法是相对于最优算法提出的，一个问题的最优算法求得该问题的最 优解，而启发式算法则可以认为是一种基于直观或经验构造的算法，在可以接受 的花费( 指计算时间、占用空间等) 下给出待解决优化问题的一个可行解，该可行解 与最优解的偏移程度不一定事先可以预计。在大部分的非线性规划问题中，最优 化算法的计算时间是无法忍受的，而且要想保证一定能找到最优解，我们很有可 能要用到穷举法，这显然是不实际的。启发式算法却可以在我们能接受的花费下 找到一个近似解。从工程实际的角度来看，在一定误差范围内的近似解都是可以 接受的。而且由于