PSO(Particle Swarm Optimization)는 군집(swarm)을 구성하는 단순한 개체들인 입자(particle)들이 각자의 경험을 공유하여 문제의 해답을 찾는 최적화 알고리즘으로 다양한 분야에서 응용되고 있다. PSO에 대한 연구는 최적화를 위해 군집이 적합한 영역으로 빠르게 수렴하도록 하는 파라미터 값의 선정, 토폴로지, 입자의 이동에서 주로 이루어지고 있다. 표준 PSO 알고리즘은 입자 자신과 최고의 이웃이 제공하는 정보만을 이용해서 이동하므로 다양한 영역을 탐색하지 못하고 지역적 최적점에 조기 수렴하는 경향이 있다. 본 논문에서는 군집이 다양한 영역을 탐색하기 위해, 각 입자는 더 나은 경험을 가진 이웃입자들의 정보를 상대적인 중요도에 따라서 참조하여 이동하도록 하였다. 다양한 영역의 탐색은 표준 PSO 알고리즘보다 지역적 최적화의 확률을 줄이고 탐색 속도를 가속화하며 탐색의 성공률을 높일 수 있다. 또한 군집이 지역적 미니멈으로부터 벗어나기 위한 검사 전략을 제안하여 탐색의 성공률을 높였다. 제안한 PSO 알고리즘을 평가하기 위하여, 벤치마크 함수들에 적용한 결과 최적화의 진행 속도 개선과 탐색 성공률의 향상이 있었다.
PSO(Particle Swarm Optimization)는 군집(swarm)을 구성하는 단순한 개체들인 입자(particle)들이 각자의 경험을 공유하여 문제의 해답을 찾는 최적화 알고리즘으로 다양한 분야에서 응용되고 있다. PSO에 대한 연구는 최적화를 위해 군집이 적합한 영역으로 빠르게 수렴하도록 하는 파라미터 값의 선정, 토폴로지, 입자의 이동에서 주로 이루어지고 있다. 표준 PSO 알고리즘은 입자 자신과 최고의 이웃이 제공하는 정보만을 이용해서 이동하므로 다양한 영역을 탐색하지 못하고 지역적 최적점에 조기 수렴하는 경향이 있다. 본 논문에서는 군집이 다양한 영역을 탐색하기 위해, 각 입자는 더 나은 경험을 가진 이웃입자들의 정보를 상대적인 중요도에 따라서 참조하여 이동하도록 하였다. 다양한 영역의 탐색은 표준 PSO 알고리즘보다 지역적 최적화의 확률을 줄이고 탐색 속도를 가속화하며 탐색의 성공률을 높일 수 있다. 또한 군집이 지역적 미니멈으로부터 벗어나기 위한 검사 전략을 제안하여 탐색의 성공률을 높였다. 제안한 PSO 알고리즘을 평가하기 위하여, 벤치마크 함수들에 적용한 결과 최적화의 진행 속도 개선과 탐색 성공률의 향상이 있었다.
PSO(Particle Swarm Optimization) is an optimization algorithm in which simple particles search an optimal solution using shared information acquired through their own experiences. PSO applications are so numerous and diverse. Lots of researches have been made mainly on the parameter settings, topolo...
PSO(Particle Swarm Optimization) is an optimization algorithm in which simple particles search an optimal solution using shared information acquired through their own experiences. PSO applications are so numerous and diverse. Lots of researches have been made mainly on the parameter settings, topology, particle's movement in order to achieve fast convergence to proper regions of search space for optimization. In standard PSO, since each particle uses only information of its and best neighbor, swarm does not explore diverse regions and intended to premature to local optima. In this paper, we propose a new particle's movement strategy in order to explore diverse regions of search space. The strategy is that each particle moves according to relative weights of several better neighbors. The strategy of exploring diverse regions is effective and produces less local optimizations and accelerating of the optimization speed and higher success rates than standard PSO. Also, in order to raise success rates, we propose a strategy for checking whether swarm falls into local optimum. The new PSO algorithm with these two strategies shows the improvement in the search speed and success rate in the test of benchmark functions.
PSO(Particle Swarm Optimization) is an optimization algorithm in which simple particles search an optimal solution using shared information acquired through their own experiences. PSO applications are so numerous and diverse. Lots of researches have been made mainly on the parameter settings, topology, particle's movement in order to achieve fast convergence to proper regions of search space for optimization. In standard PSO, since each particle uses only information of its and best neighbor, swarm does not explore diverse regions and intended to premature to local optima. In this paper, we propose a new particle's movement strategy in order to explore diverse regions of search space. The strategy is that each particle moves according to relative weights of several better neighbors. The strategy of exploring diverse regions is effective and produces less local optimizations and accelerating of the optimization speed and higher success rates than standard PSO. Also, in order to raise success rates, we propose a strategy for checking whether swarm falls into local optimum. The new PSO algorithm with these two strategies shows the improvement in the search speed and success rate in the test of benchmark functions.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 PSO 알고리즘의 최적화 속도와 탐색 성공률을 개선하기 위한 두 전략을 제안한다. 첫번째 전략은 입자가 속도 업데이트시에 이웃들의 경험을 상대적 가중치 에 따라 받아들여 상태공간의 다양한 영역을 탐색하기 위한 것이다.
본 논문에서는 PSO의 최적화 과정의 탐색 속도를 개선 하고 전역적 미니멈(global minimum)을 찾는데 있어 성공률을 향상시키기 위해 다수의 이웃 입자들과의 상대적 가중치를 이용한 정보 공유 방법과 지역적 미니멈(local minimum) 의 검사에 대한 두 전략을 제안한다. 제안 PSO는 입자 이 동시에 입자 자신과 자신보다 좋은 경험을 한 여러 이웃 입자들의 정보를 확률적으로 받아들이므로 다양한 지역의 탐색으로 전역적 미니멈을 찾을 수 있다.
본 논문에서는 표준 PSO 알고리즘의 최적화 속도 개선과 성공률 향상을 위한 두 전략을 제안하였다. 제안한 알고 리즘은 입자가 자신보다 적합치가 낮은 다수의 이웃들의 정보를 공유하고 이웃들의 상대적 중요도를 바탕으로 정보를 받아들여 이동을 하므로 적합치가 가장 낮은 이웃을 향해 직접적으로 이동을 하지 않고 보다 넓게 탐색을 하게 된다.
제안 방법
향후에는 탐색 초기에는 다수의 이웃들의 정보를 받아들여 다양한 공간을 탐험하도록 하고 점차 입자 자신과 군집 의 최적 정보의 중요도를 높이기 위한 관성 가중치(inertia weight)와 가속 계수의 조정에 대하여 연구할 계획이다. 또 한 제안 PSO 알고리즘과 신경망 알고리즘의 비교를 하겠다. 향후 연구를 통해, 군집이 전역 미니멈에 가까워질수록 탐색 속도의 가속화를 얻을 수 있으리라 기대한다.
제안한 알고 리즘은 입자가 자신보다 적합치가 낮은 다수의 이웃들의 정보를 공유하고 이웃들의 상대적 중요도를 바탕으로 정보를 받아들여 이동을 하므로 적합치가 가장 낮은 이웃을 향해 직접적으로 이동을 하지 않고 보다 넓게 탐색을 하게 된다. 또한 제안한 알고리즘에서는 최적화의 진행 상태를 의미하는 수치인 군집의 너비를 이용하여 군집이 지역적 미니멈에 서 빠져 나오지 못하는 상황인가를 검사하는 전략을 사용하 였다. 이 두 전략을 다양한 척도 함수에 적용한 실험 결과, 표준 알고리즘에 비하여 적은 수의 이동을 통해서 성공률이 빠르게 증가함을 알 수 있었다.
또한 제안 PSO는 지역적 미니멈을 검사하고 군집을 초기화하는 전략을 통해 탐색 속도와 성공률의 향상을 얻을 수 있다. 본 논문에서는 다양한 벤치마크 함수들[7,8]을 이용하여 제안 PSO와 표준 PSO 알고리즘(standard PSO)[6]을 비교하였다. 실험 결과에서 제안 PSO알고리즘이 표준 PSO알고리즘에 비하여 탐색 속도와 성공률에 큰 향상이 있었다.
본 실험에서는 군집의 크기(swarm size)와 이웃 입자의 수는 각각 12와 3으로 정하였다. (식 6)에서의 가속 계수 φ1, φ2는 표준 PSO와 같이 0.
제안 알고리즘은 (step 2)～(step 3)의 지역적 미니멈 검사에서 검사척도로서 (error) 또는 임의로 선택된 입자와 의 거리# (diff)를 사용하였다.
그러므로 제안 알고리즘은 표준 PSO 알고리즘에 비하여 평가 횟수가 작다. 제안 알고리즘은 상대적 가중치 계산과 지역적 미니멈 검사의 추가로 평가횟수당 소모시간은 증가하지만 평가횟수가 감소하므로 알고리즘 실행시간 또한 표준 PSO 알고리즘과 비교하여 작다. <표 2>는 표준 PSO알고리즘과 제안 알고리즘이 전역적 미니멈을 발견하기까지의 실행시간과 평가횟수를 비교한 표이다.
본 논문에서는 표준 PSO 알고리즘의 최적화 속도 개선과 성공률 향상을 위한 두 전략을 제안하였다. 제안한 알고 리즘은 입자가 자신보다 적합치가 낮은 다수의 이웃들의 정보를 공유하고 이웃들의 상대적 중요도를 바탕으로 정보를 받아들여 이동을 하므로 적합치가 가장 낮은 이웃을 향해 직접적으로 이동을 하지 않고 보다 넓게 탐색을 하게 된다. 또한 제안한 알고리즘에서는 최적화의 진행 상태를 의미하는 수치인 군집의 너비를 이용하여 군집이 지역적 미니멈에 서 빠져 나오지 못하는 상황인가를 검사하는 전략을 사용하 였다.
결국 군집은 지역적 미니멈에 빠질 수 있다. 제안한 전략은 이동하려는 입자 i가 자신보다 적합치가 낮은 이웃 입자들의 탐색 정보를 모두 취합하는데, 각 이웃 입자의 적합치에 따른 상대적 가중치에 비례하여 받아들인다. 입자 i에 대한 이웃 입자 j의 상대적 가중치(relative weight, rwij)는 (식 5)와 같이 구한다.
데이터처리
본 실험에서 알고리즘의 탐색 속도 향상은 평가횟수를 이용하여 평가한다. 평가횟수는 군집의 입자들이 적합치 함수 (fitness)를 평가한 총 횟수로서 입자들이 최적해를 찾기 위해 탐색 공간을 이동한 횟수를 의미한다.
실험에서 군집의 크기는 12이고 이웃 입자의 개수는 3으로 정하였다. <표 2>의 실험 결과를 바탕으로 제안 알고리즘의 탐색 속도 향상의 평가 척도로서 평가 횟수를 사용한다.
이론/모형
본 실험에서는 제안한 PSO 알고리즘의 성능을 평가하기 위해 (그림 2)와 의 벤치마크 함수인 Ackley 함수, Easom 2D 함수, Rastrigin 함수 Rosenbrock(Banana) 함수 및 Tripod 함수[5]를 이용하여 전역적 미니멈을 찾는 문제에 적용하였다[7,8].
05로 하였다. 위의 군집의 크기, 이웃 입자의 수, 가속 계수의 수치는 실험 결과와 파라미터 수축방법(constriction method)[3-5]을 바탕으로 정하였다.
첫번째 전략은 입자가 속도 업데이트시에 이웃들의 경험을 상대적 가중치 에 따라 받아들여 상태공간의 다양한 영역을 탐색하기 위한 것이다. 표준 PSO 알고리즘(standard PSO 2006)[1,3,6]은 (식 1)과 (식 2)와 같이 이웃 입자 중에서 가장 낮은 적합치 (fitness value)를 가진 입자 lbest 의 경험(#)을 이용했다. 표준 알고리즘에서는 이동하려는 입자 i가 지역적 미니멈에 가깝게 놓인 입자로부터 직접적으로 영향을 받으므로[3], 입자 i를 이웃으로 갖는 다른 입자들도 지역적 미니멈에 가까이 이동할 가능성이 높아진다.
성능/효과
두 검사 척도에 대한 비교 실험에서, 멀티모달 함수인 Rastrigin 함수와 Tripod 함수는 두 척도에 대하여 비슷한 평가 횟수와 성공률(95%이상)을 보였고, Ackley, Easom 2D, Rosenbrock 함수는 #의 적합치(error)가 더 나은 결과를 보였다.
제안 PSO는 입자 이 동시에 입자 자신과 자신보다 좋은 경험을 한 여러 이웃 입자들의 정보를 확률적으로 받아들이므로 다양한 지역의 탐색으로 전역적 미니멈을 찾을 수 있다. 또한 제안 PSO는 지역적 미니멈을 검사하고 군집을 초기화하는 전략을 통해 탐색 속도와 성공률의 향상을 얻을 수 있다. 본 논문에서는 다양한 벤치마크 함수들[7,8]을 이용하여 제안 PSO와 표준 PSO 알고리즘(standard PSO)[6]을 비교하였다.
이 결과는 표준 알고리즘에 비하여 적은 수의 이동으로 전역적 미니멈에 도달하였음을 의미한다. 본 실험에서, Rastrigin함 수는 평가 횟수와 성공률을 높이기 위해 다른 함수와는 달 리 (식 6)의 가속 계수 1, 2를 차례로 2.0, 2.1로 정하여서 이동 방향과 이동거리에 임의성을 크게 주었다.
본 논문에서는 다양한 벤치마크 함수들[7,8]을 이용하여 제안 PSO와 표준 PSO 알고리즘(standard PSO)[6]을 비교하였다. 실험 결과에서 제안 PSO알고리즘이 표준 PSO알고리즘에 비하여 탐색 속도와 성공률에 큰 향상이 있었다. 본 논문의 구성은 다음과 같다.
(그림 6)은 10차원 Ackley함수와 10차원 Rosenbrock 함수를 제안 PSO 알고리즘에 적용한 실험 결과이다. 실험에서 두 함수 모두 탐색 초기부터 적은 횟수의 이동으로 성공적으로 전역적 미니멈을 발견하는 것을 보였다. 10차원 Ackley 함수의 탐색 공간은 광대하고 많은 지역적 미니멈이 존재하여 매우 복잡한데, 이러한 공간에서 여러 이웃들의 정보를 바탕으로 이동하면 허용 에러 이하는 만족하지만 큰 적합치를 갖는 전역적 미니멈을 발견하게 되어 그래프와 같 이 평균 에러가 크다.
또한 제안한 알고리즘에서는 최적화의 진행 상태를 의미하는 수치인 군집의 너비를 이용하여 군집이 지역적 미니멈에 서 빠져 나오지 못하는 상황인가를 검사하는 전략을 사용하 였다. 이 두 전략을 다양한 척도 함수에 적용한 실험 결과, 표준 알고리즘에 비하여 적은 수의 이동을 통해서 성공률이 빠르게 증가함을 알 수 있었다.
표준 알고리즘은 이웃들 중에서 최소 적합치를 가진 이웃의 정보 #만을 참조해서 직 접적으로 최소 적합치를 가진 이웃을 향해 이동하므로 탐색 초기부터 적합치 즉 에러가 크게 감소할 수 있지만 점차 부 분적인 지역 탐색을 하므로 에러의 감소가 둔화된다. 이에 반해, 제안한 PSO알고리즘은 적합치가 낮은 다수의 이웃들 의 정보를 바탕으로 이동을 하므로 최소 적합치의 이웃에 간접적으로 이동을 하게 되어 탐색 중반까지는 에러가 크지만, 보다 넓은 탐색 공간을 탐색하여 적합치가 낮은 곳을 찾게 되므로 점차 에러는 감소하게 된다.
평가횟수는 군집의 입자들이 적합치 함수 (fitness)를 평가한 총 횟수로서 입자들이 최적해를 찾기 위해 탐색 공간을 이동한 횟수를 의미한다. 제안 알고리즘은 입자들이 적합치가 낮은 영역뿐만 아니라 보다 넓은 영역을 탐색하므로 지역적 미니멈에 빠질 확률을 줄이고, 지역적 미니멈에 빠졌어도 제안한 두번째 전략에 의해 지역적 미니멈에 계속해서 머무르지 않고 다른 곳을 탐색할 수 있다. 그러므로 제안 알고리즘은 표준 PSO 알고리즘에 비하여 평가 횟수가 작다.
평가 횟수는 군집의 입자들이 전역적 미니멈을 찾기 위해 이동한 횟수로 알고리즘의 탐색 속도를 평가하는 척도로 사용된다. 제안한 PSO알고리즘은 Rastrigin 함수를 제외한 Ackley, Easom 2D, Rosenbrock, Tripod 함수의 실험에서 표준 PSO와 비교하여 평균 평가 횟수가 감소하였다. 이 결과는 표준 알고리즘에 비하여 적은 수의 이동으로 전역적 미니멈에 도달하였음을 의미한다.
후속연구
군집이 지역적 미니멈에 빠지게 되면 이후 이동을 해도 지역적 미니멈 주위를 맴돌며 군집의 크기는 계속해서 수축 하게 된다. 본 논문에서는 군집이 매우 수축되어 있지만 계 속해서 전역적 최적점을 찾지 못한다면 지역적 미니멈에 빠졌다고 판단한다. 그리고 군집의 수축 상태를 의미하는 수치로서 군집의 현재 최저 적합치(error, #)와 군집에 서 임의로 선택한 입자와 군집의 전역적 최적점(#)사이의 거리(diff)를 이용한다.
또 한 제안 PSO 알고리즘과 신경망 알고리즘의 비교를 하겠다. 향후 연구를 통해, 군집이 전역 미니멈에 가까워질수록 탐색 속도의 가속화를 얻을 수 있으리라 기대한다.
향후에는 탐색 초기에는 다수의 이웃들의 정보를 받아들여 다양한 공간을 탐험하도록 하고 점차 입자 자신과 군집 의 최적 정보의 중요도를 높이기 위한 관성 가중치(inertia weight)와 가속 계수의 조정에 대하여 연구할 계획이다. 또 한 제안 PSO 알고리즘과 신경망 알고리즘의 비교를 하겠다.
질의응답
핵심어
질문
논문에서 추출한 답변
PSO 알고리즘은 어떤 알고리즘으로, 목표는 무엇인가요?
PSO 알고리즘은 1995년에 사회 심리학자 Kennedy와 전기 기술자 Eberhart에 의하여 제안된 최적화 알고리즘[1]으로 사회적 상호작용을 통하여 계산적인 지능(computational intelligence)을 만드는 것이 목표이다. PSO 알고리즘이 처음 소개된 이후 표준 알고리즘에 많은 변화와 성능향상이 있었고 이미지/비디오 분석, 제어 문제, 스케쥴링, 통신망 디자인 및 최적화, 데이터 마이닝, 예측, 오류의 진단과 복구, 센서 네트워크, 게임과 같은 다양한 분야에서 응용되고 있다[2].
PSO 알고리즘이 처음 소개된 이후 무엇의 향상과 어떤 분야에서 응용되고 있나요?
PSO 알고리즘은 1995년에 사회 심리학자 Kennedy와 전기 기술자 Eberhart에 의하여 제안된 최적화 알고리즘[1]으로 사회적 상호작용을 통하여 계산적인 지능(computational intelligence)을 만드는 것이 목표이다. PSO 알고리즘이 처음 소개된 이후 표준 알고리즘에 많은 변화와 성능향상이 있었고 이미지/비디오 분석, 제어 문제, 스케쥴링, 통신망 디자인 및 최적화, 데이터 마이닝, 예측, 오류의 진단과 복구, 센서 네트워크, 게임과 같은 다양한 분야에서 응용되고 있다[2]. PSO 알고리즘에 대한 주요 연구는 최적화 성능에 영향을 미치는 파라미터, 토폴로지, 입자의 이동 등에 관한 것이다[3].
표준 PSO 알고리즘은 항상 좋은 성과를 얻지 못하고 있는 이유는 무엇인가요?
표준 PSO 알고리즘은 lbest를 통해 지역적 최적화의 확률을 낮추고 있지만, 복잡한 문제에 적 용하여 항상 좋은 성과를 얻지 못한다. 그 이유는 lbest도 입자 자신과 최고 이웃으로부터만 영향을 받으므로 최고 이웃이 지역적 최적점이라면 자신과 이웃들은 빠르게 최고 이웃으로 접근하고, 새롭게 이웃을 선정하면 다른 입자들도 영향을 받아 지역적 최적점 주위로 모이게 된다. 이러한 이동이 계속되면 군집은 지역적 최적점에 빠져서 탐색 시간이 증가하고 탐색 성공률이 낮아진다. PSO 알고리즘은 이러한 상황을 발견하고 수축되어 있는 군집이 다른 지역을 탐색할 수 있도록 팽창시켜야 한다.
참고문헌 (8)
Kennedy J, Eberhart R.C., 'Particle Swarm Optimization', Proceedings of IEEE International Conference on Neural Networks, p.1942-1948, 1995
Shi Y.H, Eberhart R.C., 'A Modified Particle Swarm Optimizer', Proceedings of IEEE International Conference on Evolutionary Computation, 1998
Riccardo Poli, James Kennedy, Tim Blackwell, "Particle swarm optimization: An overview", Swarm Intell(2007) 1:p.33-57 DOI 10.1007/s11721-007-0002-0
ZHANG Li-ping, YU Huan-jun, HU Shang-xu, 'Optimal choice of parameters for particle swarm optimization', Journal of Zhejiang University SCIENCE ISSN 1009-3095, 2005
Clerc M, Kennedy J, 'The particle swarm explosion, stability and convergence in a multidimensional complex space', IEEE transaction on Evaolutionary Computation, 6(1):p.58-73, 2002
※ AI-Helper는 부적절한 답변을 할 수 있습니다.