246 2013java实现旋转门算法 基于MapReduce量子蚁群算法.pdf 4页，49 （19） and 计算机工程与应用 基于 的量子蚁群算法 贾瑞玉，李亚龙 JIA Ruiyu, LI 安徽大学 计算机科学与技术学院，合肥 of and , Anhui , Hefei , China JIA Ruiyu, LI . - ant based on model. and , 2013, 49 （19）：246-249. ：The - ant is a new which is based on the of ant opti- and , and has and . This paper aims at the of Quan- tum- ant , uses cloud to - ant , makes it to meet the key/value model of , puts -based - ant and runs the on . Using 0- 1 for test, with the of data set, of , MQACA good speed-up ratio and , the of MQACA. Key words ：- ant ; cloud ; model 摘 要：量子蚁群算法是在蚁群算法的基础上结合量子计算而提出的，该算法具有较好的全局寻优能力和种群多样性。
应用 的key/value 编程模型，将量子蚁群算法并行化，提出了基于 的量子蚁群算法（MQACA ），并将 其部署到 云计算平台上运行。对0- 1 背包问题的测试结果证明，随着数据规模的扩大和并行程度的提高，MQACA 具有良好的加速比和并行效率。 关键词：量子蚁群算法；云计算； 模型 文献标志码：A中图分类号： ：10.3778/j.issn. 1002-8331.1302-0036 1 引言的态矢量和量子旋转门引入到蚁群算法中，采用量子旋转随着信息和通信技术的快速发展，计算模式经历了把门及最优解对信息素更新，加快了算法的收敛速度并且避 任务集中交付给大型处理机的模式，基于网络的分布式任免了早熟收敛。量子蚁群算法已成功地求解出许多NP 难[1]题，文献[9]使用量子蚁群算法对0- 1背包问题（0/ 1 务处理的模式，发展到了按需处理的云计算 模式。许多 智能算法可以在云计算系统实现分布式计算，从而充分利 ）进行求解，并用数值实验说明了其有效性；文献 用云计算系统的强大计算能力。
[10]分析了量子蚁群算法的优缺点，提出一种新的量子蚁蚁群算法最早由意大利学者 于1991年提出， 群算法用于求解旅行商问题（ ， 该算法具有较好的寻优能力和较强的鲁棒性，并成功地用TSP ），并设计了一种量子交叉策略，避免搜索陷入局部最 于TSP 求解、工件排序、背包问题、车辆调度等多目标组合优，进一步提高了量子蚁群算法的性能。但量子蚁群算法2-6对这些问题的求解是在串行环境下进行的，国内尚没有利 优化问题 。量子进化算法（QEA ）是KuK- 等人于2002 年提出的java实现旋转门算法，是一种基于量子理论的进化算法。 用云计算将量子蚁群算法并行化的研究。[8] 提出的 编程模型，允许用户方便地 它吸收了量子计算 中的叠加态、相干性和纠缠性等思想， 使得量子算法突破了传统算法的极限，表现出更好的性在数据中心开发分布式应用程序，但是许多智能算法需要 能。该算法以其独特的计算性能成为研究的热点，引起国一种迭代的方式，并不遵循 的两个阶段的模 内外众多学者的研究兴趣，并取得了许多研究成果。
量子式。文献[11]提出了一个具有层次处理阶段的 蚁群算法则将量子计算和蚁群算法相结合，把量子计算中模型，可以自动地使遗传算法并行化。本文受此模型的启 基金项目：安徽省教育厅自然科学研究基金资助重点项目（No. ）。 作者简介：贾瑞玉（1965—），女，副教授，硕士生导师，主要研究方向为智能计算与数据挖掘；李亚龙（1989—），男，硕士研究生，主要研究方向为智能计算。E-mail ： 267@ 收稿日期：2013-02-05 修回日期：2013-05-07 文章编号：1002-8331（2013 ）19-0246-04 CNKI 出版日期：2013-05-29 /kcms// 11.2127..001.html 贾瑞玉，李亚龙：基于 的量子蚁群算法2013 ，49 （19） 247 发，将QACA 与 结合，实现了QACA 在云环境，其价值为 ，背包的容量为c ，现从这nw (i 12 n)vii 中的并行化，并应用于0- 1背包问题的求解；实验结果证明个物品中选出若干个放入背包，使得放入的物品重量不超 了其有效性与可行性。
过c ，且总价值达到最大。使用蚁群算法求解0- 1背包问题时，某一物品上聚集的信息素越多，则该物品被选择的概 2 并行计算编程模型率就越大。在QACA 中，对蚂蚁在物品上聚集的信息素进 2.1 模型简介行量子比特编码，采用量子旋转门更新蚂蚁携物品的量子受函数式语言中的Map 和 函数的启发，比特，聚集在物品上的信息素更新转变成量子位概率幅的 公司提出了 （映射-归并算法）的抽象模型，该模更新。 型可以使用户能够轻松地开发大型分布式应用程序。在[9]量子蚁群算法流程 ： 该模型中，每个Map 函数是独立的，并使用出现故障后重t tt步骤1 初始化量子蚁群 A(t)(a a a ) ，蚂蚁个1 2n 新执行的容错机制，可以很容易地实现大型并行化计算。 数为n ，量子位数为物品数m ，at (i12 n)为种群中第i 开源社区的[12] 项目用Java 语言实现了该模t 次迭代的第i 个量子蚂蚁。 型，同时也为云计算提供了一个开源实现平台。t t | té | |α ùα αt 1 2 | 计算模型的核心是Map 和 两个函ai ê | |ú（3 ）| | |ê t tt úβ β β| | |1 2 m 数，这两个函数均由用户编写。
Map 函数对用户输入的键ëû 值对 (k/v) 进行计算并产生一系列中间键值对 (k /v ) 。为了使算法初始搜索时所有状态以相同概率出现，1 1kA(0) 中所有的αβ (i12 m) 取值均为1/2 。 框架将关键字是 的键值对聚合起来产生关于i i1 k 键的值集合list(v ) 传给用户定义的 函数。步骤2设定各参数α、β、ρ 的值，最大迭代次数NMAX ， 11 函数再进一步处理、合并该中间键的值集合，最后形成一当前迭代次数t0 ，信息素τ(0)1 。i 个相对较小的键值对集合list(k v ) 。步骤3每只蚂蚁独立地构造一个解。蚂蚁k (k1,2, n)2 2整个过程可用如下形式表示：随机选择一个物品i 装入背包，然后按概率计算剩余的各M ap (k v) ®list(k v )（1） 个物品被选择的概率p k来选择物品放入背包，直到背包不1 (k list(v )) ®list(k v )（2 ） 能再装入物品。物品被选择概率如公式（4 ）所示：112 2 2.2 处理阶段ìαβ[τ(t)] [η(t)]ï iis ÎJ (k)在 计算模型中，整个作业的计算流程包含k ïαβpå [τ (t)] [η (t)]（4 ）i ísss ÎJ k 5 个阶段。
ï ( )ï0, other（1）Input 阶段：用户输入的数据会被自动切分成m 个îτ(t) 数据分片（）并被转换为 (k/v) 的形式分配给m 个Map式（4 ）中， 表示第t 次迭代时物品i 所含信息素的量，启i 任务，每个Map 任务会被分派到集群的某一台机器上运发函数 η(t) 表示物品i 单位质量的价值，即η(t)v /w ，αiii i 行，这些Map 任务在不同的机器上是并行执行的，对每一和 分别表示物品所含信息素的量和物品单位质量价值β 个Map 任务都要指明输入/输出的路径和其他运行参数。J (k)的权重， 为蚂蚁k 没有选择的物品的集合；信息素更新（2 ）Map 阶段：使用Map 函数中用户定义的Map 操作方程： 对(k/v) 键值对进行处理后，以list(k v ) 键值对形式输出。τ(t +1) (1 -ρ)τ(t) +Dτ(k)（5 ）1 1iii（3 ） 阶段：在调用 函数之前会对Map 任t 2Dτ(k) Q β（6 ）| | 务处理完成的数据进行分割，具有相同关键字的键值对合iiDτ(k)其中， i表示蚂蚁k 在第i 个物品上留下的信息素的 并在一起形成 (k list(v )) ，每一个(k list(v )) 就会分配到1111量，Q 为一常数， 为信息素的挥发性ρ(0 ρNMAX，输出最优解；否 结果list(k v ) 。
2 2（5 ） 阶段：此阶段把 输出结果写入到输则tt +1 ，转步骤3 。 出目录的文件中。4 基于 的量子蚁群算法（MQACA ） 3 量子蚁群算法（QACA ）对于0- 1背包问题，QACA的时间复杂度为O(NMAX ×m ×n) ，下面结合0- 1 背包问题来说明量子蚁群算法。0- 1 背计算量主要集中在步骤3 ，蚂蚁独自求解的过程。MQACA 包问题描述为：给定n 个物品和1个背包，物品i 的重量是算法用 来完成种群每一代进化的过程。Map 248 2013 ，49 （19） and 计算机工程与应用 完成蚂蚁的独立求解过程，其中蚂蚁家族的索引号作为Emit(k v ) ；1 1 键，蚂蚁的最优解和量子信息作为值，这一部分可以并行} 操作； 表达求得较优解和更新量子蚂蚁信息过程，} 输出信息转换为Map 输入的格式作为下一代Map 函数的4.3 阶段 输入，进入下一代循环。 函数接收Map 函数输出的键值对，其主要功能 4.1 MQACA 算法的步骤是分解出各个蚂蚁家族成员的解和值，求出其中的最优解具体步骤如下：和最优值，然后使用量子旋转门规则更新蚂蚁家族中各成员的量子信息，根据公式（5 ）对信息素文件进行更新，判断步骤1 初始化种群，产生键值对(k/v)java实现旋转门算法，以文件形式存是否满足终止条件，如果是则输出最优解和最优值；否则 放于 文件系统，k 表示蚂蚁家族的索引，v 表示蚂蚁list(k v )k将输出键值对保存在 文件系统中， 是 的解和量子信息。
2 22蚂蚁家族索引 是更新后的解和量子蚂蚁信息。步骤2 Map 函数接收(k/v) ，计算每个量子蚂蚁的适应2函数如函数2 所示。list(k v ) kv 度值，产生中间结果， 表示蚂蚁家族的索引，1 1 11函数2 MQACA 的 函数 表示本家族单个蚂蚁求得的解和量子信息。 (k list(v ))步骤 函数接收Map 函数产生的键值对11{ list(k v ) ，应用量子旋转门规则更新量子蚂蚁及全局信息1 1kint n ；//蚂蚁家族 中蚂蚁的个数1 素，判断是否达到最大代数，如果是则输出最优值；否则保for (int i 0 ; i