Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ 计算机应用，２０１５，３５（１０）：２７７７—２７８０，２７９７ ＩＳＳＮ １００１．９０８１ Ｃ０ＤＥＮ ＪＹＩＩＤＵ ２０１５．．１０．．１０ ｈｔｔｐ：／／ｗｗｗ．ｊｏｃａ．ｃｎ 文章编号：１００１—９０８１（２０１５）１０—２７７７－０４ ｄｏｉ：１０．１１７７２／ｊ．ｉｓｓｎ．１００１・９０８１．２０１５．１０．２７７７ 基于Ｓｐａｒｋ的蚁群优化算法 王诏远 ，王宏杰 ，邢焕来 ，李天瑞 （１．西南交通大学信息科学与技术学院，成都６１１７５６；２．四川省云计算与智能技术高校重点实验室，成都６１１７５６） （￥通信作者电子邮箱ｈｘｘ＠ｈｏｍｅ．ｓｗｊｔｕ．ｅｄｕ．ＣＢ） 摘要：为应对大数据时代中组合优化问题的求解，基于云计算框架Ｓｐａｒｋ，借助其基于内存、分布式的特定，提出 一种并行蚁群优化算法。其思路是通过将蚂蚁构造为弹性分布式数据集，由此给出相应的一系列转换算子，实现了 蚂蚁构造解过程的并行化。通过在旅行商问题（ＴＳＰ）求解的仿真实验结果说明了所提出的并行算法的可行性；并在 同等实验环境下对比基于ＭａｐＲｅｄｕｃｅ的蚁群优化算法，优化速度提升达１０倍以上。 关键词：蚁群优化算法；并行；Ｓｐａｒｋ；Ｈａｄｏｏｐ；云计算 中图分类号：ＴＰ３１１ 文献标志码：Ａ Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｓｐａｒｋ ＷＡＮＧ Ｚｈａｏｙｕａｎ 一，ＷＡＮＧ Ｈｏｎｇｊｉｅ 一，ＸＩＮＧ Ｈｕａｎｌａｉ ，ＬＩ Ｔｉａｎｒｕｉ ， （１．Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｏｕｔｈｗｅｓｔ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ Ｓｉｃｈｕａｎ ６１１７５６，Ｃｈｉｎａ； ２．Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ Ｃｌｏｕｄ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｓｉｃｈｕａｎ Ｐｒｏｖｉｎｃｅ，Ｃｈｅｎｇｄｕ Ｓｉｃｈｕａｎ ６１ １７５６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｎ ｔｈｅ ｅｒａ ｏｆ ｂｉｇ ｄａｔａ，ａ ｐａｒａｌｌｅｌ Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ （ＡＣＯ）ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｓｐａｒｋ，ａ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｔｈｅ ｄｉｓｔｒｉｂｕｔｅｄ ｍｅｍｏｒｙ ｃｏｍｐｕｔｉｎｇ，ｗａｓ ｐｒｅｓｅｎｔｅｄ．Ｔｏ ａｃｈｉｅｖｅ ｔｈｅ ｐａｒａｌｌｅｌｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｐｈａｓｅ ｏｆ ｓｏｌｕｔｉｏｎ ｃｏｎｓｔｒｕｃｔｉｏｎ ｉｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ，ａ ｃｌａｓｓ ｏｆ ａｎｔｓ ｗａｓ ｅｎｃａｐｓｕｌａｔｅｄ ｔｏ ａ ｒｅｓｉｌｉｅｎｔ ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａｓｅｔ ａｎｄ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｏｐｅｒａｔｏｒｓ ｗｅｒｅ ｇｉｖｅｎ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｈｓ ｉｎ ｓｏｌｖｉｎｇ ｔｈｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ（ＴＳＰ）ｐｒｏｖｅ ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｐａｒａｌｌｅｌ ａｌｇｏｒｉｔｈｍ．Ｕｎｄｅｒ ｔｈｅ ｓａｍｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｅｎｖｉｒｏｎｍｅｎｔ， ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｒｅｓｕｌｔｓ ｂｅｔｗｅｅｎ ＭａｐＲｅｄｕｃｅ ｂａｓｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｉｍｐｒｏｖｅｓ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｓｐｅｅｄ ａｔ ｌｅａｓｔ ｔｅｎ ｔｉｍｅｓ ｔｈａｎ ｔｈｅ ＭａｐＲｅｄｕｃｅ ｏｎｅ． Ｋｅｙ ｗｏｒｄｓ：Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ａｌｇｏｒｉｔｈｍ；ｐａｒａｌｌｅｌｉｎｇ；Ｓｐａｒｋ；Ｈａｄｏｏｐ；ｃｌｏｕｄ ｃｏｍｐｕｔｉｎｇ ０ 引言 组合优化（ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ）问题的目标是从组 合问题的可行解集中求出最优解。这类问题虽数学描述相对 简单，但具有很强的工程代表性。典型的组合优化问题包括 旅行商问题（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ，ＴＳＰ）、加工调度问 题（如Ｆｌｏｗ—Ｓｈｏｐ、Ｊｏｂ—Ｓｈｏｐ）、０—１背包问题等。这类问题广泛 地存在于生产、生活中，然而，此类问题的求解却极为困难，其 主要原因在于：待优化问题的解空间巨大、解数量众多，即所 谓的“组合爆炸”，而传统的求解方法时间和空间复杂度高， 无法胜任上述问题的求解。实际上，对于生产、生活中的许多 组合优化问题，相对于花费大量时间寻求问题的最优解，快速 搜索到问题的一个满意解更具有实用价值。因此，在求解现 实世界中的组合优化问题时，人们将更多的精力投入到如何 运用元启发式算法（ｍｅｔａ ｈｅｕｒｉｓｔｉｃ）在尽可能短的时问内寻求 问题的满意解上。元启发式算法是一类用来指导与问题相关 的启发式方法，这些方法可以朝着可能含有更高质量解的搜 索空间进行搜索…。典型的元启发式算法包括：遗传算法 （Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）Ｌ２ｊ、粒子群优化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）算法 和蚁群优化（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）算法 等。“组合爆炸”的问题在当今 大数据时代的背景下显得尤为突出，随着数据的规模数量级 增长，出现问题规模大到即使应用元启发式算法也无法高效 地在廉价计算机上优化求解的问题。由于元启发式优化算法 大都通过抽象、总结自然界生物种群一些优秀的种群协作、进 化等方式行为而来，所以这类基于种群的算法在个体之间会 具有天然的内在并行性。因此，通过结合云计算技术来并行 实现元启发式算法以有效地解决上述问题成为一种可行、可 靠的方案。 本文基于云计算框架Ｓｐａｒｋ提出实现蚁群优化算法的方 法。本文的主要贡献为：针对蚁群优化算法的特点以及Ｓｐａｒｋ 的并行模式，设计并行蚂蚁构造解的过程的并行蚁群优化算 法，即将蚂蚁封装为弹性分布式数据集（Ｒｅｓｉｌｉｅｎｔ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａｓｅｔ，ＲＤＤ），并设计一系列的弹性分布式数据集转换操 作，使之完成并行。 收稿日期：２０１５－０６—１５；修回日期：２０１５—０７－０１。 基金项目：国家自然科学基金资助项目（６１１７５０４７，６１４０１３７４）；中央高校基本科研业务费专项资金资助项目（２６８２０１４ＲＣ２３）；教育部留学 回国人员科研启动基金资助项目；四川省苗子工程（２０１５０４５）；西南交通大学“埃实之星”培养计划。 作者简介：王诏远（１９８９一），男，山西吕梁人，硕士研究生，ＣＣＦ会员，主要研究方向：进化算法、云计算； 王宏杰（１９９１一），男，河北唐山 人，硕士研究生，ＣＣＦ会员，主要研究方向：数据挖掘、云计算；邢焕来（１９８３一），男，河北唐山人，副教授，博士，ＣＣＦ会员，主要研究方向：进化 计算、网络编码、软件定义网络；李天瑞（１９６９一），男，福建莆田人，教授，博士生导师，博士，ＣＣＦ会员，主要研究方向：智能信息处理、数据挖 掘、云计算。
第２８卷第１期
２００８年１月 计算机应用
Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ Ｖ０１．２８ Ｎｏ．１
Ｊａｎ．２００８
文章编号：１００１—９０８１（２００８）叭一０ＯＯ７—０２
基于蚁群优化的路由算法
王合义 ，丁建立 ，唐万生
（１．天津大学系统工程研究所，天津３０００７２；２．中国民航大学计算机科学与技术学院，天津３００３００； ３．天津市教育教学研究室，天津３００２００）
（ｗａｎｇｈｙ＠ｔｊｊｙ．ｎｅｔ；ｊｉａｎｌｉｄｉｎｇ＠ｙａｈｏｏ．ｃｏａ１．ｃｎ；ｔａｎｇ＠ｔｊｕ．ｅｄｕ．ｅｌ１）
摘要：针对移动自组网提出了一种基于蚁群优化的路由算法，该算法很好地利用了蚁群算法的自适应性，能有
效地承载移动自组网的负载。在ＮＳ－２乎台下的算法仿真表明，该算法在移动自组网环境下表现了较好的性能，从吞
吐量、乎均延迟、传送率三个指标比较来看，比ＡＯＤＶ和ＤＳＲ的性能都要好。
关键词：蚁群优化算法；移动自组网；重负载路由；蚂蚁路由算法
中图分类号：ＴＰ３９３ 文献标志码：Ａ
Ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ
ＷＡＮＧ Ｈｅ．ｙｉ 一．ＤＩＮＧ Ｊｉａｎ．１ｉ 一．ＴＡＮＧ Ｗａｎ ｓｈｅｎｇ
（１．Ｉｎｓｔｉｔｕｔｅ ｏｆｓ ⅢＥ增 ，Ｔｉａｎｆｉｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ ３０００７２，Ｃｈｉｎａ； ２．Ｃｏｌｌｅｇｅ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏ￣，Ｃｉｖｉｌ Ａｖｉａｔｉｏｎ ＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎａ，Ｔｉａｎｊｉｎ ３００３００，Ｃｈｉｎａ； ３．Ｔｉａｎｊｉｎ Ｔｅａｃｈｉｎｇ ａｎｄ Ｒｅｓｅａｒｃｈ Ｄｅｐａｒｔｍｅｎｔ，Ｔｉａｎｆｉｎ ３００２００，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｎ ａｐｐｒｏａｃｈ ｂａｓｅｓ ｏｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｒｏｕｔｅ ａｌｇｏｒｉｔｈｍ ｏｆ ｍｏｂｉｌｅ Ａｄ Ｈｏｃ ｎｅｔｗｏｒｋｓ．
龙源期刊网
蚁群算法求解优化函数
作者：刘 媛 韩应征
来源：《中国新技术新产品》2009年第12期
摘 要：蚂蚁具有找到蚁穴与食物源之间最短路径的能力，受此启发提出的蚁群算法最初用于解决旅行商问题，具有自适应性、鲁棒性及本质上的并行性等许多特点，广泛适用于各种静态和动态的组合优化问题中，具有潜在的应用前景。为了求解一般的函数优化,文章在标准蚁群算法的基础上,引入遗传算法的编码方式,并对蚁群算法的信息素更新进行改进。通过对几个经典测试函数的求解,证明了算法的有效性。
关键词：蚁群算法；函数优化；函数逼近；鲁棒性；神经网络
1 基本蚁群算法
蚂蚁在从食物源到巢穴往返的过程中，能在其走过的路径上分泌一种化学物质,即信息素(pheromone)。运动时它们能感知信息素，并总是倾向于朝着信息素强度高的方向移动。蚁群之所以能够找到最短路径，源于蚂蚁群体的一种正反馈机制。蚂蚁在经过的路径上留下的信息素，会吸引更多的同伴选择这条路径,导致该路径上的信息素又增多，最终越来越多的蚂蚁选择了该路径。Ant System最先用于求解旅行商问题(TSP)，下面就以TSP问题为例来说明Ant
System。设m为蚁群数量；dij为城市i、j之间的距离;τ(t)为t时刻连接城市i和j的路径(i,j)上的残留信息量，初始时刻各路径上信息量相等,设τ(0)=C(C为常数);η表示城市i转移到城市j的期望程度，可根据某种启发式算法具体确定,在TSP问题中一般取ηij=l/dij。
蚂蚁k(k=l,2,…,m)根据各条路径上的信息量决定转移方向，t时刻蚂蚁k从城市i向城市j转移的概率Pij(t)计算如下：
其中,allowedK={0,1,…,n-1}-tabuk表示蚂蚁k下一步允许选择的城市。与自然蚁群系统不同之处在于人工蚁群系统具有一定的记忆力，tabuk(k=1,2,…,m)用于记录蚂蚁k所走过的城市，集合tabuk随着进化过程进行动态调整人工蚁群保留了自然蚁群信息素挥发特点,随着时间的推移，以前留下的信息逐渐消逝,参数ρ(0≤ρ
２０１２年第ｉ期 计算机光盘软件与应用
Ｃｏｍｐｕｔｅｒ ＣＤ Ｓｏｆｔｗａｒｅ ａｎｄ Ａｐｐ ｌ ｉ ｃａｔ ｉ ｏｎｓ 软件设计开发
基于蚁群算法的泊位调度优化与仿真
王民川 。苑彬
（１．郑州广播电视大学，郑州４５０００７；２．河南职业技术学院，郑州４５００００）
摘要：在全球贸易经济聚焦在中国的同时，港口的吞吐能力成为目前港１２：２业的主要矛盾。提高泊位这个环节的运作
能力，减少船舶在港时间，增加港口的吞吐能力成为主要研究对象。本文采取仿真模型与优化算法相结合的研究方法，把
泊位调度问题转化为旅行商问题，建立了一个泊位岸桥协调调度，通过蚁群算法建立数学模型，使船舶在港时间最短为目 标建立函数，求得最佳调度方案。用ＰｒｏＭｏｄｅｌ建立船舶到港停泊及离港仿真模型。验证泊位调度优化的有效性，以便指导
港口实际的泊位调度。
关键词：蚁群算法；泊位调度；ＰｒｏＭｏｄｅｌ仿真模拟
中图分类号：ＴＰ１８ 文献标识码：Ａ 文章编号：１００７—９５９９（２０１２）ｏ１＿０１３９—０２
Ｂｅｒｔｈ Ｓｃｈｅｄｕｌｉｎｇ Ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ Ｓｉｍｕｌａｔｉｏｎ Ｂａｓｅｄ ｏｎ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ
Ｗａｎｇ Ｍｉｎｃｈｕａｎ’，Ｙｕａｎ Ｂｉｎ，
（１．Ｒａｄｉｏ ａｎｄ Ｔｅｌｅｖｉｓｉｏｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｚｈｅｎｇｚｈｏｕ，Ｚｈｅｎｇｚｈｏｕ ４５０００７，Ｃｈｉｎａ；２．Ｈｅｎａｎ Ｐｏｌｙｔｅｃｈｎｉｃ，Ｚｈｅｎｇｚｈｏｕ ４５００００，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎ ｇｌｏｂａｌ仃ａｄｅ ａｎｄ ｅｃｏｎｏｍｉｃ ｆｏｃｕｓ ｉｎ Ｃｈｉｎａ ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ．ｔｈｅ ｐｏｒｔ ｈａｎｄｌｉｎｇ ｃａｐａｃｉｔｙ ｏｆ ｔｈｅ ｐｏｒｔ ｉｎｄｕｓｔｒｙ ｉＳ
ｃｕｒｒｅｎｔｌｙ ｔｈｅ ｐｒｉｎｃｉｐａｌ ｃｏｎｔｒａｄｉｃｔｉｏｎ．Ｂｅｒｔｈｓ ｉｎ ｔｈｉｓ ｐａｒｔ ｏｆ ｔｈｅ ｏｐｅｒａｔｉｏｎａ１ ｃａｐａｂｉｌｉｔｉｅｓ。ｒｅｄｕｃｅ ｓｈｉｐ ｉｎ Ｈｏｎｇ Ｋｏｎｇ ｔｉｍｅ．ｔｏ ｉｎｃｒｅａｓｅ
