Hybrid Simulated Annealing and Nelder-Mead Algorithm for Solving Large-Scale Global Optimization Problems

Download Full Text
Author(s):
Ahmed Fouad Ali
Published Date:
May 05, 2014
Issue:
Volume 4, Issue 3
Page(s):
1 - 11
DOI:
10.7815/ijorcs.43.2014.084
Views:
4726
Downloads:
115

Keywords:
global optimization, large-scale optimization, nelder-mead algorithm, simulated annealing
Citation:
Ahmed Fouad Ali, "Hybrid Simulated Annealing and Nelder-Mead Algorithm for Solving Large-Scale Global Optimization Problems". International Journal of Research in Computer Science, 4 (3): pp. 1-11, May 2014. doi:10.7815/ijorcs.43.2014.084 Other Formats

Abstract

This paper presents a new algorithm for solving large scale global optimization problems based on hybridization of simulated annealing and Nelder-Mead algorithm. The new algorithm is called simulated Nelder-Mead algorithm with random variables updating (SNMRVU). SNMRVU starts with an initial solution, which is generated randomly and then the solution is divided into partitions. The neighborhood zone is generated, random number of partitions are selected and variables updating process is starting in order to generate a trail neighbor solutions. This process helps the SNMRVU algorithm to explore the region around a current iterate solution. The Nelder- Mead algorithm is used in the final stage in order to improve the best solution found so far and accelerates the convergence in the final stage. The performance of the SNMRVU algorithm is evaluated using 27 scalable benchmark functions and compared with four algorithms. The results show that the SNMRVU algorithm is promising and produces high quality solutions with low computational costs.

  1. K. Bouleimen, H. Lecocq. "A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version". European Journal of Operational Research, 149:268-281, 2003. doi: 10.1016/s0377-2217(02)00761-0.
  2. J. Brest, M. Maucec. "Population size reduction for the differential evolution algorithm". Appl Intell 29:228-247, 2008. doi: 10.1007/s10489-007-0091-x.
  3. V. Cerny. "A thermodynamical approach to the traveling salesman problem". An efficient simulation algorithm, Journal of Optimization Theory and Applications,45:41-51, 1985. doi: 10.1007/bf00940812.
  4. H. Cho, Y. Kim. "A simulated annealing algorithm for resource constrained project scheduling problems".Journal of the Operational Research Society, 48: 736-744, 1997. doi: 10.2307/3010062.
  5. P. Damodaran, M. Vlez-Gallego. "A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times" .Expert Systems with Applications, 39:1451-1458, 2012. doi: 10.1016/j.eswa.2011.08.029.
  6. S. Das, A. Abraham, U. Chakraborty, A. Konar. "Differential evolution using a neighborhood-based mutation operator" . IEEE Trans Evol Comput, 13(3):526-553, 2009. 10.1109/tevc.2008.2009457.
  7. E. Dolan. " Pattern Search Behaviour in Nonlinear Optimization". Thesis, 1999.
  8. S. Garcia, M. Lozano, F. Herrera, D. Molina, A. Snchez. "Global and local real-coded genetic algorithms based on parentcentric crossover operators". Eur J Oper Res 185:1088-1113, 2008. doi: 10.1016/j.ejor.2006.06.043.
  9. F. Glover, E. Taillard, D. Werra. "A user's guide to tabu search". Annals of operations research. 41 (1), pp 1-28. 1993. doi: 10.1007/BF02078647.
  10. M. Hadi, M. Orguna, W. Pedryczb. "Hybrid optimization with improved tabu search". Appl Soft Comput, 11(2):1993-2006, 2011. doi: 10.1016/j.asoc.2010.06.015.
  11. P. Hansen, N. Mladenovic, M. Prezreno. "Variable neighborhood search : methods and applications". Ann Oper Res, 175(1):367-407, 2010. doi: 10.1007/s10479-009-0657-6.
  12. Hedar, AF. Ali. "Tabu search with multi-level neighborhood structures for high dimensional problems". Appl Intell, 37:189-206, 2012. doi: 110.1007/s10489-011-0321-0.
  13. A. Hedar, A. F. Ali. "Genetic algorithm with population partitioning and space reduction for high dimensional problems", in: Proceeding of the 2009, International Conference on Computer Engineering and Systems, (ICCES09), PP.151-156 Cairo, Egypt 2009. doi: 10.1109/icces.2009.5383293.
  14. F. Herrera, M. Lozano, J. Verdegay, "Tackling real-coded genetic algorithms: Operators and tools for behavioral analysis". Artif Intell Rev, 12:265-319, 1998. doi: 10.1023/a:1006504901164.
  15. F. Herrera, M. Lozano, D. Molina. "Continuous scatter search: An analysis of the integration of some combination methods and improvement strategies". Eur J Oper Res, 169(2):450-476, 2006. doi: 10.1016/j.ejor.2004.08.009.
  16. L. Hvattum, F. Glover, "Finding local optima of high- dimensional functions using direct search methods", European Journal of Operational Research, 195:31-45, 2009. doi: 10.1016/j.ejor.2008.01.039.
  17. D. Kim, K. Kim, F. Chen, " Unrelated parallel machine scheduling with setup times using simulated annealing", Robotics and Computer-Integrated Manufacturing, 18:223-231, 2002. doi: 10.1016/s0736-5845(02)00013-3.
  18. S. Kirkpatrick, C. Gelatt, M. Vecchi. "Optimization by simulated annealing", Science,220(4598):671-680, 1983. doi: 10.1016/s0736-5845(02)00013-3.
  19. T. Kolda, R. Lewies, V. Torczon, "Optimization by direct search: New perspectives on some classical and modern methods", SIAM Review,45:385-482, 2003. doi: 10.1137/s003614450242889.
  20. M. Laguna, R. Mart, "Experimental testing of advanced scatter search designs for global optimization of multimodal functions" , J Glob Optim;33(2):235-255, 2005. doi: 10.1007/s10898-004-1936-z.
  21. W. Lee, W. Ch, P. Chen. "A simulated annealing approach to make span minimization on identical parallel machines". International Journal of Advanced Manufacturing Technology, 31:328-334, 2006. doi: 10.1007/s00170-005-0188-5.
  22. J. Liang, P. Suganthan, K. Deb, " Novel composition test functions for numerical global optimization, in: Proceedings of 2005 IEEE Swarm Intelligence Symposium, 8-10 June, pp.68-75, 2005. doi: 10.1109/sis.2005.1501604.
  23. J. Liang, A. Qin, P. Suganthan, S. Baskar, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans Evol Comput, 10(3):281-295, 2006. doi: 10.1109/tevc.2005.857610.
  24. Y. Li, X. Zeng, "Multi-population co-genetic algorithm with double chain-like agents structure for parallel global numerical optimization", Appl Intell, 32: 0, 292-310, 2010. doi: 10.1007/s10489-008-0146-7.
  25. M. Locatelli, " Simulated annealing algorithms for continuous global optimization: Convergence conditions", Journal of Optimization Theory and Applications, 29(1):87-102, 2000. doi: 10.1023/A:1004680806815
  26. L. MacQueen, " Some methods for classification and analysis of multivariate observations", In:L.M. LeCam, N. Neyman (Eds.), Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probabilty, University of California press, 281-297, 1967.
  27. N. Mladenovic, M. Drazic, V. Kovac, M. Angalovic, " General variable neighborhood search for the continuous optimization", Eur J Oper Res, 191:753-770, 2008. doi: 10.1016/j.ejor.2006.12.064.
  28. M. Montes, T. Stutzle, M. Birattari, M. Dorigo, "PSO: a composite particle swarm optimization algorithm", IEEE Trans Evol Comput, 13(5):1120-1132, 2009. doi: 10.1109/TEVC.2009.2021465
  29. J. Nelder, R. Mead, " A simplex method for function minimization", Computer journal, 7:308-313, 1965. doi: 10.1093/comjnl/7.4.308.
  30. C. Rosin, R. Scott, W. Hart, R. Belew, "A comparison of global and local search methods in drug docking". In: thomas Bck(Ed.), Proceeding of the Seventh international Conference on Genetic Algorithms, (ICGA97), Morgan Kaufmann, San Francisco, PP.221-228, 1997.
  31. K. Socha, M. Dorigo, "Ant colony optimization for continuous domains", Eur J Oper Res, 185(3):1155-1173 2008.doi: 10.1016/j.ejor.2006.06.046.
  32. F. Solis, R. Wets, "Minimization by random search techniques", Mathematical Operations Research 6:19-30, 1981. doi: 10.1287/moor.6.1.19.
  33. J. Spall, "Multivariate stochastic approximation using a simulation perturbation gradient approximation", IEEE Transactions on Automatic Control, 37:332-341, 1992. doi: 10.1109/9.119632.
  34. V. Torezon, "Multi-Directional Search, A Direct search algorithm for parallel machines", Phd thesis, Rice University 1989.
  35. J. Vrugt, A. Bruce, J. Hyman, Self-adaptive multimethode serach for global optimization in real parameter spaces. IEEE Transactions on Evolutionary Computation, 13, 2009. doi: 10.1109/tevc.2008.924428.
  36. M. Wright, D. Griffhs, G. Watson, "Direct search methods, Numerical Analysis 1995. Addison wesey longman, Harlow, United Kingdom 191-208, 1996.
  37. Z. Yang, K. Tang, X. Yao, "Large scale evolutionary optimization using cooperative coevolution. Information Sciences, 178:2986-2999, 2008. doi: 10.1016/j.ins.2008.02.017

  • Lenin, K., and B. Ravindhranath Reddy, "Minimization of Active pow+F211er loss by using Hybridization of Simulated Annealing and Nelder-Mead algorithm", Majlesi Journal of Energy Management, Vol 3, No 4, 2014.