Ahmed Fouad Ali; Nashwa Nageh Ahmed

Differential Evolution Algorithm with Space Partitioning for Large-Scale Optimization Problems

Full Text (PDF, 803KB), PP.49-59

Views: 0 Downloads: 0

Author(s)

Ahmed Fouad Ali ^1,* Nashwa Nageh Ahmed ²

1. Suez Canal University, Dept. of Computer Science, Faculty of Computers and Information, Ismailia, 41552, Egypt

2. Suez Canal University, Dept. of Mathematics, Faculty of Science, Ismailia, 41552, Egypt

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2015.11.07

Received: 27 Feb. 2015 / Revised: 20 Jun. 2015 / Accepted: 14 Aug. 2015 / Published: 8 Oct. 2015

Index Terms

Differential evolution algorithm, evolutionary algorithms, large-scale optimization, globe optimization

Abstract

Differential evolution algorithm (DE) constitutes one of the most applied meta-heuristics algorithm for solving global optimization problems. However, the contributions of applying DE for large-scale global optimization problems are still limited compared with those problems for low and middle dimensions. DE suffers from slow convergence and stagnation, specifically when it applies to solve global optimization problems with high dimensions. In this paper, we propose a new differential evolution algorithm to solve large-scale optimization problems. The proposed algorithm is called differential evolution with space partitioning (DESP). In DESP algorithm, the search variables are divided into small groups of partitions. Each partition contains a certain number of variables and this partition is manipulated as a subspace in the search process. Selecting different subspaces in consequent iterations maintains the search diversity. Moreover, searching a limited number of variables in each partition prevents the DESP algorithm from wandering in the search space especially in large-scale spaces. The proposed algorithm is tested on 15 large- scale benchmark functions and the obtained results are compared against the results of three variants DE algorithms. The results show that the proposed algorithm is a promising algorithm and can obtain the optimal or near optimal solutions in a reasonable time.

Cite This Paper

Ahmed Fouad Ali, Nashwa Nageh Ahmed, "Differential Evolution Algorithm with Space Partitioning for Large-Scale Optimization Problems", International Journal of Intelligent Systems and Applications(IJISA), vol.7, no.11, pp.49-59, 2015. DOI:10.5815/ijisa.2015.11.07

Reference

[1]A.F. Ali, A. E. Hassanien, V. Sná?el, and M. F. Tolba, “A New Hybrid Particle Swarm Optimization with Variable Neighborhood Search for Solving Unconstrained Global Optimization Problems,” Advances in Intelligent Systems and Computing, pp. 151–160, 2014.
[2]A.F. 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.
[3]J. Brest, MS. Maucec Population size reduction for the differential evolution algorithm. Appl Intell, 29:228–247, 2008
[4]S.A. Chu, P.-W. Tsai, and J.-S. Pan. Cat swarm optimization. Lecture Notes in Computer Science (including subseries Lecture Notes in Arti_cial Intelligence and Lecture Notes in Bioinformatics), 4099 LNAI:854-858, 2006.
[5]S. Das, A. Abraham, UK. Chakraborty, A. Konar Differential evolution using a neighborhood-based mutation operator. IEEE Trans Evol Comput, 13(3):526–553, 2009.
[6]M. Dorigo, Optimization, Learning and Natural Algorithms, Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
[7]A. Duarte, R. RMarti, F. Glover, F. Gortazar, Hybrid scatter tabu search for unconstrained global optimization. Ann Oper Res 183:95–123, 2011.
[8]N. Hansen, The CMA evolution strategy: a comparing review. In: Lozano JA, Larra?aga P, Inza I, Bengoetxea E(eds) Towards a new evolutionary computation. Springer, Berlin, 2006.
[9]P. Hansen, N. Mladenovic, JA. Pérez Variable neighbourhood search: methods and applications. Ann Oper Res 175(1):367–407, Moreno, 2010.
[10]A. Hedar and A.F. Ali, Tabu Search with Multi-Level Neighborhood Structures for High Dimensional Problems Applied Intelligence, Springer, 2012.
[11]A. Hedar, A. Fouad, 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), Cairo, Egypt, pp 151–156, 2009.
[12]A. Hedar, M. Fukushima, Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization. Optim Methods Softw 17:891–912, 2002.
[13]F. Herrera, M. Lozano, JL. Verdegay, Tackling real-coded genetic algorithms: Operators and tools for behavioral analysis. Artif Intell Rev 12:265–319, 1998.
[14]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.
[15]D. Karaboga and B. Basturk. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (abc) algorithm. Journal of global optimization, 39(3):459-471, 2007.
[16]J. Kennedy, RC. Eberhart, Particle Swarm Optimization, Proceedings of the IEEE International Conference on Neural Networks, Vol 4, pp 1942-1948, 1995.
[17]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.
[18]CY. Lee, X. Yao, Evolutionary programming using the mutations based on the Lévy probability distribution. IEEE Trans Evol Comput 8:1–13, 2004.
[19]YW. Leung, Y. Wang, An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Trans Evol Comput 5(1):41–53, 2001.
[20]M. Lozano, F. Herrera, N. Krasnogor, D. Molina, Real-coded memetic algorithms with crossover hill-climbing. Evol Comput 12(3):273–302, 2004.
[21]X.L. Li, Z.J. Shao, and J.X. Qian. Optimizing method based on autonomous animats: Fish-swarm algorithm. Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice, 22(11):32, 2002.
[22]JJ. Liang, AK. Qin, PN. Suganthan, S. Baskar Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans Evol Comput 10(3):281–295, 2006.
[23]Y. Li, X. Zeng, Multi-population co-genetic algorithm with double chain-like agents structure for parallel global numerical optimization. Appl Intell 32:292–310, 2010.
[24]M.H. Mashinchia, MA. Orguna, W. Pedryczb, Hybrid optimization with improved tabu search. Appl Soft Comput 11(2):1993–2006, 2011.
[25]A.W. Mohamed, H.Z. Sabry and M. Khorshid, An alternative differential evolution algorithm for global optimization, Journal of advanced research, 3, 149-165, 2012.
[26]N. Mladenovic, M. Drazic, V. Kovac, M. Angalovic General variable neighborhood search for the continuous optimization. Eur J Oper Res 191:753–770, 2008.
[27]H. Mühlenbein, D. Schlierkamp, Predictive models for the breeder genetic algorithm. IEEE Trans Evol Comput 1(1):25–, 1993.
[28]QH. Nguyen, YS. Ong, MH, Lim, A probabilistic memetic framework. IEEE Trans Evol Comput 13(3):604–623, 2009.
[29]N. Noman, H. Iba, Accelerating differential evolution using an adaptive local search. IEEE Trans Evol Comput 12(1):107–125, 2008.
[30]ZJ. Pan, LS. Kang, An adaptive evolutionary algorithms for numerical optimization. In: Yao X, Kim JH, Furuhashi T (eds) Simulated evolutionary and learning. Lecture notes in artificial intelligence. Springer, Berlin, pp 27–34, 1997.
[31]M.K. Passino, Biomimicry of bacterial foraging for distributed optimization and control. Control Systems, IEEE 22(3):52-67, 2002.
[32]KV. Price, RM. Storn, JA. Lampinen, Differential evolution: a practical approach to global optimization. Springer, Berlin, 2005.
[33]R. Storn, K. Price, Differential evolution a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11:341-359, 1997.
[34]K. Socha, M. Dorigo, Ant colony optimization for continuous domains. Eur J Oper Res 185(3):1155–1173, 2008.
[35]R. Tang, S. Fong, X.S. Yang, and S. Deb. Wolf search algorithm with ephemeral memory. In Digital Information Management (ICDIM), 2012 Seventh International Conference on Digital Information Management, pages 165-172, 2012.
[36]D. Teodorovic and M. DellOrco. Bee colony optimizationa cooperative learning approach to complex tranportation problems. In Advanced OR and AI Methods in Transportation: Proceedings of 16th MiniEURO Conference and 10th Meeting of EWGT (13-16 September 2005).Poznan: Publishing House of the Polish Operational and System Research, pages 51-60, 2005.
[37]AK. Qin, VL. Huang, PN. Suganthan, Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput 13(2):298–417, 2009.
[38]JA. Vrugt, BA. Robinson, JM. Hyman, Self-adaptive multimethod search for global optimization in real-parameter spaces. IEEE Trans Evol Comput 13(2), 2009.
[39]X.S. Yang. A new meta-heuristic bat-inspired algorithm. Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), pages 6574, 2010.
[40]X.S. Yang. Firey algorithm, stochastic test functions and design optimisation. International Journal of Bio-Inspired Computation, 2(2):78-84, 2010.
[41]X. Yao, Y. Liu, G. Lin, Evolutionary programming made faster. IEEE Trans Evol Comput 3(2):82–102, 1999.
[42]W. Zhong, J. Liu, M. Xue, L. Jiao, A Multiagent genetic algorithm for global numerical optimization. IEEE Trans Syst Man Cybern, Part B, Cybern 34(2):1128–1141, 2004.

International Journal of Intelligent Systems and Applications (IJISA)