Research On Multi-objective Knapsack Problem Based On Artificial Fish Swarm Algorithm

Multi-objective optimization problem and knapsack problem have been a difficult and hot issues in the field of science and engineering research. Compared with the single objective knapsack problems, multi-objective knapsack problem generally include two or more optimization objectives, so the problem will be more complicated.Classical optimization algorithm such as dynamic programming is difficult to use feasible computational cost and time search with high quality solutions, so we need to study a more efficient algorithm structure to quickly find the Pareto optimal solution.This paper sums up the common methods of two swarm intelligence algorithms for solving multi-objective knapsack problem:Genetic algorithm and particle swarm optimization. Genetic algorithm calculation is simple, easy to achieve programming, but it is prone to premature phenomena and near optimal solutions in the vicinity of the optimal solution; Particle swarm algorithm is fast running, but it is of low accuracy. This paper introduces artificial fish swarm algorithm in detail, generalizes several commonly used distance and artificial fish swarm algorithm commonly used coding method, and focuses on artificial fish swarm algorithm for solving multi-objective knapsack problem. At last, according to the code for artificial fish,artificial fish moving strategy, we design an improved artificial fish swarm algorithm based on global artificial fish swarm algorithm.To solve the multi-objective knapsack problem, artificial fish swarm algorithm has a blind search, high complexity, low accuracy and slow convergence rate. Knapsack problem generally uses binary coding to solve the problem, but the use of binary encoding is required for frequent encoding and decoding will greatly increase the amount of computation algorithm. In the artificial fish swarm algorithm, the actual use of distance between the two fishes is the Euclidean distance with blindness and randomness. In view of these problems, the main work of this paper is to propose an improved artificial fish swarm algorithm.In the design of improved artificial fish swarm algorithm, firstly, it defines a real number coding and designs a real number code for the position of the artificial fish based on the mathematical model of multi-objective knapsack problem in this paper; in order to reduce complexity of the search algorithm,then we modify the artificial fish’s mobile strategy, remove the Euclidean distance, add a dependent iterations of the adaptive factor and reduce probability of artificial fish blind search on the basis of global artificial fish swarm algorithm; at last, on the basis of the characteristics of multi-objective optimization problem and the discrete of knapsack problem, we use the search to all non dominated solutions to the distance from the origin of arithmetic mean value to evaluate the algorithm accuracy and the distance arithmetic average value of the trend to evaluate the algorithm received convergence.The improved artificial fish swarm algorithm is analyzed in this paper. The results show that the improved algorithm significantly improves the convergence speed and precision of the algorithm in solving multi-objective knapsack problem. At the same time, compared with the classical swarm intelligence optimization algorithm surch as genetic algorithm and particle swarm optimization algorithm, the improved algorithm has obvious advantages in solving the quality, quantity and distribution of high quality solutions. The improved algorithm is more prominent with the increase of the scale of the multi-objective knapsack problem.