Paper title:

Using Harmony Search Algorithm to Solve the N-Region Four Color Map Problem

Published in: Issue 1, (Vol. 6) / 2012
Publishing date: 2011-04-11
Pages: 36-41
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
References:

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
Creative Commons License
This article is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.
Home | Editorial Board | Author info | Archive | Contact
Copyright JACSM 2007-2022