1.3 Evolutionary algorithm

The evolutionary algorithm (EA) mimics Darwinian evolution and employ natural selection of the fittest and such variation operators as genetic heredity and mutations. It can perform well for different types of free energy landscapes. Unlike the previously proposed genetic algorithms, we represent the coordinates of atoms in the unit cell and lattice vectors by real numbers. Therefore, the search space is continuous and not discrete like binary string representation.

The procedure is as shown in Fig. 2.2:

Figure 2.2: Illustration of the evolutionary algorithm for crystal structure prediction.

(1) Initialization of the first generation, that is, a set of structures satisfying the hard constraints are randomly generated;

(2) Determination of the quality for each member of the population using the so-called fitness question;

(3) Selection of the best members from the current generation as parents from which the structures of the new population are created by applying specially designed variation operators.

(4) Evaluation of the quality for each new member of the population.

(5) Repeat steps 3-4 till the halting criteria is achieved.

The above algorithm has been implemented in the USPEX (Universal Structure Predictor: Evolutionary Xtallography) code ^{4; 26; 27}.

Fitness function mathematically describes the target direction of the global search. And it is usually related to the physical quantities. The first motivation in CSP is to search for the structure with the lowest free energy (more practically, it should be enthalpy since it is not easy to obtain the free energy within the current state of the art). In the following development, one could also choose to optimize other quantities instead of energy.

Figure 2.3: Illustration of variation operator used in USPEX, (a) heredity, (b) lattice mutation, (c) softmode mutation, (d) permutation