Modified Deterministic Parameter Controlled Harmony Search Algorithm to Solve 4-Color Mapping Problem

Main Article Content

Bnar Faisal A. Daham
Mohammed Nasseh Mohammed
Kanar Shukr Mohammed

Keywords

Optimization, 4-Color Mapping Problem, Harmony Search Algorithm, Map Coloring, Parameter Control

Abstract





Harmony Search Algorithm (HSA) is one of the optimization algorithms which is imitating the behavior of musicians when composing melodies. This algorithm which consists of three phases; initialization, improvisation, and selection has been applied in this paper with some variations to solve the 4-Color Mapping Problem.


In this study, two approaches have been applied together and introduced to enhance the performance of HSA, in solving the 4-Color Mapping Problem. The first modification has been applied to the initialization section of the algorithm. And the second approach included using a number of deterministic parameter control rules to fine-tune these parameters individually and dynamically, turning harmony search into a more dynamic algorithm.






Hence, by applying both of them, better results were obtained in terms of higher performance of  the improvisation process,  and  consequently,  reducing  the time  and  number  of  cycles taken to solve  the 4-color mapping problem compared to the original HSA. In this paper, maps with different numbers of regions have been taken as case studies, using HSA, Modified Harmony Search Algorithm (MHSA), Deterministic Parameter Controlled Harmony Search Algorithm (PCHSA), and Modified Deterministic Parameter Controlled Harmony Search Algorithm (MPCHSA). The experimental results revealed that MPCHSA has better outcomes compared to HSA, MHSA, and PCHSA.

Abstract 28 | PDF Downloads 22

References

Georges Gonthier (2008) ‘Formal Proof—The Four-Color Theorem’, Notices of the AMS, Volume 55, Number 11, pp. 1382-1393.
Mohammed S. Ibrahim, Ahmed T. Sadiq, and Ali M. Sagheer (2012) ‘Hybrid Scatter Search Algorithm for 4-Color Mapping Problem’, the 13th International Arab Conference on Information Technology (ACIT), ISSN 1812-0857.
Parikshit Yadav, Rajesh Kumar, S.K. Panda, and C.S. Chang (2012) ‘An Intelligent Tuned Harmony Search Algorithm for Optimisation’, Department of Electrical and Computer Engineering, National University of Singapore, Information Sciences 196, pp. 47-72.
Ren Diao and Qiang Shen (2013) ‘Deterministic Parameter Control in Harmony Search’, Department of Computer Science, Aberystwyth University, UK.
Romie B. Horca and John Paul T. Yusiong (2012) ‘Using Harmony Search Algorithm to Solve the N-Region Four Color Map Problem’, Journal of Applied Computer Science & Mathematics, Computer Science Section, no. 12 (36).
Sachin A. Patil and D. A. Patel (2013) ‘an Overview: Improved Harmony Search Algorithm and Its Applications in Mechanical Engineering’, International Journal of Engineering Science and Innovative Technology (IJESIT), Volume 2, Issue 1, pp. 433-444.
Wan-li Xiang, Mei-qing An, Yin-zhen Li, Rui-chun He, Jing-fang Zhang (2014) ‘An Improved Global-Best Harmony Search Algorithm for Faster Optimization’, Expert Systems with Applications 41, pp. 5788–5803.