Research On Dynamic Feedback Mechanism For The Bionical Algorithms And Parallel Implementation

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.