읽기일기

패턴 인식 (11) 최적화 알고리즘

4

패턴인식, 오일석 지음/교보문고

11. 최적화 알고리즘

패턴 인식에는 많은 최적화 문제(optimization problem)이 잇다. SVM, 신경망, 베이시언 분류기들도 근본적으로 최적화 문제를 푸는 과정을 거친다. 이러한 분류기 훈련 문제들은 찾아야 하는 매개 변수가 연속 공간(continuous space)를 갖는다. 또한 특징 선택과 같이 매개 변수가 이산 공간(discrete space)에 정의되는 경우도 있다.

일반적으로 최적화 문제는 다음과 같이 기술할 수 있다.

$ J(\theta)$를 최대로 하는 $\hat{\theta}$를 찾아라. 또는,
$ J(\theta)$를 최소로 하는 $\hat{\theta}$를 찾아라.

$j(\theta)$는 목적 함수(target function) 또는 비용 함수(cost function)라 부르고 $\theta$는 매개 변수라 한다. 경우에 따라 목적 함수를 최대로 하는 최대화 문제(maximization problem)도 있고 최소로 하는 최소화 문제(minimization problem)도 있다.

어떤 문제를 해결하기 위해서는 크게 두 단계로 나누어, 목적 함수 $j(\theta)$를 정의하고, 다음으로 이 문제를 풀어 최적 매개 변수를 구한다.

11.1 패턴 인식의 최적화 문제와 풀이

여러 최적화 문제의 특성을 분석하고 이들이 어떻게 서로 다른지 살펴보자.

11.1.1 최적화 문제들

분류기

분류기를 학습하기 위해서는 학습 (훈련) 집합이 있어야 한다. 학습 집합은 $ X = \{(x_1, t_1), (x_2, t_2), \dots, (x_N, t_N) \} $으로 표기한다. $x_i$는 i번째 샘플의 특징 벡터이고, $t_i$$x_i$가 속한 부류를 나타낸다. 분류기는 매개 변수 $\theta$를 갖는다. 분류기는 $x_i$를 입력으로 받아 $\theta$를 이용하여 출력 값 $o_i$를 계산하는 함수이다. $o_i$$t_i$와 같을 수도 있고 다를 수도 있지만, N개의 모든 샘플에 대해 $o_i = t_i$이면 $\theta$는 완벽하다고 이야기할 수 있다. 하지만 문제의 복잡성으로 인하여 이런 완벽한 경우는 거의 없다. 따라서 이 둘의 차이를 최소화 하는 것을 목적으로 하여야 한다. 이에 따라 설정한 목적 함수는 다음과 같이 나타낼 수 있다.

$$J(\theta) = \sum_{i=1}^N d(o_i, t_i)$$

함수 $d(o_i, t_i)$$o_i$$t_i$의 차이를 측정해 준다.

선택

선택 문제는 대표적인 이산 공간에서 정의되는 문제이다. 여러 요소들로 구성되는 집합 $S= \{ s_1, s_2, \dots, S_N \} $이 있다고 하자. 이들 부분 집합 중에 가장 좋은 것을 찾는 것이 바로 선택 문제(selection problem)이다.

선택 문제도 매개 변수 $\theta$를 도입하여 표현할 수 있다. $\theta$는 n비트를 갖는 이진열이다. 예를 들어 n=5인 경우, 부분 집합 $S_1 = \{ s_2, s_3, s_5 \} $$\theta = 01101 $로 표현한다.

선택 문제도 앞의 분류기 학습과 동일한 방법으로 설정할 수 있다.

군집화

군집화 문제에서도 선택의 문제와 비슷한 방법으로 $\theta$가 군집의 번호를 갖도록 설정할 수 있다. 예를 들면8개의 샘플을 3개의 군집에 포함되도록 할 때 $\theta = 13131322 $의 표현을 갖는다. 이제 군집화도 최적화 문제로 볼 수 있다.

이 외에도 PCA나 EM 알고리즘 또한 최적화 문제로 표현할 수 있다.

11.1.2 문제 풀이

그렇다면 $\hat{\theta} $를 어떻게 찾아야 할까? 최적 해를 찾기 위해서는 매개 변수 $\theta$가 이루는 공간을 효율적으로 탐색하는 알고리즘이 필요하다. 이 공간은 연속일 수도 있고 이산적일 수도 있다. 공간의 크기 또한 클수도 작을수도 있으며 그 차원은 $\theta$의 차원과 매우 밀접하다. 또한 문제에서 정의된 $J(\theta)$도 문제 풀이의 난이도를 좌우한다. 비교적 단순한 형태를 갖는 경우 미분 식을 풀어 최적 점을 찾을 수도 있지만, 대부분 아주 복잡한 형태를 가지므로 다른 방식의 탐색 알고리즘을 필요로 한다. 내리막 경사법, 시뮬레이티드 어닐링, 유전 알고리즘이 모두 이런 형태를 취하는 방법들이다.

이들 알고리즘을 구현하기 위해서는 세 가지 사항을 결정해야 한다.

  1. 초기해 설정 : 탐색의 초기 점을 결정한다. 이 초기 점에 따라 지역 최적점에서 끝날 수도 있고 전역 최적 점으로 수렴할 수도 있다. 초기 점을 어떻게 결정할 것인가?
  2. 멈춤 조건 : 현재 해가 만족스러우면 그 해를 결과로 출력하고 멈춘다. 어떻게 만족스러운지 판단할 것인가?
  3. 해 갱신 : 현재 해를 다른 점으로 이동한다. 이동을 책임지는 함수를 어떻게 만들 것인가?

11.2 미분을 이용한 방법

11.2.1 분석적 풀이

다음 알고리즘은 미분을 이용하여 최고 점 또는 최소 점을 찾는 과정을 명확하게 설명한다.

  1. $j(\theta)$$\theta$로 미분한다.
  2. 방정식 $\frac{\partial J(\theta)}{\partial \theta}=0 $를 만족하는 $\hat{\theta}$를 구한다.
  3. $\hat{\theta}$를 출력

이 알고리즘은 도함수(derivative)의 값은 기울기를 나타내고 최고 점 또는 최저 점에서는 기울기가 0이라는 성질을 이용하고 있다. 만약 여러개의 해가 나오는 경우 적절한 방법을 통해 하나의 해를 선택하여야 한다.

이러한 방법을 분석적(analytical) 방법이라 한다. 도함수를 0으로 놓아 방정식을 만들고 이것을 이리저리 바꾸어 가며 해를 구하는 방식이다.

11.2.2 내리막 경사법

패턴 인식에서는 매개 변수가 수십 ~ 수백 차원의 벡터인 경우가 대부분이라 이 방법은 한정된 곳에서만 응용이 가능하다. 또한 목적함수가 모든 구간에서 미분 가능하다는 보장이 항상 있는 것도 아니다. 따라서 한 번의 수식 전개로 해를 구할 수 없는 상황이 적지 않게 있다. 이런 경우 초기 해에서부터 시작하여 해를 반복적으로 개선해 나가는 수치적 방법을 사용한다. 가장 대표적인 방법은 내리막 경사법(gradient descent method)이다. 이 방법은 현재 위치에서 경사가 가장 급하게 하강하는 방향을 찾고 그 방향으로 약간 이동하여 새로운 위치를 잡는다. 이 과정을 반복함으로써 가장 낮은 지점을 찾아간다.

최고 점을 최대화 문제에서는 경사가 가장 급하게 상승하는 방향을 찾아 그 방향으로 이동하면 된다. 이 경우는 오르막 경사법(gradient ascent method)라 부른다. 각각의 방법에서의 갱신 함수는 다음과 같다.

$$\theta_{t+1} = \theta_t - \rho \frac{\partial J}{\partial \theta}|\theta_t$$

$$\theta_{t+1} = \theta_t + \rho \frac{\partial J}{\partial \theta}|\theta_t$$

$\frac{\partial J}{\partial \theta}|\theta_t$$\theta_t$에서의 도함수 값이며 이동 방향을 나타낸다. $\rho$는 학습 률(learning rate)이며, 이동량이다. 학습률을 너무 크게 하면 최저 점을 중심으로 좌우로 왔다갔다하는 진자 현상이 발생하고, 너무 작게 하면 수렴 속도가 느려진다. 따라서 적당한 학습률의 설정은 매우 중요하다.

내리막 경사법은 전형적인 욕심 알고리즘이다. 과거 또는 미래를 고려하지 않고 현재 상황에서 가장 유리한 다음 위치를 찾아 그곳으로 이동하는 연산만을 사용한다. 따라서 지역 최적 점으로 수렴하고 끝날 가능성을 가진 알고리즘이다.

11.2.3 라그랑제 승수

어떤 조건이 주어지고 그 조건을 만족하는 상황에서 최고 또는 최저 값을 갖는 지점을 찾는 조건부 최적화(contrained optimization) 문제도 있다. 예를 들어, $J(\theta) = \theta_1^2 + 2\theta_2^2$이라는 함수를 최소화 하느 점은 (0, 0)이다. 하지만 $2\theta_1 + \theta_2 = 1 $이라는 조건 하에 최소 점을 구하려 한다면 문제는 복잡해진다.

간단한 방법은 조건 식을 풀어 변수 하나를 줄이고 그 결과를 목접 함수에 대입하여 식을 정리하는 것이다. 하지만 대부분의 문제는 이러한 방법을 적용하기에는 복잡하다. 이 때에 라그랑제 승수를 사용할 수 있다.

조건식을 $f_i(\theta)$, 목적 함수를 $J(\theta)$라 하여보자. 조건 식은 여러개가 될 수 있다. 앞의 예에서 문제의 조건은 등식으로 구성되어 있다. 이러한 문제를 등식 조건부 최적화 문제(equality constrained optimization problem)이라 부른다. 이 문제를 해결하기 위한 라그랑제 함수(Lagrange function)은 다음과 같다.

$$L(\theta, \lambda) = J(\theta) - \sum_{i=i}^n \lambda_i f_i(\theta)$$

조건 식에 할당된 $\lambda$를 라그랑제 승수(Lagrange multiplier)라 부른다. 최대화 문제인 경우 $\sum$앞의 -를 +로 바꾸어 주면 된다. 이제 풀이법은 간단하다. 라그랑제 함수를 $\theta$$\lambda$로 미분한 식을 0으로 놓고 구한 해가 바로 $\hat{\theta}$이다.

조건이 등식이 아닌 경우엔 조금 더 복잡해진다. 바로 부등식 조건부 최적화 문제(inequality constrained optimization problem)이다. 이 문제는 Karush-Kuhn-Tucker (KKT) 조건을 사용하여 푼다. KKT 조건은 세 종류의 조건으로 구성된다. 첫 번째 조건은 라그랑제 함수를 $\theta_i$로 미분한 식이 0이 되어야 한다는 것이다. 매개 변수는의 수 만큼의 식을 얻게 된다. 두 번째 조건은 모든 라그랑제 승수가 0보다 크거나 같아야 한다는 것이다. 마지막 조건은 모든 조건식에 대해 $\lambda_i = 0$이거나 $f_i(\theta) = 0$이 되어야 한다는 것이다. 이 KKT 조건은 필요 조건이다. 따라서 원래 조건부 최적화 문제의 해는 반드시 KKT 조건을 만족해야 한다.

11.2.4 최적화 알고리즘과 패턴 인식 문제들

이 책에서 다루는 패턴 인식 문제들에 해당하는 다양한 최적화 문제들과 그들이 사용한 최적화 알고리즘을 정리하여 보여주고 있다.

11.3 시뮬레이티드 어닐링

최소화 문제를 가지고 설명을 시작하여 보자. 시뮬레이티드 어닐링(simulated annealing, SA)의 기본 틀은 내리막 경사법과 같다. 하지만 내리막 경사법은 매 반복마다 해를 하강시키는 연산만 사용하는데 SA는 조건에 따라 해를 상승시키기도 한다. 이 조건은 온도라는 의미를 갖는 변수 T에 따라 조절되는데 초기에는 온도가 높아 하강과 상승이 비교적 혼합되어 나타난다. 하지만 시간이 지남에 따라 온도를 낮추어 가는데 온도가 낮으면 상승할 확률은 줄어들어 내리막 경사법에 가까워진다. SA는 이러한 방법으로 지역 최적 점을 탈출할 수 있는 기회를 확보하였다.

SA의 성능을 좌우하는 가장 중요한 요소 중의 하나는 온도 T이다. 온도는 큰 값을 가지고 출발하여 루프를 한 번 돌 대마다 일정 양만큼씩 줄여 나가서 마지막에는 0이 되도록 한다. 만일 루프의 반복 회수 $t_{\text{max}}$를 미리 알 수 있다면 가장 단순한 방법은 아래 식을 이용하여 선형적으로 줄여 나가는 것이다.

$$T = T - T/t_{\text{max}}$$

11.4 유전 알고리즘

유전 알고리즘은 미분법, 시뮬레이티드 어닐링, 진화 전략과 명확한 차별성을 가진다. 가장 두드러진 부분은 알고리즘이 다루는 해의 개수에 있다. 기존 알고리즘은 하나의 초기 해를 생성한 후 적절한 연산을 사용하여 이것을 조금씩 개선해 나간다. 하지만 유전 알고리즘은 초기 해를 여러 개 생성하여 해 집단(population)을 구성하고 해 집단을 개선해 나간다. 생물 종이 많은 개체로 구성되며 개체들이 교차(crossover)와 변이(mutation)을 통해 세대를 거치면서 조금씩 진화하는 방식과 유사하게 동작하는 것이다.

11.4.1 원리: 내리막 경사법, 시뮬레이티드 어닐링, 그리고 유전 알고리즘

다음은 유전 알고리즘의 추상화 버전이다.

  1. 초기 해 집단 P를 설정한다. // P는 여러 개의 해를 가짐
  2. P의 해들을 평가하여 적합도를 부여한다.
  3. P에서 두 개의 해 $\theta_1, \theta_2$를 선택한다. // 높은 적합도의 해가 선택 확률 높음
  4. $\theta_1$$\theta_2$를 교차시키고 변이 연산을 가하여 자식 해 $\theta'$를 얻는다.
  5. $\theta'$를 P에 대치한다.
  6. 멈춤 조건에 도달할 때 까지 3에서 5를 반복한다.

유전 알고리즘은 해 집단 P를 개선해 나간다. 해 집단 내의 해들의 품질을 평가하여 그것을 해의 적합도(fitness)로 삼는다. 해 집단에서 두 개의 해를 선택하는데 높은 적합도의 해가 선택될 확률이 높도록 한다. 부 개의 부모 해는 교차를 거쳐 자식 해를 만들어 주고 이 자식 해에 변이 연산을 가한다. 이렇게 얻은 자식 해는 부모의 형질을 이어 받는다. 마지막으로 P에 있는 기존 해 하나를 선택하여 제거하고 대신 자식 해를 삽입하는 대차가 일어난다. 이 과정을 반복하면 해 집단의 품질은 조금씩 향상된다.

시뮬레이티드 어닐링과 유전 알고리즘은 확률 알고리즘(stochastic algorithm)이다. 이들은 수행 할 때마다 다른 해를 출력한다.

11.4.2 유전 알고리즘의 구조

다음은 유전 알고리즘은 보다 구체화 시킨 것이다.

  1. 초기 해 집단을 P를 설정한다.
  2. P의 해들의 품질을 평가한다.
  3. P에서 가장 우수한 해를 $\hat{\theta}$에 저장한다.
  4. P의 해들에게 적합도를 부여한다.
  5. for(i = 1 to k) {
  6. P에서 두 개의 해를 선택하여 이들을 $\theta_1, \theta_2$라 한다.
  7. $\theta_i' = \text{crossover}(\theta_1, \theta_2) $ // 교차
  8. $\text{mutation}(\theta')$ // 변이
  9. $\theta'$의 품질을 평가한다.
  10. }
  11. $\theta_1', \dots, \theta_k'$를 P에 대치한다.
  12. $\theta_1', \dots, \theta_k'$에서 가장 우수한 해가 $\hat{\theta}$보다 좋으면 그것으로 대치한다.
  13. 멈춤 조건에 도달할 때 까지 4에서 12까지의 과정을 반복한다.

먼저 해 집단(population)을 생성한다. 해 집단에는 여러 개의 해(solution)가 들어있는데 해의 개수를 n이라 하자. 해는 보통 염색체(chromosome) 또는 개체(individual)라고도 부른다. 이들 해는 보통 난수를 생성하여 만든다. 다음 해의 품질에 따라 적합도(fitness)를 부여하고, 4에서 12까지의 과정을 수행하면 한 세대(generation)가 지났다고 말한다. 세대가 반복됨에 따라 해 집단의 품질이 조금씩 진화(evolution)될 것이다.

부모해를 선택할 때 중요한 규칙이 있다. 바로 높은 적합도를 가진 해가 선택될 확률이 높아야 한다는 것이다. 하지만 아무리 못난 해라도 선택 확률을 0으로 하면 안된다. 열성 개첼도 생존 기회가 주어진다고 보면 된다. 변이 연산에서는 엉뚱한 자식 해를 만들 가능성을 추가로 열어 놓는다. 이러한 가능성은 지역 최적점을 탈출하는 중요한 매커니즘을 제공한다.

안정 상태형과 세대형

자식해를 만들 때, k=1로 두면 한 세대에 걸쳐 하나의 새로운 해가 등장하는 셈이다. 이러한 방식을 안정 상태형(steady-state) 유전 알고리즘이라 부른다. 반면 k=n으로 하면 한 세대 동안 해 집단의 모든 해가 새로운 해로 대치된다. 이런 방식은 세대형(generational) 유전 알고리즘이라 한다. 한정 상태형은 한 세대를 거치는데 시간이 적게 걸리지만 수렴 속도가 느려 평균 적합도가 느리게 향상될 것이다. 세대형에 가까울 수록 반대의 특징을 지닌다.

해 표현과 초기 해 생성

어떤 문제가 주어지면 가장 먼저 해야 할 일이 해를 어떻게 표현할 지 결정하는 것이다. 가장 일반적인 해 표현은 m개의 크기를 갖는 벡터로 표현하는 것이다. 해 전체를 염색체라 부르고 해를 구성하는 가장 작은 단위를 유전자(gene)라 부른다. 염색체를 1차원 배열 C[m]으로 표현하기로 하자. m은 염색체를 구성하는 유전자의 개수이다.

초기 해는 보통 난수를 사용하여 임의로 생성하도록 한다.

해 집단의 크기는 사용자가 설정해야 하는 매개 변수 중 하나인데 다른 여러 매개 변수와 조화롭게 설정해야 한다.

멈춤 조건

수렴했는지 여부를 어떻게 판단할 것인지의 문제가 있다. 어떤 상황에서는 주어진 계산 자원의 한계 때문에 수렴 이전에라도 멈추어야 할 수도 있다. 보통 다음 조건 중의 하나를 사용하든지 아니면 두 개 이상의 조건을 and 또는 or로 조합한 복합 조건을 사용한다.

  • 주어진 계산 시간이 지났다.
  • 세대가 주어진 최대 세대에 도달하엿다.
  • 여러 세대에 걸쳐 더 이상 좋은 해가 발생하지 않는다.
  • 해 집단의 평균 적합도가 여러 세대에 걸쳐 더 이상 향상되지 않는다.

11.4.3 유전 연산

적합도 계산

적합도를 계산하기 위해서는 먼저 해의 품질을 계산해야 한다. 적합도 계산을 위한 첫 번째 방법은 해의 품질 그 자체를 적합도로 취하는 것이다. 이 방법은 적절할 수도 잇고 그렇지 않을 수도 있다. 보통 수행 초기에는 해의 품질이 크게 차이가 나서 우열이 두드러지는데 세대가 지남에 따라 해들의 품질이 모두 높아져 그들 간의 차이가 매우 작아 질 수 잇다. 이러한 상황에서는 모든 해들이 부모로 선택될 확률이 거의 같아 더 이상 진화가 일어나지 않을 수 있다.

두 번째로 품질 비례 방법이 잇다. 이 방법은 가장 좋은 해와 가장 나쁜 해를 기준으로 삼고 다음과 같이 적합도를 계산한다.

$$f_i = (q_i - q_{worst}) + (q_{best} - q_{worst})/(r-1)$$

$q_{best}$$q_{worst}$는 각각 가장 좋은 해와 가장 나쁜 해의 품질이다. $q_i$$f_i$는 해 i의 품질과 적합도이다. r은 사용자가 설정하는 매개 변수인데 이 값이 클수록 좋은 해에게 더 많은 선택 기회를 주는 셈이다. 좋은 해의 선택 확률을 높이면 선택 압력(selection pressure)이 높아진다라고 표현한다.

세 번째 방법은 순위 기반(rank-based) 방법이다. 이 방법은 모든 해를 품질에 따라 정렬한 후 $ f_i = q(1-q)^{i-1}$를 사용하여 순위에 따라 적합도를 배정한다. $f_i$는 정렬된 해 집단에서 i번째 좋은 해의 적합도이다. q는 (0,1)사이를 가지는 사용자 매개 변수인데 이 값이 클수록 선택 압력이 높아진다.

공유(sharing) 기법을 사용하여 앞에서 구한 적합도 $f_i$를 변환할 수도 있다. 이 기법은 해 집단의 다양성(diversity)를 유지하려는데 그 목적이 있다. 해 집단의 다양성이 높다는 것은 전체 탐색 공간을 골고루 살펴본다는 것을 뜻하므로 전역 최적 점에 도달하는데 크게 도움이 된다. 기본적인 아이디어는 해 집단 내에서 서로 가까운 해들의 적합도를 낮추어 그들의 선택 기회를 낮추는 것이다. 상대적으로 다른 해들과 멀리 떨어져 있는 해는 적합도를 높여준다. 다음의 방법은 새로운 적합도 $\hat{f}_i$를 계산한다.

$$\hat{f}_i = \frac{f_i}{\sum_{j=1}^n s(d_{ij})}$$

$d_{ij}$는 해 i와 j의 거리이며, $s(d)$는 공유 함수로서 d가 클 수록 작아지는 함수이다.

선택

선택을 위한 기본 원칙이 있다. 우수한 해가 선택될 확률이 커야 한다는 것이다. 그렇지만 열등한 해도 낮은 확률로 선택될 기회가 주어져야 한다.

단순하지만 널리 사용되는 방법은 룰렛 휠(roulette wheel) 선택이다. 이 방법은 [0, 1] 구간을 해의 적합도에 따라 분리한다.

토너먼트 선택이라는 재미있는 방법도 있다. 우선 임의로 두 개의 해를 선택한다. 그런 후 난수를 생성하여 그에 따라 우수 해와 열등 해 중의 하나를 선택한다.

교차와 변이

교차는, 자식 부모와 달라지지만 그 형질을 이어받아야 한다. 가장 널리 사용되는 교차 연산은, [1, m-1]사이의 임의의 정수를 생성하여 이를 자름 선으로 이용한다. 자름 선을 중심으로 염색체를 분할한 후 부모1과 부모2에서 교대로 유전자를 복사하여 자식 해를 만든다. 임의의 정수를 세 개 생성하여 3점 교차를 할 수도 있다. 자름 선의 수가 많을수록 교란(perburbation)이 심해 진다. 즉, 자식 해는 부모를 덜 닮게 된다. 자름 선의 개수는 사용자 매개 변수인데 선택 압력과 관련이 잇다.

자름 선을 사용하지 않는 균등 교차(uniform crossover) 방법도 잇다. 이 방법은 유전자 별로 [0, 1]사이의 난수를 생성하고 이 난수가 미리 설정한 임계값 t 보다 작으면 부모1로부터 유전자를 받고 그렇지 않으면 부모2로터 받는다. t는 0.5로 설정하거나 부모의 적합도를 기준으로 좋은 부모에서 더 많은 유전자를 물려받도록 할 수도 있다.

실수 염색체를 위한 산술 교차(arithmetic crossover)도 있다. 이 교차에서는 부모 유전자의 평균을 자식 유전자 값으로 취한다.

변이의 목적은 부모 해가 가지지 못한 형질을 부여하는 것이다. 가장 널리 사용되는 변이 방법은 각 유전자 별로 난수를 발생시키고 그것이 미리 설정한 변이 확률 $p_m$보다 작으면 0은 1로 1은 0으로 반전시킨다. 변이 확률은 시작부터 끝까지 같은 값을 사용하여도 되지만, 시간이 지남에 따라 줄여 나갈 수도 있다. 전자를 균등 변이라 하고 후자는 비균등 변이라고 한다. 시간이 지날 수록 최적 점에 가까워 지므로 낮은 변이 확률을 사용하여 교란을 줄이는 것이 비균등 변이의 취지이다. 실수 염색체의 경우 변이를 가할 유전자를 선택한 뒤에는 또 다른 난수를 발생시켜 이를 선택한 유전자에 더하는 방법을 사용할 수 있다.

대치

자식 해를 k개 생성한 뒤에는, 해 집단에서 기존 해 k개 를 들어 내고 자식 해를 넣어야 한다. 이를 대치(replacement)라 한다. 일반적인 상황에서는 k개의 자식 해를 하나씩 대치하면 된다. 어떤 자식 해를 대치할 때 그 순간 해 집단 내에서 적합도가 가장 낮은 해를 찾아 대치할 수 있다. 하지만 이 경우, 수렴은 빨라지나 설익은 수렴의 위험이 있다. 대안으로 부모 중 적합도가 낮은 해를 대치하는 것이다. 부모와 자식은 닮았으므로 다양성을 유지하는데 도움을 준다.

유전 알고리즘이 엘리티즘(elitism)을 사용한다는 말은 현 세대에서 가장 좋은 해s가 다음 세대에 반드시 생존하도록 보장함을 뜻하낟. 이를 구현하기 위해서는 다음 세대의 해 집단을 조사하여 s가 없어졌다면 가장 나쁜 해 또는 임의로 선택한 해를 들어내고 s를 넣어주면 된다.

11.4.4 매개 변수 설정과 선택 압력

유전 알고리즘은 공간 탐색 알고리즘이다. 공간 탐색은 탐사(exploitation)와 탐험(exploration) 두 가지 관점에서 바라볼 수 있다. 탐사는 어느 지점을 중심으로 그 근반만을 뒤져 가장 좋은 점을 찾아 나가지만 탐험은 전체 탐색 공간을 두루두루 살핀다. 탐사형은 수렴이 빠르지만 지역 최적 점에 빠질 가능성이 높은 반면 탐험형은 지역 최적 점에 빠질 가능성이 낮은 반면 시간이 너무 많이 소요된다.

유전 알고리즘은 탐험과 탐사의 절묘한 조화를 추구한다고 볼 수 있다. 해 집단의 다양성을 유지함으로써 탐험을 실현하는 동시에 우수한 해에게 더 많은 기회를 줌으로써 탐사도 실현한다. 이는 여러 가지 매개 변수를 적절히 설정할 때만 이룰 수 있다. 다음에서 여러 매개 변수가 선택 압력에 어떤 영향을 미치는지를 보인다. 선택 압력이 높을 수록 탐사형에 가까워진다.

  • 해 집단 / 해의 개수 n이 클 수록 / 선택 압력이 낮음
  • 순위 기반 적합도 계산 / q가 클 수록 / 선택 압력이 높음
  • 품질 비례 적합도 계산 / r이 클 수록 / 선택 압력이 높음
  • 토너먼트 선택 / t가 클수록 / 선택 압력이 높음
  • 교차 / 자름 선이 많을수록 / 선택 압력이 낮음
  • 변이 / $p_m$이 클수록 / 선택 압력이 낮음
  • 공유 / 사용하면 / 선택 압력이 낮음
  • 엘리티즘 / 사용하면 / 선택 압력이 높음
  • 대치 / 가장 나쁜 해를 대치하면 / 선택 압력이 높음

선택 압력이 지나치게 높다면 설익은 수렴에 빠질 것이다. 또 몇 세대가 지나지 않아 해 집단의 다양성이 매우 낮아져 더 이상 적합도 향상이 발생하지 않을 수 있다. 반대로 선택 압력이 낮다면 해 집단의 향상이 너무 느려질 것이다.

11.4.5 찬반 논쟁

유전 알고리즘은 수행 중에 난수를 사용하기 때문에 수행할 때마다 새로운 해를 갖는다. 여기에 찬반 의견이 있다.

찬성

  • 새로운 개념과 연산들이 재미있다.
  • 기존 알고리즘의 한계를 극복할 것 같다.
  • 시간을 더 주면 더 좋은 해를 기대할 수 있다.
  • 문제에 대한 제약 조건이 적고 응용 범위가 넓다.
  • 실제 실험해 보니 성능이 기존 알고리즘보다 좋다.

반대

  • 수학적 토대가 약하여 미덥지 못하다.
  • 수행할 때마다 다른 해를 내면 어떡하나?
  • 수행 시간이 길어 실시간 환경에서는 활용이 불가능하다.
  • 실제 실험해 보니 성능이 기존 알고리즘보다 나쁘다.

11.5 메타 휴리스틱

이 장에서 소개한 알고리즘은 대부분 메타 휴리스틱(meta heuristic)이다. 어떤 알고리즘을 구성하는 연산이 상황에 따라 보다 구체적인 알고리즘으로 대체되는 성질을 가진 경우 그 알고리즘을 메타 휴리스틱이라고 부른다.


Add a Comment Trackback