| Multi-dimensional 0-1 knapsack problem often appears in decision making and programming, resource distribution, loading, and so on. Multi-dimensional 0-1 knapsack problem is also one of a class'of typical NPC problem. It has important meanings in practice and in theory to study it. For solving this problem, many algorithms have been proposed by scholars.This paper extends the ant colony algorithm which is used for solving 0-1 knapsack problem in reference [24], and gives the mathematical model, algorithm description and program flow diagram for the ant colony algorithm which is use for solving multi-dimensional 0-1 knapsack problem. On the basis of this job, the paper also makes the simulation experiment of the pheromone, the ant route and the best route. The simulation results show that the algorithm is more efficient, but it costs long search time and gets into the local result easily.To solve this problem, the paper presents a new ant colony algorithm based on exchange strategy. Enlightenment from the ant colony algorithm with 2-opt or 3-opt local optimization for solving traveling salesman problems, the algorithm based on exchange strategy has the faster convergence rate and gets the better quality solution.For using the exchange strategy, the paper compares the difference between the Traveling Salesman Problem and the knapsack problem, and presents the 2-opt or 3-opt local algorithm for the knapsack problem. This local algorithm is introduced into the ant colony algorithm. The ant colony algorithm based on exchange strategy has shorter search time and is rather efficient for improving the convergence of the local result.Finally, by comparing other intelligence algorithms with the search era, the result quality and the search time, the experiments demonstrate that the algorithm proposed in the paper not only has the better result but also has the shorter runtime. So our algorithm is rather efficient for solving multi-dimensional 0-1 knapsack problem. |
PDF Full Text Request