Loading article…
コンピュータサイエンスと数理最適化において、メタヒューリスティックとは、特に不完全または不完全な情報や限られた計算能力がある場合に、最適化問題または機械学習問題に対する十分に優れた解を提供できるヒューリスティック（部分探索アルゴリズム）を見つけ、生成し、調整し、選択するように設計された高レベルの手順またはヒューリスティックです。 [1] [2]メタヒューリスティックは、完全に列挙したり探索したりするには大きすぎる解のサブセットをサンプリングします。メタヒューリスティックは、解決する最適化問題について比較的少ない仮定を行う可能性があるため、さまざまな問題に使用できます。[3] [4] [5] [6]計算時間が長すぎるか、提供された解が不正確すぎるなどの理由で、正確な方法や他の（近似）方法が利用できない、または適切でない場合、メタヒューリスティックの使用は常に興味深いものです。
最適化アルゴリズムや反復法と比較すると、メタヒューリスティックスは、ある種の問題でグローバルに最適な解が見つかることを保証しません。 [3]多くのメタヒューリスティックスは、何らかの形の確率的最適化を実装しているため、見つかった解は生成されたランダム変数の集合に依存します。[2]組合せ最適化では、 NP完全問題のクラスに属する問題が多くあり、比較的低い複雑度では許容時間内に正確に解くことができなくなります。[7] [8]そのため、メタヒューリスティックスは、近似法、反復法、または単純なヒューリスティックスよりも少ない計算量で優れた解を提供することがよくあります。[3] [4]これは、連続または混合整数最適化の分野にも当てはまります。[4] [9] [10]このように、メタヒューリスティックスは最適化問題に対する有用なアプローチです。[2]このテーマについては、いくつかの書籍と調査論文が出版されています。[2] [3] [4] [11] [12]メタヒューリスティック最適化に関する文献レビュー[13]では、メタヒューリスティックスという言葉を作ったのはフレッド・グローバーであると示唆されている。[14]
メタヒューリスティックスに関する文献のほとんどは実験的な性質のものであり、アルゴリズムを用いたコンピュータ実験に基づく経験的結果を説明しています。しかし、収束や大域的最適値を見つける可能性に関する正式な理論的結果もいくつかあります。[3] [15]また、特定の問題に対して他のすべてのメタヒューリスティックよりも優れたメタヒューリスティックは存在しないという、 ノーフリーランチ定理も言及する価値があります。
特に2000年代に入ってからは、多くのメタヒューリスティック手法が、新規性と実用的有効性を主張して発表されてきた。この分野では質の高い研究も行われているが、最近の出版物の多くは質が低く、曖昧さ、概念の詳細化の欠如、実験の質の悪さ、先行文献の無視などの欠点がある。[16] [17]
プロパティ
これらはほとんどのメタヒューリスティックスを特徴付ける特性である: [3]
- メタヒューリスティックスは、検索プロセスを導く戦略です。
- 目標は、最適または最適に近いソリューションを見つけるために、検索空間を効率的に探索することです。
- メタヒューリスティック アルゴリズムを構成する技術は、単純なローカル検索手順から複雑な学習プロセスまで多岐にわたります。
- メタヒューリスティックアルゴリズムは近似的であり、通常は非決定論的です。
- メタヒューリスティクスは特定の問題に特化するものではありません。しかし、連続問題[18] [19]や組合せ最適化[20]などの問題クラスに関連して開発され、その後一般化されたケースもあります。[21] [22]
- メタヒューリスティックの高レベル戦略によって制御されるヒューリスティックの形でドメイン固有の知識を活用できます。
- 検索空間の特定の領域で行き詰まるのを防ぐメカニズムを含めることができます。
- 現代のメタヒューリスティックでは、検索を制御するために検索履歴がよく使用されます。
分類
メタヒューリスティックにはさまざまな種類があり[2] [4]、それらを分類するための特性も数多くあります。[3] [24] [25] [26]したがって、以下のリストは例として理解されるべきです。
ローカル検索とグローバル検索
1つのアプローチは、探索戦略のタイプを特徴付けることです。[3]探索戦略の1つのタイプは、単純な局所探索アルゴリズムの改良です。よく知られている局所探索アルゴリズムは、局所最適解を見つけるために使用されるヒルクライミング法です。ただし、ヒルクライミングでは、グローバル最適解が見つかるとは限りません。
より良い解決策を見つけるために、局所探索ヒューリスティックを改善するメタヒューリスティックのアイデアが数多く提案されました。このようなメタヒューリスティックには、シミュレーテッドアニーリング、タブー探索、反復局所探索、可変近傍探索、GRASPなどがあります。[3]これらのメタヒューリスティックは、局所探索ベースまたはグローバル探索メタヒューリスティックに分類できます。
局所探索ベースではない他のグローバル探索メタヒューリスティックは、通常、集団ベースのメタヒューリスティックです。このようなメタヒューリスティックには、アリコロニー最適化、遺伝的アルゴリズムや進化戦略などの進化計算、粒子群最適化、ライダー最適化アルゴリズム[27] 、バクテリア採餌アルゴリズム[28]などがあります。
単一ソリューションと人口ベース
もう 1 つの分類次元は、単一解と集団ベースの探索です。[3] [12]単一解アプローチは、単一の候補解の修正と改善に重点を置いています。単一解のメタヒューリスティックには、シミュレーテッド アニーリング、反復局所探索、可変近傍探索、ガイド付き局所探索が含まれます。[12]集団ベースのアプローチは、多くの場合、集団の特性を使用して探索をガイドし、複数の候補解を維持および改善します。集団ベースのメタヒューリスティックには、進化計算と粒子群最適化が含まれます。 [12]メタヒューリスティックの別のカテゴリは、集団または群れ内の分散型の自己組織化エージェントの集合的な行動である群知能です。蟻コロニー最適化、[29]粒子群最適化、[12]社会的認知最適化、細菌採餌アルゴリズム[28]はこのカテゴリの例です。
ハイブリッド化とミームアルゴリズム
ハイブリッド メタヒューリスティックとは、数理計画法、制約プログラミング、機械学習のアルゴリズムなど、他の最適化手法とメタヒューリスティックを組み合わせたものです。ハイブリッド メタヒューリスティックの両方のコンポーネントは同時に実行され、検索をガイドするために情報を交換します。
一方、ミームアルゴリズム[30]は、進化的アプローチや集団ベースのアプローチと、問題探索のための個別の個別学習または局所的改善手順との相乗効果を表しています。ミームアルゴリズムの例としては、進化的アルゴリズムにおける基本的な突然変異演算子の代わりに、またはそれに加えて局所探索アルゴリズムを使用することが挙げられます。
並列メタヒューリスティック
並列メタヒューリスティックとは、並列プログラミングの手法を使用して複数のメタヒューリスティック検索を並列に実行するもので、単純な分散スキームから、相互作用して全体的なソリューションを改善する同時検索実行までの範囲にわたります。
集団ベースのメタヒューリスティックでは、個体またはグループをそれぞれ別のスレッドで処理するか、メタヒューリスティック自体を1台のコンピュータで実行して子孫を反復ごとに分散的に評価することで、集団自体を並列化できます。[31]後者は、評価の計算量が子孫の生成の計算量よりもかなり大きい場合に特に便利です。これは多くの実用的なアプリケーション、特にシミュレーションベースのソリューション品質の計算に当てはまります。[32] [33]
自然に着想を得たメタファーベースのメタヒューリスティクス
非常に活発な研究分野は、自然にヒントを得たメタヒューリスティックスの設計です。最近のメタヒューリスティックス、特に進化的計算ベースのアルゴリズムの多くは、自然システムからヒントを得ています。自然は、複雑な計算問題に対処するための人工計算システムを設計するための概念、メカニズム、原理の源泉として機能します。このようなメタヒューリスティックスには、シミュレーテッド アニーリング、進化的アルゴリズム、アント コロニー最適化、粒子群最適化などがあります。
最近のメタファーにヒントを得たメタヒューリスティクスの多くは、その新規性の欠如を手の込んだメタファーで隠しているとして、研究コミュニティから批判を集め始めている。 [16] [17] [25]その結果、この分野の著名な科学者の多くが、メタヒューリスティクスをより比較しやすいものにするために、メタヒューリスティクスの標準化のための研究課題を提案している。[34]もう1つの結果として、多くの科学雑誌の出版ガイドラインがそれに応じて改訂された。[35] [36] [37]
アプリケーション
ほとんどのメタヒューリスティクスは検索方法であり、それらを使用する場合、評価関数は数学的最適化よりも高い要件に従う必要があります。望ましいターゲット状態を定式化する必要があるだけでなく、評価では、検索プロセスをサポートして加速するために、ターゲットへの途中でソリューションの改善を評価する必要があります。進化的アルゴリズムまたはミーム的アルゴリズムの適応関数が例として挙げられます。
メタヒューリスティクスは、連続問題から混合整数問題、組合せ最適化、またはそれらの組み合わせに至るまで、あらゆる種類の最適化問題に使用されます。 [9] [38] [39]組合せ最適化では、離散的な探索空間で最適解が求められます。一例として巡回セールスマン問題が挙げられますが、この問題では、候補解の探索空間が問題のサイズが大きくなるにつれて指数関数よりも速く増加し、最適解を徹底的に探索することが不可能になります。 [40] [41]さらに、形状探索や動作探索などの工学におけるほとんどの設計問題[6] [42] [43] [44]を含む多次元の組合せ問題は次元の呪いに悩まされており、これもまた徹底的な探索や分析手法には実行不可能な問題となっています。
メタヒューリスティクスは、スケジューリング問題にも頻繁に適用されます。この組み合わせタスク クラスの代表的なものはジョブ ショップ スケジューリングです。これは、すべてのジョブが時間どおりに、かつ全体として可能な限り最短時間で完了するように、ジョブの作業ステップを処理ステーションに割り当てます。[5] [45]実際には、たとえば、定義済みのワークフロー[46]を通じてジョブの作業ステップの許容されるシーケンスを制限したり、たとえばエネルギー需要を平滑化する形でリソースの使用率に関して制限したりするなど、制約を遵守しなければならないことがよくあります。 [47] [48]組み合わせ問題に対する一般的なメタヒューリスティクスには、Holland らによる遺伝的アルゴリズム[49] 、Glover による散布探索[50]、タブー探索[51]などがあります。
もう一つの大きな応用分野は、連続または混合整数探索空間における最適化タスクである。これには、例えば、設計最適化[6] [52] [53]やさまざまなエンジニアリングタスクが含まれる。[54] [55] [56]組み合わせ最適化と連続最適化を組み合わせた例としては、産業用ロボットの好ましい動作経路の計画がある。[57] [58]
メタヒューリスティック最適化フレームワーク
MOFは、「メタヒューリスティックスのセットの正確で再利用可能な実装と、提供された技術を使用して特定の問題インスタンスを解決するために必要な、パートナーの従属ヒューリスティックス（ソリューションエンコーディングと技術固有の演算子を含む可能性がある）の実装を加速するための基本メカニズムを提供するソフトウェアツールのセット」と定義できます。[59]
さまざまな機能を持つ MOF として考えられる最適化ツールの候補は多数あります。次の 33 個の MOF は、[59] 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 で詳細に比較および評価されています。並列実装のサポートに関する出版物は多数ありますが、特に 10 年代後半以降は、この比較研究では欠けていました。[32] [33] [60] [61] [62]
貢献
さまざまなメタヒューリスティックスが存在し、新しい変種が継続的に提案されています。この分野への最も重要な貢献のいくつかは次のとおりです。
- 1952年: ロビンスとモンローが確率的最適化手法の研究を行う。[63]
- 1954年:バリチェリは進化プロセスの最初のシミュレーションを実行し、それを一般的な最適化問題に適用しました。[64]
- 1963年: ラストリギンがランダム探索を提案。[65]
- 1965年: マティアスがランダム最適化を提案[66]
- 1965年:ネルダーとミードは単体ヒューリスティックを提案し、パウエルはそれがいくつかの問題において非定常点に収束することを示した。 [67]
- 1965年:インゴ・レッヒェンベルグが最初の進化戦略アルゴリズムを発見。[68]
- 1966年:フォーゲルらが進化プログラミングを提案[69]
- 1970年: ヘイスティングスがメトロポリス・ヘイスティングスのアルゴリズムを提案した。[70]
- 1970年: カヴィッキオは最適化装置の制御パラメータの適応を提案した。[71]
- 1970年: カーニハンとリンは、可変深度探索と禁止ベース（タブー）探索に関連するグラフ分割法を提案した。[72]
- 1975年:ホランドが遺伝的アルゴリズムを提案した。[49]
- 1977年:グローバーが散布探索法を提案。[50]
- 1978年: マーサーとサンプソンは、別のオプティマイザを使用してオプティマイザのパラメータを調整するためのメタプランを提案した。 [73]
- 1980年: スミスが遺伝的プログラミングについて説明[ 74 ]
- 1983年：カークパトリックらがシミュレーテッドアニーリングを提案した。[75]
- 1986年：グローバーがタブー探索を提案し、メタヒューリスティックという用語が初めて登場した。[51]
- 1989年: モスカートがミームアルゴリズムを提案[30]
- 1990年: MoscatoとFontanari [76]とDueckとScheuer [77]はそれぞれ独立して、探索を加速するシミュレーテッドアニーリングの決定論的更新規則を提案した。これにより閾値受容メタヒューリスティックが生まれた。
- 1992年:ドリゴは博士論文でアリコロニー最適化を紹介した。 [29]
- 1995年: ウォルパートとマクレディがフリーランチ定理を証明。[78] [79] [80] [81]
参照
参考文献
- ^ R. Balamurugan ; AM Natarajan; K. Premalatha ( 2015). 「バイクラスタリングマイクロアレイ遺伝子発現データのための恒星質量ブラックホール最適化」。応用人工知能。29 ( 4 ): 353–381。doi : 10.1080/08839514.2015.1016391。S2CID 44624424 。
- ^ 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.
- ^ abcdefghij Blum, Christian; Roli, Andrea (2003). 「組み合わせ最適化におけるメタヒューリスティックス: 概要と概念の比較」ACM Computing Surveys . 35 (3). ACM: 268–308. doi :10.1145/937503.937505.
- ^ abcde Glover, F.; Kochenberger, GA (2003).メタヒューリスティックハンドブック. 第57巻. Springer, International Series in Operations Research & Management Science. ISBN 978-1-4020-7263-5。
- ^ ab Jarboui, Bassem; Siarry, Patrick; Teghem, Jacques 編 (2013)。生産スケジューリングのためのメタヒューリスティック。オートメーション - 制御および産業工学シリーズ。ロンドン: ISTE。ISBN 978-1-84821-497-2。
- ^ abc Gupta, Shubham; Abderazek, Hammoudi; Yıldız, Betül Sultan; Yildiz, Ali Riza; Mirjalili, Seyedali; Sait, Sadiq M. (2021). 「制約付き機械設計最適化問題を解決するためのメタヒューリスティック最適化アルゴリズムの比較」.エキスパートシステムとその応用. 183 : 115351. doi :10.1016/j.eswa.2021.115351.
- ^ ピーター・ブラッカー;クヌスト、シグリッド（2012）。複雑なスケジュール設定。ベルリン、ハイデルベルク：シュプリンガー。土井：10.1007/978-3-642-23929-8。ISBN 978-3-642-23928-1。
- ^ Papadimitriou, Christos H.; Steiglitz, Kenneth (1998).組み合わせ最適化: アルゴリズムと複雑性. ミネオラ、ニューヨーク: ドーバー出版、1982 年に Prentice-Hall から出版された作品の訂正された完全版の新版。ISBN 978-0-486-40258-1。
- ^ ab Gad, Ahmed G. (2022). 「粒子群最適化アルゴリズムとその応用: 体系的レビュー」。工学計算方法アーカイブ。29 ( 5): 2531–2561。doi : 10.1007/ s11831-021-09694-4。ISSN 1134-3060 。
- ^ Li, Zhenhua; Lin, Xi; Zhang, Qingfu; Liu, Hailin (2020). 「継続的な最適化のための進化戦略：最先端の調査」Swarm and Evolutionary Computation . 56 : 100694. doi :10.1016/j.swevo.2020.100694.
- ^ Goldberg, DE (1989).探索、最適化、機械学習における遺伝的アルゴリズム。Kluwer Academic Publishers。ISBN 978-0-201-15767-3。
- ^ abcde Talbi, EG. (2009).メタヒューリスティックス: 設計から実装まで. Wiley. ISBN 978-0-470-27858-1。
- ^ XS Yang, メタヒューリスティック最適化, Scholarpedia, 6(8):11472 (2011).
- ^ Glover, Fred (1986年1月). 「整数計画法の将来的方向性と人工知能へのリンク」(PDF) . Computers and Operations Research . 13 (5): 533–549. doi :10.1016/0305-0548(86)90048-1. ISSN 0305-0548.
- ^ Rudolph, Günter (2001). 「自己適応型突然変異は早期収束につながる可能性がある」. IEEE Transactions on Evolutionary Computation . 5 (4): 410–414. doi :10.1109/4235.942534. hdl : 2003/5378 .
- ^ 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.
- ^ ab ブラウンリー、アレクサンダー、ウッドワード、ジョン・R.「なぜ私たちは自然に触発されたアルゴリズムに魅力を感じなくなったのか」。ザ・カンバセーション（ウェブサイト） 。 2024年8月30日閲覧。
- ^ シュウェフェル、ハンス・ポール（1995年）。進化と最適探索。第6世代コンピュータ技術シリーズ。ニューヨーク：ワイリー。ISBN 978-0-471-57148-3。
- ^ Eberhart, R.; Kennedy, J. (1995)、「粒子群理論を用いた新しい最適化装置」、Conf. Proc. MHS'95、IEEE、pp. 39–43、doi :10.1109/MHS.1995.494215、ISBN 978-0-7803-2676-7
- ^ アルベルト・コロニ;ドリゴ、マルコ。ヴィットリオ・マニエッツォ (1991)、ヴァレラ・F. Bourgine, P. (編)、「アリのコロニーによる分散最適化」、Conf.手順ECAL91 - 人工生命に関する欧州会議、アムステルダム: Elsevier Publ.、134–142 ページ、ISBN 9780262720199
- ^ Socha, Krzysztof; Dorigo, Marco (2008). 「連続ドメインの蟻コロニー最適化」.ヨーロッパオペレーションズリサーチジャーナル. 185 (3): 1155–1173. doi :10.1016/j.ejor.2006.06.046.
- ^ ニッセン、フォルカー; 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日取得
- ^ メタヒューリスティックスの分類
- ^ Raidl, Günther R. (2006)、Almeida, Francisco; Blesa Aguilera, María J.; Blum, Christian; Moreno Vega, José Marcos (編)、「ハイブリッドメタヒューリスティックスの統一的見解」、ハイブリッドメタヒューリスティックス、Lecture Notes in Computer Science、vol. 4030、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 1–12、doi :10.1007/11890584_1、ISBN 978-3-540-46384-9、 2024年8月24日取得
- ^ ab Glover, Fred; Sörensen, Kenneth (2015). 「メタヒューリスティックス」Scholarpedia . 10 (4): 6532. doi : 10.4249/scholarpedia.6532 . ISSN 1941-6016.
- ^ Birattari, Mauro; Paquete, Luis; Stützle, Thomas; Varrentrapp, Klaus (2001). 「メタヒューリスティクスの分類とコンポーネント分析のための実験計画」S2CID 18347906.
- ^ 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.
- ^ 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.
- ^ ab M. Dorigo、最適化、学習、および自然アルゴリズム、博士論文、ミラノ工科大学、イタリア、1992 年。
- ^ ab Moscato, P. (1989). 「進化、探索、最適化、遺伝的アルゴリズム、格闘技について: ミームアルゴリズムに向けて」Caltech 並行計算プログラム(レポート 826)。
- ^ Cantú-Paz, Erick (2001). 効率的で正確な並列遺伝的アルゴリズム。遺伝的アルゴリズムと進化的計算。第 1 巻。ボストン、マサチューセッツ州: Springer US。doi :10.1007 / 978-1-4615-4369-5。ISBN 978-1-4613-6964-6。
- ^ ab Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.)、「並列進化アルゴリズム」、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日取得
- ^ ab Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02)、「ポピュレーションベースメタヒューリスティックの階層的並列化のための汎用的で柔軟かつスケーラブルなフレームワーク」、Proc. of the 12th Int. Conf. on Management of Digital EcoSystems (MEDES'20)、ACM、pp. 124–131、doi :10.1145/3415958.3433041、ISBN 978-1-4503-8115-4
- ^ スワン、ジェリー;アドリアンセン、スティーブン。ビシュル、モハメッド。バーク、エドマンド K.ジョン・A・クラーク;デ・コースマッケ、パトリック；ドゥリージョ、フアン・ホセ。ハモンド、ケビン。ハート、エマ。ジョンソン、コリン G.コチス、ゾルタン A.ベン・コヴィッツ。クラヴィエツ、クシシュトフ。マーティン、サイモン。メレロ、フアン・J.ミンク、レアンドロ L.オズカン、エンダー。パパ、ジゼル・ロボ。ペッシュ、エルヴィン。ガルシア＝サンチェス、パブロ。シャーフ、アンドレア。シム、ケビン。スミス、ジム。シュトゥッツル、トーマス。ワーグナー、ステファン（2015）。 「メタヒューリスティック標準化の研究課題」。意味学者。S2CID 63728283 。2024年8月30日閲覧。
- ^ 「Journal of Heuristic Policies on Heuristic Search Research」（PDF）。Journal of Heuristics - 投稿ガイドライン。 2017年7月9日時点のオリジナルよりアーカイブ。 2024年9月1日閲覧。
- ^ 「目的と範囲」。4OR 。 2024年9月1日閲覧。
- ^ 「目的と範囲」。ミームコンピューティング。 2024年9月1日閲覧。
- ^ アルメイダ、フランシスコ;ブレサ・アギレラ、マリア・J。ブルーム、クリスチャン。モレノ・ベガ、ホセ・マルコス。ペレス・ペレス、メルキアデス。ローリー、アンドレア。サンペルズ、マイケル編。 (2006)。ハイブリッドメタヒューリスティック。コンピューターサイエンスの講義ノート。 Vol. 4030. ベルリン、ハイデルベルク: Springer。土井：10.1007/11890584。ISBN 978-3-540-46384-9。
- ^ 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。
- ^ Dorigo, M.; Gambardella, LM (1997 年 4 月). 「蟻コロニーシステム: 巡回セールスマン問題に対する協調学習アプローチ」. IEEE Transactions on Evolutionary Computation . 1 (1): 53–66. doi :10.1109/4235.585892.
- ^メルツ、ピーター; フライスレーベン、ベルント (2002)。「巡回セールス マン問題のためのミームアルゴリズム」複雑系。13 (4)。
- ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. NSGA-IIに基づく遺伝的アルゴリズムを用いた電力分配システムのパレート最適再構成。エネルギー。2013; 6(3):1439–1455。
- ^ 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.
- ^ Ganesan, T.; Elamvazuthi, I.; Vasant, P. (2011-11-01). 「グリーン砂型システムの多目的最適化のための進化的正規境界交差 (ENBI) 法」。2011 IEEE 国際制御システム、コンピューティング、エンジニアリング会議。pp. 86–91。doi : 10.1109 / ICCSCE.2011.6190501。ISBN 978-1-4577-1642-3. S2CID 698459。
- ^ 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。
- ^ 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。
- ^ 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.
- ^ Grosch, Benedikt; Weitzel, Timm; Panten, Niklas; Abele, Eberhard (2019). 「複数のエネルギーキャリアを使用したエネルギー適応型生産スケジューリングのメタヒューリスティックと実際の生産システムへの実装」。Procedia CIRP . 80 : 203–208. doi : 10.1016/j.procir.2019.01.043 . S2CID 164850023.
- ^ ab Holland, JH (1975).自然システムと人工システムにおける適応. ミシガン大学出版局. ISBN 978-0-262-08213-6。
- ^ 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.
- ^ ab Glover, F. (1986). 「整数計画法の将来的方向性と人工知能へのリンク」.コンピュータとオペレーションズ・リサーチ. 13 (5): 533–549. doi :10.1016/0305-0548(86)90048-1.
- ^ Quinte, Alexander; Jakob, Wilfried; Scherer, Klaus-Peter; Eggert, Horst (2002)、Laudon, Matthew (編)、「離散要素法に基づく進化的アルゴリズムとシミュレーションを使用したマイクロアクチュエータプレートの最適化」、マイクロシステムのモデリングとシミュレーションに関する国際会議: MSM 2002、マサチューセッツ州ケンブリッジ: Computational Publications、pp. 192–197、ISBN 978-0-9708275-7-9
- ^ Parmee, IC (1997)、Dasgupta, Dipankar、Michalewicz, Zbigniew (編)、「進化的/適応的検索とエンジニアリング設計プロセスの統合戦略」、Evolutionary Algorithms in Engineering Applications、ベルリン、ハイデルベルク: Springer、pp. 453–477、doi :10.1007/978-3-662-03423-1_25、ISBN 978-3-642-08282-5、 2023-07-17取得
- ^ Valadi, Jayaraman; Siarry, Patrick, 編 (2014). プロセスエンジニアリングにおけるメタヒューリスティクスの応用. チャム: Springer International Publishing. doi :10.1007/978-3-319-06508-3. ISBN 978-3-319-06507-6. S2CID 40197553。
- ^ Sanchez, Ernesto; Squillero, Giovanni; Tonda, Alberto (2012). 進化的アルゴリズムの産業応用。インテリジェントシステムリファレンスライブラリ。第34巻。ベルリン、ハイデルベルク：Springer。doi ： 10.1007 / 978-3-642-27467-1。ISBN 978-3-642-27466-4。
- ^ Akan, Taymaz; Anter, Ahmed M.; Etaner-Uyar, A. Şima; Oliva, Diego, eds. (2023). 現代メタヒューリスティックスのエンジニアリングアプリケーション。計算知能の研究。Vol. 1069。Cham: Springer International Publishing。doi : 10.1007 /978-3-031-16832-1。ISBN 978-3-031-16831-4. S2CID 254222401。
- ^ ブルーム、クリスチャン (2000)、カグノーニ、ステファノ (編)、「進化型ソフトウェア GLEAM による最適化された衝突のないロボット移動ステートメント生成」、進化型コンピューティングの実世界応用、コンピュータサイエンスの講義ノート、vol. 1803、ベルリン、ハイデルベルク: シュプリンガー、pp. 330–341、doi :10.1007/3-540-45561-2_32、ISBN 978-3-540-67353-8、 2023-07-17取得
- ^ 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
- ^ ab パレホ、ホセ・アントニオ;ルイス・コルテス、アントニオ。ロサーノ、セバスティアン。フェルナンデス、パブロ（2012 年 3 月）。 「メタヒューリスティック最適化フレームワーク: 調査とベンチマーク」。ソフトコンピューティング。16 (3): 527–561。土井：10.1007/s00500-011-0754-8。ISSN 1432-7643。
- ^ 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
- ^ 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 。
- ^ ネブロ、アントニオ 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、土井：10.1145/3067695.3082466、ISBN 978-1-4503-4939-0
- ^ Robbins, H.; Monro, S. (1951). 「確率的近似法」(PDF) . Annals of Mathematical Statistics . 22 (3): 400–407. doi : 10.1214/aoms/1177729586 .
- ^ ノースカロライナ州バリチェリ (1954)。 「進化の過程における数値計算」。メソッド: 45–68。
- ^ Rastrigin, LA (1963). 「多数のパラメータシステムの極値制御におけるランダム探索法の収束」.オートメーションとリモートコントロール. 24 (10): 1337–1342.
- ^ Matyas, J. (1965). 「ランダム最適化」.オートメーションとリモートコントロール. 26 (2): 246–253.
- ^ Nelder, JA; Mead, R. (1965). 「関数最小化のためのシンプレックス法」. Computer Journal . 7 (4): 308–313. doi :10.1093/comjnl/7.4.308. S2CID 2208295.
- ^ Rechenberg, Ingo (1965)。「実験問題のサイバネティック解決経路」。英国王立航空研究所、図書館翻訳。
- ^ Fogel, L.; Owens, AJ; Walsh, MJ (1966). 「シミュレートされた進化による人工知能」 Wiley. ISBN 978-0-471-26516-0。
- ^ Hastings, WK (1970). 「マルコフ連鎖を用いたモンテカルロサンプリング法とその応用」. Biometrika . 57 (1): 97–109. Bibcode :1970Bimka..57...97H. doi :10.1093/biomet/57.1.97. S2CID 21204149.
- ^ Cavicchio, DJ (1970)。「シミュレートされた進化を使用した適応検索」。技術レポート。ミシガン大学、コンピューターおよび通信科学部。hdl : 2027.42/4042。
- ^ Kernighan, BW; Lin, S. (1970). 「グラフを分割するための効率的なヒューリスティック手順」Bell System Technical Journal . 49 (2): 291–307. doi :10.1002/j.1538-7305.1970.tb01770.x.
- ^ Mercer, RE; Sampson, JR (1978). 「生殖メタプランを使用した適応検索」Kybernetes . 7 (3): 215–228. doi :10.1108/eb005486.
- ^ Smith, SF (1980). 遺伝的適応アルゴリズムに基づく学習システム (博士論文). ピッツバーグ大学.
- ^ 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.
- ^ Moscato, P.; Fontanari, JF (1990)、「シミュレーテッドアニーリングにおける確率的更新と決定論的更新」、Physics Letters A、146 (4): 204–208、Bibcode :1990PhLA..146..204M、doi :10.1016/0375-9601(90)90166-L
- ^ 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
- ^ Wolpert, DH; Macready, WG (1995). 「検索のためのフリーランチ定理はない」.技術レポート SFI-TR-95-02-010 . サンタフェ研究所. S2CID 12890367.
- ^ 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: 複数の名前: 著者リスト (リンク) - ^ 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: 複数の名前: 著者リスト (リンク) - ^ 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 いくつかの実装のソース。