Genetic algorithms as global optimizers

1. Automated assignment of rovibronic spectra using GA

The task of performing a fit of the molecular Hamiltonian parameters to an experimental spectrum like the one shown below (actually, this is a rovibronic spectrum of seven different tryptamine isotopomers) using line position assigned fits can be tedious or in some cases even impossible. Details can be found in [1]. The non-assigned fit of such a spectrum can be viewed as a classical optimization process on a multidimensional parameter surface. Genetic algorithms (GA), invented by J. Holland, are optimizers [2], which have the advantage to end mostly in the global minimum.

The GA mimick thereby a scheme traced out by nature:

Representation of the parameters: The molecular parameters are encoded as binary or as real data type, each parameter representing a gene. A vector of all genes, which contains all molecular parameters is called a chromosome. In an initial step the values for all parameters are set to random values between lower and upper limits which have to be chosen by the user. No prior knowledge of the parameters is necessary. In our calculations in general a total of 300 - 500 chromosomes are randomly generated, forming a population.

The solutions (chromosomes) are evaluated by a fitness function (or cost function), which is a measure for the quality of the individual solution.

One optimization cycle, including evaluation of the cost of all chromosomes is called a generation. Generally convergence of the fit in our case is reached after 300 - 500 generations.

Pairs of chromosomes are selected for reproduction and their information is combined via a crossover process. This crossover might take place as a one-point, two-point or uniform crossover. As crossover just combines information from the parent generations. It basically explores the error landscape.

The performance of the GA depends on internal parameters like mutation rate, elitism, crossover probability and population size, which therefore should also be optimized for a given problem. Fortunately this meta-optimization results in similar parameters for quite different problems of optimization. The meta-optimization for some of the parameters is described in ref. [3].

[1] Schmitt, M., Böhm, M., Ratzer, C., Vu, C., Kalkman, I. and Meerts, W. L.: Structural selection by microsolvation: conformational locking of tryptamine. J. Am. Chem. Soc. 127 (2005), 10356).
[2] J. Holland: Adaption in Natural and Artificial Systems, MIT Press (1994)
[3] Meerts, W. L. and Schmitt, M.: A new automated assign and analyzing method for high resolution rotational resolved spectra using Genetic Algorithms. Phys. Scripta 73 (2005), C47

This project is performed in collaboration with Leo Meerts (University of Nijmegen). A nice slide show, describing the GA can be found here.

2. Determination of molecular stuctural parameters from rotational constants using GA

The rotational constants of a molecule can be determined from several spectroscopic techniques that provide rotational resolution. They are inversely proportional to the moments of inertia, which are defined as:

The determination of the structure of a molecule from the rotational constants of several isotopomers is a straightforward procedure, which has been routinely used in microwave spectroscopy for decades. The basic equations have been worked out by Kraitchman [1] and Costain [2] and are nowadays standard textbook knowledge [3]. Basically, each atom in the moelcule has succesively to be replaced by a (stable) isotope. Application of the Kraitchman equations using the moments of inertia of the parent molecule with the normal isotopes and of the singly substituted molecule yields the cartesian coordinates of this atom in the inertial system of the parent molecule.