摘要
近年来,仿生算法得到了学术界的高度重视和长足的发展,并且涌现了很多新的算法,如粒子群算法、分布估值算法和Memetic算法等等。同时,仿生算法在广度和深度方面也有进一步的发展,尤其是在并行化方面,出现了许多新的尝试和成功案例。例如,先后有基于超级计算机、工作站集群、多核处理器、GPU和网格计算等的并行化实现。近几年云计算的出现和迅速发展,尤其是MapReduce编程模型的出现,为仿生算法的并行化提供了新的发展方向,本论文正是在此背景下提出的,具体的研究内容和创新点有:
1)首先介绍了几种仿生算法和它们的发展现状、基本原理和应用领域,并总结了它们的收敛性和发散性的机理。启发式仿生算法,本质上都是随机搜索算法,对于复杂优化问题的性能不高和容易出现停滞现象,学术界一直致力于寻找发散与收敛之间的平衡点,一方面利用并行计算方法提高它们的性能,同时也采用各种优化方法提高解的质量。本文试图用最新的云平台Hadoop和Haloop来提高仿生算法的效率,并且优化了其中两种仿生算法的并行化策略。
2)仿生算法并行化主要是提高算法的运算性能,让原来串行的算法变为可以并发执行的并行算法,从而缩短算法执行时间。但往往忽略了解质量问题,即停顿和陷入局部极值问题。本文提出的并行化试图在提高运算性能的同时,尽可能地扩大搜索空间,即被处理数据的并行化。如蚁群算法就提出动态正反馈和动态正负反馈来改进发散性和收敛性。蚁群被分成为若干子群,在算法前期,子群之间信息素相互“排斥”,而后期相互“吸引”,从竞争转为合作,这相当于前期各子群的搜索空间是相互独立的小岛。随着时间的推进,群间信息素逐渐融合,小岛的界限也逐渐消失,最终融合成一个大岛。这种改进可以保证算法前期搜索空间尽可能发散,后期则尽快收敛到全局最优解,并通过吸收态Markov模型对算法的收敛性进行了初步分析。
3)沿用蚁群算法并行化优化的思路,对粒子群算法也采用动态反馈机制,并建立卫星模型。在算法前期,减小全局最优粒子的“引力”,让各个粒子子群尽可能地发散飞行,扩大搜索空间,即类似卫星的“自转‖;而随着算法不断地迭代发展,“引力”不断加强,让群的所有粒子尽快收敛到全局最优解,即类似卫星的“公转”。通过对其收敛性进行了详细分析,得出各参数的合理取值范围,也从理论上证明了算法的有效性。实验数据表明,改进算法更适合求解一定规模、较为复杂的优化问题。
4)接下来介绍Hadoop和Haloop平台的特点,尤其是它们的核心部分―MapReduce框架的实现和工作机制,同时也对推测执行进行了介绍,尤其重点说明了Haloop改进的功能点和改进内容。
5)在详细分析和对照Haloop现有的调度算法之后,本文针对Haloop的任务调度进行了改进。为了提高数据的本地性,分别给出了针对Map任务的二分图最大匹配算法和针对Reduce任务的加权二分图最佳匹配算法,尽可能地提高Map任务和Reduce任务的数据本地性,减少数据的网络传输,―移动计算比移动数据更划算‖。
6)最后,结合Haloop平台API的特点和要求,用MapReduce编程模式分别实现了蚁群算法和粒子群算法的并行化。由于Haloop是组建在普通PC基础之上的,成本低廉,同时支持大规模的动态扩展,很适合应用仿生算法解决大规模的NP完全问题。通过仿真实验,初步确定算法改进的有效性和Haloop对仿生算法并行化的适应性。
In recent years,bionic algorithm attracted lots of academic attention,considerableprogresses also have been achieved. Many new algorithms are emerging, such as PSO(Particle Swarm Optimization), EDAs (Estimation of Distribution Algorithms) and MA(Memetic Algorithm), etc. Meanwhile, the bionic algorithms have been continuouslyresearched in breadth and depth aspects, especially parallelization of the bionic algorithms.There have appeared much attemptation and success practice,e.g. the parallelization onsuper-computers,workstation clusters,multi-core processors,GPU and grid computing,etc. Recently, the emergence and rapid development of cloud computing,particularlyMapReduce programming mechanism provides a new direction for the parallelization of thebionic algorithms.
The main contents and innovations of this dissertation are as follows:
1) Firstly,the dissertation introduces several bionic algorithms with their developments,basic principles and applications,and compares their convergence and divergencemechanism. The heuristic bionic algorithms are random search algorithms in essence,theperformance for complex optimization problems is not high and prone to stagnation.Many researchers made great efforts to find the tradeoff between exploration andexploitation of the bionic algorithms,they not only resorted to parallel computing toenhance performance,but also optimized the algorithms to improve the solution quality.This dissertation also attempts to provides new parallelization strategies for the bionicalgorithms and parallelize them based on Hadoop,Haloop platform and MapReducemechanism to improve efficiency of the algorithms.
2) The purpose of the bionic algorithm parallelization is mainly to improve performance bymeans of changing serial mode into parallel one. The algorithms can be executedconcurrently,but the solution quality is often overlooked. This dissertation presents theparallelization,trying to improve operational performance as well as expand the searchspace by parallelizing data processing. As for the ant colony optimization (ACO),thisdissertation proposes the dynamic positive feedback and negative feedback approach to achieve dynamic divergence and convergence. Usually,ants are divided into severalcolonies,the pheromone of the other colonies will exclude the ants from one certaincolony at the prior stage to enhance search diversity and to avoid prematureconvergence,which is called competition. At the posterior stage,the pheromone of theother colonies will change the roles to attract the ants from this colony,which is calledcooperation. The positive and negative feedback will change the weights of the exclusivepheromone and the attractive pheromone to lead the transition from the competition to thecooperation occurring dynamically and gradually. Preliminary analysis for convergenceof proposal algorithms is provided based on the absorbing state Markov model.
3) Similar to the idea of ACO,the dynamic feedback mechanism is also introduced to theparticle swarm optimization (PSO),and this optimization version of PSO is called asPP-PSO (Planet Parrallel PSO). The particles are also divided into several colonies,andthe colonies revolve around a global optimal particle. At the early stage,the center’s"gravity" is weak,so that each particle can flight freely,expanding the search space asmore as possible,similar to the satellite’s "rotation". With the algorithm execution,thecenter’s "gravity" strengthens gradually,all ofthe particles converge to the globaloptimalsolution as soon as possible,similar to the satellite’s "revolution". Detailed analysis for itsconvergence and reasonable range of each parameter are deduced, and the effectivenessof the algorithm is also theoretically proved.
4) Secondly,the features of Hadoop and Haloop platform are listed and compared by thisdissertation. Especially the principle and mechanism of MapReduce framework ishighlighted. Simultaneously, the improved functions of Haloop platform are also pointedout.
5) After detail analysis and comparison of existing scheduling algorithms of Haloop,a newtask scheduling algorithm has been proposed. In order to improve data locality,theHungarian algorithm of the bipartite graph is introduced to the map task schedule,and theKuhn-Munkres(KM) algorithm of the bipartite graph is introduced to reduce tasksschedule.―Moving Computation is Cheaper than Moving Data‖.
6) Finally, according to Haloop Platform API's requirements and the programming model ofMapReduce framework,the proposed parallelizations of ACO and PSO are implemented. As Haloop platform is built on the ordinary PCs,the cost is very low,and large-scaledynamic expansion is supported,therefore,it is suitable for large-scale applications of thebionic algorithms to solve NP-complete problem. The experimental results proved theeffectiveness of the proposed algorithms, and adaptability of Haloop platform toimplement parallelization of the bionic algorithms.
引文
[1] Glover F, Tabu Search: A Tutorial, Special Issue on the Practice of Mathematical Programming[J]. Interfaces,1990,20(1):74-94
[2] Soto Ricardo, Crawford Broderick, Galleguillos Cristian, et al. A hybrid AC3-tabu searchalgorithm for solving Sudoku puzzles. Expert Systems With Applications [J],2013,40(15):5817-5821
[3] Metropolis N, Rosenbluth A, Rosenbluth M, et al. Equation of state calculations by fastcomputing machines [J]. Journal of Chemical Physics,1953,21(6):1087-1092
[4] Kirkpatrick S, Gelatt Jr C D, Vecchi M P. Optimization by simulated annealing, Science [J],1983,220(4598):671-680
[5]李文勇,李泉永.基于模拟退火的全局优化算法[J].桂林电子工业学院学报,2001,21(2)
[6]谢云,尤矢勇一种并行模拟退火算法一加温一退火法[J],武汉大学学报,并行计算专刊,1991
[7]席自强.单纯形一模拟退火算法.湖北工学院学报[J],2000,15(1):27-29
[8] Oliveira, Hime A. e, Jr.; Petraglia, Antonio, Solving nonlinear systems of functional equationswith fuzzy adaptive simulated annealing [J], Applied Soft Computing,2013,13(11):4349–4357
[9] Holland J H, Outline for a logical theory of adaptive systems.Journal of the Association forComputing Machinery[J].1962,9(3):297一314
[10] Holland J H. Adaptation in natural and artificial system [M]. Ann Albor: The University ofMichigan.1975
[11] Goldberg D E. Genetic Algorithms in Search, Optimization, and Machine Learning [M]. AddisonWesley,1989
[12] Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies [J]. Proceedingof the1st European Conference on Artificial Life,1991:134-142
[13] M. Dorigo. Optimization, learning and natural algorithms [D]. Ph.D. Thesis, Department ofElectrionics, Politecnico diMilano, Italy,1992
[14] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-part B,1996,26(1):29-41
[15] Thomas. Stützle,Holger H. Hoos,MAX–MIN Ant System [J],Future Generation ComputerSystems,2000,16(8):889-914
[16] Dorigo M. Optimization, Learning and Natural Algorithm [D], ph. D. Thesis, Department ofElectronics, Politecnico di Milano,1992
[17] Dorigo M, Gambardella L M. Ant colony system:A cooperative learning approach to thetraveling salesman problem [J]. IEEE Transactions Evolutionary Computation,1997,1(1):53-66
[18] Eberhart R C, Kennedy J. A new optimizer using particle swarm theory [A], In Proceedings of thesixth international symposium on micro machine and human science [C], Nagoya, Japan.Piscataway: IEEE.1995:39-43
[19] Kennedy J, Eberhart R C. Particle swarm optimization [A]. Proc. IEEE Int. Conf. NeuralNetworks [C],1995(4):1942-1948
[20] Shi Y.H., Eberhart R.C. A Modified Particle Swarm Optimization [A].1998IEEE InternationalConference on Evolutionary Computation[C], Anchorage, Alaska, l998:69-73
[21] Clerc M. The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm-Optimization [R]. Proceedings of the Congress on Evolutionary Computation. Washinton D. C.,1999:1951-1957
[22] McCullonch W S, Pitts W A. A Logical Calculus of the Ideas Immanent In Nervous Activity [J],Bulletin of Mathematical Biology,1943,5(4):115-133
[23] Hebb D O. The Organization of Behavior: A Neuropsychological Theory [M]. New York: Wiley,1949
[24] Rosenblatt. F. Principles of Neurodynamics [M]. Spartarn,1961
[25] Widrow B, Hoff M E. Adaptive Switching Circuits, Institute of Radio Engineers, WesternElectronic Show and Convention [J]. Convention Record, Part4,1960:96-104
[26] Hopfield J J. Neural Networks and Physical Systems with Emergent Collective ComputationalAbilities [A], Proceedings of the National Academy of Sciences of the United States of America[C].1982,79(8):2554-2558,[part1: Biological Sciences]
[27] Rumelhart D E, Hinton G E, Williams R J. Learning internal representations by errorpropagation[J]. Parallel Distributed Processing,1986(1):318-362
[28] Jerne N K. Towards a network theory of the immune system [J]. Annual Immunology,125C,1974:73-389.
[29] Fanner J D., Packard N H., Perelson A.S. The immune system, adaptation and machine learning[J], Physiea,22D,1986:187-204.
[30] Baluja S, Davies S. Using optimal dependency-trees for combinatorial optimization: Learning thestructure of the search space [A]. Proceedings of the14thInternational Conference on MachineLearning [C]. Morgan Kaufmann,1997:30-38
[31] De Bonet J S, Isbell C L, Paul Viola Jr. MIMIC: Finding Optima by Estimating ProbabilityDensities [J]. Advances in Neural Information Processing Systems, Cambridge: The MIT Press,1997
[32] Martin Pelikan, Heinz Muehlenbein, The Bivariate Marginal Distribution Algorithm [J],Advances in Soft Computing,1999:521-535
[33] M ühlenbein H, Mahnig T. The factorized distribution algorithm for additively decomposablefunctions[A]. Proceedings of the1999Congress on Evolutionary Computation [C].1999,1:752-759
[34] Pelikan M, Goldberg D E, Cantú-Paz E. BOA: The Bayesian Optimization Algorithm [A].Wolfgang Banzhaf, Jason Daida, et al. Proceedings of the Genetic and Evolutionary ComputationConference (GECCO-99)[C].California: Morgan Kaufmann,1999:525-532
[35] Pablo Moscato, Michael G. Norman. A Memetic Approach for the Travelling SalesmanProblem-implementation of a Computational Ecology for Combinatorial Optimization onMessage-passing Systems [A]. In Proceedings of the International Conference on ParallelComputing and Transport Applications.1992
[36] Nicholas J. Radcliffe,Patrick D. Surry. Formal Memetic Algorithms [M]. EvolutionaryComputing,1994
[37] Krasnogor N, Smith J. A tutorial for competent memetic algorithms: model, taxonomy, anddesign issues [J]. IEEE Transactions on Evolutionary Computation,2005,9(5):474-488
[38] Ong Y S, Lim M H, Zhu N, et al. Classification of adaptive memetic algorithm: a comparativestudy [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B:Cybernetics,2006,36(1):141-152
[39] Abbass, H.A.A monogenous mbo approach to satisfability[C].Proceeding of the InternationalConferenceon Computational Intelligence for Modeling, Control andAutomation.CIMCA’2001,Las Vegas, NV, USA,2001
[40] Taher Niknam.An effcient hybrid evolutionary algorithm based on PSO and HBMO algorithmsfor multi-objective Distribution Feeder Reconfguration[J].Energy Conversion and Management,2009,50(8):2074–2082
[41] Yannis Marinakis, Magdalene Marinaki, Georgios Dounias.Honey bees mating optimizationalgorithm for the Euclidean traveling sales problem[J]. InformationSciences,2011,181(1):4684-4698.
[42] Javad Olamaei, Taher Niknam, sirous badali, Arefia.Distribution feeder reconfiguration for lossminimization based on modified honey bee mating optimization algorithm[J].EnergyProcedia,2012,(14):304-311
[43] Arit Thammano, Patcharawadee Poolsamran.SMBO: A self-organizing model of marriage inhoney-bee optimization [J].Expert Systems with Applications,2012,39(5):5576-5583
[44] Patcharawadee Poolsamran, Arit Thammano.A modified marriage in honey-bee optimization forfunction optimization problems [J].Procedia Computer Science,2011,(6):335-342
[45] Chang HS.Converging marriage in honey-bees optimization and application to stochasticdynamic programming[J].Journal of Global Optimization,2006,35(3):423-441
[46] Curkovicp,Jerbic.Honey-bees optimization algorithm applied to path planningproblem[J].International Journal of Simulation Modelling,2007,6(3):154-165
[47] Amiri B, Fathian M.Integration of self-organizing feature maps and honey bee matingoptimization algorithm for market segmentation[J].Journal of Theoretical and AppliedInformation Technology,2007,3(3):70-80
[48] Fathian M, Amiri B.A honey bee-mating approach for cluster analysis [J]. International Journal ofAdvanced Manufacturing Technology,2008,38(7-8):809-821.
[49] Haddad O B, Afshar A, Marino M A.Optimization of nonconvex water resource problems byhoney-bee mating optimization (HBMO) algorithm [J]. Engineering Computations,2009,26(3):267-280
[50] Ming-Huwi Horng, Ren-Jean Liou, Jun Wu.Parametric active contour model by using the honeybee mating optimization[J].Expert Systems with Applications,2010,37(10):7015-7025
[51] Magdalenem, Yannis M, Constantin Z.Honey bees mating optimization algorithm for financialclassification problems [J].Applied soft computing,2010,10(3):806-812.
[52] Adleman L M. Molecular Computation of Solutions to Combinatorial Problems [J]. Science,1994,266(11):1021-1024
[53] Lipton R J. DNA Solution of Hard Computation Problems [J]. Science,1995,268(4):542-545
[54] Ouyang Q, Kaplan P D, Liu S, et al. DNA Solution of the Maximal Clique Problem [J]. Science,1997,278(17):446-449.
[55] Liu Q, Wang L, Frutos A, et al. DNA Computing on Surfaces [J]. Nature,2000,403:175-179.
[56] Head T, Rozenberg G, Bladergroen R S, et al. Computing with DNA by Operating on Plasmids [J].Biosystems,2000,57(2):87-93.
[57] Wu H Y. An Improved Surface Based Method for DNA Computation [J]. Biosystems,2001,59(1):1-5.
[58] Gao L, Xu J. DNA Solution of Vertex Cover Problem Based on Sticker Model [J]. ChineseJournal of Electronics,2002,11(2):280-284.
[59]张连珍,刘光武,许进.基于质粒的DNA计算模型研究[J].计算机工程与应用,2004,40(4):51-52.
[60] Turku center for computer science-tues report [R], November,1998, http://www.tues.fi.[N]
[61] BusiN.,Using well-structured transition systems to decide divergenee for catalytic P systems[J],Theoretieal Computcr Seienee,2007,372(2-3):125-13
[62] Madhu M., Studies of P systems as a model of cellular computing [D], Indian Institute ofTechnology Madras, India,2003.
[63] KrishnaS.N., R.Rama, A variant of P systems with active membranes: solving NP-CompleteProblems[J], Joumal of Inform Seienee Teehnology,1999,2(4):357-367
[64] FreundR., G.P un,M.J.Perez-imenez, Tissue P systems with channel states[J], TheoretiealComputer Seienee,2005,330(l):101-116
[65] Feynman R P. Quantum Mechanical Computers [J]. Found. Phys.,1986,16(6):507-531
[66] Deutsch D, Quantum Computational Networks [A]. Proceedings of the Royal Society [C].London A,1989,425(1868):73-90
[67] A. Narayanan, M Moore. Quantum-inspired Genetic Algorithms [A]. In: Proceedings of IEEEInternational Conference on Evolutionary Computation [C]. Nagoya, Japan.1996:61~66
[68] E. Biham, O. Biham, D. Birom, et al. Grover’s quantum search algorithm for an arbitrary initialamplitude distribution [J]. Physical Review A.1999,60(4):2742~2745
[69] L.K. Grover. Fixed-point quantum search. Phys. Rev. Lett.2005,95(150501):1-4
[70] R. Eberhart and Y. Shi. Particle swarm optimization: Developments, applications and resources[A]. in Proc. IEEE Congr. Evol. Comput.[C],2001,(1):81-86
[71] Cecilia Jose M, Garcia Jose M, Nisbet Andy, et al. Enhancing data parallelism for Ant ColonyOptimization on GPUs [J]. Journal of Parallel and Distributed Computing,2013,73(1):42-51
[72] Delevacq Audrey, Delisle Pierre, Gravel Marc, et al. Parallel Ant Colony Optimization onGraphics Processing Units [J]. Journal of Parallel and Distributed Computing,2013,73(1):52-61
[73] Jose M. Cecilia,Jose M. Garcia. Parallelization Strategies for Ant Colony Optimisation on GPUs[A].2011IEEE International Parallel&Distributed Processing Symposium [C],2011
[74] M. Randall,A.Lewis. A parallel implementation of ant colony algorithm. Parallel and DistributedComputing [J],2002(62):1421-1432
[75] Hadoop,[EB/OL].[2012-08-15]. http://hadoop.apache.org/
[76] Haloop,[EB/OL].[2012-08-15]. http://code.google.com/p/haloop/
[77] Jeffrey Dean, Sanjay Ghemawat. MapReduce: simplified data processing on large clusters [J],Communications of the ACM-50th anniversary issue,2008,51(1):107-113
[78] Jin Hui, Sun XianHe, Performance comparison under failures of MPI and MapReduce: Ananalytical approach [J], Future Generation Computer Systems-the International Journal of GridComputing and Escience,2013,29(7):1808-1815
[79] T.Stutzle, H.H.Hoos. The MAX-MIN ant system: Introdcing MAX-MIN ant system [A].Proceeding International Conference on Artificial Neural Networks and Genetic Algorithms [C],1997. Springer Verlag, Wien
[80] Stützle T., H.H.Hoos.The MAX-MIN ant system and local search for the Traveling SalesmanProblem [A]. Proceedings of the IEEE International Conference on Evolutionary Computation[C],1997:309-314
[81] M. Dorigo,Di Caro G. The ant colony optimization meta-heuristic [A]. New Ideas inOptimization[C], London: McGraw-Hill,1999
[82] S.G.Lee, T.U.Jung, T. C.Chung. An effective dynamic weighted rule for ant colony systemoptimization [A]. Proceedings of the2001Congress on Evolutionary Computation [C], USA,IEEE Press,2001,2:393-397
[83] Cheng-Fa Tsai, et al. A new approach for solving large Traveling Salesman Problem usingevolution ant rules [A]. Neural Networks, IJCNN’02, Proceedings of the2002, International JointConference [C], Honolulu, HI, USA, IEEE Press,2002:154-1545
[84]张煜东,吴乐南,韦耿.基于正负反馈机制的蚁群算法用于软硬件划分[J].电子测量与仪器学报,2009,23(8):32-38
[85]夏鸿斌等.基于多蚁群的并行ACO算法[J].计算机工程,2009(11),35(22):23-25
[86] Dawson L, Stewart I, Improving Ant Colony Optimization performance on the GPU using CUDA[A].2013IEEE Congress on Evolutionary Computation [C],2013:1901-8
[87] Voelkel Gunnar, Maucher Markus, Kestler Hans A. Group-Based Ant Colony Optimization [A].GECCO'13: Proceedings of the2013Genetic and Evolutionary Computation Conference[C].2013:121-128
[88] Behalek M, Bohm S., Kromer P., et al. Parallelization of ant colony optimization algorithm usingKaira [A].201111th International Conference on Intelligent Systems Design and Applications
[C].2013:510-515
[89] Q. Lv, X. Xia, P. Qian, A parallel ACO approach based on one pheromone matrix [A], in:Proceedings of the5th International Workshop on Ant Colony Optimization and SwarmIntelligence [C], Lecture Notes in Computer Science vol.4150,2006:332–339
[90] S. Tsutsui, N. Fujimoto, Parallel ant colony optimization algorithm on a multicore processor [A],in: Proceedings of the7th International Conference on Swarm intelligence [C], Lecture Notes inComputer Science6234,2010:488–495
[91] A. Catalá, J. Jaen, J. Mocholí, Strategies for accelerating ant colony optimization algorithms ongraphical processing units [A], in: Proceedings of the IEEE Congress on EvolutionaryComputation [C], IEEE Press,2007:492–500
[92] Mocholí, J. Martínez, J. Canós, A grid ant colony algorithm for the orienteering problem [A], in:Proceedings of the IEEE Congress on Evolutionary Computation [C], IEEE Press,2005:942–949
[93] M. Pedemonte, H. Cancela, A cellular ant colony optimisation for the generalized Steinerproblem [J], International Journal of Innovative Computing and Applications,2010,2(3):188–201
[94] Mora A. M, Garcia-Sanchez P, Merelo J. J, et al. Pareto-based multi-colony multi-objective antcolony optimization algorithms: an island model proposal [J], Soft Computing,2013,17(7):1175-1207
[95] T. Stützle, Parallelization strategies for ant colony optimization [A], in: Proceedings of the5thInternational Conference on Parallel Problem Solving from Nature [C], Lecture Notes inComputer Science vol.1498,1998:722–731
[96] H. Bai, D. OuYang, X. Li, L. He, H. Yu, Max-min ant system on gpu with cuda [A], in:Proceedings of the2009Fourth International Conference on Innovative Computing, Informationand Control, IEEE Computer Society,2009:801–804
[97] S. Janson, D. Merkle, M. Middendorf, Parallel ant colony algorithms [M], in: E. Alba (Ed.),Parallel Metaheuristics, Wiley,2005:171–201(Chapter8)
[98] R. Michel, M. Middendorf, An island model based ant system with lookahead for the shortestsupersequence problem [A], in: Proceedings of the5th International Conference on ParallelProblem Solving from Nature [C], Lecture Notes in Computer Science1498,1998:692–701
[99] R. Michel, M. Middendorf, An ACO algorithm for the shortest common supersequence problem[J], in: D. Corne, M. Dorigo, F. Glover, D. Dasgupta, P. Moscato, R. Poli, K. Price (Eds.), NewIdeas in Optimization, McGraw-Hill,1999:51–62
[100] L. Chen, C. Zhang, Adaptive parallel ant colony algorithm [A], in: Proceedings of the1stInternational Conference in Advances in Natural Computation [C], Lecture Notes in ComputerScience3611,2005:1239–1249
[101] M. Randall, A. Lewis, A parallel implementation of ant colony optimization [J], Journal ofParallel and Distributed Computing,2002,62(9):1421–1432
[102] I. Iimura, K. Hamaguchi, T. Ito, S. Nakayama, A study of distributed parallel processing forqueen ant strategy in ant colony optimization [A], in: Proceedings of the6th InternationalConference on Parallel and Distributed Computing Applications and Technologies [C], IEEEComputer Society,2005:553–557
[103] Thomas Stützle, Marco Dorigo. A Short Convergence Proof for a Class of Ant ColonyOptimization Algorithms [J]. IEEE Transactions on Evolutionary Computation,2002,6(4):358–365
[104]苏兆品,蒋建国.蚁群算法的几乎处处强收敛性分析[J].电子学报,2009,37(8):1646-1650
[105]朱庆保.蚁群优化算法的收敛性分析[J].控制与决策,2006,21(7):763-770
[106]黄翰,郝志峰等.蚁群算法的收敛速度分析,计算机学报,2007,30(8):1344-1353
[107] M. Clerc and J. Kennedy. The particle swarm-explosion, stability, and convergence in amultidimensional complex space [J]. IEEE Transactions on Evolutionary Computation,2002,6(1):58–73
[108] de Campos Arion Jr, Pozo, Aurora T. R., Duarte, Elias P., Jr. Evaluation of asynchronousmulti-swarm particle optimization on several topologies [J]. Concurrency andComputation-Practice&Experience,2013,25(8):1057-1071
[109]黄芳,樊晓平,基于岛屿群体模型的并行粒子群优化算法.控制与决策[J],2006,21(2):175-179
[110] L vbjerg M,Rasmussen T K,Krink T.Hybrid Particle Swarm Optimizer with Breeding andSubpopulations [A].In:Proc. of the3rd Genetic and Evolutionary Computation Conference[C].San Francisco,USA: Morgan Kaufmann,2001:273-280
[111] J. Kennedy, Stereotyping: Improving particle swarm performance with cluster analysis [A].in Proc.2000Congr. Evolutionary Computing [C],2000:1507–1512
[112] Stefan Janson and Martin Middendorf. A hierarchical particle swarm optimizer and itsadaptive variant [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics,2005,35(6):1272-1282
[113] Ben Niu, Yunlong Zhu, Xiaoxian He et al. A multi-swarm optimizer based fuzzy modelingapproach for dynamic systems processing [J]. Neurocomputing,2007:1-13
[114] X. Li. Adaptively choosing neighborhood bests using species in a particle swarm optimizerfor multimodal function optimization [A]. in Proc.Genetic Evol. Comput. Conf.[C], Jun.2004:105-116
[115] R.Brits, A.P. Engelbrecht, F. van den Bergh. A Niching Particle Swarm Optimizer [A]. inProceedings of the4th Asia-Pacific Conference on Simulated Evolution and Learning [C],Singapore: Orchid Country Club,2002:692-696
[116] T. M. Blackwell and J. Branke, Multi-swarm optimization in dynamic environments [A].LNCS No.3005: Proceedings of Applications of Evolutionary Computing: EvoWorkshops [C],Coimbra, Portugal.2004:489-500
[117] J. J. Liang and P. N. Suganthan. Dynamic Multi-Swarm Particle Swarm Optimizer [A].IEEE International Swarm Intelligence Symposium [C],2005:124-129
[118] Chutima, P.; Kid-Arn, S. PSONK: particle swarm optimization with negative knowledge formulti-objective U-shaped assembly lines balancing with parallel workstations [J]., Journal ofAdvanced Manufacturing Systems,2013,12(1):15-41
[119] L Mussi, YSG Nashed, S Cagnoni, GPU-based asynchronous particle swarm optimization[A], GECCO '11Proceedings of the13th annual conference on Genetic and evolutionarycomputation [C],2011:1555-1562
[120] Trelea I.C., The particle swarm optimization algorithm: convergence analysis and parameterselection [J]. Information Processing Letters,31March2003, Volume85, Issue6:317-325
[121] Lucene,[EB/OL].[2013-06-18]. http://lucene.apache.org/
[122] Nutch,[EB/OL].[2013-08-15]. http://nutch.apache.org/
[123]蔡斌,陈湘萍. Hadoop技术内幕[M].机械工业出版社,2013:216-220
[124] Bu Yingyi, Bill Howe, Magdalena Balazinska, etal. HaLoop: Efficient Iterative DataProcessing on Large Clusters. In36th International Conference on Very Large Data Bases,(Singapore), September,2010:14-16
[125] Matei Zaharia, Andy Konwinski, Anthony D. Joseph et al. Improving MapReducePerformance in Heterogeneous Environments [A]. In: Proc of the8thUSENIX Conf on Operatingsystems design and implementation [C]. USA: USENIX Association Berkeley,2008:29-42
[126] Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System [A]. In:Jeanna Matthewsed. Proceedings of the nineteenth ACM symposium on Operating systemsprinciples (SOSP '03)[C]. New York: ACM Press,2003.29–43
[127] Edmund B, Nightingale E.B, Chen P.M,et al. Speculative execution in a distribute filesystem [A]. Proceedings of the twentieth ACM symposium on Operating systems principles[C],2005:191-205
[128] Ganesh Ananthanarayanan, Srikanth Kandula, Albert Greenberg, Ion Stoica, Yi Lu, BikasSaha, Edward Harris. Reining in the Outliers in Map-Reduce Clusters using Mantri [A]. In:Remzi Arpaci-Dusseau, Brad Chen, eds. Proceedings of the9th USENIX conference onOperating systems design and implementation [C]. New York: ACM Press,2010:1-16
[129] Capacity Scheduler Guide [EB/OL].http://hadoop.apache.org/docs/current/hadoop-yarn/hadoop-yarn-site/CapacityScheduler.html
[130] Fair Scheduler Guide [EB/OL].http://hadoop.apache.org/docs/current/hadoop-yarn/hadoop-yarn-site/FairScheduler.html
[131] Max-Min Fairness (Wikipedia)[EB/OL]. http://en.wikipedia.org/wiki/Max-min_fairness
[132] Matei Zaharia, Andy Konwinski, Anthony D. Joseph, Randy Katz, Ion Stoica. ImprovingMapReduce Performance in Heterogeneous Environments [A]. In: Richard Draves, Robbert vanRenesse, eds. Proceedings of the8th USENIX conference on Operating systems design andimplementation [C]. California: USENIX Association Berkeley,2008:29-42
[133] Hadoop分布式文件系统:架构和设计[EB/OL]. http://hadoop.apache.org/docs/r1.0.4/cn/hdfs_design.html
[134]董西成. Hadoop技术内幕[M].机械工业出版社,2013:162-163
[135] Tom White, Hadoop: The Definitive Guide[M], O’Reilly Media, Inc.,2009:67-68
[136] M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, I. Stoica. DelayScheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling [J].EuroSys’10,2010:265-278
[137]吴文虎,王建德,图论的算法与程序设计[M],清华大学出版社,1997:111-136
[138] Stanford Large Network Dataset Collection [EB/OL].http://snap.stanford.edu/data/index.html
[139] Jure Leskovec, Jon Kleinberg, Christos Faloutsos. Graphs over Time: Densification Laws,Shrinking Diameters and Possible Explanations [A]. In: Christopher Clifton ed. Proceedings ofthe eleventh ACM SIGKDD international conference on Knowledge discovery in data mining [C].New York: ACM Press,2005:177-187
[140] Jimmy Lin, Chris Dyer, Data-Intensive Text Processing with MapReduce [M], Morgan&Claypool Publishers,2010
[141] Chu Shu chuan, John F. Roddick, Pan Jeng Shyang. Ant colony system with communicationstrategies [J]. Information Sciences vo.167,2004:63–76
[142] TSPLIB [EB/OL].[2013-01-01]. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html
[143] J. Kennedy and R. Mendes, Population structure and particle swarm performance [J]. InProc. IEEE Congr. Evol. Comput., Honolulu, HI,2002:1671–1676