# Patent

## Title
Method for predicting optimized crystal structures

## Abstract

Disclosed is a method and system for prediction of an optimized crystal structure using an evolutionary algorithm that includes inputting characterization information of a chemical structure and input parameters, generating a first generation of crystal structures from the characterization information using symmetrical initialization, optimizing the chemical structure of the first generation of crystal structures according to the input parameters, inputting the optimized first generation of crystal structures into a niching algorithm, producing a child group of crystal structures from the parent group of crystal structures using a variation operator, and adding the child group of crystal structures to an optimal group of crystal structures to form a next generation, with the niching algorithm selecting an optimal group of crystal structures and a parent group of crystal structures from the first generation of crystal structures.

## Background
PRIORITY
This application claims priority to U.S. Provisional Applications No. 61/501,527 and 61/663,828, filed with the U.S. Patent and Trademark Office on Jun. 27, 2011 and Jun. 25, 2012, respectively, the content of each of which is incorporated herein by reference.


BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computational material design and, more particularly, to a system using an evolutionary algorithm for optimized crystal structure prediction.
2. Description of the Related Art
Evolutionary algorithms are widely used in the field of crystal structure prediction. Specifically, evolutionary algorithms are useful for determining a ground state of a crystal structure for a given chemical composition at given pressure and temperature conditions. The ground state refers to the crystal structure with a lowest possible free energy, i.e. enthalpy, for the chemical composition. An evolutionary algorithm of Universal Structure Predictor: Evolutionary Xtallography (USPEX) provides an efficient and reliable method and system for crystal structure prediction, improvements to which are disclosed herein.
USPEX is utilized in various applications, for example prediction of hardness, which is an important property for determination of new materials for applications such as cutting and drilling tools. The ability to predict a hardest phase of a crystal and other structures, for a given stoichiometry, enables a systematic search for novel hard materials and allows efficient evaluation of potentially controversial experimental results. Problems encountered utilizing conventional systems are summarized in Modern Methods of Crystal Structure Prediction, Andriy O. Lyakhov et al., (Artem Oganov ed., Wiley VCH, 2011). Problems that arise in conventional systems include finding a global minimum on a surface in multidimensional space, such as hardness and free energy, as a function of the atomic positions and lattice vectors, respectively. Computing the hardness of a given crystal structure is a difficult task. Only recently has significant progress been achieved in formulating models that are physically meaningful and sufficiently accurate for several classes of compounds. See F. Gao et al., Phys. Rev. Lett. 91, 0155021 (2003); A. Simunek and J. Vackar, Phys. Rev. Lett. 96, 0855011 (2006); K. Li et al., Phys. Rev. Lett. 100, 235504 (2008); and A. R. Oganov and A. O. Lyakhov, J. Superhard Mater. 32, 143 (2010).
Evolutionary crystal structure prediction begins with a set or population of crystal structures and evolves this set of crystal structures based on input parameters and variation operators that provide the conditions for optimization of the set of crystal structures to produce child crystal structures from parent crystal structures. A conventional method to determine next generations of crystal structures is provided in International Publication No. WO2007/071095 of Glass et al. Child, i.e. next generation, crystal structures retain vestiges of parent crystal structures after operation of the variation operators, while new features are introduced into the child crystal structures. These new features include both desirable and undesirable characteristics. Variation operators include a heredity operator, which creates a child crystal structure from two or more parents, and a mutation operator, which creates a child using a single parent.
An initial population may be randomly created or input based on desired ground state information, such as likely candidate structures, lattice parameters, and space groups. Conventional evolutionary algorithms locally optimize the crystal structures, typically by relaxation of chemical bonds by a user determined theory, such as empirical potentials, density functional theory, hybrid functions and Quantum Monte Carlo algorithms.
However, conventional evolutionary algorithms generate crystal structures that often become trapped in a local free energy minimum rather than a global free energy minimum. In addition, a number of local minima rises exponentially as the crystal structure's size increases, further raising the risk of trapping. Accordingly, current evolutionary algorithms are limited to crystal structure prediction of materials of only 15-40 atoms in size.
Moreover, random input of conventional systems will often create an initial population of crystal structures that is randomly produced. Such random initialization typically leads to highly disordered output of nearly identical child structures with similar high energies and a low degree of order. Thus, conventional methods and systems fail to provide a method for optimized prediction of crystal structures, particularly for materials with larger sized molecules.
SUMMARY OF THE INVENTION
Accordingly, aspects of the present invention address the above problems and disadvantages and provide the advantages described below. An aspect of the present invention provides a method and system for prediction of an optimized crystal structure using an evolutionary algorithm that includes inputting characterization information of a chemical structure and input parameters, generating a first generation of crystal structures from the characterization information using symmetrical initialization, optimizing the chemical structure of the first generation of crystal structures according to the input parameters, inputting the optimized first generation of crystal structures into a niching algorithm, producing a child group of crystal structures from the parent group of crystal structures using a variation operator, and adding the child group of crystal structures to an optimal group of crystal structures to form a next generation, with the niching algorithm selecting an optimal group of crystal structures and a parent group of crystal structures from the first generation of crystal structures based on fitness and fingerprint functions, and repeating the algorithm for a predetermined number of generations to output the optimized crystal structure.



BRIEF DESCRIPTION OF THE DRAWINGS
The above and other aspects, features and advantages of certain embodiments of the present invention will be more apparent from the following detailed description taken in conjunction with the accompanying drawings, in which:
FIG. 1 is a flow chart of a method to predict optimized crystal structure using an evolutionary algorithm according to an aspect of the present invention;
FIG. 2 illustrates atoms merging by coordinate averaging according to an aspect of the present invention;
FIG. 3 is a graph illustrating optimized crystal structure predictions, according to an aspect of the present invention;
FIG. 4 shows structures of a non-optimized first generation crystal structures in a top row and shows optimized crystal structures in a bottom row; and
FIG. 5 shows structures of a non-optimized second generation crystal structures in a top row and shows optimized in a bottom row.



DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION
The following detailed description of certain embodiments of the present invention will be made with reference to the accompanying drawings. In describing the invention, explanation about related functions or constructions known in the art are omitted for the sake of clearness in understanding the concept of the invention, to avoid obscuring the invention with unnecessary detail.
FIG. 1 illustrates a method for predicting an optimized crystal structure using an evolutionary algorithm. At step 300, characterization information of a chemical structure is input. The characterization information includes chemical formulas, an atomic number of an atom, a number of atoms in a unit cell, valences of atoms, and unit cell volume. The characterization information may also include lattice parameters known from experimental data and other information.
Following the inputting of characterization information, a first generation of crystal structures is obtained, preferably by a random input, seed input or symmetrical initialization. The first generation of crystal structures is described herein as being generated using a symmetrical initialization algorithm based on the input characterization information. A randomly produced crystal structure can be utilized to commence generation of crystal structures in step 310, with the symmetrical initialization algorithm randomly selecting a space group compatible with the number of atoms in a unit cell of the chemical structure. For example, the space group can be randomly selected from space group numbers 1 to 230 using a Mersenne Twister algorithm. See Matsumoto, M., et al., Mersenne Twister: A 623-dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions On Modelling and Computer Simulation, 8 (1) (1998), pp. 3-30. The space group can also be randomly selected by a random number generator algorithm. The symmetrical initialization selects from either an entire list of two hundred and thirty space groups or selects from a user-provided list of space groups. A symmetrical initialization unit cell is then configured based on the selected space group and a predetermined initial volume.
The symmetrical initialization preferably includes adding symmetrical random structures in each generation to improve population diversity and provide new crystal structures to be explored by the evolutionary algorithm. The symmetrical initialization includes unit cell splitting to provide a reduced number of degrees of freedom of the crystal structures. The symmetrical initialization introduces additional translational symmetry, i.e. pseudosymmetry, to the crystal structures. The symmetrical initialization uses up to two hundred and thirty space groups, allowing the user to produce a diverse first generation of crystal structures.
FIG. 2 illustrates a merging of atoms based on determined averages of coordinates of each atom, according to an aspect of the present invention. Specifically, FIG. 2 illustrates that when a distance (d) between atoms for atomic pairs is smaller than a user determined threshold (dmin), the atoms will merge. Merging the atoms by averaging the coordinates is equivalent to merging the atoms on symmetry elements that were used to produce the atoms.
Using the symmetrical initialization algorithm, a plurality of atoms are randomly placed on separate first Wyckoff positions, herein a first position, and coordinates of each of the atoms are multiplied by space group symmetry operations. The first position of each of the atoms includes all points of a space group for which site-symmetry groups are conjugate subgroups of the space group. If an inter-atomic distance of two or more symmetry-related atoms is within a user-defined threshold, the symmetry-related atoms are merged into one atom on a second position defined by averaging of coordinates of symmetry-related atoms.
A sum of the merged atoms and remaining atoms outside of the user-defined threshold for the inter-atomic distance is compatible with the space group symmetry operation. However, discarding the merged atoms from a crystal structure of the first generation of crystal structures may be necessary if the sum is incompatible with the space group symmetry operation. New atoms are added one at a time to ensure that no atoms, including symmetrically unrelated atoms, are too closely positioned.
To obtain an exact number of atoms necessary in a unit cell, certain atoms are placed on special Wyckoff positions having a correct multiplicity. The multiplicity of the Wyckoff position refers to a number of atoms obtained after multiplying the atom in the Wyckoff position using a group symmetry element. For example, if six atoms are needed to reach the number of atoms in the unit cell, atoms are input into positions with multiplicities of 1-6, but not with a multiplicity larger than six. Otherwise after multiplication, more atoms than are desired for the unit cell are obtained. This process of symmetrical initialization provides an unbiased procedure for sampling of each allowed space group and placing of atoms in positions that ensure distances of at least dmin between all atoms. If symmetrically related atoms are closer than the user-defined threshold, they are merged into the second position, as illustrated by FIG. 2. If symmetrically non-equivalent atoms are within a user-defined threshold for distance between atoms, the crystal structure is discarded without relaxation. The user-defined threshold is one of the user input parameters, which in a preferred embodiment, is set to a half sum of the covalent radii of the corresponding atoms.
Returning to step 315 of FIG. 1, local optimization of the chemical structure of the first generation of crystal structures according to the input parameters occurs. Local optimization, i.e. relaxation, does not break individual cell symmetry, but increases symmetry of the entire supergroup. Preferably, random displacement of atomic positions provides a possibility of breaking symmetry. Variation operators are also provided to break symmetry, and to remove bias that may have been caused by the selected space group.
After optimization, in step 320 the optimized first generation of crystal structures is input into a niching algorithm to select two separate groups of crystal structures from the optimized first generation of crystal structures. The niching algorithm calculates a set of conventional fitness functions and a set of fingerprint functions for each crystal structure of the first generation of crystal structures. The set of fitness functions allow the user to assess the quality of the crystal structures in the first generation of crystal structures according to a chemical property of the chemical structure that the user wants to optimize. The chemical property includes free energy, density, hardness, dielectric constant and bandgap. The set of fingerprint functions allows the user to assess the similarity between each of the crystal structures of optimal group of crystal structures and the parent group of crystal structures. A fingerprint function of a crystal structure is calculated according to Equation (1):




  
    
      
        
          
            
              F
              
                
                  A
                  i
                
                ⁢
                B
              
            
            ⁡
            
              (
              R
              )
            
          
          =
          
            
              
                ∑
                
                  B
                  j
                
              
              ⁢
              
                
                  δ
                  ⁡
                  
                    (
                    
                      R
                      -
                      
                        R
                        ij
                      
                    
                    )
                  
                
                
                  4
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      R
                      ij
                      2
                    
                    ⁡
                    
                      (
                      
                        
                          N
                          B
                        
                        /
                        V
                      
                      )
                    
                  
                  ⁢
                  Δ
                
              
            
            -
            1
          
        
        ,
      
    
    
      
        (
        1
        )
      
    
  




where V is the unit cell volume, NB is a number of type B atoms in the unit cell, Rij is inter-atomic distance between atoms Ai and Bj, δ(R−Rij) is a Gaussian-smeared delta function, which absorbs numerical errors and makes F(R) a smooth function. Gaussian smearing is controlled by an input parameter sigmaFing. F(R) is discretized over bins of width Δ to obtain a fingerprint vector FPAiB. Bins of width Δ are preferably specified by a user as an input parameter deltaFing. The fingerprint function input parameters are preferably set as 0.03 for sigmaFing, 0.08 for deltaFing, and 8.0 for RmaxFing.

The fingerprint function of Equation (1) is provided for an individual type Ai atoms relative to all Bj type atoms, referred to herein as atoms Ai and Bj, respectively, surrounding atom Ai with a sum running over all Bj atoms within a distance threshold Rmax, which preferably is user specified as an input parameter RmaxFing, with Rmax referring to a sum over all atoms Bj for which Rij<Rmax.
The niching algorithm includes determining a degree of similarity between a plurality of fingerprint functions from the set of fingerprint functions. Specifically, to determine a degree of similarity between crystal structures of Ai and Bj type atoms, a cosine distance dij between fingerprint functions FPi and FPj of crystal structures Ai and Bj, respectively, is calculated according to Equation (2):




  
    
      
        
          
            d
            ij
          
          =
          
            0.5
            ⁢
            
              (
              
                1
                -
                
                  
                    
                      FP
                      i
                    
                    ⁢
                    
                      FP
                      j
                    
                  
                  
                    
                      
                      
                        FP
                        i
                      
                      
                    
                    ⁢
                    
                      
                      
                        FP
                        j
                      
                      
                    
                  
                
              
              )
            
          
        
        ,
      
    
    
      
        (
        2
        )
      
    
  




where FPi is a fingerprint vector of crystal structure of Ai, ∥FPi∥ is a norm of the FPi fingerprint vector, FPj is a fingerprint vector of crystal structure of Bj, and ∥FPj∥ is a norm of a FPj fingerprint vector. As discussed above, the fingerprint vector is a result of discretization of the fingerprint function calculated according to Equation (1).

In Equation (2), the set of fingerprint functions, and thus the associated crystal structures, are considered identical if dij is less than input parameter toleranceFing or toleranceBestHM, which are a distance threshold given by the user. For example, when dij is smaller than 0.005, the crystal structures are considered identical, with toleranceFing and toleranceBestHM referring to input file names that provide a variable indicating the distance threshold between fingerprint functions. Where identical structures are determined, only those that have a best fitness function, i.e. structures having a lowest free energy, are selected to participate in creation of child crystal structures. Since pairs of parent crystal structures cannot be fully identical, the diversity of the next population improves by employing the niching algorithm.
In a preferred embodiment, step 320 further includes determining a value of the fitness function for each crystal structure of the first generation of crystal structures from a set of fitness functions. An optimal group of crystal structures is selected according to the value of the fitness function and a degree of similarity. The optimal group of crystal structures may be selected according to a user-defined threshold for the fitness function. For example, crystal structures having a free energy below the user-defined threshold are included in the optimal group of crystal structures. Alternatively, the user-defined threshold may define the optimal group of crystal structures as a percentage, such that the crystal structures having a top 20% fitness function value are included in the optimal group of crystal structures.
To improve diversity when selecting the optimal group of crystal structures, a first optimal crystal structure from the parent group of crystal structures is discarded when a distance between the fingerprint function of the first optimal crystal structure and the fingerprint function of a second optimal crystal structure is smaller than a user-defined distance threshold. The user-defined threshold for the distance between the fingerprint functions of the optimal group of crystal structures is input as input parameter toleranceBestHM.
The parent group of crystal structures is also selected according to the value of the fitness function. The parent group of crystal structures may be selected according to a user-defined threshold for free energy. For example, crystal structures having a free energy above the user-defined threshold for the optimal group of crystal structures are included in the parent group of crystal structures. Alternatively, the user-defined threshold may define the optimal group of crystal structures as a percentage, such that the crystal structures within the remaining 80% of fitness function values are included in the optimal group of crystal structures. However, the user-defined thresholds for the optimal group of crystal structures and the parent group of crystal structures may overlap.
To improve diversity when selecting the parent group of crystal structures, a first parent crystal structure from the parent group of crystal structures is discarded when a distance between the fingerprint function of the first parent crystal structure and the fingerprint function of a second parent crystal structure is smaller than the user-defined threshold. The user-defined threshold for the distance between the fingerprint functions of the parent group of crystal structures is input as input parameter toleranceFing. In a preferred embodiment, toleranceBestHM of a 10% increase in strictness requires more diverse crystal structures than toleranceFing.
Output of the niching algorithm of step 320 of FIG. 1 provides an optimal group of crystal structures that survive unchanged into a next generation. The optimal group of crystal structures is selected as the first selected group, which represents crystal structures having most desirable crystal structures, i.e. structures with lowest free energy, from the optimized first generation of crystal structures.
An example of an empirically obtained first threshold is provided in FIG. 3, which shows in the graph enthalpy of numerous crystal structures of boron using an aspect of the evolutionary algorithm employing a soft-mode mutation operator, searched at 40 gigapascal (GPa) with 28 atoms in the unit cell. The inserts of FIG. 3 show two crystal structures corresponding to structures marked with numbers 1 and 2, with structure 1 having a higher enthalpy than structure 2. As shown in the inserts, the lower energy structure 2 has an optimized crystal structure. In FIG. 3, an amplitude of displacement was set by the user to  ̃1.5 times an average bond length. As described above, when a displacement was determined to bring atoms too close together, the displacement amplitude was decreased to satisfy minimum-distance constraints. Once the crystal structure is input into the soft-mode mutation operator, a next lowest-frequency non-degenerate mode is used for subsequent mutation and mode degeneracy is determined using the fingerprint function as described herein.
Output of the niching algorithm also provides a parent group of crystal structures having crystal structures with a best fitness function, i.e. the lowest free energy, that differ by at least toleranceFing. Crystal structures with a poor fitness function are discarded. Crystal structures that are duplicates of crystal structures within the optimal group and the parent group of crystal structures are preferably also discarded. The evolutionary algorithm may be tuned using input parameters to allow a user to optimize desired properties, including free energy, density, hardness, dielectric constant and bandgap, of the chemical structure. These input parameters include sigmaFing, deltaFing, RmaxFing, toleranceFing, toleranceBestHM, and goodBonds. Approximately sixty to seventy optional input parameters may be employed depending on the properties of the chemical structure that the user wishes to tune.
The parent group of crystal structures selected in step 320 is output from the optimized first generation of crystal structures according to the fitness function. The parent group of crystal structures selected from the optimized first generation of crystal structures are chosen as a user defined function of the optimal group of crystal structures.
Thereafter, in step 335, a child group of crystal structures are produced from the parent group of crystal structures using a variation operator that includes one of a lattice mutation operator, a coordinate mutation operator, a spatial heredity operator and an atomic permutation operator, to produce a child group of crystal structures from the parent group of crystal structures according to user-defined proportions. For example, 25% of the parent group of crystal structures will be input into each of the lattice mutation operator, the coordinate mutation operator, the spatial heredity operator, and the atomic permutation operator to produce the child group of crystal structures.
Random variation operators provide a diverse population by exploring an entire search space. Randomness ensures an unbiased search and limits genetic drift. However, completely random variation operators are typically inefficient when applied to crystal structures with a unit cell size of over forty atoms. To improve the variation operators, a local order element is introduced. For individual atoms i=[1, . . . , N] in the unit cell, the local order element is calculated using the crystal structure's fingerprint function, with the local order element for atom i determined according to Equation (3):




  
    
      
        
          
            ∏
            i
            
              
            
          
          ⁢
          
            
          
          ⁢
          
            =
            
              
                
                  ∑
                  B
                
                ⁢
                
                  
                    
                      N
                      B
                    
                    N
                  
                  ⁢
                  
                    Δ
                    
                      
                        (
                        
                          V
                          /
                          N
                        
                        )
                      
                      
                        1
                        /
                        3
                      
                    
                  
                  ⁢
                  
                    
                      
                      
                        F
                        
                          
                            A
                            i
                          
                          ⁢
                          B
                        
                      
                      
                    
                    2
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        3
        )
      
    
  




where i=[1, . . . , N] denotes individual atoms in a unit cell, N is a total number of atoms in the unit cell, V is a unit cell volume, FPAiB is a fingerprint vector of Ai, and B represents all atom types present in the unit cell. Πi is the local order element for atom i and Πi characterizes environment quality and atomic position symmetry, with a smaller value of Πi for a given atom indicating a larger probability that the given atom will mutate.

In step 335 of FIG. 1, the local order element quantifies a degree of symmetry of the environment of a given atom and also quantifies the average degree of order of a fragment of a crystal structure. Thus, the less distorted and less defective regions of the crystal structure may be input into the spatial heredity operator and more defective regions of the crystal structures may be input into the lattice mutation operator and the atomic permutation operator. When the local order element is low, a number of defects and distortion are high. Where the local order element is high, the number of defects and distortion are low. However, a value of the local order element depends on factors that include atoms involved and atomic positions. If distortions or defects are favorable, the user may select those regions of the crystal structures accordingly.
Also in step 335, a plurality of slices are selected from a parent group of crystal structures in a spatial heredity operator as a function of an order-fitness function correlation coefficient according to an aspect of the present invention. Each slice is a portion of a crystal structure formed when the crystal structure is cut along two parallel planes. All atoms located between these planes form the slice. Specifically, two parallel cuts are made through the crystal structures and the portion of crystal structure between the parallel cuts is the slice. The spatial heredity operator preferably includes generating an amount of slices of a unit cell and selects a slice from slices having a highest average order. Specifically, in the spatial heredity operator, the slices of the unit cell are selected from a plurality of crystal structures from the parent group of crystal structures and the slices are then combined to produce the child group of crystal structures. The slices selected from the parent group of crystal structures in the spatial heredity operator function as an order-fitness correlation coefficient. To improve diversity of crystal structures, a user may incorporate portions of both the less distorted and defective regions, as well as the more distorted and defective regions. To determine which portions to incorporate, correlation between the average order of the crystal structures and the fitness value of the crystal structures is calculated. Depending on the degree of correlation, the degree to which the local order element influences the variation operators is determined. When there is a positive correlation, N, attempts to cut the slices are made from each parent and the most ordered slices are selected. That is, the number of slices of the unit cell from which the slice with the highest average order is selected is determined according to Equation (4):




  
    
      
        
          
            N
            s
          
          =
          
            L
            
              
                L
                char
              
              +
              
                
                  (
                  
                    L
                    -
                    
                      L
                      char
                    
                  
                  )
                
                ·
                
                  
                    cos
                    ⁡
                    
                      (
                      
                        
                          π
                          2
                        
                        ⁢
                        r
                      
                      )
                    
                  
                  2
                
              
            
          
        
        ,
      
    
    
      
        (
        4
        )
      
    
  




where Ns is the number of slices, r∈[−1;1] is a Pearson product-moment correlation coefficient, L is a thickness of a unit cell in a direction of the slice for the spatial heredity operator, and Lchar is a length of half of a cubic root of an average atomic volume, with Ns rounded to the nearest integer. Thus, N, changes from a value of one in the absence of correlation (r=0) to L/Lchar for perfect correlation.

According to an aspect of the present invention, the coordinate mutation operator preferably includes mutating atoms with lower order, and displaces each atom in the unit cell in a random direction. A degree of displacement is inversely proportional to the local order Πi of the atom.
Also in step 335, the variation operator includes a soft mode mutation operator, according to an aspect of the present invention. Using the soft mode mutation operator, atoms are moved along eigenvectors of softest modes, since low-frequency eigenmodes imply low curvature of an energy surface and likely also low energy barriers. The softest modes refer to modes with smallest eigenfrequencies. Specifically, the soft mode mutation operator includes diagonalising a dynamical matrix to obtain eigenfrequencies and eigenvectors, though the atoms need not move exactly along the eigenvector. To overcome an energy barrier and end up in a new free energy minimum, an approximate direction and sufficiently large mutation amplitude is provided to arrive at a new low-energy minimum. The soft mode mutation operator also includes selecting a lowest non-zero eigenfrequency and moving atoms along a corresponding eigenvector and setting an amplitude of displacement.
Since the user does not need an exact and computationally expensive ab initio dynamical matrix to calculate phonon modes, the dynamical matrix may be calculated from bond hardness coefficients while setting atomic masses to unity. The soft-mode mutation operator includes calculating the dynamical matrix according to Equation (5):




  
    
      
        
          
            
              D
              
                α
                ⁢
                
                  
                
                ⁢
                β
              
            
            ⁡
            
              (
              
                a
                ,
                b
              
              )
            
          
          =
          
            
              ∑
              m
            
            ⁢
            
              
                
                  ∂
                  2
                
                
                  
                    ∂
                    
                      α
                      a
                      0
                    
                  
                  ⁢
                  
                    ∂
                    
                      β
                      b
                      m
                    
                  
                
              
              ⁢
              
                (
                
                  
                    1
                    2
                  
                  ⁢
                  
                    
                      ∑
                      
                        i
                        ,
                        j
                        ,
                        l
                        ,
                        n
                      
                    
                    ⁢
                    
                      
                        
                          H
                          
                            i
                            ,
                            j
                          
                          
                            l
                            ,
                            n
                          
                        
                        ⁡
                        
                          (
                          
                            
                              r
                              
                                i
                                ,
                                j
                              
                              
                                l
                                ,
                                n
                              
                            
                            -
                            
                              r
                              
                                0
                                
                                  i
                                  ,
                                  j
                                
                              
                              
                                l
                                ,
                                n
                              
                            
                          
                          )
                        
                      
                      2
                    
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        5
        )
      
    
  




with coefficients α, β denoting coordinates (x,y,z); coefficients a, b, i, j describing an atom in a unit cell; and coefficients l, m, n describing a unit cell number. ri,jl,n is a distance between atom i in the unit cell l and atom j in the unit cell n, while r0i,jl,n is the corresponding bond distance. Hi,jl,n is a bond hardness coefficient between the atom i in the unit cell/and atom j in the unit cell n. For example, atoms are preferably treated as point particles and bonds as springs that connect the atoms with a stiffness determined by Hi,jl,n. Bonds with a valence strength greater than input parameter goodBonds are included in Hi,jl,n. Eigenvectors of Dαβ(a,b) correspond to lowest non-zero eigenvalues and determine a direction of the soft mode mutation operator.

Valence strength is a chemical property of the bond between two atoms. A higher valence strength indicates a stronger bond between atoms. The input parameter goodbonds sets a threshold that determines which bonds are considered sufficiently strong to participate in the dynamical matrix. The dynamical matrix, as explained above, is used to calculate the eigenvectors and eigenvalues. The eigenvalue together with corresponding eigenvector is referred to as a mode. A mode having a relatively small eigenvalue is considered a soft mode in which mutation consists of movement of atoms along the eigenvector.
In step 345 of FIG. 1, the child group of crystal structures that are output from step 335 are added to the optimal group of crystal structures and a next generation is output.
Following output of the next generation of crystal structures, the above-described steps are repeated a predetermined number of times for a predetermined number of generations, to output an optimized crystal structure, preferably in Vienna Ab initio Simulation Package (VASP) format describing the crystal structure in terms of unit cell distances to provide dimensions for each atom in the unit cell in each direction and providing coordinates of each atom within the unit cell.
According to an aspect of the present invention, a user may implement halting criteria to stop the evolutionary algorithm after the predetermined number of generations is achieved. Specifically, the user may implement the halting criteria to stop the evolutionary algorithm when the next generation crystal structures output from at step 345 attain the ground state for the crystal structure and free energy does not decrease with another repetition.
According to an aspect of the present invention, the method includes removing chemistry-preserving constraints on the variation operator in step 335. Specifically, the chemistry-preserving constraints on the variation operator require input of a set of individual atoms. By removing the chemistry-preserving constraints, molecules may be inputted without specifying stoichiometry. For example, inputting the set of atoms with chemistry-preserving constraints in place for sodium (Na), chlorine (Cl) and oxygen (O) may be inputted according to the following formula: xNa+yCl+zO, where x, y, and z are integers. However, with the chemistry-preserving constraints removed, a molecule including Na, Cl and O may be inputted according to the following formula: xNaCl+yNaO. Thus, with chemistry-preserving constraints in place, only one chemical structure is studied. However, when studying NaCl, without the chemistry-preserving constraints, all possible chemical compositions formed by Na and Cl such as pure Na, pure Cl, NaCl, Na2Cl, NaCl5 etc. are inputted.
According to an aspect of the present invention, the method includes introducing a chemical transmutation operator in step 335. The chemical transmutation operator changes the identities of atoms in the structure, thus changing the crystal structure chemical composition. For example, where a hypothetical crystal structures is a mixture of elements A and B having a general formula AxBy, where x and y and non-negative integers, the chemical transmutation operator picks a random atom A and puts a random atom B in atom A's position. The chemical transmutation operator allows the user to change the chemical structure of the crystal structures and thus study a more diverse population of the chemical structures
The method also includes determining the fitness function of the chemical structure as a difference between free energy per atom of the chemical structure and free energy per atom of all possible decompositions of the chemical structure according to known values of free energy. As described above, the fitness function of each crystal structure may be evaluated at step 320 of FIG. 1 by the free energy of a crystal structure. Alternatively, the crystal structure may be evaluated by comparison to the predetermined structure, or the free energy of the predetermined structure may have been previously calculated and saved in a history of a computer system running the evolutionary algorithm.
The embodiments described above provide a cumulative effect resulting in a method outperforming conventional methods. Other methods may successfully predict crystal structures with 15-40 atoms. However, aspects of the present invention successfully predict crystal structures with up to 160 atoms in the unit cell. Optimizing properties of a crystal structure and varying the crystal structure's stoichiometry provides steps forward to a fully computational material design.
Another aspect of the invention provides a method for predicting an optimized surface structure by inputting characterization information of a chemical structure and input parameters, with the characterization information including a number of atoms, a surface energy and a volume of a unit cell. A first convex hull of a first generation of surface structures is generated from the characterization information using a docking algorithm. Surface structures of the first generation of surface structures include a bulk substrate layer, an adatom layer and a vacuum layer. The first generation of surface structures is restricted based on a convex hull algorithm according to a user-defined chemical potential constraint.
The docking algorithm includes scanning the adatom layer for vacant sites and adding atoms to the vacant sites within the adatom layer based on predetermined conditions that include a coordination number and a distance from adjacent atoms. The docking algorithm includes outputting a configuration of the atoms added to the vacant sites.
The method includes outputting a second convex hull of the first generation of surface structures and optimizing the second convex hull of the first generation of surface structures according to the input parameters. The optimized second convex hull is input into a niching algorithm to select an optimal group of surface structures and a parent group of surface structures based on a fitness function. A child group of surface structures is produced from the parent group of surface structures by applying a variation operator to the adatom layer of the surface structures of the first generation of surface structures. The child group of surface structures is added to the optimal group of surface structures to form a second generation of surface structures. The optimizing through adding steps are repeated for a predetermined number of generations, surface structures having a chemical potential above a user-defined threshold are discarded.
An example of an application of an aspect of the present invention is provided using characterization information of the chemical structure of thirteen atoms per unit cell, an atomic number of 42 for each atom (molybdenum), goodbonds input parameter set to 0.7, to include bonds with valence strength above 0.7 in the calculation of the dynamical Equation (5) above. With the fitness function set to optimize enthalpy, the first generation of crystal structures and subsequent generations of crystal structures are set to include five crystal structures, and the optimal group of crystal structures is set to include the two crystal structures with the lowest enthalpy to survive in the next generation.
The niching algorithm is set to select 80% of the optimized first generation of crystal structures to be the parent group of crystal structures and 20% of the optimized first generation of crystal structures to be the optimal group of crystal structures. The variation operators are set to produce a child group of crystal structures from the parent group of crystal structures according to proportions of 40% produced through the spatial heredity operator, 20% randomly produced according to a user-defined space group, and 40% produced by the soft-mode mutation operator. The user-defined space group in this example is set to a space group of one, which is a no symmetry group to demonstrate that a symmetrical crystal structure is obtained from non-symmetrical crystal structures.
A distance of 0.003 is set for input parameter toleranceFing. Thus, where the distance between crystal structures is less than 0.003 the crystal structures are considered identical, duplicate crystal structures are discarded when selecting the parent group of crystal structures. The input parameter toleranceBestHM is set to a distance of 0.030, such that structures having a distance less than 0.030 are considered identical when selecting the optimal group of crystal structures using the niching algorithm. Accordingly, with respect to the current example, the degree of similarity between the fingerprint functions of each of the crystal structures calculated according to Equation (2) conforms to the input parameters toleranceFing and toleranceBestHM.
The input parameters and the characterization information are input into the evolutionary algorithm and data for the non-optimized first generation of crystal structures are output and are listed in VASP format as crystal structures N1-N5, an example of which is provided in Table 1.









TABLE 1









Structure N 1



1.0



14.617033312 0 0



0 14.521428022 0



0 0 12.933782102



13



Direct



0.34275080949 0.60067489226 0.51597991576



0.42693784055 0.43233012956 0.51201560899



0.38475415012 0.46801241756 0.4702635557



0.49396977542 0.61290144978 0.48127492028



0.65724919051 0.51577858163 0.41950507652



0.49158419709 0.3682318986 0.46876612343



0.47726348379 0.53256513396 0.38735769323



0.42704225922 0.65499260868 0.54716383867



0.62413621182 0.44704387635 0.48681339032



0.47576381044 0.4502255069 0.58829288624



0.4949307235 0.34500739132 0.61264230677



0.648485505 0.5248090586 0.51592664214



0.57630076588 0.47721237507 0.40052306093



Structure N 2



1.0



16.755358566 0 0



0 13.791490047 0



0 0 13.005954767



13



Direct



0.31161480925 0.52508624971 0.52973596117



0.66372045684 0.63673250801 0.40217456125



0.70099117961 0.47283959975 0.56568666457



0.62103072508 0.36326749199 0.4974762089



0.38912804524 0.43208930111 0.38520816733



0.34337781118 0.41532797356 0.44304752931



0.48600752703 0.57624560642 0.49295706406



0.43518758937 0.63432610544 0.52165204311



0.4740301618 0.38546571547 0.50855865003



0.54002495747 0.4359034668 0.61479183267



0.29900882039 0.60110959954 0.54598513559



0.69581038906 0.50625255366 0.44308602273



0.62338799011 0.5905228276 0.53508858353



Structure N 3



1.0



17.872833718 0 0



0 13.892469368 0



0 0 13.65864643



13



Direct



0.4560701613 0.63937296767 0.60630211741



0.6911769326 0.57130883343 0.40575981942



0.62786029587 0.5216820855 0.50384886632



0.60545404631 0.46243148482 0.49935189243



0.55000351136 0.44965049769 0.55546549442



0.57434168116 0.5805028261 0.51220224417



0.49583555995 0.36062703233 0.47058090169



0.28031369167 0.41235704155 0.50009898278



0.42561147677 0.55071061313 0.40692001188



0.62043732053 0.487343122 0.36680062153



0.68862200233 0.41135915493 0.63319937847



0.71968630833 0.5583697667 0.54898224825



0.34505831776 0.58176591244 0.50342147577



Structure N 4



1.0



17.229339505 0 0



0 13.821712325 0



0 0 11.806010304



13



Direct



0.65627263063 0.39731321696 0.47500045107



0.29078305634 0.42803261955 0.50466649739



0.33646253658 0.36247317858 0.49157861563



0.34211167368 0.56558865977 0.42436012431



0.42235818453 0.41463987259 0.56849405662



0.43922050624 0.54150977596 0.55689058013



0.70921694366 0.53488275335 0.57563987569



0.45360530648 0.37882884072 0.497041593



0.38054900272 0.62350928477 0.45778493115



0.60631416794 0.61713650597 0.45789853632



0.53925715817 0.53954083369 0.43455385255



0.47217788542 0.63752682142 0.53180854887



0.60351494512 0.44756698446 0.44529285927



Structure N 5



1.0



15.205211223 0 0



0 14.775543346 0



0 0 14.419737856



13



Direct



0.38874464235 0.66092617491 0.39976428763



0.32949229883 0.53847443139 0.43314107093



0.67050770117 0.51901684249 0.45277385946



0.38212310109 0.48364384941 0.54119190229



0.50175170345 0.52101089266 0.54638371385



0.4456361569 0.39817263448 0.53123449082



0.60384289841 0.5495005888 0.53962185561



0.5623027444 0.43306177342 0.34744043547



0.53664899258 0.33907382509 0.43722021453



0.59636428118 0.59593586209 0.45121622569



0.38646267806 0.36581094694 0.54428001367



0.5291069569 0.48889432875 0.65255956453



0.3854326954 0.49024366943 0.3957966032










The first generation of crystal structures is then locally optimized according to the input parameters, and data for the optimized first generation of crystal structures are output. Data for an example of an optimized first generation of crystal structures is listed in VASP format as crystal structures EA1-EA5 is provided in Table 2.









TABLE 2









EA1 17.8 15.8 12.8 90 90 90 Sym. group: no SG



1.0



17.770965 0 0



9.6874601234e−16 15.820823 0



7.8459421988e−16 7.8459421988e−16 12.813396



13



Direct



0.6525712458 0.57199584533 0.40160214418



0.52016836218 0.68332745459 0.44658890195



0.60682046829 0.6056319057 0.61960216258



0.55620914696 0.42869151644 0.60279441388



0.39318094454 0.394374336 0.61960452973



0.44379276299 0.57131233238 0.60279327843



0.71808004903 0.46913589957 0.5739877002



0.63257452486 0.385147248 0.40238488723



0.34742652961 0.42800068861 0.40159864812



0.49999813809 0.49999816603 0.40606264615



0.36742495069 0.61484968561 0.40238790508



0.47983172096 0.31667006031 0.44660249036



0.28192115597 0.53086486144 0.57399029211



EA2 17.8 15.3 13.4 90 90 90 Sym. group: no SG



1.0



17.799065 0 0



9.3511016952e−16 15.271508 0



8.1996973471e−16 8.1996973471e−16 13.391122



13



Direct



0.61692295919 0.47368925441 0.5983877378



0.40829474418 0.32730504101 0.43271598659



0.31381146103 0.6351715604 0.54664194311



0.44249725359 0.66331333703 0.41403482391



0.66149774595 0.48083942359 0.3837914316



0.75086055862 0.57720444044 0.53725200481



0.50108054923 0.48379303729 0.43454594887



0.48130655778 0.37251056402 0.62664767057



0.59558965757 0.63843994069 0.48980911129



0.46568116352 0.57210806352 0.61796693732



0.58219624574 0.31943713745 0.46149496868



0.34402354626 0.50859143597 0.37490456194



0.33623755733 0.44759676418 0.5818068735



EA3 17.3 15.3 14.6 90 90 90 Sym. group: no SG



1.0



17.287583 0 0



9.3450078527e−16 15.261556 0



8.9152872511e−16 8.9152872511e−16 14.559769



13



Direct



0.45350715812 0.33569220312 0.62484484251



0.69342144498 0.40873573253 0.46111228076



0.55305015057 0.47758157317 0.55549315989



0.56718193973 0.64255192282 0.44648827419



0.42158264756 0.60094556506 0.54456121027



0.54773614652 0.30495132712 0.45668614861



0.42586573301 0.59269947059 0.34112621405



0.27985184107 0.54882691403 0.44179555133



0.41416714374 0.42724392024 0.44849619975



0.5602399359 0.47192747831 0.35107886205



0.56044335454 0.64839971864 0.65292847189



0.70024504881 0.57978207705 0.5565493927



0.32270745545 0.46066209732 0.618839392



EA4 17.1 15 13.9 90 90 90 Sym. group: no SG



1.0



17.074984 0 0



9.1594793735e−16 14.958565 0



8.5406769801e−16 8.5406769801e−16 13.947984



13



Direct



0.62818567406 0.33492697043 0.53495589539



0.27757980092 0.60219520167 0.50522498104



0.27758240213 0.39779920163 0.5052379321



0.40349749304 0.49999626018 0.41125628994



0.3851729963 0.50000163042 0.63026077782



0.53900963469 0.49999804808 0.54335027967



0.6907561917 0.50000094484 0.64067648015



0.44646638584 0.33693090598 0.52379698044



0.44646250082 0.66306640601 0.52379375635



0.68521868552 0.50000676528 0.4283625765



0.54594476035 0.60068864752 0.35905975469



0.62817400275 0.66507507046 0.53496718206



0.54594947189 0.3993139475 0.35905711386



EA5 17 15 15.1 90 90 90 Sym. group: no SG



1.0



16.954574 0 0



9.2056706015e−16 15.034001 0



9.2547752642e−16 9.2547752642e−16 15.114195



13



Direct



0.56859568752 0.50000789817 0.63487002953



0.7354981758 0.5000030579 0.57403048908



0.32649293359 0.39684501264 0.49407146323



0.61603148218 0.60115142267 0.47069874252



0.61603382961 0.39884972267 0.47070539354



0.46941855696 0.50000026977 0.47620905357



0.46809499532 0.33324169347 0.38117761351



0.39218169023 0.50000155303 0.64896647229



0.3264891872 0.60314811264 0.49407211318



0.47820283484 0.33719524121 0.58106041202



0.46809048198 0.66675249347 0.38116769426



0.55667202531 0.49999388114 0.31191933242



0.47819811946 0.66280964122 0.58105119086










FIG. 4 shows on a top row thereof structures of a non-optimized first generation above respective crystal structures optimized according to an aspect of the present invention. Specifically, FIG. 4 shows the crystal structures 1-5 before and after step 315.
Enthalpies are provided for the optimized first generation of crystal structures 1-5 and the optimized second generation of crystal structures 6-12 in Table 3:







TABLE 3





Structure - Enthalpy

















 1 −39.6369



 2 −39.1438



 3 −38.8497



 4 −40.4333



 5 −41.472



 6 −41.472



 7 −40.1281



 8 −41.472



 9 −40.4333



10 −44.3268



11 −41.472



12 −39.6369










The niching algorithm selects crystal structures 1, 2, 4 and 5 from the first generation of crystal structures and outputs the parent group of crystal structures. The niching algorithm selects crystal structures 1 and 5, and outputs the optimal group of crystal structures. In the present example, crystal structure 4 has a next lowest enthalpy; however, crystal structure 4 has distance less than 0.030 to crystal structure 5 and is considered identical.
Parent structures 1, 2, 4 and 5 produce five children, according to the variation operator proportions described above, with child 1 created by applying heredity operator to parent crystal structures 5 and 1; with child 2 created by applying heredity operator to parent crystal structures 4 and 5; with child 3 created by using symmetrical initialization; child 4 created by applying soft-mode mutation operator to parent crystal structure 4; and child 5 created by applying soft-mode mutation operator to parent crystal structures 2, with child 3 from the first generation of crystal structures being discarded in step 320 of FIG. 1.
Thus, five child crystal structures are output and the two structures from the optimal group are added. The second generation of non-optimized crystal structures are output and are listed as crystal structures N6-N12 in Table 4.









TABLE 4









Structure N 6



1.0



7.434777459 0 0



3.1875652647e−16 5.2056891292 0



3.2639921656e−16 3.2639921656e−16 5.3305037303



13



Direct



0.35601782179 0.21999031649 0.72365372813



0.0013875360825 0.35168892397 0.47954530038



0.34815833908 0.33950706074 0.18301109379



0.75201607784 0.17442862788 0.88594912418



0.99861246392 0.26047995721 0.44603991624



0.74308416326 0.36588076285 0.0018377687599



0.63460232918 0.0017654227859 0.3826907669



0.22530006854 0.93921617565 0.45095832926



0.87838815241 0.7998331413 0.59975675916



0.55638077682 0.64104108852 0.33032248737



0.53241601781 0.99789585107 0.79519900132



0.5192915315 0.82087704544 0.11699646699



0.5347037152 0.61914814976 0.99816223124



Structure N 7



1.0



5.5695669066 0 0



3.4469176115e−16 5.6292436545 0



3.8288600588e−16 3.8288600588e−16 6.253003007



13



Direct



0.52014244419 0.43596178505 0.62820272629



0.410268354 0.15384108053 0.98737601055



0.62993443698 0.23710191558 0.22641786853



0.0018405766766 0.37509777733 0.76141458703



0.12010866469 0.40961134373 0.31429903343



0.28974847262 0.0016928872934 0.54633715037



0.82790860747 0.90653404607 0.30727762253



0.2349016332 0.54604975843 0.80660628746



0.50079740595 0.50643374956 0.39489005514



0.34469099502 0.99813173789 0.52649336906



0.73219364156 0.73426062841 0.77682878878



0.0017521756741 0.58921484218 0.35927875051



0.99824782433 0.40013883807 0.45891625438



Structure N 8



1.0



16.238676007 0 0



0 14.407927802 0



0 0 12.531716197



13



Direct



0.35913067639 0.44632977628 0.48358248699



0.69147731024 0.62709662529 0.44513092032



0.59330626683 0.57152396383 0.46673827878



0.54625823392 0.42404251942 0.52954266081



0.5350561228 0.48427490168 0.51134070527



0.31378694078 0.5116349745 0.52040329729



0.30852268976 0.64933526783 0.43618804072



0.43307431708 0.55233018854 0.39978562561



0.57393896999 0.51966411599 0.59119828186



0.47554065099 0.65227477062 0.60021437439



0.64256451304 0.60010889298 0.4119827101



0.38253297965 0.36120829513 0.45214144955



0.6888131181 0.34772522938 0.46947705006



Structure N 9



1.0



8.6083183614 0 0



0 5.1919965502 0



0 0 4.570734745



13



Direct



0.21777370899 0.0034206320098 0.41095996739



0.99878140749 0.77186385949 0.6606726934



0.99883833293 0.22799045138 0.66078817445



0.6704304906 0.49992878494 0.59813043671



0.86704781869 0.50009682679 0.0021878320572



0.36852294857 0.49997899517 0.11462230699



0.0011616670737 0.49994145979 0.32255000757



0.59499215501 0.0019260413414 0.1427198497



0.5949618643 0.99807395866 0.14270574469



0.23848107124 0.49998305499 0.99781216794



0.50524699804 0.75114632235 0.74392209214



0.21777510568 0.99647896401 0.41118278287



0.50521980283 0.24880620844 0.74386491312



Structure N 10



1.0



8.2037135946 0 0



0 5.1416561598 0



0 0 5.2389359512



13



Direct



0.77394291061 0.5137507588 0.71522513365



0.33415886159 0.9404365867 0.35291088701



0.0012189601556 0.060747308981 0.56643887416



0.35069544107 0.0019448986259 0.37435769195



0.57059561275 0.61397795063 0.0019087845496



0.99878103984 0.0702259486 0.30635747728



0.43197393888 0.54060168524 0.57324061994



0.48730679547 0.85624413624 0.91596712181



0.68190414353 0.064260524634 0.66275167505



0.3851347217 0.30187580852 0.99809121545



0.70105786731 0.99805510137 0.46500553778



0.14766950997 0.46546217422 0.078894547351



0.14765817852 0.64260824029 0.6305720181



Structure N 11



1.0



6.9545731638 0 0



0 5.0340017008 0



0 0 5.1141961962



13



Direct



0.40832996094 0.49996773184 0.9563848597



0.0014379027676 0.49998218728 0.77658325592



0.9985529639 0.80806276567 0.54027704821



0.29268610014 0.19790350168 0.47120268247



0.29268037734 0.80207571713 0.4712223385



0.65011417395 0.49999051399 0.48748753202



0.65334088869 0.99801350882 0.2066371968



0.83841015438 0.49998668156 0.99804465851



0.99856209723 0.19194040495 0.54027896902



0.62869895751 0.98620627387 0.79735907721



0.65335189176 0.0019864911842 0.20660788202



0.43739869147 0.50000959359 0.001955341488



0.62871045317 0.013761784124 0.79733182552



Structure N 12



1.0



7.770964423 0 0



0 5.8208217366 0



0 0 2.8133956913



13



Direct



0.15109510036 0.3043140238 0.0035703461247



0.45387952746 0.001717970495 0.20845910164



0.25571988328 0.21289219683 0.99643479545



0.3714599602 0.69381099263 0.91988518648



0.74427964144 0.78708408397 0.99644557641



0.6285384277 0.30617179197 0.91988001517



0.0012868415625 0.58388434381 0.78868720712



0.19682443441 0.81216303893 0.0071352895936



0.84891274257 0.69568864243 0.0035544235853



0.50000563572 0.50000160748 0.023885361989



0.80317952059 0.18783854102 0.0071490341644



0.54612303808 0.99828202951 0.20852098904



0.99871315844 0.41610683338 0.78869901179










FIG. 5 shows a non-optimized second generation and an optimized second generation of crystal structures, according to an aspect of the present invention. FIG. 5 shows crystal structures 6-10 before and after step 315. Crystal structures 11 and 12 are part of the optimal group of crystal structures and are therefore not changed during optimization. Thus, crystal structures 11 and 12 are the same as the optimized first generation of crystal structures 1 and 5 in FIG. 4. After local optimization of the second generation of crystal structures, the evolutionary algorithm stops, since the lowest enthalpy crystal structure for the chemical structure is obtained by locally optimizing the second generation of crystal structure 5. The second generation of non-optimized crystal structures are output, and are listed as crystal structures EA6-EA12 in Table 5.









TABLE 5









EA6 17 15 15.1 90 90 90 Sym. group: no SG



1.0



16.9545 0 0



9.205741631e−16 15.0341170



9.2546619844e−16 9.2546619844e−16 15.11401



13



Direct



0.43141461947 0.50000285522 0.63486483185



0.26450543497 0.49999990193 0.57404617832



0.38396554687 0.60115225448 0.47070904337



0.60782741588 0.49999806941 0.64896128843



0.67351194063 0.60315237749 0.49406593874



0.53190166032 0.66675749473 0.38117117302



0.52180540994 0.66280623978 0.58105606483



0.38396347576 0.39885255448 0.47070818989



0.67350787009 0.39684087749 0.49406398024



0.53058385991 0.49999977415 0.47620356366



0.53189540795 0.33324159473 0.38117105513



0.44331550178 0.50000196634 0.31192223567



0.52180185644 0.33719403978 0.58105645685



EA7 15.4 14.9 15.2 90 90 90 Sym. group: no SG



1.0



15.384205 0 0



9.1280371793e−16 14.907216 0



9.2846597077e−16 9.2846597077e−16 15.163



13



Direct



0.53064703906 0.50001606351 0.45725916187



0.41922786414 0.49998273347 0.29867475304



0.55371143256 0.33687446222 0.56692441941



0.34248637406 0.49996664016 0.48032424033



0.3618894285 0.33808114463 0.59197968777



0.43657741037 0.33606835335 0.41074639471



0.65696953722 0.50003155611 0.60686531201



0.43649481518 0.66391125848 0.41074480732



0.46420195154 0.49999469143 0.6378579777



0.55365325477 0.66315206598 0.56691473203



0.69114728879 0.60237034172 0.43986471075



0.36182961885 0.66186114847 0.59198350028



0.69116398496 0.39768954048 0.43986030278



EA8 17 15 15.1 90 90 90 Sym. group: no SG



1.0



16.954589 0 0



9.2057446926e−16 15.034122 0



9.2547562822e−16 9.2547562822e−16 15.114164



13



Direct



0.38396565335 0.39885224393 0.4707053257



0.67350424572 0.60316399151 0.49407245614



0.52179329997 0.66280546312 0.58105407853



0.53190560482 0.3332395711 0.38117929548



0.53058394943 0.49999992928 0.47620523902



0.44332921898 0.49998865632 0.31191875936



0.26450346757 0.50000183398 0.5740443011



0.43141147886 0.49999676455 0.63486286215



0.53189745881 0.6667556711 0.38116858193



0.38396374348 0.60114254394 0.47069722075



0.60782288146 0.50000257652 0.648964421



0.52180583778 0.33719556313 0.58105750361



0.67351315975 0.39685519152 0.49406995523



EA9 17.1 15 13.9 90 90 90 Sym. group: no SG



1.0



17.074928 0 0



9.1594695764e−16 14.9585490



8.540680654e−16 8.540680654e−16 13.94799



13



Direct



0.6281914205 0.6650721694 0.4650458814



0.27758014872 0.39780461753 0.49476964367



0.27758042787 0.60220051753 0.49476908542



0.40349694131 0.50000431757 0.58874285849



0.38517353428 0.50000305403 0.36973895937



0.53901003707 0.50000225904 0.45664985197



0.69075483395 0.50000049649 0.35932484467



0.44646802107 0.66306994327 0.47620248973



0.44646195433 0.33693614327 0.47620342311



0.68521734076 0.49998785804 0.57163684494



0.54594185325 0.39931042723 0.64094173107



0.62817235417 0.3349232694 0.46503361396



0.54595113272 0.60068492723 0.6409407722



EA10 15.5 15.5 15.2 90 90 90 Sym. group: no SG



1.0



15.533712 0 0



9.5015973157e−16 15.517286 0



9.3241625272e−16 9.3241625272e−16 15.227513



13



Direct



0.67753484184 0.46966096512 0.45202530139



0.42917676941 0.39029628042 0.63541654178



0.38468740448 0.54933130863 0.35967684728



0.44265170729 0.67726664684 0.49884391904



0.47015064315 0.57897802065 0.66926327492



0.62363740871 0.62802838512 0.55591812852



0.50000075557 0.49999983477 0.49999915137



0.55734680584 0.3227320959 0.50115279577



0.57082194192 0.60970146009 0.36458009496



0.52985086239 0.42102068004 0.33073654889



0.61530979513 0.45066673997 0.64032488026



0.32247036269 0.53034363823 0.54797980639



0.37636070158 0.37197394423 0.44408270943



EA11 17 15 15.1 90 90 90 Sym. group: no SG



1.0



16.954573164 0 0



0 15.034001701 0



0 0 15.114196196



13



Direct



0.4314043091 0.50000789817 0.63487001886



0.26450181259 0.5000030579 0.57403048322



0.67350707497 0.39684501745 0.4940714637



0.3839685121 0.60115141795 0.47069874484



0.38396616467 0.39884972738 0.47070539586



0.53058144455 0.50000026977 0.47620905545



0.53190500626 0.33324170124 0.38117762292



0.60781831509 0.50000155303 0.6489664605



0.67351082136 0.60314810783 0.49407211365



0.52179716623 0.3371952488 0.58106040561



0.53190951959 0.6667524857 0.38116770366



0.44332797189 0.49999388114 0.3119193473



0.52180188162 0.66280963363 0.58105118444



EA12 17.8 15.8 12.8 90 90 90 Sym. group: no SG



1.0



17.770964423 0 0



0 15.820821737 0



0 0 12.813395691



13



Direct



0.34742874924 0.57199585108 0.40160214181



0.47983163717 0.68332746923 0.44658890066



0.39317952824 0.60563191414 0.61960216547



0.44379085122 0.42869151074 0.60279441635



0.60681905892 0.39437432757 0.61960453261



0.55620723883 0.57131233808 0.60279328091



0.28191994389 0.4691358971 0.57398770198



0.36742547083 0.38514723883 0.40238488488



0.65257347534 0.42800068286 0.40159864575



0.50000186191 0.49999816603 0.40606264389



0.63257505362 0.61484969478 0.40238790273



0.52016827969 0.31667004567 0.44660248907



0.71807885111 0.5308648639 0.57399029389










In a preferred aspect, a system for predicting an optimized crystal structure using an evolutionary algorithm includes a processor configured to execute the above described method. Specifically, the methods of the present invention are implemented in systems that use software run on a computer processor to carry out the above described methods. While in preferred embodiments, the methods are carried out in an automated format, entirely within the computer processor, it should be understood that one or more components may be carried out by a human and that the methods may involve human interaction or intervention at one or more points.
The computer processor for conducting aspects of the methods of the present invention may be housed in devices that include desktop computers, scientific instruments, hand-held devices, personal digital assistants, phones, a non-transitory computer readable medium, and the like. The methods need not be carried out on a single processor. For example, one or more steps may be conducted on a first processor, while other steps are conducted on a second processor. The processors may be located in the same physical space or may be located distantly. In some such embodiments, multiple processors are linked over an electronic communications network, such as the Internet. Preferred embodiments include processors associated with a display device for showing the results of the methods to a user or users, outputting results as a video image of a predicted crystal structure that include coordinates of atoms, molecules or motifs. The processors may be directly or indirectly associated with information databases, which include crystal structure databases. As used herein, the terms processor, central processing unit, and CPU are used interchangeably and refer to a device that is able to read a program from a computer memory, e.g. ROM or other computer memory, and perform a set of steps according to the program. The terms computer memory and computer memory device refer to any storage media readable by a computer processor. Examples of computer memory include, but are not limited to, RAM, ROM, computer chips, digital video discs, compact discs, hard disk drives and magnetic tape. Also, computer readable medium refers to any device or system for storing and providing information, e.g., data and instructions, to a computer processor, DVDs, CDs, hard disk drives, magnetic tape and servers for streaming media over networks. As used herein, encode refers to the process of converting one type of information or signal into a different type of information or signal to, for example, facilitate the transmission and/or interpretability of the information or signal. For example, image files can be converted into, i.e. encoded into, electrical or digital information. Likewise, light patterns can be converted into electrical or digital information that provides and encoded video capture of the light patterns.
While the invention has been shown and described with reference to certain aspects thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the appended claims and equivalents thereof.

## Claims

1. A method for predicting an optimized crystal structure using an evolutionary algorithm, the method comprising:
inputting characterization information of a chemical structure and input parameters;
generating a first generation of crystal structures from the characterization information using symmetrical initialization;
optimizing, by a processor, the chemical structure of the first generation of crystal structures according to the input parameters;
inputting the crystal structures of the optimized first generation into a niching algorithm to select an optimal group of crystal structures and a parent group of crystal structures based on a fitness function;
producing a child group of crystal structures from the parent group of crystal structures using a variation operator;
adding the child group of crystal structures to the optimal group of crystal structures to form a next generation of crystal structures; and
repeating the optimizing through adding steps for a predetermined number of generations,
wherein the variation operator includes a local order element determined by:





  
    
      ∏
      i
      
        
      
    
    ⁢
    
      
    
    ⁢
    
      =
      
        
          
            ∑
            B
          
          ⁢
          
            
              
                N
                B
              
              N
            
            ⁢
            
              Δ
              
                
                  (
                  
                    V
                    /
                    N
                  
                  )
                
                
                  1
                  /
                  3
                
              
            
            ⁢
            
              
                
                
                  F
                  
                    
                      A
                      i
                    
                    ⁢
                    B
                  
                
                
              
              2
            
          
        
      
    
  
  ,



wherein Πi is the local order element for atom i, i=[1, . . . , N] denotes individual atoms in a unit cell, N is a total number of atoms in the unit cell, V is a unit cell volume, FPAiB is a fingerprint vector of atom Ai, and B represents atom types in the unit cell.

2. The method of claim 1, wherein the symmetrical initialization comprises:
splitting the unit cell having the chemical structure of the input characterization information;
selecting a space group compatible with the unit cell;
configuring a symmetrical initialization unit cell according to the selected space group and a predetermined volume of the unit cell;
locating a plurality of atoms of the symmetrical initialization unit cell at a plurality of positions;
multiplying coordinates of each of the plurality of atoms by space group symmetry operations;
merging the plurality of atoms to a new position by averaging of coordinates when an inter-atomic distance between the plurality of atoms is determined to be within a user-defined threshold to produce a merged atom; and
discarding the merged atom when the merged atom is determined to be incompatible with the space group symmetry operation.

3. The method of claim 1, wherein the niching algorithm further comprises:
calculating a set of fitness functions and a fingerprint function for each crystal structure of the first generation of crystal structures;
determining a degree of similarity between the fingerprint function;
determining a value of a fitness function for each crystal structure of the first generation of crystal structures from the set of fitness functions;
selecting the optimal group of crystal structures according to the value of the fitness function and the degree of similarity;
selecting the parent group of crystal structures according to the value of the fitness function; and
discarding a first parent crystal structure from the parent group of crystal structures when a distance between the fingerprint function of the first parent crystal structure and the fingerprint function of a second parent crystal structure is smaller than a user-defined threshold.

4. The method of claim 3, wherein the set of fingerprint functions is determined by:




  
    
      
        F
        
          
            A
            i
          
          ⁢
          B
        
      
      ⁡
      
        (
        R
        )
      
    
    =
    
      
        
          ∑
          
            B
            j
          
        
        ⁢
        
          
            δ
            ⁡
            
              (
              
                R
                -
                
                  R
                  ij
                
              
              )
            
          
          
            4
            ⁢
            
              
            
            ⁢
            π
            ⁢
            
              
            
            ⁢
            
              
                R
                ij
                2
              
              ⁡
              
                (
                
                  
                    N
                    B
                  
                  /
                  V
                
                )
              
            
            ⁢
            Δ
          
        
      
      -
      1
    
  
  ,



wherein NB is a number of type B atoms in the unit cell, Rij is inter-atomic distance between atoms Ai and Bj, and β(R−Rij) is a Gaussian-smeared delta function.

5. The method of claim 4, wherein a degree of similarity between a plurality of fingerprint functions among the set of fingerprint functions is determined by:




  
    
      d
      ij
    
    =
    
      0.5
      ⁢
      
        (
        
          1
          -
          
            
              
                FP
                i
              
              ⁢
              
                FP
                j
              
            
            
              
                
                
                  FP
                  i
                
                
              
              ⁢
              
                
                
                  FP
                  j
                
                
              
            
          
        
        )
      
    
  
  ,



wherein FPi and FPj are fingerprint vectors, ∥FPi∥ and ∥FPj∥ are respective norms of the fingerprint vectors.

6. The method of claim 1, further comprising:
removing chemistry-preserving constraints on the variation operator;
introducing a chemical transmutation operator; and
determining the fitness function of the chemical structure as a minimal difference between free energy per atom of the chemical structure and free energy per atom of each decomposition of the chemical structure.

7. The method of claim 1, wherein the variation operator comprises at least one of a lattice mutation operator, a coordinate mutation operator, a spatial heredity operator, a soft-mode mutation operator and an atomic permutation operator.

8. The method of claim 7, wherein the spatial heredity operator further comprises generating a number of slices of the unit cell and selecting a slice with a highest average order.

9. The method of claim 8, wherein the number of slices with the highest average order is determined by:




  
    
      N
      s
    
    =
    
      L
      
        
          L
          char
        
        +
        
          
            (
            
              L
              -
              
                L
                char
              
            
            )
          
          ·
          
            
              cos
              ⁡
              
                (
                
                  
                    π
                    2
                  
                  ⁢
                  r
                
                )
              
            
            2
          
        
      
    
  
  ,



wherein r∈[−1;1] is a Pearson product-moment correlation coefficient, L is a thickness of a unit cell in a direction of the slice, and Lchar is half of a cubic root of an average atomic volume.

10. The method of claim 7, wherein the coordinate mutation operator mutates atoms with a lower order.

11. The method of claim 7, wherein the soft-mode mutation operator comprises:
calculating a dynamical matrix;
diagonalising the dynamical matrix to obtain eigenfrequencies and eigenvectors;
selecting a lowest non-zero eigenfrequency and moving atoms along a corresponding eigenvector;
setting an amplitude of displacement;
decreasing the amplitude of displacement to satisfy minimum-distance constraints;
selecting a next lowest-frequency non-degenerate mode for a subsequent mutation; and
analyzing mode degeneracy using a fingerprint function.

12. The method of claim 11, wherein the dynamical matrix is calculated by:




  
    
      
        D
        
          α
          ⁢
          
            
          
          ⁢
          β
        
      
      ⁡
      
        (
        
          a
          ,
          b
        
        )
      
    
    =
    
      
        ∑
        m
      
      ⁢
      
        
          
            ∂
            2
          
          
            
              ∂
              
                α
                a
                0
              
            
            ⁢
            
              ∂
              
                β
                b
                m
              
            
          
        
        ⁢
        
          (
          
            
              1
              2
            
            ⁢
            
              
                ∑
                
                  i
                  ,
                  j
                  ,
                  l
                  ,
                  n
                
              
              ⁢
              
                
                  
                    H
                    
                      i
                      ,
                      j
                    
                    
                      l
                      ,
                      n
                    
                  
                  ⁡
                  
                    (
                    
                      
                        r
                        
                          i
                          ,
                          j
                        
                        
                          l
                          ,
                          n
                        
                      
                      -
                      
                        r
                        
                          0
                          
                            i
                            ,
                            j
                          
                        
                        
                          l
                          ,
                          n
                        
                      
                    
                    )
                  
                
                2
              
            
          
          )
        
      
    
  
  ,



wherein Dαβ(a,b) represents the dynamical matrix, coefficients α, β are coordinates, coefficients a, b, i, j are an atom in the unit cell, coefficients l, m, n are a unit cell number, ri,jl,n is a distance between atom i in unit cell l and atom j in unit cell n, while r0i,jl,n is a corresponding bond distance, and Hi,jl,n is a bond hardness coefficient.

13. The method of claim 1, wherein the fitness function includes variables of at least one of free energy, density, hardness, dielectric constant and bandgap.

14. A system for predicting an optimized crystal structure using an evolutionary algorithm, comprising the processor configured to execute the method of claim 1.

15. A method for predicting an optimized surface structure using an evolutionary algorithm, the method comprising:
inputting characterization information of a chemical structure and input parameters;
generating a first convex hull of a first generation of surface structures from characterization information using a docking algorithm;
restricting the first generation of surface structures based on a convex hull algorithm according to a user-defined chemical potential constraint and outputting a second convex hull of the first generation of surface structures;
optimizing, by a processor, the second convex hull of the first generation of surface structures according to the input parameters;
inputting the optimized second convex hull into a niching algorithm to select an optimal group of surface structures and a parent group of surface structures based on a fitness function;
producing a child group of surface structures from the parent group of surface structures by applying a variation operator to an adatom layer of the surface structure of the first generation;
adding the child group of surface structures to the optimal group of surface structures to form a second generation of surface structures; and
repeating, by the processor, the optimizing by adding steps for a predetermined number of generations,
wherein the variation operator comprises at least one of a lattice mutation operator, a coordinate mutation operator, a spatial heredity operator, a soft-mode mutation operator and an atomic permutation operator, with the spatial heredity operator generating a number of slices of a unit cell and selecting a slice with a highest average order that is determined by:





  
    
      N
      s
    
    =
    
      L
      
        
          L
          char
        
        +
        
          
            (
            
              L
              -
              
                L
                char
              
            
            )
          
          ·
          
            
              cos
              ⁡
              
                (
                
                  
                    π
                    2
                  
                  ⁢
                  r
                
                )
              
            
            2
          
        
      
    
  
  ,



wherein r∈[−1;1] is a Pearson product-moment correlation coefficient, L is a thickness of a unit cell in a direction of the slice, and Lchar is half of a cubic root of an average atomic volume.

16. The method of claim 15, wherein the docking algorithm comprises:
scanning the adatom layer for vacant sites;
adding atoms to the vacant sites within the adatom layer based on predetermined conditions; and
outputting a configuration of the atoms added to the vacant sites.

17. The method of claim 16, wherein the predetermined conditions comprise at least one of a coordination number and a distance from adjacent atoms.

18. The method of claim 15, further comprising discarding the surface structures having a chemical potential above a user-defined threshold.