| 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 | |
