目次
  1. 自然界から着想を得た最適化アルゴリズム
  2. 遺伝的アルゴリズムの概要
  3. 遺伝的アルゴリズムの特性
  4. 材料科学における応用
  5. まとめ
  6. 参考文献

自然界から着想を得た最適化アルゴリズム

自然は常に、人類が複雑な問題を革新的な方法で解決するためのインスピレーションの源となってきました。鳥に触発された航空機の設計、魚に触発された海洋工学など、自然界のデザインは人間の課題に対してシンプルかつ効果的な解決策を提供することが多いです。遺伝的アルゴリズム（GA, Genetic Algorithm）は、進化的アルゴリズムの一派であり、自然界の強力な最適化プロセスである「進化」に着想を得ています。

進化においては、種が世代を重ねるごとに適応・改善し、最も適応度の高い個体がその形質を次世代に伝えます。GAはこの自然選択のメカニズムを模倣し、最適解の探索を行います。

化学や材料科学分野では、分子構造の最適化、新素材設計、触媒開発などでGAが応用され、その有用性が報告されています。また、機械学習アルゴリズムのハイパーパラメータや計算化学シミュレーションのモデルパラメータの最適化などでもよく用いられており、知らずとも恩恵を受けている科学者も多いかと思います。

本記事では、遺伝的アルゴリズムの基本要素や特徴の紹介を中心として、化学・材料科学への応用性についても触れていきます。

遺伝的アルゴリズムが解決する問題

世の中には、従来の手法では解が求めにくい問題が多数存在します。

  1. パラメータ数が多く全体の探索が困難な問題
  2. 解析的に解くことが難しい問題
  3. 解空間が非連続で局所解に陥りやすい問題

といったケースに対して、GAは効果的に用いられます。

(1) GAでは多数の解候補を同時に扱うため、全体の探索空間を効率的にカバーします。
(2) 理論的な解析解が求められない場合においては、解候補を適応的な操作によって徐々に改善し、近似的な最適解を求めていきます。
(3) 解空間に凹凸が多い場合では、GAはランダム性のある突然変異や交叉といった操作により局所解から抜け出せる性質があります。

GAがこういった能力を獲得する理由について、具体的な概念や手続きを説明することで理解していきましょう。

遺伝的アルゴリズムの概要

GAには様々なバリエーションがありますが、本記事では共通する基本的な構成要素に焦点を当てます。主要な概念を簡単に示した後に、計算手続きについてビジュアルと共に説明します。

主要な概念

  • 初期化（Initialization）
    遺伝的アルゴリズムを開始する前に、問題の設定やアルゴリズムの動作に必要なパラメータ（集団サイズ、交叉率、突然変異率、終了条件など）を決定するプロセスです。
  • 集団（Population）
    最適化問題における解候補の集合を指します。最初に設定する集団は「初期集団」として統計的手法またはドメイン知識をもとに生成されます。個体群とも言われます。
  • 個体（Individual）
    集団内の各解候補を個体と呼びます。各個体の変数を遺伝子と呼びます。
    例として、図1および図2では、各個体が6つの遺伝子（6変数）を持ち、その範囲は0～4となっています。
  • 適応度関数（Fitness function）
    各最適化問題において、解の「良さ」を定量化する関数です。
    例として、最大化問題では、より高い目的関数値を持つ解が高い適応度とされ、最適解に近いと評価されます。
  • 選択（Selection）
    次世代の子孫生成において使用される個体を選ぶプロセスです。たとえば適応度に基づいた選択とすることで、適応度の高い個体（エリート）が選ばれる確率が高くなります。
    ただし、エリートのみ選ばれると多様性が失われるため、ルーレット選択やトーナメント選択などの手法が用いられます。
  • 遺伝的操作（Genetic operations）
    次世代の子孫を多様かつ適応的に生成するため、以下の主要な操作があります。
    • 交叉（Crossover）: 2つの親個体の遺伝子を組み合わせ、新たな子個体を生成します（図1）。
    • 突然変異（Mutation）: 個体の遺伝子に変化を加え、新たな解候補を生成します（図2）。
  • 世代（Generation）
    選択、交叉、突然変異といった操作の1サイクルが1世代に相当します。世代ごとに新たな集団（解候補）が形成され、繰り返し進化することでより良い解を見つけます。
  • 収束（Convergence）
    ある一定数の世代において、著しい改善が見られなくなった場合、解候補が安定化し、プロセスは収束したと判断します。この時点で得られた最も高い適応度の個体を、最適解として採用します。
遺伝的アルゴリズム（GA）は、個体群を進化させて最適解を探索する進化学習手法。交叉はGAにおける主要操作の一つで、親個体の遺伝子を交換し、新たな子個体を生成。既存の優れた特徴を融合し、親の良い部分を受け継いだ子を得ることで解空間を探索。

図1. 「交叉」の操作例

突然変異(mutation)は1つの個体の遺伝子をランダムに変更し、解の多様性を高める遺伝的操作。親個体から継承されなかった新たな遺伝情報を生み出すことで、探索範囲を拡張。ランダムな変化により、局所的な最適解にとどまらず、未踏の領域を探る。

図2. 「突然変異」の操作例

最適化プロセス

上記の概念を用いて、進化と世代更新により適応度を向上させていくGAの手順を可視化します（図3）。

  1. 初期化
  2. 初期集団選定
  3. 初期集団の適応度評価
  4. 選択
  5. 交叉
  6. 突然変異
  7. 新世代の適応度評価
  8. 世代交代（4-7の繰り返し）
  9. 収束
遺伝的アルゴリズムの標準的な手順。初期化から始まり、個体群の適応度を評価後、選択・交叉・突然変異によって新世代を生成し、世代交代を繰り返す。最後に収束判定で最適解を得る。第一原理計算などのシミュレーションや機械学習のパラメータ最適化で活用。

図3. 遺伝的アルゴリズムの基本的な手順

このように遺伝的アルゴリズムは、遺伝的操作を介して既に得られた高評価の局所解を効果的に活用しながら、全体の最適解（大域解）を探索していきます。選択と交叉によって良い解を洗練し、突然変異によって未知の領域にも踏み込むプロセスを、視覚的に説明します（動画1）。

動画1では、初期点が局所的なエリア（左下の明るい領域）に設定され、徐々に外側へと探索が広がり、大域解（中央の暗い領域）へ向かう流れが描かれています。その中で、遺伝的操作によりエリート個体が選択され、突然変異により既存の範囲を超えた領域の探索が行われ、各世代で並列に最適解を追求する様子が示されています。

ここで、アルゴリズムのパラメータを変更すると、挙動がどのように変わるでしょうか。たとえば突然変異の影響を上げると、各個体が持つ情報が頻繁に変化し、局所解から脱出しやすくなる一方で、良好な解の探索が不安定になり、探索の幅が広がりすぎて最適解の周辺で十分な精度を得るのが難しくなります。（動画2）。

動画2では、初期の局所的なエリアから急速に広い範囲に散らばる個体群が、大域解の近くに一度到達するものの、収束せずにフィールド全体を行き来する様子が描かれています。

同じアルゴリズムでもパラメータ設定によって探索の戦略が大きく変わることを視覚的にも理解いただけたかと思います。

次に、このような挙動を示す遺伝的アルゴリズムの特性についてまとめていきます。少しテクニカルな説明になること、ご容赦ください。

遺伝的アルゴリズムの特性

1. 非微分での最適化特性

従来の最適化手法（例: 勾配降下法）は、問題を解く際に「微分情報」、つまり関数の傾きや変化率を利用します。しかし、多くの実際の問題では、評価関数が必ずしも滑らかでない場合があります。その結果、微分を正確に求めることが難しくなることがあります。

遺伝的アルゴリズム（GA）の大きな強みは、このような微分情報を一切必要とせず、単に各候補解（個体）の評価値（適応度）のみで最適解を探索できる点です。

  • 柔軟な適用範囲： 関数が非連続やノイズを含んでいても、その「評価結果」のみで次の世代を決定できるため、滑らかさを要求しない幅広い問題に対応できます。
  • ブラックボックス最適化： 目的関数の内部構造が不明な場合でも、実験やシミュレーションから得られる数値評価だけを利用して最適解を探すことが可能です。
  • 局所解からの脱出： 集団全体を並行して評価するため、多様な解候補からより良い解を見つけ出しやすくなります。

微分情報が不要であるため、理論的な前提条件に縛られることなく、実際の複雑な問題に対しても柔軟かつ効果的に最適解を探索できます。

2. 並列探索能力

GAは、個体群全体を同時に評価・進化させるという性質を持っています。各個体は互いに独立して評価されるため、同時に複数の候補解を探索することが可能です。並列処理が容易なため、複数の計算資源を利用して、広大な探索空間の中から効率的にグローバル最適解へと近づけることができます。並列探索できることは、計算コストが高く解空間が非常に広い問題に対して、探索速度を大幅に向上させる強みとなります。

遺伝的アルゴリズムが適さない場合

上述したGAの特性を考えると、必ずしもメリットだけでなく、GAが不適切な状況も浮かび上がってきます。あえて不適切な場合を理解することで、有用性についてもより深く理解いただければと思います。

  1. 評価（適応度計算）に非常に時間やコストがかかる場合
    GAは、複数の候補解（個体）を並行して評価し、何世代にもわたって進化を繰り返します。そのため、各個体の評価に多大な時間やコストがかかる場合、世代を重ねるごとができず収束に至りません。
    分子設計や材料探索で、1回の実験やシミュレーションが非常に高コストの場合、GAを何世代も回すよりも、ベイズ最適化など、評価回数を極力抑えつつモデルを更新する手法が有効です。ベイズ最適化では、ガウス過程などの確率的モデルを用いて、限られた評価回数で最適解に近づくことを目指します。
  2. 評価関数が単純で勾配が取りやすい場合
    GAは微分情報を必要としないため、勾配を取りにくい問題に向いています。もし目的関数が単純で滑らか、かつ容易に微分可能ならば、勾配降下法や準ニュートン法のほうが速く最適解に収束する可能性が高いです。
  3. 解の正確性や理論的保証が必要な場合
    GAは近似解を探索するメタヒューリスティックであり、厳密解や理論的な収束保証を重視する場面には向いていません。

そのほかにも、GAによる並列化が十分に行えない場や、適応度関数が頻繁に変化する環境などにおいても、GAの強みを生かせずに探索が不十分になることがあります。

実際の適用においては、対象とする問題の特性や制約条件を考慮して、GAと他の手法の特性を比較し、最適な手法（場合によってはハイブリッドアプローチ）を選択します。

ベイズ最適化の基礎を知る

材料科学における応用

遺伝的アルゴリズムの基礎を学んだところで、材料科学における応用について簡単に述べたいと思います。汎用的なアルゴリズムなので、普段使っているソフトウェアの裏側でGAが走っているケースも多いですが、ここでは直接的にGAを用いる例を3つ提示いたします。

  1. 分子設計
    AI分子生成の導入と基本手法の紹介では、分子生成においてGBGA (Graph-Based Genetic Algorithm) という遺伝的アルゴリズムの応用手法を用いて特性を最適化した分子の設計について触れています。分子生成におけるGA応用は他にも数多くありますが、それは広大な化学空間をシミュレーションを用いて並列探索するアプローチとGAとの相性の良さがあるからでしょう。
  2. 構造最適化 / 安定構造探索
    有機分子だけでなく、無機物質の構造探索にも遺伝的アルゴリズムは用いられます。遺伝的操作を用いて構造生成を行い、第一原理計算等で評価するサイクルを繰り返すことで、効率的に低エネルギーの安定構造を探索することができます。UXPEXなどのソフトウェアがあります。
  3. 記述子や力場のパラメータ最適化
    機械学習による精度の高い物性予測や、適切なシミュレーション結果を得るためには、入力となる記述子や力場パラメータの選択が重要です。たとえば、局所原子環境を表現するSOAP（Smooth Overlap of Atomic Positions）記述子のパラメータや、分子動力学計算に用いる経験的ポテンシャルのパラメータを、遺伝的アルゴリズムを用いて効果的に探索することができます（例：SOAP_GAS、EZFF）。

まとめ

本記事では、遺伝的アルゴリズム（GA）の基本概念から主要な構成要素、そして具体的な応用例まで、その概要について解説しました。

GAは、候補解を同時に検討し、優れた解を選択・交叉・突然変異させながら、最終的な最適解に向けて集団全体が進化していく手法です。このプロセスは、材料実験においても、試行錯誤を繰り返す実験者の直感と経験に似た側面を持っています。
実験科学者がGAを直接プログラムする機会はほぼないかと思いますが、マテリアルズ・インフォマティクスにおける機械学習やシミュレーションの利用の背後にはこのような手法が多用されているということを知っていただければと思います。

補足

MI-6の提供するmiHub®ソフトウェアにおいては、ベイズ最適化による実験候補点の導出における内部処理の複数箇所で遺伝的アルゴリズムを活用しています。高度化させた遺伝的アルゴリズムを用いて、よりロバストな解析に役立てています。

参考文献

  • Holland, J. H. Adaptation in Natural and Artificial Systems; MIT Press: Cambridge, MA, 1992. https://mitpress.mit.edu/9780262581110/adaptation-in-natural-and-artificial-systems/
    遺伝的アルゴリズムの理論に関する古典的著作です。
  • Unger, R.; Moult, J. Genetic Algorithms for Protein Folding Simulations. J. Mol. Biol. 1993, 231, 75–81. https://doi.org/10.1006/jmbi.1993.1258
    タンパク質の折り畳みシミュレーションにおける遺伝的アルゴリズムの応用例です。
  • Neto, J. C.; Meyer, G. E.; Jones, D. D. Individual Leaf Extractions from Young Canopy Images Using Gustafson–Kessel Clustering and a Genetic Algorithm. Comput. Electron. Agric. 2006, 53 (1), 81–92. https://doi.org/10.1016/j.compag.2005.11.002
    キャノピー画像から個々の葉を抽出するため、クラスタリングと遺伝的アルゴリズムを組み合わせた手法を提案しています。
  • Tang, L. L.; Tian, X.; Steward, B. L. Color Image Segmentation with Genetic Algorithm for In‐Field Weed Sensing. Trans. ASABE 2000, 43 (4), 1443–1448. https://doi.org/10.13031/2013.2970
    農業現場における雑草検出のため、色画像分割に遺伝的アルゴリズムを適用しています。
  • Lee, C. K. H. A Review of Applications of Genetic Algorithms in Operations Management. Eng. Appl. Artif. Intell. 2018, 75, 66–75. https://doi.org/10.1016/j.engappai.2018.08.011
    オペレーションマネジメント分野における遺伝的アルゴリズムの応用事例を網羅的にレビューしています。
  • Chen, R.; Liang, C.-Y.; Hong, W.-C.; Gu, D.-X. Forecasting Holiday Daily Tourist Flow Based on Seasonal Support Vector Regression with Adaptive Genetic Algorithm. Appl. Soft Comput. 2015, 30, 133–140. https://doi.org/10.1016/j.asoc.2014.10.022
    SVRと適応的遺伝的アルゴリズムを組み合わせて観光客流量を予測しています。
  • Kavitha, A. R.; Chellamuthu, C. Brain Tumour Segmentation from MRI Image Using Genetic Algorithm with Fuzzy Initialisation and Seeded Modified Region Growing (GFSMRG) Method. J. Med. Eng. Technol. 2016, 40 (3), 125–133. https://doi.org/10.1080/13682199.2016.1178412
    遺伝的アルゴリズムとファジー初期化を組み合わせて脳腫瘍画像をセグメント化しています。
  • Ghaheri, A.; Shoar, S.; Naderan, M.; Hoseini, S. S. The Applications of Genetic Algorithms in Medicine. Oman Med. J. 2015, 30 (4), 269–274. https://doi.org/10.5001/omj.2015.82
    医療分野における遺伝的アルゴリズムの多様な応用事例の総説です。
  • Paul, C. J.; Steen, L.; Jens, S. H.; Tejs, V.; Thomas, B. Genetic Algorithms for Computational Materials Discovery Accelerated by Machine Learning. npj Comput. Mater. 2019, 5, 82. https://doi.org/10.1038/s41524-019-0181-4
    機械学習と連携することで新素材探索を加速する遺伝的アルゴリズムの応用を報告しています。
  • Chiho, K.; Rohit, B.; Lihua, C.; Huan, T.; Rampi, R. Polymer Design Using Genetic Algorithm and Machine Learning. Comput. Mater. Sci. 2020, 180, 109–117. https://doi.org/10.1016/j.commatsci.2020.110067
    ポリマー設計において、遺伝的アルゴリズムと機械学習を融合したアプローチを提案しています。
  • Takahiro, I.; Takashi, T.; Katsuya, S. Materials Informatics Based on Evolutionary Algorithms: Application to Search for Superconducting Hydrogen Compounds. arXiv 2019, arXiv:1908.00746. https://arxiv.org/abs/1908.00746
    進化的アルゴリズムに基づくマテリアルズインフォマティクス手法を用い、超伝導水素化合物の探索を試みています。
  • Bartók, A. P.; Kondor, R.; Csányi, G. On Representing Chemical Environments. Phys. Rev. B 2013, 87 (18), 184115. https://doi.org/10.1103/PhysRevB.87.184115.
    局所原子環境の平滑かつ連続的な記述法であるSOAP記述子を提唱しています。