An improved ant colony optimization with an automatic updating mechanism for constraint satisfaction problems. (February 2021)

• Record Type: Journal Article
• Authors: Guan, Boxin; Zhao, Yuhai; Li, Yuan
• Is Part Of: Expert systems with applications. Volume 164(2021)
• Publication Date: 2021-02
• Subjects: Ant colony optimization -- Automatic updating mechanism -- Constraint satisfaction problem -- Evolutionary algorithms; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.114021
• Languages: English
• ISSNs: 0957-4174

Abstract

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.