An improved ant colony optimization with an automatic updating mechanism for constraint satisfaction problems. (February 2021) - Guan, Boxin; Zhao, Yuhai; Li, Yuan
Highlights: The paper proposes an improved ant colony optimization. An automatic updating mechanism is incorporated into the proposed algorithm. The proposed algorithm can solve constraint satisfaction problems efficiently. Abstract: Constraint satisfaction problem (CSP) is defined as a set of variables whose values need to satisfies a set of constraints. Ant colony optimization (ACO) has been proved to be a promising algorithm for solving the CSP, but the solution quality and convergence speed of existing ACO-based algorithms are not satisfactory. To overcome these drawbacks, this paper proposes an improved ant colony optimization with an automatic updating mechanism (AU-ACO). The idea of the automatic updating mechanism is to optimize an assignment without giving up the excellent variable-value pairs of the assignment. Under the impact of this mechanism, AU-ACO can only optimize the non-excellent variable-value pairs of a selected assignment, which results in the algorithm having a greater chance of finding better solutions. Furthermore, by optimizing only some variable-value pairs rather than all variable-value pairs, the convergence speed of the proposed algorithm is improved. AU-ACO is compared with eight other state-of-the-art algorithms on a wide range of binary problems, and experimental results demonstrate that AU-ACO a more effective and efficient for solving the CSP.