An Improved Algorithm For Multidimensional Backpack Problem

Multidimensional knapsack problem (MKP) is one kind of knapsack problem which is the most widely used in life and the famous integer programming problem. Since the first MKP was designed by Lorie and Savage, the researchers have explored it constantly. Through the efforts for half a century, MKP has a wide range of applications in operational research, economics, informatics, aviation technology and other fields.The paper presents an improved genetic algorithm based on schema disturbance (SIGA). At the first time, the method replaces the schema of initial population to generate and keep excellent genes. Then introduce a disturbance factor to optimize the crossover operation and schema genetic differences proportion to improve the searching ability, to mostly increase the diversity of the population and avoid the method falling into local optimal. Finally use the weighted average calculation of greedy operator to evaluate the fitness value for reaching correction and restoration to maximum utilization. The simulation results show that the method can quickly search for the optimal solution and quickly converge to the value. Meanwhile, the search performance is stronger than general genetic algorithm, so the precision is higher and more stable.On the basis of the analysis of chaos theory and ant colony algorithm, the paper introduces a method which combined with the chaos search and adaptive ant colony algorithm (CAACA) to solve the MKP. It uses the chaos factor to influence the update of pheromone which ensures the speed of the search at the beginning and expands the search scope in the late. Redesign selection probability and select the ant path based on the roulette thought for the sum of the probabilities as u, increased the search of randomness. To a large extent, that is to avoid algorithm into local optimum coupled with the dynamic adjustment of heuristic factor and exchange strategy of taboo table. A lot of comparative results of solution performance and astringency show that the CAACA not only get high precision solution, but also effectively improve the problem of premature convergence of the ant colony algorithm, as well as the search performance.Finally, the paper make a comparison between SIGA and CAACA two kinds of algorithm performance, and the container loading problem is modeled as a multi-dimensional knapsack problem solving. The results show that, for small scale problems, SIGA is better than CAACA in efficiency, speed of convergence in solving; in solving large-scale problems, CAACA is better than SIGA in solving the performance, precision of solution.