TY - GEN
T1 - An Effective Binary Equilibrium Optimizer Based on Fitness-Distance Balance for the Minimum k-Dominating Set Problem
AU - Abed, Saad Adnan
AU - Tareq, Mustafa
AU - Mahmood, Ali A.
AU - Hassan, Farrukh
N1 - Publisher Copyright:
© 2025 IEEE.
PY - 2025
Y1 - 2025
N2 - A k-dominating set of a graph G=(V, E) is a subset D ⫅ V such that every vertex not in D is adjacent to at least k vertices in D. Finding the minimum k-DS (MKDS) is not solvable in polynomial time as it belongs to the class of NP-hard problems. Hence, we present a meta-heuristic method to find near-optimal solutions for the MKDS in a reasonable amount of time. A binary solution representation is used to solve the tackled problem; where, ones refer to the k-DS nodes and zeros are the other nodes. This paper presents a Binary Equilibrium Optimizer (BiEO) for the MKDS problem. The standard binary equilibrium optimizer tends to converge prematurely when applied to dominating set problems. To address this limitation, we propose a Fitness-Distance Balance (FDB) mechanism aimed at promoting exploration and helping the algorithm to avoid getting trapped in low-quality local optima. The proposed BiEO-FDB is evaluated on benchmark datasets. The experiments show that BiEO-FDB performs better than the original BiEO and competes favorably with other related approaches for the tested instances. Based on the evaluation, we can conclude that the proposed method provides an effective solution to the MKDS problem.
AB - A k-dominating set of a graph G=(V, E) is a subset D ⫅ V such that every vertex not in D is adjacent to at least k vertices in D. Finding the minimum k-DS (MKDS) is not solvable in polynomial time as it belongs to the class of NP-hard problems. Hence, we present a meta-heuristic method to find near-optimal solutions for the MKDS in a reasonable amount of time. A binary solution representation is used to solve the tackled problem; where, ones refer to the k-DS nodes and zeros are the other nodes. This paper presents a Binary Equilibrium Optimizer (BiEO) for the MKDS problem. The standard binary equilibrium optimizer tends to converge prematurely when applied to dominating set problems. To address this limitation, we propose a Fitness-Distance Balance (FDB) mechanism aimed at promoting exploration and helping the algorithm to avoid getting trapped in low-quality local optima. The proposed BiEO-FDB is evaluated on benchmark datasets. The experiments show that BiEO-FDB performs better than the original BiEO and competes favorably with other related approaches for the tested instances. Based on the evaluation, we can conclude that the proposed method provides an effective solution to the MKDS problem.
KW - Binary Optimization
KW - Equilibrium Optimizer
KW - Fitness-Distance Balance
KW - Minimum k-Dominating Set
UR - https://www.scopus.com/pages/publications/105031371103
U2 - 10.1109/IICAIET67254.2025.11265404
DO - 10.1109/IICAIET67254.2025.11265404
M3 - Conference contribution
AN - SCOPUS:105031371103
T3 - 7th IEEE International Conference on Artificial Intelligence in Engineering and Technology, IICAIET 2025
SP - 425
EP - 430
BT - 7th IEEE International Conference on Artificial Intelligence in Engineering and Technology, IICAIET 2025
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th IEEE International Conference on Artificial Intelligence in Engineering and Technology, IICAIET 2025
Y2 - 26 August 2025 through 28 August 2025
ER -