Improving Biased Random Key Genetic Algorithm with Variable Neighborhood Search for the Weighted Total Domination Problem

Alejandra Casado, Jesús Sánchez-Oro, Anna Martínez-Gavara, Abraham Duarte

enero, 2024

Resumen

The Weighted Total Domination Problem (WTDP) belongs to the family of dominating set problems. Given a weighted graph, the WTDP consists in selecting a total domination set D such that the sum of vertices and edges weights of the subgraph induced by D plus, for each vertex not in D, the minimum weight of its edge to a vertex in D is minimized. A total domination set D is a subset of vertices such that every vertex, is at least adjacent to one vertex in D. This problem arises in many real-life applications closely related to covering and independent set problems, however it remains computationally challenging due to its NP-hardness. This work presents a Variable Neighborhood Search procedure to tackle the WTDP. In addition, we develop a Biased Greedy Randomized Adaptive Search Procedure that keeps adding elements once a feasible solution is found in order to produce high-quality initial solutions. We perform extensive numerical analysis to look into the influence of the algorithmic components and to disclose the contribution of the elements and strategies of our method. Finally, the empirical analysis shows that our proposal outperforms the state-of-art results, supported by an statistical analysis.

Tipo

Artículo de conferencia

Publicación

Lecture Notes in Computer Science