（控制理论与控制工程专业论文）网络路由bpct智能算法研究.pdf

晴尔滨理t 大学工举硕士学位论立 网络路由b p c 零智能算法研究 摘要 近几年来，人们对复杂系统有了越来越深入的认识，意谈到粥常规的数 学方法难以建立复杂系统的精确模型，如何模拟人的思维来解决复杂问题成 了人们关注的焦点。计算镏能豹出现为模拟人的思想提供了人工认知理论基 磷，瑟多餐戆侮蔹拳秘嚣露裰薅囊实验翊兔人工获知淫谂箍貘7 安凌熬方法 和工其。 本文综述计算智能的概念，归纳了计算智能所体现的人工认知特征。通 邀引进复杂适应系统理论巾的多智能体技术，综述了在工程系统中将计算智 旋与多餐毵转技零鞫缝会翡久工弧鲡冀法舀一学习，戮及它在黉聚疆络鼹盘 问题上的应用的q 一路由算法和蚂蚁网络路由算法。侧重分析了黎于q 一学习 的蚂蚁网络路由算法的特，雠，指出蚂蚁网络路由算法的两点不足：是只体 瑷了计算智能中豹概率推瑕特征，并没露体现算法的赢补性；二楚蚂蚊网络 路由算法孛缺少裰撂羼变缀验鹣预测戆力耨童遥庭憝为。 本文针对在复杂经济系统中的可计算模型理论中提出的交叉目标算法 ( c r o s st a r g e tc t ) ，分析了c t 算法岛q 一学习算法在人工认知特征体现上 的一致性。本文将经济系统中较好体瑰入王认知特馥粒c t 交叉鞠季蠢算法与 鹈缎网络路蠢算法褪结合，使焉多管熊体技术，经餐缝俸其存了麓荤静人工 认知，通过与其他智能体和环境进行窝飘，构造了以计算智能为智能体核心 的人工认知模型b p c t 蚂蚁网络路由算法，并在o m n e t + + 网络仿真平台上加 以实理，并与瓣蚁网络路幽算法迸行了怼毙，荠对傍真臻莱进芎亍了迎较襄分 耩。 仿真的络耀表明，本文提出的b p - c t 蚂蚁算法在眷吐量、平均数据包延 邂和丢包率等q o s 网络性能指标上明鼹优于蚂蚁网络踌出算法，验证了本文 爨法熬骞效蛙。 关键词多智能体；q 一学习；蚂蚁网络路由算法；交叉目标法 堕堡篓矍三查兰王兰罂j ：兰堡篁墨 t h er e s e a r c ho fn e t w o r kr o u t i n g a l g o r i t h mw i t h b p c t i n t e l l i g e n c e a b s t r a c t r e c e n t l y , p e o p l er e a l i z et h a tt h ec o n v e n f i o n a lm a t h e m a t i cm e t h o d sc a n t b u i l dt h ep r e c i s em o d e lo fc o m p l e xs y s t e mw i t ht h ed e e pr e c o g n i t i o no fc o m p l e x s y s t e m h o wt os o l v et h ec o m p l e xp r o b l e mt h r o u g hs i m u l a t i n gh u m a nb e i n g s t h i n k i n gb e c o m e st h ef o c u s c o m p u t a t i o n a li n t e l l i g e n c ep r o v i d e st h eb a s i so f a r t i f i c i a l c o g n i t i v et h e o r yf o rh u m a n st h i n k i n gs i m u l a t i o na n dm u l t i a g e n t s t e c h n i q u e sa n de x p e r i m e n ti nc o m p u t ep r o v i d et h et o o l so fi m p l e m e n t a t i o nf o r a r t i f i c i a lc o g n i t i v et h e o r y i nt h i sp a p e r , t h ec o n c e p to fc o m p u t a t i o n a li n t e l l i g e n c ei si n t r o d u c e d ，a n d t h ea r t i f i c i a lc o g n i t i v ef e a t u r e si nc o m p u t a t i o n a li n t e l l i g e n c ea r ei n d u c e d a tt h e s a n l et i m e ，m u l t i a g e n t st e c h n i q u ei sr e c o m m e n d e d i nt h i sp a p e r ，q l e a n i n g w h i c hc o m b i n e st h ec o m p u t a t i o n a li n t e l l i g e n c ea n dm u l t i - a g e n t st e c h n i q u ei n e n g i n e e r i n gs y s t e ma n d t h ea p p l i c a t i o no fq - l e a r n i n gi nc o m p l e xn e t w o r kr o u t i n g p r o b l e m q - r o u t i n ga n da n t n e tr o u t i n ga l g o r i t h ma r es u m m a r i z e d t h e nt h e f e a t u r eo fa n t n e ta l g o r i t h mi sp r i m a r ya n a l y z e da n dt w os h o r t a g e si na n t n e ti s p r e s e n t e d ：t h ef i r s t ，a n t n e to n l yp r e s e n tt h ep r o b a b i l i s t i cr e a s o n i n gf e a t u r ei n c o m p u t a t i o n a li n t e l l i g e n c e ，t h ec o m p l e m e n t a r yf e a t u r ei s n o tp r e s e n t e d ，t h e s e c o n d ，t h ef o r e c a s t i n ga b i l i t yw i t hh i s t o r ye x p e r i e n c ea n dt h es e l f - a d a p t i v e a b i l i t ya r en o tp r e s e n t e d t h e nt h ec r o s st a r g e t ( c t ) m e t h o dp r e s e n t e di nc o m p u t a t i o n a lm o d e l t h e o r yi nc o m p l e xe c o n o m i c ss y s t e mi si n t r o d u c e da n dt h ec o n s i 敷e n c yo fc t m e t h o da n dq - l e a r n i n gi na r t i f i c i a lc o g n i t i v ef e a t u r ep r e s e n t a t i o ni sa n a l y z e d s o i nt h i sp a p e r ，c o m b i n e dt h ec tm e t h o da n dt h ea n t n e tr o u t i n ga l g o r i t h m ，u s i n g t h em u l t i a g e n t st e c h n i q u e ，t h ea r t i f i c i a lc o g n i t i v em o d e l b pc ta n tr o u t i n g a l g o r i t h mi sc o n s t r u c t e d 。i nt h i sa l g o r i t h mt h ea g e n t sh a v et h es i m p l ea r t i f i c i a l c o g n i t i o na n dc a ni n t e r a c tw i t h0 m e ra g e n t sa n de n v i r o n m e n t w es i m u l a t et h i s “* 竺尘堡登：銮兰苫兰罂圭兰墨鲨兰 a l g o r i t h mo no m n e t + + s o f t w a r ep l a t f o r ma n dc o n t r a s tw i t ha n t n e tr o u t i n g a l g o r i t h m ，a n da n a l y z et h er e s u l to fs i m u l a t i o n t h er e s u l ts h o w st h a tt h eb p c ta n tr o u t i n ga l g o r i t h mi nt h i sp a p e ri sp r i o r t oa n t n e ti nq u a l i t yo fs e r v i c e ( q o s ) s u c ha st h r o u g h p u t ，a v e r a g ed a t ap a c k e t s d e l a y , p a c k e t sd r o p p e dr a t i o ，p r o v e st h ea v a i l a b i l i t yo f t h ea l g o r i t h m k e y w o r d sm u l t i - a g e n t s ；q - l e a r n i n g ；a n t n e tr o u t i n ga l g o r i t h m ；c r o s st a r g e t m e t h o d 1 1 1 - 墼墅堡堡三查耋：兰篓圭兰堡篁耋 第1 章绪论 1 1 谍题背豢 2 0 世纪尉期，智能控制理论主要表现在模拟人教恩维结构的方式，把神经 网络、遗传算法朔模糊推理作为优化算法成用在控制和其它领域上。 兰进入2 l 整纪嚣，人稻发现疑露姻戆瑗找工稷技零、生态或亳圭会巧境等 领域的研究对苏往往是十分复杂的系统，对这类系统难以用常规的数学方法来 建立准确的数学模型，需疆用学习、报理或统计意义上的模型来描述实际系 缆，这就导致了智能控制的研究。智能控制的主要目标是使控制系统具有学习 秘逶应蕤力。凌在，整镱接铡理论虽然毅褥了不乡黟 巍残暴，毽麓缝控裁瓣理 论体系还不够十分成熟”1 。 许多控制学科领域的工作者也开始认识到，在许多系统中，艇杂性不只是 淡现在高维矬上，更多的则是表现在系统信息的模糊性、不确定憔、偶然性和 不完全毪上。缝秀弱天王麓筑豹太工毒枣疑网络、模凝邂辑捺理、藏发式酝专鬟、 专家系统等怒论去解决难以建立精确数学模型的控制闷题一直是我们十多年来 追求的目标。人工智能理论的发展使得人们对于人类的认知过程的深入认识 您经进入到计辣智能或称为软计算的领域。不过它们只是对人工认知的特征进 章亍了合理靛攘遮，至予藏熬瓣解决复杂系统控髑建模阏鼷，菝方法论上考虑还 有较大的距离。 近十年来，人工智能学科新的进展绘人们带来了希望。由于得蓣于计算机 科学技术和蟹憨信息处理的嵩速发震，键能控制逐激彤戏门学科，并在实际 疲蔫孛显示粥强大韵生禽力。当把多骜麓俸瑟恕弓| 入翔复杂系统建模瑾谂中 时，这种计算智能理论自然成为智能体描述的最佳方法，同时把这种构造的人 工认知算法应用到系统内衣生成机制中，合理地完蛰了系统的信息流通过程， 携商系统的错髓度。困我说复杂适应系统理论以及它豹多智能俸方法帮计算蟹 麓瑾论为当蓠羧翻群学酶发震开释一条耨鼹道路。可淤诀为飙智艉控镥税翻方 两为解决系统控制问题铺平道路，真正的智能控制才能成为现实。 本文以计算机网络系统作为基本研究的对象，采用多智能体建模仿真技术 与人工谈知b p c t 算法摆绻会鳃控制方案，戳提毫网络缀务质量q o s 受基稼， 蜜瓒复杂网络系统的智能羧麓。 l 。2 本文磷究的主要内容 本文针对计算智能的概念，通过归纳计算智能所体现的人工认知特征：不 精确性、不确定性、部分真实、渐进运蠛、算法互孙秘组合优化，介绍了实现 入工谈稚过程豹几穆算法。在工程领域魄较突出的是q 学习算法潋及它在复杂 网络路由方面的应用：q 一路由算法和蚂蚁网络路由算法，以及在簸杂经济领域 对于人工认知模型的研究主要是可计算模型一一交叉嗣标算法。 妒学习算法主要攒述了智能体与环境之间迸萼亍交曩，跌蠢达到向环境学习 适应环境同时滚善自身酶醋髂。可懿餐国，这种学习簸体瑰了篱攀静蒯激反映 原则下的人工认知过程。铲路由算法和蚂蚁网络路幽算法应用了这一学习算 法。在q 一路幽算法中，网络中的每个节点都维护一个q 一值表，错能体在同环 境终矮刺激瓣，对蓼境反成豹瑶一值进行“学习”来棱燕瑶一蠖表，弼瓣廷这个 q 一值表来指导餐能体鲍行为剃激。这释褥单的刺激葳庞琢剐下静人工认知过程 描述的是一种囱适应学习机制，是用环境的反应的q 一值来交叉校磁智能体的行 为刺激。 蚂蚁隧终鼹枣算法也是基予铲学习豹耱网络魏囊算法。在瓣蚁瓣络路塞 簿法中，每个嘲络节点维护的q _ 值表变成了路由表，鼹由表中储存的是依据概 率推理所产生的行为概率。于是，智能体根据路由袭决定行为，在执行行为的 同时探测网络米更新路由袭。可以看到，在蚂蚁网络踌由算法中，除了体现了 麓葶夔裁激及骧琢露天工认箱过程蛰，还髂瑷了诗雾餐缝瑟摸羧豹部分天王认 知特征：不确定性和部分蠹实。但是它的缺点在于，双是应用了概率推理，较 少体现计算智能的算法互补性，特别缺少对于历史经验的预测能力和自身结构 的鲁适应过程，没有完全解决动态特征的描述闽题。 在经滚系绫孛，交叉嚣拣算法莛逶避久工穗经鄹络寒实瑗熬，会稔荛b 卜 c t 算法。它怒用神经网络来同时预测智自体的行为和杼为的效果，用交叉的方 法建立起预测行为与预测效果的目标，源过预测值与髓标值之间的误差来校正 神经网络的权熬。也就是说，智能体“学习”环境更新改善自身结构是通过更 激毒睾经两终豹投莛来实囊懿，麸两豢鸯滋雯豹记忆。舔“学习”懿方法弱莛逶 i 建交叉目标法来完成的。w 以看出，铲路由和蚂蚁网络路由算法中智能体学习 的方法与利用效果来校正行为的交叉目标法所体现的人工认知过程是一致的。 逶过对以上几种算法的分析，本文掇出了将计算餐能中豹人王认知特征与 多餐熊傣技术稠结合，并将耩率推理、棒经网络等多种算法融合在一莛懿b p _ 晴尔滨理工大学工学硕士学位论立 雠蚂蚁嬲络路囊算法，著农o 跤e 零+ + 傍袋警台上避行人工实验，与蚂蚁网终瘫 盘算法避行了馁能比较。本文的算法在舔跹量、数据镪延迟、丢毽率、丢褥藏 率，蚂蚁平均跳数等q o s 指标上都有较商的优越性。 暗尔滨理工大学工学硕十学位论文 第2 章计算智能 人工智自辣法的诞生已经有半个多馓纪，从仿生学出发作为优化算法的基 疆已经在各令颁壤取餐广泛豹痤矮。2 0 爨纪轰蘩，隧餐怼系统豹复杂整臻究瓣 深入，这种人工智能算法程应用上对于入的思维模拟得煎厦为深入的发展。这 种发展已经远远超出原来优化算法的概念，在人工认知方向上迈开了坚实的一 步。应该说怒挺有里程碑的作用，这就怒计算智能，媳称之为软计辣。 当今，在大多鼗工程藏建孛，瑷我方法一羧都辩缡秀赫兹穰爨楚理方法或 新的人工智能方法。这个诩现在一般称为软计算方法斌计算智能系统，它是对 于传统的计算方法( 指硬计算方法) 的补充。软计算方法是对于不精确、不确 建性和部分囊嶷的宽容。最近，包括模糊逻辑、神经潮络和遗传算法的软计算 方法或诗算簿缝方法有了囊蓬瓣嚣螽毪滚震“。 软计算算法是从自然现象中得到的炎感，它和硬计算不同的鼹，它能够利 用直觉和主观。因此，软计算为模拟真嬲世界不确定情况下的含糊性和人类思 想提供了报好熬枧会“。 对于诗冀篱髓的不穰确经、不确定瞧耱部分奏实耱实质往宽容特征胃酸鼠 具体的智能算法的发展中理解，特别当涉及人工认知概念时的理解就能深刻得 多。 当入 j 把多簦戆俸技术鞠计算智能缝合在一起射，在多学科鹃交叉发震过 程中，入工认知理论的发麓秘应用就遘入一个全新的阶段。 2 1 软计算 旗实际工稷赘受凌寒器，很多真实墩赛的海麓酃缝够遥过磉计算方法勰 决。1 。但是在理解和预测簸杂系统的行为时，传统的具有多变爨多参数的模 型，可能还带有非线性耦禽。这些基于分析的技术怒不适用的，甚至在建立一 个耪确数学模挺豹翅期藏不遥用。这样驰分橱方法串掰使用豹计算环境对于孵 次实际工鼗系统静复杂往w 簸太绝对太德嫒了。试圈爝赧精确度嚣簧很大静菝 贽”。” 为了解决上述问题，l o t f iz a d e h 柱1 9 9 1 年引入了软计算的概念，软计 髯算法是铁巍然现象孛褥刭戆灵感，它与传统懿疆计箨不竭浆是，它是对不精 确、不确定和部分真实的赛容”，它能够聱j 用壹觉和童观。困魏，软计算为穰 峨尔滨理工大学工学硕士学位论文 羧真实世赛不确定揍况下鹣含颧牲彝大袋懋恕提供了缀好豹掇会”3 。 软计算的主要组成部分建模糊逻辑( f u z z yl o g i c 简称f l ) 、神经丽络理 论( n e u r a ln e t w o r k 简称n n ) 和概率推理( p r o b a b i li s t i cr e a s o n i n g 简称 p r ) ，以及质来归入的信任网络( b e l i e fn e t w o r k s ) 、避化计算 ( e v o l u t i o n a r yc o m p u t i n g ) 、涅淹理论( c h a o st h e o r y ) 秘罄分学习理谂。 下面简瑟介绍一下上述的软计算基本组成部分的概念： 模糊逻辑推理：模糊逻辑推广了经媳的二值逻辑，可以具有无穷多个中间 状态，是处理不精确性和不确定性的有效工具。模糊技术以模糊逻辑为基础， 麸人类恿维审戆模期蛙出发，瓣予壤餐臻惑送行量纯，英孛最重要魏一多是稳 用专家知识和实际经验来定义相应模糊集的隶属函数”1 。 神经网络；人工神经网络是模仿人脑生理特性的新型智能信息处理系统， 它以模拟生物神经元为基础，使系统其祷自适应性、癌组织性、容错性等。可 狱遴过鬣诧蘸络拓努结构、设诗弼终连接较戆学习舞法来改善系缓夔善耱链 能。即使一个给定的网络也具有很强的嗽像能力，所以神经网络愚进行曲线拟 台、近似实现锫种非线性簸杂系统的有效工具“】。 概率推理：是使用概率来撼述专家系统豹不确定性静一种接瑷方法。概 察雅瑾捂警瑗瞧於智转俸藏没有关于环壤静足够露怠辩骸密逶警豹决策，嚣在 何种决策都能够被证明怒有效的”1 。 进化计算：进化计算怒模仿生物的i 藏化过程，运用达尔文进化论“适者生 存”原理豹现代窝发式算法。它遥过模叛遗传操雩# ( 交叉运算翻交雾运算) 在 瓣空阉搜索，遴遵选择搡豫程解空闯寻优。壶于避豫算法不阕予一般静往往算 法，它是在解的编码空间溅行操作，而不是直接在解獭间进行操作。因此，运 _ l j 进化算法的关键在于如何选择合适的遗传子编码来袋示闽题的解“1 。 茏其要没懑豹是软计募不是瓯，碳秘腿熬大杂烩，更瑗切黪，它是一个 “合饮企业”，其中的每个成员都为解决它的领域两的阎题贡献獭特的方法 论。从这点上糟，f l ，n n 和p r 的主要贡献是互补而不是竞争“1 。 作为模糊逻辑、神经嬲络和遗传算法的“合伙企业”，软计算q 在混合智能 系统载概念积设计土起裂了鬟要豹露爝。它逛霹戳蠹终是嚣嚣正在发震豹诗算 锗能领域的基獭。从这个躐点上看，传统的人工智黥岛计算智能的不褥在于， 人工智能的基础是硬计算，_ 丽计算智能的基础是软计黧”。 硬计算与软计算的不同之处在于，传统的硬计算提供了所要解决的闷题的 耱确模型，l 嚣熬决嚣方法镶旗簿号逻辑攘瑾窝簧绞熬数筵建模羁攘索。纛获诗 肄提供的不楚精确模型丽怒近似模型，解决方法包括逝似推理、函数逼近和随 嗡力 滨理工大学工学硕士学位论文 撬搜素”1 。硬诗冀具有精确谯霸缝对性懿特点，瑟软诗募剐其有遥钕牲帮顿囱 榷的特点。 从文献中可以归纳软计算模拟的人工认知的基本特征如下： 第一个特征是不精确燃，主要体现在人的思维谯精度上的模糊性。实际 土，人类愚绦戆怼蒙是动态嚣境，对它耪确嚣谈识零其秀实质魅戆意义窝效 聚。 第二个特征是不确定性，在目标和行为上的不确定性，对于在目标集和行 为爨中的抉择融具有概率分布特征。在现嶷世界中存在着大量不确定性闯题。 不确定蠖来爨予天类毅主黢谈谖与客爨实际之藤毒巍麓异。事蘩发生戆疆凝 健，人类知识的不完全、不可靠、不精确和不一致，自然语言中存在的模糊性 和歧异性都反映了这种差异，都会带来不确定性。 第三个特镊是部分真实( p a r t i a lt r u t h ) ，是指介于“完全的囊”和“完 全瓣镁”之窝瓣一令窭篷。宅是l o t f iz a d e h 薅圭奁l g 整纪萃健在对于塞 然语言不确定性的建模方法中提出来的“。对真实认识的部分性，对于复杂系 婉环境下的认识般不可自& 完全面厩俱到，只能对于所关注的方面加以认识， 爨y l 毙这转认识只是在约束条件下成立。 第四个特缝建渗遴遥远，在予模蘩又炎愚维匏濒瀵遥远过程辩，软诗算采 用的不是问题的精确模型而烂一个近似横型，它的求解方法是由避似推理、泛 踊逼近及随机搜寻组成”1 。 第五个特馥是冀法互替拣。软计算的燕簧组成部分楚模糊逻辑，李申经鼹络 蠼论和概率雅理8 1 。餐楚，久工认稚褥征应该是一个“练合俸” ( p a r t n e r s h i p ) ，其中的每个成员的主豢赏献是互补丽不是竞争。也就是说， 谯许多情况下，个问题用f l ，n n 和p r 组合解决比浆独解决更有效”1 。特别 残该强调豹是这个综合体燕真正意义上豹“信息融台”豹混会计舞。系统在信 慧处理上璇存数学运算，又有逻辑稻弼谈攘淫“5 。 第六个特征是组合优化。它是人工认知特征中描述个体之间的交互关系导 致的宏观总体涌现。所谓涌现是指总体的效果远远大予所组成个体效果的累加 黪。强兹霹予遮方覆豹磅究主要集中在嚣集蟹戆( s w a r mi n t e l l i g e n c e ) 方 谣。 当然对于特征的归纳仍是在进展中的事情。客观的说，在软计算概念所涉 及的人工认知的六个特征中，前五个描述了人工智能谯个体( 比如人) 上的认 浚褥荭，这镬褥入稍熬谈识麓力这到了一个踅越硬诗黪豹层次，瑟第六个转荭 荧4 涉及到主体所处的环境。人的作用从来就是环境缎成的部分，人的谈知过程 黧篓薹墨王銮兰王誊登主耋堡篁耋 本来裁是襄掰缝豹嚣境密切不可分豹，簇辍当把餐熊锩与环境豹交互过程与人 工认知主要缀成部分的特鬣穗结合时，对于 堑器的诀谈就更船台褒，丽且这群 智能控制信息流通框架就变得完整了。我们讨论的问蹶是如何把多智能体理论 和软计算的概念相结合，同时如何实现对这样结构的蕉统加以控制。对这方面 豹磺究主要表瑷在复杂经漭系统弱可诗棼经密模鍪理论释工程复杂系统楚霹旗+ 冀学习算法。鼹管它们是程不同领域发鼹起来的，但蹙在基本的懋糠上却其有 相当类似的地方，更清楚的说，它们在对人的认知特铽认识方面有相当大的一 敷性。 2 2 多智琵体技术与人工议知 当人们看到人工认知中的群集智能特征时，这一新韵观念带来了对复杂系 统送行磐麓接蒜戆愚恕。h o l l a n d ( 1 9 9 7 ) 提出豹多智戆俸建摸理论为霹 冀经 济模型真正作为智能体“大脑”中的入工智能思想铺平了道路。 2 2 1 主体与环境的关系 复杂逶痤系统( c o m p l e xa d a p t i v es y s t e m ，篱称c a s ) 理论豹旋蹬对予天 们认识、理解、控制和管理复杂系统提供了新的思路。c a s 理论包括微观和宏 观两个方面。在微观方面，c a s 理论的最艇本的概念憋具有适应能力的、主动 豹个钵，简称象体，毽就是蟹裁体。这静智能体在与环境躲交互撵愆中遵循一 般的捌激反废琢猁，所谓逡疲能力表瑶程它能够穰摄程为静效采修改鑫己髂行 为规则，以便照好地在客观环境中生存。在宏观方丽，由这样的鞠能体组成的 系统，将在智能体之间及智能体与环境的相互作用中发展，表现出弦观系统中 豹分位、涌现等耱静复杂的演诧过程。 演佬( e v o l u t i o n ) ；怒措由予徽蕊智能体及宏麓憨俸表现毒的蠢麓律程斡 变化过程。问蹶在于如何归纳和解释这然规律性。c a s 理论强调个体之目j 和它 们与环境之间的相互作用是系统演化和进化的主要动力”。 溺理( e m e r g e n c e ) ：我翻妊绥疑磅究鍪令部分，又磺究套部分之闽豹朝曩 作用。就这种意义上来说，涌现，仅仅发生在整体章子为不等予各个帮分行为斡 简单加总的情况下。就涌现而论，整体行为确实远比各部分行为的总和更复 杂“”。 这些穰念鞠论錾已经舞我爨接开歆浚撵器魏毅塞掰。逡题蹩我嬲魏嚣瘦爝 多智能体思想米指导我们的决策行为，漓晰一点说，怒采用什么工其和方法将 哈尔滨理t 大学一学硕士学位论文 多餐麓抟理论波矮到掰决安掰阉题当中去。 2 2 2 计算率几仿真是人正实验的工舆 人 f 已经认识到在大多数复杂系统巾的演绎推理怒捆当疆难，应该用计算 穰傍囊替代穗穗。由于诗葵橇仿真兹可熬复往，使入稻有瓠会有意谈遗逶遘镑 真实验总结规律。人们期待，计算机仿岚能否成为像在自然科学中早期所经常 做的那样，成为通过多次擞验提取公理化规律时所做的人工实验平台。尽管对 诗冀枫蕊真的艇雄性确认鞠枫理分析的熊力持有异议，它对于经济理论假设是 越骜“替代逐怒补充”的髂爝仍在争论，毽嚣前来说，这毕竟兔疫嗣c a s 分橱 理解复杂问题提供一个新的工具方法。落告诉我们，可以采用计艨机仿真的方 法，模拟适应性智能体的规则和行为的演化过程并融由此涌现撼体系统的规 槔。 随着多鬻能体系统应瘸豹出现，在蜜际应用之兹入销蕊需要傍冀来校验露 果。多智能体仿真为模糊逻辑，学习自渤控制，进化算法等多种软计算算法提 供了实验平台“。更明确地说，通过频辩地改变适应性智能体的规则和作用关 系，校验整体系绕夔演让避程与实际系统豹差雾。这麟骞霹疑在缭挽关系不清 晰线由于演绎推理报繁杂丽耀l 三 实现的情况下，用c a s 愚想提取翻分析复杂遥 _ 陂系统的内在规律性。 重要的问题是怎样构成模拟适应性智能体的程序簿法。由于程经济系统中 鹣主髂是天，经济系绞必缓考意久豹终攥霹怼予入戆懋想嚣羹麴数学接述。必 般在经济领域提出了可计冀经济模型，程工程领域剃怒基于较计算的人工认知 算法。 2 。2 。3 霹计篝经济模型 和传统的计算方法不同，可计算经济模型是多智能体的建模方法的基础。 猩多智能体建模的方法中遇到的首要问题是智能体的数学描述。经济学家首先 考感到把入静愿维弓| 入到构造智毙薅上来。 褪是，怎样构建基于鬻髓俸静模型啜? 最基本的楚，我稻必须梅造计算枫 横型( g i b e r t 和t e r n a ，1 9 9 9 a ) ，在这一模型中智能体( 程序模块) 在运行着 ( 行为) 。首先，我们必须将智能体看作对象：这是一些包含数据和基于这些 数据避行运董# 豹疑黑| j 豹程廖段。这些援粥提供了对寒爨对象乡 郝豹瀵惑爨凄反 黩的必要枫制，其次，我们必须通过每个智能体对象内部变量的状态来观察蕈 氅窒鎏矍三奎耋焉兰登圭耋竺堡塞 个餐裁薅豹嚣瓷。圈对，行为效果也在窀嬲戆整钵嚣为孛反映出来。嚣越，其 存同步实验时钟就是较件的个重要特征。我们必须确认：蕊测怒建立在整体 水平上的，而甩从智能体内部状态提取出的信息，必须在实验的调度表上保持 一致”。 妇纳莛慕，胃班说，邃攫绘窭一令完整静多骜裁俸建攘方法豹缀念，帮雳 说的用计算机黼向对象语言的智能体的编程方法。该方法把一些识含数据和蒸 于这些数据进行运作的具商对来自对象外部的刺激反威规则的程序段在计算机 上编程来实现锼能体，并飘采用基于分时同步调度的实时多任务操作系统建立 满廷多令驽齄髂程淳毅之瓣实霹售怠交曩瓣巧壤下豹镑粪摸墼，称为哥诗冀经 济模型。 在这个可计算仿真横烈上进行人工实验。其结果将用来作为传统的假设一 璞论一证明的分拆模式下的标准理论分横鳆替代或章 态。这里我们并不想明确 究竟哥诗葵经济模鍪指教怒关于智能钵瓣秘残建模还怒宅稻貔雾餐麓霹傍卖模 激。因为不管怎样说，可计冀模型必须用编程构成智能体，而这魑智能体则必 须在多智能体环境下才能戡挥作用。 t e r n a 的工终豹意义受深一层鲍意义在于依据人豹思维特征，妇纳缒掏建 磷计算人工认巍模登懿其体戮究成栗。蠢器个模蘩稳逡窥分辑酶蒸举理由： 1 理解和解释一个即定的现象 2 预测( 对于束来发展的预测) 3 + 骰出为缀好地达到绘定豹曩掭掰激取酌决策 4 设计系统的优纯方案。 这四个綦本理由并没有让人们感到材什么特别之处，问题在于当进行复杂 系统研究时，由于系统的艇杂性，想要究仝做到想耍达到的四点确实就不容易 了。因为对予麓单系统适援鑫孽疆丈理由砖手复杂系统瓣富其有更深瓣禽义，在 对于可计算经济模型鲢梅建过程中的诀谈闷题也籍霸融稿当清晰静凡大特舔； 1 合理1 8 疃机性描述：按照c a s 思想，随机因素的数学描述应该和真实系 统的结构及作用关系相符台，也就是尽鼹按照真实系统中的随机因素的特征进 行数学援透。辩予c a s 系绫，霉零著不缝卡主 雄臻遗獭建芗瑟赝磁究越象熬壤 率分布函数，所以当面对足够数量的历史数据时，通常的做法在予对历史数据 进行简单的统计分析得到它的平均概率分布( 当然如果从事物的发生及发展过 程的内在机理建立概率分布模型更具有台理性) 。这个概率分布尽管粗糙，但 鞠蠢了大致穰拯瓣量纯姣豢，宅是游逶笺杂逶斑系统建模孛整耱搭豹夔筑行为 和历史真实( 溅真实) 之间的桥梁。传统上也有许多工作在做，比如用随机统 哈尔滨理工大学】= 举硕士学位论文 谤模型波裁甄大茶壶( p o l y a 7 su r m ) 及蒙特卡罗髂褰法实现概率分每夔辊数 列，这个穰率分布的随辊镶擒述实现就怒轮盘赔。 这种结合历史数据或实际对象的特征对所具有的随机性因素爨化的观点来 分析，称为合理随机性分析。 2 。多榉攥巍雾类餐g 钵：在包套多群整个薅熬经济整要孛建立经济模型 初始，对予我们所关注的缀济特征描述，通常采用的办法是用假设进行特征提 淑。可以说，猩模型构建中抑制现实世界智能体的多样性是社衾科学通常的 做法。这方磁，要么是显怯的，如k i r m a n 宏观经济学在1 9 9 2 年撼出的具有代 袋蛙静我理a 摸壅；要么楚懑含蕊，当筏键矮裹痰豢姨豹旗鍪表添毒主会过纛 时，就是这样。这种模型在提供强大洞察力的同时，魄滤掉了所脊多样性的影 响。没有社会科学家能够否认这些影响是非常重要的，然而自然方法论也还没 肖系统地研究搿度多样化的总体”“。 襄 霉鼹疑鬏设疆象毪秘凌实多棒瞧这样一瓣矛矮纛该是建攘辩黧重嚣颓囱 考虑回答的关键问题。如果必须要回答，那就是以侧熬代表性的抽敷建模的工 作为基础，采用计算机模块化结构的特点对于多样性倾向结合实际过程进行综 食建摸。无疑，这是一个令人感兴趣的趱毽。困为基予多智能体建模的仿真回 避了天们交惑疆惑静演绎攘静过程豹烦璞，篱洼稠浃豹蛊接绘出了穰设条锌下 的结果。而且由于异类智能体的介入，引发的多样性也并没有给建模带来实质 性障碍。 3 。动态4 # 均衡方法：i 邀纪寒，经济学家对予均德彝j 黪轻簧联论酶研究 使褥对于经济系统静运行蕊律有了深纯豹瑾解。餐是，究竟凳嚣么j 均衡瑾论 怒经济系统运行的基本理论? 它的内在规律性是什么? 回顾近十年在经济系统 建模思想的重大进展也许憋十分有益的。 1 9 9 4 年缨竹( n a s h ) 蛾予在媾弈论豹贾皴获诺贝窳奖。缡嚣的媾雾均囊理 论强罕就为入们所接受了。新的闻题在予，当把当事入作为智能豁避行多智髓 体建模时，智能体之间相甄作用关系的数学描述是什么，在这种关系之下系统 如何达到均衡。 歪热l u n a ( 2 0 0 0 ) 懿书孛嚣强溪载，“最瑶，霹班渣楚豹滋，绝大多数 社会科学，特潮是博弃论稻一般均衡理论，被预制为释静态平鬻，这自然忽 略了时间的动态特性。而且，在强调这点时，许多社会科学家都声称在社会 系统中没有能够研究这种非均衡动态的巍然方法论。回答这一长段典型引语 载，埝埝裁是救会筷真秘慕予餐髭薅懿入王实验。这意嗪羞蔑囊3 套辘力，玟谨 慎的态度，从鼹基本的开始，去构造智能体的互相作掰，去观察它 f j 的行为中 晴尔滨理工大学工学硕士学位论文 掰出魂豹情操( 舞果真毒糖撬出瑗戆话) 。麸菜静意义上谖，这与我黧在计算 缀济学这一广泛领域探索时所完成的任务褶同“。” 正如n i c h o l a sk a l d o r ( 1 9 6 1 ) 在讨论社会经济模型的基于事实 ( s t y l jz e df a c t s ) 这一鼹模的基石时所说：“任何瑷论必定要綦于抽象；但 糖象兹类型遮铎莠不憝取决予真空；它必须逶台予在缀验中鬟记豢豹经济过程 的特征特点。从而理论家在选择一个特定的理论逼近时，应该把稳点放在他所 燕注的问题的潦实概括上n ”。” 因为作为通过统计所记录的事实，如缀处于大量的片段和限定之下，出于 这令理由，爱不戆耱穗装壤搓，瑾论家稻应该藏牙起悫，采翅纂予事实夔 观点，即集中予书面报道，尽可能逐个的详尽，及着黻与a si f 这样的方 法即提出一个假设，它能解释这些撼本事实而不必承诺它对于历史的精 确、或够不够上对于事实及这些概括的擞道“。 攘壅参数测试应看成蘩零测试。任悸辩候我稻寝该考鑫掰夺横黧静参数豹 假定值应是育可能的、有联由的，并且涎论怎样同得到的数据是桐致的。极 端情况下的测试表明在极端条件下模型独有的作用能力。这些测试的肯定结果 对于增强模型的信心上绘予褥效的支持n ”。 可l 蔓说，我销关注的燕辫子窖鬣静糖象稷设下酶烧簿豹提取。秘为靖予复 杂系统来说，般对于真实对象的完全描述是不可能的，这里在假设条件下的 娥模规律测试魁对于真实对蒙的逼近，而且一般说来，它可以替代濉以实现的 捺理过程。付出的伐挽是对予真实对蒙模 茧l 熬不穗确黢。 在复杂适磁系统鬓论黥发展中，圭簧核心是可诗冀经济理论，窀更加裙确 的要求抽象智能体人工认知特征的理论糖础。不难看出，可计算经济理论在发 展的进程中有很多和计算镏能相通交叉的地方，甚至照源于计算错能的。但是 镑对经济系统巾核心豹特镊，在入静 # 搦因素数学接述趣题麴鳃块上，可计算 经济模型在人工认知数学摸篷方向上 l ；i 乎滋震静侠一悠。 2 2 。4 复杂网络系统的计算智能应用 逛足年，对予软诗算亵餐缝侮孛魏纛瓣邑经开展粒寒，特裂夜僖怠整雾逐 渐深入至1 人们的生活之中时。对于计算机嘲络技术的歼发应用中，人们就很早 用到智能体的概念，尽管只是限于规则决策。当软计辣作为智能体的思想方法 对，鼹络世冕将会出现一个崭薪的发展。王程复杂系统对手人工认知方法的应 鹰需求已经蠢澎显露。 喻尔滨理工大学t 掌硕上学位论文 在多智能体系统中，褒没有中心控翩器傍援下，锷戆傣在是部镶息露不是 龛筠信怠的蕊璐上自组绞生存。多智能傣的交互褥为弓l 起了整个系统行兔靛 “涌现”模式，攘个系统的行为是不能通过单个智能体的行为简单的预测出来 的”“。 实骣土惠予计冀秘技术粒发震，多餐熊蓓建模豹方法基经较为黢型。软计 冀在智稚体的设计上超舞了整要静作用。为了更好的解决智能体的行为模型， 尤其是智能体悯的交互发，土_ 在不精确、不确定和部分真实的环境中时，软计算 方法起到了很好的效果”“。 奁_ 王覆领域，是辜毒威效豹嫠敦诗雾秘多餐麓搭方法槎续合。簸群往诬算 法( a c o ) 是多籍能体与较计算结合的一个很好的例子。蚁群优纯爨法是一种 群集智能算法，它是基于自然界中的真实蚁群的行为的”“1 。自然界中的蚁群 能够在食物源岛蚁巢之间找到一条最短路经，不是依靠可见的视赞线索而是通 避它稻矮器敖趱豹一秘称笼髂塞素魏耽攀黪震“”。鹅蚁在运动过稷巾戆够慧翔 信息素的存在及其强度，并以此知道自醋的运动方向，蚂蚁倾向予朝着信息素 强度高的方向移动。因此，由大量蚂蚁组成的蚁群的行为便表现出种信息的 睚反馈现象：巢一路径上庇过豹蚂蚁越多，则后来糟选择该路径的概率就越 大。瓣簸之阕簸楚逶过这秘绥慧翁交滚寒遮弱援素食秘羽嚣熬“”。受聚上覆这 种真实蚂蚁的行为的启迪，就产生了蚁群优化算法。谯算法中，一缀人工蚂蚁 通过人工信息索间接的交换信息来进行食作。这种人工信息素通过种学习机 制在行程对阕内被积聚起来，这种学习擞铡可以绘好的解决方寨以奖殿“”。由 魏霹疆看盘，该算法不莰翻蠲了委反渎淼壤，在一定稳度上爵滚热侠进琵过 稷，而且是一种本质劳行的算法，不同个体( a g e n t ) 之间不断进行信息交流 和传递，从而能够相互协作，有利于发现较好的解。遮种算法可以解释为一种 特殊的增强学习( r l ：r e i n f o r e c e m e n tl e a r n i n g ) 算法“。增强学魂算法的 掇凼拜了在多餐能体瑾论中旋用久工诀鲡豹先溽。 2 3 本章小绪 诗舞誊巍帮软诗算，稠辩子疆诗冀褥套，黠不糖确、不确定藕瀑分寞实有 一定程度的宽容，这就为模拟真实世界不确定情况下的宙糊性和人类思想提供 了很好的机会，计算智能体现了人工认知的基本特征。 多智能体技术为软计算话楚算法在复杂系统中发拇绍雳镳平了邀路。在复 杂适应系统牵，霹诗算模蘩怒构造智髓侮与环境之阕豹鸯逶疲穰锻瓣数学菇 述。 瑶静在工程系统孛，入铝邕经舜娥兼浚较诗冀与多智瑟髂技零的结台，释 用软计算的方法来设计智自体。工程系统中的q 一学习就是这样的辣法。 嗡尔滨理工大学z 学硕士学位论文 第3 章可计算学习 增强学习锋法概念的提出应该说是在计算智能发展的基础上又前进一大 步，毽受它可黻把嚣蔻诗葵餐能矮装豹瑟算法壤摇超慕。 增强学习算法实际上和b p c t 算法中的c t 算法脊异曲同工之处。可默看 出，在增强学习的蚁群优化簿法中，人工蚂蚁的行为就是沿某路襁上行进，而 行为的效果就熄它所遗留下来的人工信息索，后面的蚂蚁根据遗燃的信息素的 多少帮行为效浆鹣磐嚣来决定蠢已兹嚣麓，这耱恕翳簸懿行秀依羧瓣予琢凌变 化出的行为散采，而这种行为的效果连接着环境中的诸多蚂蚁的行为。这种行 为和效果的一致性正是c t 算法的精髓，也是刺激反映原则的一种麒体实现。 遮乖争蚁群优化簿法后来被废罔到复杂网络闯题中用寒聪决路由问题，即蚂蚁网 缀爨囊雾法( a n t n e t ) 。在a n t n e t 孛，黼样澄弱速耱增强学习瓿翻塞僮餐蔻侮 即人工蚂蚁更快的找到从源节点到目的节点之间的最缀路径。 我们并不魑仅仅关注尽快有效的找剥计算智能的实现方法，问题的焦点在 予翔何认识人工智能的可计算学习的特缎，从损本上说蹙如 可去构建计算智能 方法。 3 1 如何构建可计算学习 这重爨浚豹霹诗雾学骂就是在餐黥髂瓣篾爨移交囊算法串，逶过缡程梅建 对于环境的自懑应、自组缓和自学习行为。 关于学习问题，人们融经研究很久，但是在多智熊体环境下，这个问题本 痨就是具有吸弓| 力和剖薪意义的。我们想知道豹是在多智能体环麓下豹学习的 主要关键特援蹩舒么，学习在多簪髭俸建模静耀个繇警士可懿发箨有效筠终 用，描述这种学习特征的结构是什么以及如何把软计黧的诸多特征脊机结合在 一个智能体的鲜法中。关于这种新的学习特征可以从以下几个方面说明。 第一个方灏是优豫交亘食谗。在多糍熊钵丽境下以选择对哪个爆节进行控 籁静 乍瑶最强佟为基本窭发点，困秀获涌溪考虑，在遥警条俘下静涌现可戳魄 个体效益累加和高出很多，所以为获得总体效益最大的捷径就是促成涌现。因 此优化合作问题已经被提到学习的核心部分地位上来。 我识豹嚣粒是设计出戆够遴毒亍有效豹交互豹是动纯罄戆 奉。2 够帮助内部 麓麓体合作的麓要能力是蘩予交流稻折巾的观点。霞为多智熊体技术的重要性 暗尔滨理工大学：r 学硕士学位论文 蠢可能提寒，避过毯纯交鬣，我织可以农台搏方嚣逡嚣援毫，也可以褥到一个 离质量的调度寝“。 那么应该如何构建优化交互方式? 归纳起来可以出两种方式：博弈和自适 应交互方式。 注意鬟餐能髂之闲夔交互终臻是鼹经慈髂灞现夔关键嚣素。瑟喜莞数交互穆 用简单的理解为多方之间的相互作用，为清晰超觅，交互作用的数学描述可以 归为两种方案，一种就是简单的双方博弈，另一种魑个体对于环境的自适应和 囱组织过程，在复杂适应系统中称为环境一规则一智能体e r a 方案。对于由所有 黪餐爱薅秘或熬嚣凌纛言，妇果篱摹缓浚每令鏊毙髂瓣予整夺强凌戆交互偌嚣l 贝能通过与其它的智能体的交互来完成，那么这两种方案并没有本质的区别。 提出两种方案对于建模框架构思和仿真编程会方便许多。特别的是学习是 遴过交互作用宪成的，两耪交互作用的方察就出现鼹茅申风格完全不阉的可计算 举习冀法。 第二个方麟是在交互谈判中的基本骚素。这里先从博弈方式谈起。交互谈 削的三要素悬自身利益评价指标、刺激反应原理和历史经验积累。 要素一：蠢身剩盏评价指标。对交互谈判( n e g o t i a t i o n ) 麴定义，已 经被讨谂了缀多次，藿这个术语本身酶意思还不蹩缀鞠确“。不翳确戆覆困在 于如何进行特征提取。为达到总体效益的提高这一目标，我们要讨论能够达成 这个目标的可能的最好的方法，和在执行过程中所包禽的问题。这种策略包含 撼学习集中在麓能体自身瓣穰念上移将掰计算方法和溯糖兹行为本性鞠结合。 蕊本程点藏怒一个学习餐麓体髓够对它辩处的环境和獒它智麓钵酶策珞避行学 习并适应，用最好的可行的方法去反作用，并使它自身的效益最大化。因此， 我们可以看出自身利益( s e l fi n t e r e s t ) 的基础仍然是很明鼹的，只是智 熊体露应霜戆到达