article

Distributed differential evolution with explorative---exploitative population families

Authors:

Matthieu Weber,

Ville TirronenAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 10, Issue 4

Pages 343 - 371

https://doi.org/10.1007/s10710-009-9089-y

Published: 01 December 2009 Publication History

Abstract

This paper proposes a novel distributed differential evolution algorithm, namely Distributed Differential Evolution with Explorative---Exploitative Population Families (DDE-EEPF). In DDE-EEPF the sub-populations are grouped into two families. Sub-populations belonging to the first family have constant population size, are arranged according to a ring topology and employ a migration mechanism acting on the individuals with the best performance. This first family of sub-populations has the role of exploring the decision space and constituting an external evolutionary framework. The second family is composed of sub-populations with a dynamic population size: the size is progressively reduced. The sub-populations belonging to the second family are highly exploitative and are supposed to quickly detect solutions with a high performance. The solutions generated by the second family then migrate to the first family. In order to verify its viability and effectiveness, the DDE-EEPF has been run on a set of various test problems and compared to four distributed differential evolution algorithms. Numerical results show that the proposed algorithm is efficient for most of the analyzed problems, and outperforms, on average, all the other algorithms considered in this study.

References

[1]

E. Alba, B. Dorronsoro, The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans. Evol. Comput. 9(2), 126-142 (2005).

Digital Library

[2]

E. Alba, S. Khuri, Sequential and distributed evolutionary algorithms for combinatorial optimization problems, in Recent Advances in Intelligent Paradigms and Applications, Studies in Fuzziness and Soft Computing (Springer, New York, 2003), pp. 211-233.

[3]

E. Alba, M. Tomassini. Parallelism and evolutionary algorithms. IEEE Trans. Evolu. Comput. 6(5), 443-462 (2002).

Digital Library

[4]

E. Alba, J.M. Troya, A survey of parallel distributed genetic algorithms. Complexity 4(4), 31-52 (1999).

Digital Library

[5]

E. Alba, J.M. Troya, Cellular evolutionary algorithms: evaluating the influence of ratio, in Parallel Problem Solving from Nature, vol 1917 of Lecture Notes in Computer Science (Springer, New York, 2000), pp. 29-38.

[6]

J. Apolloni, G. Leguizamón, J. García-Nieto, E. Alba, 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 (2008).

Digital Library

[7]

M.G. Arenas, P. Collet, A.E. Eiben, M. Jelasity, J.J. Merelo, B. Paechter, M. Preuß, M. Schoenauer, A framework for distributed evolutionary algorithms, in Parallel Problem Solving from Nature, vol 2439 of Lecture Notes in Computer Science (Springer, New York, 2002), pp. 665-675.

[8]

T.C. Belding, The distributed genetic algorithm revisited, in Proceedings of the International Conference on Genetic Algorithms (Morgan Kaufmann Publishers, 1995), pp. 114-121.

[9]

J. Brest, M.S. Mau¿ec, Population size reduction for the differential evolution algorithm. Appl. Intell. 29(3), 228-247 (2008).

Digital Library

[10]

E. Cantú-Paz, A survey of parallel genetic algorithms. Technical Report 97003, IlliGAL (1997).

[11]

E. Cantú-Paz, A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systems Repartis. 10(2), 141-171 (1998).

[12]

E. Cantú-Paz, Topologies, migration rates, and multi-population parallel genetic algorithms, in Proceedings of the Genetic and Evolutionary Computation Conference, pp. 91-98 (1999).

[13]

E. Cantú-Paz, Efficient and Accurate Parallel Genetic Algorithms (Kluwer Academic Publishers, 2000).

[14]

E. Cantú-Paz. Migration policies, selection pressure, and parallel evolutionary algorithms. J. Heuristics. 7(4), 311-334 (2001).

Digital Library

[15]

U.K. Chakraborty (ed.), Advances in Differential Evolution, vol 143 of Studies in Computational Intelligence (Springer, New York, 2008).

[16]

A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computation (Springer, Berlin, 2003).

[17]

I. De Falco, A. Della Cioppa, D. Maisto, U. Scafuri, E. Tarantino, Satellite image registration by distributed differential evolution, in Applications of Evolutionary Computing, vol 4448 of Lectures Notes in Computer Science (Springer, New York, 2007), pp. 251-260.

[18]

I. De Falco, D. Maisto, U. Scafuri, E. Tarantino, A. Della Cioppa, Distributed differential evolution for the registration of remotely sensed images, in Proceedings of the IEEE Euromicro International Conference on Parallel, Distributed and Network-Based Processing, pp. 358-362 (2007).

Digital Library

[19]

I. De Falco, U. Scafuri, E. Tarantino, A. Della Cioppa, A distributed differential evolution approach for mapping in a grid environment, in Proceedings of the IEEE Euromicro International Conference on Parallel, Distributed and Network-Based Processing, pp. 442-449 (2007).

[20]

H.-Y. Fan, J. Lampinen, A trigonometric mutation operation to differential evolution. J. Global Optim. 27(1):105-129 (2003).

[21]

V. Feoktistov, Differential Evolution in Search of Solutions (Springer, New York, 2006).

[22]

F. Fernández, M. Tomassini, L. Vanneschi, An empirical study of multipopulation genetic programming. Genet. Program. Evol. Mach. 4(1), 21-52 (2003).

[23]

F. Fernández, M. Tomassini, L. Vanneschi, Saving computational effort in genetic programming by means of plagues, in it Proceedings of the IEEE Congress on Evolutionary Computation, pp. 2042- 2049 (2003).

[24]

M. Giacobini, E. Alba, A. Tettamanzi, M. Tomassini, Modeling selection intensity for toroidal cellular evolutionary algorithms, in Genetic and Evolutionary Computation, vol 3102 of Lecture Notes in Computer Science (Springer, 2004), pp. 1138-1149.

[25]

M. Giacobini, E. Alba, M. Tomassini, Selection intensity in asynchronous cellular evolutionary algorithms, in Genetic and Evolutionary Computation, vol 2723 of Lecture Notes in Computer Science, ed. by E. Cantú-Paz et al. (Springer, New York, 2003), pp. 955-966.

[26]

M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba, Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Trans. Evol. Comput. 9(5), 489-505 (2005).

Digital Library

[27]

J. Grefenstette, Parallel adaptive algorithms for function optimization. Technical Report CS-81-19, Vanderbilt University (1981).

[28]

R. Joshi, A.C., Sanderson. Minimal representation multisensor fusion using differential evolution. IEEE Trans. Syst. Man Cybern. Part A 29(1), 63-76 (1999).

Digital Library

[29]

K.N. Kozlov, A.M. Samsonov, New migration scheme for parallel differential evolution, in Proceedings of the International Conference on Bioinformatics of Genome Regulation and Structure, pp. 141-144 (2006).

[30]

W. Kwedlo, K. Bandurski, A parallel differential evolution algorithm, in Proceedings of the IEEE International Symposium on Parallel Computing in Electrical Engineering, pp. 319-324 (2006).

[31]

J. Lampinen, Differential evolution--new naturally parallel approach for engineering design optimization, in Developments in Computational Mechanics with High Performance Computing, ed. by B.H. Topping (Civil-Comp Press, 1999), pp. 217-228.

[32]

J. Lampinen, I. Zelinka. On stagnation of the differential evolution algorithm, in Proceedings of 6th International Mendel Conference on Soft Computing, ed. by P. O'mera pp. 76-83 (2000).

[33]

P. Moscato, M. Norman, A competitive and cooperative approach to complex combinatorial search. Technical Report 790 (1989).

[34]

H. Mühlenbein, M. Schomisch, J. Born, The parallel genetic algorithm as function optimizer. Parallel Comput. 17(6-7), 619-632 (1991).

Digital Library

[35]

F. Neri, V. Tirronen, On memetic differential evolution frameworks: a study of advantages and limitations in hybridization, in Proceedings of the IEEE World Congress on Computational Intelligence, pp. 2135-2142 (2008).

[36]

M.S. Nipteni, I. Valakos, I. Nikolos, An asynchronous parallel differential evolution algorithm, in Proceedings of the ERCOFTAC Conference on Design Optimisation: Methods and Application (2006).

[37]

NIST/SEMATECH. e-handbook of statistical methods. http://www.itl.nist.gov/div898/handbook/, (2003).

[38]

M. Nowostawski, R. Poli, Parallel genetic algorithm taxonomy, in Proceedings of the International Conference on Knowledge-Based Intelligent Information Engineering Systems, pp. 88-92 (1999).

[39]

N.G. Pavlidis, D.K. Tasoulis, V.P. Plagianakos, G. Nikiforidis, M.N. Vrahatis, Spiking neural network training using evolutionary algorithms, in Proceedings of the IEEE International Joint Conference on Neural Networks, pp. 2190-2194 (2005).

[40]

V.P. Plagianakos, D.K. Tasoulis, M.N. Vrahatis, A review of major application areas of differential evolution, in Advances in Differential Evolution, vol 143 of Studies in Computational Intelligence, ed. by U.K. Chakraborty (Springer, New York, 2008), pp. 197-238.

[41]

K.V. Price, Mechanical engineering design optimization by differential evolution, in New Ideas in Optimization, ed. by D. Corne, M. Dorigo, F. Glover (McGraw-Hill, 1999), pp. 293-298.

[42]

K.V. Price, R. Storn, J. Lampinen, Differential Evolution: A Practical Approach to Global Optimization (Springer, New York, 2005).

[43]

W. Punch, E. Goodman, M. Pei, L. Chain-Shun, P. Hovland, R. Enbody, Further research on feature selection and classification using genetic algorithms, in Proceedings of the International Conference on Genetic Algorithms, ed. by S. Forrest (Morgan Kaufmann, 1993), pp. 557-564.

[44]

A.K. Qin, P.N. Suganthan. Self-adaptive differential evolution algorithm for numerical optimization, in Proceedings of the IEEE Congress on Evolutionary Computation, vol 2, pp. 1785-1791 (2005).

[45]

I. Rechemberg, Evolutionstrategie: Optimierung Technisher Systeme nach prinzipien des Biologishen Evolution (Fromman-Hozlboog Verlag, 1973).

[46]

G. Rudolph, Global optimization by means of distributed evolution strategies, in Parallel Problem Solving from Nature, vol 496 of Lecture Notes in Computer Science (Springer, New York, 1991), pp. 209-213.

[47]

G.D. Ruxton, The unequal variance t-test is an underused alternative to Student's t-test and the Mann-Whitney test. Behav. Ecol. 17(4), 688-690 (2006).

[48]

M. Salomon, G.-R. Perrin, F. Heitz, J.-P. Armspach, Parallel differential evolution: application to 3-d medical image registration, in Differential Evolution--A Practical Approach to Global Optimization, Natural Computing Series, chapter 7, ed. by K.V. Price, R.M. Storn, J.A. Lampinen (Springer, New York, 2005), pp. 353-411.

[49]

R. Storn, System design by constraint adaptation and differential evolution. IEEE Trans. Evol. Comput. 3(1), 22-34 (1999).

Digital Library

[50]

R. Storn, Designing nonstandard filters with differential evolution. IEEE Signal Process. Mag. 22(1), 103-106 (2005).

[51]

R. Storn, K. Price, Differential evolution--a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical Report TR-95-012, ICSI (1995).

[52]

R. Storn, K. Price, Differential evolution--a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11, 341-359 (1997).

[53]

D.K. Tasoulis, N.G. Pavlidis, V.P. Plagianakos, M.N. Vrahatis, Parallel differential evolution, in Proceedings of the IEEE Congress on Evolutionary Computation, pp. 2023-2029 (2004).

[54]

V. Tirronen, F. Neri, T. Kärkkäinen, K. Majava, T. Rossi, A memetic differential evolution in filter design for defect detection in paper production, in Applications of Evolutionary Computing, vol 4448 (Springer, Berlin, 2007), pp. 320-329.

[55]

V. Tirronen, F. Neri, T. Kärkkäinen, K. Majava, T. Rossi, An enhanced memetic differential evolution in filter design for defect detection in paper production. Evol. Comput. 16, 529-555 (2008).

Digital Library

[56]

M. Tomassini, Parallel and distributed evolutionary algorithms: a review, in Evolutionary Algorithms in Engineering and Computer Science- Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications, ed. by K. Miettinen, M.M. Mäkelä, P. Neittaanmäki, J. Périaux (Wiley, New York, 1999).

[57]

M. Tomassini, L. Vanneschi, J. Cuendet, F. Fernández, A new technique for dynamic size populations in genetic programming. in Proceedings of the IEEE Congress on Evolutionary Computation, pp. 486-493 (2004).

[58]

D. Whitley, Cellular genetic algorithms, in Proceedings of the International Conference on Genetic Algorithms, ed. by S. Forrest (1993), p. 658.

[59]

D. Zaharie, Parameter adaptation in differential evolution by controlling the population diversity, in Proceedings of the International Workshop on Symbolic and Numeric Algorithms for Scientific Computing, ed. by D. Petcu et al. (2002), pp. 385-397.

[60]

D. Zaharie, Control of population diversity and adaptation in differential evolution algorithms, in Proceedings of MENDEL International Conference on Soft Computing, ed. by D.Matousek, P. Osmera (2003), pp. 41-46.

[61]

D. Zaharie, A multipopulation differential evolution algorithm for multimodal optimization, in Proceedings of Mendel International Conference on Soft Computing, ed. by R. Matousek, P. Osmera (2004), pp. 17-22.

[62]

D. Zaharie, G. Ciobanu. Distributed evolutionary algorithms inspired by membranes in solving continuous optimization problems. in Membrane Computing, vol 4361 of Lecture Notes in Computer Science (Springer, New York, 2006), pp. 536-553.

[63]

D. Zaharie, D. Petcu. Parallel implementation of multi-population differential evolution, in Proceedings of the NATO Advanced Research Workshop on Concurrent Information Processing and Computing (IOS Press, 2003), pp. 223-232.

[64]

K. Zielinski, R. Laur, Stopping criteria for differential evolution in constrained single-objective optimization, in Advances in Differential Evolution, vol, 143 of Studies in Computational Intelligence, ed. by U.K. Chakraborty (Springer, New York, 2008), pp. 111-138.

[65]

K. Zielinski, P. Weitkemper, R. Laur, K.-D. Kammeyer, Parameter study for differential evolution using a power allocation problem including interference cancellation, in Proceedings of the IEEE Congress on Evolutionary Computation, pp. 1857-1864 (2006).

Cited By

Abbasi BMajidnezhad VMirjalili S(2024)ADE: advanced differential evolutionNeural Computing and Applications10.1007/s00521-024-09669-z36:25(15407-15438)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00521-024-09669-z
Kitamura TFukunaga A(2022)Differential Evolution with an Unbounded Population2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870363(1-8)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870363
Zhan ZShi LTan KZhang J(2022)A survey on evolutionary computation for complex continuous optimizationArtificial Intelligence Review10.1007/s10462-021-10042-y55:1(59-110)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10462-021-10042-y
Show More Cited By

Distributed differential evolution with explorative---exploitative population families
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Population size reduction for the differential evolution algorithm

This paper studies the efficiency of a recently defined population-based direct global optimization method called Differential Evolution with self-adaptive control parameters. The original version uses fixed population size but a method for gradually ...
Multi-population differential evolution with adaptive parameter control for global optimization
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Differential evolution (DE) is one of the most successful evolutionary algorithms (EAs) for global numerical optimization. Like other EAs, maintaining population diversity is important for DE to escape from local optima and locate a near-global optimum. ...
An improved adaptive differential evolution algorithm with population adaptation
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

In differential evolution (DE), there are many adaptive algorithms proposed for parameters adaptation. However, they mainly aim at tuning the amplification factor F and crossover probability CR. When the population diversity is at a low level or the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 10, Issue 4

December 2009

131 pages

ISSN:1389-2576

Issue’s Table of Contents

Copyright © Copyright © 2009 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abbasi BMajidnezhad VMirjalili S(2024)ADE: advanced differential evolutionNeural Computing and Applications10.1007/s00521-024-09669-z36:25(15407-15438)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00521-024-09669-z
Kitamura TFukunaga A(2022)Differential Evolution with an Unbounded Population2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870363(1-8)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870363
Zhan ZShi LTan KZhang J(2022)A survey on evolutionary computation for complex continuous optimizationArtificial Intelligence Review10.1007/s10462-021-10042-y55:1(59-110)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10462-021-10042-y
Neri FRostami S(2021)Generalised Pattern Search Based on Covariance Matrix DiagonalisationSN Computer Science10.1007/s42979-021-00513-y2:3Online publication date: 25-Mar-2021
https://dl.acm.org/doi/10.1007/s42979-021-00513-y
He ZPeng HChen JDeng CWu Z(2021)A Spark-based differential evolution with grouping topology model for large-scale global optimizationCluster Computing10.1007/s10586-020-03124-z24:1(515-535)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10586-020-03124-z
Ge YYu WZhan ZZhang J(2018)Competition-Based Distributed Differential Evolution2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477758(1-8)Online publication date: 8-Jul-2018
https://dl.acm.org/doi/10.1109/CEC.2018.8477758
(2018)Differential evolution with individual-dependent topology adaptationInformation Sciences: an International Journal10.1016/j.ins.2018.02.048450:C(1-38)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.ins.2018.02.048
Piotrowski ANapiorkowski J(2018)Some metaheuristics should be simplifiedInformation Sciences: an International Journal10.1016/j.ins.2017.10.039427:C(32-62)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.ins.2017.10.039
(2017)SparkCUDEInternational Journal of High Performance Systems Architecture10.5555/3270816.32708217:4(211-222)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3270816.3270821
Villarreal-Cervantes M(2017)Approximate and Widespread Pareto Solutions in the Structure-Control Design of Mechatronic SystemsJournal of Optimization Theory and Applications10.1007/s10957-016-1053-4173:2(628-657)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s10957-016-1053-4
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents