nach oben

Cluster Computing

Erschienen in:

01.06.2014

Enhancing distributed EAs by a proactive strategy

verfasst von: Carolina Salto, Francisco Luna, Enrique Alba

Erschienen in: Cluster Computing | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this work we propose a new distributed evolutionary algorithm that uses a proactive strategy to adapt its migration policy and the mutation rate. The proactive decision is carried out locally in each subpopulation based on the entropy of that subpopulation. In that way, each subpopulation can change their own incoming flow of individuals by asking their neighbors for more frequent or less frequent migrations in order to maintain the genetic diversity at a desired level. Moreover, this proactive strategy is reinforced by adapting the mutation rate while the algorithm is searching for the problem solution. All these strategies avoid the subpopulations to get trapped into local minima. We conduct computational experiments on large instances of the NK landscape problem which have shown that our proactive approach outperforms traditional dEAs, particularly for not highly rugged landscapes, in which it does not only reaches the most accurate solutions, but it does the fastest.

Vorheriger Artikel Solving the three dimensional quadratic assignment problem on a computational grid

Nächster Artikel A general purpose parallel block structured open source incompressible flow solver

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Aguirre, H., Tanaka, K.: A study on the behavior of genetic algorithms on nk-landscapes: effects of selection, drift, mutation, and recombination. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E86-A(9), 2270–2279 (2003)

Alba, E., Dorronsoro, B.: Cellular Genetic Algorithms. Operations Research/Computer Science Interfaces Series, vol. 42. Springer, Berlin (2008) MATH

Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002) CrossRef

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

Alba, E., Troya, J.M.: Analyzing synchronous and asynchronous parallel distributed genetic algorithms. Future Gener. Comput. Syst. 17(4), 451–465 (2001) CrossRefMATH

Araujo, L., Merelo, J.J.: Diversity through multiculturality: assessing migrant choice policies in an island model. IEEE Trans. Evol. Comput. 15(4), 456–469 (2011) CrossRef

Bäck, T.: Self-adaptation in genetic algorithms. In: Proceedings of the First European Conference on Artificial Life, pp. 263–271. MIT Press, Cambridge (1992)

Bäck, T., Fogel, D., Michalewicz, Z.: Handbook of Evolutionary Computation. Oxford University Press, New York (1997) CrossRefMATH

DeJong, K.: An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, Ann Arbor, MI (1975)

10.

Eiben, A., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Trans. Evol. Comput. 3(2), 124–141 (1999) CrossRef

11.

Eiben, A.E., Michalewicz, Z., Schoenauer, M., Smith, J.E.: Parameter control in evolutionary algorithms. In: Studies in Computational Intelligence, vol. 54, pp. 19–46. Springer, Berlin (2007)

12.

Alba, E., et al.: MALLBA: A Library of Skeletons for Combinatorial Optimisation. LNCS, vol. 2400, pp. 927–932. Springer, Berlin (2002)

13.

Gong, X., Xie, J.: Migration strategy and mathematical analysis of sub-population size adaptation in parallel genetic algorithm. In: Medical Imaging, Parallel Processing of Images, and Optimization Techniques, vol. 7497, pp. 1–15 (2009)

14.

Greffenstette, J.J.: Optimization of control parameters for genetic algorithms. IEEE Trans. Syst. Man Cybern. 16(1), 122–128 (1986) CrossRef

15.

Hijaze, M., Corne, D.: Distributed evolutionary algorithm topologies with adaptive migration schemes. In: IEEE Congress on Evolutionary Computation, pp. 608–615 (2011)

16.

Kauffman, S.: The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, London (1993)

17.

Kauffman, S., Levin, S.: Towards a general theory of adaptive walks on rugged landscapes. J. Theor. Biol. 128(1), 11–45 (1987) CrossRefMathSciNet

18.

Kramer, O.: Evolutionary self-adaptation: a survey of operators and strategy parameters. Evol. Intell. 3(2), 51–65 (2010) CrossRefMATH

19.

Kwasnicka, H.: An ensemble of cooperative genetic algorithms as an intelligent search tool. Int. J. Comput. Intell. Res. 3(2), 165–176 (2007) CrossRef

20.

Luque, G., Alba, E.: Parallel Genetic Algorithms: Theory and Real World Applications. Studies in Computational Intelligence, vol. 367. Springer, Berlin (2011)

21.

Michalewicz, M.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd revised edn. Springer, Berlin (1996) CrossRefMATH

22.

Ochoa, G., Harvey, I., Buxton, H.: On recombination and optimal mutation rates. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 488–495 (1999)

23.

Osorio, K., Luque, G., Alba, E.: Distributed evolutionary algorithms with adaptive migration period. In: 2011 11th International Conference on Intelligent Systems Design and Applications (ISDA), pp. 259–264 (2011) CrossRef

24.

Salto, C., Luna, F., Alba, E.: Heterogeneity through proactivity: enhancing distributed EAs. In: 1st International Workshop on Soft Computing Techniques in Cluster and Grid Computing Systems (SCCG), Part of the Seventh International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), pp. 279–284 (2012)

25.

Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423 (1948) and 623–656 CrossRefMATHMathSciNet

26.

Skolicki, Z., De Jong, K.: The influence of migration sizes and intervals on island models. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation (GECCO’2005), pp. 1295–1302 (2005) CrossRef

27.

Spiessens, P., Manderick, B.: A massively parallel genetic algorithm. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 279–286 (1991)

28.

Srinivasa, K.G., Venugopal, K.R., Patnaik, L.M.: A self-adaptive migration model genetic algorithm for data mining applications. Inf. Sci. 177(20), 4295–4313 (2007) CrossRefMATH

29.

Syswerda, G.: Study of reproduction in generational and steady-state genetic algorithms. In: Foundations of Genetic Algorithms, pp. 94–101 (1991)

30.

Tanese, R.: Distributed genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 434–439 (1989)

31.

Tang, J., Lim, M.-H., Ong, Y.-S.: Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput. 11(9), 873–888 (2007) CrossRef

32.

Wang, R., Ru, Y., Long, Q.: Improved adaptive and multi-group parallel genetic algorithm based on good-point set. J. Softw. 4(4), 348–356 (2009)

Titel: Enhancing distributed EAs by a proactive strategy
verfasst von: Carolina Salto
Francisco Luna
Enrique Alba
Publikationsdatum: 01.06.2014
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 2/2014
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-013-0321-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2014

Seamless Paxos coordinators

Service models and pricing schemes for cloud computing

Software quality in the clouds: a cloud-based solution

Architecture and applications for an All-FPGA parallel computer

Reverse computation for rollback-based fault tolerance in large parallel systems

A Coarray Fortran implementation to support data-intensive application development