（管理科学与工程专业论文）基于混沌神经网络的组合优化问题研究.pdf

中文摘要 嫩优化技术是现代科学镑理方法的一项基本技术 为满足现代镑理中求解 大蕊模复杂後纯问题的需求 迫切需要开发磁更加有效的优化技术 八十年代 中 h o p f i e l d 网络被成功应用于组含优化问题求解厝 成为解决优化问题的一 种有力的工爨 然瑟 该方法的一个明显缺陷是往往廷能褥到优纯润题的妫部 极值 而非全局最优解 因此本文采用近年米掀起的混沌神经网络求解组合优 位嗣戆静垒筠最优解 建立适合予各释大裁禳复杂缀合优纯闯题求解的混淹神 经网络算法 从而为复杂组合优化问题的求解提供一种新的方法和手段 本文曹笼对瑗毒瓣各耱羧凌纯接拳进行了分橱警评述 分褥了入工神缀网 络优化技术的研究成果与进展 介绍了人工神经网络优化技术的理论基础殿其 稳定馕 揍爨了混涟李孛经礴络圣戆证技笨懿簪 究遴震耧存在豹 薅逶与爨羧 第二 比较系统地介绍和分析了混沌神经网络解优化问题时的渐近稳定性 及其全局最饯援索 力 戈聪续各章基于漫滤糖经鼷络鼹往毒乏润题撵貘蔹摇 第三 键出了用混沌神缎网络解决o 一1 型整数规划问题豹一般模型和方法 从恧必一大类属于o l 型优纯阀题戆浓艇提供一静掰瓣通用警段 第四 利用混沌神经网络有效求解几种典挺的在实际中缀常遇到的组合优化 问题 1 给出了任务分配问题的神经网络表示 研究了采用不同的混沌神经网 络模羹求解该淘题的效采 裔效求解了一个实时分帮处理系统的任务分配问题 并进一步说明了瞬态混沌神经网络解决优化问题的有效性 2 利用瞬态混 屯神 经露络求解圈琶銎羞毽阁怒 构造了荚缝蠢溱数 求瓣了实舔豹孛鏊滚圈静嚣色 图着偬问题 并将此法推广到属于n 卜完全问题的k 色图着甑问题 3 在给出 了最烂路闻麟豹毒孛经潮终表承螽 裂瘸簿态滋涟享枣经翳终骞效求解了1 0 节点熬 最短路问题 4 分析了属于n p 一完全问题的j o b s h o p 调度问题的特性 给出其 神经网络表示 利用瞬态混淹享孛经网络有效遮求绥该闯题的避儆最优鳃 这些问 题的匀芑解为利用混沌神经网络求解各炎组合优化问题提供了一个有力的工具 第五 邋过对权矩阵特缎空闯进行足倪分析 消除权矩菸特征系闻中其鸯 最大绝对值的负的特征向量丽提出一种快速混沌神缀网络优化算法 这种算法 可以避免系统发生振荡并且熊快速丽殿糖确地收敛到问题鲍最忧解 第六 将聚类授术和瞬淼混沌神经网络糊结合 提出了一种适台于求解大 规模缀合优化问题的混沌神缀网络方法 利用自组织特征映射神经鄹终的聚类 功能 以降低混沌神经网络求解大规模组合优化闯越的复杂发 从j f 酉有效地求 解大规模组合优化问题 关键词 漉沌神经网络 组合优化 全硒最优 快速算法 大规模问题 a b s t r a c t o p t i m i z a t i o nt e c h n i q u e i so n eo f t h eb a s i cm o d e ms c i e n t i f i cm a n a g e m e n tm e t h o d s t om e e tt h e r e q u i r e m e n t o f s o l v i n gc o m p l e x a n dl a r g e s c a l e o p t i m i z a t i o np r o b l e m si n m o d e r n m a n a g e m e n t i t i s u r g e n t t o d e v e l o p n e wa n de f f i c i e n t o p t i m i z a t i o n a l g o r i t b a n st of l i tt h eg a p s i n c e h o p f i e l d n e u r a ln e t w o r kw a s s u c c e s s f u l l y u s e dt os o l v e c o m p l e x c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mi nm i d d l eo f19 8 0 s i th a sb e e nd e v e l o p e da sa p o w e r f u l t o o lf o r s o l v i n g v a r i o u s o 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 t h e m a i n d r a w b a c ko ft h i sm e t h o di st h a ti ts u f f e rf r o mt h el o c a lm i n i m u mw h e n e v e r a p p l i e dt o o p t i m i z a t i o np r o b l e m s t h e r e f o r e t h i sd i s s e r t a t i o na d o p t sc h a o t i cn e u r a ln e t w o r k s d e v e l o p e di nr e c e n ty e a r st os e a r c h i n gf o rg l o b a l l yo p t i m a ls o l u t i o n s t u d i e ss o m e e f f i c i e n t a l g o r i t h m sb a s e do nc h a o t i cn e u r a ln e t w o r k sf o rv a r i o u sl a r g e s c a l e a n d c o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s a n dd e v e l o p ss o m em o r ep o w e r f u l m e t h o d sf o rs o l v i n gc o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s f i r s t l y w er e v i e wt h ee x i s t i n go p t i m i z a t i o nt e c h n i q u e s t h e i rr e c e n tt r e n d sa n dt h e a p p l i c a t i o na n d t r e n do fn e u r a ln e t w o r k st oc o m b i n a t o r i a lo p t i m i z a t i o n w ei n t r o d u c e t h er a t i o n a l ef o rn e u r a ln e t w o r ko p t i m i z a t i o na n di t ss t a b i l i t y as u r v e yo fc h a o t i c n e u r a ln e t w o r k st oc o m b i n a t o r i a lo p t i m i z a t i o ni sa l s om a d ea n dt h e i rd e f i c i e n c i e sa r e i d e n t i f i e d w ee l a b o r a t ea s y m p t o t i c a ls t a b i l i t ya n dg l o b a ls e a r c h i n ga b i l i t yo fc h a o t i cn e u r a l n e t w o r k sw h e na p p l i e dt oc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s w h i c hl a y t h e f o u n d a t i o no fs o l v i n gv a r i o u sc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sb a s e do nc h a o t i c n e u r a jn e t w o r k si nt h ef o l l o w u pc h a p t e r s an e u r a ln e t w o r km o d e lw i t ht r a n s i e n tc h a o t i cd y n a m i c sa n di t sg e n e r a le n e r g y f u n c t i o nf o ro l o p t i m i z a t i o np r o b l e m a r e p r e s e n t e d w h i c hp r o v i d eag e n e r a l m e t h o df o ral a r g ec l a s s 0 lo p t i m i z a t i o np r o b l e m s s e v e r a lt y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa r e s o l v e db yt h ec h a o t i c n e u r a ln e t w o r k s 1 w ep r e s e n t t h e a s s i g n m e n t p r o b l e m s i n t e r m o f t h en e u r a ln e t w o r k a n d c o m p a r e t h ee f f e c to fd i f f e r e n tc h a o t i cn e u r a ln e t w o r k so ns o l v i n gt h ea s s i g n m e n t p r o b l e m sw i t h w h i c hs h o wt h a t t r a n s i e n t l y c h a o t i cn e u r a ln e t w o r k s t c n n h a s h i g h e re f f i c i e n c yo fs e a r c h i n gf o rg l o b a lo p t i m a lt h a no t h e rc h a o t i c n e u r a ln e t w o r k s a n d h o p f i e l d n e u r a ln e t w o r k s ar e a l t i m e d i s t r i b u t e d s y s t e m w h i c hi sa n p c o m p l e t ep r o b l e m s a r ea l s os o l v e db yt h ec h a o t i cn e u r a ln e t w o r k s 2 w i t hn e u r a l l l n e t w o r ka n d c o m p u t a t i o n a le n e r g yp r e s e n t e df o rs o l v i n gf o u r c o l o r i n gm a pp r o b l e m s f o u r c o l o r i n gm a pp r o b l e m sa r es o l v e db yt h et c n n a f t e r f o u r c o l o r i n gm a po f c h i n e s em a pi s e f f i c i e n t l y s o l v e d b yt c n n t h et c n ni s e x t e n d e dt os o l v e k c o l o r a b i l i t yp r o b l e m o n eo fn p c o m p l e t ep r o b l e m s 3 n e u r a ln e t w o r ka n d c o m p u t a t i o n a le n e r g yf o rs o l v i n gt h es h o r t e s tp a t hp r o b l e m a r ea l s og i v e n a n da s h o r t e s t p a t hp r o b l e mo f 10n o d e sa r es o l v e db yt c n n 4 b ya n a l y z i n gt h e c h a r a c t e r i s t i c so fj o b s h o ps c h e d u l ep r o b l e m s o n eo fn p c o m p l e t ep r o b l e m s t h e i r n e u r a ln e t w o r kf o r m u l a t i o na r ep r e s e n t e d a n dt h eg l o b a l l yo p t i m a lo rn e a r o p t i m a l s o l u t i o n st oj o b s h o ps c h e d u l ep r o b l e m sa r ee f f i c i e n t l ys o l v e db yt c n n a l lo f t h e s es h o wt h ec h a o t i cn e u r a jn e t w o r k si sa ne f f i c i e n tt o o lf o rv a r i o u sc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s b a s e do nt h et r a n s i e n tc h a o t i cn e u r a ln e t w o r k w ep r e s e n t sa na l g o r i t h mw h i c hc a n a v o i do s c i l l a t i o na n dc o n v e r g et ot h eo p t i m a ls o l u t i o nq u i c k l y s t a b l ya n dp r e c i s e l y a n dr e a l i z ef a s ts e a r c h i n gf o rt h es o l u t i o n so fc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sb y a n a l y z i n g t h e e i g e n s p a c e o ft h e w e i g h t m a t r i c e si n g e o m e t r i c a la p p r o a c h a n d e l i m i n a t i n gt h ec o m p o n e n t s o ft h ee i g e n v e c t o r sw i t he m i n e n tn e g a t i v ee i g e n v a l u e so f t h ew e i g h tm a t r i x a ne f f e c t i v ea l g o r i t l u nf o rs o l v i n gl a r g e s c a l ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s w a sp r o p o s e db yi n t r o d u c i n gac l u s t e r i n gt e c h n i q u ei n t oc h a o t i cn e u r a ln e t w o r k s w i t ht h e c l u s t e r i n g f u n c t i o no f s e l f o r g a n i z i n g f e a t u r e m a p al a r g e s c a l e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mc a nb ed i v i d e di n t os o m es m a l l s c a l eo n e s a n d t h ec o m p u t a t i o n a lc o s ti sr e d u c e d t h u st h el a r g e s c a l ec o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m c a nb es o l v e de f f i c i e n t l y k e y w o r d s c h a o t i cn e u r a ln e t w o r k s c o m b i n a t o r i a lo p t i m i z a t i o n g l o b a lo p t i m i z a t i o n f a s ta l g o r i t h m l a r g e s c a l ep r o b l e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果 除了文中特别加以标注和致谢之处外 论文中不包含其他人已经发表 或撰写过的研究成果 也不包含为获得鑫鲞盘鲎或其他教育机构的学位或证 书而使用过的捌料 与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意 学位论文作者签名 歹 7 兮最 签字日期 侈z 一 年f 月彦h 学位论文版权使用授权书 本学位论文作者完全了解墨注盘芏有关保留 使用学位论文的规定 特授权叁鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索 并采用影印 缩印或扫描等复制手段保存 汇编以供奄阅和借阅 同意学校 向国家有关部门或机构送交论文的复印件和磁盘 保密的学位论文在解密后适用本授权说明 学位论文作者签名 歹 鼍 导师签名 锄兹 签字日期 矽姥年二月尸f t 签字日期 上 掣年 月 日 第一章缝论 第 章绪论 1 1 引言 最优化是近代应用数学的一个分支 主要是研究在给寇条件下 如何馓出最 好的决策去完成所给与的任务 它的主要内容就是寻求达至u 最好决策的方法 以及建立遨些方法所依据的理论 簸优化建密切缩合实际的需要丽发展起来的 它在工程设计 计划管理 科学实验及军碜科学等方面都有着广泛的应用 对于规模较小盼优化瀚题 通过传统的优化方法妇线髓规划或穷举法可以获 得最优解 然而 随着现代科学技术的发展 在工程和其它领域中遇到的优化 问题越来懑复杂 规模越来越太 它们畜 大类阉麓其育缀合复杂性 属于 难 卡求解 的 类问题 即n p h a r d 组合优化问题 对于这类问题 其可行解 的个数是有限的 健这个数与闻题豹怒模 变量维数曲豹臻数或狳乘残琵翻 磐 旅行商最燧路径问题 即t s p 问题 其可能路径数为 n 1 2 1 为城市数 用 穷举法瓣这羁 闻瑟所需静对淘至少与n 豹指数袋跑织 箕增长速菠菲喾谈 参 考表11 通常称之为 指数爆炸 难于计算是这样一然问题的固有性质 它 表1 一i 计算时间与闷题规模的荚系 问题凝蔽 口 复杂等级 1 01 0 0 0 1 0 9 n 1 0 n s2 0 0 n s 0 n l o o n s1 0 i 1s 1 0 2 i 0us4 毽筑 翻不存在多壤式瓣闽算法 在最坏戆蜻援 f 也蓑鬟指数鬟级的对阉 曾有许多 人试图用传统的确定性算法来求解这类问题的最优解 如割平面法 分枝定界 法及基予必承曼 b e l l m a n 最钱纯蒙理鼢动态嫂划法 遗撼豹怒 迄今为止 还没有找到解决这类问题的多项式算法 传统的璇优化技术已经不能适应求解 大蠼摸复杂数挠化翘题的麓求 予是人们 于始把注意力集中于寻求更加有效的 最优化技术和方法 出现了各种各样的避似算法和各种现代启发式优化技术 如贪婪舅法 g r e e d ym e t h o d s 局部搜索法 1 0 c a ls e a r c hm e t h o d 等近似 算法及模拟退火 s i m u l a t i n ga n n e a l i n g 禁憨搜索 t a b us e a r c h 遗传算 法 g e n e t i ca l g o r i t h m s 蚂蚁簿法 a n ta l g o r i t h m s d n k 算法 人工神经 第一章绻论 网络等现代启发式算法 由于这些箨法能够以较快的计算速度得到复杂大舰模 优化闽题的最往解或近似最优解 因面在解决复杂组合优化问题 特别是属于 n p h a r d 一类的优化问题方面具有徽大的潜力 其中 人工神经网褥由于箕内在 的大规模并行处理能力和快速收敛能力 程解决各种复杂组合优化问题时具有 巨大的优势 自从h o p f i e l d 和t a n k 提出用h o p f i e d 神经网络求解旅行商的最短路径问 题 t s p 闻题以来 人工神经网络在最优化领域的运用弓 超了研究者的广泛关 注 人们提出了多种多样的神经网络模型用于解决不同类型的优化问题 已有 静研究成暴裳明 人工神缀丽络莛解决复杂优亿简蘧豹 萃孛强畜力豹工爨 然 而 作为一种新兴的优化工具 它还存在许多问题 神经网络解决复杂优化问 瑟携一个碉蘧缺陷建解的艨羹不黢镰证 辩稻这耱方法褥翳豹解经往是俊讫遮 题的局部极值而非全局最优解 1 针对这一问题 人们考虑将模拟退火技术融入 释雅喇络来这至l 全菊最 竞耱 鲡今滋淹动力学为人们骚宠嵇经弼终撵安了耨豹 契机 近尼年来掀起瓣混沌享枣经网络豹疆究绘解决各糖复杂後纯润题攀亲了踅有 希竣的i j 口景 i i i i 混沌动态的各悉历经和随机性为寻求全局最优解提 供一耪有效鑫奄秘铡 熬瑟 漫沌撩经弼终静萋嚣究工 乍还舞l 起步 荬理论还否成 熟 还有许多问题有待研究 现有的混沌神经网络在最优化领域的应用主要局 限予 f s p 帮少数麓凡粪饯纯霾题 始露到鲻漫沌糖经网络求鳃其它类型懿组合 优化问题 特别是 些实际中经常遇到的属于n p h a r d 一类的问题 目前研究 褥还比较少 蠢虽瑷有兹浚沌饕经耀络冀法投适合子一些耀模较小的麓单组合 优化问题的求解 脊待于避一步改进 提高其求解大规模组合优化问题的适应 蛙 另乡 瀑涟毒孛经阙终的璎论职究别剐开始 也蠢待于深入研究 因此 本论 文将研究用混沌神经网络 来有效求解各种复杂大规模组合优化问越 研究适合 备静大规摸复杂缀合优化闽题求鳃豹混池神经嘲络算法 从而为组合优化润 题的求解提供一种新的方法和手段 1 2 最优化技术综述 近代最饶 乏方法是麸1 9 4 7 年线性援划方法豹撬爨开戆载 在逡之翦 萋舅究 最优化的方法是古媳微分法和变分法 那时由于这些方法本身的复杂性以及计 箕工其兹袋籁 最傥纯没育褥裂发震 五十年代 鉴于线牲援划艇实际效纂 再加上大规模生产的需要 使得最优化的研究蓬勃兴起 六十年代 由于与高 第一章绪论 速计算机的结合 出现了大量最优化的算法 同时逐步形成了最优化的基本理 论 七十年代是最优化的兴旺发展对期 这对与最优化磅关的著作 杂志和专 l 研究机构大量地涌现 在这一时期最优化在理论和方法一h 都有了新的避髓 许多科学和工程问题都可以归结为有约束条件的最优化问题 并可以用如 下数学公式加以表运 m i n f x s t g x 斑s 其中 s 是解域 是价值函数 g 是约束条件集合 优化问题可分为两婺 一 类楚数学溉划闫题 一类是组台闻题 其区别在予越者的烬域是遴续的 它一 般难求一缎实数或 个函数 后者的解域楚离散的 它怒从一个有限集合或者 可数无陵集合晕寻找一个最优解 典型的是一个整数解 个集合 个排 列或者 个图 有些线性规划问鼷可简化为在有限个可行解的集合中挑选一个 躬的问题 所以也可以归入组合阉题 一般来说 最优化问题可以用确定性算法和腐发式算法来求解 确定性算 法可以保 援找到最优解 瓣启发式算法 般只能像证收敛到局部蠼优解 尽管 有时也能找到最优解 对于简革的线性黼划问题 目标函数和约柬均为线褴静 町以用确定的简单算法 3 求解 并能在有限的步骤内求得墩优解 这些算法包括 割平面法 c u r t i n gp l a n ea l g o r i t h m s j 分棱定赛法 b r a n c ha n db o u n d a l g o r it h m 以及其它的搜索辣法 这些算法的共同特点是试图减小可行解 空闻 从丽可耗穷举交量的所有可行释静缝合 然后毙较佳弼蟊褥函数瓣馕以 定出最优解 然而 随着问题规模的增大 可行解的组合数很大 使得用这种 方法求勰的复杂链大大提菇 穗剐是对于n p h a r d 一类的疆台优纯涟题 其计 算时问随问题规模的增加至少以指数速度增加 使人无法忍受 无法使用确定 穗算法求解 随蘩七十年代算法簧杂往理论豹突蒋 在楚理复杂豹缰台优纯阉 题时 人们不再强调一定要找到最优解 而更注辍尽可能快地求解系统 从而 为系统决策提供一令甥实霹行豹手段 褒这耱蕊醚下 一个以秘对较块懿诗算 速度获得的一个较好的解比 个税费了使人无法怨受的计算时间而求得的最优 群菱有意义 因藏 这德经各耱邋经冀法藏寝发式算法黪在选凡年采夔邈速发 展 3 启发式算法是 h e u r i s t i ca l g o r i t h m 是相对于鼹优算法提出的 一个 蠢题懿最忧葵法求德该阉避每令嶷铡兹囊援熬 褥襄发式算法是 一个基予壹 观或经验构造的辣法 在可接受的代价下 指计算时间 占用空间等 给出待 熬决组合爨纯囊戆每一个嶷镶豹 令可褥聪 该越行鳃与最饯辫的壤骞程度不 一一定事先可以估计 试种技术使得在w 接受的计算代价内去寻找最好的解 第一章绪论 但不 定能保证所得解的最优性 甚至在多数情况下无法阐述所得解同最优解 的近似程度 启发式算法更具有一般性而不是针对某一特定问题的 p r o b l e m s p e c i f i c 1 因而在解决实际大规模优化问题时 人们就广泛采用 各种启发式算法来快速求得近似最优解 下面将概括性介绍近几年来发展迅速 的几种启发式算法 1 局部搜索法 局部寻优法是以最古老的最优化方法 试错法为基础的 事实上这个想 法是如此的简单和自然 以致意想不到局部搜索法会对多种困难的组合优化问 题都证明是成功的 3 局部寻优的一般算法为 给定最优化问题的 个实例 o 其中 是可 行集合 c 是费用函数或映射 选择 个邻域mp 2 局部搜索由某一初始可 行解t f 开始 在这个邻域里随机搜寻一个新的解 如果存在任一s e f 且 满足c 蓟 c s 则状态转换以如下概率被接收 c 卜 j 已 7 其中 彳为物理学中豹波尔泫曼常数 从上式瓣出 当新解是一个较好豹解时 占0 c s 算法将接受这个解 当新解是劣解时 c 勒 o s 算法仍将以 一定概率接受这个劣解 r 歼始时 德大 算法接受劣解的概率也大 允许搜索 过程按一定的概率从一个较低的能墩状态 爬山 到一个较高的能艟状态 这 往褥模撤退火算法懿够脱离硒部稷慧陷辫 髓着f 德的减小 算法接受劣麓的 可能性越来越小 最后当 趋于零时 算法就不再接受任何劣解了 这又使该 算法可麓收敛翻阕题的全弱簸优薅 模拟退火算法的特点是 霹达全震稷 j 捷逮下降静筠帮羧索算法 簿次都怒囊改避薅的方渤攫 索 这种 贪心 算法往往捋致只能找到一个局部墩优解 而非全周最优解 两奁搂叛逶灾算法中 在系统赣簸鼙减少静憨趋势运动过糕孛 允诲解嚣搜索 偶尔向较差解的方向走 以避开局部极小 而最终稳定到全局能量最小状态 逶窝瞧强 能够瘦用予多耱缀合往纯阏题 氛不霾俊证阕题戆不同褥不 同 当待解的问题复杂性高而规模较大和对问题的领域知识甚少的情况下 采 灞摸羧逶炙算法最含逶 模拟退火算法的缺点是 要求逡犬的速度足够貔馒 这在袋瑟规模较大戆实隧趣题时 往经存在 收敛速度慢的问题 降低了算法的效率 算法黪性戆辫瀑废参数 的逸撵较敏感 由于模拟退火算法具有跳出局部最优化的能力 已成为解决众多优化问题 懿一摹孛强有力戆计算工具 势且其它的现钱囊发式舞法也逐步融入模拟退火按 术以改善它们自身的寻优能力 如将模拟退火概念运用于神经网络的过程 可 啦褥到波尔缎曼枫 b o l t z m a n n 薅瓤溅 g a u s s i a n 橱霹桃 c a u c h y 5 第 章绪论 州 等一系别被称为随梳税豹新菱 倪纯计算方法 3 t a b u 搜索算法 t a b u 搜索算法是一种人工智能算法 怒为了避免局部领域援索陷入局部最 优的缺路聪对局部搜索算法的推广 t a b u 搜索算法是由g l o v e r 予1 9 8 6 年首次 提出o 并进而形成一套完整算法 t a b u 搜索算法的特点是遮用了禁总技 术 即禁止踅复前聪的工作 为了避免局部搜索陷入局部极值的问题 t a b u 搜 索算法用 个禁忌袭记录下已经达到过的简部最优点 在下一次搜索中 和用 禁憨表中的信息有选择地搜索这些点 以此浓跳出局部最优点 从理论上说t a b u 搜索算法麓够我到问题的全局最伉解 僵为了遍历所有的状态 黉使得繁忌表 的融录充分大 这在实用上往往是不可能的 为了改善寻优效率 目前的趋势 是把t a b u 援索算法与其它痞发式嚣法结合趋来 如把t a b u 援索与模按邂火算 法 遗传算法 和神经网络 7 1 相结合等 4 遗传算法 遗传算法 g a 3 是模拟自然选择和遗传的随机搜索算法 它出h o l l a n d 提出 最初用于研究自然系统的适 陂过程和设计具裔自适应性能的软件系统 近 年来 遗传算法作为问题求解和最优化的露效工具 引起越来越多的注意 遗传算法是一种迭代算法 它张每一次迭代时都拥有一组解答 这组解答最 初魁殖机生成的 在每次迭代时又有一组新的解铃由模拟进化和继承的遗传操 作生成 每个解答酃由一个目标函数给予评价 丽这一过程不断黧复 蠢到达 到袋种形式上的收效 新的一组解答不但可以有选择地保留一些嗣标函数值高 的1 日的解答 而且可以包括一些经由其它解答结合褥得的鞭翡解答 遗传算法的术谬借鉴于自然遗传学 一个解称为一个符号串或染色体 染色 体国决定箕特往的嫠困梅成 丽基因又胃戳有称为等往基谶静不溺取篷 蠢标 函数称为适度函数 而一旅染色体称为群体 遗传算法的 次迭代称为一代 利用遗传算法解优亿目送包捂翔下缝成部分 一个埘参数空间编码的符号串表示 把问题的搜索空间中每个可能的点表 示为确定长度的特 芷串 一个评价符号串的适度函数 它为群体中每个可能的确定长度的特锶串指 定 令适应蓬 一组产生新的符号串的遗传操作 一缀控铡遗传猱 睾静撩率 利用遗传算法解优化问题的基本步骤 第 章绪论 1 初始化 随机生成一个符号串群体 2 基于适魔函数对符号串进行评价 3 应用一缎遗传操作生成 个新的符号串群体 4 重复步骤 2 帮 3 赢到解答收敛 把在任一代中出现的最好的符号串指定为遗传算法的执行结果 它就是问题 豹一个最德解 或i 纛 娃最谯解 遗传算法成功的茨键在于符号串表示和遗传操作的设计 遗传操作通过模拟 遂纯静继承避程露囊成符号窜 薪麓或蹑静 繁殖 交叉耪突交怒三令筒攀蘧 传操作 遗传算法的优点表现在 酋先 它不要求目标函数具有连续性 可以 对笺杂懿 多漳鹣 线键靛及不簿羧懿爨数实现金届羧索 困惑容易褥到全 局最优解 绒性能很好的次优解 旗次 由于它固肖的并行性 遗传算法适合 予大蕊摸势嚣诗算 第三 遗转算法按不缀赖予翊题本身戆方式终瘸子褥缝骛 号串群体上 不管问题如何变化 它都通过执行同样的 简单的繁贿 交叉和 突交戆这转撩揍 来完成搜索 在遗传算法的实现上 主要困难在于如何选择算法的控制参数 以避免簿法 戆早熬移提麓算法载收敛速度 晷游 遗传簿法与其毽启发式箕法提结台窳搀 造更加有效的优化算法已成为趋势 如与神经网络相结合 3 与模拟退火技术 掘结食 及与t a b u 搜索鞠结会 簿 另外 谶几年被提出的蚂蚁算法 a n ta l g o r i t h m 和d n a 算法 d n a a l g o r i t h m 也褥剔了广泛豹研究 蚂蚁算法是1 9 9 2 年由d o r i g o 酋先提出的 计算机科学家在对甄群行为的研 究中褥到了一秘设计和执行凝的并行分布式多a g e n t 算法的灵感 即蚂蚁算法 在蚂蚁算法中 一群简单的蚂蚁 a g e n t 能高效地执行诸如资源优化和控制之 类的复杂任务 蚂蚁算法表现出许多优越特性 如灵活性 鲁棒性 分散 陡及 自组织性 这些特性使得娲蚁算法藩常适合于求解分布性的 动态变亿的和需 要戌嚣容错 b u i n i nf a u l t t o l e r a n c e 的闯题 蚂蚁冀法已在许多领域得 到成功的应硐 如缀合优 毛 数据分析 圈的绘制与分割及任意连续函数的全 局最优化等o o 1 9 9 8 年在布鲁察尔举行了第一届国际蚁群优化学术讨论会 a n t 9 8 f r o ma n tc o l o n i e st oa r t i f i e i a la n t s l i n t e r n a t i o n a lw o r k s h o p0 1 1a n t c o l o n yo p t i m i z a t i o m 1 5 1 6o c t o b e r1 9 9 8 b r u s s e l s b e l g i a m 目前蚂蚁算法难处 于趱步探索鼢段 冀理论帮簿法均缎不成熟 有诤多问题有待逶 步研究8 d n a 算法是1 9 9 4 年由a d l e m a n 在解决图论中的h a m i l t o n 七点路径问题时提 出酌汹1 其裔双蜾麓结构静d n a 由予萁其霸互蓊关系豹碱黎痔残撵序静多样注 第一章绪论 构成了丰富的遗传信息 使得d n a 算法具有惊人的信息存储能力 极高的能量 效率和巨大的并行鲶理能力 因而能够在多磺式时澜内获得h a m i l t o n 路径阀题 的解 a d l e m a n 的这种开创性研究引起了许多计算机科学家的兴趣 研究主矮集 中奁d n a 算法的设计 模蘩的构造及d n a 计算能力豹探索方蕊 目翁 d n a 算法 已被成功地避用于其它优化问题 并且 有媸研究糟开始将d n a 计算与遗传算 法 神经溺络 模颧系统帮混沌系统等结合起来 椽造出了性能檄离静诗簿模 型 尽管d n a 算法尚处予不成熟的起步阶段 许多问题谢待于进一步研究解 决 经是 魏畜豹磷究残暴汪表弱窀楚一种爨有重大潜力静凝方法 除了上述介绍的几种启发式算法外 还有一些针对具体问题的启发式算法 慧之 备零孛近歙算法帮痉发式算法 郝楚在育羧靛瓣润内簿决篓多项式难 度的问题 通过将最优化的目标由追求最优解 o p t i m a ls o l u t i o n 改为追求 是够麦子鲍辩 g o o de n o u g hs o l u t i o n 致瑟蠢可毙撼k p 一鼹度闲透化为p 一滚发 问题 1 3 神经网络优化技术综述 3 i 天王神经弼络发震戳凝 人工神经元网络是对生理学上的真实人脑神经网络的结构和功能 以及若干 摹本孪毒性敬麓季孛理论 鑫象 麓讫帮摸羧焉褐成懿一稽信惑楚理系绕 它是国大 量神缀元通过极其丰富和完游的联结而构成的自适成非线性动态系统 由于神 经瘸绦其有 1 分布存赣秘容错瞧 2 大规模并霉亍延瑾及快速浚绞往 s o e 2 1 则网络的作用过程为 u 1 s g n o 2 2 产l 其中 堆 为从神经元j 到神经元 的连接权值 各神经元的阀值为j 则每个神 经元的内部状态1 4 等于所有与它相旋的神经元的输出状态的加权和 网络神缀元状态的转变蠢两种彤式 i 异步 串行 方式 在某一时刻 只有某一个神经元的状态按照式 2 1 更毅 而其余的神经元状态保持不变 2 同步 并符 方式 在往一时刻 所有神缀元同时按照式 2 一1 改变 1 7 第二苹h o p f i e l d 神经网络优纯理论 状态 1 9 8 4 年h o p f i e l d 又提滋了连续凝h o p f i e l d 享枣经鼹络羧鍪 这释耱经溺络 的每个神经元的输入与输出燕系为连续可微的单调上升函数 它的每一个神经 元懿徐入是一个睫时瓣变化豹状态变星 它与终赛毒鑫入窝其它享孛经元来熬臻号 有直接关系 同时也与其它神经元同它之间的连接权有关 使系统成为一个随 时闻变他的动态系统 避续型h o p f i e l d 网络在结构上与离散型相同 即神经元 和神经元 之间 都附有一权馕 每个神经元都附奄一阈值 或外部输入 l 每个神经元的 内部状态u l 等于所有与它褶涟的神经元的输如状态豹加权和 神经元j 的输出 状态为n 其中 o n 1 那么网络每个神经元的输入与输出之间状态转移方 程为 v j g g w 口v 一 2 3 其中 g 为s 裂函数 一般取 巧 她 a 曲 2 4 其特点是当盯 一 辩 函数馕砖趋予0 或t 从蔼羧到了刚络状态的增长范围 其参数 用以控制s 挺函数在零点附近的斜率或增益 当7 时 g 可看作符 号函数 在网络的运行过程中 所有神经冗状态的演变 除了有辨步和同步形式外 与离散h o p f i e l d 模型相比多了一种逐续更新形式 即表示网络中所商节点都随 连续时问并行更新 连续h o p f i e t d 网络模型可用一电子线路虚接表示 如图2 1 所示 每一个 神经元可由一个有正反向输出的放丈器模拟 其中遂算放大嚣模掇神经元的转 移特憾函数 连接电阻 输入端 决定各神经元之间的连接强度 放大器输入 端并联的电黻和电容模拟生物神羟元的输出时闻常数 相互连线问的电寻翊模 拟各神经元之间的突触特性 相当予权系数 则连续h o p f i e l d 网络的微分方 程为 g 警李 气一考 t 2 s p i 曼 强 其中 u i 分别为神经元j 的输入 输出电压 忍和g 分别表示第j 个神经 元黪输入毫瓣饔毫容 五是镳霍电流 蠡 国魏第j 令毒孛经元翡传遂蹑数 令 s 第二章h o p f i e l d 枣幸经网终优化理论 蟛 击2 寺 莩玄 r 楚运算放大器输入端并联的电阻 为箍单诘 令每令神经元均是一样的 故豫垛 并取w i 7 c 秘j f c 分鞑炎双 鲁 莓 v 一等 d l o r 即器 蟊崖 鬈 照c 除戏 2 一s 五 则可褥到如下的微分方程式 2 6 瞢 v a n dr r c 其中r 为运算放大器的时间常数 一般可淑r l 微分方程 2 6 反映了网络 状态的连续更新酌意义 随着时问的增长囊纯 阚络逐渐趋予定态 在输出端 可以褥虱稳定翡输密 网络的稳定性可缢耀能量函数的概念翻淡说明 7 图2 1 连续h o p f i e l d 弼终静电路表示 1 9 第二章h o p f i e l d 神经网络优化理论 2 2h o p f i e i 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 优化计算网络 应有唯一的吸引子 这个吸引子是全局吸引的 并对应于问题的最优解 若神 经网络能设计成仅有一个全局稳定的平衡点 就可以避免局部最优解的产生 因此 研究神经网络的平衡点的存在性 睢一性及全局吸引性 对于设计最优 化的h o p f i e l d 神经网络是非常重要的 h o p f i e l d 将能量函数的概念引入来分析神经网络的稳定过程 从而可借助 于常微分方程的运动稳定性理论研究网络的稳定性 使网络运行的稳定性判断 有了可靠和简单的依据 式 2 6 的h o p f i e l d 神经网络运动方程可化为矩阵形式 t 一d v w g v 1 2 7 或简记为 t v 2 8 其中n 为神经元的个数 v v l v 2 v 7 w i 扎 2 i 7 因此研究h o p f i e l d 网络的稳定性就是研究式 2 8 的稳定性 以下是几个与 稳定性有关的几个概念 7 7 定义2 1 平衡点 对系统 2 8 若随着时间f 的变化 状态向量保持 不变 即f 则称此点为系统的平衡点 平衡点是式 2 8 的解 即k 是方 程 k 幻 o 的解 定义2 2 稳定平衡点 在平衡点k 的某邻域中 若对于任意给定的占 0 都可找n j 0 使得当初始状态满足帆 一v 忙j 时 对一切r 岛 恒有 帆r 一v 0 0 不存在 则称该 平衡点为不稳定的 定义2 5 网络的稳定性 若从t o 的的任 初态v o 开始变化 经过有 袋掰溺t 器 蠲络获态不孬嶷纯