A genetic algorithm for the maximum 2-packing set problem

• Autorzy: Trejo-Sánchez Joel Antonio , Fajardo-Delgado Daniel , Gutierrez-Garcia J. Octavio

Identyfikatory

DOI

10.34768/amcs-2020-0014

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

maximum 2-packing set; genetic algorithms; graph algorithms

PL

algorytm genetyczny; algorytm grafowy

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2020
• Tom: Vol. 30, no. 1
• Strony: 173--184
• Opis fizyczny: Bibliogr. 33 poz., rys., tab., wykr.

Twórcy

autor

Trejo-Sánchez Joel Antonio

• Center for Research in Mathematics, National Council of Science and Technology, Carretera Sierra Papacal, Chuburna Puerto km 5, Mérida, 97302, Mexico

autor

Fajardo-Delgado Daniel

• Department of Systems and Computation, National Technological Institute of Mexico-Ciudad Guzman, Av. Tecnológico 100, Ciudad Guzmán, Jalisco, 49000, Mexico

autor

Gutierrez-Garcia J. Octavio

• Department of Computer Science, Mexico Autonomous Institute of Technology (ITAM), Río Hondo 1, Ciudad de México, 01080, Mexico

Bibliografia

• [1] Adacher, L. and Gemma, A. (2017). A robust algorithm to solve the signal setting problem considering different traffic assignment approaches, International Journal of Applied Mathematics and Computer Science 27(4): 815–826, DOI: 10.1515/amcs-2017-0057.
• [2] Adamic, L.A. and Huberman, B.A. (2000). Power-law distribution of the world wide web, Science 287(5461): 2115–2115.
• [3] Agrawal, A., Klein, P. and Ravi, R. (1995). When trees collide: An approximation algorithm for the generalized Steiner problem on networks, SIAM Journal on Computing 24(3): 440–456.
• [4] Alon, U. (2007). An Introduction to Systems Biology: Design Principles of Biological Circuits, Chapman & Hall/CRC, Boca Raton, FL.
• [5] Amaral, L.A.N., Scala, A., Barthélémy, M. and Stanley, H.E. (2000). Classes of small-world networks, Proceedings of the National Academy of Sciences 97(21): 11149–11152.
• [6] Andrade, D.V., Resende, M.G. and Werneck, R.F. (2012). Fast local search for the maximum independent set problem, Journal of Heuristics 18(4): 525–547.
• [7] Back, T. and Khuri, S. (1994). An evolutionary heuristic for the maximum independent set problem, IEEE World Congress on Computational Intelligence, Orlando, FL, USA, pp. 531–535.
• [8] Baran, M. (2018). Closest paths in graph drawings under an elastic metric, International Journal of Applied Mathematics and Computer Science 28(2): 387–397, DOI: 10.2478/amcs-2018-0029.
• [9] Eiben, A.E. and Smith, J.E. (2015). Introduction to Evolutionary Computing, Natural Computing Series, 2nd Edn, Springer-Verlag, Berlin/Heidelberg.
• [10] Feitelson, D.G. (1996). Packing schemes for gang scheduling, in D. G. Feitelson and L. Rudolph (Eds), Workshop on Job Scheduling Strategies for Parallel Processing, Springer, Berlin/Heidelberg, pp. 89–110.
• [11] Flores-Lamas, A., Fernández-Zepeda, J.A. and Trejo-Sánchez, J.A. (2018). Algorithm to find a maximum 2-packing set in a cactus, Theoretical Computer Science 725: 31–51.
• [12] Fortin, F.-A., De Rainville, F.-M., Gardner, M.-A., Parizeau, M. and Gagné, C. (2012). DEAP: Evolutionary algorithms made easy, Journal of Machine Learning Research 13(7): 2171–2175.
• [13] Gairing, M., Geist, R.M., Hedetniemi, S.T. and Kristiansen, P. (2004a). A self-stabilizing algorithm for maximal 2-packing, Nordic Journal of Computing 11(1): 1–11.
• [14] Gairing, M., Goddard, W., Hedetniemi, S.T., Kristiansen, P. and McRae, A.A. (2004b). Distance-two information in self-stabilizing algorithms, Parallel Processing Letters 14(03n04): 387–398.
• [15] Garey, M.R. and Johnson, D.S. (2002). Computers and Intractability, Vol. 29, WH Freeman New York, NY.
• [16] Gregor, D. and Lumsdaine, A. (2005). The parallel BGL: A generic library for distributed graph computations, Parallel Object-Oriented Scientific Computing (POOSC), Glasgow, UK, pp. 1–18.
• [17] Hale, W.K. (1980). Frequency assignment: Theory and applications, Proceedings of the IEEE 68(12): 1497–1514.
• [18] Hochbaum, D.S. and Shmoys, D.B. (1985). A best possible heuristic for the k-center problem, Mathematics of Operations Research 10(2): 180–184.
• [19] Holland, J.H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor, MI.
• [20] Karp, R.M. (1972). Reducibility among combinatorial problems, in R.E. Miller et al. (Eds), Complexity of Computer Computations, Springer, Boston, MA, pp. 85–103.
• [21] Knudsen, M. and Wiuf, C. (2008). A Markov chain approach to randomly grown graphs, Journal of Applied Mathematics 2008: 1–14.
• [22] Lamm, S., Sanders, P., Schulz, C., Strash, D. and Werneck, R.F. (2017). Finding near-optimal independent sets at scale, Journal of Heuristics 23(4): 207–229.
• [23] Manne, F. and Mjelde, M. (2006). A memory efficient self-stabilizing algorithm for maximal k-packing, in A.K. Datta and M. Gradinariu (Eds), Symposium on Self-Stabilizing Systems, Springer, Berlin/Heidelberg, pp. 428–439.
• [24] Mjelde, M. (2004). k-Packing and k-Domination on Tree Graphs, Master’s thesis, University of Bergen, Bergen.
• [25] Newman, M.E.J. (2002). Handbook of Graphs and Networks, Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim, DOI: 10.1002/3527602755.
• [26] Nogueira, B., Pinheiro, R.G. and Subramanian, A. (2018). A hybrid iterated local search heuristic for the maximum weight independent set problem, Optimization Letters 12(3): 567–583.
• [27] Shi, Z. (2012). A self-stabilizing algorithm to maximal 2-packing with improved complexity, Information Processing Letters 112(13): 525–531.
• [28] Soto, J.G., Leanos, J., Ríos-Castro, L. and Rivera, L. (2018). The packing number of the double vertex graph of the path graph, Discrete Applied Mathematics 247: 327–340.
• [29] Trejo-Sánchez, J. A., Vela-Navarro, A., Flores-Lamas, A., López-Martínez, J.L., Bermejo-Sabbagh, C., Cuevas-Cuevas, N.L. and Toral-Cruz, H. (2018). Fast random cactus graph generation, in M. Torres et al. (Eds), International Conference on Supercomputing in Mexico, Springer, Cham, pp. 129–136.
• [30] Trejo-Sánchez, J.A. and Fernández-Zepeda, J.A. (2012). A self-stabilizing algorithm for the maximal 2-packing in a cactus graph, 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), Shanghai, China, pp. 863–871.
• [31] Trejo-Sánchez, J.A. and Fernández-Zepeda, J.A. (2014). Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs, Journal of Parallel and Distributed Computing 74(3): 2193–2202.
• [32] Trejo-Sánchez, J.A., Fernández-Zepeda, J.A. and Ramírez-Pacheco, J.C. (2017). A self-stabilizing algorithm for a maximal 2-packing in a cactus graph under any scheduler, International Journal of Foundations of Computer Science 28(08): 1021–1045.
• [33] Turau, V. (2012). Efficient transformation of distance-2 self-stabilizing algorithms, Journal of Parallel and Distributed Computing 72(4): 603–612.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).