Balancing exploration and exploitation in ACS algorithms for data clustering

• Main Authors: Jabbar, Ayad Mohammed, Sagban, Rafid, Ku-Mahamud, Ku Ruhana
• Format: Article
• Language: English
• Published: Little Lion Scientific 2019
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://repo.uum.edu.my/27861/1/JTAIT%2097%2016%204320%204333.pdf; http://repo.uum.edu.my/27861/; http://www.jatit.org/volumes/ninetyseven16.php

Ant colony optimization (ACO) is a swarm algorithm inspired by different behaviors of ants. The algorithm minimizes deterministic imperfections by assuming the clustering problem as an optimization problem. A balanced exploration and exploitation activity is necessary to produce optimal results. ACO for clustering (ACOC) is an ant colony system (ACS) algorithm inspired by the foraging behavior of ants for clustering tasks. The ACOC performs clustering based on random initial centroids, which are generated iteratively during the algorithm run. This makes the algorithm deviate from the clustering solution and performs a biased exploration. This study proposes a modified ACOC called the population ACOC (P-ACOC) to address this issue. The proposed P-ACOC allows the ants to process and update their own centroid during the algorithm run, thereby intensifying the search at the neighborhood before moving to another location.However, the algorithm quickly produces a premature convergence due to the exploitation of the same clustering results during centroid update. To resolve this issue, this study proposes a second modification by adding a restart strategy that balances between the exploration and exploitation strategy in P-ACOC.Each time the algorithm begins to converge with the same clustering solution, the restart strategy is performed to change the behavior of the algorithm from exploitation to exploration. The performance of the proposed algorithm is compared with that of several common clustering algorithms using real-world datasets. The results show that the accuracy of the proposed algorithm surpasses those of other algorithms.