떼지능(Swarm Intelligence)

    여기서는 생물의 군집이 나타내는 지적 활동에서 힌트를 얻은 알고리즘인 떼지능(swarm intelligence)에 공부합니다. 일자군집 최적화, 개미집단 최적화, 물고기 떼의 행동행태 알고리즘 등을 예로서 개념을 이해하는데 중점을 두고 공부해 보겠습니다.

1. 입자군집 최적화(PSO; Particle Swarm Optimization)  

    입자군집 최적화(PSO; Particle Swarm Optimization)는 물고기 떼로 대표되는 생물의 군집 활동을 시뮬레이션하여 최적값을 탐색하는 최적화 방법입니다. PSO와 같은 swarm-based optimization에서는 주어진 법칙에 더하여 agent들이 저장하고 있는 정보를 조합하여 최적해를 찾아갑니다.

    입자군집 최적화(PSO)에서는 탐색 공간 속에 최적해를 탐색할 복수의  입자(agent)들을 날아다니게 해서 최적해를 탐색합니다. 여기에서 입자(이하 'agent'로 표기합니다)란 생물 개체를 추상화한 존재입니다. 초기 상황에서는 탐색공간 어느 곳에 최적해가 존재하는지 모르기 때문에 일정범위 내에서 랜덤으로 agent를 적당히 배치합니다. 각 agent는 자신의 현재 위치에 관한 정보를 비롯해 이동할 방향에 관한 속도정보를 가지고 있습니다. 각 agent는 특정시간에 있는 자신의 위치에서 자신이 가진 속도 정보에 따라 이동합니다. 이때 과거의 기억(정보)을 사용하여 속도성분을 순차적으로 조절합니다. 이때 이용하는 과거의 기억(정보)은 두 가지입니다.

    1) 자신의 기억(자신이 과거에 얻은 최고의 해의 값과 그때의 위치)

    2) 군집 전체의 기억(군집 전체가 과거에 얻은 최고의 해의 값과 그때의 위치)  

    위의 1)은 자신의 초기위치에서 이동해 온 길에서 가장 좋은 평가값을 얻은 위치 좌표에 관한 기억입니다. 이 정보에 근거하여과 거 최고의 위치로 향해 속도를 조절합니다.

    2)는 자신이 아닌 군집 전체가 과거에 얻은 가장 좋은 평가값에 대응한 좌표의 정보입니다. 이 정보를 사용하여 군집 전체가 가진 기억을 공유하면서 과거 최고의 해를 얻은 장소를 향해서 속도를 수정합니다. 입자군집 최적화(PSO)에서는 이와 같은 방법으로 과거에 경험했던 최고값을 얻을 수 있는 장소를 중심으로 탐색하는 것입니다. 

    (속도 계산(velocity calculation), 위치 업데이트(position update) 및 평가(evaluation)에 관련된 수학적인 수식과 계산 과정들은 생략하겠습니다.)

 

    이러한 swarm-based optimization은 계산량이 많다는 단점이 존재하지만, 각 agent가 서로 정보를 교환하면서 최적화를 수행하기 때문에 하나의 agent가 local optimum에 빠지더라도 전체적으로는 global optimum에 수렴할 수도 있다는 장점이 있습니다. 이러한 업데이트 방식 때문에 PSO를 global optimization algorithm으로 분류하기도 합니다.

 

2. 개미집단 최적화(ACO; Ant Colony Optimization)

     개미집단 최적화(ACO; Ant Colony Optimization)는 최단 경로를 탐색하는데 특화된 최적화 알고리즘입니다. 개미 집단이 먹이 장소와 개미집 사이의 최단 경로를 찾아내는 원리를 시뮬레이션한 떼지능 알고리즘(swarm intelligence)입니다.

 

(그림) 최단결로 탐색 원리

    위 (그림)은 개미집단 최적화에의 최단 경로 탐색 원리를 나타냅니다. 즉, 개미집(N)과 먹이 장소(F) 사이의 최단경로를 탐색하는 과정입니다. 처음에는 개미들은 랜덤으로 경로를 선택해서 개미집(N)과 먹이장소(F) 사이를 왕복합니다. 개미는 이동시 다리에서 페로몬을 방출하는데, 페로몬의 화학물질로서 개미를 끌어당기는 성질이 있습니다. 경로 선택에서는 경로에 페로몬의 농도가 높은 쪽이 선택되기 쉽습니다. 또한 페로몬은 휘발성 물질이라 시간이 지나면서 농도가 줄어들게 됩니다.

    이러한 설정을 근거로 개미 집단의 보행 시뮬레이션을 실행하는 과정을 단계적으로 보면, 개미들은 다음과 같은 과정을 따릅니다.

 

1. 개미들은 무작정 개미집 주변을 돌아다닌다.

2. 만약 음식을 찾아내면 개미는 페로몬을 뿌리며 집으로 돌아온다.

3. 페로몬은 매우 매력적이어서 개미가 따라가고 싶게 만든다.

4. 개미가 집으로 돌아오는 횟수가 많을수록 그 경로는 더 견고해진다.

5. 긴 경로와 짧은 경로가 있으면 같은 시간에 짧은 경로로 이동할 수 있는 횟수가 많다.

6. 짧은 경로는 갈수록 더 많은 페로몬이 뿌려지면서 더욱 견고해진다.

7. 페로몬은 휘발성이기 때문에 시간이 지나면서 긴 경로는 사라진다.

8. 결국 모든 개미가 짧은 경로를 선택한다.

 

   개미집단 최적화(ACO)는 최적경로 탐색에 특화된 알고리즘으로 통신망 트래픽의 최적화 문제나 공작기계의 최적 배치 문제 등에 적용되고 있습니다.

 

3. 물고기 떼의 행동행태 알고리즘(AFSA; Artificial Fish Swarm Algorithm)

    물고기 떼의 행동행태 알고리즘(AFSA; Artificial Fish Swarm Algorithm)은 입자군집 최적화(PSO; Particle Swarm Optimization)가 발전된 최적화 방법입니다. 

 

    인공 물고기 떼 알고리즘에서는 물고기 떼에서 나타나는 다음과 같은 행동을 시뮬레이션하여 최적화를 실행합니다.

    1) 회피: 물고기가 밀집된 곳을 회피한다.

    2) 포식: 다른 물고기의 현재 위치에 대한 평가값을 조사하여 더 좋은 장소로 이동한다

    3) 추미: 더 좋은 평가값을 주는 위치에 있는 물고기에 접근한다.

    4) 랜덤 이동: 랜덤으로 이동한다.

 

    물고기 떼의 행동행태 알고리즘은 입자군집 최적화와 비교해 더 좋은 탐색 성적을 보이기도 하지만 탐색 알고리즘이 복잡해서 구현하기 어렵다는 단접도 있습니다.    

 

    이상으로 떼지능(Swarm Intelligence)의 몇 가지 주요한 알고리즘을 알아보았습니다.

 

    (다음 편에는 자연어처리에 대해 공부하고자 합니다)

 

2023.05.29 - [인공지능(AI; Artificial Intelligence)] - 인공지능(AI): 진화연산(3) - 유전 알고리즘(GA; Genetic Algorithm) (2)