Paper Info
Title
A hybrid genetic hill-climbing algorithm for four-coloring map problems
Abstract
We propose a Hybrid Genetic hill-climbing Algorithm (HGA) search algorithm and in this paper, demonstrated for n-region 4-coloring map problems. The HGA incorporates the usual Genetic Algorithm (with reproduction, crossover and mutation genetic operators) and a local hill-climbing algorithm. To effectively reduce the magnitude of the search space by 23 times (equivalent to better than one order of magnitude), in particular where n6, we propose a group representation that does not result in any loss of generality. We further propose an objective measure as a guide for the search process. To depict the efficacy of the proposed HGA algorithm, we compare its performance against the established standard Genetic Algorithm, Hill-climbing and an artificial neural network optimization algorithm for several n-region 4-color maps. We show that the proposed HGA is the only algorithm that is able to obtain an optimal solution for large maps (n500). Furthermore, we show that the proposed HGA is the fastest algorithm to yield an optimal solution in all n-region 4-color maps compared.
Year
Venue
Keywords
2003
HIS
four-coloring map problem,fastest algorithm,hybrid genetic hill-climbing algorithm,optimal solution,proposed hga,search algorithm,search process,established standard genetic algorithm,proposed hga algorithm,local hill-climbing algorithm,n-region 4-color map,hill climbing,genetics
Field
DocType
Volume
Hill climbing,Mathematical optimization,Crossover,Search algorithm,Computer science,Algorithm,FSA-Red Algorithm,Operator (computer programming),Artificial neural network,Population-based incremental learning,Genetic algorithm
Conference
104
ISSN
ISBN
Citations 
0922-6389
1-58603-394-8
2
PageRank 
References 
Authors
0.41
8
2
Name
Order
Citations
PageRank
Bah-Hwee Gwee124460.10
Josep S. Chang220.41