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. Coelho, V.N. & Grasas, A. & Ramalhinho, H. & Coelho, I.M. & Souza, M.J.F. & Cruz, R.C., 2016. "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, Elsevier, vol. 250(2), pages 367-376.
    5. 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.
    6. Bulhões, Teobaldo & Subramanian, Anand & Erdoğan, Güneş & Laporte, Gilbert, 2018. "The static bike relocation problem with multiple vehicles and visits," European Journal of Operational Research, Elsevier, vol. 264(2), pages 508-523.
    7. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    8. 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.
    9. Raja Marappan & Gopalakrishnan Sethumadhavan, 2020. "Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring Problem," Mathematics, MDPI, vol. 8(3), pages 1-20, February.
    10. 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.
    11. 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.
    12. Mohammad Ehsanifar & David A. Wood & Arezoo Babaie, 2021. "UTASTAR method and its application in multi-criteria warehouse location selection," Operations Management Research, Springer, vol. 14(1), pages 202-215, June.
    13. Melachrinoudis, Emanuel & Min, Hokey, 2007. "Redesigning a warehouse network," European Journal of Operational Research, Elsevier, vol. 176(1), pages 210-229, January.
    14. Kurt Jörnsten & Andreas Klose, 2016. "An improved Lagrangian relaxation and dual ascent approach to facility location problems," Computational Management Science, Springer, vol. 13(3), pages 317-348, July.
    15. 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.
    16. Pierre Hansen & Jack Brimberg & Dragan Urošević & Nenad Mladenović, 2007. "Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 552-564, November.
    17. Gwo-Hshiung Tzeng, 1985. "Coal Transportation System Modeling: The Case of Taiwan," The Energy Journal, , vol. 6(1), pages 145-156, January.
    18. Yunes Almansoub & Ming Zhong & Asif Raza & Muhammad Safdar & Abdelghani Dahou & Mohammed A. A. Al-qaness, 2022. "Exploring the Effects of Transportation Supply on Mixed Land-Use at the Parcel Level," Land, MDPI, vol. 11(6), pages 1-28, May.
    19. 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.
    20. 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.

    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.