コンピュータサイエンスと数学的最適化 において、メタヒューリスティックとは、特に不完全または不完全な情報や限られた計算能力がある場合に、最適化問題または機械学習問題に対して十分に優れた解を提供できるヒューリスティック（部分探索アルゴリズム）を見つけ、生成し、調整し、選択するように設計された高レベルの手順または発見的方法である。[1] [2] [3] [4]メタヒューリスティックは、完全に列挙したり探索したりするには大きすぎるソリューションのサブセットをサンプリングする。メタヒューリスティックでは、解決する最適化問題について比較的少ない仮定を行う可能性があるため、さまざまな問題に使用できる可能性がある。[1] [5] [6]計算時間が長すぎるか、提供されたソリューションが不正確すぎるなどの理由で、正確な方法または他の（近似）方法が利用できないか適切でない場合、メタヒューリスティックの使用は常に興味深いものである。

最適化アルゴリズムや反復法と比較すると、メタヒューリスティックスは、ある種の問題でグローバルに最適な解が見つかることを保証しません。 [4]多くのメタヒューリスティックスは、何らかの形の確率的最適化を実装しているため、見つかった解は、生成されたランダム変数の集合に依存します。[3]組み合わせ最適化では、 NP完全問題のクラスに属し、比較的低い複雑度から許容時間内に正確に解決することができなくなった問題が多数あります。[7] [8]そのため、メタヒューリスティックスは、近似法、反復法、または単純なヒューリスティックスよりも少ない計算量で優れたソリューションを提供することがよくあります。[4] [1]これは、連続または混合整数最適化の分野にも当てはまります。[1] [9] [10]このように、メタヒューリスティックスは、最適化問題に対する有用なアプローチです。[3]この主題に関する書籍や調査論文がいくつか出版されています。[3] [4] [1] [11] [12]メタヒューリスティック最適化に関する文献レビュー[13]では、メタヒューリスティックスという言葉を作ったのはフレッド・グローバーであると示唆されている。[14]

メタヒューリスティックスに関する文献のほとんどは実験的な性質を持ち、アルゴリズムを用いたコンピュータ実験に基づく経験的結果を記述しています。しかし、収束性や大域的最適解の発見可能性など、正式な理論的結果もいくつか存在します。[4] [15]また、ノー・フリー・ランチ定理も言及する価値があります。これは、与えられた問題に対して、他のすべてのメタヒューリスティックよりも優れたメタヒューリスティックは存在しないというものです。

特に2000年代以降、多くのメタヒューリスティック手法が、その新規性と実用的有効性を謳って発表されてきました。この分野には質の高い研究も数多く存在しますが、近年の発表の多くは質の低いものであり、曖昧さ、概念の精緻化の欠如、実験の不備、先行研究の無視といった欠陥が見られます。[16] [17]

プロパティ

これらはほとんどのメタヒューリスティックの特徴である。[4]

  • メタヒューリスティックスは、検索プロセスを導く戦略です。
  • 目標は、最適または最適に近いソリューションを見つけるために、検索空間を効率的に探索することです。
  • メタヒューリスティックアルゴリズムを構成する技術は、単純なローカル検索手順から複雑な学習プロセスまで多岐にわたります。
  • メタヒューリスティックアルゴリズムは近似的であり、通常は非決定論的です。
  • メタヒューリスティクスは特定の問題に特化するものではありません。しかし、連続最適化[18] [19]や組合せ最適化[20]といった特定の問題群に関連して開発されることも多く、その後、一般化されるケースも見られます。[21] [22]
  • メタヒューリスティックの高レベル戦略によって制御されるヒューリスティックの形でドメイン固有の知識を活用できます。
  • 検索空間の特定の領域で行き詰まるのを防ぐメカニズムを組み込むことができます。
  • 現代のメタヒューリスティックでは、検索を制御するために検索履歴がよく使用されます。

分類

メタヒューリスティックスの異なる分類のオイラー図[23]

メタヒューリスティックスにはさまざまな種類があり[3] [1]、それらを分類するための特性も数多く存在します。[4] [24] [25] [26]したがって、以下のリストは例として理解されるべきです。

一つのアプローチは、探索戦略の種類を特徴づけることである。[4]探索戦略の一つの種類は、単純な局所探索アルゴリズムの改良である。よく知られた局所探索アルゴリズムの一つに、局所最適解を求めるために使用されるヒルクライミング法がある。しかし、ヒルクライミング法は大域最適解の発見を保証するものではない。

より良い解を見つけるために、局所探索ヒューリスティックを改良するメタヒューリスティックのアイデアが数多く提案されています。このようなメタヒューリスティックには、シミュレーテッドアニーリング、タブーサーチ、反復局所探索、可変近傍探索、GRASPなどがあります。[4]これらのメタヒューリスティックは、局所探索型メタヒューリスティックとグローバル探索型メタヒューリスティックに分類できます。

局所探索ベースではない他のグローバル探索メタヒューリスティックは、通常、集団ベースメタヒューリスティックです。このようなメタヒューリスティックには、アリコロニー最適化、遺伝的アルゴリズムや進化戦略などの進化計算、粒子群最適化、ライダー最適化アルゴリズム[27]、バクテリア採餌アルゴリズム[28]などがあります。

単一ソリューション vs. 人口ベース

もうひとつの分類の次元は、単一解と集団ベースの探索である。[4] [12]単一解アプローチは、単一の候補解の修正と改善に焦点を当てる。単一解メタヒューリスティックスには、シミュレーテッドアニーリング、反復局所探索、可変近傍探索、誘導局所探索などがある。[12]集団ベースのアプローチは、複数の候補解を維持・改善し、多くの場合、集団の特性を使用して探索を導く。集団ベースのメタヒューリスティックスには、進化計算や粒子群最適化などがある。[12]メタヒューリスティックスのもうひとつのカテゴリは群知能で、これは集団または群れの中の分散型自己組織化エージェントの集合的行動である。蟻コロニー最適化、[29] 粒子群最適化、[12] 社会的認知最適化、細菌採餌アルゴリズム[28]などがこのカテゴリの例である。

ハイブリッド化とミームアルゴリズム

ハイブリッドメタヒューリスティックとは、メタヒューリスティックと他の最適化手法（数理計画法、制約プログラミング、機械学習などのアルゴリズム）を組み合わせたものです。ハイブリッドメタヒューリスティックの両コンポーネントは同時に実行され、探索を導くために情報を交換することができます。

一方、ミームアルゴリズム[30]は、進化的アプローチや集団ベースのアプローチと、問題探索のための個別の個体学習または局所改善手順との相乗効果を表す。ミームアルゴリズムの一例として、進化的アルゴリズムにおいて、基本的な突然変異演算子の代わりに、あるいはそれに加えて局所探索アルゴリズムを用いることが挙げられる。

並列メタヒューリスティック

並列メタヒューリスティックとは、並列プログラミングの手法を使用して複数のメタヒューリスティック検索を並列に実行するものです。これらは、単純な分散スキームから、相互作用して全体的なソリューションを改善する同時検索実行までの範囲にわたります。

集団ベースのメタヒューリスティックでは、個体群自体を並列化するために、個体またはグループをそれぞれ別のスレッドで処理するか、メタヒューリスティック自体を1台のコンピュータで実行し、子孫を反復ごとに分散的に評価することができます。[31]後者は、評価にかかる計算量が子孫の生成にかかる計算量よりも大幅に大きい場合に特に有用です。これは多くの実用的なアプリケーション、特にシミュレーションに基づく解の品質計算において当てはまります。[32] [33]

自然に着想を得たメタファーベースのメタヒューリスティック

非常に活発な研究分野の一つに、自然に着想を得たメタヒューリスティックスの設計があります。近年の多くのメタヒューリスティックス、特に進化計算に基づくアルゴリズムは、自然界のシステムに着想を得ています。自然界は、複雑な計算問題に対処するための人工計算システムを設計するための概念、メカニズム、原理の源泉となっています。このようなメタヒューリスティックスには、シミュレーテッドアニーリング、進化アルゴリズム、アントコロニー最適化、粒子群最適化などがあります。

近年のメタファーに着想を得たメタヒューリスティックの多くは、その新規性の欠如を複雑なメタファーの背後に隠しているとして、研究コミュニティから批判を浴び始めている。 [16] [17] [25] [34]その結果、この分野の著名な科学者の多くが、メタヒューリスティックの標準化を推進し、比較可能性を高めるなどの研究課題を提案している。[35]もう一つの結果として、多くの科学雑誌の出版ガイドラインがそれに応じて改訂された。[36] [37] [38]

アプリケーション

ほとんどのメタヒューリスティックは探索手法であり、それらを用いる場合、評価関数は数学的最適化よりも高い要求を満たす必要があります。望ましい目標状態を定式化する必要があるだけでなく、探索プロセスをサポートし加速させるために、目標到達までの途中における解の改善に対しても評価を与える必要があります。進化的アルゴリズムやミーム的アルゴリズムの適応度関数がその一例です。

メタヒューリスティクスは、連続問題から混合整数問題、組合せ最適化、またはそれらの組み合わせに至るまで、あらゆる種類の最適化問題に使用されます。 [9] [39] [40]組合せ最適化では、離散的な探索空間で最適解が探索されます。問題の一例としては巡回セールスマン問題があり、この問題では、候補解の探索空間が問題のサイズが大きくなるにつれて指数関数よりも速く増加し、最適解の網羅的な探索が不可能になります。 [41] [42]さらに、形状探索や挙動探索などの工学におけるほとんどの設計問題[6] [43] [44] [45]を含む多次元の組合せ問題は次元の呪いに悩まされており、これも網羅的な探索や解析手法の実行を不可能にします。

メタヒューリスティクスはスケジューリング問題にも頻繁に適用されています。この組み合わせタスクの代表的な例としては、ジョブショップスケジューリングが挙げられます。これは、すべてのジョブが予定通りに、かつ全体として最短時間で完了するように、ジョブの作業ステップを処理ステーションに割り当てることを含みます。[5] [46]実際には、例えば、定義済みのワークフロー[47]を通じてジョブの作業ステップの許容される順序を制限したり、例えばエネルギー需要の平滑化といった形でリソース利用に関して制限したりするなど、制約を遵守しなければならないことがよくあります。[48] [49]組み合わせ問題に対する一般的なメタヒューリスティクスとしては、Holland らによる遺伝的アルゴリズム[50] 、Glover による散布探索[51]、タブー探索[52]などがあります。

もう一つの大きな応用分野は、連続または混合整数探索空間における最適化タスクです。これには、例えば設計最適化[6] [53] [54]や様々なエンジニアリングタスクが含まれます。[55] [56] [57]組み合わせ最適化と連続最適化を組み合わせた例としては、産業用ロボットの好ましい動作経路の計画が挙げられます。[58] [59]

メタヒューリスティック最適化フレームワーク

MOFは、「メタヒューリスティックスのセットの正確で再利用可能な実装と、そのパートナーの従属ヒューリスティックスの実装を加速するための基本メカニズム（ソリューションエンコーディングとテクニック固有の演算子を含む可能性がある）を提供するソフトウェアツールのセットであり、提供されたテクニックを使用して特定の問題インスタンスを解決するために必要なもの」と定義できます。[60]

様々な機能を持つMOFとして考えられる最適化ツールは数多く存在します。以下の33種類のMOFは、それぞれ詳細な比較・評価が行われています。[60] Comet、EvA2、evolvica、Evolutionary::Algorithm、GAPlayground、jaga、JCLEC、JGAP、jMetal、n-genes、Open Beagle、Opt4j、ParadisEO/EO、Pisa、Watchmaker、FOM、Hypercube、HotFrame、Templar、EasyLocal、iOpt、OptQuest、JDEAL、Optimization Algorithm Toolkit、HeuristicLab、MAFRA、Localizer、GALIB、DREAM、Discropt、MALLBA、MAGMA、UOF。並列実装のサポートに関する論文は数多く発表されていますが、特に2010年代後半以降は、本比較研究では取り上げられていませんでした。[32] [33] [61] [62] [63]

貢献

様々なメタヒューリスティックスが存在し、新たな亜種が絶えず提案されています。この分野への最も重要な貢献には、以下のようなものがあります。

参照

参考文献

  1. ^ abcdef Glover, F.; Kochenberger, GA (2003).メタヒューリスティックスハンドブック. 第57巻. Springer, International Series in Operations Research & Management Science. ISBN  978-1-4020-7263-5。
  2. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2015). 「マイクロアレイ遺伝子発現データバイクラスタリングのための恒星質量ブラックホール最適化」.応用人工知能. 29 (4): 353– 381. doi : 10.1080/08839514.2015.1016391 . S2CID  44624424.
  3. ^ abcde Bianchi, Leonora; Marco Dorigo; Luca Maria Gambardella; Walter J. Gutjahr (2009). 「確率的組合せ最適化のためのメタヒューリスティックスに関する概説」(PDF) . Natural Computing . 8 (2): 239– 287. doi :10.1007/s11047-008-9098-4. S2CID  9141490.
  4. ^ abcdefghij Blum, Christian; Roli, Andrea (2003). 「組み合わせ最適化におけるメタヒューリスティックス：概要と概念比較」ACMコンピューティングサーベイ35 (3) . ACM: 268– 308. doi :10.1145/937503.937505.
  5. ^ ab Jarboui, Bassem; Siarry, Patrick; Teghem, Jacques 編 (2013). 生産スケジューリングのためのメタヒューリスティクス. オートメーション - 制御および産業工学シリーズ. ロンドン: ISTE. ISBN 978-1-84821-497-2。
  6. ^ abc Gupta, Shubham; Abderazek, Hammoudi; Yıldız, Betül Sultan; Yildiz, Ali Riza; Mirjalili, Seyedali; Sait, Sadiq M. (2021). 「制約付き機械設計最適化問題を解くためのメタヒューリスティック最適化アルゴリズムの比較」 . Expert Systems with Applications . 183 115351. doi :10.1016/j.eswa.2021.115351. hdl : 10072/407991 .
  7. ^ ピーター・ブラッカー;クヌスト、シグリッド（2012）。複雑なスケジュール設定。ベルリン、ハイデルベルク：シュプリンガー。土井：10.1007/978-3-642-23929-8。ISBN 978-3-642-23928-1。
  8. ^ パパディミトリウ, クリストス・H.; シュタイグリッツ, ケネス (1998). 『組み合わせ最適化：アルゴリズムと複雑性』 ミネオラ, NY: ドーバー出版, 1982年にプレンティス・ホール社から出版された著作の訂正・完全版。ISBN 978-0-486-40258-1。
  9. ^ ab Gad, Ahmed G. (2022). 「粒子群最適化アルゴリズムとその応用：系統的レビュー」.工学計算手法アーカイブ. 29 (5): 2531– 2561. doi : 10.1007/s11831-021-09694-4 . ISSN  1134-3060.
  10. ^ Li, Zhenhua; Lin, Xi; Zhang, Qingfu; Liu, Hailin (2020). 「連続最適化のための進化戦略：最先端技術の概観」 .群集と進化計算. 56 100694. doi :10.1016/j.swevo.2020.100694.
  11. ^ Goldberg, DE (1989).遺伝的アルゴリズムによる探索、最適化、機械学習. Kluwer Academic Publishers. ISBN  978-0-201-15767-3。
  12. ^ abcde Talbi, EG. (2009).メタヒューリスティックス：設計から実装まで. Wiley. ISBN  978-0-470-27858-1。
  13. ^ XS Yang, メタヒューリスティック最適化, Scholarpedia, 6(8):11472 (2011).
  14. ^ Glover, Fred (1986年1月). 「整数計画法の将来的展望と人工知能へのリンク」(PDF) . Computers and Operations Research . 13 (5): 533– 549. doi :10.1016/0305-0548(86)90048-1. ISSN  0305-0548.
  15. ^ ルドルフ、ギュンター (2001). 「自己適応的突然変異は早期収束につながる可能性がある」. IEEE Transactions on Evolutionary Computation . 5 (4): 410– 414. Bibcode :2001ITEC....5..410R. doi :10.1109/4235.942534. hdl : 2003/5378 .
  16. ^ ab Sörensen, Kenneth (2015). 「メタヒューリスティックス ― メタファーの顕在化」. International Transactions in Operational Research . 22 (1): 3– 18. CiteSeerX 10.1.1.470.3422 . doi :10.1111/itor.12001. S2CID  14042315. 
  17. ^ ab アレクサンダー・ブラウンリー、ジョン・R・ウッドワード（2015年6月3日）「なぜ私たちは自然に触発されたアルゴリズムに魅力を感じなくなったのか」The Conversation（ウェブサイト） . 2024年8月30日閲覧。
  18. ^ シュヴェフェル、ハンス＝ポール（1995年）「進化と最適解の探求」第6世代コンピュータ技術シリーズ、ニューヨーク：ワイリー、ISBN 978-0-471-57148-3。
  19. ^ エバーハート、R.; ケネディ、J. (1995)、「粒子群理論を用いた新しい最適化装置」、MHS'95会議論文集、IEEE、pp.  39– 43、doi :10.1109/MHS.1995.494215、ISBN 978-0-7803-2676-7
  20. ^ アルベルト・コロニ;ドリゴ、マルコ。ヴィットリオ・マニエッツォ (1991)、ヴァレラ・F. Bourgine, P. (編)、「アリのコロニーによる分散最適化」、Conf.手順ECAL91 - 人工生命に関する欧州会議、アムステルダム: Elsevier Publ.、 134 ～ 142ページ 、 ISBN 9780262720199
  21. ^ Socha, Krzysztof; Dorigo, Marco (2008). 「連続領域におけるアリコロニー最適化」 .ヨーロッパオペレーションズリサーチジャーナル. 185 (3): 1155– 1173. doi :10.1016/j.ejor.2006.06.046.
  22. ^ ニッセン、フォルカー; Krause、Matthias (1994)、Reusch、Bernd (編)、「Constrained Combinatorial Optimization with an Evolution Strategy」、Fuzzy Logik、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp.  33–40、doi :10.1007/978-3-642-79386-8_5、ISBN 978-3-540-58649-4、 2024年8月24日取得
  23. ^ メタヒューリスティックスの分類
  24. ^ Raidl, Günther R. (2006), Almeida, Francisco; Blesa Aguilera, María J.; Blum, Christian; Moreno Vega, José Marcos (eds.), "A Unified View on Hybrid Metaheuristics" , Hybrid Metaheuristics , Lecture Notes in Computer Science, vol. 4030, Berlin, Heidelberg: Springer Berlin Heidelberg, pp.  1– 12, doi :10.1007/11890584_1, ISBN 978-3-540-46384-9、 2024年8月24日取得
  25. ^ ab Glover, Fred; Sörensen, Kenneth (2015). 「メタヒューリスティックス」Scholarpedia . 10 (4): 6532. doi : 10.4249/scholarpedia.6532 . ISSN  1941-6016.
  26. ^ Birattari, Mauro; Paquete, Luis; Stützle, Thomas; Varrentrapp, Klaus (2001). 「メタヒューリスティックスの分類と成分分析のための実験計画法」S2CID  18347906.
  27. ^ D, Binu (2019). 「RideNN：アナログ回路の故障診断のための新しいライダー最適化アルゴリズムベースのニューラルネットワーク」. IEEE Transactions on Instrumentation and Measurement . 68 (1): 2– 26. Bibcode :2019ITIM...68....2B. doi :10.1109/TIM.2018.2836058. S2CID  54459927.
  28. ^ ab Pang, Shinsiong; Chen, Mu-Chen (2023-06-01). 「改良型バクテリア採餌アルゴリズムを用いた鉄道乗務員スケジュールの最適化」 . Computers & Industrial Engineering . 180 109218. doi :10.1016/j.cie.2023.109218. ISSN  0360-8352. S2CID  257990456.
  29. ^ ab M. Dorigo、最適化、学習、および自然アルゴリズム、博士論文、ミラノ工科大学、イタリア、1992 年。
  30. ^ ab Moscato, P. (1989). 「進化、探索、最適化、遺伝的アルゴリズム、そして格闘技：ミームアルゴリズムに向けて」Caltech 並​​行計算プログラム(レポート826).
  31. ^ Cantú-Paz, Erick (2001). 効率的かつ正確な並列遺伝的アルゴリズム. 遺伝的アルゴリズムと進化的計算. 第1巻. ボストン, マサチューセッツ州: Springer US. doi :10.1007/978-1-4615-4369-5. ISBN 978-1-4613-6964-6。
  32. ^ ab Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.), "Parallel Evolutionary Algorithms" , Springer Handbook of Computational Intelligence , ベルリン, ハイデルベルク: Springer, pp.  929– 959, doi :10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5、2024年9月4日取得
  33. ^ ab Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02)、「ポピュレーションベースメタヒューリスティックスの階層的並列化のための汎用的で柔軟かつスケーラブルなフレームワーク」、第12回デジタルエコシステム管理国際会議（MEDES'20）論文集、ACM、pp.  124– 131、doi :10.1145/3415958.3433041、ISBN 978-1-4503-8115-4
  34. ^ Lones, Michael A. (2014), Igel, Christian (ed.), 「自然にインスパイアされたアルゴリズムのメタヒューリスティック」、2014 Annual Conference on Genetic and Evolutionary Computation (GECCO'14) のコンパニオン出版物の議事録、ACM Conferences、ニューヨーク、NY: ACM、pp.  1419– 1422、doi :10.1145/2598394.2609841、ISBN 978-1-4503-2881-4
  35. ^ スワン、ジェリー;アドリアンセン、スティーブン。ビシュル、モハメッド。バーク、エドマンド K.ジョン・A・クラーク;デ・コースマッケ、パトリック。ドゥリージョ、フアン・ホセ。ハモンド、ケビン。ハート、エマ。ジョンソン、コリン G.コチス、ゾルタン A.ベン・コヴィッツ。クラヴィエツ、クシシュトフ。マーティン、サイモン。メレロ、フアン・J。ミンク、レアンドロ L.オズカン、エンダー。パパ、ジゼル・ロボ。ペッシュ、エルヴィン。ガルシア＝サンチェス、パブロ。シャーフ、アンドレア。シム、ケビン。スミス、ジム。シュトゥッツル、トーマス。ワーグナー、ステファン（2015）。 「メタヒューリスティック標準化の研究課題」(PDF)。意味学者。S2CID  63728283 。2024年8月30日閲覧。
  36. ^ 「Journal of Heuristic Policies on Heuristic Search Research」（PDF） . Journal of Heuristics - 投稿ガイドライン. 2017年7月9日時点のオリジナルよりアーカイブ。 2024年9月1日閲覧。
  37. ^ 「目的と範囲」. 4OR . 2024年9月1日閲覧。
  38. ^ 「目的と範囲」Memetic Computing . 2024年9月1日閲覧。
  39. ^ アルメイダ、フランシスコ;ブレサ・アギレラ、マリア・J。ブルーム、クリスチャン。モレノ・ベガ、ホセ・マルコス。ペレス・ペレス、メルキアデス。ローリー、アンドレア。サンペルズ、マイケル編。 （2006年）。ハイブリッドメタヒューリスティック。コンピューターサイエンスの講義ノート。 Vol. 4030. ベルリン、ハイデルベルク: Springer。土井：10.1007/11890584。ISBN 978-3-540-46384-9。
  40. ^ Neri, Ferrante; Cotta, Carlos; Moscato, Pablo (編著) (2012). ミームアルゴリズムハンドブック. 計算知能研究. 第379巻. ベルリン, ハイデルベルク: Springer Berlin Heidelberg. doi :10.1007/978-3-642-23247-3. ISBN 978-3-642-23246-6。
  41. ^ Dorigo, M.; Gambardella, LM (1997年4月). 「アリコロニーシステム：巡回セールスマン問題への協力学習アプローチ」IEEE Transactions on Evolutionary Computation . 1 (1): 53– 66. doi :10.1109/4235.585892.
  42. ^ メルツ、ピーター；フライスレーベン、ベルント（2002年）「巡回セールスマン問題に対するミームアルゴリズム」複雑系研究13 （ 4）。
  43. ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. NSGA-IIに基づく遺伝的アルゴリズムを用いた電力分配システムのパレート最適再構成．エネルギー．2013; 6(3):1439–1455.
  44. ^ Ganesan, T.; Elamvazuthi, I.; Ku Shaari, Ku Zilati; Vasant, P. (2013-03-01). 「群知能と重力探索アルゴリズムを用いた合成ガス生産の多目的最適化」. Applied Energy . 103 : 368– 374. Bibcode :2013ApEn..103..368G. doi :10.1016/j.apenergy.2012.09.059.
  45. ^ Ganesan, T.; Elamvazuthi, I.; Vasant, P. (2011-11-01). 「生砂型システムの多目的最適化のための進化的正規境界交差法（ENBI）法」. 2011 IEEE International Conference on Control System, Computing and Engineering . pp.  86– 91. doi :10.1109/ICCSCE.2011.6190501. ISBN 978-1-4577-1642-3. S2CID  698459。
  46. ^ Xhafa, Fatos; Abraham, Ajith編 (2008). 産業・製造業におけるスケジューリングのためのメタヒューリスティクス. 計算知能研究. 第128巻. ベルリン、ハイデルベルク: Springer Berlin Heidelberg. doi :10.1007/978-3-540-78985-7. ISBN 978-3-540-78984-0. S2CID  42238720。
  47. ^ Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang (2013-04-22). 「マルチ基準ミームコンピューティングを用いた制約付き異種リソースへの複数ワークフローの高速再スケジュール」.アルゴリズム. 6 (2): 245– 277. doi : 10.3390/a6020245 . ISSN  1999-4893.
  48. ^ Kizilay, Damla; Tasgetiren, M. Fatih; Pan, Quan-Ke; Süer, Gürsel (2019). 「エネルギー効率の高いブロッキングフローショップスケジューリング問題のためのメタヒューリスティックのアンサンブル」. Procedia Manufacturing . 39 : 1177–1184 . doi : 10.1016/j.promfg.2020.01.352 . S2CID  213710393.
  49. ^ Grosch, Benedikt; Weitzel, Timm; Panten, Niklas; Abele, Eberhard (2019). 「複数のエネルギーキャリアを用いたエネルギー適応型生産スケジューリングのためのメタヒューリスティックと実生産システムへの実装」Procedia CIRP . 80 : 203– 208. doi : 10.1016/j.procir.2019.01.043 . S2CID  164850023.
  50. ^ ab Holland, JH (1975). 『自然システムと人工システムにおける適応』ミシガン大学出版局. ISBN  978-0-262-08213-6。
  51. ^ ab Glover, Fred (1977). 「代理制約を用いた整数計画法のヒューリスティックス」. Decision Sciences . 8 (1): 156– 166. CiteSeerX 10.1.1.302.4071 . doi :10.1111/j.1540-5915.1977.tb01074.x.  
  52. ^ ab Glover, F. (1986). 「整数計画法の将来展望と人工知能へのリンク」.コンピュータとオペレーションズ・リサーチ. 13 (5): 533– 549. doi :10.1016/0305-0548(86)90048-1.
  53. ^ クインテ、アレクサンダー、ヤコブ、ウィルフリード、シェラー、クラウス・ペーター、エッゲルト、ホルスト（2002年）、ラウドン、マシュー（編）「進化的アルゴリズムと離散要素法に基づくシミュレーションを用いたマイクロアクチュエータプレートの最適化」、マイクロシステムのモデリングとシミュレーションに関する国際会議：MSM 2002、マサチューセッツ州ケンブリッジ：コンピューテーショナル・パブリケーションズ、pp.  192– 197、ISBN 978-0-9708275-7-9
  54. ^ Parmee, IC (1997), Dasgupta, Dipankar; Michalewicz, Zbigniew (編), 「進化的/適応的探索と工学設計プロセスの統合戦略」 ,進化的アルゴリズム工学応用, ベルリン, ハイデルベルク: Springer, pp.  453– 477, doi :10.1007/978-3-662-03423-1_25, ISBN 978-3-642-08282-5、 2023年7月17日取得
  55. ^ Valadi, Jayaraman; Siarry, Patrick 編 (2014). プロセスエンジニアリングにおけるメタヒューリスティクスの応用. 出版社: Springer International Publishing. doi :10.1007/978-3-319-06508-3. ISBN 978-3-319-06507-6. S2CID  40197553。
  56. ^ サンチェス, エルネスト; スクイレロ, ジョヴァンニ; トンダ, アルベルト (2012). 進化アルゴリズムの産業応用. インテリジェントシステムリファレンスライブラリ. 第34巻. ベルリン, ハイデルベルク: シュプリンガー. doi :10.1007/978-3-642-27467-1. ISBN 978-3-642-27466-4。
  57. ^ Akan, Taymaz; Anter, Ahmed M.; Etaner-Uyar, A. Şima; Oliva, Diego 編 (2023). 現代メタヒューリスティックスの工学応用. 計算知能研究. 第1069巻. 出版社: Springer International Publishing. doi :10.1007/978-3-031-16832-1. ISBN 978-3-031-16831-4. S2CID  254222401。
  58. ^ ブルーム、クリスチャン (2000)、カグノーニ、ステファノ (編)、「進化型ソフトウェア GLEAM による最適化された衝突のないロボット動作文生成」、進化型コンピューティングの実世界応用、コンピュータサイエンス講義ノート、第 1803 巻、ベルリン、ハイデルベルク: シュプリンガー、pp.  330– 341、doi :10.1007/3-540-45561-2_32、ISBN 978-3-540-67353-8、 2023年7月17日取得
  59. ^ Pholdee, Nantiwat; Bureerat, Sujin (2018-12-14)、「多目的メタヒューリスティック探索に基づく6Dロボットの多目的軌道計画」、国際ネットワーク・通信・コンピューティング会議 (ICNCC 2018)、ACM、pp.  352– 356、doi :10.1145/3301326.3301356、ISBN 978-1-4503-6553-6、S2CID  77394395
  60. ^ ab パレホ、ホセ・アントニオ;ルイス・コルテス、アントニオ。ロサーノ、セバスティアン。フェルナンデス、パブロ（2012 年 3 月）。 「メタヒューリスティック最適化フレームワーク: 調査とベンチマーク」。ソフトコンピューティング。16 (3): 527–561 .土井:10.1007/s00500-011-0754-8。ISSN  1432-7643。
  61. ^ García-Valdez, Mario; Merelo, JJ (2017-07-15)、「evospace-js: 異種メタヒューリスティックの非同期プールベース実行」、GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference、Companion、ニューヨーク: ACM、pp.  1202– 1208、doi :10.1145/3067695.3082473、ISBN 978-1-4503-4939-0
  62. ^ Lim, Dudy; Ong, Yew-Soon; Jin, Yaochu; Sendhoff, Bernhard; Lee, Bu-Sung (2007年5月). 「グリッドコンピューティングを用いた効率的な階層型並列遺伝的アルゴリズム」. Future Generation Computer Systems . 23 (4): 658– 670. doi :10.1016/j.future.2006.10.008.
  63. ^ ネブロ、アントニオ J.バルバ・ゴンサレス、クリストバル。ニエト、ホセ・ガルシア。コルデロ、ホセ A. Montes、José F. Aldana (2017-07-15)、「jMetaISP フレームワークの設計とアーキテクチャ」、GECCO '17: Proceedings of the Genetic and Eevolutionary Computation Conference、Companion、ニューヨーク: ACM、pp.  1239–1246、doi :10.1145/3067695.3082466、ISBN 978-1-4503-4939-0
  64. ^ Robbins, H.; Monro, S. (1951). 「確率的近似法」(PDF) . Annals of Mathematical Statistics . 22 (3): 400– 407. doi : 10.1214/aoms/1177729586 .
  65. ^ ノースカロライナ州バリチェリ (1954)。 「進化過程における数値計算」。メソッド: 45–68。
  66. ^ Rastrigin, LA (1963). 「多パラメータシステムの極値制御におけるランダム探索法の収束」.オートメーションとリモートコントロール. 24 (10): 1337–1342 .
  67. ^ Matyas, J. (1965). 「ランダム最適化」.オートメーションとリモートコントロール. 26 (2): 246– 253.
  68. ^ Nelder, JA; Mead, R. (1965). 「関数最小化のためのシンプレックス法」. Computer Journal . 7 (4): 308– 313. doi :10.1093/comjnl/7.4.308. S2CID  2208295.
  69. ^ Rechenberg, Ingo (1965). 「実験問題のサイバネティック解決経路」.英国王立航空研究所, 図書館翻訳.
  70. ^ Fogel, L.; Owens, AJ; Walsh, MJ (1966). 『シミュレーテッド・エボリューションによる人工知能』 Wiley. ISBN  978-0-471-26516-0。
  71. ^ Hastings, WK (1970). 「マルコフ連鎖を用いたモンテカルロサンプリング法とその応用」. Biometrika . 57 (1): 97– 109. Bibcode :1970Bimka..57...97H. doi :10.1093/biomet/57.1.97. S2CID  21204149.
  72. ^ Cavicchio, DJ (1970). 「シミュレートされた進化を用いた適応的探索」.技術レポート. ミシガン大学コンピュータ・コミュニケーション科学科. hdl :2027.42/4042.
  73. ^ Kernighan, BW; Lin, S. (1970). 「グラフ分割のための効率的なヒューリスティック手順」. Bell System Technical Journal . 49 (2): 291– 307. Bibcode :1970BSTJ...49..291K. doi :10.1002/j.1538-7305.1970.tb01770.x.
  74. ^ Mercer, RE; Sampson, JR (1978). 「生殖メタプランを用いた適応的探索」Kybernetes . 7 (3): 215– 228. doi :10.1108/eb005486.
  75. ^ Smith, SF (1980). 遺伝的適応アルゴリズムに基づく学習システム（博士論文）. ピッツバーグ大学.
  76. ^ Kirkpatrick, S.; Gelatt Jr., CD; Vecchi, MP (1983). 「シミュレーテッドアニーリングによる最適化」. Science . 220 (4598): 671– 680. Bibcode :1983Sci...220..671K. CiteSeerX 10.1.1.123.7607 . doi :10.1126/science.220.4598.671. PMID  17813860. S2CID  205939.  
  77. ^ Moscato, P.; Fontanari, JF (1990)、「シミュレーテッドアニーリングにおける確率的更新と決定論的更新」、Physics Letters A、146 (4): 204– 208、Bibcode :1990PhLA..146..204M、doi :10.1016/0375-9601(90)90166-L
  78. ^ Dueck, G.; Scheuer, T. (1990)、「閾値受容：シミュレーテッドアニーリングよりも優れた汎用最適化アルゴリズム」、Journal of Computational Physics、90 (1): 161– 175、Bibcode :1990JCoPh..90..161D、doi :10.1016/0021-9991(90)90201-B、ISSN  0021-9991
  79. ^ Wolpert, DH; Macready, WG (1995). 「探索におけるフリーランチ定理の否定」.技術報告書 SFI-TR-95-02-010 . サンタフェ研究所. S2CID  12890367.
  80. ^ Igel, Christian, Toussaint, Marc (2003年6月). 「No Free Lunchの結果が成り立つ関数のクラスについて」. Information Processing Letters . 86 (6): 317– 321. arXiv : cs/0108011 . doi :10.1016/S0020-0190(03)00222-9. ISSN  0020-0190. S2CID  147624.{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  81. ^ Auger, Anne , Teytaud, Olivier (2010). 「Continuous Lunches Are Free Plus the Design of Optimal Optimization Algorithms」. Algorithmica . 57 (1): 121– 146. CiteSeerX 10.1.1.186.6007 . doi :10.1007/s00453-008-9244-5. ISSN  0178-4617. S2CID  1989533. {{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  82. ^ Stefan Droste、Thomas Jansen、Ingo Wegener (2002). 「ランダム化探索ヒューリスティックスによる最適化 ― (A)NFL定理、現実的なシナリオ、そして困難な関数」.理論計算機科学. 287 (1): 131– 144. CiteSeerX 10.1.1.35.5850 . doi :10.1016/s0304-3975(02)00094-4. 

さらに読む

  • セーレンセン、ケネス。マルク・セヴォー。フレッド・グローバー（2017-01-16）。 「メタヒューリスティックの歴史」(PDF)。マルティでは、ラファエル。パノス、パルダロス。レゼンデ、マウリシオ(編)。ヒューリスティックのハンドブック。スプリンガー。ISBN 978-3-319-07123-7。
  • Ashish Sharma (2022), ランダム化ハイパーコンピューティングの観点による自然にインスパイアされたアルゴリズム.情報科学. https://doi.org/10.1016/j.ins.2022.05.020.
  • Fred Glover、Kenneth Sörensen（編）「メタヒューリスティックス」Scholarpedia。
  • この分野の研究者のための EU/ME フォーラム。
  • Metaheuristics.jl いくつかの実装のソース。