모의 담금질(Simulated Annealing, SA)은 전역 최적해 탐색을 위한 확률 기반 휴리스틱 기법이다. 이 방법은 고온 상태에서 시작하여 점차 온도를 낮추면서 해의 공간을 탐색하며, 초기에는 덜 유리한 해도 일정 확률로 수용함으로써 국소 최적해에 빠지는 것을 방지한다.
기본적인 알고리즘 흐름은 다음과 같다:
- 초기 온도 \( T_0 \), 감소율 \( d \) (\( 0 < d < 1 \)), 최저 온도 \( T_{\text{min}} \) 을 설정한다.
- 현재 해와 비용을 초기화한다. <3>현재 온도가 최저 온도보다 높을 동안 반복:
- 주변 해를 무작위로 생성한다.
- 새로운 해의 비용과 현재 해의 비용 차이 \( \Delta \) 를 계산한다.
- \( \Delta < 0 \) (더 좋은 해)이면 해를 채택한다.
- 그렇지 않으면, \( e^{-\Delta / T} \) 의 확률로 받아들인다.
- 온도를 \( T \leftarrow T \times d \) 로 감소시킨다.
다음은 일반적인 C++ 구현 형태이다:
#include <random>
#include <cmath>
#include <ctime>
double current_cost, best_cost;
double T = 2000.0;
const double decay_rate = 0.995;
const double min_temp = 1e-8;
void simulated_annealing() {
std::mt19937 gen(std::time(0));
std::uniform_real_distribution<> dis(0.0, 1.0);
while (T > min_temp) {
// 새로운 후보 해 생성
auto [new_x, new_y] = generate_neighbor();
double new_cost = compute_cost(new_x, new_y);
double delta = new_cost - current_cost;
// 더 나은 해이거나 확률적으로 채택
if (delta < 0 || exp(-delta / T) > dis(gen)) {
current_cost = new_cost;
update_state(new_x, new_y);
if (new_cost < best_cost) {
best_cost = new_cost;
save_best_solution();
}
}
T *= decay_rate;
}
}
응용 사례: 기하 중심 최적화 (UVA 10228)
평면 상의 \( n \) 개 점에 대해, 모든 점까지의 거리 합을 최소화하는 위치를 찾는 문제다. 초기 추정치로 좌표 평균값을 사용하고, 이를 중심으로 주변 탐색을 수행하면 효율성이 높아진다.
double calc_total_distance(double x, double y) {
double total = 0;
for (int i = 0; i < n; ++i) {
total += sqrt((x - points[i].x)*(x - points[i].x) +
(y - points[i].y)*(y - points[i].y));
}
return total;
}
void sa_location() {
double cx = avg_x, cy = avg_y;
double best = calc_total_distance(cx, cy);
double cur = best;
double T = 2000;
while (T > 1e-10) {
double nx = cx + (2.0 * rand() / RAND_MAX - 1.0) * T;
double ny = cy + (2.0 * rand() / RAND_MAX - 1.0) * T;
double nc = calc_total_distance(nx, ny);
double diff = nc - cur;
if (diff < 0 || exp(-diff / T) > (double)rand()/RAND_MAX) {
cx = nx; cy = ny; cur = nc;
if (cur < best) best = cur;
}
T *= 0.996;
}
printf("%.0f\n", best);
}
최대화 문제: 폭탄 공격 범위 최적화
적군 유닛을 최대한 많이 포함하면서 건물은 피해가는 원을 배치하는 문제다. 여기서는 목표가 최대화이므로, \( \Delta > 0 \) 인 경우를 더 좋은 해로 간주한다.
int evaluate_bomb(double x, double y) {
double radius = 1e9;
for (auto& b : buildings)
radius = fmin(radius, distance(x, y, b.x, b.y) - b.r);
int count = 0;
for (auto& e : enemies)
if (distance(x, y, e.x, e.y) <= radius)
++count;
return count;
}
채택 조건은 \( \Delta > 0 \) 또는 \( e^{-\Delta/T} > r \) (단, \( \Delta = \text{new} - \text{current} \)) 로 수정된다.
조합 최적화: 데이터 균등 분할
배열을 \( m \) 그룹으로 나누어 각 그룹의 평균과 전체 평균의 편차 제곱합을 최소화하는 문제다. 매번 순열을 무작위로 섞고, 그리디하게 가장 작은 그룹에 값을 추가하는 전략을 사용할 수 있다.
double compute_variance() {
double mean = total_sum / m;
double var = 0;
for (int i = 0; i < m; ++i)
var += pow(group_sum[i] - mean, 2);
return sqrt(var / m);
}
void sa_partition() {
for (int iter = 0; iter < 100000; ++iter) {
std::random_shuffle(data, data + n);
std::fill(group_sum, group_sum + m, 0);
for (int i = 0; i < n; ++i) {
int idx = std::min_element(group_sum, group_sum + m) - group_sum;
group_sum[idx] += data[i];
}
double cost = compute_variance();
if (cost < best_variance)
best_variance = cost;
}
}
복잡한 상태 변화: 색칠 게임 최적화
격자판에서 인접한 칸의 색상이 다를 때마다 점수를 얻는 문제다. 두 칸의 색을 바꾸는 연산을 수행할 때, 전체 점수 변화량을 국부적으로 계산하면 효율이 향상된다.
int local_delta(int x1, int y1, int x2, int y2) {
int old_score = 0, new_score = 0;
for (auto [dx, dy] : directions) {
int nx1 = x1+dx, ny1 = y1+dy;
int nx2 = x2+dx, ny2 = y2+dy;
if (valid(nx1, ny1)) old_score += (grid[x1][y1] != grid[nx1][ny1]);
if (valid(nx2, ny2)) old_score += (grid[x2][y2] != grid[nx2][ny2]);
swap(grid[x1][y1], grid[x2][y2]);
if (valid(nx1, ny1)) new_score += (grid[x1][y1] != grid[nx1][ny1]);
if (valid(nx2, ny2)) new_score += (grid[x2][y2] != grid[nx2][ny2]);
swap(grid[x1][y1], grid[x2][y2]); // 복구
}
return new_score - old_score;
}
핵심 요약
- 모의 담금질은 국소 최적해 회피를 위해 덜 유리한 해도 확률적으로 수용한다.
- 매개변수(초기 온도, 감소율, 종료 조건) 조정이 성능에 큰 영향을 준다.
- 시간 제한 내 여러 번 실행하거나, 시드 조정을 통해 결과 안정성을 높일 수 있다.
- 비용 함수 및 이웃 해 생성 전략 설계가 성공 여부를 결정한다.