计与应ｊ 文章编号：１６７１—４５９８（２０１６）０３—０１４３—０２ 计算机测量与控制．Ｃｏｍｐｕｔｅｒ Ｍｅａｓｕｒｅｍｅｎ２ｔ＆Ｃｏ０１ ６．２４ｎ（ｔ３）ｒｏｌ ＤＯＩ：１０．１６５２６／ｊ．ｃｎｋｉ．１１－－４７６２／ｔｐ．２０１６．０３．０３９ 中图分类号：ＴＰ１８ ・ １４３ ・ 文献标识码：Ａ 基于遗传一模拟退火的蚁群算法求解ＴＳＰ问题 徐 胜，马小军，钱 海，王震宇 （南京Ｔ业大学电气工程与控制科学学院，南京 ２１１８００） 摘要：传统的蚁群算法具有收敛性好、鲁棒性强等优点，但在解决旅行商（ＴＳＰ）问题方面存在收敛时间长，容易出现停滞等问题； 为了提高传统蚁群算法的解的质量，本文提出了基于遗传一模拟退火的蚁群算法（Ｇ—ＳＡＡＣＯ），将遗传算法和模拟退火算法引入蚁群 算法中；其方法是在传统蚁群算法中引入遗传算法的变异与交叉策略来得到候选ｊ辞，增加解的多样性；同时引进模拟退火算法机制，使 得在高温时以较高概率选择候选集中比较差的解加入最新集，温度控制上加入了回火机制，进一步提高解的质量；为了检验改进的蚁群 算法，随机选用了ＴＳＰＬＩＢ中的部分城市进行仿真，结果与传统蚁群算法、模拟退火蚁群算法、遗传蚁群算法相比，算法具有较强的发 现较好解的能力，同时增强了平均值的稳定性。 关键词：传统蚁群算法；遗传算法；模拟退火；旅行商问题 Ｇｅｎｅｔｉｃ－－ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ－－ｂａｓｅｄ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ Ｘｕ Ｓｈｅｎｇ，Ｍａ Ｘｉａｏｊｕｎ，Ｑｉａｎ Ｈａｌ，Ｗａｎｇ Ｚｈｅｎｙｕ （Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｎｔｒｏ１ Ｓｃｉｅｎｃｅ，Ｎａｎｊｉｎｇ Ｔｅｃｈ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１１８００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｈａｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｇｏｏｄ ｃｏｎｖｅｒｇｅｎｃｅ ａｎｄ ｒｏｂｕｓｔｎｅｓｓ，ｂｕｔ ｈａｓ ａ ｌｏｎｇ ｃｏｎｖｅｒｇｅｎｃｅ ｔｉｍｅ ｉｎ ｓｏｌｖｉｎｇ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ＴＳＰ．Ｉｎ ｏｒｄｅｒ ｔＯ ｉｍｐｒｏｖｅ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ。Ｇ—ＳＡＡＣＯ ｉｓ ｐｒｏ— ｐｏｓｅｄ，ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ ａｒｅ ｉｎｔｒｏｄｕｃｅｄ ｉｎｔｏ ｔｈｅ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ．．Ｔｈｅ ｉｄｅａ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗａｓ ｔｏ ｉｎｔｒｏｄｕｃｅ ｔｈｅ ｖａｒｉａｔｉｏｎ ａｎｄ ｃｒｏｓｓｏｖｅｒ ｓｔｒａｔｅｇｙ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎｔｏ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｔｏ ｇｅｔ ｔｈｅ ｃａｎｄｉｄａｔｅ ｓｏｌｕｔｉｏｎｓ， ｗｈｉｃｈ ｉｎｃｒｅａｓｅｄ ｔｈｅ ｄｉｖｅｒｓｉｔｙ ｏｆ ｔｈｅ ｓｏｌｕｔｉｏｎ．Ａｎｄ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ ｍｅｃｈａｎｉｓｍ ｍａｄｅ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｖｅ ｈｉｇｈｅｒ ｐｒｏｂａｂｉｌｉｔｙ ｏｆ ｓｅｌｅｃｔｉｎｇ ｐｏｏｒ ｓｏｌｕｔｉｏｎｓ ｉｎ ａ ｃａｎｄｉｄａｔｅ ｓｅｔ ｉｎｔｏ ｔｈｅ ｌａｔｅｓｔ ｓｅｔ．Ｂｅｓｉｄｅｓ，Ｉｎ ｔｈｅ ｍｅｃｈａｎｉｓｍ ｏｆ ｃｏｎｔｒｏｌｌｉｎｇ ｔｈｅ ｔｅｍｐｅｒａｔｕｒｅ，ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｔｈｅ ｓｏｌｕｔｉｏｎｓ ｗａｓ ｉｍｐｒｏｖｅｄ ｔｈｒｏｕｇｈ ｂａｃｋｆｉｒｅ ｓｔｒａｔｅｇｙ．Ｉｎ ｏｒｄｅｒ ｔｏ ｔｅｓｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ，ｒａｎｄｏｍｌｙ ｓｅｌｅｃｔｅｄ ｐａｒｔｓ ｏｆ ｔｈｅ ｃｉｔｙ ｏｆ ｔｈｅ ＴＳＰＬＩＢ ｔｏ ｓｉｍｕｌａｔｅ．Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｓｔａｎｄａｒｄ ＧＡ，ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏ— ｒｉｔｈｍ ｆｏｒ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ（ＴＳＰ）．Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｓｔｒｏｎｇ ａｂｉｌｉｔｙ ｔｏ ｆｉｎｄ ｇｏｏｄ ｓｏｌｕｔｉｏｎｓ，ａｎｄ ｔｈｅ ｓｔａｂｉｌｉ— ｔｙ ｏｆ ｔｈｅ ａｖｅｒａｇｅ ｖａｌｕｅ ｉｓ ｅｎｈａｎｃｅｄ． Ｋｅｙｗｏｒｄｓ：ｔｒａｄｉｔｉｏｎａｌ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ；ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ ０ 引言 在２０世纪５Ｏ年代中期，人们从生物行为和生物进化的机 理中获得启发，提出了各种用来解决优化问题的方法，如遗传 算法、禁忌搜索、模拟退火、进化策略等。２０世纪９Ｏ年代， 意大利学者Ｄｏｒｉｇｏ等人通过观察蚂蚁觅食的行为提出了蚁群 慢 。 本文将遗传算法和模拟退火算法引入蚁群算法中，在对原 有算法改进的基础上，提出了一种基于遗传一模拟退火的蚁群 算法。此算法利用遗传算法对蚁群算法得到的解进行交叉变异 操作，从而获得新解，把蚁群算法的解和遗传算法的解组合成 候选集，扩大了解的范围，并在一定程度上避免了早熟现象。 同时结合模拟退火算法机制，使得在高温时能够以较高的概率 选择候选集中比较差的解加入最新集，增加了解的多样性，很 好的防止了早熟现象的发生；在低温时较差的解只有很小的概 率才会被加入到最新集，这有效地提高了算法的收敛速度。在 温度控制上加入了回火策略，进一步提高解的质量。 算法（ＡＣＯ）［１３。蚁群算法利用了蚁群觅食的正反馈原理，具 有收敛性好、鲁棒性强、并行性好等优点，使得其在解决ＴＳＰ 问题方面优于模拟退火算法、禁忌算法、遗传算法等智能算 法 ２ ］。但同时也存在收敛时间长，容易出现停滞等问题。文 献［４］中张晓婧等人提出的模拟退火蚁群算法在求解Ｊｏｂ— Ｓｈｏｐ问题时，虽然提高了算法的收敛速度，但导致了早熟现 象。文献［５３中江新姿等人提出的求解旅行商问题的模拟退 火蚁群算法，在一定程度避免了早熟现象，但收敛速度变 收稿日期：２０１５一Ｏ８—２８；修回日期：２０１５—１１—１６ 基金项目：江苏省普通高校研究生科研创新计划项目（ＳＪＬＸ一 ０３３４）。 ｌ传统蚁群算法求解ＴＳＰ问题 １．１ ＴＳＰ问题描述 设有 个城市，为任意两个城市ｉ，Ｊ之间的距离，求经过 每个城市有且仅有一次的一条路径Ｍ一（Ｍ（１），Ｍ（２），…， Ｍ（ ）），使得 作者简介：徐胜（１９９０一），男，江苏常熟人，研究生，主要从事建筑 智能化技术方向的研究。 ｍｉｎ｛ ‰… ＋ … ） １．２传统蚁群算法的ＴＳＰ求解 意大利学者Ｍ．Ｄｏｒｉｇｏ等人发现：蚂蚁在运动过程中会在 马小军（１９５６一），男，江苏南京人，教授，主要从事建筑智能化技术， ＰＬＣ，嵌入式技术方向的研究。 ・１４４ ・ 计算机测量与控制 第２４卷 所经过的路径上留下一种称之为信息素的物质，而且它们能够 感知到这种物质，并倾向于朝该物质强度高的方向移动 ］。因 此，由大量蚂蚁所组成的集体行为就表现出一种信息正反馈现 象：某一路径越短，那么该条路径上走过的蚂蚁就越多，所留 下的信息素的强度自然也就越大，后来者选择该条路径的概率 也就越大。蚂蚁个体之间通过这种信息交流来选择最短路径并 达到搜索食物的目的。 在旅行商问题中，设ｍ为蚂蚁总数，表示ｔ时刻位于城市ｉ 的蚂蚁数，则。为ｔ时刻边上信息素的强度，设（ｃ为常数）。随着 时间的推移，先前的信息素会挥发，而新的信息素会加入，ＩＤ为 信息素保留程度，１一ｆＤ为信息素消逝程度，当ｍ只蚂蚁都完成 一次循环后，各边的信息素按下面公式调整： ｒｔ＋１、一 （ ）＋Ａｒ （１） Ａｒ 一∑ （２） 表示第ｋ只蚂蚁留在路径 上的信息素，为此次循环中边 ｉｊ上的信息素增量。 一｛ （３） Ｌ 一∑ｄ （４） 为本次循环后，第ｋ只蚂蚁的路径长度，Ｑ为常数。 在循环过程中，由转移概率决定转移方向，表示第ｋ只蚂蚁 从城市ｉ转移到城市 的概率。 ｆ 堡丛 … 一１∑嘲 ，Ｊ∈ａｌｌ。Ｗ ｄ舢 为边（ｉ， ）的能见程度，是某种启发信息，信息素 和能见程度的相对重要性，一｛０，１，２，３，…，ｎ～１｝一ｔａ— ｂｕｋ表示允许蚂蚁ｋ选择城市的集合，是蚂蚁ｋ的禁忌表，用 来记录蚂蚁ｋ已走过的城市，体现了人工蚂蚁的记忆性。 传统蚁群算法解ＴＳＰ问题的基本步骤。 Ｓｔｅｐ１：迭代步数”ｆ—ｏ，ｒ 一ｃ（Ｃ为常数），ｒ，ｊ—Ｏ，将 只蚂蚁随机放在 个顶点上； Ｓｔｅｐ２：首先将各只蚂蚁的出发点放在当前解集中，然后 根据式（５）计算蚂蚁ｋ的转移概率ｐ ，并按照转移概率 移到下一个顶点 ，最后将顶点 放在当前解集中； Ｓｔｅｐ３：当各蚂蚁ｋ完成本次循环后，计算各只蚂蚁的路 径长度 ，并按照式（１）来更新信息素； Ｓｔｅｐ４： ｃ ｃ＋１； Ｓｔｅｐ５：如果ｎｃ％总迭代步数，则转步骤２； Ｓｔｅｐ６：根据各路径上信息素的强度，得出最好解。 ２遗传一模拟退火的蚁群算法 在求解ＴＳＰ组合优化问题时，蚁群算法是在整个可行解 内进行盲目的随机搜索全局最优解，因此就产生了算法的收敛 速度慢、易于停滞等问题，为了很好的克服这些问题。本文对 传统蚁群算法作了一些改进。 ２．１遗传算法的引入 遗传算法是以“适者生存”和遗传变异理论为基础的一类 仿生优化算法。本文利用遗传算法的交叉和变异的策略来改善 蚁群算法的解的多样性。 遗传算法对蚁群算法得到的解集ｐａｔｈｌ中的解与ｐａｔｈｌ中 的最优解ｐｂｅｓｔｌ按概率交叉操作得到解集ｐａｔｈ２，然后再对 ｐａｔｈｌ中的解按概率进行变异操作获得解集ｐａｔｈ３，最后将 ｐａｔｈ１、ｐａｔｈ２和ｐａｔｈ３组合成候选集ｐａｔｈ。 交叉策略：在ｐｂｅｓｔｌ中随机选择一个交叉区域，删除待 交叉解中已在ｐｂｅｓｔｌ的交叉区中出现过的城市，将ｐｂｅｓｔｌ的 交叉区域加到待交叉解的随机位置上。例如：ｐｂｅｓｔｌ一１，２， ３，４，５，６，７，８；交叉区域为：５ ６ ７ ８；待交叉解为８，７， ６，５，４，３，２，１；随机位置为３，交叉后为：４，３，２，５， ６，７，８，１。 变异策略：随机选择待变异解的第次和第次访问的城市， 在待变异解中交换这两次访问的城市，其他不变。例如：待变 异的解为８，７，６，５，４，３，２，１；一１，一４；则变异之后 的解为５，７，６，８，４，３，２，１。 ２．２模拟退火算法的引入 ２．２．１模拟退火机制的引入 本文利用模拟退火机制由候选集ｐａｔｈ生成最新解ｐａｔｈ— ｒｌｅｗ，逐个计算候选集中的解，按照下列公式决定候选集中的 解是否加入最新集。 Ｐ 一 ８‘亍 ，（△Ｌ＞０），１，（ ）， （６） 其中：△Ｌ—Ｌ 一Ｌ… ，表示候选集中第Ｗ个解的路径长 度，表示候选集中最短的路径长度，Ｔ为当前温度值。若，则 将第Ｗ个解加到最新集ｐａｔｈｎｅｗ中；否则在［ｏ，１）之间产 生一个随机数，若，则第Ｗ个解进入最新集ｐａｔｈｎｅｗ。 由式（６）可知：在高温时以较高概率选择候选集中比较 差的解加人最新集，增加了解的多样性，在一定程度在避免了 早熟和停滞现象。在低温时比较差的解只有很小的概率加入最 新集中，这样加快了算法的收敛速度。 ２．２．２回火机制 在完成一次循环和信息素的更新后，温度Ｔ按照下列式 子进行降温： Ｔｒｔ＋１、一， 口丁（ ）， （７） 从式（７）可以看出：如果取较小的降温系数ａ，这样可 以加快算法的速度，但很可能算法会陷入局部最优。为了克服 这个困难，本文运用了回火策略，当温度Ｔ下降到Ｔ 时，算 法立即温度Ｔ升到丁。，同时可以设定回火次数Ｇ，最大回火 次数Ｇ… 回火策略很好的发挥了模拟退火机制的作用。当温度Ｔ 上升到Ｔ 时，以较高概率选择候选集中比较差的解加入最新 集，大大减少了落人局部最优的风险。 ２．３信息素的更新 对于ＴＳＰ问题，在算法的初始阶段，信息素保留程度取 较大的值可以提高蚁群寻找新解的能力，但在后期取较小的值 可以使蚁群搜索更加集中｜７］。为了使算法满足这一条件，本文 １ 借助Ｐ（Ｇ＋１）一ｌＤ（Ｇ）＊（÷）。（Ｇ为回火次数）作为信息素保 留程度ｐ的更新规则。当算法第一次执行回火策略时，信息素 保留程度将降为原来的１／２，第二次执行回火策略时，Ｐ为原来 的１／４，直到达到最大回火次数Ｇｍａｘ，ＩＤ才不变，这样，大幅 提高了算法的收敛速度。 ２．４算法的描述 遗传一模拟退火的蚁群算法的步骤如下。 （下转第１４８页） 计算机测量与控制 参考文献： 第２４卷 ［６］高晋占．微弱信号检测［Ｍ］（１版）．北京：北京清华大学出版 社，２００４． ［１］孙成正，尹文庆，赵建平，等．植物电信号前置放大电路的设计 与仿真ＥＪ］．电子测量技术，２００７，３０（７）：１６８—１７１． ［２３薛琳，赵东杰，侯佩臣，等．自参考离子选择性电极技术应用 中的微电极制备及测试［Ｊ］．农业工程学报，２０１３，２９（１６）： １８２—１８９． ［７］方捷．最新器件快讯［Ｊ］．电脑维护与应用，１９９４（６）：２—３． ［８］张石锐，郑文刚，黄丹枫，等．微弱信号检测的前置放大电路设 计［Ｊ］．微计算机信息，２００９，２５（２３）：２２３—２２４． ［９］朱星，许 强，邓茂林，等．岩石次声滤波处理新技术—— ［３］Ｋｕｈｔｒｅｉｂｅｒ Ｗ Ｍ，Ｊａｆｆｅ Ｌ Ｆ．Ｄｅｔｅｃｔｉｏｎ ｏｆ ｅｘｔｒａｃｅｌｌｕｌａｒ ｃａｌｃｉｕｍ ｇｒａ— ｄｉｅｎｔｓ ｗｉｔｈ ａ ｃａｌｃｉｕｍ—ｓｐｅｃｉｆｉｃ ｖｉｂｒａｔｉｎｇ ｅｌｅｃｔｒｏｄｅ Ｉ－Ｊ］．Ｔｈｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｅｌｌ Ｂｉｏｌｏｇｙ，１９９０，１１０（５）：１５６５—１５７３． ｓａ１１ｅｎ—Ｋｅｙ数学模型［Ｊ］．煤炭学报，２０１３（８）：１３５７—１３６１． Ｅｌｏ］李东仓，杨５６６． 磊，田 勇，等．基于Ｓａｌｌｅｎ—Ｋｅｙ滤波器的核脉 冲成形电路研究［Ｊ］．核电子学与探测技术，２００８（３）：５６３ —Ｅ４３彭敏．基于ＡＲＭ７的工业控制数据采集系统的研究［Ｊ］．现代 电子技术，２０１１，３４（２）：１２—１４． ［１１］陈贺明，赵国敏．基于ＦＩＦＯ电路的高速大数据采集系统的设计 ［５］王秀华．前置低噪声放大器的研究与设计ＥＪ］．电子测量技术， ２Ｏ１３（６）：３５—３７． 与实现［Ｊ］．计算机测量与控制，２０１４（８）：２５４２—２５４５． （上接第１４４页） 表１ ３种算法的测试结果 算法 最差解／ 最好解／ 平均值／ 平均进 （ｋｍ） 模拟退火蚁群算法 Ｓｔｅｐｌ：初始化算法参数ｍ，Ｔ，Ｔ１，Ｔ ，ａ，ｄ，卢，ＩＤ，Ｇｍ…Ｑ，Ｐ ， Ｐ ， ＝ｃ，Ａｒ 一０，ｔ一０将所有的蚂蚁都放在城市１； Ｓｔｅｐ２：第 只蚂蚁按转移概率移动到 城市； （ｋｍ） （ｋｍ） 化代数 ４５１ １ ０６２．３Ｏ １ ０１２．１６ １ ０４１．４２ Ｓｔｅｐ３：当ｍ只蚂蚁都完成了一次循环，蚁群得到解集 ｐａｔｈｌ，ｐａｔｈｌ内最优解为ｐｂｅｓｔｌ； 遗传蚁群算法 遗传一模拟退火蚁群算法 １ ０５８．１７ １ Ｏ０５．０８ １ ０３５．５０ １ ０４８．３８ ９８９．１４ １ ０２４．３６ ４０９ ２８６ Ｓｔｅｐ４：解集ｐａｔｈｌ中的解逐个按概率Ｐ 与ｐｂｅｓｔｌ进行交 叉操作，获得解集ｐａｔｈ２； Ｓｔｅｐ５：解集ｐａｔｈｌ中的解逐个按概率Ｐ 进行变异操作， 得到解集ｐａｔｈ３； Ｓｔｅｐ６：解集ｐａｔｈｌ、ｐａｔｈ２和ｐａｔｈ３组合成候选集ｐａｔｈ， 记录当前最优解ｇｂｅｓｔ； Ｓｔｅｐ７：根据模拟退火机制，按照概率Ｐ 来选择ｐａｔｈ中 的解，生成最新集； Ｓｔｅｐ８：根据最新集里的解按照式（１）～式（４）对信息 素进行更新； ∞蚰∞∞踮∞∞∞０ Ｓｔｅｐ９：丁一ｎＴ， 一 ＋１；若Ｔ≥Ｔｌ，则转到Ｓｔｅｐ２；若Ｔ ＜Ｔ ，回火次数Ｇ—Ｇ ，则退出循环，输出最优解；如果且 Ｇ＜Ｇ ，则Ｇ—Ｇ＋１，Ｔ— ，转到Ｓｔｅｐ２。 图１ 用遗传一模拟退火蚁群算法解ＴＳＰａ２８０最好的解 ＴＳＰ问题能够获得比模拟退火算法、标准遗传算法和传统蚁 群算法都要好的解，而且也增加了解的多样性和稳定性，同时 算法的收敛度也得到了一定程度的改善，证明了该算法具有一 定的有效性。 参考文献： ３算法测试 为了检验本文算法，随机选用了国际上通用的ＴＳＰ测试 库ＴＳＰＬＩＢ中ａ２８０（２８０个城市）里的５Ｏ个城市来进行仿真， 并且与传统蚁群算法、模拟退火蚁群算法、遗传蚁群算法进行 比较。传统蚁群算法参数如下：蚂蚁数ｍ：３Ｏ，信息素保留程 度Ｐ一０．９，信息素的重要程度ａ一１．５，能见性的重要程度卢一 ２，初始信息素ｃ—ｉ００；采用文献［５］中的模拟退火蚁群算 法，初始温度Ｔ一１００ ０００，终止温度Ｔｏ；１０，降温系数ｎ ［１］宋志飞．基于蚁群算法的ＴＳＰ问题研究［Ｄ］．江西：江西理工大 学，２０１２． ［２］吴华锋，陈信强，毛奇凰，等．基于自然选择策略的蚁群算法求 解ＴＳＰ问题［Ｊ］．通信学报，２ｏ１３，３４（４）：１６５一ｌ７Ｏ． ［３］侯文静，马永杰，张燕，等．求解ＴＳＰ的改进蚁群算法［ｊ］． ０．９；采用文献［８］中的遗传蚁群算法，染色体数Ｎ＝３０，交 叉概率Ｐ 一０．４，变异概率Ｐ 一０．１；本文算法参数设计：ｍ 一计算机应用研究，２０１０，２７（６）：２０８７—２０８９． ［４］张晓婧，高慧敏．基于模拟退火的蚁群算法求解Ｊｏｂ—Ｓｈｏｐ问题 ３０，．Ｄ一０．９，ａ＝１．５，卢一２，Ｃ一１００，Ｑ一１００ ０００，ａ一 ［Ｊ］．计算机应用与软件，２００８，２５（５）：７７—７９． ［５］江新姿，高 尚，陈建忠．求解旅行商问题的模拟退火蚁群算法 ０．９，Ｔ一５ ０００，Ｔｌ一１００，Ｔｚ一２ ０００，Ｇ…一８，Ｐｃ一０．４， Ｐ 一０。１。对各种算法测试５Ｏ次，结果如表１所示。图１是遗 传一模拟退火蚁群算法最好的解，总路程为９８９．１４ ｋｍ。 ［Ｊ］．计算机工程与设计，２００８，２９（６）：１４９１—１４９３． ［６］刘波，蒙培生．采用基于模拟退火的蚁群算法求解旅行商问题 ［Ｊ］．华中科技大学学报（自然科学版），２００９，３７（１１）：２６—３０． ［７］陈冰梅，樊晓平，周志明，等．求解旅行商问题的Ｍａｔｌａｂ蚁群仿 真研究［Ｊ］．计算机测量与控制，２０１１，１ ９（４）：９９０ ９９７． ［８］江君莉，潘 丰．求解ＴＳＰ的遗传蚁群融合算法［Ｊ］．江南大学 学报（自然科学版），２ｏ１２，１１（３）：２５３—２５６． 从表１中的最好解－－ＹＵ可以看出遗传一模拟退火蚁群算法 具有较强的发现较好解的能力。观察他们的平均值可以知道本 文算法也具有较好的稳定性。 ４ 结论 采用传统算法改进后的遗传一模拟退火蚁群算法来求解