生物地理学に基づく最適化(BBO)は、与えられた品質尺度、すなわち適応度関数に関して、候補ソリューションを確率的かつ反復的に改善することで関数を最適化する進化的アルゴリズム(EA)です。BBOは、多くのバリエーションを含み、問題についていかなる仮定も立てないため、幅広い問題に適用できるため、メタヒューリスティックスの一種に属します。
BBOは典型的には多次元実数値関数の最適化に用いられますが、関数の勾配は考慮しません。つまり、勾配降下法や準ニュートン法といった従来の最適化手法で要求されるような関数の微分可能性を必要としません。したがって、BBOは不連続関数にも適用できます。
BBOは、候補解の集合を維持し、既存の候補解を単純な式に従って組み合わせることで新たな候補解を作成することで、問題を最適化します。この方法では、目的関数はブラックボックスとして扱われ、候補解が与えられた場合の品質指標のみを提供し、関数の勾配は必要ありません。
多くのEAと同様に、BBOは自然のプロセスに触発されて考案されました。特に、BBOは生物地理学、つまり時間と空間を通じた生物種の分布を研究する学問に触発されました。[1] BBOは2008年にダン・サイモンによって最初に導入されました。[2]
基本原則
生物地理学の数理モデルは、種分化(新しい種の進化)、島々間の種(動物、魚類、鳥類、昆虫)の移動、そして種の絶滅を記述します。[3]生命にとって住みやすい島は、高い生息地適合指数(HSI)を持つと言われています。[4] HSIと相関する特性には、降雨量、植物の多様性、地形の多様性、陸地面積、気温などがあります。HSIを決定づける特性は、適合指数変数(SIV)と呼ばれます。居住可能性の観点から見ると、SIVは独立変数であり、HSIは従属変数です。
HSI の高い島は多くの種を支えることができ、HSI の低い島は少数の種しか支えることができません。HSI の高い島には、個体数が多く、生息する種の数が多いため、近くの生息地へ移住する種が多くいます。HSI の高い島からの移住は、種が故郷を離れたいから起こるのではないことに注意してください。結局のところ、故郷の島は住むのに魅力的な場所なのです。移住は、個体数の多い多数の種に対するランダム効果が蓄積されることによって起こります。移住は、動物が漂流物に乗ったり、泳いだり、飛んだり、風に乗って近隣の島へ移動するときに起こります。種が島から移住することは、その種が元の島から完全に姿を消すことを意味するのではなく、少数の個体のみが移住するため、移住する種は元の島に存在し続けながら、同時に近隣の島へ移住します。ただし、BBO では、島からの移住はその島の絶滅につながると想定されています。この仮定は、種が関数の独立変数を表し、各島が関数最適化問題に対する候補解を表すため、BBO では必要です。
HSIの高い島は、移出率が高いだけでなく、既に多くの種が生息しているため、移入率も低くなります。このような島に移住した種は、他の種との資源をめぐる競争が激しすぎるため、HSIが高いにもかかわらず絶滅する傾向があります。
HSIの低い島では、個体数が少ないため、移入率が高くなります。繰り返しますが、これは種がそのような島に移住したがっているからではありません。結局のところ、これらの島は住みにくい場所なのです。これらの島に移住が起こるのは、新たな種を受け入れる余地が十分にあるからです。移入した種が新しい生息地で生存できるかどうか、またどのくらいの期間生存できるかは別の問題です。しかし、種の多様性はHSIと相関関係にあるため、HSIの低い島に多くの種が到着すると、その島のHSIは上昇する傾向があります。[4]
右の図は、島の移住モデルを示しています。[3]移入率と移出率は、島に存在する種の数の関数です。移入率は、島に種が 0 種のときに最大になります。種の数が増加すると、島はより混雑し、移住を生き残ることができる種の数は減少し、移入率は減少します。生息地がサポートできる種の最大数は であり、その時点で移入率は 0 です。島に種がいない場合は、移出率は 0 です。島の種の数が増えると、島はより混雑し、より多くの種の代表が島を去ることができるため、移出率は増加します。島に含まれる可能性のある種の数が最大になると、移出率は最大値 に達します。

BBOにおいて、は - 番目の候補解における特定の独立変数が置換される確率、つまりの移入確率です。独立変数が置換される場合、移入する候補解は移入確率 に比例する確率で選択されます。これは通常、ルーレットホイール選択を用いて行われます。
の場合、 は母集団内の候補解の数です。
アルゴリズム
他の多くのEAと同様に、BBOには突然変異が含まれます。次元関数を最適化するための、母集団サイズが の基本的なBBOアルゴリズムは、以下のように記述できます。
候補ソリューションの集団を初期化します。ではない間(終了基準)
それぞれについて、 の移住確率の適合度
を で設定します。それぞれについて、の移住確率を設定します。各個体について を実行します。各独立変数インデックスについて を実行します。 を
使用して、 に移住するかどうかを確率的に決定します。移住する場合は を使用します。 を使用して、移住する個体を確率的に選択します。
次の場合、終了します。
次の独立変数インデックス:
確率的に突然変異します。
次の個体:
次世代
BBO アルゴリズムの説明
- 個体数はチューニングパラメータです。個体数が小さすぎたり大きすぎたりすると、BBOの最適化パフォーマンスが低下します。BBOの典型的な実装では、20から200の間の値が使用されます。
- 候補解の初期集団は通常、ランダムに生成されます。ただし、最適化問題に対する妥当な推測や既知の良好な解に基づいて、問題に依存した方法で生成される場合もあります。
- 他のEAと同様に、終了基準は問題によって異なります。ほとんどのアプリケーションでは、終了基準は世代数制限または関数評価制限(つまり、目的関数が評価される頻度)です。
- は一時的な集団であるため、すべての移出変数は、世代の初めに存在していた集団、つまり から発生する可能性があります。
アルゴリズムのバリエーション
基本的な BBO アルゴリズムには多くのバリエーションが提案されており、その中には次のものがあります。
- エリート主義は、ほとんどのEAに実装されており、最良の候補解が世代間で失われないようにします。これは様々な方法で実装できますが、一般的な方法の1つは、各世代の開始時に最良の候補解を集合 に保存し、世代の終了時、つまり移行と突然変異が完了した後に、最悪の候補解を に置き換えることです。 のサイズは調整パラメータですが、通常は最良の2つの個体を含みます。エリート主義は、もともとDeJongによって遺伝的アルゴリズムのために提案されました。[5]エリート主義はBBOのパフォーマンスに大きな違いをもたらす可能性があるため、強く推奨されます。
- BBOでは、重複置換が頻繁に実装されます。これは、各世代の終わりに集団内の重複個体を置換する手順です。重複のスキャンは演算量が多いため、毎世代ではなく数世代ごとに実行されることがよくあります。
- BBOではブレンディングを実装できます。ブレンディングでは、移入候補解を移出候補解から で置き換える代わりに、を元の値と の線形結合に設定します。
- ここで、およびは、上記のアルゴリズムで示されている標準的な移行に対応する。ブレンド型BBOは、遺伝的アルゴリズムにおけるブレンド型交差に基づいており、[6]標準的なBBOよりも優れた性能を示すことが示されている。[7]
- 上記のBBOアルゴリズムは、移入候補解が移出候補解よりも先に選択され、移入候補解内の各独立変数の移出が他のすべての独立変数とは独立して行われることから、部分移出ベースBBOと呼ばれます。移入候補解と移出候補解を選択するための他のアプローチも提案されています。[8] [9]
- 上図の移行曲線は線形ですが、非線形移行曲線の方がパフォーマンスが向上することがよくあります。[10]
交配
- BBOは、粒子群最適化、[9] [11] 微分進化、[12] 進化戦略、[13]反対論ベースコンピューティング、[14] 事例ベース推論、[15] 人工蜂コロニーアルゴリズム、[要出典]細菌採餌最適化、[16] ハーモニーサーチ、[17]シンプレックスアルゴリズムなど、他のEAとハイブリッド化されています。[18]
- BBOをローカルサーチと組み合わせることで、 BBO単独よりもはるかに優れたパフォーマンスを発揮するミームアルゴリズムを作成することができます。[19]
ソフトウェア
MATLAB
- 以下のMATLABコードは、20次元ローゼンブロック関数を最小化するBBO実装を示しています。以下のコードは非常に基本的なものですが、エリート主義的な手法が用いられていることに注意してください。本格的なBBO実装には、重複置換、ブレンディング、非線形マイグレーション、局所最適化など、上記で説明したバリエーションのいくつかを含める必要があります。
関数BBO % 連続関数を最小化する生物地理学ベースの最適化(BBO)% このプログラムはMATLAB R2012bでテストされました
GenerationLimit = 50 ; % 世代数の制限PopulationSize = 50 ; % 人口のサイズProblemDimension = 20 ; % 各ソリューションの変数の数(つまり、問題の次元)MutationProbability = 0.04 ; % 独立変数あたりのソリューションあたりの突然変異確率NumberOfElites = 2 ; % 世代間で保持する最良のソリューションの数MinDomain = - 2.048 ; % 関数ドメインの各要素の下限MaxDomain = + 2.048 ; % 関数ドメインの各要素の上限
% 集団を初期化します
rng ( round ( sum ( 100 * clock ))); % 乱数ジェネレータを初期化しますx = zeros ( PopulationSize , ProblemDimension ); % 集団にメモリを割り当てますfor index = 1 : PopulationSize % 集団をランダムに初期化しますx ( index , :) = MinDomain + ( MaxDomain - MinDomain ) * rand ( 1 , ProblemDimension ); end Cost = RosenbrockCost ( x ); % 個々のコストを計算します [ x , Cost ] = PopulationSort ( x , Cost ); % 集団を最良から最悪の順にソートしますMinimumCost = zeros ( GenerationLimit , 1 ); % メモリを割り当てますMinimumCost ( 1 ) = Cost ( 1 ); % 各世代での最高コストを MinimumCost 配列に保存しますdisp ( [ 'Generation 0 min cost = ' , num2str ( MinimumCost ( 1 ))]); z = zeros ( PopulationSize , ProblemDimension ); % 一時的な人口のためのメモリを割り当てる
% 人口が最も適合度の高い順に並べられていると仮定して、移住率を計算する
mu = ( PopulationSize + 1 - ( 1 : PopulationSize )) / ( PopulationSize + 1 ); % 移住率lambda = 1 - mu ; % 移住率
Generation = 1 : GenerationLimit %の場合、最適なソリューションとコストをエリート配列に保存します。EliteSolutions = x ( 1 : NumberOfElites , :) ; EliteCosts = Cost ( 1 : NumberOfElites );
% 移行率を使用して、ソリューション間で共有する情報の量を決定します。
for k = 1 : PopulationSize % k番目のソリューションへの確率的移行for j = 1 : ProblemDimension
if rand < lambda ( k ) % 移住すべきか? % はい - 移住元のソリューションを選択する (ルーレット選択) RandomNum = rand * sum ( mu ); Select = mu ( 1 ); SelectIndex = 1 ; while ( RandomNum > Select ) && ( SelectIndex < PopulationSize ) SelectIndex = SelectIndex + 1 ; Select = Select + mu ( SelectIndex ); end z ( k , j ) = x ( SelectIndex , j ); % これは移住ステップですelse z ( k , j ) = x ( k , j ); % この独立変数については移住しませんend
終わり
終わり
k = 1の場合の% Mutation : ParameterIndex = 1のPopulationSize : rand < MutationProbabilityの場合の問題次元z ( k , ParameterIndex ) = MinDomain + ( MaxDomain - MinDomain ) * rand ;終わり、終わり、終わり
x = z ; % ソリューションを新しい移行バージョンと変更バージョンに置き換えますCost = RosenbrockCost ( x ); % コストを計算します[ x , Cost ] = PopulationSort ( x , Cost ); % 人口とコストを最良から最悪の順に並べ替えます
k = 1の場合: NumberOfElites % 最悪な個体を前世代のエリートに置き換えるx ( PopulationSize - k + 1 , :) = EliteSolutions ( k , :); Cost ( PopulationSize - k + 1 ) = EliteCosts ( k );終了
[ x , Cost ] = PopulationSort ( x , Cost ); % 人口とコストを良い順に並べ替えるMinimumCost ( Generation + 1 ) = Cost ( 1 ); disp ([ 'Generation ' , num2str ( Generation ), ' min cost = ' , num2str ( MinimumCost ( Generation + 1 ))]) end
% 最善の解決策を表示し、結果をプロットして終了します。disp
( [ 'Best solution found = ' , num2str ( x ( 1 , :))]) close all plot ( 0 : GenerationLimit , MinimumCost ); xlabel ( 'Generation' ) ylabel ( 'Minimum Cost' ) return
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [x, Cost] = PopulationSort ( x, Cost ) % 人口とコストを最良から最悪の順に並べ替えます[ Cost , indices ] = sort ( Cost , 'ascend' ); x = x ( indices , :); return
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [Cost] = RosenbrockCost ( x ) % x 内の各要素の Rosenbrock 関数値を計算しますNumberOfDimensions = size ( x 、2 ); Cost = zeros ( size ( x 、1 )、1 ); % Cost 配列にメモリを割り当てますfor PopulationIndex = 1 : length ( x ) Cost ( PopulationIndex ) = 0 ; for i = 1 : NumberOfDimensions - 1 Temp1 = x ( PopulationIndex 、i ); Temp2 = x ( PopulationIndex 、i + 1 );コスト(人口指数) =コスト(人口指数) + 100 * (温度2 -温度1 ^ 2 ) ^ 2 + (温度1 - 1 ) ^ 2 ;終了終了戻り値
R
- 「bbo: 生物地理学に基づく最適化」は連続BBOのためのRパッケージです。 [20]
拡張機能
BBOは、ノイズ関数(つまり、ノイズによって適応度評価が損なわれた関数)[21]、制約関数[22]、組み合わせ関数[23]、および多目的関数[24]に拡張されています。[25 ] さらに、マイクロバイオジオグラフィーに着想を得た多目的最適化アルゴリズム(μBiMO)が実装されました。これは、少数の島(μBiMOという名前の由来)に基づいているため、目的関数の呼び出しが少なくて済むため、工業デザインの分野で多目的最適化を解くのに適しています。[26]
数学的分析
BBOはマルコフモデル[27]と動的システムモデル[28]を用いて数学的に解析されてきた。
アプリケーション
研究者たちはBBOを様々な学術・産業アプリケーションに適用し、最先端のグローバル最適化手法よりも優れた性能を発揮することを発見しました。
例えば、Wangらは、BBOがFSCABCと同等の性能を発揮するが、より単純なコードであることを証明した。[29]
YangらはBBOがGA、PSO、ABCよりも優れていることを示した。[30]
参考文献
- ^ Quammen, D. (1997). 『ドードーの歌:絶滅の時代の島嶼生物地理学』スクリブナー.
- ^ Simon, D. (2008). 「生物地理学に基づく最適化」(PDF) . IEEE Transactions on Evolutionary Computation . 12 (6): 702– 713. doi :10.1109/tevc.2008.919004. S2CID 8319014.
- ^ ab マッカーサー, R.; ウィルソン, E. (1967). 『島嶼生物地理学の理論』 プリンストン大学出版局.
- ^ ab Wesche, T.; Goertler, G.; Hubert, W. (1987). 「ワイオミング州南東部におけるブラウントラウトの改良生息地適合性指数モデル」. North American Journal of Fisheries Management . 7 (2): 232– 237. Bibcode :1987NAJFM...7..232W. doi :10.1577/1548-8659(1987)7<232:mhsimf>2.0.co;2.
- ^ De Jong, K. (1975).遺伝的適応システムの行動分析(Ph.D.). ミシガン大学.
- ^ Muhlenbein, H.; Schlierkamp-Voosen, D. (1993). 「ブリーダー遺伝的アルゴリズムのための予測モデル:I. 連続パラメータ最適化」.進化計算. 1 (1): 25– 49. doi :10.1162/evco.1993.1.1.25. S2CID 16085506.
- ^ Ma, H.; Simon, D. (2011). 「制約付き最適化のための生物地理学に基づくブレンド最適化」(PDF) .人工知能の工学応用. 24 (3): 517– 525. doi :10.1016/j.engappai.2010.08.005.
- ^ Simon, D. (2013). 進化的最適化アルゴリズム. Wiley.
- ^ ab Kundra, H.; Sood, M. (2010). 「PSOとBBOのハイブリッドアプローチを用いたクロスカントリーパスファインディング」(PDF) . International Journal of Computer Applications . 7 (6): 15– 19. doi : 10.5120/1167-1370 .
- ^ Ma, H. (2010). 「生物地理学に基づく最適化のための移動モデルの均衡分析」(PDF) .情報科学. 180 (18): 3444– 3464. doi :10.1016/j.ins.2010.05.035.
- ^ Zhang, Y. (2015). 「ウェーブレットエントロピーと生物地理学に基づく最適化と粒子群最適化のハイブリッド化による磁気共鳴画像スキャンにおける病的脳検出」(PDF) .電磁気学研究の進歩. 152 : 41–58 . doi : 10.2528/pier15040602 .
- ^ Bhattacharya, A.; Chattopadhyay, P. (2010). 「生物地理学に基づく最適化によるハイブリッド微分進化による経済的負荷配分の解決」. IEEE Transactions on Power Systems . 25 (4): 1955– 1964. Bibcode :2010ITPSy..25.1955B. doi :10.1109/tpwrs.2010.2043270. S2CID 30052218.
- ^ Du, D.; Simon, D.; Ergezer, M. (2009). 「進化戦略と移民拒否を組み合わせた生物地理学に基づく最適化」(PDF) . IEEE システム・人間・サイバネティクス会議. テキサス州サンアントニオ. pp. 1023– 1028.
- ^ Ergezer, M.; Simon, D.; Du, D. (2009). 「対立的生物地理学に基づく最適化」(PDF) . IEEE システム・人間・サイバネティクス会議. テキサス州サンアントニオ. pp. 1035– 1040.
- ^ Kundra, H.; Kaur, A.; Panchal, V. (2009). 「地下水の可能性を探るための事例ベース推論を用いた生物地理学に基づく最適化への統合アプローチ」(PDF) . The Delving: Journal of Technology and Engineering Sciences . 1 (1): 32– 38.
- ^ Lohokare, M.; Pattnaik, S.; Devi, S.; Panigrahi, B.; Das, S.; Bakwad, K. (2009). 「離散変数のためのインテリジェントな生物地理学ベースの最適化」.自然と生物学にインスパイアード・コンピューティングに関する世界会議. インド、コインバトール. pp. 1088– 1093. doi :10.1109/NABIC.2009.5393808.
- ^ Wang, G.; Guo, L.; Duan, H.; Wang, H.; Liu, L.; Shao, M. (2013). 「生物地理学に基づく最適化とハーモニーサーチのハイブリッド化によるグローバル数値最適化」. Journal of Computational and Theoretical Nanoscience . 10 (10): 2312– 2322. Bibcode :2013JCTN...10.2312W. doi :10.1166/jctn.2013.3207.
- ^ Wang, L.; Xu, Y. (2011). 「カオスシステムのパラメータ推定のための効果的なハイブリッド生物地理学ベースの最適化アルゴリズム」. Expert Systems with Applications . 38 (12): 15103– 15109. doi :10.1016/j.eswa.2011.05.011.
- ^ Simon, D.; Omran, M.; Clerc, M.「再初期化と局所探索による線形生物地理学ベースの最適化」 。 2013年9月6日閲覧。
- ^ 「Bbo: 生物地理学に基づく最適化」2014年9月18日。
- ^ Ma, H.; Fei, M.; Simon, D.; Yu, M.「ノイズのある適応度関数の生物地理学に基づく最適化」 。 2013年9月7日閲覧。
- ^ Roy, P.; Ghoshal, S.; Thakur, S. (2010). 「生物地理学に基づく多制約最適電力フローのための最適化(排出量と非滑らかなコスト関数を含む)」. Expert Systems with Applications . 37 (12): 8221– 8228. doi :10.1016/j.eswa.2010.05.064.
- ^ Song, Y.; Liu, M.; Wang, Z. (2010). 「巡回セールスマン問題のための生物地理学に基づく最適化」.計算科学と最適化に関する国際合同会議. 中国安徽省黄山市. pp. 295– 299.
- ^ Roy, P.; Ghoshal, S.; Thakur, S. (2010). 「生物地理学に基づく最適化を用いた多目的最適電力フロー」.電力部品・システム. 38 (12): 1406– 1426. doi :10.1080/15325001003735176. S2CID 109069222.
- ^ Di Barba, P.; Dughiero, F.; Mognaschi, ME; Savini, A.; Wiak, S. (2016). 「生物地理学に着想を得た多目的最適化とMEMS設計」. IEEE Transactions on Magnetics . 52 (3): 1– 4. Bibcode :2016ITM....5288982D. doi :10.1109/TMAG.2015.2488982. S2CID 17355264.
- ^ Mognaschi, ME (2017). 「マイクロバイオジオグラフィーに着想を得た産業用電磁気設計のための多目的最適化」. Electronics Letters . 53 (22): 1458– 1460. Bibcode :2017ElL....53.1458M. doi :10.1049/el.2017.3072.
- ^ Simon, D.; Ergezer, M.; Du, D.; Rarick, R. (2011). 「生物地理学に基づく最適化のためのマルコフモデル」(PDF) . IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics . 41 (1): 299– 306. doi :10.1109/tsmcb.2010.2051149. PMID 20595090. S2CID 11852624.
- ^ Simon, D. (2011). 「生物地理学に基づく最適化の動的システムモデル」(PDF) .応用ソフトコンピューティング. 1 (8): 5652– 5661. doi :10.1016/j.asoc.2011.03.028.
- ^ Wang, S. (2015). 「ウェーブレットエントロピーとフィードフォワードニューラルネットワークによる果物分類、適応度スケールカオスABCと生物地理学に基づく最適化による学習」.エントロピー. 17 (8): 5711– 5728. Bibcode :2015Entrp..17.5711W. doi : 10.3390/e17085711 .
- ^ Yang, G.; Yang, J. (2015). 「ウェーブレットエネルギーと生物地理学に基づく最適化を用いた脳画像の自動分類」.マルチメディアツールとアプリケーション. 75 (23): 15601– 15617. doi :10.1007/s11042-015-2649-7. S2CID 254825916.
外部リンク
- BBOホームページ