蚁群算法
目 录
1 蚁群算法基本思想 ........................................................................................................................................................ 1
1.1 蚁群算法简介 ......................................................................................................................................................... 1
1.2 蚁群行为分析 ......................................................................................................................................................... 1
1.3 蚁群算法解决优化问题的基本思想 ..................................................................................................................... 2
1.4 蚁群算法的特点 ..................................................................................................................................................... 2
Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ 计算机应用，２０１５，３５（１０）：２７７７—２７８０，２７９７ ＩＳＳＮ １００１．９０８１ Ｃ０ＤＥＮ ＪＹＩＩＤＵ ２０１５．．１０．．１０ ｈｔｔｐ：／／ｗｗｗ．ｊｏｃａ．ｃｎ 文章编号：１００１—９０８１（２０１５）１０—２７７７－０４ ｄｏｉ：１０．１１７７２／ｊ．ｉｓｓｎ．１００１・９０８１．２０１５．１０．２７７７ 基于Ｓｐａｒｋ的蚁群优化算法 王诏远 ，王宏杰 ，邢焕来 ，李天瑞 （１．西南交通大学信息科学与技术学院，成都６１１７５６；２．四川省云计算与智能技术高校重点实验室，成都６１１７５６） （￥通信作者电子邮箱ｈｘｘ＠ｈｏｍｅ．ｓｗｊｔｕ．ｅｄｕ．ＣＢ） 摘要：为应对大数据时代中组合优化问题的求解，基于云计算框架Ｓｐａｒｋ，借助其基于内存、分布式的特定，提出 一种并行蚁群优化算法。其思路是通过将蚂蚁构造为弹性分布式数据集，由此给出相应的一系列转换算子，实现了 蚂蚁构造解过程的并行化。通过在旅行商问题（ＴＳＰ）求解的仿真实验结果说明了所提出的并行算法的可行性；并在 同等实验环境下对比基于ＭａｐＲｅｄｕｃｅ的蚁群优化算法，优化速度提升达１０倍以上。 关键词：蚁群优化算法；并行；Ｓｐａｒｋ；Ｈａｄｏｏｐ；云计算 中图分类号：ＴＰ３１１ 文献标志码：Ａ Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｓｐａｒｋ ＷＡＮＧ Ｚｈａｏｙｕａｎ 一，ＷＡＮＧ Ｈｏｎｇｊｉｅ 一，ＸＩＮＧ Ｈｕａｎｌａｉ ，ＬＩ Ｔｉａｎｒｕｉ ， （１．Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｏｕｔｈｗｅｓｔ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ Ｓｉｃｈｕａｎ ６１１７５６，Ｃｈｉｎａ； ２．Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ Ｃｌｏｕｄ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｓｉｃｈｕａｎ Ｐｒｏｖｉｎｃｅ，Ｃｈｅｎｇｄｕ Ｓｉｃｈｕａｎ ６１ １７５６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｎ ｔｈｅ ｅｒａ ｏｆ ｂｉｇ ｄａｔａ，ａ ｐａｒａｌｌｅｌ Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ （ＡＣＯ）ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｓｐａｒｋ，ａ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｔｈｅ ｄｉｓｔｒｉｂｕｔｅｄ ｍｅｍｏｒｙ ｃｏｍｐｕｔｉｎｇ，ｗａｓ ｐｒｅｓｅｎｔｅｄ．Ｔｏ ａｃｈｉｅｖｅ ｔｈｅ ｐａｒａｌｌｅｌｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｐｈａｓｅ ｏｆ ｓｏｌｕｔｉｏｎ ｃｏｎｓｔｒｕｃｔｉｏｎ ｉｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ，ａ ｃｌａｓｓ ｏｆ ａｎｔｓ ｗａｓ ｅｎｃａｐｓｕｌａｔｅｄ ｔｏ ａ ｒｅｓｉｌｉｅｎｔ ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａｓｅｔ ａｎｄ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｏｐｅｒａｔｏｒｓ ｗｅｒｅ ｇｉｖｅｎ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｈｓ ｉｎ ｓｏｌｖｉｎｇ ｔｈｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ（ＴＳＰ）ｐｒｏｖｅ ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｐａｒａｌｌｅｌ ａｌｇｏｒｉｔｈｍ．Ｕｎｄｅｒ ｔｈｅ ｓａｍｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｅｎｖｉｒｏｎｍｅｎｔ， ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｒｅｓｕｌｔｓ ｂｅｔｗｅｅｎ ＭａｐＲｅｄｕｃｅ ｂａｓｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｉｍｐｒｏｖｅｓ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｓｐｅｅｄ ａｔ ｌｅａｓｔ ｔｅｎ ｔｉｍｅｓ ｔｈａｎ ｔｈｅ ＭａｐＲｅｄｕｃｅ ｏｎｅ． Ｋｅｙ ｗｏｒｄｓ：Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ａｌｇｏｒｉｔｈｍ；ｐａｒａｌｌｅｌｉｎｇ；Ｓｐａｒｋ；Ｈａｄｏｏｐ；ｃｌｏｕｄ ｃｏｍｐｕｔｉｎｇ ０ 引言 组合优化（ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ）问题的目标是从组 合问题的可行解集中求出最优解。这类问题虽数学描述相对 简单，但具有很强的工程代表性。典型的组合优化问题包括 旅行商问题（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ，ＴＳＰ）、加工调度问 题（如Ｆｌｏｗ—Ｓｈｏｐ、Ｊｏｂ—Ｓｈｏｐ）、０—１背包问题等。这类问题广泛 地存在于生产、生活中，然而，此类问题的求解却极为困难，其 主要原因在于：待优化问题的解空间巨大、解数量众多，即所 谓的“组合爆炸”，而传统的求解方法时间和空间复杂度高， 无法胜任上述问题的求解。实际上，对于生产、生活中的许多 组合优化问题，相对于花费大量时间寻求问题的最优解，快速 搜索到问题的一个满意解更具有实用价值。因此，在求解现 实世界中的组合优化问题时，人们将更多的精力投入到如何 运用元启发式算法（ｍｅｔａ ｈｅｕｒｉｓｔｉｃ）在尽可能短的时问内寻求 问题的满意解上。元启发式算法是一类用来指导与问题相关 的启发式方法，这些方法可以朝着可能含有更高质量解的搜 索空间进行搜索…。典型的元启发式算法包括：遗传算法 （Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）Ｌ２ｊ、粒子群优化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）算法 和蚁群优化（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）算法 等。“组合爆炸”的问题在当今 大数据时代的背景下显得尤为突出，随着数据的规模数量级 增长，出现问题规模大到即使应用元启发式算法也无法高效 地在廉价计算机上优化求解的问题。由于元启发式优化算法 大都通过抽象、总结自然界生物种群一些优秀的种群协作、进 化等方式行为而来，所以这类基于种群的算法在个体之间会 具有天然的内在并行性。因此，通过结合云计算技术来并行 实现元启发式算法以有效地解决上述问题成为一种可行、可 靠的方案。 本文基于云计算框架Ｓｐａｒｋ提出实现蚁群优化算法的方 法。本文的主要贡献为：针对蚁群优化算法的特点以及Ｓｐａｒｋ 的并行模式，设计并行蚂蚁构造解的过程的并行蚁群优化算 法，即将蚂蚁封装为弹性分布式数据集（Ｒｅｓｉｌｉｅｎｔ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａｓｅｔ，ＲＤＤ），并设计一系列的弹性分布式数据集转换操 作，使之完成并行。 收稿日期：２０１５－０６—１５；修回日期：２０１５—０７－０１。 基金项目：国家自然科学基金资助项目（６１１７５０４７，６１４０１３７４）；中央高校基本科研业务费专项资金资助项目（２６８２０１４ＲＣ２３）；教育部留学 回国人员科研启动基金资助项目；四川省苗子工程（２０１５０４５）；西南交通大学“埃实之星”培养计划。 作者简介：王诏远（１９８９一），男，山西吕梁人，硕士研究生，ＣＣＦ会员，主要研究方向：进化算法、云计算； 王宏杰（１９９１一），男，河北唐山 人，硕士研究生，ＣＣＦ会员，主要研究方向：数据挖掘、云计算；邢焕来（１９８３一），男，河北唐山人，副教授，博士，ＣＣＦ会员，主要研究方向：进化 计算、网络编码、软件定义网络；李天瑞（１９６９一），男，福建莆田人，教授，博士生导师，博士，ＣＣＦ会员，主要研究方向：智能信息处理、数据挖 掘、云计算。
蚁群算法的改进与应用
摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。
关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法;
1 前言
蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991
年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。
尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。
蚁群优化算法及其应用
1.引言
1.1蚁群行为
一只蚂蚁看起来微不足道，但多个蚂蚁形成的蚁群似乎就是一个非常规整的军队，在很多情况下，他可以完成很多单只蚂蚁完成不到的事。这种行为可以看成多个蚂蚁之间的合作，最典型的一个例子就是寻找食物。在我们的生活中，我们经常可以观察到蚂蚁排成一条直线非常有规整的搬运食物，它是一条直线而不是别的形状。当蚁群的行进路线出现障碍的时候，蚂蚁的位置总是非常规整而又均匀。只要等待时间一会儿，蚂蚁就能找到回蚁穴的最短路径。蚂蚁可以利用这个信息。当蚂蚁出去觅食会释放信息素，并且沿着行进的路线释放，而且蚂蚁之间都可以互相感应信息素。信息素的浓度多少决定了食物与蚁穴之间的距离。信息素浓度越高，食物与蚁穴距离就越短。
1.2一个关于寻路行为的简单例子
戈斯S等人在1989年进行了“双桥”实验。这个实验说明了，蚁群会选择出食物与蚁穴的最短的距离。下面的例子也能解释它。
图 1
如图1所示，如果路线是从A点到D点，有俩个选择ABD和ACD路线，假如现在有俩只蚂蚁B和C分别在ABD路线和ACD路线上，一个时间单位进一步，8个时间单位后，情况如图2所示：从ABD路线最后到D的蚂蚁，从ACD路线最后到C的蚂蚁. 再过8个单位时间后，可以得到以下情况：B蚂蚁已经到A点了，而C蚂蚁才到D点.
图 2
32个单位时间后，在ABD路线上的蚂蚁已经折返了两次，而在ACD路线上的蚂蚁只有折返一次，是不是可以说明ABD上面的信息素比ACD多出了一倍。接下来，受信息素的影响，ABD路径会被两倍多的蚂蚁选择，所以ABD路线上会有更多的蚂蚁，也会有更多的信息素。最后，在32个单位的时间后，信息素浓度的比值将达到3：1。信息素浓度越来越高蚂蚁也会相应越来越多，而ACD路径将逐渐被放弃。这就是蚂蚁如何依赖信息素来形成积极反馈的方式。 由于前一条蚂蚁在一开始的路径上没有留下信息素，所以蚂蚁向两个方向移动的概率是相等的。但是，蚂蚁移动的时候，它会释放信息素。信息素是蚂蚁之间合作的重要因素。之后的蚂蚁就是根据信息素的浓度来判辨方向和之后的行进路线。实现表明短侧的路线信息素浓度更高，更多蚂蚁也会追随这条路线.
