담금질 기법

담금질 기법

담금질 기법(영어: simulated annealing)은 전역 최적화를 위한 휴리스틱 알고리즘으로, 이산 문제와 조합 문제를 해결하는 데 특히 효과적입니다.

이 알고리즘은 야금학의 풀림 과정에서 영감을 받았습니다. 풀림은 금속을 가열한 뒤 서서히 냉각하여 결정화 정도를 높이고 결함을 줄이는 기법입니다. 전수 탐색 문제에서 풀림을 시뮬레이션하면 자유 변수가 많은 함수의 전역 최솟값을 근사적으로 찾는 데 사용할 수 있습니다.

담금질 기법을 이용한 일변수 함수의 최대화

이 알고리즘은 확률적이며 수렴에 대해 거의 아무런 보장도 하지 않지만, NP-완전 문제를 풀 때 실전에서 잘 작동합니다. 때로는 대회에서 정상적인 풀이가 존재하는 어려운 조합 문제를 이 방법으로 통과시키기도 합니다. 예를 들어, 일다르 가이눌린(Ildar Gainullin)은 8학년 때 부분집합 DP 문제인 div2E를 담금질로 통과시킨 적이 있습니다.

#알고리즘 개요

구체적인 예로 외판원 문제를 살펴보겠습니다:

도로로 서로 연결된 $n$개의 도시가 있습니다. 이 도시들 사이에 각 도시를 정확히 한 번씩만 지나는 가장 짧은 순환 경로를 만들어야 합니다.

어떤 상태 $x$에 대한 함수 $f(x)$가 있고, 우리가 이 함수를 최소화하려 한다고 합시다. 이 경우 $x$는 정점(도시)을 방문할 순서대로 나열한 순열이고, $f(x)$는 그에 해당하는 경로의 길이입니다.

어떤 상태 $x_0$를 기본 해로 잡고, 이를 개선해 나가도록 합시다. 이 예시에서는 무작위 순열을 초기 경로로 잡을 수 있습니다.

온도 $t$를 도입합시다. 이는 처음에 1로 설정되는 어떤 실수로, 최적화 과정에서 변화하며 이웃 상태로 넘어갈 확률에 영향을 줍니다.

최적해에 도달하거나 시간이 다 될 때까지 다음 단계를 반복합니다:

  1. 어떤 공식 $T$에 따라 온도를 $t_{k} = T(t_{k-1})$로 낮춥니다.
  2. $x$의 임의의 이웃을 고릅시다. 즉, $x$를 약간 변경하여 얻을 수 있는 어떤 상태 $y$를 고릅니다.
  3. $p(f(x), f(y), t_k)$의 확률로 $x \leftarrow y$를 대입하고, 그렇지 않으면 $x$를 그대로 둡니다.

각 단계를 구현할 때에는 많은 자유가 있습니다. 주요 휴리스틱 고려 사항은 다음과 같습니다:

  1. 최적화 초기에는 해가 어차피 좋지 않으므로, 높은 온도를 감수하고 더 나쁜 상태로 옮겨 갈 위험을 무릅쓸 수 있습니다. 반대로 막바지에는 해가 거의 최적에 가까우므로, 그동안의 진전을 잃고 싶지 않습니다. 온도는 초기에 높아야 하며 끝으로 갈수록 천천히 낮아져야 합니다.

  2. 함수 $f(x)$가 이 변화에 대해 「매끄러울」 때, 즉 크게 변하지 않을 때 알고리즘이 더 잘 동작합니다.

  3. 새로운 상태가 이전 상태보다 나쁘다면 확률은 더 작아야 합니다. 또한 온도가 높을 때는 확률이 더 커야 합니다.

예를 들어, 외판원 문제에서는 다음과 같이 할 수 있습니다:

  1. $t_k = \gamma \cdot t_{k-1}$이며, 여기서 $\gamma$는 1에 가까운 어떤 수(예를 들어 $0.99$)입니다. 이 값은 계획한 반복 횟수에 따라 정해야 합니다. 낮은 온도에서의 최적화는 거의 아무것도 바꾸지 못하기 때문입니다.

  2. 순열의 경우, 이러한 최소한의 변화로는 예를 들어 임의의 두 원소를 교환(swap)하는 것을 들 수 있습니다.

  3. $y$가 더 나쁘지 않다면, 즉 $f(y) \leq f(x)$라면, 어떤 경우에도 $y$로 이동합니다. 그렇지 않다면 $p = e^\frac{f(x)-f(y)}{t_k}$의 확률로 $y$로 이동합니다. 이는 음수의 지수 함수이므로 $(0, 1)$ 구간의 확률을 얻게 됩니다.

하지만 구체적인 휴리스틱을 선택하는 데 「황금률」은 존재하지 않는다는 점을 인식하는 것이 중요합니다. 알고리즘의 모든 구성 요소는 서로에게, 그리고 문제에 크게 의존합니다.

#구현

실제로 이 알고리즘을 다른 문제에 적용해 봅시다:

$n \times n$ 크기의 체스판과 $n$개의 퀸이 주어집니다. 퀸들이 서로 공격하지 않도록 배치해야 합니다.

상태는 마찬가지로 $0$부터 $(n-1)$까지의 수로 이루어진 순열로 인코딩하겠습니다. $i$번 퀸은 $i$번째 행과 $p_i$번째 열이 교차하는 곳에 놓입니다.

이러한 표현은 가능한 모든 배치를 나타내지는 않지만, 오히려 이 점이 좋습니다. 퀸들이 세로나 가로로 서로를 공격하는 배치는 확실히 고려 대상에서 제외되기 때문입니다.

성공적으로 배치된 퀸의 수와 같은 함수 $f(p)$를 선택합시다.

대략 동등한 C++ 코드는 다음과 같습니다:

const int n = 100;  // размер доски
const int k = 1000; // количество итераций алгоритма

int f(vector<int> &p) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        int d = 1;
        for (int j = 0; j < i; j++)
            if (abs(i - j) == abs(p[i] - p[j]))
                d = 0;
        s += d;
    }
    return s;
}

// генерирует действительное число от 0 до 1
double rnd() { return double(rand()) / RAND_MAX; }

int main() {
    // генерируем начальную перестановку
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    shuffle(v.begin(), v.end());
    int ans = f(v); // текущий лучший ответ 

    double t = 1;
    for (int i = 0; i < k && ans < n; i++) {
        t *= 0.99;
        vector<int> u = v;
        swap(u[rand() % n], u[rand() % n]);
        int val = f(u);
        if (val > ans || rnd() < exp((val - ans) / t)) {
            v = u;
            ans = val;
        }
    }

    for (int x : v)
        cout << x + 1 << " ";

    return 0;
}

여기서 빈 대각선의 개수를 세는 작업은 $O(n^2)$에 동작합니다. 이를 $O(n)$까지 최적화하여 $O(n)$배 더 많은 반복을 수행할 수 있습니다. 각 대각선마다 그것이 점유되었는지 여부를 저장하는 불리언 배열을 만들면 됩니다. 이 최적화를 적용하면 informatics의 이 문제를 통과할 수 있을 것입니다.

연습 문제. 재계산을 $O(1)$로 최적화하십시오.

참고. 사실 퀸 문제는 구성적으로 풀 수 있습니다.