進化的アルゴリズム (EA)

2025 April 2

背景

進化的アルゴリズム（EA）は，進化論に着想を得たメタヒューリスティックな手法である． EA は，これまでに探索された安定構造（親構造）の局所環境を受け継ぐことで，新たな構造（子個体）を効果的に生成することができる． Oganov グループの USPEX はよく知られたソフトウェアであり，そのほかにも XtalOpt などがある． 先行研究の例は以下の通り．

  • T. S. Bush, C. R. A. Catlow, and P. D. Battle, J. Mater. Chem. 5, 1269 (1995).
  • A. R. Oganov and C. W. Glass, J. Chem. Phys. 124, 244704 (2006).
  • A. R. Oganov, A. O. Lyakhov, and M. Valle, Acc. Chem. Res. 44, 227 (2011).
  • A. O. Lyakhov, A. R. Oganov, H. T. Stokes, and Q. Zhu, Comput. Phys. Commun. 184, 1172 (2013).

fig_EA_pes fig_EA_pes

手順

  1. 個体群（population）の初期化
  2. 適応度（fitness）の評価
  3. 自然選択
  4. 親個体の選択
  5. 次世代の生成
  6. ステップ2（適応度の評価）に戻り繰り返す

個体群（population）の初期化

第一世代では，n_pop で指定された数のランダム構造が生成される． EAおよびEA-vcにおいては，tot_struc は使用されない．

適応度（fitness）の評価

現在，CrySPYにおいて適応度として使用できるのはエネルギーのみである． fit_reverse = False に設定することで，最小値探索モードになるよう構成されている． この fit_reverse の設定は，将来的にエネルギー以外の物性を適応度として用いる場合に備えて用意されている．

自然選択

DFT計算では，まれに失敗して極端に不合理なエネルギー値が得られることがある． emax_ea および emin_ea を用いることで，極端に高い（または低い）エネルギーを持つ構造を除外することができる:    $$ \mathrm{emin\_ea} \le E \ (\mathrm{eV/atom}) \le \mathrm{emax\_ea} $$ たとえば，emin_ea を設定すると，その値よりも低いエネルギーを持つ構造は無視される．

自然選択では，まず現在の個体群と，過去の世代から保持されたエリート個体が，適応度に基づいてランク付けされる． ここで使用されるエリート個体の数は，n_eliteで指定される． 現在の個体群とエリート個体の中から，適応度の高い順に n_fittestの数の個体が選択され，それ以外は淘汰される． 自然選択の過程では，pymatgen のStructureMatcher クラスにより重複を除去し，上位n_fittestの数の個体を選択している． n_fittest は，n_pop（個体群サイズ）の約半分に設定されることが多い． 現在の実装では，n_fittest = 0 の場合，すべての個体が保持される仕様になっている． 下の図はn_fittest = 5の場合の自然選択の例を示している．

fig_EA_natural_selection fig_EA_natural_selection

親個体の選択

親候補の個体の中から1つの親個体を選択するために，CrySPYでは2種類の選択手法が実装されている． いずれの手法も，適応度の高い個体がより高い確率で選ばれるように設計されている． slct_func = TNMを設定するとトーナメント選択が，slct_func = RLTを設定するとルーレット選択が使用される． トーナメント選択はパラメータが少なく，簡単に使用できる点が利点である．

次世代の生成

次世代は，親候補の個体に対して進化的操作を適用して生成された子個体と，一部のランダム構造から構成される． ランダム構造は，多様性を維持し，局所的最小からの脱出を促すために各世代で追加される．

進化的操作

ここでは，CrySPYに実装されている，組成固定型EAの進化的操作を紹介する．

個体群の数

crossover, permutation, strainおよびランダムに生成された構造数の合計がn_popと等しくなければならない．

  • n_pop = n_crsov + n_perm + n_strain + n_rand

進化的アルゴリズム (EA)のサブセクション

Crossover

概要

交叉(cross over)は，2つの親構造のスライスされた領域を交換することで，新たな構造（子個体）を生成する進化的操作である． この操作により，構造の多様性が促進され，局所的に安定な特徴が遺伝することが可能となる． 構造探索において低エネルギー構造を効率的に探索するための主要な手法のひとつである．

手順

  1. 親候補から異なる個体を2つ選択
  2. ランダムに並進操作
  3. 格子ベクトルをランダムに選択
  4. 中央付近で親構造を切断
  5. 切断された半分を交換
  6. 原子数の多い子構造を選択
  7. ボーダー付近で原子数の調整
  8. 最小原子間距離のチェック

fig_EA_crossover fig_EA_crossover

4. 中央付近で親構造を切断

切断ポイントは中央付近で，下記のように毎回少し変化させる．

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

以降のステップで失敗した場合，このステップ4に戻って再開する場合がある． ただし，再開可能な回数はmaxcnt_eaで上限が決められており，それを過ぎた場合は親の選択からやり直す．

5. 切断された半分を交換

crs_latがrandomの時，子構造の格子ベクトルは2つの親構造のうちのどちらか一方をそのまま引き継ぐ． crs_latがequalの場合は，親構造の格子ベクトルの平均を使う． デフォルトはrandom．

6. 原子数の多い子構造を選択

親構造を入れ替えると，通常二つの原子数の異なる構造が得られる． とりあえず，原子数の多い構造を採用する．

fig_EA_crossover_natoms fig_EA_crossover_natoms

ただし，原子数が元の構造のものと大きく違う場合はステップ4（中央付近で親構造を切断）からやり直す． その許容量はnat_diff_toleで決める． デフォルト値は4で，その場合それぞれの元素において原子数の差が±4まで許容される． 上の図の場合，元の構造と比較すると，青の原子は-1で，緑の原子は+2になっている．

7. ボーダー付近で原子数の調整

削除

原子数を調整する際，まずは原子の削除から行う． 下の図に示すように，mindistで定義される最小原子間距離を満たしていない原子から優先的に削除される．

fig_EA_crossover_rm_mindist fig_EA_crossover_rm_mindist

以下のように，もし原子の削除が完了しても最小原子間距離の制限にかかる原子がある場合，ステップ4（中央付近で親構造を切断）からやり直す．

fig_EA_crossover_rm_mindist2 fig_EA_crossover_rm_mindist2

最小原子間距離の制限にかかる原子が無く，さらに原子を削除する必要がある場合は，下の図に示すようにボーダーから近い原子から削除する．切断ポイントに加えて内部座標が0のところもボーダーであることに注意．

fig_EA_crossover_rm_border fig_EA_crossover_rm_border

追加

原子が不足しているときは，その原子をボーダー付近に追加する． 選択されている軸に沿った内部座標は下記のように決める． ここでmeanは切断ポイントの座標か0である．

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

座標の残りの二つの成分はランダムに決められる． 最小原子間距離のチェックを行いながら，元の組成と一致するまで原子を追加する．

fig_EA_crossover_addition fig_EA_crossover_addition

Permutation

概要

置換（permutation）は，単一の構造内における異なる元素同士の配置を入れ替えることで，新たな構造（子個体）を生成する進化的操作である． この操作により，格子および全体の組成を変えることなく，異なる構造配置の探索が可能となる．

手順

異なる元素の原子の位置を入れ替える． 原子の入れ替えの回数はntimesで指定する．デフォルトは1回． 入れ替え後，最小原子間距離をチェックする．

fig_EA_permutation fig_EA_permutation

Strain

概要

歪み（strain）は，親構造の格子に対して小さなランダムな変形を加えることで，新たな構造（子個体）を生成する進化的操作である． この操作により，原子の接続関係や組成を保持しつつ，構造空間の近傍領域を探索することが可能となる． 構造候補の微調整や，局所的な最小値からの脱出にも有効である．

手順

以下の歪み行列を用いて，格子ベクトル $ \mathbf{a} $を変形させる．

$$ \mathbf{a}' = \begin{pmatrix} 1 + \eta_1 & \frac{1}{2} \eta_6 & \frac{1}{2} \eta_5 \\ \frac{1}{2} \eta_6 & 1 + \eta_2 & \frac{1}{2} \eta_4 \\ \frac{1}{2} \eta_5 & \frac{1}{2} \eta_4 & 1 + \eta_3 \end{pmatrix} \mathbf{a}. $$

ここで， $ \eta_i $はガウス分布 $ \mathcal{N}\left( 0, \ \sigma_{\mathrm{st}}^2 \right) $から決まる値で， $ \sigma_{\mathrm{st}} $は入力パラメーターsigma_stで指定できる（デフォルトはsigma_st = 0.5）． 下の図に示すように，格子を変形させた後は，元の体積に戻す． 最後に最小原子間距離の制限をチェックする．

fig_EA_strain fig_EA_strain

トーナメント選択

概要

トーナメント選択は，適応度に基づいて候補の中から親個体を選ぶための手法である． この手法は，個体群内の選択圧と多様性のバランスをとるように設計されている． 下の図は，n_fittest = 10，t_size = 3の場合の例を示す．

fig_EA_tournament fig_EA_tournament

手順

  1. 親個体候補から，所定の数（t_size）の個体をランダムに選択
  2. その中で，最も適応度の高い（すなわち，エネルギーが最も低い）個体が親として選ばれる
  3. この処理を繰り返し，必要な数の親個体が選ばれるまで続ける

利点

  • シンプルで効率的
  • パラメータは1つだけ (t_size)
  • t_sizeを変えることで選択圧を調整可能

注意

  • t_sizeはデフォルトで3
  • t_sizeが小さいと，多様性が促進される
  • t_sizeが大きいと，選択圧が増して，選択確率がより適応度に依存する
  • ルーレット選択とは異なり，トーナメント選択では下位の（t_size - 1）個の個体が選択されることはない

ルーレット選択

概要

ルーレット選択は，適応度に基づいて親候補の個体の中から親個体を選ぶための確率的手法である． ルーレット選択においては，各個体の選ばれる確率はその適応度に比例する．

手順

  1. fit_reverse が False（デフォルト）に設定されている場合，これはエネルギーを適応度として用いる最小化モードに対応しており，親候補の適応度には –1 が掛けられる．
  2. 適応度 $ f_i $ は，以下の式により線形スケーリングされて $ f'_i $ に変換される．ここで， $ a $ および $ b $ は，それぞれ a_rlt および b_rlt で指定されるパラメータであり， $ 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. スケーリング後の適応度 $ f'_i $ は，次式により選択確率に変換される：
    $$ p_i = \frac{f_i'}{\sum_k f_k'} $$
    各 $ p_i $ は， $ i $ 番目の個体が選ばれる確率を表す．
  4. 親個体は， $ p_i $ に基づいてルーレット選択により1つずつ選ばれ，必要な数に達するまで繰り返される．

利点

  • すべての個体が非ゼロの確率で選ばれる可能性がある
  • 適応度のスケーリングによって選択圧を調整できる

注意

  • デフォルトでは a_rlt = 10.0，b_rlt = 1.0
  • 意味のある選択圧を得るためには，適応度のスケーリングが重要である． 下の図は， $ a $ が比較的小さい場合（左）と比較的大きい場合（右）における $ p_i $ の例を示している．
    $ a $ が小さすぎると選択圧が弱くなり，適応度の高い個体が優先されにくくなる．

fig_EA_roulette fig_EA_roulette