Using Harmony Search Algorithm to Solve the N-Region Four Color Map Problem
|Published in:||Issue 1, (Vol. 6) / 2012|
|Author(s):||HORCA Romie B., YUSIONG John Paul T.|
|Abstract.||The Harmony Search (HS) algorithm is a relatively recent addition to the family of optimization algorithms. It imitates the behavior of musicians when composing their music such as random playing of notes, previous composition-based play, and pitch-adjusted play. The algorithm was used in solving the Four Color Map Problem. In this problem, it is said one can color the regions of a map using a maximum of four colors only with the constraint that no neighboring regions should share the same color. Neighboring regions mean two regions having a common boundary, not just a common point. Simulation results proved the feasibility of HS as the primary optimization technique in solving sample maps|
|Keywords:||Optimization, Harmony Search Algorithm, Four Color Map Theorem, Map Coloring|
1. Appel, K. and Haken W.: Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977). p. 429-490.
2. Appel, K. and Haken W., Koch, J.: Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977). 491- 567
3. Computer Science Department, College of Saint Benedict, Saint John's University. From, http://www.csbsju.edu/ computer-science.html (Accessed: November 2010).
4. Cook, S.: The P versus NP Problem. University of Toronto. From,http://www.claymath.org/millennium/P_vs_NP/Official_ Problem_Description.pdf (Accessed: November 2010).
5. Geem, Z.W., Kim, J.H., and Loganathan, G.V.: A New Heuristic Optimization Algorithm. Harmony Search Simulation (2001).
6. Geem, Z.W.: Music-Inspired harmony Search Algorithm - Theory and Applications. Studies in Computational Intelligence, Vol. 191 ISBN: (2009). 1-12
7. Gonthier, G.: A computer-checked proof of the four colour theorem. From, http://en.wikipedia.org/wiki/ Four_color_theorem. (Accessed: November 2010).
9. Holland, J., Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA, (1992).
10. Kumar, A.: Using a Genetic Algorithm Approach to solve the N-Region Four Colour Map Problem. First International Conference on Emerging Trends in Engineering and Technology (2008).
12. Papadimitriou, C.H., Dasgupta, S., and Vazirani, U.V.: NPcomplete Problems. Algorithms (2006), 257-258.
13. Papalambros, P.Y. and Wilde, D.J.: Principles of Optimal Design: Modeling and Computation, Cambridge University Press. ISBN 0-521-62727-3 (2000).
14. Romero, V.M., Tomes L.L., Yusiong, J.P.T.: Tetris Agent Optimization Using Harmony Search Algorithm. International Journal of Computer Science Issues, Vol. 8, Issue 1. (2011). p. 22 – 31.
|Back to the journal content|
This article is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.