A multi-objective particle swarm optimization for multiple knapsack problem with strong constraints

摘要

Aiming at the characteristics of strong constraints of multiple knapsack problem (MKP), a method based on multi-objective particle swarm optimization is proposed in this paper. We take constraint violation as an optimal objective to avoid the troublesome of dealing with unfeasible solutions unsatisfied constraints. For updating effectively the external archive, the degree of constraint violation and the crowding degree of non-dominated particle in Pareto front are taken as two criteria. To decrease the probability of algorithm converging to a pseudo Pareto front, a mutation operator is designed. The experimental results of solving a number of MKP instances demonstrate that the proposed algorithm performs better to the MKP instances with strong constraints.