Knapsack Problem And Algorithm Design

Knapsack problem is a typical NPC problem. The NP problem can verify a solution of the problem in polynomial time, and the NPC problem is a class of the NP problems. When it is proposed by Merkel and Hellman in1978, because of its characteristics such as simple structure and scalability strong, it caused the concern of the majority of scholars. As knapsack problem growing rapidly, a variety of optimization algorithm have been proposed and widely used, such as in the resource allocation, the investment decision, loading problem, etc. At present, the optimization algorithm research has become the subject of one of the mainstream, and already appeared a variety of stochastic optimization algorithms, such as genetic algorithm, the ant colony algorithm, particle swarm algorithm, simulated annealing algorithm, and so on. This paper for the adaptive genetic algorithm and the ant colony algorithm proposed the improved thoughts, and the improved algorithm is applied to solving knapsack problem.Firstly, this paper introduces the knapsack problem. Based on the studying and researching in the genetic algorithm and the adaptive genetic algorithm, it proposed an improved adaptive genetic algorithm (IAGA). The algorithm proposed the "gene difference proportion" that it formula into contemporary iteration time factor in crossover probability and mutation probability. Based on the concept in the process of the algorithm respectively, the greatest degree increase the diversity of population and improve the ability of search algorithm. Through to the example simulation experiments, the results show that the algorithm in search ability and the solving efficiency are greatly improved.Secondly, based on the different characteristics in the genetic algorithm and the ant colony algorithm, this paper puts forward the parallel genetic ant colony hybrid algorithm (PGACA). Using the genetic algorithm to the global optimal solution from the ant colony selecting part good individual, and the selected individuals with iteration times the number of adaptive change, the rest of the individual still adopt the ant colony algorithm is optimal. In the algorithm, using the two kinds of search to parallel optimization respectively, the system of pheromone replaced global substitution and local. For an example of simulation results show that the parallel hybrid way of this algorithm is improved optimization ability and optimal speed, and shorten the running time of the algorithm.Finally, the paper introduces the logistics distribution system, and the cargo process modeling for knapsack problem. Respectively using the improved adaptive genetic algorithm (IAGA) and the parallel genetic ant colony algorithm (PGACA) optimize the problems, and the optimization results are analyzed and compared. In order to improve the precision of the algorithm it introduces the second choice repair thought and improves the approach of the repair process strategies. Through the practical application of such a problem, that can improve the effectiveness of the restoration of the strategy.