Ant Colony System Algorithm with Dynamic Pheromone Updating for 0/1 Knapsack Problem

The 0/1 Knapsack (KP) is a combinatorial optimization problem that can be solved using various optimization algorithms. Ant Colony System (ACS) is one of these algorithms that is operated iteratively and converged emphatically to a matured solution. The convergence of the ACS depends mainly on the heuristic patterns that are used to update the pheromone trails throughout the optimization cycles. Although, ACS has significant advantages, it suffers from a slow convergence, as the pheromones, which are used to initiate the searching process are initialized randomly at the beginning. In this paper, a new heuristic pattern is proposed to speed up the convergence of ACS with 0/1 KP. The proposed heuristic enforces an order-critical item selection. As such, the proposed heuristic depends on considering the profit added by each item, as similar to the existing heuristics, besides the order of item selection. Accordingly, the proposed heuristic allows the items that are added at the end to get more value in order to be considered in the beginning of the next round. As such, with each cycle, the selected items are varied substantially and the pheromones are vastly updated in order to avoid long trapping with the initial values that are initialized randomly. The experiments showed that the proposed heuristic is converged more rapidly compared to the existing heuristics by reducing up to 30% of the cycles required to reach the optimal solution using difficult 0/1 KP datasets. Accordingly, the times required for convergence have been reduced significantly in the proposed work compared to the time required by the existing algorithms.