Research On Multi-constraint Combinatorial Optimization Problem Based On Muliti-objective Particle Swarm Optimization Algorithm

The combinatorial optimization problem has an important application in the fields of transportation and financial investment.The solution method to these problems has always been the focus of people's research.The combinatorial optimization problems in practical engineering applications often have multiple constraints and in many cases the problem scale is large.Due to the need to traverse the entire solution space,traditional optimization algorithms cannot solve these problems in the polynomial time.Meta-heuristic algorithm combines random search algorithm with local search algorithm,and searches from multiple locations in the target space at the same time,with the goal of obtaining better solutions as far as possible,which is considered to be more suitable for solving combinatorial optimization problems with multiple constraints.Common meta-heuristic algorithms include genetic algorithm,particle swarm optimization,ant colony optimization,etc.Among them,particle swarm optimization algorithm makes the whole population gradually approach to the optimal solution of the problem and finally converges through the mutual cooperation among individuals in the population.In the process of solving multi-constraint combinatorial optimization problem,how to properly deal with constraints is also a problem that needs our attention.Based on the analysis of the advantages and disadvantages of the existing constraint processing methods,this paper adopt to transform the multi-constraint optimization problem into a multi-objective optimization problem with more than three objectives by using the constrain-to-target method,and combined with the particle swarm optimization algorithm to solve the problem.In order to search for the optimal solution with higher quality,an improved many-objective particle swarm optimization algorithm(IMaOPSO)was proposed in this paper.The external archive are maintained by the degree of constraint violation,and the global optimization of the population was found by taking the crowding degree and the distance between individuals and the ideal point in the population as two indexes.In addition,in view of the target space of the constraint combinatorial optimization problem is complex and large scale.On the basis of IMaOPSO algorithm,a many-obj ective particle swarm optimization algorithm based on multi-population co-evolution is proposed.Multiple populations are used to search different regions respectively.In addition,the algorithm's speed updating mechanism is improved and a replacement operator is designed to improve the convergence of the algorithm.Finally,the effectiveness of the proposed algorithm is verified by the multiple knapsack problem with different scales.