Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A study on diversity for cluster geometry optimization

  • Research Paper
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Braier P, Berry R, Wales D (1990) How the range of pair interactions govern features of multidimensional potentials. J Chem Phys 93(12):8745–8756

    Article  Google Scholar 

  2. 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. 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

  4. Cassioli A, Locatelli M, Schoen F (2008) Global optimization of binary Lennard-Jones clusters. Optim Methods Softw, online December 2008. doi:10.1080/10556780802614101

  5. Cheng L, Cai W, Shao X (2004) A connectivity table for cluster similarity checking in the evolutionary optimization method. Chem Phys Lett 389:309–314

    Article  Google Scholar 

  6. 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–5293

    Article  Google Scholar 

  7. Deaven D, Ho K (1995) Molecular geometry optimization with a genetic algorithm. Phys Rev Lett 75:288–291

    Article  Google Scholar 

  8. Demsar J (2006) Statistical comparisons of classifiers over multiples data sets. J Mach Learn Res 7:1–30

    MathSciNet  Google Scholar 

  9. 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. Doye JPK, Leary R, Locatelli M, Schoen F (2004) Global optimization of morse clusters by potential energy transformations. Informs J Comput 16:371–379

    Article  Google Scholar 

  11. 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–4243

    Article  Google Scholar 

  12. Goldberg D, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of genetic algorithms, pp 69–93

  13. Grigoryan V, Alamanova D, Springborg M (2005) Structure and energetics of nickel, copper, and gold clusters. Eur Phys J D 34:187–190

    Article  Google Scholar 

  14. 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–404

    Article  MATH  MathSciNet  Google Scholar 

  15. 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. Hartke B (1993) Global geometry optimization of clusters using genetic algorithms. J Phys Chem 97:9973–9976

    Article  Google Scholar 

  17. 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–1759

    Article  Google Scholar 

  18. 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. 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. Johnston RL (2003) Evolving better nanoparticles: genetic algorithms for optimising cluster geometries. Dalton Trans 22:4193–4207

    Article  Google Scholar 

  21. Jones JE (1924) On the determination of molecular fields. ii. From the equation of state of a gas. Proc R Soc A 106:463–477

    Article  Google Scholar 

  22. De Jong K (1975) An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, Un. Michigan

  23. De Jong K, Sarma J (1993) Generation gaps revisited. In: Foundations of genetic algorithms, vol 2, pp 19–28

  24. 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. 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. 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

    Google Scholar 

  27. Lennard-Jones JE (1931) Cohesion. Proc Phys Soc 43:461–482

    Article  MATH  Google Scholar 

  28. Liu DC, Nocedal J (1989) On the limited memory method for large scale optimization. Math Programm B 45:503–528

    Article  MATH  MathSciNet  Google Scholar 

  29. Locatelli M, Schoen F (2002) Fast global optimization of difficult Lennard-Jones clusters. Comput Optim Appl 21:55–70

    Article  MATH  MathSciNet  Google Scholar 

  30. Locatelli M, Schoen F (2003) Efficient algorithms for large scale global optimization: Lennard-Jones clusters. Comput Optim Appl 26:173–190

    Article  MATH  MathSciNet  Google Scholar 

  31. Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded memetic algorithms with crossover hill-climbing. Evol Comput 12:273–302

    Article  Google Scholar 

  32. 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–515

    Article  Google Scholar 

  33. Morse P (1929) Diatomic molecules according to the wave mechanics. ii. Vibrational levels. Phys Rev 34:57–64

    Article  Google Scholar 

  34. 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. 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. 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. 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. 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–906

    Article  Google Scholar 

  39. Roberts C, Johnston RL, Wilson N (2000) A genetic algorithm for the structural optimization of morse clusters. Theor Chem Acc 104:123–130

    Google Scholar 

  40. 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:084209

    Article  Google Scholar 

  41. Ronald S (1998) More distance functions for order-based encodings. In: Proceedings of the IEEE conference on evolutionary computation—CEC98, pp 558–563

  42. Smirnov B, Strizhev Y, Berry R (1999) Structures of large morse clusters. J Chem Phys 110(15):7412–7420

    Article  Google Scholar 

  43. Smith J (2007) On replacement strategies in steady state evolutionary algorithms. Evol Comput 15(1):29–59

    Article  Google Scholar 

  44. 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. Stillinger F (1999) Exponential multiplicity of inherent structures. Phys Rev E 59:48–51

    Article  Google Scholar 

  46. Taillard E, Waelti P, Zuber J (2008) Few statistical tests for proportions comparison. Eur J Oper Res 185:1336–1350

    Article  MATH  Google Scholar 

  47. 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–6970

    Article  Google Scholar 

  48. 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. 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. Xiao Y, Williams DE (1993) Genetic algorithms: a new approach to the prediction of the structure of molecular clusters. Chem Phys Lett 215:17–24

    Article  Google Scholar 

  51. Zar J (1999) Biostatistical analysis, 4th edn. Prentice-Hall, Englewood Cliffs

  52. Zeiri Y (1995) Prediction of the lowest energy structure of clusters using a genetic algorithm. Phys Rev 51:2769–2772

    Google Scholar 

Download references

Acknowledgments

We are grateful to the John von Neumann Institut für Computing, Jülich, for the provision of supercomputer time on the IBM Regatta p690+ (Project EPG01).

Author information

Authors and Affiliations

  1. Instituto Superior de Engenharia de Coimbra, 3030-199, Coimbra, Portugal

    Francisco B. Pereira

  2. Centro de Informática e Sistemas da Universidade de Coimbra, 3030-290, Coimbra, Portugal

    Francisco B. Pereira

  3. Departamento de Química, Universidade de Coimbra, 3004-535, Coimbra, Portugal

    Jorge M. C. Marques

Authors
  1. Francisco B. Pereira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jorge M. C. Marques
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francisco B. Pereira.

Appendix: Additional optimization results

Appendix: Additional optimization results

The analysis performed in Sects. 3 and 4 was based on the success rate, as this is the most widely used performance measure to access the efficacy of algorithms when applied to cluster geometry optimization problems. Anyway, and for the sake of completeness, we provide the mean best fitness (MBF) values of all optimization experiments previously described.

The MBF values presented in Table 4 were obtained by EA−Fit, EA−Str, EA−CM, EA−NoDiv and SA−EA in the initial optimization experiments of Morse clusters between 41 and 80 atoms. The application of the Friedman statistical test establishes the same ranking described in Sect. 3: EA−Str, EA−CM and SA−EA outperform both EA−Fit and EA−NoDiv. Between the three most successful variants there are no significant differences.

Table 4 MBF obtained by EA-Fit, EA-Str, EA-CM, EA-NoDiv and SA-EA in the optimization of Morse clusters between 41 and 80 atoms
Full size table

Table 5 shows the MBF obtained by EA−Fit, EA−Str and EA−CM on the extended runs. Entries in bold highlight a situation where the MFB is significantly better than that of the corresponding experiment that was allowed to run only for 5,000,000 evaluations (analysis performed with the non-parametric Mann-Whitney test).

Table 5 MBF obtained by EA-Fit, EA-Str and EA-CM in the extended runs performed with some selected Morse cluster instances
Full size table

Finally, Table 6 displays the MBF obtained by the three EA variants with diversity on the optimization of the Morse cluster with 61 atoms using different values for ξ. No significant differences arise on the MBF of the same EA variant when using different values for the ξ parameter (analysis performed with the non-parametric Kruskal–Wallis test).

Table 6 MBF obtained by EA-Fit, EA-Str and EA-CM in the optimization of the Morse cluster with 61 atoms. Results obtained with different values for ξ are reported
Full size table

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pereira, F.B., Marques, J.M.C. A study on diversity for cluster geometry optimization. Evol. Intel. 2, 121–140 (2009). https://doi.org/10.1007/s12065-009-0020-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-009-0020-5

Keywords

Search

Navigation