Search bias in ant colony optimization: On the role of competition-balanced systems

One of the problems encountered when applying ant colony optimization (ACO) to combinatorial optimization problems is that the search process is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Sometimes this bias is harmful and results in a decrease in algorithm performance over time, which is called second-order deception. In this work, we study the reasons for the occurrence of second-order deception. In this context, we introduce the concept of competition-balanced system (CBS), which is a property of the combination of an ACO algorithm with a problem instance. We show by means of an example that combinations of ACO algorithms with problem instances that are not CBSs may suffer from a bias that leads to second-order deception. Finally, we show that the choice of an appropriate pheromone model is crucial for the success of the ACO algorithm, and it can help avoid second-order deception.