生物地理学に基づく最適化

生物地理学に基づく最適化（BBO）は、与えられた品質尺度、すなわち適合度関数に関して、候補解を確率的かつ反復的に改善することで関数を最適化する進化アルゴリズム（EA）です。BBOは多くのバリエーションを含み、問題に関する仮定を一切行わないため、幅広い問題に適用できることから、メタヒューリスティクスに分類されます。

BBOは通常、多次元実数値関数の最適化に用いられますが、関数の勾配を用いないため、勾配降下法や準ニュートン法といった古典的な最適化手法のように、関数が微分可能である必要はありません。したがって、BBOは不連続関数にも適用可能です。

BBOは、候補解の集合を維持し、既存の候補解を単純な数式に基づいて組み合わせることで新しい候補解を生成することにより、問題を最適化します。このように、目的関数は候補解が与えられた場合の品質の尺度を提供するだけのブラックボックスとして扱われ、関数の勾配は必要ありません。

多くのEAと同様に、BBOは自然プロセスに触発されたものであり、特に、生物種の時間と空間における分布を研究する生物地理学に触発されたものである。 ^{[ 1 ]} BBOはもともと2008年にダン・サイモンによって導入された。^{[ 2 ]}

生物地理学の数理モデルは、種分化（新種の進化）、島間の種（動物、魚、鳥、昆虫）の移動、および種の絶滅を記述します。^{[ 3 ]}生命にとって好ましい島は、高い生息地適合性指数（HSI）を持つと言われています。^{[ 4 ]} HSIと相関する特徴には、降雨量、植生の多様性、地形の多様性、陸地面積、気温などがあります。決定要因となる特徴は、適合性指数変数（SIV）と呼ばれます。居住可能性の観点から、SIVは独立変数であり、HSIは従属変数です。

HSIが高い島は多くの種を支えることができ、HSIが低い島は少数の種しか支えることができません。HSIが高い島には、個体数が多く、生息する種の数も多いため、近隣の生息地へ移動する種が多くいます。HSIが高い島からの移住は、種が故郷を離れたいから起こるわけではないことに注意してください。結局のところ、故郷の島は魅力的な居住地なのです。移住は、個体数の多い多数の種にランダムな影響が蓄積されることによって起こります。動物は漂流物に乗ったり、泳いだり、飛んだり、風に乗って近隣の島へ移動します。ある種が島から移住しても、その種が元の島から完全に姿を消すわけではありません。ごく少数の個体だけが移住するため、移住する種は元の島に留まりながら、同時に近隣の島へ移動します。しかし、BBOでは、島からの移住はその島からの絶滅につながると想定されています。 BBOでは、種は関数の独立変数を表し、各島は関数最適化問題の候補解を表すため、この仮定は必要不可欠である。

HSI値の高い島々は、移住率が高いだけでなく、既に多くの種が生息しているため、移住率も低い。このような島々に移住してきた種は、島のHSI値が高いにもかかわらず、他の種との資源をめぐる競争が激しすぎるため、死滅する傾向がある。

HSIが低い島々は、人口が少ないため、移住率が高い。これもまた、種がそのような島々に移住したがっているからではない。結局のところ、これらの島々は住むには好ましくない場所なのだ。これらの島々に移住が起こる理由は、追加の種を受け入れる余地がたくさんあるからである。移住してきた種が新しい場所で生き残れるかどうか、またどれくらいの期間生き残れるかは別の問題である。しかし、種の多様性はHSIと相関関係にあるため、HSIの低い島に多くの種がやってくると、島のHSIは増加する傾向がある。^{[ 4 ]}

右の図は島嶼移住モデルを示している。^{[ 3 ]}移民率${\displaystyle \lambda }$そして移住率${\displaystyle \mu }$島に生息する種の数に依存する関数である。最大可能な移民率${\displaystyle I}$島に種がゼロの場合に発生します。種の数が増えるにつれて、島はより混雑し、移住を生き残れる種は少なくなり、移住率は低下します。生息地が支えることができる種の最大数は$\displaystyle S_{\max }}$島に種が存在しない場合、移出率はゼロになります。島に種の数が増えるにつれて、島は混雑し、より多くの種の代表が島を離れることができ、移出率が上昇します。島に可能な限り最大の数の種が存在する場合、$\displaystyle S_{\max }}$移住率は最大可能値に達する${\displaystyle E}$。

BBOでは、$\displaystyle \lambda _{k}}$は、${\displaystyle k}$第 番目の候補解が置き換えられます。つまり、$\displaystyle \lambda _{k}}$移民の確率は${\displaystyle x_{k}}$独立変数を置き換える場合、移住候補解は移住確率に比例する確率で選択される。${\displaystyle \mu _{k}}$これは通常、ルーレットホイールの選択を使用して行われます。

${\displaystyle {\text{Prob}}(x_{j}){\text{ is selected for emigration}}={\frac {\mu _{j}}{\sum _{i=1}^{N}\mu _{i}}}}$

のために${\displaystyle j=1,\cdots ,N}$、 どこ${\displaystyle N}$これは、母集団における候補解の数です。

他のほとんどのEAと同様に、BBOには突然変異が含まれています。個体群サイズが${\displaystyle N}$最適化のために${\displaystyle n}$次元関数は次のように記述できます。

集団を初期化する${\displaystyle N}$候補ソリューション${\displaystyle \{x_{k}\}}$終了条件を 満たさない間、各${\displaystyle x_{k}}$移住確率を設定する${\displaystyle \mu _{k}\propto }$フィットネス${\displaystyle x_{k}}$する​ ​${\displaystyle \mu _{k}\in [0,1]}$各${\displaystyle x_{k}}$移民確率を設定する${\displaystyle \lambda _{k}=1-\mu _{k}}$する${\displaystyle \{z_{k}\}\leftarrow \{x_{k}\}}$各個人について${\displaystyle z_{k}(k=1,\cdots ,N)}$各独立変数インデックスについて${\displaystyle s\in [1,n]}$ 使用してください${\displaystyle \lambda _{k}}$移住するかどうかを確率的に決定する${\displaystyle z_{k}}$移民する 場合は、${\displaystyle \{\mu _{i}\}}$移住する個人を確率的に選択する${\displaystyle x_{j}}$${\displaystyle z_{k}(s)\leftarrow x_{j}(s)}$End if 次の独立変数インデックス:${\displaystyle s\leftarrow s+1}$ 確率的に突然変異する${\displaystyle z_{k}}$ 次の人物：${\displaystyle k\leftarrow k+1}$${\displaystyle \{x_{k}\}\leftarrow \{z_{k}\}}$ 次世代

• 人口規模${\displaystyle N}$は調整パラメータです。${\displaystyle N}$が小さすぎたり大きすぎたりすると、BBO の最適化パフォーマンスが低下します。BBO の典型的な実装では、 の値を使用します。${\displaystyle N}$20から200の間。
• 候補解の初期集団${\displaystyle \{x_{k}\}_{k=1}^{N}}$は通常ランダムに生成されます。ただし、最適化問題に対する妥当な推測や既知の優れた解に基づいて、問題に応じて生成される場合もあります。
• 終了基準は、他の進化アルゴリズムと同様に、問題によって異なります。ほとんどのアプリケーションでは、終了基準は世代数の制限または関数評価回数の制限（つまり、目的関数が評価される回数）です。
• ${\displaystyle \{z_{k}\}}$これは一時的な人口であり、すべての移住変数は世代の開始時に存在する人口から発生する可能性があります。${\displaystyle \{x_{k}\}}$。

基本的なBBOアルゴリズムには多くのバリエーションが提案されており、その中には以下のようなものがある。

• エリート主義は、ほとんどの進化アルゴリズム（EA）で実装されており、最良の候補解が世代間で失われないようにしています。これはさまざまな方法で実装できますが、一般的な方法の1つは、各世代の開始時に最良の候補解をセットに保存することです。${\displaystyle \mathbb {E} }$;次に、最悪の候補ソリューションを置き換えます${\displaystyle \mathbb {E} }$世代の終わり、移動と突然変異が完了した後。${\displaystyle \mathbb {E} }$は調整パラメータですが、${\displaystyle \mathbb {E} }$通常は上位 2 人の個体が含まれます。エリート主義は、もともとDeJong によって遺伝的アルゴリズムに提案されました。 ^{[ 5 ]}エリート主義は BBO のパフォーマンスに大きな違いをもたらす可能性があり、強く推奨されます。
• 重複置換はBBOでよく実装されます。これは、各世代の最後に集団内の重複した個体を置き換える手順です。重複のスキャンは、${\displaystyle O(N^{2})}$そのため、この操作は毎世代ではなく、数世代に一度だけ行われることが多い。
• BBOではブレンドを実装できます。ブレンドでは、置き換える代わりに${\displaystyle z_{k}(s)}$移民候補ソリューションでは${\displaystyle x_{j}(s)}$移住候補ソリューションから、${\displaystyle z_{k}(s)}$は、その元の値と の線形結合に等しくなるように設定されます。${\displaystyle x_{j}(s)}$:

${\displaystyle z_{k}(s)\leftarrow \alpha z_{k}(s)+(1-\alpha )x_{j}(s)}$

どこ${\displaystyle \alpha \in [0,1]}$、 そして${\displaystyle \alpha =0}$これは、上記のアルゴリズムに示されている標準的なマイグレーションに対応します。ブレンドBBOは、遺伝的アルゴリズムのブレンドクロスオーバーに基づいており、^{[ 6 ]}標準的なBBOよりも優れた性能を発揮することが示されています。^{[ 7 ]}

• 上記のBBOアルゴリズムは、移住候補解が移住候補解より先に選択され、移住候補解内の各独立変数の移住が他のすべての独立変数とは独立して実行されるため、部分移住ベースBBOと呼ばれます。移住候補解と移住候補解を選択するための他のアプローチも提案されています。^{[ 8 ] [ 9 ]}
• 上記の図のマイグレーション曲線は線形ですが、非線形マイグレーション曲線の方が優れたパフォーマンスを示す場合が多いです。^{[ 10 ]}

• BBOは、粒子群最適化^{[ 9 ] [ 11 ]} 、差分進化^{[ 12 ]} 、進化戦略^{[ 13} ] 、対立ベース計算^{[ 14 ]}、事例ベース推論[15 ^]、人工蜂コロニーアルゴリズム、細菌摂食最適化[16]、^{ハーモニーサーチ[} 17 ^{]、シンプレックス}アルゴリズム^{[ 18 ]}など、他のいくつか^のEAとハイブリッド化さ^{れています}。
• BBOは局所探索と組み合わせることで、BBO単独よりもはるかに優れた性能を発揮するミームアルゴリズムを作成できます。 ^{[ 19 ]}

^BBOは、ノイズのある関数（つまり、適合度評価がノイズによって損なわれる関数）^{[ 21 ]} 、制約付き関数[ ²² ]、組み合わせ関数^{[ 23 ]}、および多目的関数[24][25]に拡張されています。^{さらに、マイクロバイオジオグラフィーに} 着想を得た多目的最適化アルゴリズム（μBiMO）が実装されました。これは、少数の島に基づいているため（そのためμBiMOという名前が付けられています）、つまり目的関数の呼び出しが少なくて済むため、工業デザインの分野での多目的最適化の解決に適しています。^{[ 26 ]}

^{BBOはマルコフモデル[ 27 ]および動的システムモデル[ 28 ]}を用いて数学的に解析されている。

研究者たちはBBOを様々な学術的および産業的応用分野に適用してきた。その結果、BBOは最先端のグローバル最適化手法よりも優れた性能を発揮することがわかった。

例えば、Wangらは、BBOがFSCABCと同等の性能を発揮するが、より単純なコードで済むことを証明した。^{[ 29 ]}

Yangらは、BBOがGA、PSO、ABCよりも優れていることを示した。^{[ 30 ]}

• BBOホームページ