The grouping differential evolution algorithm for multi-dimensional optimization problems

• Autorzy: Piotrowski A. P. , Napiórkowski J. J.
• Języki publikacji: EN

Abstrakty

EN

A variant of the Differential Evolution method is presented. The classical Differential Evolution approach is very successful for simple problems, but does not perform well enough for troublesome multi-dimensional non-convex continuous functions. To overcome some of the drawbacks, the Grouped Multi-Strategy Differential Evolution algorithm is proposed here. The main idea behind the new approach is to exploit the knowledge about the local minima already found in different parts of the search space in order to facilitate further search for the global one. In the proposed method, the population is split into four groups: three of them rarely communicate with the others, but one is allowed to gain all available knowledge from the whole population throughout the search process. The individuals simultaneously use three different crossover/mutation strategies, which makes the algorithm more flexible. The proposed approach was compared with two Differential Evolution based algorithms on a set of 10- to 100-dimensional test functions of varying difficulty. The proposed method achieved very encouraging results; its advantage was especially significant when more difficult 50- and 100-dimensional problems were considered. When dividing population into separate groups, the total number of individuals becomes a crucial restriction. Hence, the impact of the number of individuals on the performance of the algorithms was studied. It was shown that increasing the number of individuals above the number initially proposed for classic Differential Evolution method is in most cases not advantageous and sometimes may even result in deterioration of results.

Słowa kluczowe

EN

differential evolution; multidimensional problems; multimodal problems; metaheuristics

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2010
• Tom: Vol. 39, no 2
• Strony: 527--550
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Piotrowski A. P.

autor

Napiórkowski J. J.

• Institute of Geophysics, Polish Academy of Sciences, Księcia Janusza 64, 01-452, Warsaw, Poland

Bibliografia

• ADRIO, E.P. (2005) Multivariate Test Functions Library in C for unconstrained global optimization, http://geocities.com/eadorio/mvf.pdf.
• ALI, M.M., KHOMPATRAPORN, C. and ZABINSKY, Z.B. (2005) A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. Journal of Global Optimization 31, 635-672.
• ALI, M.M. (2007) Differential Evolution with preferential crossover. European Journal of Operational Research 181, 1137-1147.
• BREST, J., BOSKOVIC, B., GREINER, S., ZUMER, V. and MAUCEC, M.S. (2007) Performance comparison of Self-Adaptive and Adaptive Differential Evolution algorithms. Soft Computing 11, 7, 617-629.
• CLERC, M. (2006) Particle Swarm Optimization. ISTE Ltd, London.
• DAS, S., ABRAHAM, A., CHAKRABORTY, U.K. and KONAR, A. (2009) Differential Evolution Using a Neighborhood-based Mutation Operator. IEEE Transactions on Evolutionary Computations 13, 3, 526-553.
• GUSTAFSON, S. and BURKE, E.K. (2006) The Speciating Island Model: An alternative parallel evolutionary algorithm. Journal of Parallel and Distributed Computing 66 (8), 1025-1036.
• HEDDAR, A.R. and FUKUSHIMA, M. (2006) Tabu Search directed by direct search methods for nonlinear global optimization. European Journal of Operational Research 170, 329-349.
• HOLLAND, J.H. (2000) Building blocks, cohort genetic algorithms and hyperplane - defined functions. Evolutionary Computation 8 (4), 373-391.
• ILONEN, J., KAMARAINEN, J.K. and LAMPINEN, J. (2003) Differential Evolution training algorithm for feed-foreward neural networks. Neural Processing Letters 17, 93-105.
• KAELO, P. and ALI, M.M. (2006) A numerical study of some modified Differtential Evolution algorithms. European Journal of Operational Research 169, 1176-1184.
• LIU, J. and LAMPINEN, J. (2005) A Fuzzy Adaptive Differential Evolution algorithm. Soft Computing 9, 448-462.
• LIU, Y., YAO, X. and HIGRUCHI, T. (2000) Evolutionary ensembles with negative correlation learning. IEEE Transactions on Evolutionary Computation 4 (4), 380-387.
• MISHRA, S.K. (2006) Global optimization by Differential Evolution and Particle Swarm methods evaluation on some benchmark functions. Social Science Research Network, Working Papers Series, http://ssrn.com/ abstract=933827.
• PRICE, K.V., STORN, R.M. and LAMPINEN, J.A. (2005) Differential Evolution. A Practical Approach to Global Optimization. Springer-Verlag, Berlin-Heidelberg.
• QIN, A.K., HUANG, V.L. and SUGANTHAN, P.N. (2009) Differential Evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions Evolutionary Computation 13 (2), 398-417.
• ROWINSKI, P.M. and PIOTROWSKI, A. (2008) Estimation of parameters of transient storage model by means of multi-layer perceptron neural networks. Hydrological Sciences Journal 53 (1), 165-178.
• STORN, R. and PRICE, K.V. (1995) Differential Evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical Report TR-95-012, International Computer Sciences Institute, Berkeley, CA, USA .
• STORN, R. and PRICE, K.V. (1997) Differential Evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11 (1), 341-359.
• WANG, Y.J. and ZHANG, J.S. (2007) Global optimization by an improved Differential Evolutionary algorithm. Applied Mathematics and Computation 188, 669-680.
• WHITLEY, D., RANA, S., DZUBERA, J. and MATHIAS, K.E. (1996) Evaluating evolutionary algorithms. Artificial Intelligence 85, 245-276.
• WHITLEY, D., LUNACEK, M. and KNIGHT, J. (2004) Ruffled by Ridges: How Evolutionary Algorithms Can Fail. In: LNCS 3103, Springer, Berlin-Heidelberg.
• TAO, J. and WANG, N. (2007) DNA computing based RNA genetic algorithm with applications in parameter estimation of chemical engineering processes. Computers and Chemical Engineering 31, 1602-1618.