ACO with semi-random start applied on MKP

摘要

Ant Colony Optimization (ACO) is a stochastic search method that mimics the social behavior of real ants colonies, which manage to establish the shortest route to feeding sources and back. Such algorithms have been developed to arrive at near-optimal solutions to large-scale optimization problems, for which traditional mathematical techniques may fail. On this paper semi-random start is applied. A new kind of estimation of start nodes of the ants is made and several start strategies are prepared and combined. The idea of semi-random start is better management of the ants. This new technique is tested on Multiple Knapsack Problem (MKP). Benchmark comparison among the strategies is presented in terms of quality of the results. Based on this comparison analysis, the performance of the algorithm is discussed. The study presents ideas that should be beneficial to both practitioners and researchers involved in solving optimization problems.