データ + 進化的アルゴリズム = データ駆動型進化的最適化?進化的アルゴリズムと数学的最適化

データ駆動型進化的最適化とは何ですか? それは単なるデータ + 最適化アルゴリズムですか? データ駆動型進化的最適化はどのようなアプリケーション シナリオに適していますか? 従来の数学的最適化手法は新たな課題に直面していますか?この記事では、上記の質問に対する詳細かつわかりやすい回答を提供します。記事の最後には、関連資料と参考文献のギフトパッケージも添付しています。これらの資料は単なる書籍リストではなく、この記事の著者2人が長年の研究経験と学習プロセスに基づいて慎重に選択してまとめたものです。***ジャーナルからの質の高い論文や、一般向けの人気講演会などがあります。

データ駆動型最適化に関する関連する古典文献や進化コンピューティングに関する PPT などのコース資料を収集し、ネットワーク ディスク リンクにして後ろに配置します。

まず、データ駆動型進化最適化の動機についてお話ししましょう。

簡単に言えば、データ駆動型進化計算とは、データと進化アルゴリズムを利用して最適化問題を解決することです。まず、なぜ進化的アルゴリズムを使用するのでしょうか。いくつか例を挙げると、シミュレーション実験ソフトウェアなど、ブラックボックス最適化問題とみなすことができる一部の最適化問題では、数学的な最適化モデルを取得することが困難です。数式はわかっていても、その式が非凸、微分不可能、微分不可能である問題もあります。これらの問題は、従来の勾配ベースの数学的最適化手法では解決が困難です。このとき、遺伝的アルゴリズム、粒子群アルゴリズム、微分アルゴリズムなどのインテリジェントな最適化アルゴリズムが役立ちます。

では、なぜ依然としてデータに頼る必要があるのでしょうか。インテリジェントな最適化アルゴリズムはすべて、集団反復最適化アルゴリズムに基づいていることはわかっています。集団には数十または数百の個体 (各個体がソリューション) が含まれており、より良いソリューションを見つけるには数百世代かかります。この場合、最適化問題を何度も評価する必要があります (ソリューションの関数値を計算します)。たとえば、人口が 100 で反復回数が 100 回のインテリジェント最適化アルゴリズムの場合、最適化問題を 10,000 回評価する必要があります。ただし、一部の最適化問題の評価コストは非常に高くなります。たとえば、風洞実験の評価には数時間かかります。別の例としては、薬物試験プロセスに多額の費用がかかる製薬工学があります (薬物試験はマウスの寿命に関係します)。インテリジェントな最適化アルゴリズムには、数千または数万回の評価が必要であり、最適化問題には耐えられません。この場合、学者は、最適化問題の履歴データを使用して最適化プロセスを支援し、最適化問題の評価回数を減らし、最適化問題の評価コストを削減するというアイデアを思いつきました。

データ駆動型進化最適化アルゴリズム

では、データ駆動型進化的最適化はどのように機能するのでしょうか? そのプロセスは図1に示されています(参考文献[1]より)。まず、最適化プロセスの最適化問題（図中の厳密な関数評価、以下、実最適化問題と呼ぶ）によって生成されたデータを使用してモデルが構築されます。このモデルは代理モデル（Surrogate）と呼ばれ、これまでのデータ駆動型進化最適化アルゴリズムは代理支援進化最適化アルゴリズム（Surrogate-Assisted Evolutionary Algorithm、SAEA）とも呼ばれます。代替モデルの目的は、実際の問題を近似することです。

最適化の過程では、代理モデルと実際の問題が連携して個体を評価します。この連携をモデル管理（代理管理）と呼びます。プロキシ モデルと実際の最適化問題が連携する理由は 2 つあります。1 つは、プロキシ モデルが実際の問題のデータを使用してトレーニングされ、実際の問題との類似点があることです。プロキシ モデルは最適化問題の代わりに使用され、ソリューションを評価して実際の問題に対するより優れたソリューションを事前に選択することで、実際の問題の評価回数を減らします。一方、プロキシモデルと実際の問題の間には乖離があります。プロキシモデルが解を実際の問題から逸脱させてしまうことを防ぐために、実際の問題で解を評価します。実際の問題で評価した解をトレーニングデータセット（図の点線）に追加して、プロキシモデルを修正します。では、プロキシ モデルはどのように確立されるのでしょうか? モデル管理とは何でしょうか?

一般的に、機械学習のモデリング手法は、ガウス過程、ニューラル ネットワーク、SVM、RBF、さまざまな統合モデルなどのプロキシ モデルのトレーニングに使用できます。ただし、ガウス過程の方が一般的に使用されています (後でモデル管理について説明するときに理解できます)。

モデル管理に一般的に使用される方法は、学術的には世代と個体に基づくハイブリッド方式と呼ばれています。つまり、アルゴリズムは最初にプロキシ モデルを数世代にわたって最適化し、次に第 1 世代から個体の一部を選択して実際の問題に送り返して再評価します。 ここでの重要なポイントと難しさは (SAEA の問題も同様)、プロキシ モデルからどのソリューションが実際の問題の収束を迅速に支援できるかを選択することであり、これは前述のように適切なソリューションを事前に選択する方法です。代替モデルから実際の問題の評価ソリューションを選択する戦略は、SAEA ではインフィル サンプリング基準と呼ばれます。

1 つのアイデアは、代替モデルのソリューションの最良の部分を選択して、実際の問題を再評価することです。この場合、代替モデルが十分に正確であれば、つまり、代替モデルが実際の最適化問題に非常に類似していれば、選択されたソリューションは実際の問題の収束にさらに役立ちます。図2に示すように。

しかし、特に SAEA で収集されたデータが少ない場合、十分に正確なプロキシ モデルをトレーニングすることは現実的ではありません。したがって、ソリューションを再評価するための別の方法は、図 3 (参考文献 2 より) に示すように、代理モデルが不確実であると見なすソリューション (簡単に言えば、他の個体から遠く離れた個体) を選択することです。このとき、ガウス過程の利点が反映されます。ガウス過程は、解の評価値を直接与えるだけでなく、評価値の確実性も与えることができます (ガウス過程を説明した Web サイトは http://www.ppvke.com/Blog/archives/24049 です)。これらの不確実なソリューションを選択することには 2 つの利点があります。これらの個体が配置されている領域はほとんど探索されないため (図 3a)、実際の問題に渡すことで実際の問題の探索能力が向上する可能性があります。もう 1 つの利点は、これらの個体はまばらな領域に分布しているため、実際の問題で評価した後にトレーニング セットに追加することで、トレーニング セットの多様性が高まり、プロキシ モデル修正プロセス中にプロキシ モデルの精度が大幅に向上することです (図 3b)。

*** 最も一般的に使用される方法の 1 つは、上記の両方の条件を考慮して個人を選択することです。例えば、ガウス過程モデルでよく使われるLCB指数とExI指数は式(1)と式(2)で示される。

解の不正確さを与えることができない他のモデルについては、SAEA 研究分野でさまざまな戦略が提案されています。例えば、ローカルサロゲートモデルが確立され、ローカルサロゲートモデルの最適なソリューションが選択され、統合モデルでは、各サブモデルの評価の差を使用して個々の評価の精度などが表現されます。

実際の問題に対する最適なソリューションは、トレーニング セット (実際の問題で評価されたソリューション) から選択されます。上記は、データ駆動型進化最適化アルゴリズムの簡単なプロセスです。推奨事項のレビュー[3]と課題[4]の詳細な紹介が提供されています。

進化的アルゴリズム VS 数学的最適化 (以下の議論は単一目的最適化問題に基づいています)

上記のセクションでは、データ駆動型進化的最適化について簡単に紹介しました。これを見て、進化的アルゴリズムと数学的最適化のそれぞれの利点と欠点は何かと疑問に思うかもしれません（数学的最適化が何であるかよくわからない場合は、こちらの記事 https://zhuanlan.zhihu.com/p/25579864 を参照してください）。実際、進化的アルゴリズムと数学的最適化はどちらも最適化問題を解決するために使用されますが、出発点は非常に異なります。次のようなシナリオをよく見かけます。

ラウンド1の解答結果

進化型アルゴリズムは目的関数の値を計算するだけでよく、最適化問題自体の特性に対する要件は非常に低いです。数学的最適化アルゴリズムとは異なり、凸最適化であるかどうか、目的関数が微分可能かどうか、目的関数の導関数がリプシッツ連続であるかどうかなど、多数の条件に依存することはあまりありません。私は偏微分方程式の制約を伴う最適化問題も研究しました。目的関数が凸関数か微分可能関数かさえわからない場合がよくあります。これは、進化的アルゴリズムが数学的最適化アルゴリズムよりも優れている最大の利点です。実際、これは進化的アルゴリズムの欠点でもあります。アルゴリズムの問​​題に依存しない性質は、すべての問題に機能することを意味するため、さまざまな問題の特性を十分に活用してアルゴリズムをさらに高速化および最適化できないことがよくあります (利点はしばしば欠点につながるという哲学的弁証法的な考え方がここにあります)。数学的最適化アルゴリズムの規則と規制は、実際には数学的最適化アルゴリズムの適用範囲を定義しているようです。この範囲外でアルゴリズムがうまく機能するかどうかは不明ですが、この範囲内では数学的最適化によって基本的な理論的保証を提供できます。

結論: 数学的最適化は、一般に、線形計画法、二次計画法、凸最適化など、特定の問題構造を持つ最適化問題や、使用する最適化問題に関する十分な情報がある場合に利点があります。逆に、進化的アルゴリズムを使用すると利点があるかもしれません。 NP 困難問題など、現時点では数学的最適化では完全に解決できない問題に対しても、進化的アルゴリズムは大きな応用の見込みがあります。

ラウンド2の解決率

進化的アルゴリズムの計算速度は比較的遅いというのが一般的な見解であり、これは理解しやすいことです。各反復では、目的関数を M 回計算する必要があります。ここで、M は集団のサイズで、通常は約 30 ～ 50 です。進化的アルゴリズムの最先端の研究方向の 1 つは、大規模な最適化問題です。関連ジャーナルの論文も参照しましたが、進化的アルゴリズムにおける大規模は、数学的最適化アルゴリズムではまったく大規模ではない可能性があることがわかりました。これは、進化型アルゴリズムの計算速度のボトルネックによって、大規模な最適化問題への適用が制限されることを間接的に反映しています。近年のディープラーニングの台頭により、人々のコンピューティング能力に対する要求がますます高くなり、GPU ベースの並列コンピューティングと分散コンピューティング アーキテクチャが人工知能のさまざまな分野で広く使用されるようになったことは注目に値します。進化的アルゴリズム自体は優れた並列特性を備えているため、GPU 並列コンピューティングに基づく進化的アルゴリズムが遅い進化的アルゴリズムの問​​題をある程度解決できるかどうかは、間違いなく研究する価値のあるトピックです。

まとめると、進化的アルゴリズムと数学的最適化は、問題を理解して解決するためのツールの 1 つにすぎません。ツール自体に良いものと悪いものの絶対的な区別はありません。ツールごとに適用可能なシナリオがあります。ツールの長所と短所を特定し、適切な適用シナリオを見つけるのは、ツールを使用する私たち次第です。

まとめ

データ駆動型進化的最適化アルゴリズムは、計算コストの高い問題を解決するために使用されます。また、ロバスト最適化問題や大規模最適化問題など、他の最適化分野でも使用されます。これらの問題の解決プロセスも多くの計算時間を消費するため、その本質は実際の問題の評価回数を減らすことにあります。さらに、オフラインデータ駆動型最適化（シミュレーション最適化とも呼ばれる）の研究も始まって​​います[1]。これは、最適化プロセスではプロキシモデルしか使用できず、実際の問題を使用して検証できないことを意味します。