[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

A novel solution for GCP based on an OLMS membrane algorithm with dynamic operators

  • Regular Paper
  • Published:
Journal of Membrane Computing Aims and scope Submit manuscript

Abstract

Graph coloring problem (GCP) is an NP-complete combinatorial optimization problem. Its computational complexity motivated many efforts to get approximate solutions through different meta-heuristics, such as several variants of evolutionary algorithms. On the other hand, membrane algorithms have appeared as alternative hybrid techniques merging together the structure and operators of membrane systems, along with the capabilities of optimization algorithms inside each membrane. This paper explores the ability of a new variants of one-level membrane systems using a recent variant of evolutionary algorithm dynamically using different genetic operators depending on the best fitness found. The experimental results presented show that this new algorithm, called DOGAPS, outperforms the dynamic evolutionary algorithm, with the extra value provided by the membrane system. Additionally, the role of some parameters involved in our algorithm are analyzed, including the number of membranes, iterations per membrane or mutation rate.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Second DIMACS Implementation Challenge (1992-1993, see [5], section NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability). Center for Discrete Mathematics and Theoretical Computer Science, Rutgers, The State University of New Jersey.

References

  1. Andreu-Guzmán, J. A., & Valencia-Cabrera, L. (2018). Towards a general framework for membrane algorithms. Bulletin of the International Membrane Computing Society, 5, 91–96.

    Google Scholar 

  2. Back, T., Hammel, U., & Schwefel, H. P. (1997). Evolutionary computation: comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1, 3–17.

    Article  Google Scholar 

  3. DIMACS graphs format description. Retrieved from http://archive.dimacs.rutgers.edu/pub/challenge/graph/doc/ccformat.tex. Accessed 21 Oct 2019.

  4. DIMACS graphs. Retrieved from https://mat.gsia.cmu.edu/COLOR03/. Accessed 21 Oct 2019.

  5. DIMACS Implementation Challenge. Retrieved from http://www.dimacs.rutgers.edu/archive/Challenges/. Accessed 21 Oct 2019.

  6. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of np-completeness. New York: Freeman.

    MATH  Google Scholar 

  7. Hindi, M., & Yampolskiy, R. (2012). Genetic algorithm applied to the graph coloring problem. In Midwest Artificial Intelligence and Cognitive Science Conference, p. 60.

  8. Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press.

    Google Scholar 

  9. Huang, L., & Wang, N. (2006). An optimization algorithm inspired by membrane computing. In Advances in Natural Computation, Proceedings of international conference on natural computation, Springer Berlin Heidelberg, (pp. 49–52).

  10. Huang, L., He, X., Wang, N., & Xie, Y. (2007). P systems based multi-objective optimization algorithm. Progress in Natural Science, 17, 458–465.

    Article  MathSciNet  MATH  Google Scholar 

  11. Johnson, D.S., Trick, M.A. (Eds.) Cliques, coloring, and satisfiability: second dimacs implementation challenge, Workshop, October 11–13, 1993. American Mathematical Society, 1996.

  12. Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum Press.

    Chapter  Google Scholar 

  13. Leporati, A., & Pagani, D. (2006). A membrane algorithm for the min storage problem. LectureNotes in Computer Science, 4361, 443–462.

    Article  MATH  Google Scholar 

  14. Liu, C., Zhang, G., Zhang, X., & Liu, H. (2009). A memetic algorithm based on P systems for IIR digital filter design. In Proceedings of the 8th IEEE international symposium on dependable, autonomic and secure computing (pp. 333–334).

  15. Liu, C., Zhang, G., Zhu, Y., Fang, C., & Liu, H. (2009). A quantum-inspired evolutionary algorithm based on P systems for radar emitter signals. Proceedings of the Fourth international conference on bio-inspired computing: theories and applications (pp. 24–28).

  16. Liu, C., Zhang, G., Liu, L., Gheorghe, M., & Ipate, F. (2010). An improved membrane algorithm for solving time-frequency atom decomposition. Lecture Notes in Computer Science, 5957, 371–384.

    Article  MATH  Google Scholar 

  17. Liu, J., Zhong, W., & Jiao, L. (2016). Comments on “The 1993 DIMACS graph coloring Challenge” and “Energy function-based approaches to graph Coloring”. IEEE Transactions on Neural Networks, 17, 533.

    Google Scholar 

  18. Nishida, T.Y. (2004). An application of P-system: A new algorithm for NP-complete optimization problems. In Proceedings of 8th world multi-conference on systemics, cybernetics and informatics (pp. 109–112).

  19. Nishida, T.Y. (2005). Membrane algorithm: an approximate algorithm for NP-complete optimization problems exploiting P-systems. In Proceedings of 6th International workshop on membrane computing (pp. 26–43).

  20. Nishida, T. Y. (2006). Membrane algorithms: approximate algorithms for NP-complete optimization problems. Applications of Membrane Computing (pp. 303–314).

  21. Nishida, T. Y. (2006). Membrane algorithms. Lecture Notes in Computer Science, 3850, 55–66.

    Article  MATH  Google Scholar 

  22. Păun, Gh. (2000). Computing with membranes. Journal of Computer and System Sciences, 61, 1, 108–143 (and Turku Center for Computer Science-TUCS Report 208, November 1998, http://www.tucs.fi).

    Article  MathSciNet  MATH  Google Scholar 

  23. Păun, Gh. (2002). Membrane computing: An introduction. Berlin: Springer.

    Book  MATH  Google Scholar 

  24. Păun, Gh, & Pérez-Jiménez, M. J. (2006). Membrane computing: brief introduction, recent results and applications. Biosystems, 85, 11–22.

    Article  Google Scholar 

  25. Păun, Gh, Rozenberg, G., & Salomaa, A. (Eds.). (2010). The oxford handbook of membrane computing. Oxford: Oxford University Press.

    MATH  Google Scholar 

  26. Zhang, G., Liu, C., Gheorghe, M., & Ipate, F. (2009). Solving satis ability problems with membrane algorithm. In Proceedings of the 4th international conference on bio-inspired computing: theories and applications (pp. 29–36).

  27. Zhang, G., Gheorghe, M., Pan, L., & Pérez-Jiménez, M. J. (2014). Evolutionary membrane computing: A comprehensive survey and new results. Information Sciences, 279, 528–551.

    Article  Google Scholar 

  28. Zhang, G., Gheorghe, M., & Wu, C. (2008). A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamenta Informaticae, 87, 93–116.

    MathSciNet  MATH  Google Scholar 

  29. Zhang, G., Liu, C., & Rong, H. (2010). Analyzing radar emitter signals with membrane algorithms. Mathematical and Computer Modelling, 52, 1997–2010.

    Article  Google Scholar 

  30. Zhang, G., Pérez-Jiménez, M. J., & Gheorghe, M. (2017). Membrane algorithms. Real-life applications with membrane computing (pp. 33–115). Berlin: Springer.

    Book  MATH  Google Scholar 

  31. Zhou, F., Zhang, G., Rong, H., Cheng, J., Gheorghe, M., Ipate, F., & Lefticaru, R. (2010). A particle swarm optimization based on P systems. In Proceedings of the 6th international conference on natural computation (pp. 3003–3007).

Download references

Acknowledgements

The authors acknowledge the support from research project TIN2017-89842-P, co-financed by Ministerio de Ciencia, Innovación y Universidades of Spain, through the Agencia Estatal de Investigación (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union.

Author information

Authors and Affiliations

  1. Research Group on Natural Computing Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012, Seville, Spain

    José Antonio Andreu-Guzmán & Luis Valencia-Cabrera

Authors
  1. José Antonio Andreu-Guzmán
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luis Valencia-Cabrera
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luis Valencia-Cabrera.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Andreu-Guzmán, J.A., Valencia-Cabrera, L. A novel solution for GCP based on an OLMS membrane algorithm with dynamic operators. J Membr Comput 2, 1–13 (2020). https://doi.org/10.1007/s41965-019-00026-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41965-019-00026-x

Keywords

Search

Navigation