[云计算环境下鱼群算法的研究]鱼群算法

　　(1.合肥工业大学管理学院，安徽合肥230009；2.教育部过程优化与智能决策重点实验室，安徽合肥230009；3.安徽财贸职业学院电子信息系，安徽合肥230601)
　　摘要：人工鱼群算法(AFSA)是一新型仿生优化算法，已成功地应用于求解很多组合优化难题。但人工鱼群算法对这些问题的求解主要是在集中式串行的环境下，而云计算环境下应用人工鱼群算法分布式并行对问题进行求解的研究很少。该文应用云计算技术将人工鱼群算法并行化，将人工鱼群算法和遗传算法融合，显著提高了算法求得全局最优解的能力。仿真实验取得了较好的结果。关键词：云计算；MapReduce编程模式；人工鱼群算法；遗传算法
　　中图分类号：TP18文献标识码：A文章编号：1009-3044(2012)18-4486-04
　　Research on Artificial Fish School Algorithm in Cloud Computing
　　WANG Hui-ying1,2,3
　　(1.School of Management, Hefei University of Technology, Hefei 230009, China; 2.Key Laboratory of Process Optimization and Intelli? gent Decision-making, Ministry of Education, Hefei 230009, China；3.Department of Electronics and Information, Anhui Finance & Trade Vocational College, Hefei 230601, China)
　　Abstract: The artificial fish school algorithm (AFSA) is a nove1 bio-inspired optimizing method and was applied successfully to hard com? binational optimization problems. But it solves the problems mainly under the centralized serial environment. The research of the applica? tion of artificial fish school algorithm for distributed parallel problem solving in cloud computing is comparatively little. This paper uses cloud computing to parallel artificial fish school algorithm and combining artificial fish school algorithm with genetic algorithm. it greatly improves the ability of seeking the global excellent result. The simulation results show that the algorithm is more efficient.
　　Key words: cloud computing; MapReduce; artificial fish school algorithm; genetic algorithm
　　 4.3算法的时间开销
　　云计算环境中，任务执行时间，除求解问题所需的时间外，云计算框架也要消耗一定的时间。其耗用的时间包括：任务的部署，Map中间结果的排序、归类，Reduce结果的归并，结果的输出及网络传输等。问题求解所需时间包括：Map和Reduce时间等。为此，我们研究云计算环境中算法运行时各阶段的时间开销，来更好地求解问题。
　　选用大规模任务实例30.500-00来考察算法MIA随Map数量变化的情况，Map数量取10.20.30，其余参数同上。算法MIA运行时间消耗如表2所示。表2中结果为连续运行20代，每代各阶段的平均值。T1表示任务开始到Map开始运行所消耗的时间；T2是Map阶段的时间；T3是从Map结束到Reduce开始的时间，包括中间结果的排序、归类等操作的时间；T4为Reduce阶段的时间；T5为Reduce结束到下一任务开始的时间，包括Reduce结果的归并、输出等时间，Total为总时间。
　　从表2可以看出，T1、T3、T5在Map数量变化时，变化不大，即云计算框架为实现任务的并行，框架所需的时间基本稳定，变化不大；T4为Reduce阶段运行的时间，其相对很小；T2为Map阶段运行所占的时间，其占整个任务所需时间的大部分，且随Map数量的变化较大。这些正同问题求解过程相一致，反映问题求解的关键，该文对人工鱼群算法所做的工作主要集中在应用Map来并行化人工鱼群算法中最耗时的部分。
　　文章应用云计算技术将人工鱼群算法并行化，使其运行在云计算环境中，增强人工鱼群算法处理大规模问题的能力。文章提出基于MapReduce的改进人工鱼群算法MIA，给出其Map函数和Reduce函数；并将人工鱼群算法和遗传算法融合，给出算法的框架。改进后的算法有效改善人工鱼群算法一般仅能得到满意解域的缺陷。仿真实验，说明了该文算法处理大规模问题的能力和算法改善后的性能，实验结果良好。
　　[1] Ghemawat S, Gobioff H, Leung S T. The Google file system. In: Proc. of the 19th ACM Symp. on Operating Systems Principles[M].New York: ACM Press, 2003.:29-43.
　　[2] Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[C]//Proc. of the 6th Symp. on Operating System Design and Implementation. Berkeley: USENIX Association, 2004:137-150.
　　[3] Burrows M. The chubby lock service for loosely-coupled distributed systems[C]//Proc. of the 7th USENIX Symp. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006:335-350.
　　[4] Chang F, Dean J, Ghemawat S, et al. Bigtable: A distributed storage system for structured data[C]// Proc. of the 7th USENIX Symp. on Op? erating Systems Design and Implementation. Berkeley: USENIX Association, 2006:205-218.
　　[5]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践, 2002, 22(11):32-38.
　　[6]李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法应用[J].山东大学学报:工学版, 2004, 34(5): 64-67.
　　[7] Multi-Demand Multidimensional Knapsack problem [EB/OL]..uk/~mastjjb/jeb/orlib/mdmkpinfo.html.