Optimization : ABC (Artificial Bee Colony) algorithm

ABC 알고리즘에서는 꿀벌 군집을 이루는 세 종류의 꿀벌이 각자의 기능을 수행하면서 가장 풍부한 자원을 찾는 방식으로 알고리즘이 진행된다.

 

1. 꿀벌 정리

꿀벌 군집을 이루는 꿀벌

• employed bee
• onlooker bee
• scout bee

2. 용어 정리

• Source : 찾고자 하는 최적의 해 후보들
• Nectar Amount : 꿀의 양 == 우리가 갖고자 하는 해의 적합도, error율 최소화 비율
• Abandon : nectar amount가 증가되지 않는 Source들을 버리는 행위.
• SN : Source Number
• BN : Bee Number
• D : Optimization Parameter's Number
• MCN : Maximum Cycle Number

---

3. 알고리즘 구조

일벌이 global 을 돌아다니고 확률적으로 최적화 구간을 얘기해주면, 여왕벌이 그 지역으로 가서 최적화된 지역을 찾는 것이다.

1) Employed Bee (일벌)

기존 source 및 neighbor source 탐색

 

알고리즘에서 가장 1번째 단계에서 탐색을 실행하는 객체.

자신에게 할당된 하나의 source로 접근해서, neigbor source를 탐색하고 greedy method를 이용해서 nectar amount가 더 큰 source를 선택해서 onlooker bee에 알려준다.

전체 source 수와 employed bee, onlooker bee 의 수는 같다.

2) Onlooker Bee

의사결정

 

알고리즘에서 의사결정을 수행하는 객체

각각의 employed bee로 부터 받은 각각의 source들의 nectar amount의 정보를 바탕으로 확률적으로 source를 선택해서 해당 source로 이동한다. 

source로 이동한 후 neigbor source들을 탐색하고 greedy method를 이용하여 nectar amount가 더 큰 source를 선택한다.

어떠한 source가 탐색과 의사결정의 반복이 거듭되어도 nectar amount가 증가하지 않는다면, scout bee에게 해당 source를 abandon, 버리고 새로운 source를 찾도록 지시한다.

3) Scout Bee

새로운 source 탐색

 

---

4. 연산 정의

• 모든 source에 한 employed bee가 존재한다.
• 선택에 의해 source를 버리는 bee들은 scout bee들로 된다.source의 위치 : optimization problem의 위치
• source의 nectar amount 정도 : optimization의 정도
• employed bee 또는 onlooker bee의 갯수는 인구밀도에서 solution의 갯수와 동일하다.
• 위치를 solution이라고도 칭한다.

1) source 초기화

첫 스텝에서는 ABC는 random한 구간을 선택하는데, ABC는 source 위치의 무작위 분포 초기 모집단 P (G = 0)를 생성합니다.

여기서 i, SN은 모집단 size.

j, optimization parameter의 갯수. (2차원이면 j는 0,1, index를 말한다.)

2) Evaluate population

employed bee들은 각자 source에서 가져온 fitness 정도를 모두 합해서, Softmax 함수로 확률로써 정의한다.

SN은 source number이기 때문에 시그마 위에 SN이 올라가서 SN만큼 합을 한다.

 

3) Employed Bee의 neighbor source 탐색

 

Employed bee는 수식 (2)를 이용하여 자신이 할당받은 source의 neighbor source를 탐색하고, 할당받은 source와 neighbor source의 적합도(nectar amount)를 계산하여 적합도가 더 큰 source를 onlooker bee에게 알리고 적합도가 낮은 source는 버린다. 

 

vik는 자신이 할당받은 source의 neighbor source를 나타낸다.

xik는 자신이 할당받은 source를 나타낸다. 

xjk는 (모든 source - 자신이 할당받은 source) == 임의로 선택한 source. 

 

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의 적합도가 이전 반복에서의 적합도보다 좋아지지 않았다면 trialitriali를 1 증가시킨다. 만약 trialitriali가 알고리즘의 인자로 전달받은 limitlimit 인자의 값보다 커지면 onlooker bee는 해당 source를 버리고, scout bee에게 새로운 source를 탐색할 것을 지시한다.

 

5) Scout bee의 새로운 source 탐색

초기화는 처음 min, max를 이용해서 위치의 모집단을 (1)번 식으로 고른 후,

각 source들의 값들을 측정한 후, 은 employed, onlooker, scout bee의 탐색 과정에서 반복된 사이클 MCN에 적용된다.

즉, MCN, Maximum Cycle Number을 적용하면 MCN을 넘기면 cycle을 종료한다.

 

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

 

여기서 employed bee들은 local 정보에 의존하는 onlooker의 메모리에 의해서 위치를 조정하고, 새로운 source의 nectar amount를 테스트한다. onlooker bee에 따라서 움직인다.