Ant Colony Optimization for Multiple Knapsack Problems with Controlled Starts

Abstract

Ant Colony Optimization is a stochastic search method that mimics the social behaviour of real ant colonies, which manage to establish the shortest routes to feeding sources and backwards. Such algorithms have been developed to reach near-optimum solutions of large-scale optimization problems, for which traditional mathematical techniques may fail. In this paper, a generalized net model of the process of ant colony optimization is constructed and on each iteration intuitionistic fuzzy estimations of the ants' start nodes are made. Several start strategies are developed and combined. This new technique is tested on Multiple Knapsack Problem, which is a real world problem. Benchmark comparisons among the strategies are presented in terms of quality of the results. Based on this comparison analysis, the performance of the algorithm is discussed along with some guidelines for determining the best strategy. The study presents ideas that should be beneficial to both practitioners and researchers involved in solving optimization problems.

Keywords

• Ant Colony Optimization
• Metaheuristics
• Discrete optimization
• Intuitionistic fuzzy estimation