IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i7p1155-d384597.html
   My bibliography  Save this article

Improved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set

Author

Listed:
  • Yupeng Zhou

    (Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
    School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

  • Jinshu Li

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

  • Yang Liu

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

  • Shuai Lv

    (Urban Construction Archives, Changchun 130000, China)

  • Yong Lai

    (Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
    College of Computer Science and Technology, Jilin University, Changchun 130012, China)

  • Jianan Wang

    (Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
    School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

Abstract

The minimum weight vertex independent dominating set (MWVIDS) problem is an important version of the minimum independent dominating set. The MWVIDS problem has a number of applications in many fields. However, the MWVIDS problem is known to be NP-hard and thus computationally challenging. In this work, we present the improved memetic algorithm called MSSAS for solving the MWVIDS problem. The proposed MSSAS algorithm combines probability-based dynamic optimization (PDO) (to generate good and diverse offspring solutions by assembling elements of existing good solutions) as well as a local search phase named C_LS (to seek high-quality local optima by combining the idea of constrained-based two-level configuration checking strategy and tabu mechanism). The extensive results on popular DIMACS and BHOLIB benchmarks demonstrate that MSSAS competes favorably with the state-of-the-art algorithms. In addition, we analyze the benefits of the newly raised components including two above proposed ideas with our memetic framework. It is worth mentioning that the combination of both components has excellent effects for the MWVIDS problem.

Suggested Citation

  • Yupeng Zhou & Jinshu Li & Yang Liu & Shuai Lv & Yong Lai & Jianan Wang, 2020. "Improved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set," Mathematics, MDPI, vol. 8(7), pages 1-17, July.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:7:p:1155-:d:384597
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/7/1155/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/7/1155/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Lü, Zhipeng & Hao, Jin-Kao, 2010. "A memetic algorithm for graph coloring," European Journal of Operational Research, Elsevier, vol. 203(1), pages 241-250, May.
    2. Dulebenets, Maxim A., 2019. "A Delayed Start Parallel Evolutionary Algorithm for just-in-time truck scheduling at a cross-docking facility," International Journal of Production Economics, Elsevier, vol. 212(C), pages 236-258.
    3. Basheer M. Khumawala, 1972. "An Efficient Branch and Bound Algorithm for the Warehouse Location Problem," Management Science, INFORMS, vol. 18(12), pages 718-731, August.
    4. Mauricio G.C. Resende & Celso C. Ribeiro, 2010. "Greedy Randomized Adaptive Search Procedures: Advances, Hybridizations, and Applications," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 283-319, Springer.
    5. Miguel Terra-Neves & Inês Lynce & Vasco Manquinho, 2019. "Virtual machine consolidation using constraint-based multi-objective optimization," Journal of Heuristics, Springer, vol. 25(3), pages 339-375, June.
    6. Pinacho Davidson, Pedro & Blum, Christian & Lozano, Jose A., 2018. "The weighted independent domination problem: Integer linear programming models and metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 265(3), pages 860-871.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Alejandro Lara-Caballero & Diego González-Moreno, 2023. "A Population-Based Local Search Algorithm for the Identifying Code Problem," Mathematics, MDPI, vol. 11(20), pages 1-17, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bo Peng & Yuan Zhang & Yuvraj Gajpal & Xiding Chen, 2019. "A Memetic Algorithm for the Green Vehicle Routing Problem," Sustainability, MDPI, vol. 11(21), pages 1-20, October.
    2. Musmanno, Leonardo M. & Ribeiro, Celso C., 2016. "Heuristics for the generalized median graph problem," European Journal of Operational Research, Elsevier, vol. 254(2), pages 371-384.
    3. Mohammad Amin Amani & Mohammad Mahdi Nasiri, 2023. "A novel cross docking system for distributing the perishable products considering preemption: a machine learning approach," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-32, July.
    4. García Cáceres, Rafael Guillermo & Aráoz Durand, Julián Arturo & Gómez, Fernando Palacios, 2009. "Integral analysis method - IAM," European Journal of Operational Research, Elsevier, vol. 192(3), pages 891-903, February.
    5. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    6. Mazzola, Joseph B. & Neebe, Alan W., 1999. "Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type," European Journal of Operational Research, Elsevier, vol. 115(2), pages 285-299, June.
    7. Melachrinoudis, Emanuel & Min, Hokey, 2000. "The dynamic relocation and phase-out of a hybrid, two-echelon plant/warehousing facility: A multiple objective approach," European Journal of Operational Research, Elsevier, vol. 123(1), pages 1-15, May.
    8. Bingtao Quan & Sujian Li & Kuo-Jui Wu, 2022. "Optimizing the Vehicle Scheduling Problem for Just-in-Time Delivery Considering Carbon Emissions and Atmospheric Particulate Matter," Sustainability, MDPI, vol. 14(10), pages 1-19, May.
    9. Potoczki, Tobias & Holzapfel, Andreas & Kuhn, Heinrich & Sternbeck, Michael, 2024. "Integrated cross-dock location and supply mode planning in retail networks," International Journal of Production Economics, Elsevier, vol. 276(C).
    10. Li‐Lian Gao & E. Powell Robinson, 1992. "A dual‐based optimization procedure for the two‐echelon uncapacitated facility location problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 191-212, March.
    11. P Hansen & J-F Thisse, 1977. "Multiplant Location for Profit Maximisation," Environment and Planning A, , vol. 9(1), pages 63-73, January.
    12. Angel Juan & Javier Faulin & Albert Ferrer & Helena Lourenço & Barry Barrios, 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 109-132, April.
    13. Canel, Cem & Khumawala, Basheer M. & Law, Japhet S., 1996. "An efficient heuristic procedure for the single-item, discrete lot sizing problem," International Journal of Production Economics, Elsevier, vol. 43(2-3), pages 139-148, June.
    14. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Hubert Ruta & Tomasz Krakowski & Paweł Lonkwic, 2022. "Optimisation of the Magnetic Circuit of a Measuring Head for Diagnostics of Steel-Polyurethane Load-Carrying Belts Using Numerical Methods," Sustainability, MDPI, vol. 14(5), pages 1-19, February.
    16. Victor Reyes & Ignacio Araya, 2021. "A GRASP-based scheme for the set covering problem," Operational Research, Springer, vol. 21(4), pages 2391-2408, December.
    17. Min, Hokey & Melachrinoudis, Emanuel, 1999. "The relocation of a hybrid manufacturing/distribution facility from supply chain perspectives: a case study," Omega, Elsevier, vol. 27(1), pages 75-85, February.
    18. Byungjun Ju & Minsu Kim & Ilkyeong Moon, 2021. "Vehicle Routing Problem Considering Reconnaissance and Transportation," Sustainability, MDPI, vol. 13(6), pages 1-19, March.
    19. Cheng-Long Wei & Gai-Ge Wang, 2020. "Hybrid Annealing Krill Herd and Quantum-Behaved Particle Swarm Optimization," Mathematics, MDPI, vol. 8(9), pages 1-23, August.
    20. Lo, Shirleen Lee Yuen & How, Bing Shen & Leong, Wei Dong & Teng, Sin Yong & Rhamdhani, Muhammad Akbar & Sunarso, Jaka, 2021. "Techno-economic analysis for biomass supply chain: A state-of-the-art review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 135(C).

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:8:y:2020:i:7:p:1155-:d:384597. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.