입자 군집 최적화

3. 매개변수 선택

PSO 매개변수 선택은 최적화 성능에 큰 영향을 미칠 수 있다. 따라서 우수한 성능을 내는 PSO 매개변수를 선택하는 것은 많은 연구 주제였다.

발산("폭발")을 방지하기 위해 관성 가중치는 1보다 작아야 한다. 다른 두 매개변수는 제약 접근 방식을 통해 도출하거나 자유롭게 선택할 수 있지만, 분석 결과 이를 제한하는 수렴 영역이 제시된다. 일반적인 값은 $[\; 1,3]$ 범위에 있다.

PSO 매개변수는 다른 오버레이 최적화 프로그램(메타 최적화)을 사용하여 조정하거나, 퍼지 논리를 사용하여 최적화 중에 미세 조정할 수도 있다.

매개변수는 다양한 최적화 시나리오에 대해서도 조정되었다.

4. 군집 토폴로지

군집 토폴로지는 각 입자가 정보를 교환할 수 있는 입자의 부분 집합을 정의한다. 알고리즘의 기본 버전은 전역 토폴로지를 군집 통신 구조로 사용한다. 이 토폴로지는 모든 입자가 다른 모든 입자와 통신할 수 있도록 허용하므로, 전체 군집은 단일 입자에서 동일한 최적 위치 '''g'''를 공유한다. 그러나 이러한 접근 방식은 군집이 지역 최솟값에 갇히게 할 수 있다.^[2]

입자 간의 정보 흐름을 제어하기 위해 다양한 토폴로지가 사용되는데, 예를 들어 지역 토폴로지에서는 입자가 입자의 부분 집합과만 정보를 공유한다. 이 부분 집합은 기하학적(예: "가장 가까운 ''m''개의 입자")일 수도 있고,^[3] 거리와 상관없는 사회적 입자 집합일 수도 있다. 이러한 경우, PSO 변형은 기본 PSO의 전역 최적(global best) 대신 지역 최적(local best)이라고 한다.

일반적으로 사용되는 군집 토폴로지는 링(각 입자는 두 개의 이웃만 가짐)이지만, 다른 많은 토폴로지도 존재한다. 토폴로지는 반드시 정적일 필요는 없으며, 입자의 통신 다양성과 관련이 있으므로, 적응형 토폴로지(SPSO,^[4] APSO,^[5] 확률적 별(stochastic star),^[6] TRIBES,^[7] Cyber Swarm,^[8] C-PSO)를 생성하기 위한 노력이 이루어졌다.

링 토폴로지를 사용하면 PSO는 세대 수준의 병렬 처리를 달성하여 진화 속도를 크게 향상시킬 수 있다.^[9]

5. 내부 작동 원리

기본적인 입자 군집 최적화(PSO, Particle Swarm Optimization) 알고리즘은 여러 후보 해(입자) 집합(무리)을 이용하여 작동한다.^[1] 이 입자들은 탐색 공간에서 간단한 수식에 따라 이동하며, 각 입자의 이동은 자신이 찾은 최적 위치와 무리 전체가 찾은 최적 위치에 영향을 받는다. 더 나은 위치가 발견되면 무리 전체의 이동 방향을 조정한다. 이 과정을 반복하여 만족스러운 해를 찾기를 기대하지만, 항상 보장되는 것은 아니다.

최소화해야 할 비용 함수 ''f'': ℝ^''n'' → ℝ에서, 이 함수는 실수 벡터 형태의 후보 해를 입력받아 해당 후보 해의 목적 함수 값을 실수로 출력한다. ''f''의 기울기는 알 수 없다. 목표는 탐색 공간의 모든 '''b'''에 대해 ''f''('''a''') ≤ ''f''('''b''')인 해 '''a'''를 찾는 것이다. ('''a'''는 전역 최솟값)

각 입자는 탐색 공간에서 위치 '''x'''_i ∈ ℝ^''n''와 속도 '''v'''_i ∈ ℝ^''n''을 갖는다. '''p'''_i는 입자 ''i''의 알려진 최적 위치, '''g'''는 전체 무리의 알려진 최적 위치이다. 비용 함수를 최소화하기 위한 기본적인 PSO 알고리즘은 다음과 같다.

1. 각 입자 ''i'' = 1, ..., ''S'' (''S''는 무리의 입자 수)에 대해:

• 입자의 위치를 균일하게 분포된 난수 벡터로 초기화: '''x'''_i ~ ''U''('''b_lo''', '''b_up''')
• 입자의 알려진 최적 위치를 초기 위치로 초기화: '''p'''_i ← '''x'''_i
• 만약 ''f''('''p'''_i) < ''f''('''g''')이면, 무리의 알려진 최적 위치 업데이트: '''g''' ← '''p'''_i
• 입자의 속도를 초기화: '''v'''_i ~ ''U''(-|'''b_up'''-'''b_lo'''|, |'''b_up'''-'''b_lo'''|)

• 각 입자 ''i'' = 1, ..., ''S''에 대해:
• 각 차원 ''d'' = 1, ..., ''n''에 대해:
• 난수 선택: ''r''_p, ''r''_g ~ ''U''(0,1)
• 입자의 속도 업데이트: '''v'''_i,d ← w '''v'''_i,d + φ_p ''r''_p ('''p'''_i,d-'''x'''_i,d) + φ_g ''r''_g ('''g'''_d-'''x'''_i,d)
• 입자의 위치 업데이트: '''x'''_i ← '''x'''_i + '''v'''_i
• 만약 ''f''('''x'''_i) < ''f''('''p'''_i)이면, 입자의 알려진 최적 위치 업데이트: '''p'''_i ← '''x'''_i
• 만약 ''f''('''p'''_i) < ''f''('''g''')이면, 무리의 알려진 최적 위치 업데이트: '''g''' ← '''p'''_i

5. 1. 수렴

• 해의 수열의 수렴 (안정성 분석, 수렴이라고도 함): 모든 입자가 탐색 공간의 한 점으로 수렴하는 경우를 말하며, 이 점이 최적점인지 아닌지는 상관없다.
• 극소점으로의 수렴: 모든 개인 최적값 '''p''' 또는 군집의 최고 위치 '''g'''가 문제의 극소점에 접근하는 경우를 말한다.

6. 적응 메커니즘

수렴('착취')과 발산('탐색') 사이의 절충 없이 적응 메커니즘을 도입할 수 있다. 적응형 입자 군집 최적화(APSO)는 표준 PSO보다 더 나은 탐색 효율을 제공한다. APSO는 더 높은 수렴 속도로 전체 탐색 공간에 대해 전역 탐색을 수행할 수 있다. 실행 시간에 관성 가중치, 가속 계수 및 기타 알고리즘 매개변수를 자동으로 제어하여 탐색 효과와 효율을 동시에 향상시킨다. 또한, APSO는 전역 최적 입자에 작용하여 가능성이 높은 지역 최적점에서 벗어날 수 있다. 그러나 APSO는 새로운 알고리즘 매개변수를 도입하지만, 추가적인 설계 또는 구현 복잡성은 도입하지 않는다.

7. 변형

기본 PSO 알고리즘에는 다양한 변형이 가능하다. 예를 들어 입자와 속도를 초기화하는 방법(예: 0의 속도로 시작), 속도를 감쇠하는 방법, 전체 무리가 업데이트된 후에만 '''p'''_i와 '''g'''를 업데이트하는 방법 등이 있으며, 이러한 선택과 성능에 미치는 영향은 문헌에서 논의되었다.

주요 연구자들은 일련의 표준 구현을 만들어, 기법 개선의 성능 테스트를 위한 기준 및 광범위한 최적화 커뮤니티에 PSO를 제시하고자 하였다. 잘 알려진 엄격하게 정의된 표준 알고리즘을 사용하면 연구 전반에 걸쳐 새로운 발전을 더 잘 테스트하는 데 사용할 수 있는 귀중한 비교 기준을 제공한다. 최신 버전은 Standard PSO 2011 (SPSO-2011)이다.

7. 1. 하이브리드화

7. 2. 조기 수렴 완화

• 입자 이동 역전 또는 방해: PSO 입자의 이동을 역전시키거나 방해한다.
• 다중 군집 사용: 다중 군집을 사용한다.^[14] 이 방법은 다중 군집 최적화에도 활용된다.
• 행동 매개변수 적응: 최적화 과정에서 PSO의 행동 매개변수를 적응시킨다.

7. 3. 단순화

8. 다목적 최적화

입자 군집 최적화(PSO)는 다목적 문제(여러 목적 함수를 동시에 최적화)에도 적용될 수 있다.

9. 이산 및 조합 최적화

PSO는 실수 기반 알고리즘이지만, 이산 및 조합 문제를 해결하기 위한 변형도 연구되고 있다. 기본적인 PSO 알고리즘은 실수를 사용하므로, 이산 문제를 풀기 위해서는 이산 탐색 공간을 연속 영역에 매핑하고, 고전적인 PSO를 적용한 후, 결과를 다시 역매핑하는 방법이 일반적으로 사용된다.^[18] 예를 들어, 반올림된 값을 사용하는 간단한 매핑이 가능하다.

하지만, PSO의 이동 방정식은 다음 네 가지 연산을 포함한다:^{[19][20][21][22]}

• 두 위치의 차이 계산 (결과는 속도, 더 정확하게는 변위)
• 속도에 숫자 계수 곱셈
• 두 속도의 덧셈
• 위치에 속도 적용

참조

_[1] 논문 A Comprehensive Survey on Particle Swarm Optimization Algorithm and Its Applications http://www.hindawi.c[...] 2015
_[2] 논문 Population Topologies and Their Influence in Particle Swarm Performance https://pdfs.semanti[...] Universidade do Minho 2004
_[3] 논문 Particle swarm optimiser with neighbourhood operator https://ieeexplore.i[...] IEEE 1999
_[4] 웹사이트 Particle Swarm Central http://www.particles[...]
_[5] 논문 A parsimonious SVM model selection criterion for classification of real-world data sets via an adaptive population-based algorithm https://link.springe[...] 2017
_[6] 논문 Stochastic Star Communication Topology in Evolutionary Particle Swarms (EPSO) https://repositorio.[...] 2008
_[7] 서적 Particle Swarm Optimization ISTE (International Scientific and Technical Encyclopedia) 2006
_[8] 논문 A Complementary Cyber Swarm Algorithm http://leeds-faculty[...] 2011
_[9] 논문 Generation-Level Parallelism for Evolutionary Computation: A Pipeline-Based Parallel Particle Swarm Optimization https://ieeexplore.i[...] 2021
_[10] 서적 Swarm Intelligence 2014
_[11] 논문 A convergence proof for the particle swarm optimizer https://repository.u[...]
_[12] 논문 Scale adaptive fitness evaluation-based particle swarm optimisation for hyperparameter and architecture optimisation in neural networks and deep learning 2023-09-00
_[13] 논문 Pathological Brain Detection in Magnetic Resonance Imaging Scanning by Wavelet Entropy and Hybridization of Biogeography-based Optimization and Particle Swarm Optimization 2015
_[14] 논문 OptiFel: A Convergent Heterogeneous Particle Sarm Optimization Algorithm for Takagi-Sugeno Fuzzy Modeling 2013
_[15] 서적 Proceedings of the 2003 IEEE Swarm Intelligence Symposium. SIS'03 (Cat. No.03EX706) 2003
_[16] 논문 Accelerated particle swarm optimization and support vector machine for business optimization and applications https://arxiv.org/ab[...] 2011
_[17] 웹사이트 Search Results: APSO - File Exchange - MATLAB Central http://www.mathworks[...]
_[18] 논문 A Novel Particle Swarm Optimization Algorithm for Multi-Objective Combinatorial Optimization Problem http://sclab.yonsei.[...] 2012
_[19] 논문 A discrete binary version of the particle swarm algorithm http://ahmetcevahirc[...] IEEE Service Center 1997
_[20] 서적 Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem https://link.springe[...] Springer 2004
_[21] 논문 Binary Particle Swarm Optimisers: toolbox, derivations, and mathematical insights http://hal.archives-[...]
_[22] 논문 A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems 2008