Abstract
This paper proposes a novel algorithm for large-scale optimization problems. The proposed algorithm, namely shuffle or update parallel differential evolution (SOUPDE) is a structured population algorithm characterized by sub-populations employing a Differential evolution logic. The sub-populations quickly exploit some areas of the decision space, thus drastically and quickly reducing the fitness value in the highly multi-variate fitness landscape. New search logics are introduced into the sub-population functioning in order to avoid a diversity loss and thus premature convergence. Two simple mechanisms have been integrated in order to pursue this aim. The first, namely shuffling, consists of randomly rearranging the individuals over the sub-populations. The second consists of updating all the scale factors of the sub-populations. The proposed algorithm has been run on a set of various test problems for five levels of dimensionality and then compared with three popular meta-heuristics. Rigorous statistical and scalability analyses are reported in this article. Numerical results show that the proposed approach significantly outperforms the meta-heuristics considered in the benchmark and has a good performance despite the high dimensionality of the problems. The proposed algorithm balances well between exploitation and exploration and succeeds to have a good performance over the various dimensionality values and test problems present in the benchmark. It succeeds at outperforming the reference algorithms considered in this study. In addition, the scalability analysis proves that with respect to a standard Differential Evolution, the proposed SOUPDE algorithm enhances its performance while the dimensionality grows.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Apolloni J, Leguizamón G, García-Nieto J, Alba E (2008) Island based distributed differential evolution: an experimental study on hybrid testbeds. In: Proceedings of the IEEE international conference on hybrid intelligent systems, pp 696–701
Brest J, Maučec MS (2008) Population size reduction for the differential evolution algorithm. Appl Intell 29(3):228–247
Brest J, Greiner S, Bošković B, Mernik M, Žumer V (2006) Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Trans Evol Comput 10(6):646–657
Brest J, Bošković B, Greiner S, Žumer V, Maučec MS (2007) Performance comparison of self-adaptive and adaptive differential evolution algorithms. Soft Comput 11(7):617–629
Brest J, Zamuda A, Bošković B, Maucec MS, Žumer V (2008) High-dimensional real-parameter optimization using self-adaptive differential evolution algorithm with population size reduction. In: Proceedings of the IEEE world congress on computational intelligence, pp 2032–2039
Chakraborty UK (ed) (2008) Advances in differential evolution, vol 143. Studies in computational intelligence. Springer, Berlin
Feoktistov V (2006) Differential evolution in search of solutions. Springer, Berlin
García S, Fernández A, Luengo J, Herrera F (2008a) A study of statistical techniques and performance measures for genetics-based machine learning: accuracy and interpretability. Soft Comput 13(10):959–977
García S, Molina D, Lozano M, Herrera F (2008b) A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the cec’2005 special session on real parameter optimization. J Heuristics 15(6):617–644
Hart WE, Krasnogor N, Smith JE (2004) Memetic evolutionary algorithms. In: Hart WE, Krasnogor N, Smith JE, (eds) Recent advances in memetic algorithms. Springer, Berlin, pp 3–27
Holm S (1979) A simple sequentially rejective multiple test procedure. Scand J Stat 6(2):65–70
Kononova AV, Hughes KJ, Pourkashanian M, Ingham DB (2007) Fitness diversity based adaptive memetic algorithm for solving inverse problems of chemical kinetics. In: Proceedings of the IEEE congress on evolutionary computation, pp 2366–2373
Kononova AV, Ingham DB, Pourkashanian M (2008) Simple scheduled memetic algorithm for inverse problems in higher dimensions: application to chemical kinetics. In: Proceedings of the IEEE world congress on computational intelligence, pp 3906–3913
Korošec P, Šilc J (2008) The differential ant-stigmergy algorithm for large scale real-parameter optimization. In: ANTS ’08: Proceedings of the 6th international conference on ant colony optimization and swarm intelligence. Lecture notes in computer science. Springer, Berlin, pp 413–414
Lampinen J, Zelinka I (2000) On stagnation of the differential evolution algorithm. In: Oŝmera P (ed) Proceedings of 6th international mendel conference on soft computing, pp 76–83
Liu Y, Zhao Q (2001) Scaling up fast evolutionary programming with cooperative coevolution. In: Proceedings of the IEEE congress on evolutionary computation, pp 1101–1108
Marchiori E, Steenbeek A (2000) An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling. In: Scheduling, in real world applications of evolutionary computing. Lecture notes in computer science. Springer, Berlin, pp 367–381
Moscato P, Norman M (1989) A competitive and cooperative approach to complex combinatorial search. Techniacl report, 790
Neri F, Tirronen V (2009) Scale factor local search in differential evolution. Memetic Comput J 1(2):153–171
Neri F, Tirronen V (2010) Recent advances in differential evolution: a review and experimental analysis. Artif Intell Rev 33(1):61–106
Noman N, Iba H (2005) Enhancing differential evolution performance with local search for high dimensional function optimization. In: Proceedings of the 2005 conference on genetic and evolutionary computation. ACM, pp 967–974
Noman N, Iba H (2008) Accelerating differential evolution using an adaptive local search. IEEE Trans Evol Comput 12(1):107–125
Olorunda O, Engelbrecht A (2007) Differential evolution in high-dimensional search spaces. In: Proceedings of the IEEE congress on evolutionary computation, pp 1934–1941
Ong YS, Keane AJ (2004) Meta-lamarkian learning in memetic algorithms. IEEE Trans Evol Comput 8(2):99–110
Potter MA, De Jong KA (1994) A cooperative coevolutionary approach to function optimization. In: Proceedings of the third conference on parallel problem solving from nature. Springer, Berlin, pp 249–257
Potter MA, De Jong K (2000) Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evol Comput 8(1):1–29
Rahnamayan S, Wang GG (2008) Solving large scale optimization problems by opposition-based differential evolution (ode). WSEAS Trans Comput 7(10):1792–1804
Rahnamayan S, Tizhoosh HR, Salama MM (2008) Opposition-based differential evolution. IEEE Trans Evol Comput 12(1):64–79
Sofge D, De Jong K, Schultz A (2002) A blended population approach to cooperative coevolution fordecomposition of complex problems. In: Proceedings of the IEEE congress on evolutionary computation, pp 413–418
Shi Y-J, Teng H-F, Li Z-Q (2005) Cooperative co-evolutionary differential evolution for function optimization. In: Advances in natural computation, vol 3611. Lecture notes in computer science. Springer, Berlin, pp 1080–1088
Tasoulis DK, Pavlidis NG, Plagianakos VP, Vrahatis MN (2004) Parallel differential evolution. In: Proceedings of the IEEE congress on evolutionary computation, pp 2023–2029
van den Bergh F, Engelbrecht AP (2004) A cooperative approach to particle swarm optimization. IEEE Trans Evol Comput 8(3):225–239
Weber M, Neri F, Tirronen V (2010a) Distributed differential evolution with explorative-exploitative population families. Genetic Program Evolvable Mach 10(4):343–371
Weber M, Tirronen V, Neri F (2010b) Scale factor inheritance mechanism in distributed differential evolution. Soft Comput Fusion Found Methodol Appl 14(11):1187–1207
Wilcoxon F (1945) Individual comparisons by ranking methods. Biometrics Bull 1(6):80–83
Yang Z, Tang K, Yao X (2007) Differential evolution for high-dimensional function optimization. In: Proceedings of the IEEE congress on evolutionary computation, pp 3523–3530
Yang Z, Tang K, Yao X (2008) Large scale evolutionary optimization using cooperative coevolution. Inf Sci 178(15):2985–2999
Zamuda A, Brest J, Bošković B, Žumer V (2008) Large scale global optimization using differential evolution with self-adaptation and cooperative co-evolution. In: Proceedings of the IEEE world congress on computational intelligence, pp 3719–3726
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by the Academy of Finland, Akatemiatutkija 130600, Algorithmic Design Issues in Memetic Computing.
Rights and permissions
About this article
Cite this article
Weber, M., Neri, F. & Tirronen, V. Shuffle or update parallel differential evolution for large-scale optimization. Soft Comput 15, 2089–2107 (2011). https://doi.org/10.1007/s00500-010-0640-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-010-0640-9