Research On The Performance Analysis Of Memetic Algorithm Based On Particle Swarm Optimization And Its Application

In recent years, the canonical meta-heuristic particle swarm optimization (PSO),which based on simulating the behavior of bird flocking and swarm fishing, has beenproved to be a novel effective approach to optimizing problems for the easiness toimplement and flexibility to use. PSO is widely applied in many research fields for itssimple mathematic model, involving less parameters self-organizing and self-learningcharacters, etc. According to the studies on PSO in recent years, the theory researcheson PSO, performance improvements, novel topology structures and typicalapplications of PSO are studied respectively and discussed. However, like many searchmethods based on population iterations, PSO is very sensitive to efficient parametersetting and it has two typical problems of slow convergence and the tendency to trapinto premature as in other adaptive evolutionary algorithms, which are based on swarmintelligence searching. In addition, the mathematics theoretical analysis on PSO is notsufficient either up to present. To deal with the drawbacks, particle swarm optimizationhas undergone many changes since its introduction in1995. Researchers and expertshave derived new variant versions, developed new applications， and publishedtheoretical studies of the effects of the various parameters and aspects of the algorithm.This paper introduces the following aspects work on PSO based on the current researchsituations from the globe.(1) The merits and drawbacks of optimizing technology are presented in thispaper by comparing the traditional optimizing methods and the modern optimizingalgorithms which based on swarm intelligence. The inertia weight of the standard PSO,the accelerating coefficients, and the compression factor, etc., are analyzed anddiscussed seriously according existing theory analysis. Typical variants of PSO areintroduced and relevant analyses are quoted to prove the convergence of PSO.(2) An improved particle swarm optimization with decline disturbance index(DDPSO), which is added to the velocity updating formula, is presented in this paper.The index is added when the velocity of the particle is prone to stagnation in themiddle and later evolution periods. The modification improves the ability of particlesto explore the global and local optimization solution, and reduces the probability ofbeing trapped into the local optima. Theoretical analysis, which is based on stochasticprocesses, proves that the trajectory of particle is a Markov process and DDPSOalgorithm converges to the global optimal solution with mean square merit.Experimental simulations show that the improved algorithm can not only improve theconvergence of the algorithm significantly, but also avoid trapping into localoptimization solution.(3) Multiprocessor task scheduling problem (MSP) has aroused the interest ofresearchers from related fields in the last decades. Theoretical analysis proves thatMSP is a NP-hard problem, and there has not an algorithm to resolve the MSPeffectively within polynomial time. A novel Memetic algorithm (MA) combined particle swarm optimization and simulated annealing algorithm is presented in thispaper. We applied the MA to deal with the problem that the system assigns the tasksreasonably represented by a directed acyclic task graph to minimize the makespan andthe maximum completion time. During the processes, PSO is employed to execute theglobe optimization, and a group of particles were selected based on the strategy ofoptimal fitness value each iteration, an improved simulated annealing algorithm isadopted to improve the selected candidates at last. Typical simulations based onBenchmark functions show that the proposed method perform well on the explorationwhile balancing the system exploration and the exploitation abilities. We apply the MAto MSP problem, and experimental results show that the method achieves an efficientcompletion time.