Skip to main content
Presentation
USING A GENETIC ALGORITHM APPROACH TO SOLVE THE N-REGION FOUR COLOUR MAP PROBLEM
IEEE co sponsored National Conference (2008)
  • anand kumar
Abstract

This paper presents a genetic algorithm approach to solve the “n-region four colour map problem”. The “n-region four colour map problem is NP complete problem and - one of the hardest problems in the class NP (non-deterministic polynomial problems). A genetic algorithm is simply the algorithm used to simulate evolution. It takes candidate solutions, selects some of the best using user-defined evaluation functions, applies user-defined transformations (often called mutation and crossover, but implementations of these depend on the problem), and makes new candidate solutions. Genetic Algorithms are being used extensively in optimization problem as an alternative to traditional heuristics. It is an appealing idea that the natural concepts of evolution may be borrowed for use as a computational optimization technique, which is based on the principle “Survival of the fittest” given by “Darvin”. In this paper I have used genetic algorithm as an optimization technique to provide the solution for “n-region four colour map problem”. I have tried to show that genetic algorithm is an alternative solution for this NP hard problem where conventional deterministic methods are not able to provide the optimal solution. .

Keywords
  • Genetic Algorithm,
  • Four colour map,
  • graph,
  • GA operators,
  • NP- complete.
Disciplines
Publication Date
Summer May 16, 2008
Citation Information
anand kumar. "USING A GENETIC ALGORITHM APPROACH TO SOLVE THE N-REGION FOUR COLOUR MAP PROBLEM" IEEE co sponsored National Conference (2008)
Available at: http://works.bepress.com/anandkumar/4/