IJCA Proceedings on Recent Innovations in Computer Science and Information Technology

© 2016 by IJCA Journal

RICSIT 2016 - Number 1

Year of Publication: 2016

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} }

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.

- 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).