Optimisation of algorithm control parameters in cultural differential evolution applied to molecular crystallography

Abstract

Evolutionary search and optimisation algorithms have been used successfully in many areas of materials science and chemistry. In recent years, these techniques have been applied to, and revolutionised the study of crystal structures from powder diffraction data. In this paper we present the application of a hybrid global optimisation technique, cultural differential evolution (CDE), to crystal structure determination from powder diffraction data. The combination of the principles of social evolution and biological evolution, through the pruning of the parameter search space shows significant improvement in the efficiency of the calculations over traditional dictates of biological evolution alone. Results are presented in which a range of algorithm control parameters, i.e., population size, mutation and recombination rates, extent of culture-based pruning are used to assess the performance of this hybrid technique. The effects of these control parameters on the speed and efficiency of the optimization calculations are discussed, and the potential advantages of the CDE approach demonstrated through an average 40% improvement in terms of speed of convergence of the calculations presented, and a maximum gain of 68% with larger population size.

Keywords

evolutionary algorithms / differential evolution / cultural evolution / powder diffraction / crystal structure solution / global optimisation

References

[1] Johnston R L, ed. Applications of Evolutionary Computation in Chemistry. In: Mingos D M P. Structure and Bonding. Berlin/Heidelberg: Springer, 2004, 110

[2] Harris K D M, Tremayne M, Kariuki B M. Contemporary advances in the use of powder X-ray diffraction for structure determination. Angewandte Chemie International Edition, 2001, 40: 1626-1651

[3] David W I F, Shankland K, McCusker L B, Baerlocher C, eds. Structure Determination from Powder Diffraction Data. Oxford: Oxford University Press, 2002

[4] Reynolds R G. An introduction to cultural algorithms. In: Sebald A V, Fogel L J, eds. In: Proceedings of the Third Annual Conference on Evolutionary Programming. Singapore: World Scientific Press, 1994, 131-139

[5] Reynolds R G. Cultural Algorithms: Theory and Applications. In: Corne D, Dorigo M, Glover F, eds. New Ideas in Optimisation. London: McGraw-Hill, 1999, 367-377

[6] Engelbrecht A P. Computational Intelligence: An Introduction. Chichester: John Wiley & Sons, 2001, 171-175

[7] Chong S Y, Tremayne M. Combined optimization using cultural and differential evolution: application to crystal structure solution from powder diffraction data. Chemical Communications, 2006, 4078-4080

[8] Storn R, Price K V. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimisation, 1997, 11: 341-359

[9] Chisholm K. Co-evolving draughts strategies with differential evolution. In: Corne D, Dorigo M, Glover F, eds. New Ideas in Optimisation. London: McGraw-Hill, 1999, 147-158

[10] Feoktistov V. Differential Evolution: In Search of Solutions. New York: Springer, 2006

[11] Wormington M, Panaccione C, Matney K M, Bowen D K. Characterisation of structures from X-ray scattering data using genetic algorithms. Philosophical Transactions of the Royal Society A, 1999, 357(1761): 2827-2848

[12] Bjorck M, Andersson G. GenX: an extensible X-ray reflectivity refinement program utilizing differential evolution. Journal of Applied Crystallography, 2007, 40: 1174-1178

[13] Seaton C C, Blagden N. Designing molecular interfaces. American Crystallographic Association Transactions, 2004, 39: 90-102

[14] Chakraborti N, Mishra P, Erkoc S. A study of the Cu clusters using Gray-coded genetic algorithms and differential evolution. Journal of Phase Equilibria and Diffusion, 2004, 25: 16-21

[15] McRee D E. Differential evolution for protein crystallographic optimizations. Acta Crystallographica, 2004, D60: 2276-2279

[16] Thomsen R, Christensen M K. MolDock: A new technique for highaccuracy molecular docking. Journal of Medicinal Chemistry, 2006, 49: 3315-3321

[17] Oeckler O, Weber T, Kienle L, Mattausch H, Simon A. Cluster disorder and ordering principles in Al-stabilized “Lal”. Angewandte Chemie International Edition, 2005, 44: 3917-3921

[18] Burgi H B, Hauser J, Weber T, Neder R B. Supramolecular architecture in a disordered perhydrotriphenylene inclusion compound from diffuse X-ray diffraction data. Crystal Growth and Design, 2005, 5: 2073-2083

[19] Tremayne M, Seaton C C, Glidewell C. Structures of three substituted arenesulfonamides from X-ray powder diffraction data using the differential evolution technique. Acta Crystallographica, 2002, B58: 823-834

[20] Seaton C C, Tremayne M. Differential evolution: crystal structure determination of a triclinic polymorph of adipamide from powder diffraction data. Chemical Communications, 2002, 880-881

[21] Chong S Y, Seaton C C, Kariuki B M, Tremayne M. Molecular versus crystal symmetry in tri-substituted triazine, benzene and isocyanurate derivatives. Acta Crystallographica, 2006, B62: 864-874

[22] Price K V. An introduction to differential evolution. In: Corne D, Dorigo M, Glover F, eds. New Ideas in Optimisation. London: McGraw-Hill, 1999, 77-108

[23] Harris K D M, Johnston R L, Kariuki B M. The genetic algorithm: Foundations and applications in structure solution from powder diffraction data. Acta Crystallographica, 1998, A54: 632-645

[24] Cheung E Y, McCabe E E, Harris K D M, Johnston R L, Raja K M P, Balaram P. C-H. . . O hydrogen bond mediated chain reversal in a peptide containing a γ-amino acid residue, determined directly from powder X-ray diffraction data. Angewandte Chemie International Edition, 2002, 41: 494-496

[25] Gao F, Liu H, Zhao Q, Cui G. Hybrid model of genetic algorithm and cultural algorithms for optimisation problem. In: Proceedings of Simulated Evolution and Learning, LNCS, 2006, 4247: 441-448

[26] Xue Z G, Guo Y N. Improved cultural algorithm based on genetic algorithm. In: Proceedings of IEEE International Conference on Integration Technology, 2007, 117-122

[27] Gao F, Zhao Q, Liu H W, Cui G. Cultural genetic algorithm for constrained optimisation problem. Dynamics of Continuous Discrete and Impulsive Systems-Series B-Applications and Algorithms, 2007, 1: 85-90

[28] Nguyen T T, Yao X. An experimental study of hybridizing cultural algorithms and local search. International Journal of Neural Systems, 2008, 18: 1-17

[29] Becerra R L, Coello Coello A C. Cultured differential evolution for constrained optimisation. Computer Methods in Applied Mechanical Engineering, 2006, 195: 4303-4322

[30] Becerra R L, Coello Coello A C. Optimisation with constraints using a cultured differential evolution approach. In: Proceedings of GECCO2005: Genetic and Evolutionary Computation Conference, 2005, 1-2: 27-34

[31] Chong S Y. Development of novel evolutionary algorithms for crystal structure determination from powder diffraction data. PhD Thesis. Birmingham: University of Birmingham, 2006

[32] Rossi M, Meyer R, Constantinou P, Caruso F, Castelbuono D, O’Brien M, Narasimhan V. Molecular structure and activity toward DNA of baicalein, a flavone constituent of the asian herbal medicine “Shosaiko- to”. Journal of Natural Products, 2001, 64: 26-31

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg