References
[1] X. S. Yang, “Firefly algorithms for multimodal optimization,” in Stochastic Algorithms: Foundations and Applications (SAGA 2009), Lecture Notes in Computer Sciences, vol. 5792, 2009, 169-178, 2009.
요약
자연에서 영감 받은 알고리즘이 가장 강력하다. 여기서는 복합 최적화 문제에 사용할 수 있는 반딧불 알고리즘 (Firefly Algorithm (FA)) 에 대해서 설명한다. 제안된 반딧불 알고리즘을 입자 떼 최적화 알고리즘(particle swarm optimization (PSO))과 같은 다른 메타휴리스틱 알고리즘과 비교해볼것이다. 모의실험 결과는 제안된 반딧불 알고리즘이 기존 메타휴리스틱 알고리즘보다 우월함을 나타낸다.
1 서론¶
생물에서 영감 받은 알고리즘이 수치적 최적화에 좋은 성능을 보이고 있다. 특히 영업사원 방문 문제(travelling salesman problem)와 같은 NP-hard 문제에 탁월하다. 생물학에서 유래한 이런 알고리즘 중에서, 입자 떼 최적화와 같은 다자 메타휴리스틱 알고리즘(multi-agent metaheuristic algorithms)이 학계에서 최신 최적화 알고리즘 개발 연구주제로 관심을 받고 있다. 입자 떼 최적화 (particle swarm optimization (PSO)) 는 Kennedy and Eberhart 에 의해서 1995 년에 개발되었다. 이것은 자연계의 물고기, 새 등의 군집 행동에 기반했다. 이것을 떼 지능(swarm intelligence)이라고 부른다. 입자 떼 최적화는 유전자 알고리즘과 유사하지만, 더 간단하다. 이유는, 돌연변이/혼합교차(mutation/crossover) 를 쓰지 않기 때문이다. 대신에, 이것은 실수(real-number) 무작위와 군집을 이루는 입자간의 전역 의사소통을 사용한다. 이런 면에서, 이것은 구현하기가 수월하다. 주로 실수(real-number)를 사용하기 때문이다. 여기서는 새로운 반딧불 알고리즘(Firefly Algorithm (FA)) 을 소개한다. 그리고 FA 와 PSO 그리고 비슷한 알고리즘을 비교한 결과를 제시한다. 먼저 입자 떼 알고리즘을 간략히 설명하고, 반딧불 알고리즘의 수학식을 개발하고 마지막으로 이 알고리즘들의 수행성능을 비교한다. FA 가 복합 함수를 더 자연스럽고 효율적으로 처리할수 있다는 측면에서, FA 최적화는 입자 떼 최적화보다 더 나아보인다. 또한, 입자 떼 최적화는 단지 반딧불 알고리즘의 특별한 형태라는 사실을 후반부에 설명할것이다.
PSO 알고리즘은 개별 입자의 궤적을 조절하는 방식으로 목표 함수 공간을 탐색한다. 개별 입자의 경로는 준-확률적 형태(quasi-stochastic manner)인 위치벡터로 구성되어있다. 현재 20개의 PSO 변종이 존재한다. 여기서는 가장 간단하지만 인기있는 표준 PSO 를 설명한다. 입자 운동은 두개의 주 성분을 가진다: 확률적 성분과 결정론적 성분이다. 입자는 현재 전역 최적값 ${g^*}$ 과 자신의 역사상 최적값 ${{x_i}^*}$ 방향으로 끌려 이동한다. 그와 동시에 입자는 무작위로 이동하는 성질을 가진다. 입자가 이전에 발견된 위치보다 더 좋은 위치를 발견하면, 입자는 그 위치를 입자 ${i}$ 의 새로운 현재 최적값으로 갱신한다. 모든 ${n}$ 입자에 대한 현재 전역 최적값이 있다. 목표는 현재 지역 최적값들 중에서 전역 최적값을 찾는것이다. 목표가 더이상 개선되지 않거나 지정된 횟수만큼 반복했으면 탐색을 중지한다. 입자 움직임에대해서, ${{x_i}^*}$ 는 입자 ${i}$ 의 현재 최적값을 나타낸다. 그리고, ${g^*}≈$ min or max{ ${f (x_i )}$ }(${i = 1, 2, ..., n}$) 이것은 현재 전역 최적값을 나타낸다. ${x_i}$ 와 ${v_i}$ 를 각각 입자 ${i}$ 의 위치 벡터와 속도라 하자. 새 속도 벡터는 다음 수식으로 결정된다.
여기서 $ε_1$와 $ε_2$는 두 무작위 벡터, 0 과 1 사이의 값을 가진다. 두 행렬에서 Hadamard product ${ \mathbf u ⊙ \mathbf v }$ 는 항목별 곱으로 정의된다. 즉, 다음과 같다. $[\mathbf u ⊙ \mathbf v]_{ij} = u_{ij}v_{ij}$. 인자 $\alpha$ 와 $\beta$ 는 학습 인자 또는 가속 상수이다. 이것들은 임의로 ${\alpha ≈ \beta ≈ 2 }$ 정도의 값을 지정할 수 있다. ${\mathbf x_i^{t=0}}$ 의 초기값은 경계값을 주거나 또는 한정값 ${ a = min(x_j), b = max(x_j)}$ 그리고 ${\mathbf x_i^{t=0} = 0}$ 을 줄수있다. 새로운 위치는 다음 식으로 갱신된다.
비록 ${\mathbf v_i}$ 는 어떤 값이라도 되지만, 보통은 어떤 범위 ${[0, \mathbf v_{max}]}$ 로 제한한다. 표준 PSO 알고리즘의 기능을 확장한 변종 알고리즘이 많이 존재한다. 그리고 가장 눈에 띄는 개선은 아마도 관성 함수 ${ \theta (t) }$ 를 사용하는것일 것이다. 여기서, ${ \mathbf x_i^t }$ 가 ${ \theta (t) \mathbf x_i^t }$ 로 교체되고 $\theta$ 는 0 과 1 사이의 값을 가진다. 단순한 경우, 관성함수는 상수로 취급할수있고, 일반적으로 ${\theta ≈ 0.5 ∼ 0.9}$ 범위의 값을 가진다. 이것은 가상적인 질량을 부여한것과 동일하다. 그 결과 입자의 운동이 안정되고, 알고리즘의 수렴 속도가 빨라질것으로 예상된다.
열대지방과 온대지방에서, 여름 하늘에 수많은 반딧불이 반짝이는 광경은 환상적이다. 반딧불은 약 이천개의 종이 존재한다. 그리고 대부분의 반딧불은 짧고 율동적인 빛을 발산한다. 빛을 비추는 형태는 대부분 종별로 고유한 특성을 가진다. 반짝이는 빛은 생체발광 과정을 통해 발산된다. 그리고 그런 신호전송 체계의 참 기능이 무엇인지에 대해서는 아직 토론이 진행중이다. 그러나, 그 빛 발산의 두가지 기본적인 기능은 짝짓기 대상을 끌어 당기는것(의사소통)과 잠재적 먹이를 끌어 당기는것이다. 또한 반짝이는 섬광은 아마도 위험을 경고하는 방어적 기제의 역할도 있을것으로 추측된다. 율동적 섬광, 섬광의 빈도와 신호 시스템을 구성하는 시간의 양은 양성을 모두 끌어 당긴다. 암컷은 동종 수컷의 고유한 섬광 유형에 반응한다. photuris 와 같은 어떤 종은, 암컷 반딧불이 다른 종의 짝짓기 섬광 유형을 흉내 낼수있다. 그래서 올바른 짝짓기 섬광이라고 착각한 수컷 반딧불을 가짜로 속여서 잡아먹는다.
광원으로부터 지정된 거리 $r$ 의 위치에서 광밀도는 역 제곱 법칙을 따른다는것을 우리는 알고있다. 다시말해서, 광밀도 $I$ 는 거리 $r$ 이 증가함에 따라 감소한다. ${ I ∝ 1 / {r^2} }$. 더우기, 공기가 빛을 흡수하므로, 거리가 증가할 수록 광밀도는 점점 더 약해진다. 이 두가지 요인이 결합하여 반딧불은 제한된 거리만 볼수있게된다. 보통 밤에는 몇 백 미터 정도만 볼수 있으며, 이것은 보통 반딧불이 의사소통하는데 충분한 거리다. 섬광빛은 최적화 할 목표함수에 관련되어 있는것으로 수식화 할 수 있다. 그러면 새 최적화 알고리즘을 수식화 하는것이 가능하다. 이 후에는, 먼저 반딧불 알고리즘의 기본 수식을 개관하고, 구현에 대해서 토론하고, 자세히 분석해 볼것이다.
이제 우리는 반딧불 섬광 특성에 대해서 어느정도 생각을 가지게 되어 이것으로 반딧불에서 영감받은 알고리즘을 개발한다. 새 반딧불 알고리즘(FA)에 대한 설명을 편리하게 하기위해, 지금부터는 다음 세가지 이상적인 규칙을 사용하기로 한다: 1) 모든 반딧불은 암수한몸(자웅동체)이다. 그래서 하나의 반딧불은 자신의 성에 상관없이 다른 반딧불에 끌어 당겨진다. 2) 유인력(誘引力)(매력, 끌어당기는 힘)은 밝기에 비례한다. 그러므로 반딧불 두마리가 있을때, 덜 밝은 놈이 더 밝은 놈 쪽으로 끌려 이동한다. 유인력은 밝기에 비례한다. 따라서 거리가 증가할 수록 유인력과 밝기는 감소한다. 자신보다 더 밝은 놈이 없을 경우, 반딧불은 무작위적으로 이동한다; 3) 반딧불의 밝기는 목표함수의 풍경에 영향을 받거나 또는 그것에의해서 결정된다. 최대값 문제에서, 밝기는 단순히 목표함수 값에 비례한다. 다른 형태의 밝기는 유전자 알고리즘의 적합 함수과 같은 방식으로 정의할 수 있다. 이 세가지 규칙에 의해서, 반딧불 알고리즘(FA) 의 기본 절차를 요약하면, 의사코드로 표현할 수 있으며 이는 Fig. 1. 에서 보는바와 같다.
반딧불 알고리즘
목표 함수 $f(x)$, ${ \quad x = (x_1,...,x_d)^T }$
반딧불의 초기 개체군을 생성한다. ${ x_i \ (i = 1,2,...,n) }$
위치 $x_i$ 에서 광밀도 $I_i$ 는 ${\ f(x_i)}$ 로 결정한다.
광 흡수 계수 $\gamma$ 를 정의한다.
${ \mathbf{while} \ \text{( t < MaxGeneration ) }}$
${ \mathbf{for} \text{ i = 1:n} \quad \quad \text{ 모든 n 반딧불에 대하여 }}$
${ \quad \mathbf{for} \text{ j = 1:i } \quad \text{ 모든 n 반딧불에 대하여 }}$
${ \quad \quad { \mathbf{if} \ (I_j > I_i), \text{ d-차원 상에서 반딧불 i 를 j 쪽으로 이동시킨다; } \mathbf{ end}\ \mathbf{ if }}}$
${ \quad \quad \quad \text{유인력은 거리} \ r \ \text {에 따라 변한다. } \text{exp}[ - \gamma r ]}$
${ \quad \quad \quad \text{새 해법을 계산하고 광밀도를 갱신한다.} }$
${ \quad \mathbf{end} \ \mathbf{ for} \ \text{j}}$
${ \mathbf{end} \ \mathbf{ for} \ \text{i}}$
${ \text{반딧불을 비교하고 현재 최적값을 발견한다.} }$
${ \mathbf{end} \ \mathbf{ while} }$
${ \text{결과를 후처리 하고 시각화한다.} }$
${ \text{Figure 1:} \text{ 반딧불 알고리즘 (FA) 의사코드 }}$
어떤 면에서, 반딧불 알고리즘과 박테리아 침략 알고리즘(BFA, bacterial foraging algorithm) 간에는 개념적 유사성이 있다. BFA 에서는, 박테리아 사이의 유인력은 일부는 자신의 적합성에 있고, 일부는 자신의 거리에 있다. 반면 FA 에서는, 유인력은 목표함수에 연결되어 있으며 거리에 비례하여 유인력이 단조롭게 감쇠한다. 그러나, FA 에서 행위자(agent, 반딧불 한마리)는 가시성을 조절할 수 있고 유인력을 다양하게 변화시킬수 있다. 그래서 이런특성으로 행위자의 이동성을 증가시키고 탐색공간을 더 효율적으로 탐사할 수 있다.
반딧불 알고리즘에서, 두가지 중요한 사항이 있다: 광밀도 변화와 유인력 공식이다. 간편하게 하기위해서, 반딧불의 유인력은 자신의 밝기에의해서 결정된다고 가정할 수 있다. 그것은 결과적으로 부호화된 목표함수에 연관되어 있다. 가장 간단한 경우 최대값 최적화 문제에서, 특정 위치 $x$ 에서 반딧불의 밝기 $I$ 는 ${ I(x)∝ f(x)}$ 로 선택될 수 있다. 그러나, 유인력 $\beta$ 는 상대적이다, 이것은 행위자의 눈으로 보아야하고 상대 반딧불에의해서 판단되어야 한다. 그러므로, 이것은 반딧불 i 와 반딧불 j 사이의 거리 ${r_{ij}}$ 에 따라 변한다. 광밀도는 광원으로부터의 거리에 따라 감소한다. 또한 빛은 매질에의해 흡수된다. 그러므로 유인력이 흡수도에 따라 변하도록 허용해야한다. 가장 간단한 형태로, 광밀도 ${I(r)}$ 은 역제곱법칙 ${ I(r) = I_s \ / \ {r^2} }$ 에 따라 변한다. 여기서 $I_s$ 는 광원에서의 광밀도이다. 주어진 매질에서 고정 광 흡수 계수 $\gamma$, 광밀도 $I$ 는 거리 $r$ 에 따라 변한다. 그것은 ${ I = I_{0}e^{-\gamma r}}$, 여기서 $I_0$ 는 원래 광밀도이다. 수식 ${I_s \ / \ {r^2} }$ 에서 ${r \ = \ 0}$ 인 경우의 특이점을 피하기위해, 역제곱법칙과 흡수개념을 합치면 다음과 같이 가우시안 식으로 근사시킬 수 있다.
어떤 때는, 느린 비율로 단조롭게 감소시키는 함수가 필요하다. 이런경우, 다음 식을 쓸 수 있다.
짧은 거리에서, 위 두개의 식은 본질적으로 같다. 이것은 ${ r \ = \ 0}$ 에 대한 급수전개
가 ${O(r^3)}$ 차 까지는 서로 같기 때문이다. 반딧불의 유인력이 인접한 반딧불에게 보이는 광밀도에 비례하기 때문에, 이제 반딧불의 유인력 $\beta$ 를 다음과 같이 정의할 수 있다.
여기서 ${\beta_0}$ 는 ${r \ = \ 0}$ 에서의 유인력이다. 대부분의 경우, 지수함수보다 ${ 1 / (1+r^2) }$ 를 계산하는것이 빠르기 때문에, 위 함수는, 필요하다면, 편리하게 ${ \beta = \frac{ \beta_0}{1+ \gamma r^2} }$ 으로 교체할 수 있다. 수식 (6) 은 특성 거리 ${\Gamma = 1 / \sqrt{\gamma}}$ 를 정의한다. 유인력은 $\beta_0$ 로부터 ${\beta_0 e^{-1}}$ 까지 범위에서 크게 변한다. 구현에서는, 유인력 함수 ${\beta(r)}$ 의 실제 모양은 단조롭게 감소하는 함수라면 아무거나 써도 좋다. 예를 들면 다음과 같이 일반화된 식이 있다.
광 흡수 계수 ${\gamma}$ 가 고정되었다면, 특성길이는 이렇게 된다. ${\Gamma = \gamma ^ {-1 / m}} \ \rightarrow 1$ ${ , \ \ \ }$ ${m \rightarrow \infty}$ 이면. 꺼꾸로, 최적화 문제에서 길이 비율 $\Gamma$ 가 주어졌을때, 인자 $\gamma$ 는 전형적인 초기값으로 사용될 수 있다. 그것은 ${\gamma = \frac{1}{\Gamma^m}}$ 이다.
각각 $x_i$ 와 $x_j$ 에 위치한 두 반딧불 $i$ 그리고 $j$ 사이의 거리는 다음과 같이 직교 거리로 표현 할 수 있다.
여기서 ${x_{i,k}}$ 는 $i$ 번째 반딧불의 다차원 공간 좌표 $x_i$ 의 $k$ 번째 차원 성분이다. 이차원(2-D)의 경우는 다음과 같다. ${r_{ij}=\sqrt{\left(x_i - x_j \right)^2 + \left(y_i - y_j \right)^2}}$.
다른 더 매력적인(더 밝은) 반딧불 $j$ 에게 끌려 이동하는 반딧불 $i$ 의 운동은 다음 식에 의해 결정된다.
여기서 두번째 항은 유인력이다. 세번째 항은 무작위이다. $\alpha$ 는 무작위 인자이다. ${ \mathtt { rand}}$ 는 [0,1] 에서 균일분포된 무작위 숫자 생성기이다. 대부분은, ${\beta_0 = 1}$ 그리고 ${\alpha \in [0,1]}$ 로 구현 한다. 또한, 무작위 항은 표준편차 ${N(0,1)}$ 이나 또는 다른 분포를 사용하여 쉽게 확장할 수 있다. 추가로, 다른 차원 상에서 배율이 심하게 변하는경우, 예를 들어 한 차원에서는 ${-10^5}$ 에서 ${10^5}$ 으로 변하고, 다른 차원에서는 -0.001 에서 0.01 로 변할때, ${\alpha}$ 를 ${\alpha S_k}$ 로 바꾸는것이 좋다. 여기서 차원 d 에서의 배율인자 ${S_k \ (k = 1,...,d)}$ 는 대상 문제의 실제 배율에 의해서 결정되어야 한다.
인자 $\gamma$ 는 이제 유인력의 변화에 의한 특성을 가진다. 그 값은 수렴속도를 결정하고, FA 알고리즘이 동작하는 방식을 결정하는데 결정적으로 중요하다. 이론적으로, ${ \gamma \in [0, \infty) }$ 이다. 그러나, 실제로는, ${ \gamma = O(1) }$ 조건을 만족하려면, 최적화되는 시스템의 특성길이 ${\Gamma}$ 에의해서 결정된다. 그러므로, 대부분의 응용문제에서는, 그 값은 0.01 에서 100 사이의 값을 가진다.
위에서 정의된 거리 $r$ 이 유클리드 거리에만 제한되지 않는다는 사실을 짚어주는 것이 의미가 있다. 해결하고 싶은 문제의 종류에 따라, n-차원 초공간에서 여러가지 다른 형태의 거리 $r$ 을 정의할 수 있다. 예를들어, 작업 계획 문제에서, $r$ 은 시간 지연이나 시간 간격으로 정의할 수 있다. 인터넷이나 사회적 망 같은 복잡한 네트워크에서, 거리 $r$ 은 지역 클러스터링 정도 와 정점의 평균 근접의 조합으로 정의할 수 있다. 사실, 최적화 문제에서 관심있는 양을 효과적으로 특성화하는 어떠한 척도라도 '거리' $r$ 로 사용될 수 있다. 전형적인 배율 $\Gamma$ 가 관심있는 최적화 문제의 배율과 연관되어야 한다. 만약 $\Gamma$ 가 주어진 최적화 문제의 전형적인 배율이고, m 이 지역 최적값의 숫자일때, 반딧불 숫자가 매우 큰 값이면 ${n ≫ m}$, 이 $n$ 개의 반딧불의 초기 위치는 준-몬테카를로(quasi-Monte Carlo) 모의실험에서와 같은 형태로, 전체 탐색 공간상에서 상대적으로 균등하게 분포되어야 한다. 반복횟수가 진행되면서, 반딧불은 (전역 최적값을 포함한) 모든 지역 최적값에 통계적 형태로 수렴할 것이다. 이 모든 최적값들을 비교하여, 최선의 해결책을 선택하는 방법으로, 전역 최적값은 쉽게 발견할 수 있다. 지금은, ${n \rightarrow \infty}$ 이고 ${t ≫ 1}$ 이면, 반딧불 알고리즘이 전역 최적값에 근접한다는것을 형식적으로 증명하려고 한다. 실제로, 일반적으로 반복횟수가 50 에서 100 세대 이내에서, 이것은 매우 빨리 수렴한다. 이것을 여러가지 표준 시험 함수를 사용하여 추후에 시연해 보일것이다. 두가지 중요한 제한적인 경우가 있다. ${\gamma \rightarrow 0}$ 그리고 ${\gamma \rightarrow \infty}$ 인 경우이다. ${\gamma \rightarrow 0}$ 이면, 유인력은 상수 ${\beta = \beta_0}$ 가 되고 ${\Gamma \rightarrow \infty}$ 가 된다. 이것은 이상적인 하늘에서 광밀도가 감소하지 않는다는 것을 의미한다. 그러므로, 반딧불의 반짝임을 주어진 영역의 모든곳에서 볼수있다는 뜻이다. 그러므로, 단일 (전역) 최적값에 쉽게 도달할 수 있다. 이것은 앞에서 언급했던 입자 떼 최적화 (PSO, particle swarm optimization) 의 특수한 경우에 해당한다. 이 특별한 경우의 효율성은 PSO 의 효율성과 같다. 반면에, ${\gamma \rightarrow \infty}$ 의 제한적인 경우는 ${\Gamma \rightarrow 0}$ 이 되고 ${\beta(r) \rightarrow \delta(r)}$ ( Dirac delta function) 이 된다. 이것은 다른 반딧불의 시각에서 유인력이 거의 영이거나 반딧불이 근시라는 뜻이다. 이것은 반딧불이 안개가 매우 짙은 지역을 무작위로 날아다니는 상황과 같은 의미이다. 다른 반딧불은 보이지 않고, 모든 반딧불이 완전히 무작위로 방황한다. 그러므로, 이것은 완전 무작위 탐색 방법에 해당한다. 반딧불 알고리즘은 보통 이 두 극단 사이의 어딘가에 존재하므로, 인자 ${\gamma}$ 와 ${\alpha}$ 를 조절하여 무작위 탐색과 PSO 보다 더 높은 성능을 낼 수 있다. 사실, FA 는 전역 최적값을 찾을 수 있을 뿐만 아니라, 모든 지역 최적값을 매우 효율적인 방법으로 동시에 찾아낼 수 있다. 이 이점을 나중에 구현에서 자세히 시연할 것이다. FA 의 또다른 이점은 모든 반딧불이 거의 독립적으로 일하므로, 병렬처리 구현에 적합하다. 이것은 유전자 알고리즘과 PSO 보다도 더 뛰어나다. 반딧불이 모든 최적값 주변에 더 가까이 모이기때문이다. (유전자 알고리즘의 경우처럼 최적값 주변에서 팔짝팔짝 뛰지 않는다.) 서로다른 하위영역사이의 상호작용이 병렬처리 구현의 최소 요구사항이다.
반딧불 알고리즘이 작동하는 방식을 시연하기위해, Matlab 으로 구현 하였다. 새 알고리즘을 확인하기위해 여러가지 시험 함수를 사용할것이다. 예를 들어, FA 를 사용하여, Michalewicz 함수의 전역 최적값을 찾을 것이다.
여기서 ${m = 10}$ 이고 ${d = 1,2,....}$ 전역 최소값 ${ \ \ f_* ≈ -1.801}$ 는 이차원에서 ${(2.20319, 1.57049)}$ 에 위치한다. 이것은 반딧불 40 마리가 10 번의 반복횟수 후에 약 400 번의 계산을 통해 발견된다. ( Fig. 2 그리고 Fig. 3) 이제 FA 를 써서 좀 어려운 시험 함수의 최적값을 찾아본다. 이것은 대부분의 기존 메타휴리스틱 알고리즘보다 더욱 효율적이다. 위 모의시험에서, 인자값은 ${\alpha = 0.2, \gamma = 1}$ 그리고 ${\beta_0 = 1}$ 이다. 매우 어려운 시험 함수들도 테스트해보았다. 예를 들어, Yang 은 정지파 형태처럼 보이는 다중 함수를 설명하였다.
이것은 많은 지역 정점과 계곡으로 이루어진 다중함수이다. 이것의 고유 전역 최소값 ${\ \ f_* = -1}$ 은 ${\left(0,0,...,0 \right) }$ 에 위치한다. 지역은 ${-20 \le x_i \le 20}$ 이고, ${i = 1,2,...,d}$ 그리고 ${a = 15}$ 이다. Yang 함수의 이차원 풍경은 Fig. 4 와 같다.
많은 연구에서 PSO 알고리즘이 유전자 알고리즘(GA) 보다 수행성능이 좋다는 결과를 보여주었다. 그리고 많은 최적화 문제를 해결하는데 다른 기존 알고리즘들 보다 뛰어나다는 결과를 보여주었다. 이것은 현재의 최적해를 전파하는 능력 덕분에 최적값에 더 잘 더 빠르게 수렴하기 때문이다. 진화 알고리즘의 통계적 수행성능을 평가하는 일반적인 뼈대는 Shilane 등에 의해서 자세히 토론되었다. 이제 여러가지 표준 시험 함수상에서 반딧불 알고리즘을 PSO, 유전자 알고리즘과 비교할것이다. 유전자 알고리즘은 표준 버전을 사용했으며 엘리트주의를 사용하지 않고 돌연변이 확률 ${p_m = 0.05}$ 교차혼합 확률 ${0.95}$ 를 설정하였다. 입자 떼 최적화(PSO) 역시 표준 버전을 사용했으며, 학습인자는 ${\alpha ≈ \beta ≈ 2}$ 이고 관성수정을 사용하지 않았다. 여러가지 인구크기를 사용하였다. ${n=15}$ 에서 ${n=200}$ 범위의 인구수를 사용하였다. 그러므로, 모든 모의시험 비교는 인구크기 ${n=40}$ 으로 고정한것을 사용하였다. 이 알고리즘들을 Matlab 으로 구현한 후, 대규모의 모의 시험을 시험하였다. 모든 알고리즘은 최소 100 번이상 실행하여 의미있는 통계적 분석이 수행되도록 하였다. 이 알고리즘들이 정지하는것은 여러가지 함수값이 주어진 허용오차 ${\epsilon \le 10^{-5}}$ 보다 작을때이다. 결과는 다음 테이블에 (Table 1) 요약하였다. 숫자형식의 의미는 다음과 같다: 평균 계산 횟수(성공 비율), 그래서 ${ 3752 \pm 725 \ ( 99 \% ) }$ 는 함수 계산 평균횟수가 3752 이고 표준편차 725 이고, 이 알고리즘이 전역 최적해를 찾은 성공 비율은 ${ 99 \% }$ 라는 의미이다. FA 가 매우 효율적이라는것을 알 수 있다. 전역 최적해를 찾는데 성공률이 높다. 모든 함수 계산은 현대의 개인용 컴퓨터상에서 실제 즉각 이루어진다. 예를 들어, 10,000 번 계산 시간은 3GHz 컴퓨터에서 약 5초 이다. 입자와 반딧불의 위치를 보여주는 그래픽을 출력해도, 보통 몇 분 밖에 걸리지 않는다. 더 정형화된 통계적 가설을 실험해서 이것을 확인할수도 있을것이다.
여기서, 새로운 반딧불 알고리즘을 수식화 했다. 그리고 입자 떼 최적화와의 유사성과 차이점과 분석했다. 그리고 이 알고리즘들을 구현하고 비교했다. 모의시험 결과, 여러가지 시험 함수들의 전역 최적해를 찾을 때 입자 떼 알고리즘이 유전자 알고리즘같은 기존 방법보다 수행성능이 높은것을 알 수 있다. 그런데 새로운 반딧불 알고리즘은 효율성과 성공률 면에서, PSO 와 GA 를 모두 능가하는 결과가 나왔다. 이것은 FA 가 잠재적으로 NP-hard 문제를 푸는데 더 강력하다는 의미를 함축한다. 이것은 앞으로 더 연구되어야 할 것이다. 기본 반딧불 알고리즘은 매우 효율적이지만, 최적해에 근접할 때 해가 계속 변하는 현상이 있다. 무작위성을 점차적으로 감소시키는 방법으로 해 안정성을 증가시키는것이 가능할것이다. 알고리즘의 수렴 개선은 무작위 인자 ${\alpha}$ 에 의해서 변한다. 그러므로 최적해에 근접해 갈수록 수렴 개선은 점차적으로 감소하게된다. 이것은 향후 연구의 중요한 주제이다. 더우기, 상대적으로 복잡하지 않은 확장으로, 반딧불 알고리즘을 수정하여 다중 목적 최적화 문제를 풀 수 있다. 더우기, 반딧불 알고리즘을 응용하여 다른 알고리즘과 조합하는것이 향후 연구의 흥미로운 분야가 될것이다.
