A Genetic Algorithm for the Maximum 2–Packing Set Problem

International Journal of Applied Mathematics and Computer Science

Trejo-Sánchez Joel Antonio¹  Gutierrez-Garcia J. Octavio²  Fajardo-Delgado Daniel³ 

[1] Center for Research in Mathematics, National Council of Science and Technology, Carretera Sierra Papacal, Chuburna Puerto km 5, Mérida, 97302, Mexico;Department of Computer Science, Mexico Autonomous Institute of Technology (ITAM), Río Hondo 1, Ciudad de México, 01080, Mexico;Department of Systems and Computation, National Technological Institute of Mexico—Ciudad Guzman, Av. Tecnológico 100, Ciudad Guzmán, Jalisco, 49000, Mexico;

关键词: maximum 2-packing set;    genetic algorithms;    graph algorithms;   

DOI  :  10.34768/amcs-2020-0014

来源: DOAJ

【 摘 要 】

Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in S is at least 3 and S has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.

【 授权许可】

Unknown