Résumé:
This research explores the integration of data mining techniques with metaheuristic algorithms to address hard combinatorial problems, with a particular focus on the Boolean Satisfiability Prob- lem (SAT). The core metaheuristic employed is Elephant Herding Optimization (EHO), a swarm- based algorithm inspired by the social behavior of elephants, known for its balance between explo- ration and exploitation.
To align EHO with the discrete nature of the SAT problem, a first adaptation phase was carried out. During this stage, stagnation emerged as a significant limitation, affecting the algorithm's ability to maintain progress toward better solutions. To mitigate this, three strategies were proposed: muta- tion, re-division, and a combination of both. These simple improvements led to a notable reduction in stagnation and significantly increased the satisfiability rate, particularly with the mutation strat- egy, which also offered the shortest execution time in most test cases.
The second phase consisted of selecting suitable data mining techniques to hybridize with EHO, aiming to further enhance performance. K-Means and DBSCAN clustering methods were chosen due to their alignment with EHO's internal mechanisms, such as clan division and worst-solution handling. K-Means was integrated by replacing random clan division with similarity-based group- ing. DBSCAN, on the other hand, was adapted both to replace the random clan division using a density-based similarity approach and, in addition, to detect and manage outliers by improving the considered worst individuals through guided reintegration. These hybridizations resulted in sub- stantial performance gains, with the DBSCAN-based approach achieving the best balance of high satisfiability and low execution time. These findings confirm that combining data-driven clustering with swarm-based metaheuristics offers a promising direction for solving complex discrete prob- lems.
Keywords: Metaheuristic,Swarm intelligence , EHO, Data Mining, Clustering, Problem Solving, SAT, Stagnation, Hybridization.
