CPD News Index

Memetic Algorithms for molecular conformation and other optimization problems

With the name of `Memetic Algorithms' we recognize a class of metaheuristics which constitutes an emerging paradigm for optimization. For more than a decade now it has been applied with success to a large variety of combinatorial and nonlinear problems. In the last four years, and mostly in the last two, several techniques introduced in molecular optimization problems can be characterized in this way. We try to just introduce here the new techniques while we seek to emphasize the relation with previous and current work in Memetic Algorithms and Scatter Search. Memetic Algorithms (MAs) is a population-based approach to optimization [28]. It can be applied both to nonlinear and discrete (combinatorial) optimization problems. They are orders of magnitude faster than Genetic Algorithms in some problem domains. We call it a `metaheuristic' since it is a general purpose strategy that guides other basic heuristics or truncated exact methods. Other metaheuristics, like Simulated Annealing (SA) or Guided Local Search (GLS) (which guide some underlying ``Hill- climbing'' procedure), are applied to a single ``optimizer'' and thus they can not be categorized as `population-based'. Basic Tabu Search (TS) techniques also use a single optimizer, but more evolved metaheuristics like Scatter Search (SS), also use procedures based in ``multiple-point'' optimization. Genetic Algorithms (GAs), also try to evolve solutions in configuration space by using a ``population'' of individuals which represent alternative solutions of the problems. Good reviews stressing the similarities and differences of these approaches can be found in [10] [11] and [28] (the latter, written in 1990-92, anticipates the relevance of MAs in protein landscapes). 

A main difference between GAs and MAs is that the latter approach tries to use all possible knowledge available to solve the problem. Some SS procedures can be be classified as MAs too, though none of the approaches properly includes the other. In essence, MAs constitute an exercise of humbleness and common sense; if several alternative algorithms for the problem already exist, it should be a wise idea to use them together. This is of particular interest for the practitioner, who has been relying on a well-known code which enables to give locally optimal solutions but requires some extra global optimization (adding stochasticity to the search). Thus MAs are sometimes called ``Hybrid Genetic Algorithms'', or ``Lamarkian Evolutionary Algorithms'' or even ``knowledge-augmented GAs''. Other denominations include ``Genetic Local Search'' or ``Parallel Genetic Algorithms''. They are easy to be recognized from the so-called ``standard GAs'' since in MAs the new configurations (children) are created from highly evolved ``parents'' from previous generations. The independent evolution of parents is done using knowledge about the problem. In non-linear settings this generally achieved using gradient information. In combinatorial optimization problems they generally use some local search or constructive algorithm but truncated exact procedures (like truncated branch-and-bound or branch-and-cut techniques) can also be used. In all cases the existence of theorems and properties related to the structure of the optimum configuration greatly help to reduce the whole search process. 

The term ``memetic'' comes from R. Dawkins introduction of the term ``meme'' to denote an analogous to the gene but in the field of cultural evolution. In a Caltech report written in 1989 we discussed several MAs for combinatorial optimization and we conjectured the reasons for its success over the standard GAs approaches. Currently, a home page we maintain contains links to all available papers and relevant bibliography for MAs. In this note, due to length constraints, we will omit most of the references available from the web page. The Caltech report that gave its name to the, at that time incipient, field discussed a hybrid of GAs and SA developed with M.G. Norman in 1988. Currently, several papers are applying hybrids of GAs with SA or other methods to a variety of molecular optimization problems [39] [34] [33] [22] [1] [4] [37] [18] [21] [12] [19] [17] [40] [3] [27] [8] [23] [35]. In all of them, the authors of these papers refer to their metaheuristic as ``genetic'', probably being unaware about the existence of other MAs. For instance, Fu et al. in [9] say that GAs ``combined with conjugated gradient or molecular dynamics has been demonstrated to be efficient for the ground-state configuration search in materials research, e.g. fullerene formation, in this paper, based on the generalized tight-binding molecular dynamics, we apply the GA to study the surface reconstruction of Silicon (001) for the first time''. Hybrid population approaches like this can hardly be catalogues as being `genetic', but this denomination has appeared in previous work by Deaven and Ho [5] which got extra recognition due to an article by J. Maddox in Nature [24]. Other applications include cluster physics. Niesse and Mayne in [29] said: ``In a recent paper, Gregurick, Alexander, and Hartke [S. K. Gregurick, M. H. Alexander, and B. Hartke, J. Chem. Phys. 104, 2684 (1996)] proposed a global geometry optimization technique using a modified Genetic Algorithm approach for clusters. They refer to their technique as a deterministic/stochastic genetic algorithm (DS-GA). In this technique, the stochastic part is a traditional GA, with the manipulations being carried out on binary- coded internal coordinates (atom-atom distances). The deterministic aspect of their method is the inclusion of a coarse gradient descent calculation on each geometry. This step avoids spending a large amount of computer time searching parts of the configuration space which correspond to high-energy geometries. Their tests of the technique show it is vastly more efficient than searches without this local minimization''. Other papers in the area of cluster physics include [30] [16] [31] [37] [15] [6]. Other evolutionary approaches to a variety of molecular problems can be found in: [36] [32] [8] [26] [25] [14] [13]. Their use for design problems is particularly appealing, see: [18] [38] [2]. They have also found a way into protein design [7] [20], probably due to their landscape structure [28]. References 

1. M.J. Bayley, G. Jones, P. Willett, and M.P. Williamson. Genfold: A genetic algorithm for folding protein structures using NMR restraints. Protein Science, 7(2):491--499, Feb. 1998. 
2. D.E. Clark and D.R. Westhead. Evolutionary algorithms in computer-aided molecular design. Journal of Computer-aided Molecular Design, 10(4):337--358, Aug. 1996. 
3. T. Dandekar and P. Argos. Identifying the tertiary fold of small proteins with different topologies from sequence and secondary structure using the genetic algorithm and extended criteria specific for strand regions. Journal of Molecular Biology, 256(3):645--660, Mar. 1, 1996. 
4. P.A. de Souza, R. Garg, and V.K. Garg. Automation of the analysis of Mossbauer spectra. Hyperfine Interactions, 112(1--4):275-- 278, 1998. 
5. D.M. Deaven and K.O. Ho. Molecular-geometry optimization with a genetic algorithm. Physical Review Letters, 75(2):288--291, Jul 10, 1995. 
6. D.M. Deaven, N. Tit, J.R. Morris, and K.M. Ho. Structural optimization of Lennard-Jones clusters by a genetic algorithm. Chemical Physics Letters, 256(1--2):195--200, Jun. 21, 1996. 1 See: http://www.densis.fee.unicamp.br/~moscato/memetic_home.html 
7. J.R. Desjarlais and T.M. Handel. New strategies in protein design. Current Opinion in Biotechnology, 6(4):460--466, Aug. 1995. 
8. R. Doll and M.A. VanHove. Global optimization in LEED structure determination using genetic algorithms. Surface Science, 355(1-3):L393--L398, Jun. 1, 1996. 
9. R.T. Fu, K. Esfarjani, Y. Hashi, J. Wu, X. Sun, and Y. Kawazoe. Surface reconstruction of Si (001) by genetic algorithm and simulated annealing method. Science Reports of The Research Institutes Tohoku University Series A-Physics Chemistry And Metallurgy, 44(1):77--81, Mar. 1997. 
10. F. Glover. Genetic algorithms and scatter search - unsuspected potentials. Statistics And Computing, 4((2)):131--140, Jun. 1994. 
11. F. Glover. Scatter search and star-paths - beyond the genetic metaphor. OR Spektrum, 17((2-3)):125--137, Sep. 1995. 
12. J.R. Gunn. Sampling protein conformations using segment libraries and a genetic algorithm. Journal of Chemical Physics, 106(10):4270--4281, Mar. 8, 1997. 
13. B. Hartke. Global geometry optimization of clusters using genetic algorithms. Journal of Physical Chemistry, 97(39):9973--9976, Sep. 30, 1993. 
14. R. Hirsch and C.C. Mullergoymann. Fitting of diffusion- coefficients in a 3-compartment sustained-release drug formulation using a genetic algorithm. International Journal of Pharmaceutics, 120(2):229--234, Jun. 30, 1995. 
15. K.M. Ho, A.A. Shvartsburg, B.C. Pan, Z.Y. Lu, C.Z. Wang, J.G. Wacker, J.L. Fye, and M.F. Jarrold. Structures of medium-sized silicon clusters. Nature, 392(6676):582--585, Apr. 9, 1998. 
16. S. Hobday and R. Smith. Optimisation of carbon cluster geometry using a genetic algorithm. Journal of The Chemical Society-Faraday Transactions, 93(22):3919--3926, Nov. 21, 1997. 
17. G. Jones, P. Willett, R.C. Glen, A.R. Leach, and R. Taylor. Development and validation of a genetic algorithm for flexible docking. Journal of Molecular Biology, 267(3):727--748, Apr. 4, 1997. 
18. B.M. Kariuki, H. Serrano-Gonzalez, R.L. Johnston, and K.D.M. Harris. The application of a genetic algorithm for solving crystal structures from powder diffraction data. Chemical Physics Letters, 280(3-4):189--195, Dec. 5, 1997. 
19. E. Landree, C. Collazo-Davila, and L.D. Marks. Multi-solution genetic algorithm approach to surface structure determination using direct methods. Acta Crystallographica Section B - Structural Science, 53:916--922, Dec. 1, 1997. 
20. G.A. Lazar, J.R. Desjarlais, and T.M. Handel. De novo design of the hydrophobic core of ubiquitin. Protein Science, 6(6):1167--1178, Jun. 1997. 
21. L.P. Li, T.A. Darden, S.J. Freedman, B.C. Furie, B. Furie, J.D. Baleja, H. Smith, R.G. Hiskey, and L.G. Pedersen. Refinement of the NMR solution structure of the gamma-carboxyglutamic acid domain of coagulation factor IX using molecular dynamics simulation with initial Ca2+ positions determined by a genetic algorithm. Biochemistry, 36(8):2132--2138, Feb. 25, 1997. 
22. D.M. Lorber and B.K. Shoichet. Flexible ligand docking using conformational ensembles. Protein Science, 7(4):938--950, Apr. 1998. 
23. A.L. MacKay. Generalized crystallography. THEOCHEM-Journal of Molecular Structure, 336(2--3):293--303, Jun. 30, 1995. 
24. J. Maddox. Genetics helping molecular-dynamics. Nature, 376(6537):209--209, Jul. 20, 1995.  
25. A.C.W. May and M.S. Johnson. Protein-structure comparisons using a combination of a genetic algorithm, dynamic-programming and least-squares minimization. Protein Engineering, 7(4):475--485, Apr. 1994. 
26. J.C. Meza, R.S. Judson, T.R. Faulkner, and A.M. Treasurywala. A comparison of a direct search method and a genetic algorithm for conformational searching. Journal of Computational Chemistry, 17(9):1142--1151, Jul. 15, 1996. 
27. S.T. Miller, J.M. Hogle, and D.J. Filman. A genetic algorithm for the ab initio phasing of icosahedral viruses. Acta Crystallographica Section D - Biological Crystallography, 52:235--251, Mar. 1996. 
28. P. Moscato. An introduction to population approaches for optimization and hierarchical objective functions: The role of tabu search. Annals of Operations Research, 41(1-4):85--121, 1993. 
29. J.A. Niesse and H.R. Mayne. Global geometry optimization of atomic clusters using a modified genetic algorithm in space-fixed coordinates. Journal of Chemical Physics, 105(11):4700--4706, Sep. 15, 1996. 
30. N. Pucello, M. Rosati, G. DAgostino, F. Pisacane, V. Rosato, and M. Celino. Search of molecular ground state via genetic algorithm: Implementation on a hybrid SIMD-MIMD platform. International Journal of Modern Physics C, 8(2):239--252, Apr. 1997. 
31. W.J. Pullan. Structure prediction of benzene clusters using a genetic algorithm. Journal of Chemical Information and Computer Sciences, 37(6):1189--1193, Nov.-Dec. 1997. 
32. M.L. Raymer, P.C. Sanschagrin, W.F. Punch, S. Venkataraman, E.D. Goodman, and L.A. Kuhn. Predicting conserved water-mediated and polar ligand interactions in proteins using a k-nearest-neighbors genetic algorithm. Journal of Molecular Biology, 265(4):445--464, Jan. 31, 1997. 
33. K. Shankland, W.I.F. David, and T. Csoka. Crystal structure determination from powder diffraction data by the application of a genetic algorithm. Zeitschrift Fur Kristallographie, 212(8):550--552, 1997. 
34. K. Shankland, W.I.F. David, T. Csoka, and L. McBride. Structure solution of ibuprofen from powder diffraction data by the application of a genetic algorithm combined with prior conformational analysis. International Journal of Pharmaceutics, 165(1):117--126, Apr. 20, 1998. 
35. K.Y. Tam and R.G. Compton. GAMATCH - a genetic algorithm- based program for indexing crystal faces. Journal of Applied Crystallography, 28:640--645, Oct.1, 1995. 
36. A.H.C. vanKampen, C.S. Strom, and L.M.C Buydens. Lethalization, penalty and repair functions for constraint handling in the genetic algorithm methodology. Chemometrics And Intelligent Laboratory Systems, 34(1):55--68, Aug. 1996. 
37. R.P. White, J.A. Niesse, and H.R. Mayne. A study of genetic algorithm approaches to global geometry optimization of aromatic hydrocarbon microclusters. Journal of Chemical Physics, 108(5):2208- -2218, Feb. 1, 1998. 
38. P. Willett. Genetic algorithms in molecular recognition and design. Trends in Biotechnology, 13(12):516--521, Dec. 1995. 
39. C.R. Zacharias, M.R. Lemes, and A.D. Pino. Combining genetic algorithm and simulated annealing: a molecular geometry optimization study. THEOCHEM-Journal of Molecular Structure, 430(29--39), Apr. 14, 1998. 
40. M. Zwick, B. Lovell, and J. Marsh. Global optimization studies on the 1-d phase problem. International Journal of General Systems, 25(1):47--59, 1996.