（计算机应用技术专业论文）双参数精确罚函数非线性神经网络的研究.pdf

攘要 组合优化中的n p - h a r d 问题和非线性全局优化l 例题是优化研究中 的难赢。近年来，有许多入袋用模拟退火( s i m u l a t e da n n e a l i n g ) 、 遗传算法( g e n e t i ca l g o r i t h m s ) 察人工神经随络( a r t i f i c i a l n e u r a l n e t w o r k s ) 等启发式算法对这两类问题进行了研究，并取得了一定得 进展。但这些方法通常存在计算量大、收敛慢及参数敏感等不足。本 文主要讨论了东双参数精礁锈丞数下，魏篱将糖确钧函数纛毒枣经阚终 及遗传算法结合的系统应用于优化问题。 本文我们介绍了罚函数、神经网络和遗传算法的研究现状。通过 对双参数精确爨凝数的讨论，翻惩双参数精确毳丞数鳇性质，构造了 一种毒# 线性神经阙络，并讨论了该神经两络的稳定链阔题，提出了一 个求解这种神经网络的算法，给出了一魃算例。最厝，我们研究了使 用遗传算法求解这种神经瞬络阃题，我们提出一个求鳃神经网终阀题 鲶滋会遗黄算法，并给窭了数值诗篓缝聚。诗算绪祭表暖，繇撵逡的 方法魁有效。与单纯的遗传辣法求解t s p 问题相比，新的混合法在解 的收敛性上要更优。 本文的主要成果是：构造一个双参数精确露函数麓毒 线性糟经网 络模装，并提出了一个模拟求解算法，阏时还提蹬一个求解这种神经 网络问题的混合遗传算法。 本文对于非线性神经网络的理论及组合优化求解具有重要的理论 意义。 关键词：双_ 参数精确罚函数神经网络遄传算法 a b s t r a c t 1 1 1 en p - h a r d p r o b l e m sa n d t h eg l o b a lo p t i m i z a t i o np r o b l e m sa r ct w o c a t e g o r i e so f t h em o s tc h a l l e n g e ds u b j e c t si nm a t h e m a t i c a lp r o g r a m m i n g r e c e n t l y , s o m eh e u r i s t i cf l g o f i t h r a s ，s u c h a ss i m u l a t e da n n e a l i n g ( s a ) ， g e n e t i ca l g o r i t h m s a n d a r t i f i c i a ln e u r a l n e t w o r k s ( a n n ) ，a r e e m p l o y e dt ot h e s e d i f f i c u l tp r o b l e m sa n dm a n yo fp r o m i s i n gr e s u l ta r e o b t a i n e d h o w e v e r , t h e a m o u n to f c a l c u l a t i o n , t h es p e e do f t h ec o n v e r g e n c e a n dt h es e n s i t i v i t yo f p a r a m e t e r so f t h e s ea l g o r i t h m sa r el e s se n c o u r a g e d i n t h e p r e s e n tp a p e r , w ei n v e s t i g a t e d h o wt o a p p l y t h ea r t i f i c i a ln e u r a l n e t w o r k sa n dg e n e t i ca l g o r i t h mt ot h eo p t i m i z a t i o np r o b l e m sw i t he x a c t p e n a l t y f u n c t i o nw i t h t w o - p a r a m e t e r w ei n t r o d u c e dt h er e s e a r c hc o n d i t i o no ft h ep e n a l t yf u n c t i o n , n e u r a l n e t w o r ka n dt h eg e n e t i ca l g o r i t h m p a s st ot h ed i s c u s s i o no ft h ee x a c t p e n a l t yf u n c t i o nw i t ht w od a r a m e t e r , m a k e u s eo f t h e p r o p e r t yo f t h ee x a c t p e n a l t yf u n c t i o nw i t ht w o 脚e t e l , c o n s l n l c t ak i n do fn o n l i n e a rn e r v e n e t w o r k , d i s c u s s e dt h es t a b i l i t yo fn e u r a ln e t w o r k , s u b m i ta na l g o r i t h mt o g e ts o l u t i o no ft h i sk i n do fn e u r a ln e t w o r k s ，a n dg i v es o m ee x a m p l e s f i n a l l y ，w ei n v e s t i g a t e d h o wt o a p p l y t h e g e n e t i ca l g o r i t h m t ot h e o p t i m i z a t i o np r o b l e m sw i t he x a c tp e n a l t y f u n c t i o nw i t h t w o - p a r a m e t e r w e s u b m i tag e n e t i ca l g o r i t h mo fm i xf o rs o l v i n gn e u r a ln e t w o r k , a n dg i v e s o m en u m e r i c a lc o m p u t a t i o n s t h ec o m p u t a t i o nr e s u l te x p r e s s e st h a ti ti s a v a i l a b i l i t y c o m p a r et ot h ep u r eg e n e t i ca l g o r i t h mt os o l v et h et s p ，t h e n e wm i x e dm e t h o di sm o r ee x c e l l e n ti nt h ea s t r i n g e n c yo f s o l v e m a i nf i a l i ti s ：b u i l d i n gam o d e lo f n o n l i n e a rn e u r a ln e t w o r kw i t he x a c t p e n a l t yf u n c t i o n w i t ht w o p a r a m e t e r s ，b f i n l n gf o r w a r da s i m u l a t ea l g o r i t h m t og e tt h es o l u t i o n , c o n t e m p o r a r yp u tf o r w a r dag e n e t i ca l g o r i t h mo fm i x f o rs o l v i n gn e u r a ln e t w o r k t l i st e x th a st h ei m p o r t a n t t h e o r ym e a n i n g f o rt h et h e o r yo f n o n l i n e a r n e t w o r ke n ds o l v e st h ec o m b i n a t o r i a lo p t i m i z a t i o n k e y w o r d s ：e x a c t p e n a l t y f u n c t i o nw i t h t w o - p a r a m e t e r g e n e f i c a l g o r i t h m s n e u r a ln e t w o r k s 湘津大学硕士学位论文w 第一章绪论 本章介绍了非线性优化有关的概念、技术和研究现状，论述了 非线性优化的研究背景和起源，总结了黼人在此领域所取得的成果， 探讨? 在双参数婧礁器函数审结合神经鼹络毒遗铸算法如留避蠢拓 展和成用。最后介绍了本文詹面研究的内容。 1 1 弓l 言 罚函数方法是解决约柬优化问题的主要工具，它将约柬优化 问题转化为一系列无约束优化问题求解，通过求解无约束优化问 瑟潋褥到爨滔题豹解。这群使褥求解变遗篱单，巍竣甏函数方法 在解决约束优化闯题时具有重要的作用。自1 9 4 9 年c o u r a n 首先 提出外部罚函数算法啦，到现在为止人们已经研究了许多形式的 罚函数方法n 州”。罚函数法戆主要研究内容是；骧闯题对发的霹 饶纯阏题的最侥解在什么条件下是原润鼷的最优解。在罚函数囊际计 算中，往往需要求解多个罚优化问题才舷获得原问题的解，这样大大 的增加了计算工作量，1 9 6 7 年z a n g h i l l 提出了一个精确罚函数口1 ， 园秀耩确毳丞鼗楚求鼹对应酶一令翥隈麓蓑参数对癍豹器饶绽溜运 的最优解，就可以获得原问题的最优解。这样大大地减少了计算工 作量，所以精确罚函数在解决约束优化问题具有重臻的作用。 髑字孛经网络求鳃菲线形规划闯题的典型的是h o p f i e l d 裤经网络 ( 联螨) ，它是嚣蒋研究褥较充分并褥戮广泛应羽的神经圈络模壅之 一。h o p f i e l d 神经网络模型是美国加州理工学院物理学家h o p f i e l d 教授予1 9 8 2 年提出来的。1 9 8 5 年h o p f i e l d 与d w t a n k 一道用模 拟电予线路实现th o p f i e l d 鹅，著罨它成功翡探讨了其嘉n p c 复杂 性的旅行商问题( t s p ) 的求解方法。当年正是因为h o p f i e l d 网络 求解了这个具有相当难度的组合优化问题，才使神经网络重新被重 视起来，对享孛经瓣络研究憋复苏起了里程碡式的露耀。神经网络在 解决优化随题时，首先我稍必须把要求瓣的目题映射到神经潮络上 塑璺查兰堡主兰垡丝苎：! ： 来。 遗传算法( ga ) 遗传算法( ga ) 是一种人工智能方法，它的机 理基于达尔文的生物进化论的适者生存原理，模拟生物进化的步骤， 将繁殖、杂交、变异、竞争和选择等概念引入到算法中。通过维持 一组可行解，并通过对可行解的重新组合，改进可行解在多维空间内 的移动轨迹或趋向，最终走向最优解。它克服了传统优化方法容易陷 入局部极值的缺点，是一种全局优化算法。 罚函数方法、神经网络、遗传算法都是用来解决优化的工具， 他们之间存在某种联系，人们发现利用罚函数可以构造非线性神经 网络，用于解决优化问题，而罚函数不一定是可微的，我们可以利 用遗传算法来求解问题。由此，我们希望寻找新的罚函数来构造新 的人工神经网络，来解决优化问题作为我们的研究课题。本文将研 究一种新的罚函数来构造一种非线性神经网络问题，并用于解决含 约束的优化问题。 1 2 罚函数研究现状 罚函数方法是解决非线性规划的一个非常有效的方法，也是发 展最快和应用最多的一种方法。它解决最优化问题的办法是寻找一 个容易求解的替代问题，而这个替代问题的解正好是原问题的解。 1 9 4 9 年c o u r a n 首先提出外部罚函数算法，有效地将带有约束的非线 性规划问题转化称无约束规划问题。对非线性规划问题： 0 叻m 八x ) s 1 吕0 i = l z ，鸣 吩( 功- - 0 , ，= 1 ，z ，孕 其外部罚函数定义为： _一卢 p ( x ) = m 强 o ，岛( x ) 4 + 2 1 h , 0 。对应的罚优化问题( f p ) 为： 湘潭大学硕士学位论文- 3 - n f m _ ，( x ) + p p ( x ) s x 孵“ 其中p 是罚参数。可以证明在一定的条件下，当罚参数增大到无 限大时，罚优化问题的最优解也是原问题( n p ) 的最优解。这样当我 们不断的增加罚参数时，我们需要求解一系列罚优化问题，得到一 个近似最优解，但受到精度影响，罚参数不可能无限增大。 1 9 5 5 年f r i s h 和1 9 5 9 年c a r r o l l 发展了内部罚函数。考虑非线 性规划问题： ( 聊 r a i n f ( x ) j j g f ( x ) 0 ，f = 1 , 2 ，m 注意到任何_ 一个问题0 巾) 都可以转化成问题( p ) 的形式。其内部 罚函数曰( z ) ：蓑l o g b ) i 对应的罚优化问题( f p ) 为： m i n 八力+ t 联x ) s j x 孵“ 其中，是罚参数，可以证明在一定条件下，当罚参数，趋向0 时， 罚优化问题的最优解也是原问题( p ) 的最优解。 还有其他形式的内部罚函数，如口= 一喜( 砷， 刀( x ) = 喜名。：等。上面的外部罚函数p ( x ) 和内部罚函数b ( x ) 并不 是精确罚函数，1 9 6 7 年z a n g h i l l 提出了一个精确罚函数 3 1 ： p ( x ，p ) = ，( 工) + p m x o ，蜀( 曲 在一定条件下，存在一个值声使得当p 万时对应的罚优化问题 的最优解都是原问题的最优解。这样我们可能只需求解一个罚优化 问题就可以得到原问题的最优解。因此，精确罚函数成为人们解决 塑翌盔堂堡圭兰垒堕苎：! ： 约束非线性规划的重要方法，并开展了许多研究，如1 9 7 9 年h a n 和 m a n g a s r i a n 讨论了精确罚函数，1 9 8 1 年r o s e n b e r g h e 哺1 和 l a s s e r r e 呻1 分别给出了一个精确罚函数的全局收敛算法，1 9 8 2 年 c l a r k e 在文 9 中讨论了精确罚函数的镇定性和稳定性条件，1 9 8 4 年r o s e n b e r g 也在文 1 0 中讨论了精确罚函数的镇定性和稳定性， 其中镇定性和稳定性是判断精确性的充分必要条件，但对于复杂问 题无法验证。d i p p i l l o 和g r i p p o 在文 7 8 中研究了精确罚函数的 算法。1 9 9 5 年m o n g e a u 和s a r t e n a e r 在文 1 1 中对精确罚函数的罚 参数自动减小问题进行了研究，1 9 9 0 年k o r n e r 和f r a n k 研究二次规 划的精确罚函数的数值解法m “，1 9 8 6 年b e n t a l 和t e b o u l l e 讨论了 随机规划的罚函数问题d ”，1 9 9 5 年韦增欣研究了一族精确罚函 数的存在性及控制参数的下界嘶1 ，1 9 9 6 年林亮讨论了一种精确罚函 数的存在性啪1 ，王万量在文 3 7 中研究了l 1 精确罚函数的存在性， 杨波艇和张可村研究了用l 1 一罚函数作线性搜索函数的一种修正约 束变尺度算法口”，刘昌文讨论了二次规划的精确罚函数法，1 9 9 7 年张连生给出了全局精确罚函数的一个充要条件h ”。文献 2 6 2 7 、 3 0 对各种序列罚函数技术进行了详细论述。 1 3 神经网络与遗传算法研究现状 神经网络是解决大规模优化问题的一种有效方法，h o p f i e l d 和 t a n k 首先提出了提出一种神经网络来解决线性规划问题。在1 9 8 5 年 h o p f i e l d 与d w t a n k 一道用模拟电子线路实现了h o p f i e l d 网，并用 它成功的探讨了具有n p c 复杂性的旅行商问题( t s p ) 的求解方法。 神经网络的设计就是根据一定的法则，合适的选择网络结构，线性 和非线性函数及其权值，使得特定的目标函数达到最小。他们的工 作吸引了更多的人去进一步研究h o p f i e l d - t a n k 模型( h t m ) 神经网 络在优化计算方面的能力。 文献 4 3 4 6 介绍了国外的一些研究进展，在国内近几年的研究 中，主要有中国科学院数学与系统科学研究院应用数学研究所章祥 塑整盔兰堡主兰堡熊兰： ! ： 荪分别在1 9 9 2 筇及1 9 9 5 年和朱会灿，1 9 9 5 年和谭德俊讨论了神经 阙终与优化计算秘“鹎，1 9 9 7 年王磊和章祥荪进行了祷l 经麓络t s p 静 比较研究拍“。1 9 9 8 侯增广和畏沧浦研究了一类非线性大系统递阶优 化的神经网络方法暗”。1 9 9 9 司昕和安擞南提出了类优化计算的神 经隧络模型疆封。1 9 9 9 彭宏翻侯进军提逝了棒经隧终酶一静新的缝合 优化算法潮。1 9 9 9 陈建明和张仲义用神经网络在优化计算中进行了 一些臌用哪。2 0 0 2 余新新进行了神经网络模型优化问题的研究及其 应用。2 0 0 2 李有梅和王梦云讨论了离数神经瞬终的优化熊力嘲。 逮簧算法憝模叛自然器生物进化避程的专 算模鍪，宅魏恐想源 予生物遗传学和适者生存的自然规律，是具有“生存+ 检测”的迭代 过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用 随规化技术指导对一令被编码麓参数窆润进行煮效搜索。箕孛，选 择、交叉和交彝构成了遗转算法的遗传攥作；参数编码、初始群体的 设定、适应度函数的设计、遗传操作设计、控制参数，设定5 个要素 组成了遗传算法的核心内容。它体现了自然界中“物竞天择、适者 生存”遗像过程，从瑟啜雩 t 大戴戆研究者，迅速接广至饶纯、搜索、 机器学习等方面，并奠定了氅实的理论基础。旅行商问题是一个典型 的组念优化问题，并且是一个np 难题，其可能的路径数目与城市数 基n 怒成指数受增长鳇，蹶苏一般缎难精确建求密箕最往解，黢嚣寻 找出有效的近似求解算法就有着重要的理论意义。另一方面锻多实 际应用问题，如印制电路板的钻孔路线方案、连锁店的货物配送路线 等，经过简化处理后，均可建模为旅行商闳题，因而基于遗传算法的 旅行裔润惩求瓣方法鑫馨磺究爨寿重要的藏焉价值。 和传统的优化方法相比，遗传算法具有下述特点。 1 ) 遗传算法不是直接处理设计变景本身，而是设计变量的代码， 这些代码逶零用二进制数码表忝。也霹熙其它夔方法进辱编码，襞鳃， 本文在处理旅行商闯题时根据其特点便用自然数进行编码。这些被 编码的设计变量称为位串，俄串中的每个字符相当于一个基因，由多 个位串构成个体位串，他代表人造的染色体。 2 ) 遗黄算法不是锌对每令变量露戳率进行寻傀，两是针对诲多 位串构成的个体位串即方案进行寻优，这意味着遗传算法可以同时 湘潭大学硕士学位论义， 6 - 处理多个方案。 3 ) 遗抟算法是剩震随概操缀基因睇遗传算子实现信息交换，控 制搜索过程，因此，对遗传算予的研究已成为人们关注的焦点。 图外有g r e f e r 蟮t e t t e ，g o l d b e r g ，d a v i de d w a v a 等人对遗传算法结 梅貔纯麴研究疆删，b i l l i n gs 鑫，z h e n ggl d 对垒犀纯往毒搴经网络 拓扑结构遗传算法的分析渊，m a n i f z z 0v 对权值的研究嘲。禚国内 近几年在遗传算法和优化计算的结合研究中，主要有1 9 9 9 张敏、赵 金城提出全局优化神经嚼络拓扑结构及权值的遗传算法陆“。1 9 9 9 陈 静超、陆金鞋察寒彳鑫兴挺爨遗传算法和枣枣经隧络豹结构优纯策略潮。 1 9 9 9 周兆凯和周毓菁提出一类遗传算法一优化设计一神经网络的耦合 技术旧1 。1 9 9 9 卢洵进行了基于遗传算法的神经网络优化的研究。 1 9 9 9 嶷辉、赵荚凯鞠丁瑶裁进行了基予榜经溺终戆遗传算法傀纯及 其应用嘲。2 0 0 1 正凤琴、高颗和赵军掇出基于遗传算法的神缀网络 优化。 1 4 本文研究内容 弓i 进了一种新的双参数罚函数，它相传统的罚函数不同是多了 一个豳标罚参数，在一定条件下，这种罚函数具有精确性和可微性 等爨好鹃往痰，纛诧它可震予 鸯造薪的入工神经潮络。 为此，本文将对双参数精确罚函数构造的神经网络进行研究并 结合遗传算法进行计算，研究主要集中在以下几个方面： 1 论述了羁爨数、搴枣经睡络翻遗传算法豹研究褒获。 2 ) 讨论了双参数精确罚函数的一种模型。 3 ) 研究了双参数精确罚函数的神经网络构造殿求解算法。 4 ) 研究了一个遗传算法求解构造的神经网终方法。 下面介绍本文以后各章节的安排： 第2 章给出了一个双参数精确罚函数模型，并针对模型性质， 分析了一个双参数弱函数例子，对精确援定理，双参数糖确爨函数 算法等问题进行了讨论。 塑翌奎兰堡主堂垡堡兰：! ： 第3 章主要研究了双参数精确罚函数反馈神经网络模型，给出 了网络参数、罚因子及网络结构的设计，稳定性分析，并提出了一 个算法及进行了实例计算。 第4 章讨论了遗传算法的基本原理，并提出了一个算法及进行 了实例计算。 接下来，我们将本文所做的一些工作进行了总结，并展望了未 来的工作。 最后是参考文献、攻读硕士期间公开发表的论文、参加的科研 项目及致谢。 湘潭大学硕士学位论文- 第二章双参数精确罚函数模型构造 给出了一个双参数精确罚函数模型，并针对模型性质，分析了 一个双参数罚函数例子，对精确罚定理，双参数精确罚函数算法等 问题进行了讨论。 2 1 糯_ 确罚函数模型 罚函数方法是解决约束优化问题的主要工具，它解决最优化问 题的办法是寻找一个容易求解的替代问题，而这个替代问题的解正 好是原问题的解。这样使得求解变得简单，所以罚函数方法在解决 约束优化问题时具有重要的作用。它可以有效地将带有约束的非线 性规划问题转化为无约束规划问题。 对非线性规划问题： ( p )r a i n ，( x ) s j ( 0 ，i = 1 , 2 ，m 精确罚函数为： 三 p ( x ，力= ，( 功+ p m a x o ，g a x ) 在一定条件下，存在一个值万使得当p 芦时对应的罚优化问题 的最优解都是原问题的最优解。这样我们可能只需求解一个罚优化 问题就可以得到原问题的最优解。 精确罚函数的概念如下：精确罚函数满足的条件是，对于某个 罚参数对应p 的无约束罚优化问题的最优解也是原问题的最优解。 由于精确罚函数p ( x ，p ) 是非光滑函数，所以，它的应用受到了许多 限制。下面我研究一种新的罚函数形式。 2 2 双参擞精确罚函数模型 对于函数q ：r _ r u 柚) 和p ：r r u 删各自满足 湘潭大学硕士学位论文 9 - q ( t 1 = 0 仅当f = o q 0 ) o 当t 豫 q ( t 1 _ 佃 当t 斗佃 0 对于给定的p 和q ，定义下面的双参数罚函数： f ( x ，p ，m ) = 烈五一m ) + p p ( z ) 酊 当罚参数p o 和目标参数m e 婀，如果鳓) ，p ( f ) ，f ( x ) ( i e i o ) 是 可导的，则显然易见f ( x ，p ，m ) 也是可导的，例如，我们令q o ) = r 2 ， p ( f ) = m a x t ，o ) 4 ，我们得到下面的罚函数， f ( x ，p ，m ) = ( 二o ) 一肘) 2 + 尸4 i f , 当z + ( x ) = m a x ( o ，z ( ) ，f e j 对所有的f 厶，如果z 是一维开导的， 则4 也是一维开导的，如果z 是二维开导的，则z + 4 也是二维 开导的，同理可以推 塑至l j f ( x , p ，m ) 。 2 3 双参教精确罚函数模型性质 传统的单参数精确罚函数满足的条件是，对于某个罚参数p 对应 的无约束罚优化问题的最优解也是原问题的最优解。 这里我们给出双参数罚函数的精确性概念，对于给定的罚参数 m 和p ，如果r 是罚问题( p ( p ，膨) 的最优解，那么x 也是问题( p ) 的 最优解，则称f ( x ，p ，m ) 是关于( 肘：p 的精确罚函数，m 和p 是精确 罚参数。 显然，双参数精确罚的概念是单参数精确罚概念的推广。如果 塑星奎堂缝主兰垒i 坚： ! ! ： 我们能够找到双精确罚参数，那么，我们只要求解对应的一个无约 束罚优化阏题的最优髂就可以得到原闻蘧懿最优解。 我们讨论有关双参数精确羁添数盼凡令定理。 定理2 3 1 如果r 是问题( p ) 的最优解，且m = 五( 并+ ) ，则对予侄 褒p o ，是舞霆逶联岛掰羚的最优解，豆f 缸，岛掰) = 0 。 证嘲因为x + 是问题( p ) 的最优解，m = 矗f ) ，那么f ( x ，岛掰) ；0 。 而对于任何善e 9 t ”，我们有f “胁m ) 0 。所以，x + 是罚问题( p ( a 吖) ) 鲸最优解。 定理2 2 。1 说骥，当x + 是瓣题( p ) 的最优解和m = 五f ) ，那么任 何罚参数p 对应的无约束罚优化问题的最优解并：一定使得 f ( x ，岛肘) 一，辑，岛五( r ) ) = o ，石蝣) = 五o ) ，且是问题( p ) 的可行解， 因瑟迄蹩润遂( p ) 酶最佬解，那么羁丞数f 瓴岛材) 是耱礁魏。我稍 有下面翼好的结果。 定理2 。3 2 设矿是闯题( p ) 的最优解，对菜令p o 和挺，x ：是镄 滴蘧妒溉掰羚的最优鳃显是阔愁( p ) 的可行解，并f t 猕壕q ， 如果m 一m 五( 蠢) 一f o ) 0 缓设存在x e x 镶得磊一掰o ，那么我们有f o ( x ) m o 和m ，设是罚问题 ( p ( p ，m ) ) 的最优解，则 ( i ) 若c 是问题( p ) 的可行解且f ( x ，p ，m ) = 0 ，则ms m s m 。 ( i i ) 若f ( x * j a m ) o ，并且m 肘。，则m 。进而，如果是 问题( p ) 的可行解，则x ：是问题( p ) 的最优解。 证明( i ) 结论显然成立。 ( i i ) 如果m 茎盯，那么ms 肘s m ，因为五是连通紧集x 上的 连续函数， 由引理2 3 1 知，存在而e x 使得m = f o ( x o ) 。从而 f ( x o ，p ，m ) = 0 。但是，因为是罚问题妒( 岛肘) ) 的最优解且 f ( x o ，p ，m ) 0 ，故0 f ( ，a m ) f ( x o ，肛m ) = o ，这是一个矛盾。因此 我们有从。进而，如果x ：是问题( p ) 的可行解，根据定理2 3 2 知x ：是问题( p ) 的最优解。 例2 3 1 求解下面问题： 口2 3 1 ) r a i n 砰+ 霹 s j 一西s o ，一屯茎0 问题p 2 3 1 的最优解是g ，葛) = ( o ，o ) ，对应的最优目标值是0 。定 义下面的罚函数： 湘潭大学硕士学位论文- 1 2 f ( x ，p ，m ) = ( 砰+ 一m ) 2 + p ( m a x 0 ，一而) 4 + m a x o ，恐) 4 ) 为了使得罚优化问题( p ( b 吖) ) 得到最优解，求f ( x ，p ，m ) 的偏导数 为零： 罢：4 而暖+ # 一m ) 一4 p m a x o ，_ ) ，：o ， 昙：4 屯( 砰+ 霹一m ) - 4 p m a x o ，屯) 3 ：o o a 2 得解而= o , x 2 = 0 。然后再求f k b 肘) 在( 西，而) = ( o ，o ) 的h e s s e 矩 阵， 护fa 2 f e 3 2 x = 挑织 a 2 fa 2 f 两a ba 2 而 r - 4 m0 、 2 i o- 4 m j 当m o ，根据定理2 3 2 知f 似户，m ) 是关于( n 膨) 的精确罚函数。 2 4 双参数精确罚函数算法 根据定理2 3 3 ，我们给出一个求解问题( p ) 全局最优解的一个 算法。尽管已经证明双参数罚函数在一定条件下是精确的，但我们 并不知到精确罚参数的具体值是多少，所以与已有传统精确罚函数 算法一样。我们的算法思想仍然是通过求解序列无约束双参数罚函 数来获得原问题的解，不同的是通过改变目标罚参数m 进行求解， 最后算法的收敛性证明需要用到精确罚定理2 3 3 ，所以我们把下 面的算法称为双参数精确罚算法( t w o - p a r a m e t e re x a c tp e n a l t y a l g o r i t h m ) 。 湘潭大学硕士学位论文- 1 3 - 算法2 1 ( 双参数精确罚函数算法) s t e p l ：给定p x ，s o ，p 0 ，令k = 1 ，一个充分小的q 使得 a i o t ，算法的终止条件收敛很快。总之，算法2 1 的收敛速度 的快慢主要由s t e p 2 求解无约束罚优化问题的子算法选取决定。 下面的所有例子在使用m a t l a b 程序调用优化函数时，其中变量 需要加下界和上界值。因此，下面例子中变量如果本身是有解的约 束，那么这些约束并没有写在罚函数中，并不影响问题的求解。 例2 4 1 ( p 2 4 1 ) r a i n ， ) = 1 0 0 0 一# 一2 4 一一五屯一 毛 j j g l ( 功= + + 一2 5 = 0 9 2 ( x ) = ( 玉一5 ) 2 + 霹+ 一2 5 = o 9 3 0 ) = ( 毛一5 ) 2 + ( 恐- 5 ) 2 + ( 而一5 ) 2 - 2 5 0 所用罚函数为： f ( x ，b m ) = ( ，( 功一m ) 2 + p o l n a ) 【 o ) ，o ) ”+ m a x 一蜀( ，o 1 2 + m a x 9 2 ( x ) ，o ) ”+ m a x - 9 2 ( x ) ，o ) 12 + m a x g r x ) ，o ) “) 取 五= f i x , ，而，而) i o 蔓薯 1 0 0 , i = 1 ，2 ，3 ) 。 取p = 1 0 0 0 ， x o = ( 2 5 ，2 5 0 0 0 ，3 5 3 5 5 ) z ，a l = - 9 5 3 6 6 1 2 ，岛= 9 5 3 6 6 1 2 ，m = o 在迭 代数k = 8 时，得一个近似最优解一= ( 2 5 0 0 0 0 0 ，4 2 2 2 0 0 7 , 0 9 6 1 5 8 9 ) 和目 标值f ( x 8 ) = 9 4 4 2 1 5 6 6 3 。尽管我们已经证明算法2 1 的收敛性与罚参 数p 无关，但由于计算精度影响，罚参数值p 仍然对算法2 1 的收敛 性有影响，如果取了不合适的罚参数值p ，我们可能得到的近似解比 较差对于取不同的罚参数值，当迭代步数k = 8 时，我们得到下面 计算结果 湘潭大学硕士学位论文1 5 - 表2 4 1 旦璺f 12 鱼! 芏! 鱼! ! ! ! ! 1 2生f 芷!丝 吨硼- 0 in o a o om7 90n 1 7 吨42 l b n7 a 9 3 t e )9 4 59 4 3 1 5 19 t2 1 0 6 8 7 i o- 0 0 0 0 0 c n- 3 n 0 0 0 0 0n n o c a 0 0 0n5 m37 3 m 1 4 a , 21 & q 2 3 7 ) 9 4 s 2 0 9 b i l2 1 0 e 7 1 0 0- f t n0 0 0 0 0 0no g 0 0 0 0n o o a o 衄 2e , c 啪e o 4 嚣5 t n 9 姗0 t2 1 6 t 2 9 9 4 6 2 1 0 6 8 7 i 啪- 0 加- 0 o o o e o on o o o o o oo d o 05 0 0 0 0 0 42 2 2 0 0 7 n 1 6 a 9 ) 9 4 42 1 5 6 4 5 3 “2 1 0 b w t h t 肿 【；5 0 0 u o u , z z l 罚q n 蛳删9 4 42 1 5 7 9 3 9i 拍e * 由表2 4 3 ，当p = 1 或p = 1 0 ，获得的近似解并不好，因此为了 求到更好的近似解，在实际计算中，我们需要取一些不同的罚参数 值p ，直到求得最好的近似解。 如果取非线性罚函数为 f ( x ，岛m ) = 5 0 1 7 寸“7 + p ( m a x g l ，o ) 1 2 + m 积 嘀( x ) ，o 产 + m 缸 9 2 ( 功，o ) ”+ m a x - - 9 2 ( x ) ，o ) ”+ m a x 9 3 ( x ) ，o ) 1 。2 ) 那么， 对于取p = 1 0 0 0 ，x o = ( 2 5 ，2 5 0 0 0 ，3 5 3 5 5 ) e x ， 嘎= - 9 5 3 6 6 11 6 5 2 ，岛= 9 5 3 6 6 1 2 ，m = 4 2 9 1 4 7 5 2 4 4 我们只要迭代k = 4 步，就得到解一- - ( 2 5 ，4 2 6 5 1 4 2 ，0 7 4 7 3 7 ) 和厂) = 9 4 4 2 7 7 2 8 1 。这个结果 一4 要比已有的结果更好。 例2 4 2 ( p 2 4 2 ) r a i n ，( x ) = l o o x i + 1 2 0 x 2 + 9 0 x 3 + 8 0 x 4 + 7 0 x s + 1 4 0 x + + 4 0 x 7 + 2 0 x a + 3 0 x 9 + 2 0 x l o + 4 0 x 1 1 + l o x l 2 s 1 蜀( = 毛+ 而+ 而一2 5 = o 9 2 ( x ) = 矗+ 黾+ 咤一1 5 = 0 g ， ) = 五+ x 4 2 0 = 0 9 4 ) = 而+ x s 一1 0 = 0 9 5 ( x ) = 毛+ x 6 1 0 = 0 9 6 ( x ) = x 7 + 黾+ 而一5 0 = 0 湘潭大学硕士学位论文- 岛( 舅) = 毛。+ 苓 + 鼍2 3 0 = 0 醌( x ) = 而+ x j o 一2 0 = 0 岛( 砖= 而+ x a l 一4 0 = 0 岛o ( 茹) = 焉+ 鹚2 2 0 = 0 g l l ( x ) = x a + x 7 3 0 s 0 9 1 2 并) = 而+ x 9 3 0 s 0 0 7 5 ，i ；l ，1 2 获矮毳鍪数菇： f ( x , p ，材) = ( ，( 力一射) 2 + p c 蜀( 2 + m a x g l l ( ，o 2 + m a x 9 1 2 ( ，o 2 ) f - l 在使焉m a t l a b 绽程隧，变量麓赛o 玉 7 5 f f = 1 ，。，1 2 ) ，不笺在爱 函数中。 设p = 3 0 0 0 ，x o = ( 1 5 ，5 ，5 ，5 ，5 ，5 ，1 0 , 3 0 , 1 0 ，1 0 , 1 0 ，1 0 ) 芒x ，q = 一3 0 0 0 0 ， 连- - - 6 0 0 0 ，鳆= 一1 8 0 0 0 。巍迭代裂k = 2 2 时， | 譬到最饶解 x 2 2 一 o 。那 么 f ( x , p ， ，) = ( 五( x ) 一j i ，) 2 + p z , + ( 砷2 i l l 是双参数罚函数一种最简单的一种形式之一，那么对于这种形 式，除了本章获得的结果，我们将会得到比本章研究更多的结果。 详细结果见文 1 。 湘潭大学礤士学位论文， 第墨章菲线性人工神经网络 本章介绍了非线性h o p f i e l 矗人工神经网络有关的概念和技术。 建立了一个双参数精磺羲函数反馈砖经跨嗡模型，讨论了网络参数、 罚霹子茨辩络结构的设计及稳定性分析，并给出数值结暴。 3 。1 h o p f i e l d 型神经网络 神经网络是鳃决火规模优化问题的一种有效方法，h o p f i e l d 和 t a n k 首先提出了提出一种神经网络来解决线性规划问题。1 9 8 6 年美 国物理学家j 。3 h o p f i e l d 陆续发表咒篱论文，提塞了h o p f i e l d 勰l 经网络。德利孀菲线性动力学系统理论中的能量函数方法研究反馈 人工神经阿络的稳定性，并利用此方法建咸求解优化计算问题的系 统方程式。基本的h o p f i e l d 神经鼹络是一个瞧非线性元件构成的企 连接囊攀豢反馈系统势焉它成功懿探讨了荚宥n p c 复鸯 往的旅行窿 问题( t s p ) 的求解方法。神经网络的设计就是根据一定的法则，合 适的选择网络结构，线性和非线性函数及权值，使得特定的目标黼 数达到最小。 在类似盼神经网络的构造巾，闯题的难点在子能鬣黼数的构造。 使得构造出来的神经湖络是稳定的。h o p f i e l d 神经网络是一个反馈 型的网络。其状态变化可以用蓑分方程来表征。反馈型网络豹一个 重要特熹就是它具存稳定状态。当薅络达戮稳定状态的时候，也藏 是它的熊爨函数达到最小的时候。这里的能星函数不是物理意义上 的能量函数，而是在寝达形式上与物理意义上的能量概念一致，袭 征匪络状态的变纯趋势，著可戳俊据h o p f i e l d 工终运行筑则不断进 行状态变化，最终熊够达到的巢个极小值的潜标函数。网络收敛就 是指能量黼数达到极小值。如聚把一个最优化问题的目标函数转换 成网络的能量函数，搬阅题的变爨对应予网络的状态，那么h o p f i e l d 神经露终麟簏够震予解决貔纯组会阕遥。 塑壅茎登跫圭堂垡笙茎：! ! ： h o p f i e l d 神经网络的能量黼数是朝着梯度减小的方向变化，但 它仍然存在一个阕题，那就是星能量函数陷入到局部极小篷，它 将不麓窝渤跳出局部极小点，到达全局最小点，因露笼法求得网络 最优解。 神经网络在解决优化问题时，首先我们必须把要求解的问题映 射燮神经耀络主寒。一般麓步骤凳： ( 1 ) 选择一种含适的问题表示方式，使神经元的输出和问题的 解彼此相对应； ( 2 ) 构造一种能爨函数，使褥最小值对照予勰题的最优解； ( 3 ) e l l 能量函数推导出连接权值m o - ； ( 4 ) 导出运动轨迹方程；