Skip to main content
Erschienen in: Evolutionary Intelligence 3/2009

01.12.2009 | Research Paper

A study on diversity for cluster geometry optimization

verfasst von: Francisco B. Pereira, Jorge M. C. Marques

Erschienen in: Evolutionary Intelligence | Ausgabe 3/2009

Einloggen

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

search-config
loading …

Abstract

Diversity is a key issue to consider when designing evolutionary approaches for difficult optimization problems. In this paper, we address the development of an effective hybrid algorithm for cluster geometry optimization. The proposed approach combines a steady-state evolutionary algorithm and a straightforward local method that uses derivative information to guide search into the nearest local optimum. The optimization method incorporates a mechanism to ensure that the diversity of the population does not drop below a pre-specified threshold. Three alternative distance measures to estimate the dissimilarity between solutions are evaluated. Results show that diversity is crucial to increase the effectiveness of the hybrid evolutionary algorithm, as it enables it to discover all putative global optima for Morse clusters up to 80 atoms. A comprehensive analysis is presented to gain insight about the most important strengths and weaknesses of the proposed approach. The study shows why distance measures that consider structural information for estimating the dissimilarity between solutions are more suited to this problem than those that take into account fitness values. A detailed explanation for this differentiation is provided.

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat Braier P, Berry R, Wales D (1990) How the range of pair interactions govern features of multidimensional potentials. J Chem Phys 93(12):8745–8756CrossRef Braier P, Berry R, Wales D (1990) How the range of pair interactions govern features of multidimensional potentials. J Chem Phys 93(12):8745–8756CrossRef
2.
Zurück zum Zitat Burke EK, Gustafson S, Kendall G, Krasnogor N (2002) Advanced population diversity measures in genetic programming. In: 7th International conference parallel problem solving from nature (PPSN-2002), vol 2439. Springer Lecture Notes in Computer Science. Springer, Heidelberg, pp 341–350 Burke EK, Gustafson S, Kendall G, Krasnogor N (2002) Advanced population diversity measures in genetic programming. In: 7th International conference parallel problem solving from nature (PPSN-2002), vol 2439. Springer Lecture Notes in Computer Science. Springer, Heidelberg, pp 341–350
3.
Zurück zum Zitat Cassioli A, Locatelli M, Schoen F (2008) Dissimilarity measures for population-based global optimization algorithms. Comput Optim Appl, online July 2008. doi:10.1007/s10589-008-9194-5 Cassioli A, Locatelli M, Schoen F (2008) Dissimilarity measures for population-based global optimization algorithms. Comput Optim Appl, online July 2008. doi:10.​1007/​s10589-008-9194-5
5.
Zurück zum Zitat Cheng L, Cai W, Shao X (2004) A connectivity table for cluster similarity checking in the evolutionary optimization method. Chem Phys Lett 389:309–314CrossRef Cheng L, Cai W, Shao X (2004) A connectivity table for cluster similarity checking in the evolutionary optimization method. Chem Phys Lett 389:309–314CrossRef
6.
Zurück zum Zitat Cheng L, Yang J (2007) Global minimum structures of morse clusters as a function of the range of the potential: 81 ≤ n ≤ 160. J Phys Chem A 111:5287–5293CrossRef Cheng L, Yang J (2007) Global minimum structures of morse clusters as a function of the range of the potential: 81 ≤  n ≤  160. J Phys Chem A 111:5287–5293CrossRef
7.
Zurück zum Zitat Deaven D, Ho K (1995) Molecular geometry optimization with a genetic algorithm. Phys Rev Lett 75:288–291CrossRef Deaven D, Ho K (1995) Molecular geometry optimization with a genetic algorithm. Phys Rev Lett 75:288–291CrossRef
8.
Zurück zum Zitat Demsar J (2006) Statistical comparisons of classifiers over multiples data sets. J Mach Learn Res 7:1–30MathSciNet Demsar J (2006) Statistical comparisons of classifiers over multiples data sets. J Mach Learn Res 7:1–30MathSciNet
9.
Zurück zum Zitat Doye JPK (2006) Physical perspectives on the global optimization of atomic clusters. In: Global optimization: scientific and engineering case studies. Springer, Heidelberg, pp 103–139 Doye JPK (2006) Physical perspectives on the global optimization of atomic clusters. In: Global optimization: scientific and engineering case studies. Springer, Heidelberg, pp 103–139
10.
Zurück zum Zitat Doye JPK, Leary R, Locatelli M, Schoen F (2004) Global optimization of morse clusters by potential energy transformations. Informs J Comput 16:371–379CrossRef Doye JPK, Leary R, Locatelli M, Schoen F (2004) Global optimization of morse clusters by potential energy transformations. Informs J Comput 16:371–379CrossRef
11.
Zurück zum Zitat Doye JPK, Wales DJ (1997) Structural consequences of the range of the interatomic potential. A menagerie of clusters. J Chem Soc Faraday Trans 93:4233–4243CrossRef Doye JPK, Wales DJ (1997) Structural consequences of the range of the interatomic potential. A menagerie of clusters. J Chem Soc Faraday Trans 93:4233–4243CrossRef
12.
Zurück zum Zitat Goldberg D, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of genetic algorithms, pp 69–93 Goldberg D, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of genetic algorithms, pp 69–93
13.
Zurück zum Zitat Grigoryan V, Alamanova D, Springborg M (2005) Structure and energetics of nickel, copper, and gold clusters. Eur Phys J D 34:187–190CrossRef Grigoryan V, Alamanova D, Springborg M (2005) Structure and energetics of nickel, copper, and gold clusters. Eur Phys J D 34:187–190CrossRef
14.
Zurück zum Zitat Grosso A, Locatelli M, Schoen F (2007) A population-based approach for hard global optimization problems based on dissimilarity measures. Math Program Ser A 110:373–404MATHCrossRefMathSciNet Grosso A, Locatelli M, Schoen F (2007) A population-based approach for hard global optimization problems based on dissimilarity measures. Math Program Ser A 110:373–404MATHCrossRefMathSciNet
15.
Zurück zum Zitat Hart W, Krasnogor N, Smith J (2004) Recent advances in memetic algorithms, volume 166 of Studies in fuzziness and soft computing, chapter Memetic evolutionary algorithms. Springer, Heidelberg, pp 3–27 Hart W, Krasnogor N, Smith J (2004) Recent advances in memetic algorithms, volume 166 of Studies in fuzziness and soft computing, chapter Memetic evolutionary algorithms. Springer, Heidelberg, pp 3–27
16.
Zurück zum Zitat Hartke B (1993) Global geometry optimization of clusters using genetic algorithms. J Phys Chem 97:9973–9976CrossRef Hartke B (1993) Global geometry optimization of clusters using genetic algorithms. J Phys Chem 97:9973–9976CrossRef
17.
Zurück zum Zitat Hartke B (1999) Global cluster geometry optimization by a phenotype algorithm with niches: location of elusive minima, and low-order scaling with cluster size. J Comput Chem 20(16):1752–1759CrossRef Hartke B (1999) Global cluster geometry optimization by a phenotype algorithm with niches: location of elusive minima, and low-order scaling with cluster size. J Comput Chem 20(16):1752–1759CrossRef
18.
Zurück zum Zitat Hartke B (2001) Global geometry optimization of atomic and molecular clusters by genetic algorithms. In: Proceedings of the genetic and evolutionary computation conference (GECCO-2001). Morgan Kaufmann, San Francisco, pp 1284–1291 Hartke B (2001) Global geometry optimization of atomic and molecular clusters by genetic algorithms. In: Proceedings of the genetic and evolutionary computation conference (GECCO-2001). Morgan Kaufmann, San Francisco, pp 1284–1291
19.
Zurück zum Zitat Hartke B (2004) Application of evolutionary algorithms to global cluster geometry optimization. In: Applications of evolutionary computation in chemistry. Structure and Bonding. Springer, Heidelberg, pp 33–53 Hartke B (2004) Application of evolutionary algorithms to global cluster geometry optimization. In: Applications of evolutionary computation in chemistry. Structure and Bonding. Springer, Heidelberg, pp 33–53
20.
Zurück zum Zitat Johnston RL (2003) Evolving better nanoparticles: genetic algorithms for optimising cluster geometries. Dalton Trans 22:4193–4207CrossRef Johnston RL (2003) Evolving better nanoparticles: genetic algorithms for optimising cluster geometries. Dalton Trans 22:4193–4207CrossRef
21.
Zurück zum Zitat Jones JE (1924) On the determination of molecular fields. ii. From the equation of state of a gas. Proc R Soc A 106:463–477CrossRef Jones JE (1924) On the determination of molecular fields. ii. From the equation of state of a gas. Proc R Soc A 106:463–477CrossRef
22.
Zurück zum Zitat De Jong K (1975) An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, Un. Michigan De Jong K (1975) An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, Un. Michigan
23.
Zurück zum Zitat De Jong K, Sarma J (1993) Generation gaps revisited. In: Foundations of genetic algorithms, vol 2, pp 19–28 De Jong K, Sarma J (1993) Generation gaps revisited. In: Foundations of genetic algorithms, vol 2, pp 19–28
24.
Zurück zum Zitat Krasnogor N (2004) Recent advances in memetic algorithms, volume 166 of Studies in fuzziness and soft computing, chapter Towards robust memetic algorithms. Springer, Heidelberg, pp 185–207 Krasnogor N (2004) Recent advances in memetic algorithms, volume 166 of Studies in fuzziness and soft computing, chapter Towards robust memetic algorithms. Springer, Heidelberg, pp 185–207
25.
Zurück zum Zitat Krasnogor N, Blackburnem B, Hirst JD, Burke EK (2002) Multimeme algorithms for protein structure prediction. In: 7th International conference parallel problem solving from nature (PPSN-2002). Springer, Heidelberg, pp 769–778 Krasnogor N, Blackburnem B, Hirst JD, Burke EK (2002) Multimeme algorithms for protein structure prediction. In: 7th International conference parallel problem solving from nature (PPSN-2002). Springer, Heidelberg, pp 769–778
26.
Zurück zum Zitat Lee J, Lee I-H, Lee J (2003) Unbiased global optimization of Lennard-Jones clusters for n ≤ 201 by conformational space annealing method. Phys Rev Lett 91(8):080201.1–080201.4 Lee J, Lee I-H, Lee J (2003) Unbiased global optimization of Lennard-Jones clusters for n ≤ 201 by conformational space annealing method. Phys Rev Lett 91(8):080201.1–080201.4
29.
30.
Zurück zum Zitat Locatelli M, Schoen F (2003) Efficient algorithms for large scale global optimization: Lennard-Jones clusters. Comput Optim Appl 26:173–190MATHCrossRefMathSciNet Locatelli M, Schoen F (2003) Efficient algorithms for large scale global optimization: Lennard-Jones clusters. Comput Optim Appl 26:173–190MATHCrossRefMathSciNet
31.
Zurück zum Zitat Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded memetic algorithms with crossover hill-climbing. Evol Comput 12:273–302CrossRef Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded memetic algorithms with crossover hill-climbing. Evol Comput 12:273–302CrossRef
32.
Zurück zum Zitat Mattiussi C, Waibel M, Floreano D (2004) Measures of diversity for populations and distances between individuals with highly reorganizable genomes. Evol Comput 12(4):495–515CrossRef Mattiussi C, Waibel M, Floreano D (2004) Measures of diversity for populations and distances between individuals with highly reorganizable genomes. Evol Comput 12(4):495–515CrossRef
33.
Zurück zum Zitat Morse P (1929) Diatomic molecules according to the wave mechanics. ii. Vibrational levels. Phys Rev 34:57–64CrossRef Morse P (1929) Diatomic molecules according to the wave mechanics. ii. Vibrational levels. Phys Rev 34:57–64CrossRef
34.
Zurück zum Zitat Pelta D, Krasnogor N (2004) Recent advances in memetic algorithms, volume 166 of Studies in fuzziness and soft computing, chapter Multimeme algorithms using fuzzy logic based memes for protein structure prediction. Springer, Heidelberg, pp 49–64 Pelta D, Krasnogor N (2004) Recent advances in memetic algorithms, volume 166 of Studies in fuzziness and soft computing, chapter Multimeme algorithms using fuzzy logic based memes for protein structure prediction. Springer, Heidelberg, pp 49–64
35.
Zurück zum Zitat Pereira FB, Marques JMC (2008) A self-adaptive evolutionary algorithm for cluster geometry optimization. In: Proceedings of the eight international conference on hybrid intelligent systems. IEEE Press, New York, pp 678–683 Pereira FB, Marques JMC (2008) A self-adaptive evolutionary algorithm for cluster geometry optimization. In: Proceedings of the eight international conference on hybrid intelligent systems. IEEE Press, New York, pp 678–683
36.
Zurück zum Zitat Pereira FB, Marques JMC, Leitao T, Tavares J (2006) Analysis of locality in hybrid evolutionary cluster optimization. In: Proceedings of the IEEE congress on evolutionary computation, vols 1–6. IEEE-Press, New York, pp 2270–2277 Pereira FB, Marques JMC, Leitao T, Tavares J (2006) Analysis of locality in hybrid evolutionary cluster optimization. In: Proceedings of the IEEE congress on evolutionary computation, vols 1–6. IEEE-Press, New York, pp 2270–2277
37.
Zurück zum Zitat Pereira FB, Marques JMC, Leitao T, Tavares J (2008) Efficient evolutionary algorithms for cluster optimization: a study on locality. In: Advances in metaheuristics for hard optimization. Springer, Heidelberg, pp 223–250 Pereira FB, Marques JMC, Leitao T, Tavares J (2008) Efficient evolutionary algorithms for cluster optimization: a study on locality. In: Advances in metaheuristics for hard optimization. Springer, Heidelberg, pp 223–250
38.
Zurück zum Zitat Pullan W (2005) An unbiased population-based search for the geometry optimization of Lennard-Jones clusters: 2 ≤ n ≤ 372. J Comp Chem 26(9):899–906CrossRef Pullan W (2005) An unbiased population-based search for the geometry optimization of Lennard-Jones clusters: 2 ≤ n ≤ 372. J Comp Chem 26(9):899–906CrossRef
39.
Zurück zum Zitat Roberts C, Johnston RL, Wilson N (2000) A genetic algorithm for the structural optimization of morse clusters. Theor Chem Acc 104:123–130 Roberts C, Johnston RL, Wilson N (2000) A genetic algorithm for the structural optimization of morse clusters. Theor Chem Acc 104:123–130
40.
Zurück zum Zitat Rogan J, Ramírez M, Mu noz V, Valdivia J, García G, Ramírez R, Kiwi M (2009) Diversity driven unbiased search of minimum energy cluster configurations. J Phys Condens Matter 21:084209CrossRef Rogan J, Ramírez M, Mu noz V, Valdivia J, García G, Ramírez R, Kiwi M (2009) Diversity driven unbiased search of minimum energy cluster configurations. J Phys Condens Matter 21:084209CrossRef
41.
Zurück zum Zitat Ronald S (1998) More distance functions for order-based encodings. In: Proceedings of the IEEE conference on evolutionary computation—CEC98, pp 558–563 Ronald S (1998) More distance functions for order-based encodings. In: Proceedings of the IEEE conference on evolutionary computation—CEC98, pp 558–563
42.
Zurück zum Zitat Smirnov B, Strizhev Y, Berry R (1999) Structures of large morse clusters. J Chem Phys 110(15):7412–7420CrossRef Smirnov B, Strizhev Y, Berry R (1999) Structures of large morse clusters. J Chem Phys 110(15):7412–7420CrossRef
43.
Zurück zum Zitat Smith J (2007) On replacement strategies in steady state evolutionary algorithms. Evol Comput 15(1):29–59CrossRef Smith J (2007) On replacement strategies in steady state evolutionary algorithms. Evol Comput 15(1):29–59CrossRef
44.
Zurück zum Zitat Spears W (1995) Adapting crossover in evolutionary algorithms. In: Proceedings of the fourth annual conference on evolutionary programming. MIT Press, Cambridge, pp 367–384 Spears W (1995) Adapting crossover in evolutionary algorithms. In: Proceedings of the fourth annual conference on evolutionary programming. MIT Press, Cambridge, pp 367–384
45.
Zurück zum Zitat Stillinger F (1999) Exponential multiplicity of inherent structures. Phys Rev E 59:48–51CrossRef Stillinger F (1999) Exponential multiplicity of inherent structures. Phys Rev E 59:48–51CrossRef
46.
Zurück zum Zitat Taillard E, Waelti P, Zuber J (2008) Few statistical tests for proportions comparison. Eur J Oper Res 185:1336–1350MATHCrossRef Taillard E, Waelti P, Zuber J (2008) Few statistical tests for proportions comparison. Eur J Oper Res 185:1336–1350MATHCrossRef
47.
Zurück zum Zitat Tsai CJ, Jordan KD (1993) Use of the histogram and jump walking methods for overcoming slow barrier crossing behavior in Monte Carlo simulations: applications to the phase transitions in the (ar)13 and (h2o)8 clusters. J Chem Phys 99:6957–6970CrossRef Tsai CJ, Jordan KD (1993) Use of the histogram and jump walking methods for overcoming slow barrier crossing behavior in Monte Carlo simulations: applications to the phase transitions in the (ar)13 and (h2o)8 clusters. J Chem Phys 99:6957–6970CrossRef
48.
Zurück zum Zitat Whitley D (1989) The genitor algorithm and selection pressure: why ranked-based allocation of reproductive trials is best. In: Proceedings of the third international conference on genetic algorithms—ICGA89, pp 116–121 Whitley D (1989) The genitor algorithm and selection pressure: why ranked-based allocation of reproductive trials is best. In: Proceedings of the third international conference on genetic algorithms—ICGA89, pp 116–121
49.
Zurück zum Zitat Wineberg M, Oppacher F (2003) Distance between populations. In: Proceedings of the genetic and evolutionary computation conference—GECCO 2003, Part II, pp 1481–1492 Wineberg M, Oppacher F (2003) Distance between populations. In: Proceedings of the genetic and evolutionary computation conference—GECCO 2003, Part II, pp 1481–1492
50.
Zurück zum Zitat Xiao Y, Williams DE (1993) Genetic algorithms: a new approach to the prediction of the structure of molecular clusters. Chem Phys Lett 215:17–24CrossRef Xiao Y, Williams DE (1993) Genetic algorithms: a new approach to the prediction of the structure of molecular clusters. Chem Phys Lett 215:17–24CrossRef
51.
Zurück zum Zitat Zar J (1999) Biostatistical analysis, 4th edn. Prentice-Hall, Englewood Cliffs Zar J (1999) Biostatistical analysis, 4th edn. Prentice-Hall, Englewood Cliffs
52.
Zurück zum Zitat Zeiri Y (1995) Prediction of the lowest energy structure of clusters using a genetic algorithm. Phys Rev 51:2769–2772 Zeiri Y (1995) Prediction of the lowest energy structure of clusters using a genetic algorithm. Phys Rev 51:2769–2772
Metadaten
Titel
A study on diversity for cluster geometry optimization
verfasst von
Francisco B. Pereira
Jorge M. C. Marques
Publikationsdatum
01.12.2009
Verlag
Springer-Verlag
Erschienen in
Evolutionary Intelligence / Ausgabe 3/2009
Print ISSN: 1864-5909
Elektronische ISSN: 1864-5917
DOI
https://doi.org/10.1007/s12065-009-0020-5