Crossover

Overview

Crossover is an evolutionary operation that creates a new structure (offspring) by exchanging sliced regions between two parent structures. This promotes structural diversity and enables the inheritance of locally stable features. It is one of the main operators used to explore low-energy configurations in structure search.

How it works

1. Select two distinct individuals from the candidate parents
2. Perform a random translation
3. Randomly select a lattice vector
4. Slice the parents near the center
5. Swap the sliced halves
6. Select the offspring with more atoms
7. Adjust the number of atoms near the border
8. Perform a minimum interatomic distance check

4. Slice the parents near the center

The slice point is placed near the center and slightly varied each time.

slice_point = np.clip(np.random.normal(loc=0.5, scale=0.1), 0.3, 0.7)

If any of the subsequent steps fail, the process may be restarted from step 4. However, the number of retries is limited to maxcnt_ea, and if this limit is exceeded, the parent selection step is repeated.

5. Swap the sliced halves

When crs_lat is set to random, the lattice vectors of one of the two parent structures are randomly selected. When crs_lat is set to equal, the average of the lattice vectors of the two parent structures is used. The default is random.

6. Select the offspring with more atoms

Swapping the sliced parts of the parent structures results in two structures with different numbers of atoms. Temporarily, we select the structure with more atoms.

However, if the composition differs too much from the target, the process restarts from step 4 (Slice the parents near the center). The tolerance for the difference in the number of atoms is set by nat_diff_tole. The default value of nat_diff_tole is 4, which allows a tolerance of ±4 atoms per element. In the figure above, the number of blue atoms is -1 and the number of green atoms is +2 relative to the original composition.

7. Adjust the number of atoms near the border

Deletion

When adjusting the number of atoms, the process starts with atom deletion. The number of green atoms is excessive and needs to be reduced. As illustrated in the figure below, atoms that do not satisfy the minimum interatomic distance defined by mindist are preferentially removed.

As shown below, if atoms that violate the minimum interatomic distance remain after the deletion process, the procedure is restarted from step 4 (Slice the parents near the center).

If there are no atoms violating the minimum interatomic distance but atoms still need to be deleted, atoms are removed in order of increasing distance from the border, as shown in the figure below. Note that, in addition to the central slicing point, positions with internal coordinates of 0 are also considered borders.

Addition

When atoms are lacking, the missing atoms are added near the border. The internal coordinate along the selected axis is determined as shown below. Here, mean refers to either the slice point or 0.

coords[axis] = np.random.normal(loc=mean, scale=0.08)

The remaining two components of the coordinate are determined randomly. Atoms are added until the target number is reached, while checking for violations of the minimum interatomic distance.

Permutation

Overview

Permutation is an evolutionary operation that generates new structures (offspring) by modifying the atomic arrangement within a single structure. It enables the exploration of alternative configurations without changing the lattice or the overall composition.

How it works

The positions of atoms of different elements are swapped. The number of swaps can be specified by ntimes, which is set to 1 by default. After the swap, a minimum interatomic distance check is performed.

Strain

Overview

Strain is an evolutionary operation that generates a new structure (offspring) by applying a small random distortion to the lattice of a parent structure. It helps to explore nearby regions of the configuration space while preserving atomic connectivity and composition. This operator is useful for fine-tuning structural candidates and escaping local minima.

How it works

The lattice vectors are $ \mathbf{a} $ transformed to $ \mathbf{a}' $ by applying a strain matrix, as follows:

Here, $ \eta_i $ are given by a Gaussinan distribution $ \mathcal{N}\left( 0, \ \sigma_{\mathrm{st}}^2 \right) $. $ \sigma_{\mathrm{st}} $ is specified by the input parameter sigma_st (by default, sigma_st = 0.5). As shown in the figure below, the lattice is deformed and then rescaled to restore the original volume. Finally, the minimum interatomic distance constraint is checked.

Tournament selection

Overview

Tournament selection is a method used to choose parent individuals from the candidate parents based on their fitness. It is designed to balance selection pressure and diversity in the population. The figure below shows an example with n_fittest = 10 and t_size = 3.

How it works

1. A fixed number of individuals (t_size) are randomly selected from the candidate parents.
2. Among them, the individual with the highest fitness (i.e., lowest energy) is chosen as the parent.
3. This process is repeated until the required number of parents is selected.

Advantages

• Simple and efficient
• Requires only one parameter (t_size)
• Can control selection pressure by adjusting t_size

Notes

• The default value of t_size is 3.
• If t_size is small, diversity is promoted.
• If t_size is large, selection pressure increases, favoring the fittest individuals.
• Unlike roulette selection, tournament selection never chooses the bottom (t_size - 1 ) individuals from the candidate parents.

Roulette selection

Overview

Roulette selection is a probabilistic method used to select parent individuals from the candidate parents based on their fitness. In roulette selection, each individual’s chance of being selected is proportional to its fitness.

How it works

1. When fit_reverse is set to False (default), corresponding to minimization mode where energy is used as fitness, the fitness values of the candidate parents are multiplied by –1.
2. The fitness values $ f_i $ are linearly scaled into $ f'_i $ using the following equation, where $ a $ and $ b $ are parameters specified by a_rlt and b_rlt, respectively (with the condition that $ a > b $). $$ f_i' = \frac{a - b}{f_{\mathrm{max}} - f_{\mathrm{min}}} f_i + \frac{b f_{\mathrm{max}} - a f_{\mathrm{min}}}{f_{\mathrm{max}} - f_{\mathrm{min}}} $$
3. The scaled fitness values $ f_i’ $ are converted into selection probabilities using the following equation:    $$ p_i = \frac{f_i’}{\sum_k f_k’} $$ Each probability $ p_i $ represents the likelihood of selecting the $ i $-th individual.
4. Parent individuals are then selected one by one according to the probabilities $ p_i $ using roulette wheel sampling, until the required number of parents is obtained.

Advantages

• All individuals have a non-zero chance of being selected
• Selection pressure can be adjusted by scaling the fitness values

Notes

• By default, a_rlt = 10.0 and b_rlt = 1.0
• Proper scaling of fitness values is important to ensure meaningful selection pressure.The figure below shows examples of $ p_i $ when $ a $ is relatively small (left) and relatively large (right). If $ a $ is too small, the selection pressure becomes weak, making it more difficult to favor individuals with higher fitness.

Crossover (vc)

The variable-composition crossover is almost the same as the fixed-composition version, but it differs in that the adjustment of the number of atoms is minimized.

In step 6 of the fixed-composition crossover, the difference in the number of atoms in each atom type is calculated directly. In contrast, in crossover (vc), the difference is calculated based on the allowed range defined by ll_nat and ul_nat. For example:

ll_nat = [4, 4, 4]
ul_nat = [8, 8, 8]
offspring_nat = [2, 6, 12]
nat_diff = [-2, 0, 4]

If this difference in the number of atoms (nat_diff in the example above) exceeds the allowed tolerance (nat_diff_tole), the operation is retried. Otherwise, the number of atoms is adjusted to fall within the range defined by ll_nat and ul_nat.

Addition

An atom type whose current count does not exceed the limit specified by ul_nat is randomly selected, and one atom of that type is added at a random position.

• One atom is added, and if it does not violate the minimum interatomic distance defined by mindist, the structure is accepted.
• If the distance condition is not satisfied, the atom is placed again at a different random position. This process is repeated up to maxcnt_ea times.
• If no valid offspring is obtained, the volume is expanded by 10%, and the same procedure is retried up to maxcnt_ea times.
• If that also fails, the volume is expanded up to 20% and the structure generation is attempted again. If it still fails, the parent is replaced.

Elimination

An atom type whose current count is above the lower limit specified by ll_nat is randomly selected, and one atom of that type is removed.

Substitution

Substitution randomly selects two different atom types: one whose current count is above the lower limit specified by ll_nat, and another whose current count is below the upper limit specified by ul_nat. Then, one atom of the former type is replaced with an atom of the latter type. Finally, the minimum interatomic distance defined by mindist is checked, and if no violations are found, the structure is accepted as an offspring.