Analysis And Application Of Particle Swarm Optimization

Particle swarm optimization (PSO) is an optimization algorithm based on swarm intelligence developed by Kennedy and Eberhart in 1995. Similar to genetic algorithm, it is based on swarm iteration and consists of a group of particles cooperate to searching in the problem space. However it is unlike genetic algorithm in that there is no crossover and mutation operation. The inner cooperation is more emphasized, rather than the"survival of the fittest"theory of Darwin. Particle swarm optimization algorithm has become a new research hot point in computation intelligence area for the rapid convergence and simple to implementation, while the theory research is still in initial step stage. This thesis has made a deep theory analysis for particle swarm optimization, proposed several improved algorithms and applied it into engineering practice. Several points are included in this paper as follows:The thinking origin of PSO is reviewed thoroughly. Firstly the research background and thinking origin is introduced simply, followed along with the discussion about the development and mainly research direction of swarm intelligence theory. The comparison between PSO and EC is detailedly analyzed too.A deep mathematical analysis is made for PSO respectively from macroscopic and microscopic views. Firstly from macroscopic view, a strict mathematical description is given for the basic conception of PSO algorithm, with the definition of many notions, such as particle state, particle swarm state, particle swarm state equivalence class and so on. The particle swarm state transition equation has proved to be a Markov chain process, based on which, the Markov chain model of PSO is established. In the meantime, an elementary convergence analysis of PSO has finished, which testifies that PSO algorithm has no ability to guarantee the convergence. From microscopic view, difference equation and Z transform are adopted to analyze the velocity change process and position change process of single particle. Assuming that pBest and gBest have no change and ignoring random quantities, we can obtain the conditional expression about the convergence of single particle's trajectory. A further discussion about the influence pBest,gBest and random quantity put on particle trajectory has been given, as well as the relationship between single particle's trajectory and algorithm convergence. Theoretical formula and condition adjusting the parameter of PSO in engineering practice have also been offered.According to the theoretical analysis and research result of PSO, two improved PSO with mutation operator (MuPSO1 and MuPSO2) and a new improved PSO based on social information (C-Pg PSO) have been proposed in this paper. MuPSO1 and MuPSO2 judge whether the algorithm is stagnant by some attributes in particle swarm iteration, and if stagnant, then add some proper mutation operators to increase the variety of particle to enhance the convergence. The thinking of C-Pg PSO algorithm comes from social observation. It's not easy to be trapped into local optimum, for particle swarm follows gBest to change at all times, by adding some other influence. A serial of test functions are tested on some massive computing to appraise the performance of all improved algorithms. First of all, an analysis testing about the sensitivity of parameters is made for all improved algorithms. Then a comparison analysis testing about the calculated performance is given too. At last, combined with theory and the test result above, a further discussion and analysis is provided for the calculated performance and use value of improved algorithms. The performance of MuPSO1 algorithm has been illustrated further by the rotating plane layout optimization instance.The application of PSO algorithm to combination optimization problem is developed, as the investigated subject is the typical combination problem: vehicle routing problem with time window. According to the features of vehicle routing problem, a proper particle expression is put forward, including most of constraint conditions, which leads to the result that the number of non-feasible solutions is reduced sharply, and the feasibility calculation on the non-feasible solution is simplified too. Moreover, the rationality and validity of the expression have been testified by several experiments. Some issues we must take into consideration when applying PSO to the combination optimization problem and remarkable processing methods are mentioned in addition.A multi-objective optimization algorithm has been proposed while the idea of particle swarm is introduced into multi-objective optimization. Take previously nondominiated vectors found by the algorithm as the elitism set. Randomly select particles from the elitism set as gBest in iteration, which are followed by the particle swarm to search Pareto nondominiated set. The niche technique is used to screen out the particles in the elitism set to maintain the uniformity of nondominiated set. At the same time, boundary mutation and portion mutation strategies are adopted to increase the diversity of nondominiated set. Experiments proof that this method is a quick and effective multi-objective optimization method.In the end, a discussion and analysis of promising research way based on this paper is presented, including the extension and definition of swarm intelligence, convergence analysis of PSO algorithm, mathematical techniques of PSO algorithm analysis and application of PSO algorithm for combination optimization problem etc.