Chinese Journal of Computers   Full Text
Title	An Improved Ant Algorithm for Multidimensional Knapsack Problem
Authors	YU Xue-Cai ZHANG Tian-Wen
Address	(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
Year	2008
Issue	No.5(810—819)
Abstract &   Background	Abstract Ant Colony Optimization (ACO) is a metaheuristic. And it has been applied to many hard discrete optimization problems. Recently, some researchers have proposed several different ACO algorithms to solve the multidimensional knapsack problem (MKP), which is an NP-hard combinatorial optimization problem. Although these algorithms could obtain good solutions of MKP, they consume too more CPU time. For the sake of decreasing the time complexity of the existing ACO algorithms, a new improved ACO algorithm is proposed for MKP in this paper. First, a pheromone representation, which was defined by Blum C. in his paper "the hyper-cube framework for ant colony optimization" as an example, models binary decision variables assigned to all items and their values. Based on this pheromone model, a new rule choosing the objective item is defined. In this way, the time complexity of the proposed ACO algorithm can be decreased. However, incorporating the heuristic information into the solution construction of the artificial ants is difficult. A new heuristic information of MKP based on some order of all items is described. Experimental results show that in the case of the same computing task, the new one uses less CPU time and obtains better solutions compared with other ACO algorithms whether the serial or parallel implementation. Also, the new algorithm has obtained two new solutions of test 5.250-22. Keywords ant colony optimization; pheromone model; heuristic information; combinatorial optimization; multidimensional knapsack problem Background There still exists many other complex calculations which computers can not solve in reasonable CPU time limits. Examples are large-scale instances of the travel salesman problem, the multidimensional knapsack problem, the job shop problem, and so on. Thus various heuristic and metaheuristic approaches have been suggested for solving discrete optimization problems. In general, metaheuristic performs over heuristic. Ant colony optimization is a metaheuristic. The authors mainly bend themselves to theoretical foundation and application of ant colony optimization. The results will aid to deepen understanding of ant colony optimization algorithm, to improve the performance of ant colony optimization and to extend the area of applying ant colony optimization approach. Ant colony optimization has been extensively applied to many combinatorial optimization problems. Many experimental results show that ant colony optimization is powerful. However, all ant colony optimization algorithms for solving the multidimensional knapsack problem perform not very good. This work designed a new rule selecting a knapsack item and defined a new heuristic information which can be easily incorporated into the new solution constructing rule. The new ant colony optimization algorithm provided in this paper greatly enhances the capability of ant colony optimization solving the multidimensional knapsack problem. The approach described in this paper can aid to develop ant colony optimization algorithms for other subset problems such as the cardinality tree problem and the multi-demand multidimensional knapsack problem.