Particle Swarm Optimization ( PSO , 입자 군집 최적화 )

알고리즘

정지홍 2025. 3. 1. 18:32

PSO의 개요

1995년에 제안된 최적화 알고리즘이다.
이는 새와 물고기 떼의 이동 패턴에서 영감을 받아서 개발되었다.
- PSO는 주어진 목적 함수를 최적화하기 위해서, 여러 개의 입자( particle )로 구성된 군집( swarm )을 활용하며, 개별 입자들은 '자신의 경험'과 '군집 전체의 경험'을 활용해서 최적 해를 찾아간다.
장점
- 1. 파라미터가 적으며 수식이 적어서 구현이 간단함.
- 2. 전역 최적해는 찾을 가능성이 높다.
- 3. 기울기 계산이 필요하지 않아서, 비선형 or 복잡한 함수에도 적용 가능
단점
- 1. 적절한 매개변수를 사용하지 않는다면, 지역 최적해에 빠질수도 있다. 그리고 탐색속도에도 영향을 줌.
- 2. 많은 입자가 존재할 시, 차원이 높아져서 성능이 저하된다.

2. 속도와 위치를 업데이트
- 공식에 따라서 모든 입자의 속도를 업데이트함.
- 속도를 반영하여 입자의 위치 업데이트
3. 최적 해 갱신
- 현재 위치의 적합도(fitness)를 평가
- 기존의 개인 최적해( p best )와 비교하여 갱신
- 기존의 군집 최적해( g best )와 비교하여 갱신
4. 종료 조건 검사
- 최적해가 수렴하거나 최대 반복 횟수에 도달하면 종료한다.

1. 입자 particle
- 최적화 문제에서 가능한 해(solution)을 나타냄.
- 입자는 위치( position )와 속도( velocity )를 가짐.
2. velocity와 position 업데이트
- 입자는 탐색 공간을 이동하면서, '자신의 경험'과 '군집의 경험;을 바탕으로 속도를 조절함.

1. 입자의 개수 ( N , swarm size )
- 군집을 이루는 입자의 수이다. 보통 10~100개 사이로 설정
2. 관성 계수 ( w )
- 입자의 현재 속도를 유지하려는 정도를 조절한다.
  - 값이 클수록 탐색(exploration)증가
  - 값이 작을수록 수렴 증가
  - 일반적으로는 0.4 ~ 0.9 범위를 사용
3. 학습 계수 ( c1 , c2 )
- 개인 최적화와 군집 최적 해를 따르는 정도를 조절
- 보통 c1=c2=2.0이 많이 사용됨
4. 속도 제한 ( V max )
- 속도의 최대값을 설정해서 탐색이 지나치게 코지는 것을 방지한다.

PSO를 적용한 path planning에서는, 여러개의 particle은 각기 다른 경로를 나타낸다. 그리고 이 particle들이 서로 협력하면서 점점 더 좋은 경로를 찾아가는 방식으로 최적화를 수행
경로 탐색 과정
- 1. particle 정의
  - 하나의 particle은 경로를 의미함. ( 처음에는 랜덤하게 여러 개의 particle( path )를 생성
- 2. fitness(적합도) 함수 정의
  - 각 particle( path )의 품질을 평가해야한다.
  - fitness function은 path의 length와 obstacle과의 collision 여부를 고려해서 계산
  - ex) fitness function
    - Fitness = lengthOfPath + ( collision횟수 * 1000 )
    - ===> 경로는 짧을수록 좋으며, 충돌시에는 큰 패널티를 부여해서 나쁜 경로를 제거한다.
- 3. p best와 g best를 업데이트
  - 각각의 particle은 자신이 경험한 가장 좋은 p best를 기억한다.
    군집 내에서 가장 좋은 경로 ( g best )를 전체 particle이 공유한다.
- 4. 속도 업데이트 및 새로운 경로 생성
  - particle들은 p best와 g best를 참고해서 점점 더 좋은 경로로 이동함.
- 5. 최적 경로 찾기
  - 위의 과정을 여러번 반복하다가보면, particle들은 점점 더 obstacle을 피하면서 짧은 경로를 찾게 된다.
    ==> 최종적으로는 g best에 저장된 path가 가장 좋은 path가 된다.