自然なアルゴリズム。 蜂の群れ行動アルゴリズム
遺伝的アルゴリズム、その長所と短所は、Habrahabrで繰り返し議論されました。 しかし、遺伝的アルゴリズム（または、そのさまざまな亜種の銀河全体）は一意ではありません。 これは、いわゆる自然アルゴリズムと呼ばれます。 また、「シミュレーテッドアニーリング」アルゴリズム、「ミツバチの群れ行動」アルゴリズム、「アリのコロニー行動」アルゴリズム、および他のほとんど未知のアルゴリズムも含まれます。
2番目の、あまり一般的ではないがそれほど面白くない合成および最適化アルゴリズム（ミツバチの群れの行動のためのアルゴリズム）について説明し、その原理を説明したいと思います。
ミツバチの群れの行動に対するアルゴリズムの動作原理、またはミツバチの群れ（MCI）の方法を検討するために、実際のミツバチの群れとの類推に頼ります。 畑にミツバチの群れを想像してください。 彼らの目標は、フィールド上で最も色の濃いエリアを見つけることです。 先験的にフィールドのアイデアがなければ、ミツバチはランダムな速度ベクトルでランダムな位置から花を探し始めます。 各ミツバチは、最も多くの花を見つけた位置を覚えていて、他のミツバチが最も高い密度で花を見つけた場所をどういうわけか知っています。 ミツバチが最も花を見つけた場所に戻るか、他の人が最も花の多い場所として決定した場所を探索するかを選択すると、ミツバチは彼女の決定に大きな影響を与えるものに応じて、2つのポイントの間の方向に急ぎます-個人的な記憶または社会的反射。 道に沿って、蜂は以前に発見されたよりも花の濃度が高い場所を見つけることができます。 将来的には、群れ全体で見つかった花が最も集中している場所と同様に、花が最も集中している新しい場所として指定することができます。 偶然、蜂は他の群れ蜂よりも多くの花のある場所を飛び越えることができます。 全体の群れは、それぞれのミツバチの観察に加えて、この場所を満たすために努力します。 したがって、ミツバチは野原を探索します。最高の濃度の飛行場は、その方向に減速します。 彼らは、以前に見つかった色の濃度が最も高い場所と比較して飛行した場所を継続的にチェックし、色の絶対的な濃度が最も高いことを期待しています。 最終的に、ハチは、花が最も集中している畑の代わりに動きを終わらせます。 まもなく、群れ全体がこの位置の近くに集中します。 花の濃度が高い場所を検出できないため、ミツバチは花の密度が最も高いエリアで絶えず群がっています。 蜂のこの行動は、この最適化手法の基礎でした。
粒子またはエージェント-群れの中の各蜂は、粒子またはエージェントと見なされます。 すべてのスウォームパーティクルは、1つの制御原則に従って個別に動作します。つまり、現在の位置の値を常にチェックしながら、最高の個人的および最高の全体的位置の方向に加速します。
位置-フィールド上の蜂の位置と同様に、xy平面上の座標で表されます。 ただし、一般的な場合、このアイデアはタスクに応じて任意のN次元空間に拡張できます。 このN次元空間は、最適化された問題の解領域であり、各座標セットが解を表します。
適合性-蜂の群れの例との類似性により、適合性関数は色の密度になります：密度が高いほど、位置が良くなります。 フィットネス関数は、物理的な問題と最適化アルゴリズム間のコミュニケーションの手段として機能します。
個人的な最高の位置-ミツバチの群れとの類推により、それぞれのミツバチは自分が最も多くの花を見つけた位置を覚えています。 ミツバチによって検出された最高のフィットネス値を持つこの位置は、Personal Best Position（PNP）として知られています。 それぞれの蜂には、飛行した経路によって決定される独自のPNPがあります。 移動経路に沿った各ポイントで、ハチは現在の位置の適合性の値をPNPの値と比較します。 現在の位置のフィットネス値が上記の場合、EOR値は現在の位置の値に置き換えられます。
グローバルな最高の位置-各ミツバチは、群れ全体によって定義された、花が最も集中している領域も何らかの方法で認識します。 最も適したこのポジションは、グローバルベストポジション（GNP）として知られています。 群れ全体にとって、これはすべてのハチが努力している1つのGNPです。 旅行中の各ポイントで、各ミツバチは現在の位置の適性をGNPと比較します。 蜂がより適切な位置を見つけた場合、GNPはその蜂の現在の位置に置き換えられます。
MCIの実装の最初のステップは、最適化する必要があるパラメーターを選択し、最適な値を見つけるための許容可能な間隔を決定することです。 次に、ミツバチは許容領域にランダムに配置され、ベクトルとその移動速度も設定されます。 次に、各粒子は、まるで群れの中の蜂のように、溶液の空間を移動する必要があります。 アルゴリズムは各パーティクルに個別に作用し、少量ずつ移動し、群れ全体を周期的に移動します。 各パーティクルに対して次の手順が実行されます。
粒子の適合性の評価、PNPおよびGNPとの比較。 決定空間内の粒子の座標を使用するフィットネス関数は、現在の位置のフィットネス値を返します。 この値がこの粒子に対応するPNPまたはGNPの値より大きい場合、対応する位置は現在の位置に置き換えられます。
粒子速度の補正。 粒子速度の操作は、すべての最適化の重要な要素です。 速度の決定に使用される方程式を正確に理解することは、最適化プロセス全体を理解するための鍵です。 粒子速度は、PNP位置とGNP位置の相対位置に応じて変化します。 彼女は、次の式に従って、最も適切なこれらのポジションを目指します。
ここで：
前のステップのn次元の粒子速度です。
n次元の粒子の座標です。
-PNP、
-GNP。
Nのそれぞれについて計算が行われます。この方程式から、単純にスケーリングすることにより、古い速度から新しい速度が得られることがわかります。
、この特定の方向にGNPとPNPの方向を追加します。 
そして 
-これらは、PNPとGNPに対する相対的な相互「誘引」を決定するスケール係数です。 それらは時々認知的および社会的要因と見なされます。 粒子がPNPに及ぼす影響を決定する係数です。 -群れの他のメンバーがパーティクルに与える影響を決定する係数。 増やす 各粒子をそのPNPの方向に移動することにより、解の空間を研究します。 増す 推定されたグローバルな最大値の調査が含まれます。 乱数関数rand（）は、-1〜1の数値を返します。一般的な場合、rand（）関数の2つの出現は、関数の2つの異なる呼び出しです。 ほとんどの実装では、2つの独立したランダム変数を使用して、GNPとEORの相対的な引力を確率的に変更します。 最適化へのランダム要素のこの導入は、スウォームの実際の動作のわずかに予測不可能なコンポーネントをシミュレートすることを目的としています。 「慣性重量」と呼ばれ、この数値（0から1の間で選択）は、粒子が元のコースに忠実であり、GNPおよびEORの影響を受けない程度を反映しています。
最初に境界を設定しましたが、式とメソッドのどこにも言及していませんでした。 それでは、それらをどのように考慮しますか？ この質問にはいくつかの答えがあります。
たとえば、壁を吸収させることができます。 粒子がいずれかの次元で解空間の境界に到達すると、この次元の速度はゼロになり、最終的に粒子は指定された解空間に戻ります。 これは、境界-「壁」が領域を解決しようとする粒子のエネルギーを吸収することを意味します。 または、粒子が「壁」まで飛ぶときの粒子の速度を反映します。 しかし、最も効果的なソリューションは「見えない壁」でした。 パーティクルは静かに限界を超えて飛ぶことができますが、許可されたエリアの外にあるため、パーティクルが取得する値は、戻るまで考慮されません。
最後に、ミツバチの群れの方法は、いくつかの並列プロセスに効果的に分割できるため、速度が大幅に向上することに注意してください。
さまざまな方法で演算子を実装できる遺伝的アルゴリズムと比較すると、演算子が1つだけあります-速度計算で、使いやすくなっています。
ミツバチの群れの方法では、グローバルミニマムポイントの達成を簡単に判断できますが、遺伝的アルゴリズムではこれは非常に複雑です。
これらの方法の概念は、2つのまったく異なる自然プロセスに基づいています。MCIは群れの社会的行動に基づいており、遺伝的アルゴリズムは進化と自然naturalのプロセスを模倣します。 このため、これら2つの方法を組み合わせることが可能です。
2番目の、あまり一般的ではないがそれほど面白くない合成および最適化アルゴリズム（ミツバチの群れの行動のためのアルゴリズム）について説明し、その原理を説明したいと思います。
ミツバチの群れの行動に対するアルゴリズムの動作原理、またはミツバチの群れ（MCI）の方法を検討するために、実際のミツバチの群れとの類推に頼ります。 畑にミツバチの群れを想像してください。 彼らの目標は、フィールド上で最も色の濃いエリアを見つけることです。 先験的にフィールドのアイデアがなければ、ミツバチはランダムな速度ベクトルでランダムな位置から花を探し始めます。 各ミツバチは、最も多くの花を見つけた位置を覚えていて、他のミツバチが最も高い密度で花を見つけた場所をどういうわけか知っています。 ミツバチが最も花を見つけた場所に戻るか、他の人が最も花の多い場所として決定した場所を探索するかを選択すると、ミツバチは彼女の決定に大きな影響を与えるものに応じて、2つのポイントの間の方向に急ぎます-個人的な記憶または社会的反射。 道に沿って、蜂は以前に発見されたよりも花の濃度が高い場所を見つけることができます。 将来的には、群れ全体で見つかった花が最も集中している場所と同様に、花が最も集中している新しい場所として指定することができます。 偶然、蜂は他の群れ蜂よりも多くの花のある場所を飛び越えることができます。 全体の群れは、それぞれのミツバチの観察に加えて、この場所を満たすために努力します。 したがって、ミツバチは野原を探索します。最高の濃度の飛行場は、その方向に減速します。 彼らは、以前に見つかった色の濃度が最も高い場所と比較して飛行した場所を継続的にチェックし、色の絶対的な濃度が最も高いことを期待しています。 最終的に、ハチは、花が最も集中している畑の代わりに動きを終わらせます。 まもなく、群れ全体がこの位置の近くに集中します。 花の濃度が高い場所を検出できないため、ミツバチは花の密度が最も高いエリアで絶えず群がっています。 蜂のこの行動は、この最適化手法の基礎でした。
メソッド言語
粒子またはエージェント-群れの中の各蜂は、粒子またはエージェントと見なされます。 すべてのスウォームパーティクルは、1つの制御原則に従って個別に動作します。つまり、現在の位置の値を常にチェックしながら、最高の個人的および最高の全体的位置の方向に加速します。
位置-フィールド上の蜂の位置と同様に、xy平面上の座標で表されます。 ただし、一般的な場合、このアイデアはタスクに応じて任意のN次元空間に拡張できます。 このN次元空間は、最適化された問題の解領域であり、各座標セットが解を表します。
適合性-蜂の群れの例との類似性により、適合性関数は色の密度になります：密度が高いほど、位置が良くなります。 フィットネス関数は、物理的な問題と最適化アルゴリズム間のコミュニケーションの手段として機能します。
個人的な最高の位置-ミツバチの群れとの類推により、それぞれのミツバチは自分が最も多くの花を見つけた位置を覚えています。 ミツバチによって検出された最高のフィットネス値を持つこの位置は、Personal Best Position（PNP）として知られています。 それぞれの蜂には、飛行した経路によって決定される独自のPNPがあります。 移動経路に沿った各ポイントで、ハチは現在の位置の適合性の値をPNPの値と比較します。 現在の位置のフィットネス値が上記の場合、EOR値は現在の位置の値に置き換えられます。
グローバルな最高の位置-各ミツバチは、群れ全体によって定義された、花が最も集中している領域も何らかの方法で認識します。 最も適したこのポジションは、グローバルベストポジション（GNP）として知られています。 群れ全体にとって、これはすべてのハチが努力している1つのGNPです。 旅行中の各ポイントで、各ミツバチは現在の位置の適性をGNPと比較します。 蜂がより適切な位置を見つけた場合、GNPはその蜂の現在の位置に置き換えられます。
アルゴリズム
MCIの実装の最初のステップは、最適化する必要があるパラメーターを選択し、最適な値を見つけるための許容可能な間隔を決定することです。 次に、ミツバチは許容領域にランダムに配置され、ベクトルとその移動速度も設定されます。 次に、各粒子は、まるで群れの中の蜂のように、溶液の空間を移動する必要があります。 アルゴリズムは各パーティクルに個別に作用し、少量ずつ移動し、群れ全体を周期的に移動します。 各パーティクルに対して次の手順が実行されます。
粒子の適合性の評価、PNPおよびGNPとの比較。 決定空間内の粒子の座標を使用するフィットネス関数は、現在の位置のフィットネス値を返します。 この値がこの粒子に対応するPNPまたはGNPの値より大きい場合、対応する位置は現在の位置に置き換えられます。
粒子速度の補正。 粒子速度の操作は、すべての最適化の重要な要素です。 速度の決定に使用される方程式を正確に理解することは、最適化プロセス全体を理解するための鍵です。 粒子速度は、PNP位置とGNP位置の相対位置に応じて変化します。 彼女は、次の式に従って、最も適切なこれらのポジションを目指します。
ここで：
前のステップのn次元の粒子速度です。
n次元の粒子の座標です。
-PNP、
-GNP。
Nのそれぞれについて計算が行われます。この方程式から、単純にスケーリングすることにより、古い速度から新しい速度が得られることがわかります。
、この特定の方向にGNPとPNPの方向を追加します。 そして -これらは、PNPとGNPに対する相対的な相互「誘引」を決定するスケール係数です。 それらは時々認知的および社会的要因と見なされます。 粒子がPNPに及ぼす影響を決定する係数です。 -群れの他のメンバーがパーティクルに与える影響を決定する係数。 増やす 各粒子をそのPNPの方向に移動することにより、解の空間を研究します。 増す 推定されたグローバルな最大値の調査が含まれます。 乱数関数rand（）は、-1〜1の数値を返します。一般的な場合、rand（）関数の2つの出現は、関数の2つの異なる呼び出しです。 ほとんどの実装では、2つの独立したランダム変数を使用して、GNPとEORの相対的な引力を確率的に変更します。 最適化へのランダム要素のこの導入は、スウォームの実際の動作のわずかに予測不可能なコンポーネントをシミュレートすることを目的としています。 「慣性重量」と呼ばれ、この数値（0から1の間で選択）は、粒子が元のコースに忠実であり、GNPおよびEORの影響を受けない程度を反映しています。
境界条件
最初に境界を設定しましたが、式とメソッドのどこにも言及していませんでした。 それでは、それらをどのように考慮しますか？ この質問にはいくつかの答えがあります。
たとえば、壁を吸収させることができます。 粒子がいずれかの次元で解空間の境界に到達すると、この次元の速度はゼロになり、最終的に粒子は指定された解空間に戻ります。 これは、境界-「壁」が領域を解決しようとする粒子のエネルギーを吸収することを意味します。 または、粒子が「壁」まで飛ぶときの粒子の速度を反映します。 しかし、最も効果的なソリューションは「見えない壁」でした。 パーティクルは静かに限界を超えて飛ぶことができますが、許可されたエリアの外にあるため、パーティクルが取得する値は、戻るまで考慮されません。
おわりに
最後に、ミツバチの群れの方法は、いくつかの並列プロセスに効果的に分割できるため、速度が大幅に向上することに注意してください。
さまざまな方法で演算子を実装できる遺伝的アルゴリズムと比較すると、演算子が1つだけあります-速度計算で、使いやすくなっています。
ミツバチの群れの方法では、グローバルミニマムポイントの達成を簡単に判断できますが、遺伝的アルゴリズムではこれは非常に複雑です。
これらの方法の概念は、2つのまったく異なる自然プロセスに基づいています。MCIは群れの社会的行動に基づいており、遺伝的アルゴリズムは進化と自然naturalのプロセスを模倣します。 このため、これら2つの方法を組み合わせることが可能です。
All Articles