생체지리학 기반 최적화

BBO(Biogeography-Based Optimization, BBO)는 일정한 품질 측정, 즉 피트니스 기능과 관련하여 후보 솔루션을 확률적이고 반복적으로 개선하여 기능을 최적화하는 진화 알고리즘(EA)이다. BBO는 많은 변형을 포함하며, 문제에 대해 어떠한 가정도 하지 않기 때문에 광범위한 문제에 적용될 수 있기 때문에 메타휴리스틱스 등급에 속한다.

BBO는 일반적으로 다차원 실제값 함수를 최적화하기 위해 사용되지만 함수의 구배를 사용하지 않기 때문에 구배 강하법이나 준 뉴턴법 등 고전적 최적화 방법에서 요구하는 대로 함수를 달리할 필요가 없다는 것을 의미한다. 따라서 BBO는 불연속 기능에 사용될 수 있다.

BBO는 후보 솔루션의 모집단을 유지하고, 기존 후보 솔루션을 단순한 공식에 따라 결합하여 새로운 후보 솔루션을 만들어 문제를 최적화한다. 이런 식으로 객관적 기능은 후보 해법이 주어지는 품질 측정만 제공하는 블랙박스로 취급되며, 기능의 구배는 필요하지 않다.

많은 EA들과 마찬가지로, BBO는 자연적인 과정에 의해 동기부여되었고, 특히 BBO는 시간과 공간을 통한 생물종의 분포에 대한 연구인 생물지리학에 의해 동기부여되었다.^[1] BBO는 원래 Dan Simon에 의해 2008년에 도입되었다.^[2]

기본 원리

수학적 생물지질학 모델들은 특정종(신종의 진화), 섬들 사이의 종(동물, 물고기, 새 또는 곤충)의 이동, 종의 멸종을 기술한다.^[3] 생활밀착형 섬은 서식지 적합성지수(HSI)가 높다고 한다.^[4] HSI와 상관관계가 있는 특징으로는 강우, 식물 다양성, 지형 다양성, 토지 면적, 온도 등이 있다. 결정하는 특징을 적합성 지수 변수(SIV)라고 한다. 거주성 측면에서 SIV는 독립 변수, HSI는 종속 변수다.

HSI가 높은 섬은 많은 종을 지원할 수 있고, HSI가 낮은 섬은 몇 가지 종만 지원할 수 있다. HSI가 높은 섬들은 많은 개체수와 그들이 주최하는 많은 종들 때문에 가까운 서식지로 이주하는 많은 종들을 가지고 있다. HSI가 높은 섬에서 이주하는 것은 종들이 그들의 집을 떠나고 싶어하기 때문에 일어나지 않는다는 것에 주목하라; 결국, 그들의 고향 섬은 살기 좋은 곳이다. 이민은 개체수가 많은 다수의 종에 대한 임의의 영향이 축적되기 때문에 발생한다. 이민은 동물들이 배를 타고, 수영하고, 날아다니거나, 바람을 타고 이웃 섬으로 가면서 일어난다. 한 종이 섬에서 이주할 때, 그것은 그 종들이 원래의 섬에서 완전히 사라진다는 것을 의미하는 것이 아니다; 단지 소수의 대표자들만이 이민을 갔기 때문에, 이주하는 종은 동시에 이웃 섬으로 이주하는 동안 원래의 섬에 남아 있다. 그러나, BBO에서는 섬에서 이민을 가면 섬에서 멸종한다고 가정한다. 종은 함수의 독립 변수를 나타내며, 각 섬은 함수 최적화 문제에 대한 후보 솔루션을 나타내기 때문에 BBO에서는 이러한 가정이 필요하다.

HSI가 높은 섬은 이민률이 높을 뿐만 아니라 이미 많은 종을 지원하고 있기 때문에 이민률이 낮다. 이러한 섬으로 이주하는 종들은 다른 종들로부터 자원을 얻기 위한 경쟁이 너무 심하기 때문에 섬의 높은 HSI에도 불구하고 죽는 경향이 있을 것이다.

HSI가 낮은 섬은 인구가 적어 이민률이 높다. 다시 말하지만, 이것은 종들이 그러한 섬으로 이주하기를 원하기 때문이 아니다; 결국, 이 섬들은 살기 바람직하지 않은 장소들이다. 이들 섬으로 이민이 발생하는 이유는 추가 종의 여지가 많기 때문이다. 이민 온 종들이 새로운 집에서 얼마나 오래 생존할 수 있을지는 또 다른 의문이다. 그러나 종 다양성은 HSI와 상관관계가 있기 때문에 더 많은 종들이 낮은 HSI 섬에 도착하면 섬의 HSI는 증가하는 경향이 있을 것이다.^[4]

오른쪽 그림은 섬 이주 모델을 보여준다.^[3] 이민률 $\lambda {\displaystyle }$ ${\디스플레이$ 스타일 $\lambda}$과 이민률 $\mu {\displaystyle }$ ${\디스플레이$ 스타일 $\mu}$은 섬 내 종수의 함수다. $가능$한 최대 이민률 I {\$displaystyle I}$은 섬에 0종이 있을 때 발생한다$$. 종의 수가 늘어나면서 섬은 점점 더 붐비고, 이민에서 살아남을 수 있는 종은 줄어들고, 이민률은 감소한다. 서식지가 지원할 수 있는 종 중 가장 많은 $수$가 ${\displaystyle {Smax}_{}}${\$displaystyle S_{\max$}}인데, 이 시점에서 이민률은 0이다. 섬에 종이 없다면 이민률은 0이다. 섬의 종 수가 증가함에 따라 점점 더 붐비게 되고, 더 많은 종 대표자들이 섬을 떠날 수 있게 되며, 이민률도 높아진다. 섬이 가장 많은 수의 $가능$한 종 S ${\displaystyle {max}_{}}$ ${\$을 포함할 때, 이민률은 최대 가능한 값 $E{\displaystyle }$ ${\displaystyle E}$에 도달한다$.$

이민$$ 모델 $\lambda {\displaystyle }$ ${\displaystyle \lambda }$ 및 이민 $\mu s{\displaystyle }$ ${\displaystyle \mu }$ 확률$$. ${\displaystyle S_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$은 평형종 수이고, ${\displaystyle {Smax}_{}}$ ${\$은 섬이 지원할 수 있는 최대 종 수이다$$. ${\displaystyle I}$ ${\displaystyle I}$과 $E{\displaystyle }$ ${\displaystyle E}$은 각각 최대 이민률과 이민률이다.

BBO에서 ${\displaystyle {\lambda }_{}}$ k ${\$는 k$${\$displaystyle k$} -th$$ 후보 솔루션에서 주어진 독립 변수가 교체될 ${\displaystyle {확률}_{}}$이며, 즉, $\$ k {\$displaystyle$ \$lambda_{k}}}$는$$ {\$displaysty x_{$k}의 이민 확률이다$.$ 독립 변수가 재생될 경우ed, 그리고 나서 이민 후보 해법은 이민 확률 ${\$에 비례하는 확률로 선택된다$.$ 이것은 보통 룰렛 휠 선택을 사용하여 수행된다.

${\displaystyle {\text{Prob}(x_{j})이민을 위해 {\text{{n1}={\frac {\mu _{j}{\sum _{i=1}^{N}\mu _{i}}}}}}}}}}}}}을(를) 선택한다.$

$j{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle \cdots }$, ${\displaystyle N}$ ${\displaystyle j=1,\cdots ,N}$에 대해$,$ 여기서 $N{\displaystyle }$ ${\displaystyle N}$은 모집단의 후보 솔루션 수입니다.

알고리즘.

대부분의 다른 EA들처럼, BBO는 돌연변이를 포함한다. $n{\displaystyle }$ ${\displaystyle n}$ -차원$$ 함수를 최적화하기 위한$$ 모집단 크기가 $N{\displaystyle }$ ${\displaystyle N}$인 기본 BBO 알고리즘은 다음과 같이 설명할 수 있다.

$N{\displaystyle }$ ${\$ $N}$ 후보$$ 솔루션 {$}{x_{k}\}\displaystyle \{$$k$}\}\c}}의 모집단을 초기화하지 않음(종료 기준) 각 ${\displaystyle x_{}}$ k ${\displaystystyle$$x_{$$k$$}}}}}$에 대해 $마이그레이션{\displaystyle {}_{}}$ 확률${\displaystyle {}_{}{\mu k}_{}}$를 설정하십시오$.$ ${\displaystyle \mu _{k}\in [0,1]}$ For each ${\displaystyle x_{k}}$, set immigration probability ${\displaystyle \lambda _{k}=1-\mu _{k}}$ do ${\displaystyle \{z_{k}\}\leftarrow \{x_{k}\}}$ For each individual ${\displ$$aystyle z_{k}(k=1,\cdots ,N)}$ do For each independent variable index ${\displaystyle s\in [1,n]}$ do             Use ${\displaystyle \lambda _{k}}$ to probabilistically decide whether to immigrate to ${\displaystyle z_{k}}$ If immigrating then                 Use ${\displaystyle \{\$$mu _{i}\}}$ to probabilistically select the emigrating individual ${\displaystyle x_{j}}$ ${\displaystyle z_{k}(s)\leftarrow x_{j}(s)}$ End if         Next independent variable index: ${\displaystyle s\leftarrow s+1}$         Probabilistically mutate ${\displaystyle z_{$$k}}}$ ${\displaystyle \mathrm{다음<img\; alt="\{\backslash displaystyle\; z\_\{k\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/a51cdfac24f8b95ed711f11ea9502da4087b6a24"\; style="vertical-align:\; -0.671ex;\; width:2.17ex;\; height:2.009ex;">}}$ ${\displaystyle \mathrm{개인}}$: $k{\displaystyle }$ ${\displaystyle \leftarrow }$ k${\displaystyle }$+ 1 ${\displaystyle$ k$\leftarrow k+1$${k$}\}}{\$displaystyle$\{$x_${k$}\}\{z_{k}\}}}}}}}$다음$$ 세대 

BBO 알고리즘의 논의

• 모집단 크기 $N{\displaystyle }$ ${\displaystyle N}$은(는) 튜닝 매개 변수다. $N{\displaystyle }$ ${\displaystyle N}$이(가) 너무 작거나 크면 BBO의 최적화 성능이 저하된다. BBO의 일반적인 구현에서는 20에서 200 사이의$$ $N{\displaystyle }$ {\$displaystyle$ N$}$ 값을 사용한다$.$
• 후보 솔루션${\displaystyle }${ ${\displaystyle x_{}}$ k ${\displaystyle {}_{}{}_{}^{}}$ k${\displaystyle {}_{}^{}}$= ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{N}}_{}^{}}$ ${\$의 초기 모집단은 대개 무작위로 생성된다$$. 그러나 일부 합리적인 추측이나 이전에 알려진 최적화 문제에 대한 좋은 해결책에 기초하여 문제 의존적인 방식으로 생성될 수 있다.
• 종료 기준은 다른 EA와 마찬가지로 문제에 의존한다. 대부분의 애플리케이션에서 종료 기준은 세대수 한계 또는 기능 평가 한계(즉, 목표 기능이 평가되는 빈도)이다.
• ${\displaystyle \{}$ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}}${\$displaystyle$\{$z_{k}\}\}}$은(는) 모든 이민 변수가 세대 초기에 있는 모집단에서 발생할 수 있도록 임시 모집단으로$,{\displaystyle }$ { ${\displaystyle {}_{}}$ ${\displaystyle k_{}}${\$displaystyle$\{$x_{k}\}}}}$이다$.$

알고리즘 변형

기본 BBO 알고리즘에 많은 변형이 제안되어 왔으며, 그 중 다음과 같다.

• 엘리트주의는 한 세대에서 다음 세대로 최고의 후보 해결책이 없어지지 않도록 하기 위해 대부분의 EA에서 시행된다. 이것은 다양한 방법으로 구현될 수 있지만, 한 가지 일반적인 방법은 각 세대의 초기에 최적의 후보 솔루션을 세트 $E{\displaystyle \mathbb{}}$ ${\$에 저장한 다음$,$ 마이그레이션과 돌연변이가 복합된 후$$, 최악의 후보 솔루션을 세대 말에 $E{\displaystyle \mathbb{}}$ ${\$로 교체하는 것이다.레티드. $E{\displaystyle \mathbb{}}$ ${\$의 크기는 조정 매개 변수지만$$ E ${\$은(는) 일반적으로$$ 가장 우수한 두 개인을 포함한다. 엘리제이션은 원래 DeJong에 의해 유전 알고리즘을 위해 제안되었다.^[5] 엘리트주의는 BBO의 성과에 상당한 차이를 만들 수 있으며, 이를 적극 추천한다.
• 중복 교체는 BBO에서 시행되는 경우가 많다. 이것은 인구에서 중복된 개인을 대체하는 각 세대 말기의 절차다. 중복 스캔은 $O{\displaystyle ({}^{}}$ $){\displaystyle O(N^{2})$ 연산이기$$ 때문에 연산 집약적일 수 있으므로, 모든 세대가 아닌 몇 세대에 한해서만 수행되는 경우가 많다.
• 혼합은 BBO에서 구현될 수 있다. 혼합을 사용할 경우, 이민자 후보 솔루션의 z$$ ${\displaystyle k_{}}$( s )${\displaystyle$ $z_$${$$k}(s)$를 이민자 ${\displaystyle {솔루션}_{}}$에서 x $j{\displaystyle {}_{}}$ ${\displaystyle (}$s ) {\$displaysty$x_${j}($s$$$)$로 대체하는 대신, z ${\displaystyle k_{}}$(${\displaystyle s}$$)$는$$원래 $값$과 x${\displaystyle {}_{}}$(${\displaystyle }$) ${\$$displ$)의 선형 조합으로 설정된다$$.$aystyle x_{j$$s):$

${\displaystyle z_{k}s\왼쪽 화살표 \cHB_{k}+(1-\cHB)x_{j}s}$

여기서 $\alpha {\displaystyle }$ ${\displaystyle \in }$ [ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle \alpha \in [0,1]}$및 $\alpha {\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \alpha =0}$은(는) 위의 알고리즘에 표시된 대로 표준 마이그레이션에 해당한다$$. 혼합 BBO는 유전 알고리즘의 혼합 교차점을 기반으로 하며 표준 BBO를 능가하는 것으로 나타났다.^[6][7]

• 위에서 제시한 BBO 알고리즘은 이민 후보 해법이 선택되기 전에 이민 후보 해법이 선택되기 때문에 부분 이민 기반 BBO라고 하며, 이민 후보 해법에서 각 독립 변수에 대한 마이그레이션은 다른 모든 독립 변수와 독립적으로 수행된다. 이민·이민 후보 해법 선정을 위한 다른 접근법도 제시됐다.^[8][9]
• 위 그림의 마이그레이션 곡선은 선형이지만 비선형 마이그레이션 곡선은 종종 더 나은 성능을 제공한다.^[10]

잡종화

• BBO는 입자 군집 최적화,^[9][11] 미분 진화,^[12] 진화 전략,^[13] 반대 기반 컴퓨팅,^[14] 사례 기반 추론,^[15] 인공 벌 군집 알고리즘,^{[citation needed]} 박테리아 포징 최적화,^[16] 조화 탐색 및 ^[17]심플렉스 알고리즘을 포함한 여러 다른 EA와 혼합되었다.^[18]
• BBO를 로컬 검색과 결합해 BBO 단독보다 훨씬 뛰어난 성능을 가진 memetic 알고리즘을 만들 수 있다.^[19]

소프트웨어

매트랩

• 다음의 MATLAB 코드는 20차원 로젠브로크 기능을 최소화하기 위한 BBO 구현을 제공한다. 다음 코드는 엘리트주의를 포함하지만 매우 기본적이라는 점에 유의하십시오. 심각한 BBO 구현에는 중복 교체, 혼합, 비선형 마이그레이션 및 국소 최적화 등과 같이 위에서 논의된 몇 가지 변형이 포함되어야 한다.

함수 BBO % 바이오지오그래피 기반 최적화(BBO) % 연속함수 %을(를) 최소화하기 위한 이 프로그램을 MATLAB R2012b GenerationLimit = 50, % 세대수 제한 MumpSize = 50, % 모집단 크기 문제Dimension = 20, 각 솔루션(즉 문제 차원)의 변수 수 = 0.04, 돌연변이를 사용하여 테스트했다.독립 변수 NumberOfElite당 솔루션 수 = 2; 한 세대에서 다음 MinDomain = -2.048까지 유지할 수 있는 최상의 솔루션 수 %; 함수 도메인 MaxDomain = +2.048, 함수 도메인 각 요소의 % 상한 비율 모집단 rng 초기화(100*클럭); 초기 %ize the random number generator x = zeros(PopulationSize, ProblemDimension); % allocate memory for the population for index = 1 : PopulationSize % randomly initialize the population  x(index, :) = MinDomain + (MaxDomain - MinDomain) * rand(1, ProblemDimension); end Cost = RosenbrockCost(x); % compute the cost of each individual   [x, Cost] = PopulationSort(x, Cost); % sort the population from best to worst MinimumCost = zeros(GenerationLimit, 1); % allocate memory MinimumCost(1) = Cost(1); % save the best cost at each generation in the MinimumCost array disp(['Generation 0 min cost = ', num2str(MinimumCost(1))]); z = zeros(PopulationSize, ProblemDimension); % allocate memory for the temporary 모집단 % 계산 마이그레이션 비율(인구 비율 + 1 - (인구 크기 + 1:인구 크기 + 1) / (인구 크기 + 1); % 이민률 람다 = 1 - mu; % 세대 이민률 = 1 : 세대 제한 비율 % 엘리트 어레이 엘리트 솔루션에서 최고의 솔루션 및 비용 절약 x(1: 번호)OfElites:);EliteCosts)Cost(1:NumberOfElites).%사용 이동 요금 해결책 사이에 k를 공유하는 것이 얼마나 정보를 결정할)1:j의k-th 해결책 PopulationSize%확률 이동)1:ProblemDimension 만약 란드 <, lambda(k)%?%예-해결책에서(룰렛 whee 이민을 가려면 트집을 잡아라 이민해야 한다.나는 s선거)RandomNum)발생*sum(뮤), 선택)mu(1), SelectIndex=1;(RandomNum>선택)&&(SelectIndex<>PopulationSize)SelectIndex = SelectIndex+1;을 선택합니다)+mu(SelectIndex)을 선택합니다;끝 z(kj))x(SelectIndex j).%이것은 이주 단계 다른 z(kj)=x(kj), 이 독립 variab에%가 이동되는 것이다.끝까지 르k = 1에 대한 끝 % 돌연변이 : 모수에 대한 모집단 크기지수 = 1 : 랜드 < 돌연변이 확률 z(k, 매개변수)일 경우 문제차원Index) = MinDomain + (MaxDomain - MinDomain) * rand;  end  end  end  x = z; % replace the solutions with their new migrated and mutated versions  Cost = RosenbrockCost(x); % calculate cost  [x, Cost] = PopulationSort(x, Cost); % sort the population and costs from best to worst  for k = 1 : NumberOfElites % replace the worst individuals with the previous generation's elites  x(PopulationSize-k+1, :) = EliteSolutions(k, :);  Cost(PopulationSize-k+1) = EliteCosts(k);  end  [x, Cost] = PopulationSort(x, Cost); % sort the population and costs from best to worst  MinimumCost(Generation+1) = Cost(1);  disp(['Generation ', num2str(Generation), ' min cost = ', num2str(MinimumCost(Generation+1))]) end % Wrap it up by displaying the best solution and by plotting the results 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) % Sort the population and costs from best to worst [Cost, indices] = sort(Cost, 'ascend'); x = x(indices, :); return %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [Cost] = RosenbrockCost(x) % Compute the Rosenbrock function value of each element in x NumberOfDimensions = size(x, 2); Cost = zeros(size(x, 1), 1); % allocate memory for the Cost array for PopulationIndex = 1 : 길이(x) 비용(인구)색인) = 0; i = 1에 대해 : NumberOfDimensions-1 Temp1 = x(인구)색인, i); 온도2 = x(인구)색인, 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를 적용했다. 그들은 BBO가 최첨단 글로벌 최적화 방법보다 더 잘 수행된다는 것을 발견했다.

예를 들어, Wang 등은 BBO가 FSCABC와 동일한 성능을 수행했지만 더 간단한 코드를 사용했다는 것을 증명했다.^[29]

양 외 연구진은 BBO가 GA, PSO, ABC보다 우수하다는 것을 보여주었다.^[30]

참조

외부 링크

• BBO 홈 페이지