基于信息熵的异类多种群蚁群算法

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　基于信息熵的异类多种群蚁群算法　邓可１，林杰１，张鹏１，２　ＤＥＮＧ　Ｋｅ　，ＬＩＮ　Ｊｉｅ　，ＺＨＡＮＧ　Ｐｅｎｇ　’　１同济大学经济与管理学院，上海２０００９２　２．西安理工大学信息系，西安７１００４８　１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｅｃｏｎｏｍｉｃｓ＆Ｍａｎａｇｅｍｅｎｔ，Ｔｏｎｇｊｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０００９２，Ｃｈｉｎａ　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　７１００４８，Ｃｈｉｎａ　Ｅ—ｍａｉｌ：ｄｋ９４＠１６３．ＣＯＢ　ＤＥＮＧ　Ｋｅ，ＬＩＮ　Ｊｉｅ，ＺＨＡＮＧ　Ｐｅｎｇ．Ｍｕｌｔｉｐｌｅ　ｈｅｔｅｒｏｇｅｎｅｏｕｓ　ａｎｔ　ｃｏｌｏｎｉｅｓ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｅｎｔｒｏｐｙ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（３６）：１６－１９．　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｔｒｏｐｙ　Ｂａｓｅｄ　Ｍｕｈｉｐｌｅ　Ｈｅｔｅｒｏｇｅｎｅｏｕｓ　Ａｎｔ　Ｃｏｌｏｎｉｅｓ　Ａｌｇｏｒｉｔｈｍ（ＩＥＢＭＨＡＣＡ）．Ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｓ　ｍｕｈｉｐｌｅ　ｈｅｔｅｒｏｇｅｎｅｏｕｓ　ａｎｔ　ｃｏｌｏｎｉｅｓ　ｉｎ　ｓｉｍｕｌｔａｎｅｏｕｓ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｃａｌｃｕｌａｔｉｏｎ．Ｆｏｒ　ｅａｃｈ　ａｎｔ　ｃｏｌｏｎｙ，ｅｖｏｌｕｔｉｏｎ　ｄｅｇｒｅｅ　ｉｓ　ｅｘｐｒｅｓｓｅｄ　ｂｙ　ｉｎｆｏｒｍａｔｉｏｎ　ｅｎｔｒｏｐｙ，ＳＯ　ｔｈｅ　ａｎｔｓ　ｃａｎ　ａｄａｐｔｉｖｅｌｙ　ｃｈｏｏｓｅ　ｓｔｒａｔｅｇｉｅｓ　ｔｏ　ｅｘｃｈａｎｇｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｂｅｔｗｅｅｎ　ｃｏｌｏｎｉｅｓ　ｔｏ　ａｃｈｉｅｖｅ　ｄｙｎａｍｉｃ　ｅｑｕｉｌｉｂｒｉｕｍ　ｂｅｔｗｅｅｎ　ｓｏｌｕｔｉｏｎ　ｄｉｖｅｒｓｉｔｙ　ａｎｄ　ｃｏｎｖｅｒｇｅｎｃｅ　ｓｐｅｅｄ．Ｔｈｏｓｅ　ｓｔｒａｔｅｇｉｅｓ　ｉｎｃｌｕｄｅ　ｓｅｌｅｃｔｉｎｇ　ｉｆｎｏｒｍａｔｉｏｎ　ｅｘｃｈａｎｇｉｎｇ　ｏｂｊｅｃｔ，ｒｅｇｕｌａｔｉｎｇ　ｅｘｃｈａｎｇｉｎｇ　ｃｙｃｌｅ　ａｎｄ　ｕｐｄａｔｉｎｇ　ｐｈｅｒｏｍｏｎｅ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｏｎ　ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ　ｓｈｏｗ　ｔｈａｔ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ａ　ｇｏｏｄ　ｇｌｏｂａｌ　ｓｅａｒｃｈｉｎｇ　ａｂｉｌｉｔｙ，ｈｉｇｈ　ｃｏｎｖｅｒｇｅｎｃｅ　ｓｐｅｅｄ　ａｎｄ　ｓｏｌｕｔｉｏｎ　ｄｉｖｅｒｓｉｔｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｉｎｆｏｒｍａｔｉｏｎ　ｅｎｔｒｏｐｙ；ｍｕｌｔｉｐｌｅ　ｈｅｔｅｒｏｇｅｎｅｏｕｓ；ａｎｔ　ｃｏｌｏｎｉｅｓ　ａｌｇｏｒｉｔｈｍ；Ｔｒａｖｅｌ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ（ＴＳＰ）　摘要：提出了一种基于信息熵的异类多种群蚁群算法。算法使用多个异类种群的蚂蚁子群体同时进行优化计算，引入信息熵来　表示蚂蚁种群的进化程度，根据蚂蚁子群体间的信息熵来决定子群体间的信息交流策略，包括选择信息交流的对象和调节信息交　流的周期以及信息更新策略，以取得各蚂蚁子群体中解的多样性和收敛性之间的动态平衡。基于旅行商问题的实验证明，该算法　具有很好的全局搜索能力、收敛速度以及解的多样性。　关键词：信息熵；异类多种群；蚁群算法；旅行商问题　ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００８．３６。００４　文章编号：１００２—８３３１（２００８）３６—００１６—０４　文献标识码：Ａ　中图分类号：ＴＰ３０１　１引言　比采用相同总个数的单蚂蚁群体的蚁群算法收敛速度快，在问　蚁群算法是１９９２年由意大利学者Ｄｏｒｉｇｏ　Ｍ等人首先提　题规模较大时，这个优点更加突出［５－７］。目前，对于多种群蚁群算　出的，它是对蚂蚁进行模拟而得出的一种模拟进化算法，该算　法的研究主要针对同类种群的蚂蚁算法（Ｍｕｌｔｉｐｌｅ　Ｃｏｎｇｅｎｅｒ　法不依赖于具体问题的数学描述，有很强的全局优化能力和本　ａｎｔ　Ｃｏｌｏｎｉｅｓ　Ａｌｇｏｒｉｔｈｍ，ＭＣＡＣＡ）：Ｇａｍｂａｒｄｅｌｌａ　ｒｓｌ提出了专门用　质上的并行性，是解决ＮＰ一完全问题的有效方法，在求解ＴＳＰ　于解决多目标规划的基于层次结构的多蚁群算法，不同的蚁群　问题上取得了很好的结果ｌｌＩ。蚁群算法主要包括５个基本系统：　针对不同的子目标函数进行求解，蚁群间按照规则进行通信和　蚂蚁系统（Ａｎｔ　Ｓｙｓｔｅｍ，ＡＳ）、精英策略蚂蚁系统（Ａｎｔ　Ｓｙｓｔｅｍ　解交换；Ｍａｒｔｉｎ等　“　提出了子群体之间进行信息交流的４种　ｗｉｔｈ　Ｅｌｉｔｉｓｔ　Ｓｔｒａｔｅｇｙ，ＡＳＷＥＳ）、优化排序蚂蚁系统（Ｒａｎｋ—Ｂａｓｅｄ　方法，但４种方法存在共同的缺点：子群体问的信息交流缺乏　Ｖｅｒｓｉｏｎ　ｏｆ　Ａｎｔ　Ｓｙｓｔｅｍ，ＲＢＶＡＳ）、蚁群系统（Ａｎｔ　Ｃｏｌｏｎｙ　ＳｖＳ　定的导向性，不利于各子群体根据自身的进化特点选择进行　ｔｅｍ，ＡＣＳ）、最大最小蚁群系统（Ｍａｘ—Ｍｉｎ　Ａｎｔ　Ｓｙｓｔｅｍ，ＭＭＡｓ）　。　信息交流的对象。对于蚁群算法，在对全局搜索过程中，通常的　然而，单一种群的蚁群算法存在搜索时间长、易于停滞的问题。　目标是在前期有较高的探索能力以得到合适的解，而在后期有　实际上蚁群是有组织、有分工的，不同种类的蚁群有不同的信　较高的开发能力以加快收敛速度。为实现上述目标，本文将采　息素调控机制，这种分工组织方式对蚁群完成复杂任务具有重　用精英策略蚂蚁系统和优化排序蚂蚁系统作为两种蚁群的算　要意义。采用多种群的蚁群算法可使多个种群充分加速收敛，　法。这两种算法具有较强的互补性，精英策略蚂蚁系统在每次　基金项日：国家自然科学基金（ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．７０５３１０２０）；同家８６３／ＣＩＭＳ主题资助项目（Ｐｒｏ—　ｊｅｃｔ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｈｉｇｈ—Ｔｅｃｈ．Ｒ＆Ｄ　Ｐｒｏｇｒａｍ　ｆｏｒ　ＣＩＭＳ，Ｃｈｉｎａ　Ｎｏ．２００７ＡＡ０４ＺＩ５１）；新　：ｉｆｌ｛　西『＼才支持计划资助（Ｐｒｏｇｒａｍ　ｏｆｒ　Ｎｅｗ　Ｃｅｎｔｕｒｙ　Ｅｘｃｅｌｌｅｎｔ　Ｔａｌｅｎｔｓ　ｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｉｎａ　Ｎｏ．ＮＣＥＴ一０６—０３７７　ｏ　作者简介：邓可（１９７５一），男，博士，主要研究领域为系统建模与仿真、决策支持系统；林杰（１９６７一），男，教授，博士生导师，主要研究领域为系统建　模与仿真、群体智能；张鹏（１９７５～），男，博士，主要研究领域为管理信息系统。　·　收稿Ｉ：１期：２００８—０７—３１　修回Ⅱ期：２００８—１０－１３　邓可，林杰，张鹏：基于信息熵的异类多种群蚁群算法　２００８，４４（３６）　１７　循环之后给予最优解以额外的信息素量，以加快最优解的收敛　是同类蚁群，即多个种群的算法是基本相同的。多个种群在并　行求解后期容易出现停滞现象，其保持解的多样性的能力有　速度，但是弱点在于很容易过早收敛。基于优化排序的蚂蚁系　统在每次迭代后，对路径进行长度优化排序，并根据排序结果　按照路径的排名进行信息素的激励，以有效避免某些极优路径　被很多蚂蚁过分重视的情况发生，这样以减缓收敛速度的代　价，尽力避免陷入局部最优的陷阱。将这两种蚁群算法构成异　类多种群蚁群算法，充分发挥各自优势，扬长避短，有利于提高　算法性能。同时，在异类多种群的蚁群算法中，算法将根据当前　各蚂蚁种群的进化程度自适应的交换种群之间的信息素，使算　法跳出局部极值点，因此如何衡量算法是否陷人局部最优是算　限，从根本上不能有效减少早熟停滞的现象。本文中，采用具有　不同寻优策略的异类蚁群并行进行优化计算，并且根据当前各　蚂蚁种群的进化程度自适应的交换种群之间的信息素，达到避　免算法早熟的目的。　３．１信息熵　为了描述蚁群的进化程度，即各种群中蚂蚁在选择路径时　的不确定性，本文引入信息熵作为度量值。熵（Ｅｎｔｒｏｐｙ）作为热　力学概念，最早由克劳修斯提出用以描述系统的无序状态。后　法的关键。　本文提出了一种基于信息熵的异类多种群蚁群算法（Ｉｎ—　ｆｏｒｍａｔｉｏｎ　Ｅｎｔｒｏｐｙ　Ｂａｓｅｄ　Ｍｕｌｔｉｐｌｅ　Ｈｅｔｅｒｏｇｅｎｅｏｕｓ　Ａｎｔ　Ｃｏｌｏｎｉｅｓ　Ａｌｇｏｒｉｔｈｍ，ＩＥＢＭＨＡＣＡ），将蚁群划分为若干个子群体，每个种　群具有不同的信息素更新机制。运算中，用信息熵来衡量各个　种群自身的解的进化程度，根据信息熵自适应地选择种群间的　通讯策略，交换各自的最优解和信息素，完成合作和竞争，有效　地缓解蚁群算法容易早熟、停滞和收敛速度之间的矛盾。　２基本蚁群算法模型　所有的蚁群算法都是在基本蚁群算法的基础上发展起来　的，其转移概率和信息素更新机制如式（１）一（４）所示蚴。　状态转移概率　（ｔ）公式：　：（　）　ｊ＝ｄｌｏｗｅｄｋ　∑ｒ：（ｔ）　（１）　Ｅａｌｌｏｗｅｄｋ　０　ｏｔｈｅｒｗｉｓｅ　其中，ａｌｌｏｗｅｄｋ＝｛０，１，…，ｎ一１ｌ表示蚂蚁ｋ下一步允许选择的城　市；　是边（　√）上的信息素强度；　是边（　√）的能见度，ｄ　是城　市ｉ到城市　之间的距离，７／　＝１，ｄｆ　；　和１３为两个参数，分别反　映了蚂蚁在运动过程中积累的信息素和启发信息在蚂蚁路径　选择中的相对重要性。　蚂蚁完成一次循环，各路径上的信息素更新的公式：　（ｔ＋１）＝（１　）　（ｔ）＋△Ｊｒ　（　，ｔ＋１），ＰＥ（０，１）　（２）　ＡＴ　ｔ＋１）＝∑△ｔｒ　ｔ＋１）　（３）　△　？（ｔ．ｔ＋１）＝｛Ｌ　ｆ　蚂蚁ｋ在本次循环中经过路径（　．　）　（４）　【０　否则　其中，Ｐ为信息素的衰减系数；ｍ是蚁群中蚂蚁的数量；Ｑ为常　数；Ａｔ：（　，ｔ＋１）表示第ｋ只蚂蚁在（　，ｔ＋１）时刻留在（　，．　）路段上　的信息素；△　．（　，ｔ＋１）表示本次循环中路段（　）的信．息素增量。　３　基于信息熵的异类多种群蚁群算法（ＩＥＢＭＨＡＣＡ）　基本蚁群算法主要由两部分构成：选择策略和信息素更新　机制。从公式（１）中可知，选择策略的正反馈机制是造成算法易　于停滞的根本原因，而蚂蚁的选择策略直接与路径的信息素大　小相关。在算法进行的过程中，各路径的信息素大小具有不确　定性，因此，蚂蚁选择哪条路径也表现出不确定性。就全局来　看，这种不确定性越大，说明算法陷入停滞的可能性越小，反　之，算法可能出现早熟。传统的多种群蚁群算法，所用到的种群　来熵的概念被引入多个领域，申农（Ｓｈａｎｎｏｎ）将热力学熵引入　信息论提出信息熵，用于度量信息、选择的不确定性。对于离散　型随机变量，其信息熵为ｓ—ｋ　ｐ　ｌｎｐ　，其中，Ｐｉ为各状态发生　Ｅ＝１　的概率，且满足Ｐ　Ｉ＞０，　Ｐ　＝１。　‘＝１　对于给定的ＴＳＰ问题，每只蚂蚁完成一个解的构造需要进　行连续的ｎ次搜索以构成一条回路，１７，为城市节点的数目，蚂　蚁的每一步选择代表一个状态，在蚁群算法中，其状态转移概　率如公式（１）所示。设在ｔ时刻，蚂蚁　在节点ｉ的下一步路径　搜索空间为　：Ｊ∈ｄｌｏｗｅｄ　，ｄｌｏｗｅｄ￣＝ｆ０，１，…，ｎ一１｝表示蚂蚁ｋ　下一步允许选择的城市，则　：对应的概率分布为　，　Ｉ＞０，且　ＸＰｊ＝ｌ　￣＝ｌ，　为蚂蚁ｋ路径选择的概率向量。因此，可以定义蚂　蚁ｋ从状态ｉ到状态ｆ的信息熵表达式为：　ｓ：（　）＝一ｆ∑　（Ｊ　ｄ／ｏｗｄ￣　　）ｌ　（　）　（５）　上式表示在ｔ时刻，蚂蚁ｋ由状态ｉ到状态．７的不确定性。根据　公式（５），可以表示蚂蚁ｋ在ｔ时刻构造解的不确定性，即蚂蚁　ｋ在ｔ时刻的信息熵表达式为：　三Ｌ　ｓ　（　）＝　ｓ　（ｔ）　（６）　ｉ＝１　整个蚁群的信息熵表达式定义为：　三　，ｓ（　）＝１　ｓ　（ｔ）　（７）　ｍ酉　其中，ｍ为当前蚁群的蚂蚁数量。公式（７）表示整个蚁群在ｔ时　刻构造解集的平均不确定性，此定义结合了蚁群算法自身的特　点，将蚁群算法的运算过程与信息熵结合了起来。　由ｓ（ｔ）的定义可知，算法初始时各路径的信息素相等，信　息熵值最大，而后随着特定路径的信息素不断增强，信息素在　各路径间的分布不均衡，其值逐渐变小，若群体的信息熵出现　持续增大或保持不变时，则必定发生了成熟前收敛。由此可知，　蚁群信息熵的变化可用来预报群体内成熟前收敛的发生，同　时，信息熵值越小，说明蚂蚁种群进化程度越高。因此，信息熵　是自适应调节收敛速度、信息素更新以及群体之间交流信息的　依据。　３．２交流子群体的选择　为了保持各个子群体解的多样性，同时扩大较优解在整个　群体中的影响，各蚂蚁子群体之间要在一定的时间间隔后，通　过最优解和信息素的交换进行信息交流。各个子群体根据信息　熵来选择信息交流的对象。设子群体ｉ选择子群体　作为进行　１８　２００８．４４（３６）　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　表１　ＩＥＢＭＨＡＣＡ与ＭＣＡＣＡ实验结果对比表　信息交流的对象，则．　可由式（８）决定。　ｊ＝ａｒｇ　ｍａｘ（Ｉ　ｓ　ｚ－ｓｊ　Ｉ）　删（８）　其中，ｈ为子群体的个数，　、　，分别为当前时刻子群体ｉ和．　的　相同。初始化设置各个子群体内的参数，信息素矩阵都设为相　同的值，设置　、ＪＢ、Ｐ、Ｑ等参数。　步骤２各子群体按照不同的蚁群算法进行独立的路径寻　信息熵。　由公式（８）可见，信息熵大的子群体会选择信息熵小的子　群体来交流信息，避免了随机选择的盲目性。信息熵小的子群　体路径上的信息素过于集中，可以根据信息熵较大的子群体上　的信息来平衡自己的信息素分布，使得大多数的路径都有被选　择的机会；反过来，信息熵较大的子群体的路径上信息素较分　散，通过与信息熵较小的子群体的交流，适当地将信息素集中，　这样都有利于互相交流的两个子群体进一步进化，提高了寻求　最优解的潜力。　３．３交流周期的确定　在算法中，子群体间交流的时间间隔并不是固定的，而是　根据解的分布情况进行变化，这样有利于在解的多样性和算法　的收敛速度两个方面达到平衡。算法根据整个蚂蚁群体的收敛　情况来调整子群体之间交流的时间间隔ｇａｐ：　ｇａｐ＝ｋ１·ｅ　（９）　其中，ｋ　为常数，ｈ为子群体的个数，ｓ，为第ｉ个子群体的信息熵。　从式（９）可以看出，在蚁群搜索开始阶段，当ＣＯＹ－－（　ｓ　）／ｈ　的值较大时，整体的信息素都比较分散，表示解的多样性较好，　此时交流的时间间隔较大，以免破坏每个子群体内部的搜索。　搜索后期随着ＣＯＹ值的减小，整个蚂蚁群体中信息素都比较集　中，不利于各子群体蚂蚁进行进一步的搜索，此时交流的时间　间隔可以适当地减小，使得优质解在子群体之间得以迅速传　播，以改善每个子群体的进化环境。　３．４信息素的自适应更新　设子群体ｉ根据公式（８）选择与－Ｔ－￣ｋｊ进行信息交流，那　么子群体ｉ则会根据　上的信息来更新自己的信息素，反之亦　然。其具体方法是：假设子群体　的最优解经过路径（　，　），自　适应的更新系数Ａ体现了子群体对ｉ的信息素的影响程度，　可以有效避免路径上的信息素过于集中而造成算法的早熟。Ａ　越大，子群体门生子群体ｉ的路径（　，　）上的信息增量就越多，　这样可以有效地促进信息素均匀分布在各条路径上，防止子群　体ｉ陷入局部最优：　＋Ａ△７＿　（１ｏ）　其中，Ａ…与Ａ　为常数，分别表示更新系数的最小值和最大　值；Ａ＝ｌ　Ｓｉ　ｌ，Ａ　＜Ａ＜＾　，△　为子群体　在路径（　，　）上的信　息素。　３．５算法流程　算法流程如下：　步骤１把蚁群分为多个子群体，每个子群体的蚂蚁数量　优，一次迭代完成后，各子群体根据公式（７）计算种群当前的信　息熵值ｓ　。　步骤３如果满足子群体进行信息素交换的时间间隔ｇａｐ，　根据公式（８）选择进行信息素交流的子群体Ｐ　（ｉ，．　利用子群　体　上解的信息，计算出更新系数Ａ，根据公式（１０）来更新子群　体ｉ的信息素，采用同样方式更新子群体．　的信息素；重新根据　公式（９）计算蚁群进行信息素交换的时间间隔值ｇａｐ，即下一　次交换发生在距离当前迭代次数的第几次迭代上；否则，转步　骤４。　步骤４循环执行。如果已经达到最大蚁群迭代次数则退　出循环，输出最优路径；否则转步骤２循环执行。　４实验结果及分析　实验选取ｅｉｌ５１ＴＳＰ、ｅｉｌｌ０１ＴＳＰ、ｓｔ７０ＴｓＰ［”作为实验对象，将　基于信息熵的异类多种群蚁群算法ＩＥＢＭＨＡＣＡ和同类多种群　蚁群算法ＭＣＡＣＡ性能进行对比，其中ＭＣＡＣＡ算法的信息交　换方法参照Ｍａｒｔｉｎ　Ｍｉｄｄｅｎｄｏｆ总结的子群体之间进行信息交　流的最优的环形局部最优解交换方法『１ｏｌ。实验中，算法的蚂蚁　总数量相同。本文算法的参数设置如下：精英策略蚂蚁系统的　参数为ａ＝ｌ，　＝５，ｔｒ＝４，ｒ＝Ｏ．１，Ｑ＝ＩＯ０，优化排序蚂蚁系统的参数　为ａ＝ｌ，ＪＢ＝３，ｐ＝ｔｏ＝Ｏ．０５，自适应交换的参数为Ａ　＝Ｏ．１，Ａ…＝０．４，　ｋ　＝１０，所有蚁群蚂蚁个数之和ｍ为１００，迭代次数为５００次。　实验结果如表１所示：对于ｅｉｌ５１ＴＳＰ，两种算法都找到目　前最优解４２８．１３，但ＩＥＢＭＨＡＣＡ的迭代次数明显较少。在　ｓｔ７０ＴＳＰ中，两种算法均未能在５００次迭代中找到理论最优解　６７５，而ＩＥＢＭＨＡＣＡ则找到相对最优解６８０．４９。而在ｅｉ１１０１ＴＳＰ　的优化中，如图１（ｂ）所示，ＩＥＢＭＨＡＣＡ则获得更为优良的解曲　线，可以明显看出ＩＥＢＭＨＡＣＡ具有更快的收敛速度和更高的　解精度。同时，在多次实验中ＩＥＢＭＨＡＣＡ算法的平均解也优于　ＭＣＡＣＡ算法。对种群的数量和配比作了进一步的实验，在不同　种群数量下，对于ｅｉｌｌＯ１城市问题，采用不同的种群算法配比　的ＩＥＢＭＨＡＣＡ的求解结果如表２所示。从表中可以看出当种　群数量为４时，精英蚁群同优化排序蚁群数量比例为１：３时有　最好的结果。图１（ｃ）是本文算法在求解过程中的解的多样性　曲线，其多样性用公式（１１）进行计算：　表２　ＩＥＢＭＨＡＣＡ异类蚁群数最配比实验结果对比表　邓　可，林杰，张鹏：基于信息熵的异类多种群蚁群算法　∞　２００８，４４（３６）　加　ｍ　５　０　１９　流的周期以及信息更新策略，以取得各蚂蚁子群体中解的多样　ＤＩＶ（ｎ）＝　（１１）　性和收敛『生之间的动态平衡。实验证明该算法比基本同类多种　群蚁群算法具有更好的收敛速度和稳定性，此优点在求解复杂　问题时显得尤为重要。下一步的研究工作是将算法应用于复杂　的组合优化问题，以进一步检验算法的性能。　其中，ＡⅣ　ⅣＵＭ为蚂蚁数，Ｌ　（ｎ）为第１７，代第ｋ个蚂蚁所经过　的路径长度，ａｖｇ（Ｌ（ｎ））为第ｎ代所有蚂蚁经过路径长度的平　均值。从图中可以看出，在整个进化过程中，解的多样陛一直很　好，具有不断获得新的最优解的能力，使得本文算法可以获得　全局最优解，而不易陷入局部最优解。　图１（ｄ）是ＩＥＢＭＨＡＣＡ在精英蚁群同优化排序蚁群种群　数量配比为１：３时，求解ｅｉｌｌＯ１城市问题的性能曲线，图中４　条曲线分别表示４个种群的收敛性能，粗曲线表示精英策略蚂　蚁系统的性能曲线，其余３条表示优化排序蚁群种群的性能曲　参考文献：　［１］Ｄｏｒｉｇｏ　Ｍ，Ｍａｎｉｅｚｚｏ　Ｖ，Ｃｏｌｏｒｎｉ　Ａ．Ａｎｔ　ｓｙｓｔｅｍ：Ｏｐｔｉｍｉｚａｔｉｏｎ　ｂｙ　ａ　ｃｏｌｏｎｙ　ｏｆ　ｃｏｏｐｅｒａｔｉｎｇ　ａｇｅｎｔｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　ＳＭＣ，１９９６，　２６（１）：２９—４１．　［２］Ｂｕｌｌｎｈｅｉｍｅｒ　Ｂ，Ｈａｒｔｌ　Ｒ　Ｆ，Ｓｔｒａｕｓｓ　Ｃ．Ａ　ｎｅｗ　ｒａｎｋ　ｂａｓｅｄ　ｖｅｒｓｉｏｎ　ｏｆ　ｔｈｅ　ａｎｔ　ｓｙｓｔｅｍ—Ａ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｓｔｕｄｙ［Ｊ］．ＣＥＪＯＲ，１９９９，７：２５—３８．　线。由图中可见，精英策略蚂蚁系统在求解的初期，能快速收　敛，给其他３个采用优化排序蚁群算法的种群提供启发信息，　后期精英蚂蚁系统性能下降，但优化排序蚁群算法的种群能弥　补其缺点，进行ｌ夹速收敛。　［３】Ｓｔｕｔｚｌｅ　Ｔ．Ｐａｒａｌｌｅｌｉｚａｔｉｏｎ　ｓｔｒａｔｅｇｉｅｓ　ｆｏｒ　ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／　Ｅｉｂｅｎ　Ａ　Ｅ，Ｂａｃｋ　Ｔ，Ｓｃｈｏｅｎａｕｅｒ　Ｍ，ｅｔ　ａ１．ＬＮＣＳ：Ｐａｒａｌｌｅｌ　Ｐｒｏｂｌｅｍ　Ｓｏｌｖｉｎｇ　ｆｒｏｍ　Ｎａｔｕｒｅ＿—ｐＰＳＮ　Ｖ．Ｂｅｒｌｉｎ　Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ．１９９８：７２２－７３１．　［４］Ｓｔｕｔｚｌｅ　Ｔ，Ｈｏｏｓ　Ｈ　Ｈ．Ｍａｘ—ｍｉｎ　ａｎｔ　ｓｙｓｔｅｍ［Ｊ】．Ｊｏｕｒｎａｌ　ｏｆ　Ｆｕｔｕｒｅ　Ｇｅｎｅｒａｔｉｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ，２０００，１６（９）：８８９—９１４．　［５］Ｔａｌｂｉ　Ｅ　Ｇ，Ｒｏｕｘ　Ｏ，Ｆｏｎｌｕｐｔ　Ｃ，ｅｔ　ａ１．Ｐａｒａｌｌｅｌ　ａｎｔ　ｃｏｌｏｎｉｅｓ　ｆｏｒ　ｅｏｍ－　ｂｉｎａｔｏｒｉａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ［Ｃ］／／Ｒｏｌｉｍ　Ｊ．ＬＮＣＳ：Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓ－　ｔｒｉｂｕｔｅｄ　Ｐｒｏｃｅｓｓｉｎｇ，１　１　ＩＰＰＳ／ＳＰＤＰ’９９　Ｗｏｒｋｓｈｏｐｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，　１９９９：２３９—２４７．　［６］章春芳，陈峻，陈娟．求解频率分配问题的自适应的多种群蚁群算　法［Ｊ】＿小型微型计算机系统，２００６，２７（５）：８３７—８４１．　［７　Ｃｈｕｇ　Ｓｈｕ－ｃｈｕａｎ，Ｒｉ７］ｄｄｉｅｋ　Ｊ　Ｆ，Ｐａｎ　Ｊｅｎｇ－ｓｈｙａｎｇ．Ａｎｔ　ｃｏｌｏｎｙ　ｓｙｓｔｅｍ　ｗｉｔｈ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｓｔｒａｔｅｇｉｅｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，２００４，１６７（１２４）．　（ａ）最优路径图　（ｂ）两种算法效果比较　［８】Ｇａｍｂａｒｄｅｌｌａ　Ｌ　Ｍ，Ｔａｉｌｌａｒｄ　Ｅ，Ａｇａｚｚｉ　Ｇ．ＭＡＣＳ—ＶＲＰＴＷ：Ａ　ｍｕｈｉｐｌｅ　ａｎｔ　ｃｏｌｏｎｙ　ｓｙｓｔｅｍ　ｆｏｒ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍｓ　ｗｉｈ　ｔｔｉｍｅ　ｗｉｎｄｏｗｓ，　Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏ￣Ｉｄｓｉａ　ＩＤＳＩＡ一０６—９９　ＬＵＧＡＮＯ［Ｒ］．Ｓｗｉｔｚｅｒｌａｎｄ，　１９９９．　ｆ９　Ｍｉ９］ｄｄｅｎｄｏｒｆ　Ｍ，Ｒｅｉｓｃｈｌｅ　Ｆ，Ｓｃｈｍｅｃｋ　Ｈ．Ｍｕｌｔｉ　ｃｏｌｏｎｙ　ａｎｔ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．　Ｈｅｕｒｉｓｔｉｃｓ，２００２，８（３）：３０５—３２０．　［１０］Ｍｉｄｄｅｎｄｏｒｆ　Ｍ，Ｒｅｉｓｃｈｌｅ　Ｆ，Ｓｃｈｍｅｃｋ　Ｈ．Ｉｎｆｏｒｍａｔｉｏｎ　ｅｘｃｈａｎｇｅ　ｉｎ　ｍｕｌｔｉ　ｃｏｌｏｎｙ　ａｎｔ　ａｌｇｏｒｉｔｈｍｓ［Ｃ］／／Ｒｏｌｉｍ　Ｊ．ＬＮＣＳ：Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓ—　ｌｏｏ　２００　３００　４００　５００　ｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ，Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　５　ＩＰＤＰＳ　２０００　Ｗｏｒｋ－　（ｃ）解的多样性曲线　（ｄ）异类种群收敛曲线　ｓｈｏｐｓ．Ｔｈｉｒｄ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｂｉｏｌｏｇｉｃａｌｌｙ　Ｉｎｓｐｉｒｅｄ　Ｓｏｌｕｔｉｏｎｓ　ｔｏ　Ｐａｒ－　图１　ｅｉｌｌ０１ＴＳＰ实验结果图　ａｌｌｅｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｐｒｏｂｌｅｍｓ（ＢｉｏＳＰ３），Ｍａｉ　１　５，２Ｏ００，Ｃａｎｃｕｎ，Ｍｅｘｉ—　ｃｏ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ．２０００：６４５—６５２．　４结论　本文提出一种基于信息熵的异类多种群的蚁群算法，算法　将蚂蚁群体划分为若干个子群体，每个子群体利用具有互补特　性的不同种类的蚁群算法并行地进行优化，以便充分发挥算法　机制的优越性。在寻优过程中，算法根据信息熵来决定蚂蚁群　体间的信息交流策略，包括选择信息交流的对象和调节信息交　ｆ１　１】Ｍｉｃｈｅｌｓ　Ｒ，Ｍｉｄｄｅｎｄｏｒｆ　Ｍ．Ａｎ　ａｎｔ　ｓｙｓｔｅｍ　ｆｏｒ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｃｏｍｍｏｎ　ｓｕｐｅｒ　ｓｅｑｕｅｎｃｅ　ｐｒｏｂｌｅｍ［Ｃ］／／Ｃｒｏｎｅ　Ｄ，Ｄａｒｉｏ　Ｍ，Ｇｌｏｖｅｒ　Ｆ．Ｎｅｗ　Ｉｄｅａｓ　ｉｎ　Ｏｐｔｉｍｉｚａｔｉｏｎ．Ｎｅｗ　Ｙｏｒｋ：ＭｃＧｒａｗ—Ｈｉｌｌ，１９９９：５１－６１．　［１２】段海滨．蚁群算法原理及其应用ｆＭ］　Ｅ京：科学出版社，２００５．　［１３］Ｒｅｉｎｅｌｔ　Ｇ．ＴＳＰＬＩＢ９５［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｉｎｆｏｒｍａｔｉｋ．ｕｎｉ－ｈｅｉｄｅｌｂｅｒｇ．　ｄｅ／ｇｒｏｕｐｓ／ｅｏｍｏｐｆｆｓｏｆｌｗａｒｅ／ＴＳＰＬＩＢ９５／ｉｎｄｅｘ．ｈｔｍ１．　（上接１０页）　［７］Ｚｈａｏ　Ｓ，Ｓｔｕｔｚｂａｃｈ　Ｄ，Ｒｅｊａｉｅ　Ｒ．Ｃｈａｒａｃｔｅｒｉｚｉｎｇ　ｆｉｌｅｓ　ｉｎ　ｔｈｅ　ｍｏｄｅｒｎ　Ｇｎｕｔｅｌｌａ　ｎｅｔｗｏｒｋ：Ａ　ｍｅａｓｕｒｅｍｅｎｔ　ｓｔｕｄｙ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　［９　Ｌｉ９］　Ｃｈｕｎ－ｘｉ，Ｃｈｅｎ　Ｃｈａｎｇ－ｊｉ＆Ｏｎ　Ｇｎｕｔｅｌｌａ　ｔｏｐｏｌｏｇｙ　ｄｙｎａｍｉｃｓ　ｂｙ　ｓｔｕｄｙ—　ｉｎｇ　ｌｅａｆ　ａｎｄ　ｕｌｔｒａ　ｃｏｎｎｅｃｔｉｏｎ　ｊｏｉｎｆｌｙ　ｉｎ　ｐｈａｓｅ　ｓｐａｃｅ【Ｊ１．Ｃｏｍｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ，２００８，５２：６９５—７１９．　ＳＰＩＥ／ＡＣＭ　Ｍｕｌｔｉｍｅｄｉａ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗ叫ｋｉｎｇ（ＭＭＣＮ’０６），Ｓａｎ　Ｊｏｓｅ，ＣＡ，２００６．　［１０】Ａｃｏｓｔａ　Ｗ，Ｃｈａｎｄｒａ　Ｓ．Ｕｎｄｅｒｓｔａｎｄｉｎｇ　ｔｈｅ　ｐｒａｃｔｉｃａｌ　ｌｉｍｉｔｓ　ｏｆ　ｔｈｅ　ｇｎｕｔｅｌｌａ　Ｐ２Ｐ　ｓｙｓｔｅｍ：Ａｎ　ａｎａｌｙｓｉｓ　ｏｆ　ｑｕｅｒｙ　ｔｅｒｍｓ　ａｎｄ　ｏｂｊｅｃｔ　ｎａ／ｎｅ　［８】Ｗａｎｇ　Ｘｉａｏ—ｒｉｎｇ，ｕＹａｏ　Ｚｈｏｎｇ－ｍｅｉ，Ｌｏｇｕｉｎｏｖ　Ｄ．Ｒｅｓｉｄｕａｌ－ｂａｓｅｄ　ｍｅａｓｕｒｅｍｅｎｔ　ｏｆ　ｐｅｅｒ　ａｎｄ　ｌｉｎｋ　ｌｉ￣ｔｉｍｅｓ　ｉｎ　ｇｎｕｔｅｌｌａ　ｎｅｔｗｏｒｋｓ［ｊ／ｏＥ１．　［２００７１．ｈｔｔｐ：／／ｉｅｅｅｘｐｌｏｒｅ．ｉｅｅｅ．ｏｒｓ／ｉｅ１５／４２１５５８１／４２１５５８２／０４２１５６３５．　ｄｉｓｔｒｉｂｕｔｉｏｎｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＡＣＭ／ＳＰＩＥ　Ｍｕｌｔｉｍｅｄｉａ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ（ＭＭＣＮ’０８），Ｓａｎ　Ｊｏｓｅ，ＣＡ，Ａｐｒｉｌ　２００８．