[지능형시스템] - Artificial Bee Colony(ABC) Algorithm

1. 개요

Artificial Bee Colony Algorithm(이하 ABC 알고리즘)은 computer Science, operation research 분야에서 이용되는 전역 최적화 알고리즘이다. 비교적 최근에 연구된 알고리즘으로써 Karaboga, Basturk (2007), A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm에서 본격적으로 소개된 ABC 알고리즘은 꿀벌 군집(honey bee swarm)의 지능적인 수렵 행위를 모방하여 최적화를 수행한다. 아직 한글로 번역된 문서가 없기 때문에 이 글에서는 논문에서 사용한 영어 단어를 그대로 사용한다.

ABC 알고리즘에서는 꿀벌 군집을 이루는 세 종류의 꿀벌이 각자의 기능을 수행하면서 가장 풍부한 자원을 찾는 방식으로 알고리즘이 진행된다. 꿀벌 군집을 이루는 꿀벌은 employed bee, onlooker bee, scout bee가 있다. 다음 항목에서는 ABC 알고리즘을 서술하기 위한 용어나 개념을 정의한다.

2. 용어 정의

Source: 찾고자 하는 최적해의 후보이다.

Nectar amount: 직역하면 꿀의 양이지만, ABC 알고리즘에서는 어떠한 해의 적합도(fitness)를 나타낸다.

Abandon: nectar amount가 증가되지 않는 source를 버리는 행위이다. 이를 통해 ABC 알고리즘은 전역 최적화를 수행할 수 있다.

3. 알고리즘 구조

ABC 알고리즘은 employed bee의 기존 source 및 neighbor source 탐색, onlooker bee의 의사결정, scout bee의 새로운 source 탐색 순으로 알고리즘이 진행된다. 각각의 꿀벌이 하는 자세한 기능은 아래와 같다.

 

1) Employed Bee

알고리즘의 가장 첫 번째 단계에서 탐색을 실행하는 객체로써 자신에게 할당된 하나의 source에 접근하여 neighbor source를 탐색하고 greedy method를 이용하여 nectar amount가 더 큰 source를 선택하여 onlooker bee에게 알린다. 전체 source의 수와 employed bee, onlooker bee의 서로 같다.

2) Onlooker Bee

알고리즘에서 의사결정을 수행하는 객체로써 employed bee로부터 전달받은 각각의 source의 nectar amount 정보를 기반으로 확률적으로 source를 선택하여 해당 source로 이동한다. source로 이동하면 neighbor source를 탐색하고 greedy method를 이용하여 nectar amount가 더 큰 source를 선택한다. 어떠한 source가 탐색과 의사결정의 반복이 거듭되어도 nectar amount가 증가하지 않는다면 scout bee에게 해당 source를 버리고(abandon) 새로운 source를 찾도록 지시한다.

3) Scout Bee

앞에서 설명한 onlooker bee의 명령에 따라 새로운 source를 탐색하는 객체이다.

4) 알고리즘의 실행

ABC 알고리즘의 실행은 아래와 같다. 각 단계에서 이용되는 연산은 다음 항목에서 서술한다.

4. 연산 정의

1) source 초기화

ABC 알고리즘의 첫 번째 단계는 source를 임의의 값으로 초기화하는 것이다. ABC 알고리즘의 각 source는 아래의 수식 (1)과 같이 임의의 값으로 초기화된다. \({X}_{i} = [{x}_{1}, {x}_{2}, {x}_{3}, ..., {x}_{n}]\)는 $i$번째 source를 의미하고, 알고리즘의 인자로 입력받는 \({x}_{max,j}\)는 $X$의 j번째 요소의 최댓값, \({x}_{min,j}\)는 $X$의 j번째 요소의 최솟값을 의미한다. $rand(0,1)$은 0부터 1사이의 임의의 값을 출력하는 함수를 나타낸다.

     

2) Employed bee의 neighbor source 탐색

Employed bee는 수식 (2)를 이용하여 자신이 할당받은 source의 neighbor source를 탐색하고, 할당받은 source와 neighbor source의 적합도(nectar amount)를 계산하여 적합도가 더 큰 source를 onlooker bee에게 알리고 적합도가 낮은 source는 버린다. ${v}_{ik}$는 자신이 할당받은 source의 neighbor source를 나타내고, ${x}_{ik}$는 자신이 할당받은 source를 나타낸다. ${x}_{jk}$는 모든 source 중에서 자신이 할당받은 source를 제외하고 임의로 선택한 source이다. 

     

3) Onlooker bee의 확률적 source 선택

자신의 employed bee에 의해 탐색된 source와 계산된 적합도를 기반으로 onlooker bee는 자신이 직접 탐색할 source를 선택한다. 이 과정에서 onlooker bee는 employed bee가 찾아온 source 중에서 적합도가 좋은 source를 무조건 선택하는 것이 아니라, 적합도가 높은 source가 선택될 확률이 높도록 설정하고 모든 source 중에서 하나를 확률적으로 선택하는 roulette wheel method 또는 Monte Carlo method를 이용한다. 모든 source 중에서 $i$번째 source가 선택될 확률 ${P}_{i}$는 수식 (3)과 같이 계산되며, \({f}_{{X}_{n}}\)는 source ${X}_{n}$의 적합도를 의미한다.

다음으로, onlooker bee는 자신의 employed bee가 찾아온 source와 자신이 선택한 source의 neighbor source에 대한 적합도를 비교하여 최종적으로 source 하나를 선택한다.

     

ABC 알고리즘에서 source를 선택하는 방법은 이 글에서 설명한 roulette wheel method 이외에도 ranking based selection, stochastic universal sampling, tournament selection 등의 방법을 이용할 수 있다.

4) Onlooker bee의 neighbor source 탐색

Onlooker bee는 위에서 설명한 확률적 source 선택에 의해 하나의 source를 선택하고 선택된 source의 neighbor source를 탐색한다. Onlooker bee가 이웃 소르를 탐색하는 방법은 앞에서 설명한 employed bee의 neighbor source 탐색 방법과 같다. 따라서, onlooker bee 또한 수식 (2)를 이용하여 자신이 확률적으로 선택한 source의 neighbor source를 탐색한다. 탐색이 끝나면 자신의 employed bee가 찾아온 소스의 적합도와 자신이 찾은 neighbor source의 적합도를 비교하여 적합도가 더 좋은 source만 남긴다. 이 때, 자신이 관리하는 source의 적합도가 이전 반복에서의 적합도보다 좋아지지 않았다면 ${trial}_{i}$를 1 증가시킨다. 만약 ${trial}_{i}$가 알고리즘의 인자로 전달받은 $limit$ 인자의 값보다 커지면 onlooker bee는 해당 source를 버리고, scout bee에게 새로운 source를 탐색할 것을 지시한다.

5) Scout bee의 새로운 source 탐색

Scout bee는 $i$번째 onlooker bee의 명령에 의해 새로운 $i$번째 source를 찾는다. Scout bee가 찾는 새로운 source는 수식 (2)처럼 어떠한 source의 neighbor source를 탐색하는 것이 아니라, source 초기화에서 이용한 수식 (1)을 이용하여 기존의 source와 상관없는 새로운 source를 탐색한다. Scout bee의 탐색에 의해 ABC 알고리즘은 전역 최적화를 수행할 수 있게 된다.

5. 슈도코드(Pseudocode)

ABC 알고리즘을 하나씩 예시를 들며 설명하기에는 너무 복잡하기 때문에 간단한 슈도코드를 첨부한다.