極値最適化（EO）は、組み合わせ最適化のためのメタヒューリスティックアルゴリズムであり、1999年にStefan BoettcherとAllon G. Percusによって導入されました。これは、自然界のシステムが、最も適合度の低い構成要素の繰り返し除去を通じて臨界状態へと進化する様子を記述する、Bak-Snppenの自己組織化臨界モデルに着想を得ています。最適化において、EOは、二値または値を持つ変数の集合から候補解を構築し、その後、局所適合度が最も悪い変数を反復的に選択してランダムな値に置き換えることで問題に取り組み、これにより、偏った極値プロセスを通じて解空間を探索します。
このアルゴリズムは、その単純さと、勾配情報に依存せずに困難な問題に対して高品質な解を達成することで注目されています。これは、進化的計算手法のより広いクラスに属しますが、集団の繁殖と交叉を使用する遺伝的アルゴリズムとは異なります。代わりに、EOは単一の解を使用し、べき乗則の選択確率を介して動作し、解空間での時折の大きなジャンプを可能にします。この確率的挙動は、局所最適解からの脱出を助け、特に巡回セールスマン問題、グラフ分割、スピングラス基底状態問題などの問題に対して、ほぼ最適な結果をしばしば見つけ出します。
歴史的発展
この手法は、1999年にBoissとPercusによって初めて発表され、『Physical Review Letters』誌に「Extremal optimization: Methods derived from co-evolution」というタイトルで掲載されました。彼らの研究は、砂山や生物学的生態系などの自然界のシステムが、性能の低い要素の除去を通じて臨界状態へと自己組織化するという観察に動機付けられました。これにより、より複雑で集団駆動型のアプローチとは対照的な、単純な突然変異ベースのヒューリスティックが開発されました。初期の実験では、EOが大規模なNP困難問題においてシミュレーテッドアニーリングと同等以上の性能を発揮できることが実証され、最適化文献におけるその地位が確立されました。
導入以来、EOは拡張され、二方向グラフ分割、グラフ彩色、そして最近では機械学習における特徴選択など、さまざまな領域に適用されてきました。制約付き問題を扱い、適応型確率分布を通じて収束を改善するための変種が提案されています。また、EOを自己組織化臨界のダイナミクスと関連付ける研究もあり、その挙動に対する理論的正当性が提供されています。
コアアルゴリズムとメカニズム
基本的なEOアルゴリズムは次のように動作します：
- 各可能な解が値が割り当てられた変数（またはスピン）の集合で構成される探索空間で問題を定義します。
- 各変数について、解全体のコストまたは適合度への寄与に基づいて局所適合度値が計算されます。
- 各反復で、局所適合度が最も悪い（最も低い）変数、すなわち極値変数が選択されます。その後、可能な割り当てのドメインから選ばれる新しいランダムな値が与えられます。
- 更新する変数を選択するために、べき乗則に比例する確率分布がしばしば使用され、最悪のみの選択がプロセスを閉じ込めるのを防ぎます。ランクr（r=1が最悪）の変数の典型的な選択確率はp(r) ~ r^-τであり、τは通常約1の値に設定されます。
- 各更新後、影響を受ける変数の局所適合度が再計算され、プロセスは固定回数の反復または停止基準が満たされるまで繰り返されます。
注目すべき特徴は、EOが明示的な局所探索ステップや山登り法を使用しないことです。代わりに、単一の突然変異とtau-パラメータが探索と活用のバランスを提供します。τが小さいとよりランダムな変更が行われ、τが大きいと最悪の中での最良への選択に偏り、少数の悪い構成要素が問題を引き起こす場合に役立ちます。最終解の品質は、実行中に任意の時点で観測された最高の局所適合度値であり、これはしばしば追跡されます。
コンピューティングシステムへの応用
EOは、さまざまな最適化課題に適用されてきました。Artificial intelligenceの分野では、ニューラルネットワークのトポロジーを進化させ、ハイパーパラメータを調整するために使用され、勾配ベースの手法に代わるものを提供しています。Machine learningでは、予測変数の最良のサブセットを選択することを目的とした特徴選択に適用されており、EOは、特徴を検証精度への寄与に基づく局所適合度を持つ構成要素として扱うことができるため、良好に機能します。
さらに、EOは、ビンパッキング問題、ジョブショップスケジューリング、誤り訂正符号の構築などの組み合わせ最適化インスタンスを解くためにも頻繁に使用されます。また、並列および分散システムの設計、例えば、メイクスパンを最小化するためにタスクをプロセッサに割り当てる際にも使用されます。勾配情報がないため、目的関数が不連続または離散的である問題に適用できます。グラフの二分割に適用すると、EOは優れたコミュニティ検出結果を生成し、主要なグラフ分割アルゴリズムに匹敵することが示されています。
他のメタヒューリスティックとの関係
EOは、遺伝的アルゴリズムやシミュレーテッドアニーリングとファミリー的な類似性を共有しますが、異なるメカニズムを使用します。遺伝的アルゴリズムは解の集団を維持し、組換えと突然変異を使用しますが、EOは単一の解を使用します。シミュレーテッドアニーリングは、ランダムな摂動によって解全体を変更し、温度に応じて変更を受け入れますが、EOは局所適合度に導かれて最悪の構成要素のみを変更します。重要な違いは、EOの変更する構成要素の選択が、解全体の目的関数値ではなく、ランクに基づいて決定的（またはべき乗則ランダム）であることです。
自己組織化臨界（SOC）との理論的関連は、EOが自然界で見られるべき乗則の変動を再現することを意味し、これにより多くのランドスケープタイプに対する堅牢性が得られます。古典的なベンチマーク（巡回セールスマン問題）での比較では、EOはシミュレーテッドアニーリングと競合しますが、しばしばより少ない関数評価を必要とします。実際には、近傍が構成要素の適合度のランクによって定義される問題では、EOは単純な実装でも効率的です。
拡張と変種
研究により多くの変種が生み出されています。最も一般的なのはtau-EOであり、パラメータtauが高ランクの変数を選択する確率を制御します。tauの値とべき乗則の裾の範囲は、一貫性を改善するために調整できます。別の変種は、テールにジッターを導入した確率的山登り法です。別のアプローチである共進化は、相互作用する構成要素を持つ問題を扱い、共適応に基づいて複数の変数が突然変異されます。最近では、このアルゴリズムは局所探索ヒューリスティックと組み合わされ、EOの発見フェーズ後に追加の微調整を実行するハイブリッドEOが生み出されています。
Deep learningアプリケーションでは、EOの一形態がモデルアーキテクチャを自動的に調整するために使用されてきました。特にNeural network探索で使用されていますが、より複雑な方法に取って代わられています。EOは勾配を必要としないため、勾配が利用できないかコストがかかるモデル、例えば非微分可能な損失に適用できます。また、強化学習問題における離散空間の探索にも適しています。
制限とオープンリサーチ
EOの重要な課題の1つは、tauパラメータとべき乗則の値範囲の設定です。適切に選択されないtauは、収束不良やカオスにつながる可能性があります。さらに、一度に1つの変数のみを変更するため、非常に制約の強い問題や変数間の依存関係がある問題では、高い計算コストを避けるために適合度の慎重な形式化が必要です。
オープンリサーチは、EOをより適応的にすることに焦点を当てており、例えば、tauをオンザフライで推定したり、tauにアニーリングスケジュールを使用したりします。また、変数のランダム値置換を選択するより高度な方法や、分散設定でのEOの使用に関する研究もあります。
EOの理論的理解は他のメタヒューリスティックほど成熟していませんが、実装が簡単で多くの種類の困難な問題に対して堅牢であるため、組み合わせ最適化と自然に着想を得たコンピューティングのツールセット内で注目すべき概念です。将来は、特殊なオプティマイザーとのさらなる統合と、実用的なスケジューリングと設計のためのべき乗則統計のさらなる研究が見られるでしょう。
主要な研究者と影響
元の著者であるStefan BoettkeとAll Percus（当時は両者ともサンタフェ研究所に所属）は、SOCの視点を最適化にもたらしました。Xerox ParcやBerkeley AI Researchを含む他のグループによるその後の研究は、この手法の枠組みと分析を拡張しました。現代の機械学習ツールの最前線にはありませんが、自然に着想を得たヒューリスティックの参照点であり、進化的計算に関するコース教材にしばしば含まれています。
要約すると、極値最適化は、困難な組み合わせ問題を近似するためのミニマリストで非勾配の確率的枠組みを提供し、問題が単一の適合度値を持つ構成要素に分解できる理論研究と応用の両方において、概念およびアルゴリズムとして継続的な価値を持っています。
制限と注意点
実用的な使用のために、この方法は大域的最適性を保証せず、一部の問題では選択確率分布の調整が必要になる可能性があることに注意する必要があります。適切な設定があれば、これは単純でありながら効果的な最適化ツールとなり得ます。