Research Of Multi-Objective Particle Swarm Optimization Algorithm Based On Hill Climbing Strategy With Sidesteps And Its Application

There are many multi-objective optimization problems in scientific research and engineering practice with the principle of maximizing benefits while minimizing costs. Gradient-based multi-objective optimization methods often have limitations in solving problems which are discontinuous, non-differentiable and without explicit expressions. Multi-objective particle swarm optimization algorithm (MOPSO) is superior to those gradient-based methods when solving these problems since it has no requirements for problem’s continuity, and it’s simpler and converge faster comparing to other evolutionary algorithms. MOPSO is a rising swarm intelligent optimization that uses the cooperative and competitive information among particles to guide searching, and uses particles’ individual knowledge to optimize. It has gradually become a hot area of the optimization. However, the particle swarm may converge slowly in late period and even stick in local optimum since its searching procedure heavily depends on its leaders. Solving such problems will significantly help the algorithm develop in the future.In this thesis, a hill climbing strategy with sidesteps is introduced into MOPSO and a hybrid algorithm (H-MOPSO) based on this strategy is created. A further study is made to the hybrid strategy and sensitivity of relevant parameters. Also, we discuss its applications in multi-objective mixed-integer programming problems, using supplier selection and order lot sizing problems for example.The main contents and contributes of this thesis are described as follows: 1. For solving the problem of easily trapped into local optimal, the mutation operator and the inertia weight are optimized. Specifically, a non-uniform mutation strategy is introduced to help particles escape from local optimal. Meanwhile, the inertia weight is set to be linearly decreased to balance the algorithm’s ability of global search and local search. Simulation results based on test functions showed that the diversity of the solutions is improved.2. To improve the algorithm’s convergence and diversity performance, the hill climbing strategy with sidesteps is introduced, and a hybrid MOPSO based on this strategy is created. First, a hybrid model of local search and particle swarm optimization is established. According to the model, the local search algorithm based on hill climbing strategy with sidesteps is performed periodically, making particles search along descent direction or along Pareto front according their distance from the front. Furthermore, relevant parameters are analyzed based on variable control method to obtain robust values. Simulation results indicate that the proposed algorithm has favorable performance comparing to MOPSO, NSGA-Ⅱ and MOEA/D.3. For the supplier selection and order lot sizing problem, we use the proposed hybrid multi-objective particle swarm optimization algorithm based on hill climbing strategy with sidesteps, so that the given of weights can be avoided, and the number of candidate solutions can be increased. By adjusting the particle flight and increasing the equality constraint handling mechanism, the algorithm successfully solves two multi-objective mixed-integer programming problems. Finally, through the introduction of TOPSIS method, selection of the ideal solution for decision makers is achieved.