（计算机应用技术专业论文）改进群体智能算法及其在背包问题中的应用.pdf

山东大学硕士学位论文 摘要 随着人类社会、经济和科学技术的飞速发展，许多复杂性、非线性、 庞大巨系统和快速反应性系统等方面的问题大量呈现在人们的面前，传 统的优化方法逐渐陷入困境这时，自然界中那些群居的简单生物表现 出来的复杂的群体智慧给人们很好的启迪这些生物群体中每一个个体 的行为都很简单，也没有受到集中统一的指挥，但它们之间的有机协调 和自组织能力，却使得整个群体表现出高度的智慧，能够完成非常复杂 的任务这种现象吸引了众多学者的关注，去深入研究在现象背后存在 的机理，并通过计算机模拟其中可循的规律，用来指导和解决传统方法 难以解决的实际问题 目前通过模拟生物群体的行为来解决优化问题已经成为优化领域新 的研究热点，并已经在一些实际应用领域取得突破性的进展其中有代 表性的有意大利学者m a r c od o “g o 于1 9 9 1 年提出的蚁群优化方法和 1 9 9 5 年j a m e sk e n n e d y 和r u s s e l le b e r h a r t 基于对鸟群、鱼群捕食行为 的模拟，提出了粒子群优化方法由于这些方法概念简明、实现方便， 特别用以解决复杂的组合优化问题具有优越性，迅速得到国际优化计算 领域的认可，并在工程设计、生产优化等应用领域取得成功的应用 本论文重点研究了当前应用最广泛、最典型的群体智能优化方法一 一蚁群优化方法和粒子群优化方法系统深入地分析了蚁群优化算法基 本原理和对已有的n p h a r d 问题的求解过程，然后给出了改进的对背包 问题的蚁群算法此外，本文对基本粒子群算法原理作了系统深入的研 究，对n p - 难问题求解的已有工作进行了深入分析，在此基础上，设计 了一种新型的混合粒子群算法和实现步骤上述理论研究成果都通过实 际算例给出验证体现了改进算法的有效性和优越性 本文的主要创新点体现在三个方面； 一是在对基本蚁群算法原理、实现过程深入研究的基础上，为了减 囊磊& 国衙藿碥奄噶 芎镯妻t r 趸王蓼剖引海蠡磊嚣摧辩麓蔫誊冀鬟嚣嚣塑萋磊醚黧瀚 攀囊鋈塑器鲢琵瑟瑟强溺铺灏i 堇! 襄翻嚣矍葬瓣拜携懿劈静箱塑霾蓊霆 慝瑙引捌，黧蓊妻萄型并篓萄翔，磐嚣也疆韵到涮舞萄篓器骚鏊一篓慧 漫藩爨麓，淄凰醺稀鞠靖薷翼毳姜3 蓊警蔷邕篓；惩旺藕矍鞠蔷裂美霸 蕊霆一婪蚓耄霸蓊黼蕊。翻需囊薰毯篓冀薷豢嚣蓍眷麓； 圈攒熏矍黎矬醚霆蟊捌嚣馥毳霎舔鞍繇嚣羚鹞弹嚣魏联秘酗，孬錾 港一蕊粥銎翼积褥邀j 耋弱划璧蠢磊弧皤坦蓬蓊矗囊釜终墅滢基i 黉邕 撼搿塑露裂蠢露裁交萋鞫灏鞠蛙嚣蓑篓野毡鳃鹱羹；鬻嗣魈剿蕃鳇羹j 麓燮嚣菇溺翻鲴。塑萄删塑墅蓠颡南。塑醛鲞謦* n l 矍鬓翼嚣鞭避鞫剜 鬟；荔蠢魏释艘曩羹霎囊翳鑫鞭菲琵鐾。羹筹强弱蚕一蠢羹囊薹翻理篓攀 蠢奏娶骚疆褐璧阉， 蒌雾鎏蠹墼雾群塾獭引翼塞潮鬻鲤霸爨铂壁l p 鐾靛赘舞垂善夔羹篓 一一测强蠢嚣。弱羹荭强鬻翌磊鞠莲辩鬟鬟型嚣i 拍篷蘩螽鞋器疆羹鲤； 强弱霞娶鹭蠹爨娶鸯璧疆剜羽毳曦。靛鬃娶鬻i 臻凝潮鬣 i i l 晶麓羲琵 蠢嚣筵馨篓消器翼黝霎翻臻嚣蔺；翼霪冀鞫滞雾圈萋夔耄羹蓊巍藏妻， 舅警鞠嚣漤嚣澄蠹装，鬻美垂器燃懑嚣蜊啸跫嚣霸蘸嚣萄蛹鞴篓 x 山东大学硕士学位论文 o p e r a t o ra n do u t e rm u t a t i o no p e r a t o r a c c o r d i n gt ot h em i x e dm u t a t i o n ，w e g a v ean e wi n l p r o v e da i g o r i t h ma n dd e s i g n e do p e r a t i o ns t e p s 2 t h ed i s s e r t a t i o n g a v e an e wi m p r o v e dp s oa l g o r i t h mw h i c h i n t r o d u c e dc r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o ro fg a w ec a ng e tt h e n e wf i t n e s sv a l u ef r o mc r o s s o v e r i n go ft h ec u r r e n tf i t n e s sv a l u e ， t h e i n d i v i d u a lf i t n e s sv a l u ea n dt h eg l o b a lf i t n e s sv a l u e ，t h en e x ts t e pi st h e m u t a t i o no p e r a t e r i nt h ec o u r s eo fc r o s s o v e r ，w eu s ed a v i s sm e t h o do f s e q u e n c ec r o s s o v er ，b e s i d e st h i sw ea d o p tr e v e r s em u t a t i o ni nt h em u t a t i o n s t e p o nt h eb a s i so ft h i s ，w eo b t a i n e dan e wh y b “dp s oa l g o r i m ma n d o p e r a t i o ns t e p s 3 t h ei m p r o v e dt w os w a r mi n t e l l i g e n c ea l g o r i t h m sa r eu s e dt os o l v e t h et y p i c a ln p h a r dp r o b l e m t h ek n a p s a c kp r o b i e mw eg o tb e t t e rr e s u l t t h r o u g ht h ep r a c t i c a ln u m e r i c a ie x a m p l e s ，i tp r o v e dt ob ee f f e c t i v ea n d a s c e n d a n ti ns o i v i n gt h i sp r o b l e m t h i sp a p e ri n t r o d u c e dt h eo p “m a lv a l u e t h e o r e ma b o u tt h ek n a p s a c kp r o b l e mb yd a n t z i gt ot h ei m p r o v e dp s 0 ，f r o m t h a t ，w eg o tt h eb o u n d a r yo ft h ef i 协e s sv a l u e ，a n dg a v eu st h eb e t t e r c o n d i t i o nt oe l i m i n a t en o n - o p t i l n a ls o l u t i o n s i n c et h ek n a p s a c kp r o b l e mi s r e p r e s e n t a t i v ea n do c c u p i e sa ni m p o n a n tp o s i t i o n ， t h en e wa l g o r i t h m s w h i c ht h ed i s s e r t a t i o np r o p o s e dh a sc o n s i d e r a b l et h e o r e t i c a ls i g n i f i c a n c e a n dp r a c t i c a lm e a n i n g k e yw o r d s ： s w a r mi n t e l l i g e n c e ；a n tc o i o n yo p t i m i z a t i o n ； p a r t i c l es w a r mo p “m i z a t i o n ；k n a p s a c kp r o b i e m 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：= 衅 日 期：二坦呸血 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：也谴4 丝导师签名： 日期：丝! 垒：1 7 山东大学硕士学位论文 第1 章绪论 自从第二次世界大战以来，传统的优化方法( 如线性规划、非线性 规划、多目标规划、随机规划、排队论、库存论、对策论、决策论等) 不仅在理论上有了深入的发展，而且在军事、经济、城市建设、生产计 划、最优设计等应用方面取得显著成就随着人类社会、经济和科学技 术的飞速发展，许多复杂性、非线性、庞大巨系统和快速反应性系统等 方面的问题大量呈现在人们的面前，传统的优化方法逐渐陷入困境 群体智能是指一种通过大量数目的智能群体来实现的智能方式作 为实现群体智能的每一个个体，它的功能相对于整个问题求解来说是有 限的，甚至是极其有限的每个智能个体在整个智能系统中只能实现总 体功能的某个子集在解决优化问题时，虽然能构成寻优问题的解答， 但往往是非全局最优的解答作为智能个体本身，在没有得到智能群体 的总体信息反馈的时候，它在解空间中的运动是完全没有规律的只有 在受到其他智能体在解空间中行进方式的影响之后，每个智能个体才能 表现出在解空间中具有寻优特征的行进状态当然，作为智能个体，其 定义本身就是相对的，其大小和功能要根据所求解的问题而定并且， 每个智能个体，即使处于合理的寻优进程之中，它的个体动态也并不能 保证在每个时刻都具有最佳的寻优收敛特征，其智能寻优方式的实现是 通过整个智能群体的总体优化特征来实现的 蚁群算法作为群体智能的典型实现，是基于种群寻优的启发式搜索 算法，它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁 穴至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之 山东大学硕士学位论文 间的相似性，得到了具有n p 难度的旅行商问题的最优解答同时该算法 还被用于求解j o b s h o p 调度问题、二次指派问题以及背包问题等，显示 了其适用于组合优化类问题求解的优越特征蚁群算法之所以能引起相 关领域研究者的注意，是因为该种求解模式能将问题求解的快速性、全 局优化特征以及有限时间内答案的合理性结合起来其中寻优的快速性 是通过正反馈式的早熟性收敛，同时，具有贪婪启发式搜索特征的蚁群 系统又能在搜索过程的早期就找到可以接受的问题解答这种优越的问 题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算 法模型基础上得到了很大的改进和拓展，并被应用到了包括机器人系统、 图像处理、制造系统、车辆路径规划、通信系统、工程设计以及电力系 统在内的多种场合，解决了实际系统中的动态资源配置、数据分类等问 题【l j 粒子群算法也是一种典型的群体智能实现模式模型中个体与个体、 个体与其所处的环境的局部作用使整个群体的宏观行为表现出全局的智 能涌现行为，这种特性为许多问题的解决提供了新的方法该种求解模 式能将问题求解的分布式自组织、全局优化特征以及有限时间内答案的 合理性结合起来其中，粒子群中的微粒个体是分布式的，不存在中心 控制，能够适应当前网络环境下的工作状态，并且具有较强的鲁棒性， 另外，分布式计算的特征又避免了算法的早熟性收敛，同时，具有协同 启发式搜索特征的粒子群系统又能在搜索过程的早期就找到可以接受的 问题解答这种优越的问题分布式求解模式经研究者努力已经在最初的 算法模型基础上得到很大改进，并被应用到了工程设计和优化、电力系 统、机器人路径规划与导航、工业生产过程优化以及计算机和通讯等领 域粒子群算法具有无集中控制、多代理机制、算法结构简单、并行性 2 山东大学硕士学位论文 以及容易理解和实现等突出优点【2 】 由于群体智能方法的研究才有十余年的历史，还处于发展阶段无 论是在理论方面还是在算法设计方面都有待于丰富和完善在应用方面 也有待于迸一步开阔和深入尽管如此，目前蚁群优化方法和粒子群优 化方法已经成为组合优化和复杂性计算领域最活跃、最具潜力的群体智 能算法，也成为众多学者和应用人员研究的热点 本文共分7 章，重点研究了当前应用最广泛、最典型的群智能优化 方法一一蚁群优化方法和粒子群优化方法对这些方法的机理、特点、 算法构造进行了深入分析，提出了改进方案，并将改进方案应用于典型 的组合优化问题一一背包问题，验证了改进算法的有效性和优越性其 中第1 章介绍了群体智能算法的研究现状第2 章从总体上介绍了群体 智能算法的有关概念，分析了群体智能算法的特点第3 章对基本蚁群 算法作了分析主要分析了基本蚁群算法的生物学原理，对基本蚂蚁群 体智能的模拟，基本蚁群算法的实现过程、数学模型及对t s p 问题求解 模式，对基本蚁群算法进行了复杂性分析，阐述了蚁群算法研究的进 展第4 章提出了对蚁群算法的改进方案，分析了改进蚁群算法的思路 和依据，设计了改进蚁群算法的步骤对改进蚁群算法的应用效果进行 了研究介绍了典型的组合优化问题一一背包问题的实际背景、数学模 型，并将改进蚁群算法应用于求解背包问题中，通过数值算例显示了改 进算法的有效性和与基本蚁群算法相比较表现出来的优越性第5 章对 基本粒子群算法进了分析阐述了基本粒子群算法的生物学原理和对基 本粒子群体智能的模拟，分析了基本粒子群算法的实现过程、算法的数 学模型及对t s p 问题的求解，简单综述了基本粒子群算法研究的进展第 3 山东大学硕士学位论文 6 章在研究了基本粒子群算法机理的基础上，设计了一种新型的混合粒 子群算法，并将这种新的算法用于求解背包问题，通过数值算例显示了 改进算法的有效性和优越性第7 章对全文进行了总结提出了今后需 要进一步研究的问题 4 山东大学硕士学位论文 第2 章群体智能算法 本章主要介绍群体智能算法产生的背景、群体智能算法的基本概念、 群体智能系统的主要特点 2 1 群体智能算法产生的背景 2 0 世纪5 0 年代中期人们创立了仿生学，人们从生物进化的机理中 受到启发提出了许多用以解决复杂优化问题的新方法，如进化规划、 进化策略、遗传算法等，这些算法成功地解决了一些实际问题 群智能理论研究领域有两种主要的算法：蚁群算法( a n tc o l o n y 0 p t i m i z a t i o n ，a c o ) 和微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 前 者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问 题微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅 食的过程，但后来发现它是一种很好的优化工具 自2 0 世纪9 0 年代以来，随着计算机应用技术的迅速发展和对高效 优化技术的更高需求，人们通过模拟生物群体的行为来解决优化问题已 经成为优化领域新的研究热点，形成了以群体智能为核心的理论体系， 并已经在一些实际应用领域取得突破性的进展意大利学者m a r c o d o “g o 于1 9 9 1 年从生物进化的机理中受到启发，通过模拟蚂蚁的觅食行 为提出了第一个蚁群优化方法【3 1 用该方法求解t s p 问题、分配问题、 j o b - s h o p 调度问题，取得了较好的试验结果虽然研究时间不长，但是现 在的研究显示出，蚁群算法在求解复杂优化问题( 特别是离散优化问题) 方面有一定优势，表明它是一种有发展前景的算法这种方法能够被用 山东大学硕士学位论文 体智能行为的智能计算或优化方法称为群体智能算法群体智能是一种 在自然界生物群体所表现出的智能现象启发下提出的人工智能模式，是 对简单生物群体的智能涌现现象的具体模式研究 群体智能中的群体( s w a r m ) 指的是“一组相互之间可以进行直接通信 或者间接通信( 通过改变局部环境) 的主体，这组主体能够合作进行分布 问题求解”而所谓群体智能指的是“无智能的主体通过合作表现出智能 行为的特性” 群体智能的核心是由众多简单个体组成的群体能够通过相互之间的 简单合作来实现某一较复杂的功能，完成某一较复杂的任务所以群体 智能可以在没有集中控制并且缺少全局信息和模型的前提下，为解决复 杂的分布式问题提供了可能 1 9 9 4 年著名学者m i l l o n a s 提出了群体智能应遵循的五条基本原则 【2 l ： 1 相似性原则( p r o x i m i t yp “n c i p l e ) ： 群体能够进行简单相似的空 间和时间计算 2 品质响应原则( q u a l 埘p r i n c i p l e ) ：群体能够对环境中的各类品 质因子作出响应 3 多样性反应原则( p r i n c i p l eo f d i v e r s er e s p o n s e ) ：群体的行动和 响应范围不应太窄 4 稳定性原则( s t a b i l i t yp r i n c i p l e ) ：群体不应在每次环境变化时都 改变自身的行为 5 适应性原则( a d a p t a b i l i t yp f i n c i p l e ) ：在能够接受的计算代价内， 群体必须能够在适当的时候合理改变自身的行为 山东大学硕士学位论文 2 3 群体智能系统的主要特点 不少传统的优化方法在搜索最优解时往往利用目标函数和约束函数 的梯度信息( 函数连续可导时) 或次梯度信息( 函数不可微时) 构造搜 索方向，而群体智能算法依靠的是概率随机搜索的方法虽然概率搜索 算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相 比，其优点还是显著的另外，根据m i l l o n a s 提出的原则，实现群体智 能的智能个体必须能够在环境中表现出自主性、反应性、学习性和自适 应性等智能特性群体智能比较突出的特点有以下几方面： 1 简单性( s i m p i c i t y ) 在群体智能系统中每个个体的能力十分简单，每个个体只能感知局 部信息，不能直接拥有全局信息，对个体的模拟易于实现且执行时间比 较短在算法实现中其数据处理过程对c p u 和内存的要求也不高而且， 这种方法只需目标函数的输出值，而无需其梯度信息，易于实现这样 当系统中个体增加时相应的系统需新增加的通信量也较小，从而系统具 有简单性虽然每个个体简单，但整个群体却表现为高度协调化的社会 组织，在许多情况下能完成远远超过个体能力的复杂任务 2 分布式( d i8 t r b u t e d ) 群体智能系统中相互合作的个体是分布式的，可以是均匀分布，也 可以是非均匀分布或其他随机分布整个群体没有中心的控制，而是通 过自组织，涌现出群体的总体特征这样更能够适应网络环境下的工作 状态，符合一些复杂系统的实际演变状况同时，这种并行分布式算法 模型，还可以充分利用多处理器 山东大学硕士学位论文 3 鲁棒性( r o b u 8 t ) 由于群体智能系统中的个体是分布式的，无集中控制约束，加之个 体对整体系统的影响力较小，系统不会由于某一个或者几个个体的故障 而影响整个问题的求解因此系统具有较强的鲁棒性 4 易扩展性( s c a l a b ii t y ) 群体智能系统可以不通过个体之间直接通信而是通过非直接的信息 交流方式进行合作，即通过个体当前所在的小环境作为媒介进行合作， 具有自组织性因此这样的系统具有更好的可扩展性 5 广泛的适用性( a p p l c a b j i ；t y ) 由于群体智能算法对问题定义的连续性无特殊要求，不仅在处理组 合 优化问题方面有突出的优越性，而且对于连续性问题也可以通过离散化 的手段进行处理在处理问题的规模上也没有限制，相反问题规模越大 越能显示群体智能算法的优越性另外，群体智能算法对问题的结构化 要求不高，可以处理半结构化以及非结构化的问题因此在处理的问题 方面，具有广泛的适用性 群体智能系统的上述优良品质奠定了这一领域的发展潜力 最早关于群体智能的研究是c r a i g r e y n o i d s 在1 9 8 6 年所提出的一个 用于模拟鸟类聚集飞行行为的仿真模型b o i d 该模型通过对现实世界中 这些群体运动的观察，在计算机中复制和重建了这些运动轨迹，对这些 运动进行抽象建模，以发现新的运动模式 目前，对群体智能的研究尚处于初级阶段，但由于其所具有的分布 9 山东大学硕士学位论文 图3 1 蚁群算法原理示意图 当某只蚂蚁觅到食物后，一般沿原路回巢，同时在归途上留下信息 素设a 点为巢穴，食物在d 点若有第一、第二两只蚂蚁分别沿路 a b d 和a c d 同时出发，随后都找到食物，且沿原路返回( 见图3 ，1 ) 因a b d 比a c d 短，当第一只蚂蚁沿a b d 回到巢穴a 点时，第二 只蚂蚁( 沿d c a 的蚂蚁) 才回到c 点于是a b d 路上有两次信息素的 遗留物( 去一次、回来一次) ，而在a c 路上只有去一次的信息素遗留物， 放a b 的信息素浓度比a c 上的浓度大因为后面的蚂蚁一般会沿信息 素浓度大的路径前行，于是后面的蚂蚁会渐渐地沿着由a 到b 的路到达 d 点，如果从a 到d 有多条路的话，根据这一原理，越短的路径会被越 来越多的蚂蚁访问，信息素浓度也就越来越大，极限情况是所有的蚂蚁 最终会集中到由a 经过b 再到d 的最短路上以上就是蚂蚁能找到最短 路进行搬运食物的原理 g o s s 等人做了一种“双桥实验”并给出数学模型【5 1 ： 设有埘只蚂蚁a 、b 分别表示长桥和短桥，彳。和曰。分别表示其上的 蚂蚁数目，并且爿。+ b 。= 埘当所有埘只蚂蚁都经过两桥后，第小+ 1 只蚂 蚁选择桥a 的概率为； 柏+ 1 ) = 雨 山东大学硕士学位论文 选择桥b 的概率为： b ( m + 1 ) = 1 一只( 川+ 1 ) 其中， 和七是经验数据，是与真实情况有关的参数 第肼+ 1 只蚂蚁首先计算只似+ 1 ) ，然后生成一个【o ，l 】中均匀分布的随 机数f ，若f 只+ 1 ) ，则选择桥a ，否则选择桥b 3 2 基本蚂蚁群体智能的模拟 对基本蚂蚁群体智能的人工模拟，目的是为了更加有效地刻划出真 实蚁群中能够为算法所借鉴的机理，同时摒弃与建立算法模型无关的因 素人工蚂蚁可看成一个简单的智能体，能够完成所求问题简单解的构 造过程，也能通过一种通信手段相互影响，根据上述生物学原理模拟出 人工蚂蚁群体，并设计出寻求最短路的“蚂蚁算法”模拟过程的主要环 节有以下几点： 1 ) 首先要模拟在一个群体中个体之间相互交流的通信机制，个体之 间实际是通过改变和感知当前所处环境的机制来实现通信交流的真实 蚂蚁在经过的路径中可以留下信息素，那么人工蚂蚁相应的就应该能够 改变其所经路径上存储的数字信息，该信息就是算法中所定义的信息 量这一信息量记录了蚂蚁当前解和历史解的性能状态，而且可被其他 后继人工蚂蚁读写这种交流方式改变了当前蚂蚁所经路径周围的环境， 同时以函数的形式改变了整个蚊群所存储的历史信息 2 ) 在蚁群寻食过程中有一个信息素的挥发机制这样在入工蚁群中 也应当设计这样一个机制它像真实的信息量挥发一样随着时间的推移 来改变路径上的信息量这种挥发机制可以使蚂蚁忘却历史信息，选择 山东大学硕士学位论文 路径时不局限于以前蚂蚁所存留的经验这种机制也在一定程度上，有 利于淘汰掉非最短的路径 3 ) 为了找到并纪录从源点到目的点的最短路径，设定人工蚂蚁和真 实蚂蚁都不具备跳跃性，只能在相邻节点之间一步步移动为了能在多 次寻路过程中找到最短路径，需要记录当前的移动序列 4 ) 在蚂蚁的路径选择上，利用当前信息进行路径选择的随机选择策 略蚂蚁从某一节点到下一节点的移动都是利用概率选择策略来实现而 且概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来 的信息所使用的选择策略在时间上、空间上都是局部的 5 ) 人工蚂蚁也可以不局限于实际的蚁群而有自己的特点比如可以 在一个离散的空间中，其移动是从一个状态到另一个状态的转换可以 有一定的记忆能力，能记忆已经访问过的节点即具有一个记忆其本身 过去行为的内在状态可以使人工蚁群存在于一个与时间无关联的环境 之中在选择下一条路径的时候可以不是完全盲目的，而是根据问题空 间特征的启发按一定的算法规律有意识地去寻找例如有时在产生一个 解后改变信息量；有时每作出一步选择就更改信息量等 6 ) 可以给人工蚁群增加一些其它性能，如利用对未来预测的信息、 局 部优化、回退等性能人工蚂蚁也可在局部优化过程中相互交换信息这 些特点，为人工蚁群的改进，提高执行最优化过程的性能，留有较大的 空间 3 3 基本蚁群算法的实现过程 首先对于解空间的抽象是将真实的三维空间抽象成一个二维解空间 1 4 山东大学硕士学位论文 ( 平面或酋面) ，将真实蚂蚁活动的连续二维平面离散为人工蚂蚁活动的 离散平面因此，常常把蚁群算法所求解的问题空间用由节点和与其相 关联的边构成的“图”来描述 对于真实蚂蚁觅食过程抽象为算法中解的构造过程，将信息素抽象 为存在于图的边上的轨迹在每个节点，人工蚂蚁感知连接该节点与相 邻节点边上的信息素轨迹浓度，并根据该浓度决定走向下一节点的概率 蚂蚁觅食过程中信息素的挥发是随时间的推移连续发生的，为了处 理的方便将这一过程离散化，通常的做法是当蚂蚁完成从某一节点到下 一节点的移动后，即经过个时间单位之后，进行一次信息素的挥发 真实蚁群觅食过程具有自组织性，但这种自组织系统存在一个缺陷 就是系统演化的时间较长人工蚂蚁的模拟过程要体现系统的这种自组 织性，因此在决定蚂蚁行走方向的状态转移概率时，引入一个随机搜索 的过程一一启发因子，根据所求问题空间的具体特征，给蚁群算法一个 初始的引导，这个过程可以极大地增加算法的时间有效性在解的构造 过程中人工蚂蚁没有接受任何全局的指导信息，因而求解过程是自组织 的蚂蚁个体通过随机决策机制和相互协调机制可自适应地作出并完成 自身评价 这样。蚁群算法具有很强的自学习能力，它可以根据环境的改变和 过去的行为结果对自身的知识库或自身的组织结构进行再组织，实现了 算法求解能力的进化这种进化是环境变化与算法自学能力交互作用的 产物 在定义了上述规则之后，人工蚂蚁就可求解那些可用图来描述的求 解问题但是，由于算法机理的复杂性和环境变化的不确定性，也进一 步增加了蚁群算法的不可预测性 山东大学硕士学位论文 基本蚁群算法的逻辑过程可以归纳如下；【6 儿7 】 ( 1 ) 初始化蚁群 ( 2 ) 根据目标函数对每只蚂蚁的适应度作一评价 ( 3 ) 释放信息素根据适应度，对蚂蚁所经过的路径按一定的比例 释放信息素，适应度越高，所释放的信息素越多 ( 4 ) 蚂蚁移动蚂蚁依据前面蚂蚁所留下的信息素和自己的判断选 择路径 ( 5 ) 信息素的挥发信息素会随着时间不断消散 3 4 基本蚁群算法的数学模型及对t s p 问题求解 为了- 更好地剖析基本蚁群算法，以便于研究可改进之处，特别通过 对t s p 问题的求解，分析其实现过程 设c = 如，乞，) 是”个城市的集合，工= 以h ，o6 c ) 是集合c 中 元素( 城市) 两两连接的边的集合，d = 办k 工) 是连接城市f 和城市_ ，的 边0 的长度集合，即城市f 和_ ，之间的e u c l i d e 锄距离； 略= 厄i 再而 其中( 薯，儿) 和( 0 ，乃) 分别为城市f 和，的位置坐标( 不妨假设在平面内) ， g = ( c ，上，d ) 是一个赋权有向图t s p 的目的是从有向图g 中寻出长度最 短的h a m i l t o n 圈，此即一条对c 中甩个元素( 城市) 访问且只访问一次的 最短封闭路线 t s p 分为对称t s p 和非对称t s p 两大类，若两城市往返的距离相同， 则为对称t s p ，否则为非对称t s p t s p 的已知数据包括一个有限完全 山东大学硕士学位论文 中这些信息素信息对蚂蚁未来的搜索有指导作用 基本蚁群算法对t s p 问题的描述与求解如下： 设6 t ( f ) 表示f 时刻位于元素( 城市) f 的蚂蚁数目，勺( f ) 为f 时刻 连接城市c ，和城市q 的路径，上的信息量，一= i c i 表示t s p 的规模，即 城市的个数肌为蚁群中蚂蚁的总数目，则：m = 包( f ) 厂( f ) = 勺( f ) b ，o c ) 是f 时刻集合c 中元素( 城市) 两两连接0 上残留信息量的集合初始时 刻各条路径上的信息量相等，给定一个初值即勺( o ) = c 删f ，v 勺( o ) 厂( o ) 基本蚁群算法的寻优通过赋权有向图g = ( c ，厶厂) 实现 蚂蚁七( 后= 1 ，2 ，肼) ，在运动过程中，根据各条路径上的信息量决定 其转移的方向这里用禁忌表t a b u ( _ | = 1 ，2 ，肼) 来记录蚂蚁后当前走过的 城市集合，集合随着t a b u 进化过程作动态调整 在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来 计算状态转移概率 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁 走完一步或者完成对所有撑个城市的遍历( 一个循环结束) 后，要对残留 信息进行更新处理这种更新策略模仿了人类大脑记忆的特点，在新信 息不断存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡 化，甚至忘记 在f + 胛时刻，路径勺上的信息量按如下规则进行处理： 勺o + ，1 ) = ( 1 一力。勺( f ) + 4 勺( r ) 山东大学硕士学位论文 钙( f ) = 4 ( f ) 其中，p 表示信息素挥发因子，则1 一矿表示信息素残留因子，为了防止 信息的无限积累，p 取值范围为【0 ，1 ) 4 勺( f ) 表示本次循环中路径( f ) 上的信息素增量，初始时刻为4 f ，( o ) = o 4 ，“( f ) 表示第七只蚂蚁在本次循环中留在路径上的信息量 d o r i g om 提出了三种不同的基本蚁群算法模型： a n t c y c l e 模型 a n t q u a n t i t y 模型 a n t d e n s i 锣模型 三者的差别在于a t ( f ) 求法的不同 信息素更新策略1 a n t - c y c l e 模型： t ( f ) ： 罢，若第青只蚂蚁在本次循环中经过。，p i o ， 否则 其中： q 表示信息素强度，它在一定程度上影响算法的收敛速度； 工t 表示第七只蚂蚁在本次循环中所走路径的总长度 信息素更新策略2 a n t q u a n t i t y 模型： 瑚r ) - 悟若第枳蚂蚁在f 辄“之间经过) l o ，否则 其中： q 表示信息素强度，它在一定程度上影响算法的收敛速度； 山东大学硕士学位论文 九表示城市f 栅之间的距离 信息素更新策略3 a n t d e n s i t y 模型： 蜘= 忙裟坝燃机机“加绁以力 其中： q 表示信息素强度，它在一定程度上影响算法的收敛速度 第一种策略中，( 舭t ) 利用整体信息，即当蚂蚁完成了自己的行程 后才更新所有路径上的信息素而且每个蚂蚁所释放的信息素被表达为 反映相应行程质量的函数 第二种策略中，( q 肘“) 和第三种策略中( q ) 利用局部信息，即蚂蚁完成一步后更新路径上的信息素 通过与其它各种通用的启发式算法相比，在不大于7 5 个城市的t s p 问题中，这三种基本算法的求解能力还是比较理想的基本蚁群算法的实现步骤如下： 1 ) 参数初始化，令时间f = 0 和循环次数肌= o ，设置最大循环次数 c m 口x ，将肌只蚂蚁置于拧个元素( 城市) 上，令有向图上每条边( 彬) 的初始化信息量( f ) 2c 。n s t ( 常数) ( 比如可取冗i ，h 为三中元素的个数) ， ( o ) 20 2 ) 循环次数n c n c + 1 3 ) 蚂蚁的禁忌表t a b u 索引号扣1 4 ) 蚂蚁数目七一后+ 1 5 ) 蚂蚁个体根据状态转移概率计算的值选择元素( 城市) g 并前进， 其中， c t a b u t 山东大学硕士学位论文 f u t u r eg e n e r a t i o nc o m p u t e rs y s t e m s ( v b l 1 6 ，n o 8 ) 和i e e e t r 柚s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ( v 0 1 6 ，n o 4 ) 分别于2 0 0 0 年和 2 0 0 2 年出版了蚁群算法的特刊 2 0 0 0 年g u t j a h r wj 首次对蚁群算法的收敛性进行了证明”1 他将蚁 群算法的行为简化为在一幅代表所求问题的有向图上的行走过程，进而 从有向图论的角度对一种改进蚁群算法图搜索蚂蚁系统 ( g r a p h b a s e da n ts y s t e m ，g b a s ) 的收敛性进行了理论分析同时还证明了 在一些合理的假设条件下，他所提出的g b a s 能以一定的概率收敛到所求 问题的最优解1 ” 我国研究有关蚁群算法的最早投出的论文是东北大学控制仿真研究 中心的张纪会博士与徐心如教授【”1 由于蚁群算法对解决规模较大问题时表现出性能下降的现象，此后， 许多学者致力于对蚁群算法的改进较早的一种改进方法是精英策略 ( e l i t i s ts t r a t e g y ) ，其思想是在算法开始后即对所有已发现的最好路径给 予额外的增强，并将随后与之对应的行程记为t g b ( 全局最优行程) ，当进 行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记 为“精英”，从而增大较好行程的选择机会这种改进型算法能够以更快 的速度获得更好的解但是若选择的精英过多则算法会由于较早的收敛 于局部次优解而导致搜索的过早停滞为了进一步克服这一问题，1 9 9 6 年，g a n b a r d e l l alm 和d o r i g om ，又提出一种称之为蚁群系统( 孤t c o l o n ys y s t e m ，a c s ) 的修正蚁群算法16 1 ，其中使用了一种非随机的状态 转移规则( s t a t et r a n s i t i o nr u l e ) 该系统的提出是以a n t - q 算法为基础 的a n t q 将蚂蚁算法和一种增强型学习算法q l e a r n i n g 有机地结合了起 山东大学硕士学位论文 来 1 9 9 9 年，吴庆洪等1 7 1 提出了具有变异特征的蚁群算法，其核心思想 是为了克服蚁群算法收敛较慢的问题，采用逆转变异方式，随机地进行 变异，以增大进化时所需的信息量这种变异机制充分利用了2 一交换法 简洁高效的特点，因而具有较快的收敛速度 目前，蚁群算法及其变异已有广泛的应用，比如运输调度问题 ( s c h e d u l i n gp r o b l e m ) 1 ”、旅行商问题【1 9 1 ( t s p ) 、连续函数优化问题2 0 ，2 1 1 、 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 2 2 ，2 3 1 、指派问题( q u a d r a t i c a s s i g n m e n tp r o b l e m ，q a p ) 2 ”、频率分配问题2 ”、机器工件排序问题2 “、 网络路由设计问题【2 7 1 等还有些研究工作，针对应用的实际问题给出 相应的算法，如h p 公司和英国电信公司设计的蚁群路由算法( a n t c o l o n y r o u t i n a c r ) 每只蚂蚁根据它在网络上的经验与性能，动态更新路由 表项如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延 迟，那么就对该表项做较大的增强根据信息索挥发机制实现系统的信 息更新，从而抛弃过期的路由信息这样，在当前最优路由出现拥堵现 象时，算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的 均衡性、负荷量和利用率有的学者针对大型光网络设计了基于蚁群算 法的分布式计算方式，克服了传统集中式算法可扩展性差的缺点，更适 应现代频繁变化的大型光网络2 8 1 因此，近年来国内外对并行的分布式 算法表现出极大的兴趣目前这方面的应用研究仍在升温，因为通信网 络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与 蚊群算法的本质和特性非常相似 山东大学硕士学位论文 在蚁群算法每一次迭代产生新的信息素浓度矩阵后，如果信息素浓 度矩阵的某一列出现过于集中的现象，则对该信息矩阵进行变异，其方 法是根据一定的概率对该列用一个随机概率向量替代，用变异后的信息 矩阵产生q 个编码，然后在这些编码中选择g 个好的编码作为父代种群进 行下一次迭代 正如在遗传算法中尽管有变异算子，但不能排除早熟现象的发生一 样，蚁群算法在引入变异算子后依然不能保证排除早熟现象，为了解决 这个问题，文献【1 2 】给出了最优个体进行变异的方法考虑到信息素在 蚁群算法中的重要性，我们下面对蚁群算法引入基于信息素的变异算 子，在蚁 群算法中引入种群入侵算子，这个算子的形式如下面算法中给出如果 我们将变异算子看作是内部的变异优化，那末种群入侵算子就被视为是 外部的变异优化，我们分别称这两种算子为内变异和外变异，这种变异 是根据信息的集中程度而决定的， 在信息矩阵中，如果某个元素的取值远远大于其所在列中其他各元 素的值，即信息素矩阵出现局部集中情况，此时需要内变异，若每一列 都出现信息集中，则需要进行外变异在实际算法中，信息的集中的程 度也可以用一个阀值来界定 4 2 改进蚁群算法的实现 设人工蚁群规模为q s t e p1 初始化 给定蚁群规模q ，父代种群规模g ，输入初始信息素矩阵口( o ) ，置f = o 山东大学硕士学位论文 给出行集中度阀值日，矩阵集中度阀值龟，内变异概率p 和外变异概率 口并根据初始信息素矩阵b ( o ) ，随机产生q 个编码，记为 4 ( o 户“( o ) 以( o ) ，以( 0 ) s t e p2 选择 计算出每个编码的目标函数和适应度，并根据适应度随机选择g 个 编码作为父代种群，判断是否满足要求，若满足，即停止，以彳( f ) 中最 好的编码为近似最优解，否则转s t e p3 s t e p3 计算新的信息量 在第，个编码中，若第f 个待定分量薯= ，令( f ) = z ( f ) ，其中 石( ，) 为t 时刻第，个编码对应的目标值；否则( f ) = o 计算信息矩阵 b ( f + 1 ) 各列的集中度和矩阵的信息度 s t e p4 内变异 若某列的集中度大于s 1 ，则产生一个随机数，若随机数小于p ，则随 机产生一个概率向量替换该列，转s t e p5 ；否则转s t e p6 s t e p5 外变异 若矩阵的集中度大于岛，则随机产生一个概率矩阵星，令 否( f + 1 ) = 口b o + 1 ) + ( 1 一口) 垦， 转s t e p7 s t e p6 产生新蚁群 根据信息素随机产生q 个编码，记为： a o + 1 ) = 4 ( f + 1 ) ，4 ( f + 1 ) ，。，如o + 1 ) 山东大学硕士学位论文 m 瓤只薯， r “ “j 善咐筑 【毛 0 ，l ，f = l 2 ，尼 二进制变量_ 用来表示物品j 是否装包， - 2 1o ， 否则 f 1 ，如果取物品， ( 4 ，1 ) 不失一般性，假定价值和重量均为正数，总重量不超过容重限制c 这一模型应用范围很广，如资金一定选择若干项目使收益最大的计 划问题、人员工作分配问题、集覆盖问题、旅行售货商问题等都可以抽 象或转化成类似模型 对于更一般的一维非线性背包问题的数学模型可表示如下： m 戥，( x ) = 乃( ) ， j = l “g ( x ) = 毋( _ ) 6 ， j = l x 工= p z ”k 叶，j = l ，2 ，一 其中 v m 一 ( 52 ) 【2 一v m 。，乏， 一。 式( 5 1 ) 中，9 6 p s 白是整个微粒群的历史最优位置纪录，其与当前微 粒的位置之差被用于改变当前微粒向群体最优值运动的增量分量，此增 量还需进行一定程度的随机化( 运用删。( ) 随机发生器) ；加p s o 是当前 微粒的历史最优位置记录，类似地它与当前微粒的位置之差也被用于该 微粒的方向性随机运动设定( m 耐：( ) 亦为随机发生器) ：，为惯性权重 ( i n e r t i aw e i g h t ) ，q ，乞为加速常数( a c c e l e r a t i o nc o n s t a n t s ) 式( 5 2 ) 中，对微粒f 的速度u