1. 序章

このチュートリアルでは、さまざまな自然要素に触発されたメタヒューリスティックアルゴリズムのクラスを調べます。 これには、メタヒューリスティックとは何か、最適化問題を解決するためにメタヒューリスティックが必要な理由を理解する必要があります。 これは、私たちが自然から来るインスピレーションを探求するのに役立ちます。 自然に着想を得た人気のあるアルゴリズムとそのアプリケーションの詳細を見ていきます。

2. 最適化問題とメタヒューリスティック

数学と工学では、最適化問題はすべての実行可能な解決策から最良の解決策を見つける問題です。 通常、このような問題は、一連の制約を持つ1つ以上の変数の目的関数として定義されます。 これらの問題は、関係する変数が離散的であるか連続的であるかに応じて、離散的または連続的である可能性があります。

最適化問題の複雑さは、目的関数とそれが考慮する変数の数に直接関係します。 興味深いことに、多くの実世界の最適化問題は、NP (非決定論的多項式時間)として知られるカテゴリに分類されます。 これは、非決定論的アルゴリズムを使用して、多項式時間でそれらを解くことができることを意味します。

NPまたはNP困難な問題の詳細な分析は、このチュートリアルの範囲を超えています。 ただし、このような問題のグローバルに最適なソリューションを見つけるには多くのリソースが必要になることを理解するだけで十分です。 したがって、それは実質的に実行不可能になるか、少なくとも非効率的になります。 旅行のセールスマンやグラフ彩色のような多くの一般的な問題は、このカテゴリに分類されます。

これは、メタヒューリスティックが私たちを助けることができる場所です。 メタヒューリスティックは、最適化問題に対して十分に優れたソリューションを提供できる高レベルの手順またはヒューリスティックです。 通常、これらは、完全に列挙するには大きすぎるソリューションのサブセットをサンプリングすることによって動作します。 最も重要なことは、それらは不完全または不完全な情報でも機能する可能性があることです。

数値最適化アルゴリズムとは異なり、メタヒューリスティックは、グローバルに最適なソリューションが見つかることを保証できません。 ただし、はるかに少ない計算労力で、合理的なソリューションをより迅速に実現できます。 多くのメタヒューリスティックは確率的最適化も採用しており、見つけた解は確率変数に依存します。

3. メタヒューリスティックの定式化

メタヒューリスティックの目標は、探索空間を探索して、ほぼ最適な解を効率的に見つけることです。 これらは、検索プロセスを推進するための戦略に基づいています。 戦略は、観察中の任意の自然または人工システムからインスピレーションを得ることができます。 これは、アリの採餌行動へのアニーリングの冶金学的プロセスと同じくらい多様なソースから来る可能性があります。

検索戦略に関するメタヒューリスティックを定義するには、科学的および工学的な目標を追求する必要があります。 科学的な目標は、アリの群れのようなインスピレーションの背後にあるメカニズムをモデル化することです。 エンジニアリングの目標は、実際の問題を解決できるシステムを設計することです。 一般的なフレームワークを定義することは実用的ではありませんが、いくつかの定義特性について説明することができます。

メタヒューリスティックアプローチの重要な側面の1つは、探索と活用の適切なバランスをとることです。 探索の目的は、実行可能領域のできるだけ多くを探索して、次善の解決策を回避することです。 搾取の目的は、有望な地域の周辺を探索して最適な解決策を見つけることです。

ほとんどすべてのそのようなメタヒューリスティックでは、候補解を評価するために適応度関数を使用する傾向があります。 これは、搾取に焦点を当てるためにこれまでのところ最良の解決策をサンプリングすることです。 さらに、検索戦略の特定の側面を使用して、ランダム性をもたらし、探索を強調します。 これはすべての検索戦略に固有であるため、一般的な定式化を使用して表すことは非常に困難です。

これらのメタヒューリスティックを使用して、勾配に依存せずに多次元実数値関数を解決できます。 これは、これらのアルゴリズムを使用して、非連続的で、ノイズであり、時間の経過とともに変化する最適化問題を解くことができることを意味するため、重要なポイントです。 これは、線形回帰などの最急降下法を使用するいくつかのアルゴリズムとは対照的です。

4. 自然に触発されたメタヒューリスティックの種類

何年にもわたって、多くの研究が新しいメタヒューリスティック手法の開発に費やされてきました。 検索プロセスを推進する戦略は非常に多様である可能性があり、その結果、メタヒューリスティックアルゴリズムの範囲が広くなることがわかりました。 したがって、それらを意味のある形で分類することは困難です。 メタヒューリスティックを分類するそのような試みの1つがここに文書化されています

このチュートリアルの焦点は、自然に触発されたメタヒューリスティックです。 これらはメタヒューリスティックであり、その検索戦略は自然のシステムに触発されています。 上記は、ローカルとローカルに基づいてさまざまなメタヒューリスティックを分類するオイラー図です。 グローバル検索とシングルvs。 人口ベースの検索プロパティ。

進化的計算は、生物学的進化に触発された大域的最適化アルゴリズムのファミリーを備えた人工知能のサブフィールドを形成します。 自然に触発されたメタヒューリスティックは、固有のプロパティを複数の方法で使用して分類できます。 ただし、特に、進化的計算(EC)として知られる自然に触発されたメタヒューリスティックのクラスに焦点を当てます。

進化的計算には、アルゴリズムの複雑な分類があります。 ただし、進化的コンピューティングを進化的アルゴリズム(EA)と群知能アルゴリズム(SA)に分類するボードに焦点を当てます。 どちらも、候補ソリューションの母集団ベースのプレゼンテーションと、確率的探索を使用した反復手順を使用します。

4.1. 進化的アルゴリズム

進化的アルゴリズム(EA)は、ダーウィンの進化論に触発されたアルゴリズムのクラスです。 ダーウィンの進化論は、種のメンバー間で変動がランダムに発生すると仮定しています。 それはまた、その子孫が個人の特性を継承する可能性があり、存在のための闘争は、好ましい特性を持つものだけが生き残ることを可能にすることを示唆しています

進化的アルゴリズムは、この理論からインスピレーションを得て、探索空間でほぼ最適な解を特定します。 このようなアルゴリズムの各反復は世代と呼ばれ、親の選択、組換え(クロスオーバー)、突然変異、および生存者の選択で構成されます。 クロスオーバーと突然変異が探索の原因ですが、親と生存者の選択は搾取を引き出します。

4.2. スウォームアルゴリズム

群知能アルゴリズム(SA)は、社会的な動物や昆虫の集団行動に触発されています。 群れは、ミツバチのような複数のエージェントで構成されています。 単一のエージェントの動作は非常に単純で、ローカルで、確率的です。 エージェントの動作を制御するための集中化された構造がなくても、エージェント間の相互作用は、群知能(SI)と呼ばれるグローバルなインテリジェントな動作を生成します。

これらのアルゴリズムは、アリやミツバチなどの自然のエージェントの集団行動からインスピレーションを得ています。 このようなアルゴリズムのキーポイントは、群れ内で共有される情報であり、各エージェントの動きに直接影響を与える可能性があります。 群れの中のエージェント間の情報共有を制御することにより、探索空間の探索と活用のバランスをとることができます。

5. 人気のある進化的アルゴリズム

数十年前の進化的計算(EC)の開始以来、進化的アルゴリズムに多くの焦点が当てられてきました。 この分野の集中的な研究により、遺伝的アルゴリズム(GA)遺伝的プログラミング(GP)進化的プログラミング(EP)などの成熟したアルゴリズムが生まれました。差分進化(DE)。 このセクションでは、いくつかの一般的な進化的アルゴリズム(EA)の詳細について説明します。

5.1. 遺伝的アルゴリズム

遺伝的アルゴリズムは、おそらく私たちが今日知っている最も古く、最も人気のある自然に触発されたメタヒューリスティックの1つです。 自然淘汰プロセスの仕組みに基づいた検索最適化アルゴリズムとして、1975年にJohnHollandによって導入されました。 本質的には、「適者生存」の概念を模倣しようとします。この概念では、強者は適応して生き残る傾向があり、弱者は滅びる傾向があります。

問題領域の個々のソリューションは、染色体として遺伝的に表されます。 遺伝子と呼ばれる一連のパラメーターによってソリューションを特徴付けます。 次に、すべての遺伝子を文字列に結合して染色体を形成します。

最初に、ランダムに、またはヒューリスティックを使用して初期母集団を選択します。 次に、適応度関数を使用して、母集団のメンバーを評価し、それらのパフォーマンスにランク付けします。 これにより、下位の染色体が排除されます。 残りの個体群は、生殖の過程に参加し続けます:

次の2つの演算子、クロスオーバーと突然変異は、遺伝的アルゴリズムにとって重要です。 クロスオーバーは、集団から2つの染色体をランダムに選択し、それらの遺伝子を交換することによってそれらを結合します。 突然変異は、染色体を取り、その遺伝子をランダムに突然変異させることから成ります。 これらの演算子により、アルゴリズムは検索空間の探索を強調できます。

このサイクルが繰り返され、新しい母集団の生成は終了基準が満たされるまで続きます。 これは、最大世代数に達するか、最適なソリューションを見つけることによって行われます。 他の戦略を使用して、下位の染色体が生殖に参加できるようにすることもできます。 さらに、エリート主義を採用して、クロスオーバーや突然変異の際に最良の解決策が破壊されるのを防ぐことができます。

5.2. 差分進化

差分進化は、進化的アルゴリズムで非常に人気のあるもう1つのアルゴリズムです。 技術的には遺伝的アルゴリズムと非常によく似ており、1997年にRainerStornとKennethPriceによって導入されました。 主な違いは、差分進化がより良い解決策を探す際の主要な演算子として突然変異をどのように使用するかにあります

遺伝的アルゴリズムと同様に、最初の母集団を選択してから、個々のソリューションの適合性を評価することから始めます。 このアルゴリズムは、検索メカニズムおよび選択操作として突然変異操作を利用して、検索を潜在的な領域に向けます。

各反復で新しい母集団を生成するための3つのパラメーターベクトルがあります。 これらのパラメータベクトルは、現在の母集団からランダムに選択されます。 突然変異ステップ中に、ベースベクトルと呼ばれる最初のパラメーターベクトルと他のパラメーターベクトルから作成された差分ベクトルを利用して、突然変異体またはドナーベクトルを生成します。

次に、ターゲットベクターとミュータントベクターの間でクロスオーバーを実行して、トライアルベクターを作成します。 ここで、ターゲットベクトルには検索空間に解が含まれています。 最後に、問題領域の適応度関数に基づいて、ターゲットベクトル(親)と試行ベクトル(子孫)のどちらかを選択します。

遺伝的アルゴリズムとは異なり、母集団内のすべてのソリューションは、親として選択される確率が同じです。 子孫は、突然変異と交叉操作の後にのみ評価されます。 さらに、差分進化の子孫は、親よりもパフォーマンスが良くない場合、すぐに破棄されます。 その結果、これまでで最高のソリューションを個別に保存できます。

6. 人気のある群知能アルゴリズム

群知能アルゴリズム(SA)は、進化的計算(EC)で比較的新しく、非常に活発な研究分野です。 SalpSwarmGreyWolfなどの新しいエージェントの集団行動に触発された新しいメタヒューリスティックについて文献で読むことができます。 ただし、蟻コロニー最適化(ACO)粒子群最適化(PSO)など、この分野で人気のあるいくつかのアルゴリズムに限定します。

6.1. アリコロニー最適化

アリコロニー最適化は、群知能のカテゴリーで最も早く、最も広く研究され、採用されたメタヒューリスティックの1つです。 マルコ・ドリゴは、1992年に博士論文でそれを提案しました。 アリの採餌行動はそれを刺激します。 より具体的には、アリがフェロモンを使用してコロニーと食料源の間のより短い経路を見つける方法を模倣しようとします

アリは、フェロモンと呼ばれる化学物質を移動経路上に落とします。 他のアリがフェロモンの痕跡を見つけると、彼らはそれに従う傾向があります。 ただし、時間の経過とともにフェロモンは蒸発し、強度が低下します。 これで、長いパスよりも短いパスの方が頻繁に移動します。 したがって、短いパスのフェロモン強度は長いパスのよりも高くなります。

最適化問題を重み付きグラフで最短経路を見つける問題に変換する必要があります。 アリコロニーアルゴリズムの架空のエージェントとしてアリを使用して、検索スペースを探索および活用します。 アルゴリズムの反復では、各人工アリは、グラフのエッジをトラバースする順序を見つけることによって、確率的に解を構築しようとします。

次に、さまざまなアリによって構築されたパスを比較し、それに応じて各エッジのフェロモンレベルを更新します。 これは、アリがソリューションのエッジを選択する方法で重要な役割を果たします。 彼らは、現在の位置からの各エッジの長さと対応するフェロモンレベルを考慮して決定を下します。

フェロモンの更新は、堆積と蒸発によって行われます。 評価値によると、人工アリはその軌跡でフェロモンを増加させ、フェロモンは時間の経過とともに減少します。 堆積と蒸発の違いは、人工アリによる探索空間の探索と最適な解決策の活用との間のバランスを保ちます。

6.2. 粒子群最適化

群知能アルゴリズムのカテゴリで非常に人気のあるもう1つのメタヒューリスティックは、粒子群最適化です。 そうだった Jによって紹介されました。 ケネディとR。 1995年のEberhart 、ほぼアリコロニー最適化の導入後。 は、鳥の群れや魚の群れなど、自然のエージェントの単純な群れ行動からインスピレーションを得ています。

アルゴリズムは、粒子と呼ばれる候補解の母集団を選択することから始まります。 次に、粒子の位置と速度に基づく単純なルールに従って、これらの粒子を探索空間内で移動させる必要があります。 パーティクルの動きは、パーティクル自体の最もよく知られている位置( pbest )や群れ全体の最もよく知られている位置( gbest )などのパラメータの影響を受けます。

ここで、グローバルベストソリューションは、群れの最適な場所への収束を促進する要素です。 同時に、各粒子の個人的な最良の解決策は、各粒子に固有の動作を生成することにより、群れの多様性の維持に貢献します。 これらのパラメータは、慣性を考慮して、各パーティクルの速度を更新する際にも重要です。

粒子群最適化がどのように機能するかの背後にある有用な直感は、いくつかの単純な動作の観点から理解することです。 たとえば、分離、整列、凝集などの動作でこれを説明できます

ここで、分離とは、混雑した地元の群れを避ける行動です。 アラインメントとは、地元の群れの仲間の平均的な方向に向かって移動する行動です。 最後に、結束は、地元の群れの仲間の平均的な位置に向かって移動する行動です。 これにより、アルゴリズムは、探索空間の探索と最適解の活用の間のバランスを維持できます。

7. その他の興味深いアルゴリズム

先に見たように、メタヒューリスティックスの分野は少なくとも50年前のものですが、依然として活発な研究分野です。 これは主に、メタヒューリスティックがすべての最適化問題を解決すると主張できないためです。 より興味深い現実世界の最適化問題に遭遇するにつれて、より良いメタヒューリスティックの探求がこの分野の研究を推進します。

これまで、自然の生物剤に触発されたメタヒューリスティックに焦点を当ててきました。 しかし、自然に触発されたメタヒューリスティックの分野はそれよりもはるかに広い。 これには、化学や物理学など、他の研究分野の天然物質が含まれる場合があります。 たとえば、重力、河川の形成、電磁気学、ブラックホールなど、文献レビューの1つからいくつかを挙げます。

この分野では多くの質の高い研究が行われていますが、ほとんどの文献は主に実験的なものです。 文献は新規性と実用的な有効性を主張していますが、実際の工学的問題に対して実用的であるとは証明されていない可能性があります。 それらの価値を理解するために厳密な演習を行うのは私たちのためです。 それでも、メタヒューリスティックスへの投資と改善を継続する必要があります。

このチュートリアルで提示されたものを含め、過去にメタヒューリスティックを分類するためのいくつかの試みがありました。 ただし、それらはある程度の価値があるだけであり、私たちがそれらにとらわれるべきではないことを理解することが不可欠です。 メタヒューリスティックを刺激する研究領域間には多くのクロスオーバーがあるため、非常に複雑になるはずです。

8. 実用的なアプリケーション

先に見たように、メタヒューリスティックへの関心が急上昇した理由は、他の方法では解決が難しい現実世界の最適化問題を解決するためです。 エンジニアリングやその他のドメインで最適化問題に遭遇することがよくあります。これは、広大で困難な検索スペースを示します。 このような場合に役立つ解決策を見つけるには、従来のアプローチを使用するのは非効率的であることがわかります。

初期の頃から、メタヒューリスティックは、巡回セールスマン問題のようないくつかのよく知られた組み合わせ問題を解決するためにうまく適用されてきました。 また、教育、ロボット工学、医療診断、感情分析、財務、不正検出など、さまざまなドメインでのこれらのアルゴリズムのアプリケーションも確認されています。

メタヒューリスティックは、最適化問題についてほとんど仮定をとらないことに注意することが重要です。 したがって、それらは多種多様な問題に適用されます。 ただし、同時に、これらすべての問題に対して同じレベルのパフォーマンスが保証されるわけではありません。 したがって、特定の問題により適したにするために、アルゴリズムに特定の変更を加える必要があります

これにより、このチュートリアルで見た一般的な自然に触発されたメタヒューリスティックの多数のバリエーションが生まれました。 それらすべてに名前を付けることは、このチュートリアルの範囲をはるかに超えています。 さらに、特定の問題領域に適したものにするために、これらの各アルゴリズムのパラメーターを微調整するための多くの研究が行われています。

最後に、これらのアルゴリズムの背後にある多くの直感を開発しましたが、それらは主にブラックボックスのように機能することに注意することが重要です。 したがって、特定の形式のどのアルゴリズムが最適化問題に対してより適切に機能するかを予測することは困難です。 新しい問題を発見し続け、既存の問題のパフォーマンスを向上させる必要があるため、研究に投資し続ける必要があります。

9. 結論

要約すると、このチュートリアルでは、自然に触発されたメタヒューリスティックの基本と、それらが必要な理由について説明しました。 これらのアルゴリズムの範囲は非常に広いですが、進化的アルゴリズムと群知能アルゴリズムのカテゴリでよく知られているアルゴリズムのいくつかに焦点を当てました。 最後に、これらのメタヒューリスティックアルゴリズムの実用的なアプリケーションのいくつかについて説明しました。