極限最適化

極値最適化 (EO)は、統計物理学の分野における自己組織化臨界性のBak-Sneppen モデルにヒントを得た最適化 ヒューリスティックです。このヒューリスティックは当初、巡回セールスマン問題やスピン グラスなどの組み合わせ最適化問題に対処するために設計されましたが、この手法は最適化領域でも機能することが実証されています。

自己組織化臨界性(SOC) は、統計物理学の概念で、アトラクターとして臨界点を持つ動的システムのクラスを記述します。具体的には、システムの最高スケールにまで達する変化と散逸の雪崩を通じて進化する非平衡システムです。SOC は、地形形成、地震、進化、米や砂山の粒状ダイナミクスなど、バーストのような現象を持ついくつかの自然システムの背後にあるダイナミクスを支配していると言われています。ここで特に興味深いのは、 SOC のBak-Sneppen モデルです。これは、断続平衡(絶滅イベント)を介して進化を記述できるため、進化を自己組織化臨界プロセスとしてモデル化できます。

パズルのもう 1 つのピースは、計算複雑性に関する研究です。具体的には、NP 完全問題には臨界点が存在することが示されています。NP 完全問題では、最適解に近い解が広範囲に分散しており、探索空間の障壁によって分離されているため、ローカル探索アルゴリズムが行き詰まったり、著しく妨げられたりします。Bakと Sneppen による進化的自己組織化臨界モデルと、組み合わせ最適化問題における臨界点の観察が、Stefan Boettcher と Allon Percus による極値最適化の開発につながりました。

EO は、組み合わせ最適化問題 のためのローカル検索アルゴリズムとして設計されました 。候補ソリューションの集団を処理する遺伝的アルゴリズムとは異なり、EO は単一のソリューションを進化させ、最悪のコンポーネントにローカルな変更を加えます。これには、個々のソリューション コンポーネントに品質尺度 (「適合度」) を割り当てることができる適切な表現を選択する必要があります。これは、目的関数に対する集合的な評価に基づいてソリューションのすべてのコンポーネントに均等な適合度を割り当てる、蟻コロニー最適化や進化的計算などの全体論的アプローチとは異なります。アルゴリズムは、ランダムに構築することも、別の検索プロセスから導出することもできる初期ソリューションで初期化されます。

この手法はきめ細かな探索であり、表面的には山登り（局所探索）手法に似ています。より詳しく調べると、より広範な集団ベースのアプローチ（進化的計算および人工免疫システム）に適用可能で、類似性さえあるかもしれない興味深い原理が明らかになります。このアルゴリズムの背後にある支配的な原理は、低品質のコンポーネントを選択的に除去し、ランダムに選択されたコンポーネントに置き換えることによる改善です。これは明らかに、より良いソリューションを作成するために良いソリューションを選択する典型的な進化的計算アルゴリズム である遺伝的アルゴリズムとは相容れません。

この単純な原理から得られるダイナミクスは、第一に堅牢な山登り探索動作、第二に複数回再開探索に似た多様性メカニズムです。全体的なソリューション品質を時間経過 (アルゴリズムの反復) とともにグラフ化すると、断続平衡で説明されるのと非常によく似た方法で、改善期間の後に品質の急激な低下 (雪崩) が続くことがわかります。この急激な低下または探索空間での急激な変化により、アルゴリズムは局所最適状態から抜け出すことができ、このアプローチを他の局所探索手順と区別することができます。このような断続平衡動作は「設計」または「ハードコード」できますが、これはアルゴリズムの基本である負のコンポーネント選択原理の 出現効果であることを強調する必要があります。

EO は主に、グラフ分割や巡回セールスマン問題などの組み合わせ問題や、スピングラスなどの統計物理学の問題に適用されてきました。

一般化極値最適化 (GEO) は、ビットの絶対変化率、または全体的なソリューション品質へのビットの貢献度によってコンポーネントの品質が決定されるビット ストリングを操作するために開発されました。この作業には、標準関数最適化問題およびエンジニアリング問題領域への適用が含まれます。EO の同様の拡張機能として、連続極値最適化 (CEO) があります。

EO は、画像のラスタライズに適用されているほか、アリコロニー最適化を使用した後のローカル検索としても使用されています。EO は、複雑なネットワーク内の構造を識別するために使用されています。EO は、複数のターゲットの追跡問題に使用されています。最後に、選択を制御するために使用される確率分布を調査する研究も行われています。

• 遺伝的アルゴリズム
• シミュレーテッドアニーリング

• Bak, Per; Tang, Chao; Wiesenfeld, Kurt (1987-07-27). 「自己組織化臨界性: 1/f ノイズの説明」. Physical Review Letters . 59 (4). American Physical Society (APS): 381–384. Bibcode :1987PhRvL..59..381B. doi :10.1103/physrevlett.59.381. ISSN  0031-9007. PMID  10035754. S2CID  7674321.
• Bak, Per; Sneppen, Kim (1993-12-13). 「進化の単純なモデルにおける断続平衡と臨界性」. Physical Review Letters . 71 (24). American Physical Society (APS): 4083–4086. Bibcode :1993PhRvL..71.4083B. doi :10.1103/physrevlett.71.4083. ISSN  0031-9007. PMID  10055149.
• P Cheeseman、B Kanefsky、WM Taylor、「本当に難しい問題はどこにあるのか」^{[永久リンク切れ‍ ]}、第 12 回 IJCAI 会議録、(1991)
• G Istrate、「計算の複雑さと相転移」、議事録。第 15 回 IEEE 計算の複雑さに関する年次会議、104–115 (2000)
• Stefan Boettcher、Allon G. Percus、「極限最適化: 共進化から派生した手法」、遺伝的および進化的計算カンファレンスの議事録 (1999)
• Boettcher, Stefan (1999-01-01). 「パーコレーション閾値でのグラフ分割の極限最適化」. Journal of Physics A: Mathematical and General . 32 (28). IOP Publishing: 5201–5211. arXiv : cond-mat/9901353 . Bibcode :1999JPhA...32.5201B. doi :10.1088/0305-4470/32/28/302. ISSN  0305-4470. S2CID  7925735.
• Boettcher, Stefan; Percus, Allon (2000)、「自然の最適化の方法」、人工知能、119 (1–2): 275–286、arXiv : cond-mat/9901351、doi :10.1016/S0004-3702(00)00007-2、S2CID  7128022
• Boettcher, S. (2000). 「極限最適化: 共進化雪崩によるヒューリスティック」.科学と工学におけるコンピューティング. 2 (6). 電気電子技術者協会 (IEEE): 75–82. arXiv : cond-mat/0006374 . Bibcode :2000CSE.....2f..75B. doi :10.1109/5992.881710. ISSN  1521-9615. S2CID  7259036.
• Boettcher, Stefan; Percus, Allon G. (2001-06-04). 「極限ダイナミクスによる最適化」. Physical Review Letters . 86 (23). American Physical Society (APS): 5211–5214. arXiv : cond-mat/0010337 . Bibcode :2001PhRvL..86.5211B. doi :10.1103/physrevlett.86.5211. ISSN  0031-9007. PMID  11384460. S2CID  3261749.
• Dall, Jesper; Sibani, Paolo (2001). 「低温でのモンテカルロシミュレーションの高速化。待ち時間法」。Computer Physics Communications . 141 (2): 260–267. arXiv : cond-mat/0107475 . Bibcode :2001CoPhC.141..260D. doi :10.1016/s0010-4655(01)00412-x. ISSN  0010-4655. S2CID  14585624.
• Boettcher, Stefan; Grigni, Michelangelo (2002-01-28). 「極値最適化ヒューリスティックのジャミングモデル」. J​​ournal of Physics A: Mathematical and General . 35 (5). IOP Publishing: 1109–1123. arXiv : cond-mat/0110165 . Bibcode :2002JPhA...35.1109B. doi :10.1088/0305-4470/35/5/301. ISSN  0305-4470. S2CID  640976.
• Souham Meshoul と Mohamed Batouche、「極値ダイナミクスによる最適化を使用した画像レジストレーションのための堅牢なポイント対応」^{[永久リンク切れ‍ ]}、Lecture Notes in Computer Science 2449、330–337 (2002)
• Onody, Roberto N.; De Castro, Paulo A. (2003). 「自己組織化臨界性、最適化、生物多様性」。International Journal of Modern Physics C . 14 (7). World Scientific Pub Co Pte Lt: 911–916. arXiv : cond-mat/0302260 . Bibcode :2003IJMPC..14..911O. doi :10.1142/s0129183103005054. ISSN  0129-1831. S2CID  14553130.
• Boettcher, Stefan; Percus, Allon G. (2004-06-24). 「3色問題の位相遷移における極値最適化」. Physical Review E . 69 (6). American Physical Society (APS): 066703. arXiv : cond-mat/0402282 . Bibcode :2004PhRvE..69f6703B. doi :10.1103/physreve.69.066703. ISSN  1539-3755. PMID  15244779. S2CID  3070942.
• Middleton, A. Alan (2004-05-14). 「Ising スピン グラスの極値最適化の改善」. Physical Review E. 69 ( 5). American Physical Society (APS): 055701(R). arXiv : cond-mat/0402295 . Bibcode :2004PhRvE..69e5701M. doi :10.1103/physreve.69.055701. ISSN  1539-3755. PMID  15244875. S2CID  28439352.
• Heilmann, F; Hoffmann, K. H; Salamon, P (2004). 「極値最適化ランクにおける最良確率分布」. Europhysics Letters (EPL) . 66 (3). IOP Publishing: 305–310. Bibcode :2004EL.....66..305H. doi :10.1209/epl/i2004-10011-3. ISSN  0295-5075. S2CID  250810936.
• [1] ポンタス・スヴェンソン、「センサーレポート前処理のための極値最適化」、Proc SPIE 5429、162–171（2004）
• Zhou, Tao; Bai, Wen-Jie; Cheng, Long-Jiu; Wang, Bing-Hong (2005-07-06). 「Lennard-Jones クラスターの連続極値最適化」. Physical Review E. 72 ( 1). American Physical Society (APS): 016702. arXiv : cond-mat/0411428 . Bibcode :2005PhRvE..72a6702Z. doi :10.1103/physreve.72.016702. ISSN  1539-3755. PMID  16090129. S2CID  26578844.
• Duch, Jordi; Arenas, Alex (2005-08-24). 「極値最適化を用いた複雑ネットワークにおけるコミュニティ検出」. Physical Review E. 72 ( 2). American Physical Society (APS): 027104. arXiv : cond-mat/0501368 . Bibcode :2005PhRvE..72b7104D. doi :10.1103/physreve.72.027104. ISSN  1539-3755. PMID  16196754. S2CID  13898113.
• Ahmed, E.; Elettreby, MF (2006). 「生物学に動機づけられた組み合わせ最適化について」.応用数学と計算. 172 (1). Elsevier BV: 40–48. doi :10.1016/j.amc.2005.01.122. ISSN  0096-3003.

• ステファン・ベッチャー – エモリー大学物理学科
• アロン・パーカス – クレアモント大学院大学
• グローバル最適化アルゴリズム – 理論と応用 – 2008-09-11 にWayback Machineにアーカイブ– Thomas Weise