Call for Paper - August 2019 Edition
IJCA solicits original research papers for the August 2019 Edition. Last date of manuscript submission is July 20, 2019. Read More

Use of Genetic Algorithm and Fuzzy Logic in Optimizing Graph Coloring Problem

Print
PDF
IJCA Proceedings on Recent Innovations in Computer Science and Information Technology
© 2016 by IJCA Journal
RICSIT 2016 - Number 1
Year of Publication: 2016
Authors:
Tabiya Manzoor Beigh
Girdhar Gopal

Tabiya Manzoor Beigh and Girdhar Gopal. Article: Use of Genetic Algorithm and Fuzzy Logic in Optimizing Graph Coloring Problem. IJCA Proceedings on Recent Innovations in Computer Science and Information Technology RICSIT 2016(1):1-4, September 2016. Full text available. BibTeX

@article{key:article,
	author = {Tabiya Manzoor Beigh and Girdhar Gopal},
	title = {Article: Use of Genetic Algorithm and Fuzzy Logic in Optimizing Graph Coloring Problem},
	journal = {IJCA Proceedings on Recent Innovations in Computer Science and Information Technology},
	year = {2016},
	volume = {RICSIT 2016},
	number = {1},
	pages = {1-4},
	month = {September},
	note = {Full text available}
}

Abstract

Minimum number of colors while coloring the vertices of a graph is a massive apprehension of research scholars in the area of soft computing. Method such as Genetic Algorithm (GA) is highly preferred to solve the Graph Coloring problem by the researchers for many years. In this paper, an optimization technique based on Genetic Algorithm and Fuzzy Logic approach is applied for solving Graph Coloring Problem. The selection operator used in the optimization technique has based on Fuzzy logic. The proposed algorithm is tested on standard DIMACS instances. 11 problems from DIMACS dataset are picked and results are compared with known chromatic numbers. It has found that proposed algorithm has solved nearly all of the problem instances at very good efficiency rate.

References

  • Ali, F. F. -W. (1999). An evolutionary approach for graph coloring. In Proceedings of The International Conference on Systems, Man, and Cybernetics. (pp. 527-532). IEEE.
  • Porumbel, & Cosmin. , D. (2009). Heuristic Algorithms and Learning Techniques: Applications to the Graph Coloring Problem,. Département Informatique, Université d'Angers.
  • Holland J. , "Adaptation in natural and artificial systems", University of Michigan Press, Ann Arbor, 1975.
  • Goldberg D. E. , "Genetic algorithms in search, optimization, and machine learning", Addison Wesley Longman, Inc. , ISBN 0-201- 15767-5, 1989.
  • Diaz, Mendez, I. , & Zabala, P. (1999). A generalization of the Graph Coloring Problem. Departamento de Computacion, .
  • Musa, M. , & Roman, V. (2012). Genetic Algorithm applied to Graph Coloring Problem. Proceedings of the Twenty third Midwest Artificial Intelligence and Cognitive Science. University of Cincinnati Cincinnati, Ohio.
  • Tagawa, K. K. (1999). Distance based hybrid genetic algorithm: an application for the graph coloring problem. In Proceedings of Congress on Evolutionary 2332. Washington.
  • Croitoru, C. L. (2002). A New Genetic Graph Coloring Heuristic. In Proceedings of The Computational Symposium on Graph Coloring and its Generalizations, (pp. 63-74). Ithaca, New York, USA.
  • Biman Ray, A. J. (2010). An Efficient GA with Multipoint Guided Mutation for Graph Coloring Problems. International Journal of Signal Processing, Image Processing and Pattern Recognition , 3 (2).
  • Lorena, L. A. (1997). "Constructive genetic algorithm for graph coloring. " Submetido para. Pesquisa Operacional.
  • Garey, M. J. (1979). Computers and Intractability: A Guide to the Theory of NP- Completeness. New York, Nantes, France. : Freeman and Company.
  • Rakesh Kumar, Gopal Girdhar (2013). Alpha Cut Based novel selection for Genetic Algorithm. International Journal Of Computer Applications , 13-17.
  • Back, T. , Hammel, U. , & Schwefel, H. P. (1997). Evolutionary computation: comments on the history and current state. IEEE Transactions on Evolutionary Computation1, (pp. 3-17).