CFP last date
22 April 2024
Reseach Article

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

Published on September 2016 by Tabiya Manzoor Beigh, Girdhar Gopal
Recent Innovations in Computer Science and Information Technology
Foundation of Computer Science USA
RICSIT2016 - Number 1
September 2016
Authors: Tabiya Manzoor Beigh, Girdhar Gopal
7f4bb0ed-67d8-4aa6-9f9f-c40be26d5b1c

Tabiya Manzoor Beigh, Girdhar Gopal . Use of Genetic Algorithm and Fuzzy Logic in Optimizing Graph Coloring Problem. Recent Innovations in Computer Science and Information Technology. RICSIT2016, 1 (September 2016), 1-4.

@article{
author = { Tabiya Manzoor Beigh, Girdhar Gopal },
title = { Use of Genetic Algorithm and Fuzzy Logic in Optimizing Graph Coloring Problem },
journal = { Recent Innovations in Computer Science and Information Technology },
issue_date = { September 2016 },
volume = { RICSIT2016 },
number = { 1 },
month = { September },
year = { 2016 },
issn = 0975-8887,
pages = { 1-4 },
numpages = 4,
url = { /proceedings/ricsit2016/number1/26182-2016/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 Recent Innovations in Computer Science and Information Technology
%A Tabiya Manzoor Beigh
%A Girdhar Gopal
%T Use of Genetic Algorithm and Fuzzy Logic in Optimizing Graph Coloring Problem
%J Recent Innovations in Computer Science and Information Technology
%@ 0975-8887
%V RICSIT2016
%N 1
%P 1-4
%D 2016
%I International Journal of Computer Applications
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
  1. 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.
  2. Porumbel, & Cosmin. , D. (2009). Heuristic Algorithms and Learning Techniques: Applications to the Graph Coloring Problem,. Département Informatique, Université d'Angers.
  3. Holland J. , "Adaptation in natural and artificial systems", University of Michigan Press, Ann Arbor, 1975.
  4. Goldberg D. E. , "Genetic algorithms in search, optimization, and machine learning", Addison Wesley Longman, Inc. , ISBN 0-201- 15767-5, 1989.
  5. Diaz, Mendez, I. , & Zabala, P. (1999). A generalization of the Graph Coloring Problem. Departamento de Computacion, .
  6. 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.
  7. Tagawa, K. K. (1999). Distance based hybrid genetic algorithm: an application for the graph coloring problem. In Proceedings of Congress on Evolutionary 2332. Washington.
  8. 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.
  9. 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).
  10. Lorena, L. A. (1997). "Constructive genetic algorithm for graph coloring. " Submetido para. Pesquisa Operacional.
  11. Garey, M. J. (1979). Computers and Intractability: A Guide to the Theory of NP- Completeness. New York, Nantes, France. : Freeman and Company.
  12. Rakesh Kumar, Gopal Girdhar (2013). Alpha Cut Based novel selection for Genetic Algorithm. International Journal Of Computer Applications , 13-17.
  13. 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).
Index Terms

Computer Science
Information Sciences

Keywords

Alpha Cut Fuzzy Logic Genetic Algorithm Graph Coloring Problem Selection