Effect of Backtracking Strategy in Population-Based Approach: The Case of the Set-Union Knapsack Problem

In this article, we study the effect of the backtracking strategy when injected into solutions related to a population-based approach, especially when tackling the set-union knapsack problem. The designed method is based upon three features: (i) using a swarm optimization for generating a set of current particles, (ii) introducing an iterative search operator for providing a series of enhancing solutions linking some particles of the population and, (iii) injecting a path-relinking strategy for retrieving solutions with high quality along the paths linking two solutions from the unsearched space. The performance of the proposed method is evaluated on benchmark instances of the literature, where its achieved results are compared to those reached by the best methods available in the literature. Encouraging results have been obtained.