Research On Multi-dimensional Knapsack Problem Based On Memetic Algorithm

Multidimensional knapsack problem(MKP)is a well-known integer programming problem and has many important practical application backgrounds,such as cargo loading,material cutting,resource allocation,and investment decision-making.This paper studies various precise algorithms and heuristic algorithms for solving multidimensional knapsack problems.The characteristics and key points of the Memetic algorithm and the multidimensional knapsack problem are deeply studied and analyzed.The G-Memetic algorithm and the GAC-Memetic algorithm are designed.The G-Memetic algorithm uses an improved genetic algorithm as a global search module and a simulated annealing algorithm for local search.In the global search module,an adaptive mode-oriented operation is first introduced to keep the best individual individuals in each generation of populations to form a pattern,which provides a reliable search direction for the global search of the G-Memetic algorithm and enhances search performance;The perturbation crossover operation and the dual selection mutation operator are used to screen individuals with little gain,enhance the diversity of the population,and accelerate the convergence speed.Finally,the maximizing repair strategy is improved to overcome the defects of poor resource utilization.The local optimization module uses the simulated annealing algorithm as the Memetic factor and accepts poor solutions according to the Metropolis criterion,thus effectively avoiding the G-Memetic algorithm from falling into a local optimum.The experimental simulation and algorithm comparison verify the superiority and effectiveness of the algorithm.By analyzing the advantages and disadvantages of genetic algorithms and ant colony algorithms for solving multidimensional knapsack problems in evolutionary algorithms,GAC-Memetic is designed based on the evolutionary module strategy in G-Memetic algorithm.The algorithm,at the same time,introduced chaos optimization and taboo mutation as its local optimization module.In the process of evolution,ant colony optimization is introduced into the roulette wheel selection probability criterion to reduce the complexity of the algorithm;then the pheromone update rules are designed to quickly reflect the heuristic information and guide the evolution direction of the next population.In the local optimization module,chaos optimization is introduced to increase the possibility of individuals searching for new solutions;using the contempt criteria in the tabu list to mutate good individuals,avoid falling into a local minimum while reducing the TS to the initial solution and the neighborhood Structural dependence.Through the simulation of test cases,GAC-Memetic algorithm is used to solve the multidimensional knapsack problem.The performance,accuracy and convergence of GAC-Memetic algorithm have been greatly improved.Finally,this paper analyzes the performance of G-Memetic algorithm and GAC-Memetic algorithm by testing a large number of examples.The comparison test results show that G-Memetic algorithm is less affected by the dimensions of the problem,is affected by the number of items to be selected,and has higher solution efficiency and convergence performance in low dimensions.However,the G-Memetic optimization ability is relatively poor when solving a large number of items to be selected,while the GAC-Memetic has a higher number of iterations but a higher accuracy.