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

Abstract

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.

Alejandra Casado

Artificial Intelligence Phd Student

My research interests include metaheuristics and combinatorial optimization.

Jesús Sánchez-Oro

Associate Professor

Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.

Abraham Duarte

Full Professor

Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.