협력 공진화 알고리즘에서 최적 부분 문제 선택을 위한 Non-Stationary UCB-Tuned 알고리즘의 활용 방법 연구

2.1 협력 공진화 알고리즘

협력 공진화 알고리즘[9]은 컴퓨터 공학 분야에서 전통적으로 활용되는 분할 정복법 메커니즘을 진화 알고리즘에 적용하여 대규모 차원의 정의역 공간을 갖는 목적함수의 전역 최적해를 효율적으로 탐색하기 위해 개발된 대표적인 진화 알고리즘의 한 종류이다. 표 1은 기본적인 협력 공진화 알고리즘의 의사코드를 보여준다.

Table 1.

Pseudocode of the basic CC algorithm

표 1에 기술된 바와 같이 협력 공진화 알고리즘은 우선 문제 분할 함수를 이용하여 주어진 목적함수 $$ f:R^n\to R$$의 정의역 공간을 구성하는 결정 변수 간의 상호 종속성을 식별하고, 이를 토대로 정의역 공간을 K 개의 부분 공간, 즉, 부분 문제로 분할한다. 이때, 목적함수 f의 정의역 공간을 구성하는 임의의 두 결정 변수 x_i와 x_j의 상호 종속성은 아래의 식 (1)을 이용하여 식별할 수 있다[11][12]. 이때, δ_i와 δ_j는 임의의 작은 상수이며, Ω(x_i,x_j) > 0이면 x_i와 x_j는 상호 종속성이 존재하는 것으로, Ω(x_i,x_j) = 0이면 상호 종속성이 존재하지 않는 것으로 판단한다.

목적함수 f에 대한 부분 문제 분할이 완료된 후 협력 공진화 알고리즘의 부분 문제 선택 함수는 매 진화 단계에서 최적해 탐색이 진행될 부분 문제를 선택한 후 진화 알고리즘을 이용하여 부분 최적해를 탐색한다. 이때, n차원의 개체(Individual) m개로 구성된 집단(Population)을 활용하여 최적해를 탐색하며, 이 과정에서 해당 부분 문제를 생성하는 결정 변수와 연관된 차원을 제외한 나머지 차원들을 상수로 고정한 후 최적해 탐색을 진행한다[18].

i번째 부분 문제에 대한 부분 최적해 탐색이 완료된 후 협력 공진화 알고리즘은 아래와 같이 i번째 부분 문제에 대한 부분 집단 P_i의 진화된 결과$$ P_i^{\prime }$$를 기존 집단 P에 반영한다.

상기 식 (2)에서 P는 n차원의 개체 m개로 구성된 m × n 행렬이며, P[:,j]는 행렬 P의 j번째 열벡터이다. 즉, 식 (2)는 진화된 부분 문제에 대한 행렬 P′ 내의 j번째 열벡터를 기존 집단 P에서 i번째 부분 문제 V_i의 v_j번째 차원에 해당하는 열벡터에 반영한다. 이렇게 갱신된 집단 내 각 개체에 대하여 적합도(Fitness)를 평가하고 가장 좋은 적합도를 갖는 개체를 새로운 전역 최적해로 지정한다. 이러한 과정은 적합도 계산을 위해 목적함수를 호출한 횟수(FEs)가 최대 허용 호출 횟수(maxFEs)를 초과할 때까지 반복적으로 수행한다. 이후, 가장 좋은 적합도를 갖는 개체를 해당 목적함수의 전역 최적해로서 반환한다.

2.2 부분 문제 선택

표 1에 기술된 바와 같이 협력 공진화 알고리즘은 매 진화 단계에서 K개의 부분 문제 중 하나의 부분 문제를 선택하고 해당 부분 문제에 대한 부분 최적해를 탐색한다. 이는 해당 부분 문제를 구성하는 결정 변수들이 생성하는 부분 공간에 한정하여 부분 최적해를 탐색하는 것과 동일하다.

그림 1은 목적함수 $$ f\left(x_1,x_2\right)=2x_1^2-x_2^4$$의 최적해 공간을 그래프로 나타낸 것이다. 협력 공진화 알고리즘의 부분 문제 분할 함수는 식 (1)을 활용하여 f(x₁,x₂)의 정의역 공간을 두 부분 문제 V₁ = {x₁}과 V₂ = {x₂}로 분할한다[12]. 이 경우, 그림 1의 경로 (a)에 표현된 바와 같이 첫 번째 부분 문제 V₁을 선택하는 경우 두 번째 부분 문제 V₂에 해당하는 차원, 즉 x₂에 대해서는 탐색이 이루어지지 않고 V₁과 관련된 x₁ 차원에 대해서만 제한적으로 최적해를 탐색한다. 이와 반대로, 경로 (b)와 같이 부분 문제 V₂가 선택될 때는 x₁차원은 고정된 채로 x₂차원에 대해서만 최적해 탐색을 수행한다.

Fig. 1.

Optimal solution surface of the objective function fx1,x2=2x12-x24

즉, 협력 공진화 알고리즘의 매 진화 단계에서 특정 부분 문제를 선택하면 해당 부분 문제를 구성하는 결정 변수가 생성하는 차원에 대해서만 제한적으로 최적해 탐색을 수행한다. 따라서, 부분 문제 선택 방법은 협력 공진화 알고리즘의 전역 최적해 탐색 성능은 물론 최종적으로 발견되는 전역 최적해의 품질에도 유의미한 영향을 미칠 수 있다.

2.3 부분 문제 선택 과정에서 탐색과 활용 균형의 필요성

앞서 2.2절에서 설명한 바와 같이 목적함수를 구성하는 결정 변수들은 해당 함수의 적합도를 계산할 때 고유의 영향력을 갖는다. 이는 곧 해당 목적함수의 최적해를 탐색하는 데 각 부분 문제가 고유의 기여도를 가짐을 의미한다. 예를 들어 그림 1에서 보인 목적함수 $$ f\left(x_1,x_2\right)=2x_1^2-x_2^4$$의 경우 x^(t) 지점에서 부분 문제 V₁을 선택하면 더 빠른 속도의 최적해 탐색을 수행할 수 있다. 이처럼, 최적해를 탐색하는 과정에서 빠른 수렴을 달성할 수 있는 부분 문제를 중점적으로 선택하여 해 탐색을 수행하는 방법을 "활용 기반의 부분 문제 선택(Exploitation-based subproblem selection)"이라 한다. 이 방법은 최적해 탐색의 수렴 속도를 강화할 수 있지만 자칫 지나치게 빠른 최적해 탐색으로 인하여 국소 최적점 또는 안장점에 조기 수렴하는 현상이 발생할 수 있으며, 이는 곧 전역 최적해를 발견하는 데 실패하는 현상을 초래할 수 있다[14].

이러한 문제점을 완화하기 위해서는 비록 낮은 기여도를 갖는 부분 문제에 대해서도 주기적으로 해 탐색을 수행하여 해의 다양성을 강화하는 것이 중요하며, 이를 "탐색 기반의 부분 문제 선택(Exploration-based subproblem selection)"이라 한다. 예를 들면, 그림 1의 x^(t) 지점에서 안장점을 피하여 최적해 탐색을 진행하기 위해서는 경로 (a)에 표현된 x₁ 차원보다는 경로 (b)의 x₂ 차원 방향으로 해 탐색을 진행하는 것이 바람직하다. 즉, x^(t) 에서는 비록 수렴 속도는 느려질지라도 부분 문제 V₂를 선택하는 것이 궁극적으로는 최적해를 탐색하는 데 더욱 효과적이다.

이처럼 목적함수의 전역 최적해 탐색을 성공적으로 수행하기 위해서는 부분 문제를 선택할 때, 이들의 기여도에 기반하여 탐색과 활용의 균형을 적절하게 유지하는 것이 중요하다. 그러나 종래의 협력 공진화 알고리즘은 표 1과 같이 순차적으로 부분 문제를 선택하는 방법을 사용하기 때문에 탐색과 활용의 균형을 유지하면서 최적해를 탐색하는 데 한계점이 존재한다. 이에 따라, 다음 장에서는 협력 공진화 알고리즘에서 탐색과 활용의 균형을 유지하면서 부분 문제를 선택하기 위해 슬라이딩 윈도 기반의 Non-Stationary UCB-Tuned 알고리즘을 활용하는 새로운 부분 문제 선택 알고리즘을 제안한다.

3.1 UCB-Tuned 알고리즘 기반의 부분 문제 선택 방법

함수 $$ f:R^n\to R$$의 해 공간은 모든 가능한 해의 집합인 실수 공간 Rⁿ의 부분 집합이며, f의 해 공간을 생성하는 n개의 결정 변수들의 집합을 V라 할 때, V는 결정 변수 간의 상호 종속성에 따라 아래와 같이 K개의 분리 집합으로 표현할 수 있다.

식 (3)에서 $$ {\forall }_{q\ne l}\Omega \left(v_{i,l},v_{i,q}\right)>0$$은 집합 V_i 내 임의의 두 변수 v_i,l와 v_i,q (단, l ≠ q) 사이에 종속성이 존재함을 의미한다. 즉, 하나의 부분 문제를 구성하는 모든 변수는 상호 종속적이다.

한편, 진화 알고리즘에서는 함수 f의 전역 최적해를 탐색하기 위해 한 개 이상의 개체로 이루어진 집단을 활용하며 m × n의 실수 행렬 P로 표기한다(즉, $$ P\in R^{m\times n}$$). 이때, 행렬 P의 i번째 행벡터는 P[i,:]와 같이 표현하며 이는 i번째 개체를 의미한다. 이와 유사하게, P의 j번째 열벡터는 P[:,j]로 표현하며 이는 행렬 P의 j번째 차원을 의미한다. 그렇다면, i번째 부분 문제 V_i에 대한 집단 P의 부분 집단 P_i는 다음과 같이 표현할 수 있다.

식 (4)에서 v_i,j는 V_i 내 j번째 원소이며(즉, $$ v_{i,j}\in V_i$$) ⊕는 두 열벡터를 왼쪽에서 오른쪽으로 연결(Concatenation)하는 이항 연산자이다. 예를 들어, $$ P\in R^{m\times n}$$이고 $$ \left\{v_1,v_5,v_7\right\}\in V_i$$일 때, P_i는 행렬 P의 v₁번째 열벡터 P[:,v₁]과 v₅번째 열벡터 P[:,v₅], v₇번째 열벡터 P[:,v₇]을 순차적으로 연결하여 생성되는 m × 3 행렬이다.

즉, 협력 공진화 알고리즘에서 i번째 부분 문제를 선택하면 진화 알고리즘은 전체 집단 P에서 부분 집단 P_i를 구성하는 차원들에 대해서만 최적해 탐색을 수행하고 나머지 차원들에 대해서는 고정된 값을 유지한다. 이 경우, i번째 부분 문제를 선택하여 최적해 탐색을 수행하기 전과 후에 발견된 두 전역 최적해의 적합도를 비교함으로써 해당 부분 문제를 선택하였을 때 얼마만큼 전역 최적해의 적합도를 향상시킬 수 있는가를 정량적으로 측정할 수 있다. 현재 시점 t를 기준으로 직전에 관찰된 전역 최적해의 적합도를 $$ f_{t-1}^{\mathrm{*}}$$, 현재 선택된 부분 문제에 대하여 최적해 탐색을 수행한 후 발견된 전역 최적해의 적합도를 $$ f_t^{\mathrm{*}}$$라 할 때, 아래와 같이 적합도 향상의 정도를 계산할 수 있다.

상기 식 (5)에서 τ는 분모가 0이 되는 현상을 예방하기 위해 사용되는 Smoothing Factor이다. 식 (5)를 응용하여 i번째 부분 문제를 j번째로 선택하여 최적해 탐색을 수행하였을 때의 적합도 향상 점수를 정의하면 다음과 같다.

식 (6)에서 $$ f_{i,j}^{\mathrm{*}}$$는 i번째 부분 문제를 j번째로 선택하여 최적해 탐색을 수행한 후 발견된 전역 최적해의 적합도이고 $$ f_{prev}^{\mathrm{*}}$$는 직전 단계에서 관찰된 전역 최적해의 적합도이다.

한편, 앞서 2.3절에서 설명한 바와 같이 부분 문제를 선택하는 과정에서 탐색과 활용의 균형을 적절하게 유지하기 위해서는 전역 최적해 탐색 과정에서 비록 낮은 기여도를 갖는 부분 문제에 대해서도 주기적으로 선택하여 탐색을 수행하는 과정이 필요하다. 동시에, 수렴 속도가 지나치게 느려지는 현상을 예방하기 위해서는 높은 기여도를 갖는 부분 문제에 대한 탐색 역시 필수적으로 수행해야 한다. 이처럼, 탐색과 활용의 균형을 유지하면서 부분 문제를 선택하기 위해서는 식 (6)에 기반하여 부분 문제를 선택하는 것보다는 UCB-Tuned 알고리즘[15]의 Arm 선택 전략을 활용하여 각 부분 문제의 기여도 점수를 계산하고 이를 토대로 부분 문제를 선택하는 것이 효과적이다. 즉, i번째 부분 문제의 기여도 점수는 다음과 같이 계산할 수 있다.

식 (7)에서 μ_i는 i번째 부분 문제에 대한 적합도 향상 점수들의 평균으로 다음과 같이 계산한다.

식 (8)에서 n_i는 i번째 부분 문제가 선택되어 최적해 탐색이 진행된 횟수를 의미한다. 한편, 식 (7)의 P_i는 i번째 부분 문제에 대한 기여도 점수를 계산할 때 탐색과 활용의 균형을 조정하는 Padding Function으로 아래와 같이 계산한다.

식 (9)에서 n은 지금까지 수행된 진화 단계의 총횟수를 의미하며, K개의 모든 부분 문제에 대해서 $$ \sum _{i=1}^K{n}_i=n$$을 만족한다. 또한, ξ_i는 i번째 부분 문제에 대한 최적해 탐색을 수행한 후 측정된 적합도 향상 점수들의 분산으로 아래의 식 (10)을 이용하여 계산할 수 있다.

식 (7)에 의해서 계산된 i번째 부분 문제에 대한 기여도 점수를 활용하여 부분 문제를 선택하면 탐색과 활용의 균형을 효과적으로 유지할 수 있다. 예를 들어, 초기 진화 단계일수록 P_i는 상대적으로 큰 값을 가지므로 식 (7)에서 P_i의 영향력 또한 커진다. 이 경우, 활용보다는 탐색의 원리에 기반하여 부분 문제를 선택한다. 반대로, 진화 과정이 진행됨에 따라 i번째 부분 문제에 대한 적합도 향상 점수의 분산이 지속적으로 감소하므로, P_i의 값은 점차 작아진다. 이 경우, 식 (7)에서 μ_i의 영향력이 상대적으로 증가하여 부분 문제를 선택할 때 활용의 효과가 강화된다. 이에 따라, 진화 단계의 후반부로 진행될수록 부분 문제의 평균 적합도 향상 점수에 기반하여 부분 문제를 선택한다. 즉, 초기 진화 단계에서는 해 탐색의 다양성을 강화하기 위해 탐색중심의 부분 문제 선택을 수행한다면, 이후에는 빠른 수렴을 위해 점진적으로 "활용"에 기반하여 부분 문제를 선택한다.

3.2 UTSWSP: 슬라이딩 윈도 기반 Non-Stationary UCB-Tuned 알고리즘을 활용한 부분 문제 선택 알고리즘

협력 공진화 알고리즘에서 최적해 탐색이 진행될수록 집단 내의 개체들은 전역 또는 국소 최적점으로 수렴한다. 이에 따라, 각 개체의 적합도 역시 국소 또는 전역 최적해의 적합도와 점차 가까워지고, 결과적으로 각 부분 문제를 선택하여 최적해를 탐색하였을 때 전역 최적해의 적합도 향상의 정도 역시 달라진다. 즉, 부분 문제별 적합도 향상 점수의 분포는 동적으로 변화하며 이는 MAB 알고리즘에서 시간이 지남에 따라 각 Arm이 반환하는 보상의 분포가 변화하는 현상과 동일하다. 이와 같이, 협력 공진화 알고리즘은 최적해 탐색이 진행됨에 따라 부분 문제의 적합도 향상 정도의 분포가 동적으로 변화하는 Non-Stationary 특성을 갖는다.

이에 따라, 진화 알고리즘의 Non-Stationary 특성을 고려하여 부분 문제에 대한 적합도 향상 점수의 평균을 계산하면, 각 부분 문제를 선택하였을 때 얼마나 유의미하게 전역 최적해의 적합도를 향상시킬 수 있었는가를 더욱 정확하게 측정할 수 있다. 즉, 식 (8)~(10)에 적용된 적합도 향상 점수의 평균과 분산을 계산할 때 Non-Stationary 메커니즘을 적용하기 위해 다음과 같이 슬라이딩 윈도[16]를 활용할 수 있다.

3.2.1 슬라이딩 윈도의 설계 방법

목적함수 f의 최대 허용 호출 횟수를 maxFEs, 진화 알고리즘 내에서 허용되는 최대 반복 횟수를 ρ, 집단 내 개체의 수를 m, f의 부분 문제의 개수를 K라 하자. 그렇다면, 최적해 탐색 과정에서 각 부분 문제별 평균 선택 횟수 $$ \tilde{n}$$는 다음과 같은 근사식으로 표현할 수 있다.

$\[ \tilde{n}\cong ⌈\frac{maxFEs}{\left(\rho +1\right)mK}⌉ \]$

(11)

즉, maxFEs가 커짐에 따라 $$ \tilde{n}$$ 또한 이에 비례하여 증가한다. 이 경우 슬라이딩 윈도의 크기 역시 이에 비례하여 확장하는 것이 합리적이다. 반면에, K, m, 또는 ρ의 값이 증가하는 경우 동일한 maxFEs 하에서 $$ \tilde{n}$$는 감소하게 된다. 이 경우에는 각 부분 문제별로 측정되는 적합도 향상 점수의 개수 역시 줄어들므로 슬라이딩 윈도의 크기를 축소하는 것이 바람직하다. 결과적으로, 슬라이딩 윈도의 평균 크기 W는 아래와 같이 $$ \tilde{n}$$에 비례한다.

$\[ W\propto \tilde{n}\cong ⌈\frac{maxFEs}{\left(\rho +1\right)mK}⌉ \]$

(12)

따라서, 슬라이딩 윈도의 크기 W의 근사 공식은 maxFEs와 ρ, m, K에 관한 식으로 다음과 같이 표현할 수 있다.

$\[ W\cong ⌈\alpha \times \frac{maxFEs}{\left(\rho +1\right)mK}⌉ \]$

(13)

식 (13)에서 α∈(0,1)는 비례 상수로 슬라이딩 윈도의 실제 크기를 결정하는 제어 파라미터의 역할을 수행한다. 만약 α를 0에 근접한 임의의 작은 값으로 설정한다면 기여도 점수 계산 시 가장 최근의 적합도 향상 점수들이 반영된다. 반면에 1에 가까운 값으로 설정하는 경우, 슬라이딩 윈도의 크기가 이에 비례하여 증가하므로 더 많은 과거 적합도 점수들을 포함하여 기여도 점수를 계산할 수 있다. 다만, α를 1에 근접한 값으로 설정하면 기여도 점수 계산 시 대부분의 과거 적합도 향상 점수들이 포함되어 결과적으로 슬라이딩 윈도를 사용하지 않는 기존의 UCB 또는 UCB-Tuned 기반의 부분 문제 선택 알고리즘[18]과 동일해지는 효과를 초래할 수 있음에 유의해야 한다.

한편, i번째 부분 문제가 선택된 횟수를 n_i라 할 때, n_i < W인 경우 슬라이딩 윈도의 크기는 n_i로 설정된다. 이후 진화 알고리즘이 진행됨에 따라 n_i 역시 점차 증가하게 되고 n_i = W가 되면 i번째 부분 문제에 대한 슬라이딩 윈도의 최종 크기는 W로 고정된다. 이에 따라, i번째 부분 문제에 대한 슬라이딩 윈도의 크기 W_i를 결정하는 방법을 수식으로 표현하면 다음과 같다.

(14)

그림 3은 슬라이딩 윈도를 이용하여 i번째 부분 문제에 대한 적합도 향상 점수의 평균을 계산하는 방법을 설명한다. 그림 3에 나타낸 바와 같이 i번째 부분 문제가 총 n_i번 선택되어 적합도 향상 점수가 계산 및 누적되었다고 가정할 때, 가장 최근에 계산된 결과(리스트의 가장 오른쪽에 표시된 값)를 포함한 최신 W_i개의 결과만을 평균 계산 시 활용한다.

Fig. 3.

Example of a method to average the fitness improvement score by utilizing the sliding window

3.2.2 슬라이딩 윈도를 활용한 Non-Stationary UCB-Tuned 기반 부분 문제 선택 알고리즘의 구현

식 (14)에서 설명한 슬라이딩 윈도 W_i를 활용하여 i번째 부분 문제에 대한 적합도 향상 점수의 평균을 다음과 같이 계산할 수 있다.

$\[ {\mu }_i^{\left(W\right)}=\frac{1}{W_i}\times \sum _{j=n_i-W_i+1}^{n_t}{\Delta }_{i,j} \]$

(15)

즉, i번째 부분 문제에 대한 평균 적합도 향상 점수를 계산하기 위해서 총 n_i개의 적합도 향상 점수 중 가장 최근에 계산된 W_i개의 점수들을 활용한다. 이와 동일한 원리로, i번째 부분 문제에 대한 Padding Function $$ P_i^{\left(W\right)}$$는 다음과 같이 계산한다.

$\[ P_i^{\left(W\right)}=\sqrt{\frac{{\Psi }_i}{W_i}\ln \sum _{r=1}^K{W}_r} \]$

(16)

식 (16)에서 Ψ_i는 부분 문제 선택 시 진화 단계에 따른 탐색과 활용의 균형을 조정하기 위한 함수로써 아래와 같이 계산할 수 있다.

$\[ {\Psi }_i=\min \left(\frac{1}{4},{\xi }_i^{\left(W\right)}+\sqrt{\frac{2}{W_i}\ln \sum _{r=1}^K{W}_r}\right) \]$

(17)

상기 식 (17)에서 $$ {\xi }_i^{\left(W\right)}$$는 슬라이딩 윈도를 이용하여 계산되는 적합도 향상 점수의 분산으로 아래의 식을 이용하여 계산한다.

$\[ {\xi }_i^{\left(W\right)}=\frac{1}{W_i}\times \sum _{j=n_i-W_i+1}^{n_i}{\Delta }_{i,j}^2-{\left[{\mu }_i^{\left(W\right)}\right]}^2 \]$

(18)

결과적으로 i번째 부분 문제에 대한 최종 기여도 점수 $$ C_i^{\left(W\right)}$$의 계산 공식을 정의하면 다음과 같다.

$\[ C_i^{\left(W\right)}={\mu }_i^{\left(W\right)}+P_i^{\left(W\right)} \]$

(19)

식 (19)를 이용하여 협력 공진화 알고리즘은 매 진화 단계에서 모든 부분 문제에 대한 기여도 점수를 계산한다. 그다음에, 가장 높은 기여도 점수를 갖는 부분 문제를 다음 진화 단계에서 최적해 탐색을 진행할 부분 문제로 선택한다. 즉, 식 (19)에 의해서 계산된 K개의 부분 문제에 대한 기여도 점수를 $$ C_1^{\left(W\right)},\dots ,C_K^{\left(W\right)}$$라 할 때, 아래의 식 (20)을 이용하여 다음 단계에서 최적해 탐색이 진행될 부분 문제의 인덱스 i^(next)를 결정한다.

$\[ i^{\left(next\right)}=\mathrm{a}\mathrm{r}\mathrm{g}{\max }_i\left(C_1^{\left(W\right)},\dots ,C_i^{\left(W\right)},\dots ,C_K^{\left(W\right)}\right) \]$

(20)

식 (14)~(20)을 종합하여 실제 협력 공진화 알고리즘에 적용할 수 있는 부분 문제 선택 방법인 UTSWSP(Non-Stationary UCB-Tuned with Sliding Window-based Subproblem Selector) 알고리즘을 구현할 수 있다. 표 2는 제안하는 UTSWSP 알고리즘의 의사코드를 보여준다. UTSWSP 알고리즘은 먼저 모든 부분 문제를 한 번씩 순차적으로 선택하고 그것의 인덱스를 반환하는 Round-Robin Subproblem Selection을 수행한다. 이는 협력 공진화 알고리즘에서 부분 문제별 기여도를 계산하기 위해서는 최소 하나 이상의 적합도 향상 점수가 필요하기 때문이다. 이후 UTSWSP 알고리즘은 모든 부분 문제에 대한 기여도 점수에 기반하여 다음 단계에서 최적해 탐색을 진행할 부분 문제를 선택한다. 이때, 기여도 점수를 효율적으로 계산하기 위해 각 부분 문제별로 측정된 적합도 향상 점수들을 인덱싱하는 리스트 Δ와 Γ를 크기가 K × W인 K개의 원형 큐(Circular queue)로 설계할 수 있다. 이 경우, 만약 n_i < W라면, i번째 부분 문제에 대한 슬라이딩 윈도의 크기 W_i는 식 (14)에 의해 n_i가 되어야 한다. 이를 효율적으로 구현하기 위해서 Δ와 Γ의 모든 성분을 "NULL"로 초기화한다. 그렇다면, n_i < W인 경우 Δ와 Γ의 i번째 행에 인덱싱된 값들의 합인 sum(Δ[i,:])와 sum(Γ[i,:])는 n_i개의 NULL이 아닌 요소들의 합을 계산하는 것과 동일하다. 이처럼 원형 큐를 이용함으로써 식 (15)와 (18)을 계산하는 데 필요한 최신 W개의 적합도 향상 점수만을 효율적으로 유지할 수 있다. 마지막으로, 모든 부분 문제에 대한 기여도 점수 계산을 완료한 후 UTSWSP 알고리즘은 식 (20)을 이용하여 최대 기여도 점수를 갖는 부분 문제의 인덱스를 반환한다.

Table 2.

Pseudocode of proposed UTSWSP algorithm

표 2의 UTSWSP 알고리즘은 진화 알고리즘의 동적 수렴 특성을 반영하기 위해 각 부분 문제별로 식 (14)의 슬라이딩 윈도를 활용하여 식 (15)와 (18)을 계산하며 이를 위해 W 크기의 원형 큐를 이용한다. 이를 통해, 최근 W개의 적합도 향상 점수들을 효율적으로 인덱싱하고 이를 기반으로 기여도 점수를 Incremental 하게 계산할 수 있다. 이러한 방법은 과거의 모든 적합도 향상 점수를 활용하여 기여도를 계산하는 기존의 부분 문제 선택 알고리즘인 [18], [19], [20]과 명확히 구별되는 UTSWSP 알고리즘만의 특징이다. 이를 통해 UTSWSP 알고리즘을 적용한 협력 공진화 알고리즘은 기존의 전통적인 부분 문제 선택 알고리즘을 적용했을 때보다 더욱 높은 품질의 전역 최적해를 효과적으로 탐색할 수 있다. UTSWSP 알고리즘을 실제 협력 공진화 알고리즘에 적용하여 최적해 탐색을 수행하는 방법에 대해서는 이어지는 3.3절에서 자세히 설명한다.

3.3 실제 협력 공진화 알고리즘 내 UTSWSP 알고리즘의 활용 방법

표 2에서 설명한 UTSWSP 알고리즘은 실제 협력 공진화 알고리즘 내에서 부분 문제 함수로써 활용할 수 있다. 이에 대한 예제 방법을 의사코드로 표현하면 표 3과 같다.

Table 3.

Example of utilizing the UTSWSP Algorithm in the CC framework

협력 공진화 알고리즘은 주어진 목적함수에 대한 전역 최적해를 탐색하기에 앞서 집단 내 개체들에 대한 초기화를 수행한 후 가장 좋은 적합도를 갖는 개체를 초기 전역 최적해로 지정한다. 다음으로, 식 (13)을 이용하여 슬라이딩 윈도의 크기 W를 결정하고, 부분 문제별 기여도 계산에 필요한 적합도 향상 점수와 부분 문제 선택 횟수 등을 인덱싱할 변수들을 초기화한다. 이후 표 2의 UTSWSP 알고리즘을 이용하여 부분 문제를 선택한 후 해당 부분 문제에 대한 최적해 탐색을 진행하고, 새롭게 진화된 부분 문제의 모든 개체를 기존 집단에 반영(갱신)한다. 이어서, 식 (6)을 이용하여 해당 부분 문제에 대한 새로운 적합도 향상 점수를 계산하고 변수 Δ[i,j]에 계산 결과를 인덱싱한다. 이 과정에서 해당 부분 문제의 선택 횟수와 새로운 전역 최적해의 적합도 정보도 함께 갱신한다. 이러한 과정은 목적함수의 호출 횟수(FEs)가 최대 허용 호출 횟수(maxFEs)를 초과할 때까지 반복적으로 수행한다. 마지막으로, 전역 최적해 탐색 과정이 종료되면 현재까지 발견된 전역 최적해를 최종적인 해로서 반환한 후 알고리즘을 종료한다.

4.1 실험 환경 구축 및 성능평가 방법

제안하는 UTSWSP 알고리즘을 실제 협력 공진화 알고리즘에 적용하였을 때, 최적해 탐색 성능을 강화하는데 얼마만큼 기여할 수 있는가를 확인하기 위해 아래와 같이 실험을 설계하여 성능평가를 진행하였다.

먼저, 협력 공진화 알고리즘에서 활용될 기반 진화 알고리즘과 문제 분할 함수로 SaNSDE[21]와 ERDG[22]를 각각 적용하였다. 이와 함께, 실제 협력 공진화 알고리즘의 최적화 성능을 평가하기 위한 벤치마크 목적함수로 CEC’2010 벤치마크 함수 세트[17]에 포함된 17개의 테스트 함수를 채택하였다. CEC’2010 벤치마크 함수 세트에는 1,000차원의 테스트 함수 20개가 포함되어 있으며, ERDG를 이용하여 이들 각각에 대한 문제 분할을 시행한 결과 함수 f₃, f₁₉, f₂₀에 대해서는 2개 이상의 부분 문제로 분할되지 않았다. 따라서, 해당 함수들을 제외한 나머지 17개의 함수(f₁, f₂, f₄~f₁₈)에 대해서만 성능평가를 수행하였다.

한편, 제안하는 UTSWSP 알고리즘을 실제 협력 공진화 알고리즘에 적용했을 때 얼마만큼 최적화 성능을 향상시킬 수 있는가를 평가하기 위해 아래의 절차에 따라 실험을 진행하였다.

첫째, UTSWSP 알고리즘과 기존 부분 문제 선택 알고리즘 각각을 협력 공진화 알고리즘에 적용하였다. 이때, 성능 비교를 위한 기존의 협력 공진화 알고리즘으로 Round-robin 기반의 부분 문제 선택 방법을 활용하는 BasicCC 알고리즘[9]과 임의로 부분 문제를 선택하는 Random CC 알고리즘(RandomCC)[9], ε-Greedy 알고리즘을 이용하여 부분 문제를 선택하는 BBCC 알고리즘[19], 그리고 적합도 향상의 정도에 기반하여 부분 문제를 선택하는 CBCC1과 CBCC2 알고리즘[20]을 채택하였다. 표 4는 각각의 부분 문제 선택 알고리즘을 활용하는 협력 공진화 알고리즘들의 명칭을 보여준다.

Table 4.

Names of the CC algorithms utilizing each of eight subproblem selection algorithms

둘째, 표 4의 협력 공진화 알고리즘 8개를 이용하여 CEC’2010 벤치마크 함수 17개에 대한 전역 최적해 탐색을 수행하였다. 이때, 하나의 테스트 함수에 대해서 25번 반복적으로 전역 최적해 탐색을 수행하고 이를 통해 발견된 전역 최적해들에 대한 평균 적합도를 계산하였다.

셋째, 각각의 테스트 함수에 대해서 UTSWSPCC가 발견한 전역 최적해의 평균 적합도와 나머지 7개의 협력 공진화 알고리즘이 발견한 전역 최적해의 평균 적합도를 상호 비교하였다. 이를 위해, 대표적 분산 분석 방법의 하나인 윌콕슨 순위 합 검정(Wilcoxon rank-sum test)을 수행하였으며, 이 과정에서 유의 수준(Significance level) p는 0.05로 설정하고 비교 과정에서 1종 오류의 발생을 예방하기 위해 Bonferroni p-correction을 수행하였다.

마지막으로, UTSWSP와 UTSWSPCC 알고리즘에서 개체의 개수 m은 100, Smoothing Factor τ는 10^-8, 목적함수의 최대 허용 호출 횟수 maxFEs는 3×10⁶, SaNSDE에서 사용하는 최대 반복 횟수 ρ는 100으로 설정하고 성능평가를 진행하였다.

4.2 슬라이딩 윈도 크기에 따른 협력 공진화 알고리즘의 최적화 성능 비교 평가

식 (12)에서 설명한 바와 같이 UTSWSP 알고리즘은 슬라이딩 윈도의 크기를 제어하는 파라미터로써 α를 사용한다. 이에 따라, 본 실험에서는 파라미터 α에 대한 최적의 설정값을 찾고, 파라미터 설정에 따른 최적해 탐색 성능을 분석하기 위한 실험을 진행하였다. 이를 위해, α를 0.1에서 1.2까지 설정한 12종의 UTSWSP 알고리즘을 구현하고, 이들 각각을 적용한 협력 공진화 알고리즘의 최적해 탐색 결과를 비교하였다. 이때, 슬라이딩 윈도를 활용한 Non-Stationary 메커니즘이 부분 문제를 선택할 때 얼마만큼 유의미하게 기여할 수 있는가를 평가하기 위해 Non-Stationary 메커니즘을 적용하지 않은 UCB-Tuned 기반의 부분 문제 선택 알고리즘을 활용하는 UCBTSPCC[18]의 최적해 탐색 결과와 비교 평가를 수행하였다.

표 5는 파라미터 α의 변화에 따른 협력 공진화 알고리즘의 최적해 탐색 결과를 보여준다. 표 5에서 "W(Win)"은 UTSWSPCC가 UCBTSPCC보다 더 좋은 최적해 탐색 결과를 달성하였음을 보여준다. 반면에, "L(Lose)"는 UTSWSPCC가 UCBTSPCC보다 더 낮은 최적해 탐색 결과를 보여주었음을 나타낸다. 마지막으로, "T(Tie)"는 UTSWSPCC와 UCBTSPCC가 통계적으로 동등한 결과를 달성하였음을 의미한다.

Table 5.

Optimization performance evaluation results of UTSWSPCC based on the configuration of the sliding window’s parameter α

표 5에 기술된 바와 같이 α를 0.2와 0.4로 설정했을 때 총 10개의 테스트 함수에서 UCBTSPCC보다 더 좋은 최적해 탐색 결과를 보여주었다. 이는 총 12개의 UTSWSPCC 모델 중에서 가장 좋은 최적해 탐색 결과이다. 특히, α를 0.2로 설정한 경우 0.4로 설정했을 때보다 17개의 테스트 함수에 대해서 평균적으로 더 좋은 적합도를 가짐을 확인하였다. 또한, α를 0.3으로 설정하였을 때, 총 9개의 함수에서 "Win"을 달성하였으며 이는 두 번째로 좋은 최적해 탐색 결과이다. 한편, α의 크기가 증가할수록 UTSWSPCC와 UCBTSPCC의 결과가 거의 동등해지는 현상을 발견할 수 있는데, 이는 α의 크기가 커질수록 슬라이딩 윈도의 크기 역시 증가함에 따라 대부분의 적합도 향상 점수들이 참조되기 때문이다.

이러한 일련의 실험 결과는 슬라이딩 윈도의 크기가 상대적으로 작을수록 최적화 성능 향상에 유리함을 보여준다. 즉, 부분 문제별로 더욱 정확하게 기여도를 평가하기 위해서는 비교적 최근에 계산된 적합도 향상 점수들을 활용하는 것이 더욱 효과적임을 확인할 수 있다. 이에 따라, 0.2를 UTSWSP 알고리즘의 파라미터 α의 최적값으로 채택하였다.

4.3 기존 부분 문제 선택 방법을 적용한 협력 공진화 알고리즘과의 최적화 성능 비교 평가

표 6은 UTSWSPCC와 나머지 7개의 협력 공진화 알고리즘 각각에 의해서 발견된 테스트 함수별 전역 최적해의 평균 적합도와 그들의 비교 결과를 보여준다. 표 5와 유사하게 "W(Win)"는 UTSWSPCC가 비교되는 다른 협력 공진화 알고리즘보다 더 좋은 최적해 탐색 결과를 달성하였음을 의미한다. "T(Tie)"는 UTSWSPCC와 비교되는 협력 공진화 알고리즘이 통계적으로 동등한 최적해 탐색 결과를 달성하였음을 나타내며, "L(Lose)"은 UTSWSPCC가 더 나쁜 탐색 결과를 보여주었음을 의미한다.

Table 6.

Optimization performance evaluation results of the CC algorithms utilizing the UTSWSP algorithm and other subproblem selection methods

표 6의 실험 결과는 제안하는 협력 공진화 알고리즘에 UTSWSP를 적용하였을 때 가장 많은 수의 테스트 함수에서 더욱 향상된 최적해 탐색 결과를 달성하였음을 보여준다. 구체적으로, UTSWSPCC는 UCB 기반의 부분 문제 선택 알고리즘이 적용된 UCBSPCC와 비교했을 때, 9개의 테스트 함수에 대해서 더 좋은 최적해 탐색 결과를 달성하였다. 또한 3개의 테스트 함수에 대해서 통계적으로 동등한 결과를 보여주었다. 이와 유사하게, UCBTSPCC와의 비교에서도 UTSWSPCC가 10개와 3개의 테스트 함수에서 더 좋거나 동등한 최적해 탐색 결과를 달성하였다. 이러한 실험 결과는 협력 공진화 알고리즘에서 최적의 부분 문제를 선택하는 데 있어서 기본적인 UCB 및 UCB-Tuned 알고리즘만을 활용하는 것보다는 슬라이딩 윈도 기반의 Non-Stationary 메커니즘이 적용된 UCB-Tuned 알고리즘을 활용하는 것이 최적해 탐색 성능을 강화하는 데 더욱 효과적임을 보여준다. 이를 통해, 부분 문제별로 기여도를 평가할 때 진화 알고리즘의 동적인 수렴 특성을 고려하여 적합도 향상 점수의 평균과 분산을 계산하는 것이 협력 공진화 알고리즘의 최적해 탐색 성능을 향상하는데 유의미하게 기여할 수 있음을 확인할 수 있다.

한편, 전통적인 협력 공진화 알고리즘과의 비교에서도 UTSWSPCC는 가장 좋은 최적해 탐색 결과를 보여주었다. BasicCC 및 RandomCC와의 비교에서, UTSWSPCC는 11개와 16개의 함수에서 더 좋은 최적화 결과를 달성하였다. 또한, CBCC1 및 CBCC2와의 비교에서도 UTSWSPCC는 12개의 테스트 함수에 대해서 더 좋은 최적해 탐색 성능을 보여주었다. 마지막으로, MAB 알고리즘 중 ε-greedy 알고리즘을 사용하여 부분 문제를 선택하는 BBCC 알고리즘과의 비교에서는 11개의 테스트 함수에 대해서 UTSWSPCC가 더 좋은 최적해 탐색 결과를, 4개의 함수에 대해서 동등한 결과를 달성하였다. 이러한 실험 결과는 협력 공진화 알고리즘에서 부분 문제 선택을 위해 MAB 알고리즘을 활용하는 경우라 할지라도 슬라이딩 윈도 기반의 Non-Stationary UCB-Tuned 알고리즘에 기반하여 부분 문제를 선택하는 것이 실제 최적해 탐색 성능을 강화하는 데 더욱 효과적임을 보여준다.