Improved Harmony Search with Chaos for Solving Linear Assignment Problems

Full Text (PDF, 563KB), PP.55-61

Views: 0 Downloads: 0


Osama Abdel-Raouf 1,* Mohamed Abdel-Baset 2 Ibrahim El-henawy 3

1. Department of Operations Research, Faculty of Computers and Information, Menoufia University, Menoufia, ShebinEl-come, Egypt

2. Department of Operations Research, Faculty of Computers and Informatics, Zagazig University, El-ZeraSquare, Zagazig, Sharqiyah, Egypt

3. Department of Computer Science, Faculty of Computers and Informatics, Zagazig University, El-ZeraSquare, Zagazig, Sharqiyah, Egypt

* Corresponding author.


Received: 11 Jun. 2013 / Revised: 7 Oct. 2013 / Accepted: 25 Dec. 2013 / Published: 8 Apr. 2014

Index Terms

Harmony Search Algorithm, Meta-Heuristics, Optimization, Assignment Problem, Chaos, Evolutionary Algorithms


This paper presents an improved version of a harmony meta-heuristic algorithm, (IHSCH), for solving the linear assignment problem. The proposed algorithm uses chaotic behavior to generation a candidate solution in a behavior similar to acoustic monophony. Numerical results show that the IHSCH is able to obtain the optimal results in comparison with traditional methods (the Hungarian method). However, the benefit of the proposed algorithm is its ability to obtain the optimal solution within less computation in comparison with the Hungarian method.

Cite This Paper

Osama Abdel-Raouf, Mohamed Abdel-Baset, Ibrahim El-henawy, "Improved Harmony Search with Chaos for Solving Linear Assignment Problems", International Journal of Intelligent Systems and Applications(IJISA), vol.6, no.5, pp.55-61, 2014. DOI:10.5815/ijisa.2014.05.05


[1]M. Balinski, "Signature methods for the assignment problem," Operations research, vol. 33, pp. 527-536, 1985.

[2]R. E. Burkard, M. Dell'Amico, and S. Martello, Assignment problems: Siam, 2009.

[3]H. W. Kuhn, "The Hungarian method for the assignment problem," Naval research logistics quarterly, vol. 2, pp. 83-97, 1955.

[4]M. Aigner, Combinatorial theory vol. 234: Springer-Verlag New York, 1979.

[5]O. Abdel-raouf and M. A.-b. Metwally, "A Survey of Harmony Search Algorithm," International Journal of Computer Applications, vol. 70, 2013.

[6]Z. W. Geem, J. H. Kim, and G. Loganathan, "A new heuristic optimization algorithm: harmony search," Simulation, vol. 76, pp. 60-68, 2001.

[7]Z. Geem, J. Kim, and G. Loganathan, "Harmony search optimization: application to pipe network design," International journal of modelling & simulation, vol. 22, pp. 125-133, 2002.

[8]Z. W. Geem, C.-L. Tseng, and Y. Park, "Harmony search for generalized orienteering problem: best touring in China," in Advances in natural computation, ed: Springer, 2005, pp. 741-750.

[9]J. H. Kim, Z. W. Geem, and E. S. Kim, "Parametersestimationofthenonlinear muskingummodelusingHarmonysearch," JAWRA Journal of the American Water Resources Association, vol. 37, pp. 1131-1138, 2001.

[10]K. S. Lee and Z. W. Geem, "A new structural optimization method based on the harmony search algorithm," Computers & Structures, vol. 82, pp. 781-798, 2004.

[11]M. Mahdavi, M. Fesanghary, and E. Damangir, "An improved harmony search algorithm for solving optimization problems," Applied mathematics and computation, vol. 188, pp. 1567-1579, 2007.

[12]M. G. Omran and M. Mahdavi, "Global-best harmony search," Applied Mathematics and Computation, vol. 198, pp. 643-656, 2008.

[13]Q.-K. Pan, P. N. Suganthan, M. F. Tasgetiren, and J. J. Liang, "A self-adaptive global best harmony search algorithm for continuous optimization problems," Applied Mathematics and Computation, vol. 216, pp. 830-848, 2010.

[14]Q.-K. Pan, P. Suganthan, J. Liang, and M. F. Tasgetiren, "A local-best harmony search algorithm with dynamic subpopulations," Engineering Optimization, vol. 42, pp. 101-117, 2010.

[15]S. Das, A. Mukhopadhyay, A. Roy, A. Abraham, and B. K. Panigrahi, "Exploratory power of the harmony search algorithm: analysis and improvements for global numerical optimization," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 41, pp. 89-106, 2011.

[16]D. Zou, L. Gao, J. Wu, S. Li, and Y. Li, "A novel global harmony search algorithm for reliability problems," Computers & Industrial Engineering, vol. 58, pp. 307-316, 2010.

[17]Z. W. Geem, K. S. Lee, and Y. Park, "Application of harmony search to vehicle routing," American Journal of Applied Sciences, vol. 2, p. 1552, 2005.

[18]R. Barton, "Chaos and fractals," The Mathematics Teacher, vol. 83, pp. 524-529, 1990.

[19]G. Heidari-Bateni and C. D. McGillem, "A chaotic direct-sequence spread-spectrum communication system," Communications, IEEE Transactions on, vol. 42, pp. 1524-1527, 1994.

[20]Y. Ke, J. Cheng, and W. Ng, "MIC framework: an information-theoretic approach to quantitative association rule mining," in Data Engineering, 2006. ICDE'06. Proceedings of the 22nd International Conference on, 2006, pp. 112-112.

[21]B. Alatas, "Chaotic harmony search algorithms," Applied Mathematics and Computation, vol. 216, pp. 2687-2699, 2010.

[22]P. Gaspard, Chaos, scattering and statistical mechanics vol. 9: Cambridge University Press, 2005.

[23]C. Letellier, Chaos in nature vol. 81: World Scientific Publishing Company, 2013.

[24]D. Yang, G. Li, and G. Cheng, "On the efficiency of chaos optimization algorithms for global optimization," Chaos, Solitons & Fractals, vol. 34, pp. 1366-1375, 2007.