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

An Efficient Memetic Algorithm for the Minimum Load Coloring Problem

Author

Listed:
  • Zhiqiang Zhang

    (Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu University, Chengdu 610106, China
    School of Information Science and Engineering, Chengdu University, Chengdu 610106, China)

  • Zhongwen Li

    (Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu University, Chengdu 610106, China
    School of Information Science and Engineering, Chengdu University, Chengdu 610106, China)

  • Xiaobing Qiao

    (College of Teachers, Chengdu University, Chengdu 610106, China)

  • Weijun Wang

    (School of Information Science and Engineering, Chengdu University, Chengdu 610106, China)

Abstract

Given a graph G with n vertices and l edges, the load distribution of a coloring q : V → {red, blue} is defined as d q = ( r q , b q ), in which r q is the number of edges with at least one end-vertex colored red and b q is the number of edges with at least one end-vertex colored blue. The minimum load coloring problem (MLCP) is to find a coloring q such that the maximum load, l q = 1/ l × max{ r q , b q }, is minimized. This problem has been proved to be NP-complete. This paper proposes a memetic algorithm for MLCP based on an improved K-OPT local search and an evolutionary operation. Furthermore, a data splitting operation is executed to expand the data amount of global search, and a disturbance operation is employed to improve the search ability of the algorithm. Experiments are carried out on the benchmark DIMACS to compare the searching results from memetic algorithm and the proposed algorithms. The experimental results show that a greater number of best results for the graphs can be found by the memetic algorithm, which can improve the best known results of MLCP.

Suggested Citation

  • Zhiqiang Zhang & Zhongwen Li & Xiaobing Qiao & Weijun Wang, 2019. "An Efficient Memetic Algorithm for the Minimum Load Coloring Problem," Mathematics, MDPI, vol. 7(5), pages 1-20, May.
    • Handle: RePEc:gam:jmathe:v:7:y:2019:i:5:p:475-:d:234245
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Wayne Pullan, 2006. "Phased local search for the maximum clique problem," Journal of Combinatorial Optimization, Springer, vol. 12(3), pages 303-323, November.
    2. Gintaras Palubeckis & Armantas Ostreika & Dalius Rubliauskas, 2015. "Maximally diverse grouping: an iterated tabu search approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(4), pages 579-592, April.
    Full references (including those not matched with items on IDEAS)

    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. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.
    2. Assif Assad & Kusum Deep, 2018. "A heuristic based harmony search algorithm for maximum clique problem," OPSEARCH, Springer;Operational Research Society of India, vol. 55(2), pages 411-433, June.
    3. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    4. Lai, Xiangjing & Hao, Jin-Kao, 2016. "Iterated maxima search for the maximally diverse grouping problem," European Journal of Operational Research, Elsevier, vol. 254(3), pages 780-800.
    5. Yang, Xiao & Cai, Zonghui & Jin, Ting & Tang, Zheng & Gao, Shangce, 2022. "A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem," European Journal of Operational Research, Elsevier, vol. 302(3), pages 925-953.
    6. Yi Chu & Boxiao Liu & Shaowei Cai & Chuan Luo & Haihang You, 2020. "An efficient local search algorithm for solving maximum edge weight clique problem in large graphs," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 933-954, May.
    7. Arne Schulz, 2022. "A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values," Annals of Operations Research, Springer, vol. 318(1), pages 501-530, November.
    8. Lai, Xiangjing & Hao, Jin-Kao & Fu, Zhang-Hua & Yue, Dong, 2021. "Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1067-1086.
    9. Qinghua Wu & Jin-Kao Hao, 2013. "An adaptive multistart tabu search approach to solve the maximum clique problem," Journal of Combinatorial Optimization, Springer, vol. 26(1), pages 86-108, July.
    10. Schulz, Arne, 2021. "The balanced maximally diverse grouping problem with block constraints," European Journal of Operational Research, Elsevier, vol. 294(1), pages 42-53.
    11. Zhou, Qing & Benlic, Una & Wu, Qinghua & Hao, Jin-Kao, 2019. "Heuristic search to the capacitated clustering problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 464-487.

    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:7:y:2019:i:5:p:475-:d:234245. 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.