Earticle

초록

영어

Proper coloring of the vertices of a graph with minimum number of colors has always been of great interest of researchers in the field of soft computing. Genetic Algorithm (GA) and its application as the solution method to the Graph Coloring problem have been appreciated and worked upon by the scientists almost for the last two decades. Various genetic operators such as crossover and mutation have been used in the GA probabilistically in the previous works, which distributes the promising solutions in the search space at each generation. This paper introduces a new operator, called double point Guided Mutation operator with a special feature. An evolutionary algorithm with double point Guided Mutation for the Graph Coloring problem is proposed here, which could advance the performance level of simple GA dramatically. The algorithm has been tested upon a large-scale test graphs and has shown better output than the earlier works on the same problem. This paper describes the advancement of performance of simple GA applied upon the problem of graph coloring using a operator called double point Guided Mutation in association of the general genetic operators Crossover and Mutation used probabilistically. Our work is still going on for designing better algorithms.

목차

Abstract
 1. Introduction
 2. Heuristics and evolutionary algorithms for graph coloring
 3. Evolutionary Algorithm for graph coloring
  3.1 Representation and fitness
  3.2 Initial population
  3.3 Multi-point Special mutation
  3.4 Algorithm MSPGCA
  3.5 Complexity
 4. Computational Experiments
 5. Conclusions
 6. References

키워드

저자

• Biman Ray [ Heritage Institute of Technology ]
• Anindya J Pal [ Heritage Institute of Technology ]
• Debnath Bhattacharyya [ Department of Multimedia Hannam University ]
• Tai-hoon Kim [ Department of Multimedia Hannam University ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Signal Processing, Image Processing and Pattern Recognition

• 간기

  격월간

• pISSN

  2005-4254

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605