The Design And Implementation Of An ACO Approach To MKP

Knapsack Problem is one of the typical NP-Hard combinatorial optimization prob-lems. MKP adds multidimensional constraints to the KP, which make us very harderto solve it, and have great applications in many domains(such as resource allocation,capital budgeting, etc). As a popular meta-heuristic, Ant Colony Optimization(ACO)has been successfully applied to many routine problems, but few discussion about theapplication of ACO for MKP.Based on analyzing the development of reseaching MKP, this paper brings up anew ACO algorithm(Core-ACO) by studying the analysis of the distance and the Corebased on e?ciency function. After researching the character of the solutions space withthe Analysis of fitness-distance, both the method for optimizing the MKP solutionsand local search method in the Core area are integrated to ACO algorithm. It solvesthe MKP by enhance the exploitation in the convergent areas so as to the ability ofalgorithm in local areas。Based on analyzing the results obtained by concerned exper-iments, we find that the Core-ACO can e?ectively reduce the search space.Whenever,it does not in?uence the quality of solutions.