[인공지능/최적화/AI] 휴리스틱 알고리즘 SA(Simulated Annealing)란 무엇인가? 국소해를 넘어서 더 좋은 해를 찾는 방법

안녕하세요.
“기억하고자 하는 모든 것”을 담아내는 “리멤버미” 입니다.

 

최적화 문제를 풀다 보면 자주 부딪히는 벽이 있습니다.
바로 지금 당장은 좋아 보이지만 전체적으로는 최선이 아닌 해, 즉 local minimum(국소 최솟값) 입니다.

이럴 때 자주 등장하는 대표적인 휴리스틱 알고리즘이 바로 SA, Simulated Annealing 입니다.
SA는 금속을 천천히 식히며 더 안정적인 상태로 가는 과정에서 아이디어를 가져온 확률적 최적화 기법으로, 1983년 Kirkpatrick, Gelatt, Vecchi에 의해 대표적인 메타휴리스틱으로 정리된 방법입니다. 핵심은 초반에는 비교적 과감하게 탐색하고, 후반에는 점점 안정적으로 수렴하는 데 있습니다.

SA를 한 문장으로 설명하면

“지금보다 나쁜 선택도 가끔은 받아들이면서, local minimum에 갇히지 않고 더 좋은 해를 찾도록 만드는 알고리즘” 입니다.

보통 greedy 방식은 현재보다 더 나쁜 해를 거의 받아들이지 않기 때문에, 한 번 국소해에 빠지면 거기서 멈추기 쉽습니다. 반면 SA는 온도(temperature)가 높을 때는 더 나쁜 해도 일정 확률로 받아들이고, 시간이 지나며 온도를 낮춰 갈수록 점점 보수적으로 움직입니다. 이 구조 덕분에 초반에는 탐색 범위를 넓게 가져가고, 후반에는 좋은 해 주변을 정교하게 다듬는 식의 탐색이 가능합니다.

 

왜 이름이 Simulated Annealing일까?

이름 그대로 보면 어렵지 않습니다.

• Simulated: 실제 물리 현상을 계산적으로 흉내 낸다는 뜻
• Annealing: 높은 에너지 상태에서 천천히 식으며 더 안정적인 상태로 가는 과정

최적화 관점에서 보면, 우리가 찾고 싶은 해는 어떤 “에너지” 혹은 “비용 함수”를 최소화하는 상태라고 볼 수 있습니다. SA는 이 에너지 지형 위를 돌아다니면서, 초반에는 뜨겁게 흔들고 나중에는 천천히 식혀 가며 더 좋은 위치로 이동하는 방식입니다.

 

SA의 핵심 아이디어: 왜 일부러 나쁜 해를 받아들일까?

이 부분이 SA의 가장 중요한 포인트입니다.

일반적인 탐색에서는 새 후보해가 더 나쁘면 바로 버립니다.
그런데 그렇게만 하면 아래처럼 local minimum에 갇히기 쉽습니다.

 

 

예를 들어 현재 위치가 어느 골짜기의 바닥이라고 해보겠습니다.
지금 위치보다 더 좋은 곳으로 바로 가는 길이 없고, 잠깐 더 높은 언덕을 넘어야만 더 깊은 골짜기로 갈 수 있다면, “나빠지는 이동을 절대 허용하지 않는 알고리즘”은 그 언덕을 넘지 못합니다.

SA는 바로 이 문제를 해결하기 위해, 초반에는 나빠지는 이동도 일정 확률로 허용합니다.
그래서 local minimum을 빠져나와 더 좋은 basin으로 갈 가능성을 만들어 줍니다.

 

SA는 어떻게 동작할까?

동작 흐름은 생각보다 단순합니다.

1. 초기 해를 하나 정합니다.
2. 현재 해 주변의 이웃해(neighbor)를 만듭니다.
3. 새 해가 더 좋으면 받아들입니다.
4. 새 해가 더 나빠도 확률적으로 받아들일 수 있습니다.
5. 온도를 조금 낮추고 다시 반복합니다.
6. 최종적으로 가장 좋았던 해를 반환합니다.

수식으로 보면 더 쉬운 핵심

SA에서 자주 등장하는 식은 다음과 같습니다.

P = exp(-ΔE / T)

여기서

• ΔE: 새 해가 얼마나 나빠졌는지
• T: 현재 온도
• P: 그 나쁜 해를 받아들일 확률

의미는 직관적입니다.

• 나빠진 폭이 크면 확률이 작아집니다.
• 온도가 높으면 확률이 커집니다.
• 온도가 낮아지면 점점 나쁜 해를 잘 안 받게 됩니다.

즉, SA는 초반에는 “조금 돌아가도 된다”는 태도로 탐색하고, 후반에는 “이제는 좋은 방향 위주로 가자”로 바뀌는 알고리즘이라고 보면 됩니다.

 

냉각 스케줄이 중요한 이유

SA에서 성능을 크게 좌우하는 것이 바로 cooling schedule, 즉 냉각 스케줄입니다.

온도를 너무 빨리 낮추면 초반 탐색이 충분하지 않아 local minimum에 쉽게 갇힐 수 있습니다.
반대로 너무 천천히 낮추면 계산 시간이 길어집니다.
그래서 SA는 알고리즘 자체도 중요하지만, 초기 온도, 냉각률, 반복 횟수, 종료 조건 같은 하이퍼파라미터 설정이 결과 품질에 매우 큰 영향을 줍니다.

 

실무적으로 보면 SA는 “알고리즘 하나만 잘 고르면 끝”이 아니라,
문제에 맞게 온도와 이동 규칙을 얼마나 잘 설계하느냐가 성능을 좌우하는 방법이라고 보는 편이 더 정확합니다.

 

SA에서 꼭 알아야 할 3가지 구성 요소

1. 상태(State)

현재 해를 말합니다.
예를 들어 TSP라면 도시 방문 순서 하나가 상태가 됩니다.

2. 에너지 또는 비용 함수(Energy / Cost)

현재 해가 얼마나 좋은지 숫자로 평가하는 함수입니다.
최소화 문제라면 값이 작을수록 좋은 해라고 볼 수 있습니다.

3. 이웃 생성 방식(Neighbor)

현재 해에서 조금 바꾼 새로운 후보해를 만드는 규칙입니다.
예를 들어 순서를 바꾸거나, 위치를 교환하거나, 파라미터를 조금 흔드는 방식이 여기에 해당합니다.
실제로는 이 neighbor 설계가 SA 성능에 굉장히 큰 영향을 줍니다.

 

SA의 장점

SA가 오래 살아남은 이유는 분명합니다.

첫째, 구현 개념이 비교적 단순합니다.
복잡한 수학적 미분이 없어도 적용할 수 있는 경우가 많습니다.

둘째, local minimum 탈출 능력이 있습니다.
이게 단순 hill climbing보다 SA가 자주 언급되는 가장 큰 이유입니다.

셋째, 조합 최적화 문제에 잘 붙습니다.
TSP, 스케줄링, 배치 문제처럼 경우의 수가 너무 많아 exact method가 부담스러운 문제에 잘 어울립니다. 실제 교육 자료와 최적화 자료에서도 scheduling, combinatorial optimization, configuration 문제에 대한 대표적 예시로 자주 소개됩니다. VLSI layout 같은 구성 최적화 문제에서도 중요한 workhorse로 설명됩니다.

 

SA의 단점

물론 만능은 아닙니다.

가장 큰 단점은 파라미터 의존성입니다.
초기 온도, 냉각률, 반복 수를 어떻게 잡느냐에 따라 결과가 꽤 달라질 수 있습니다.

또한 전역 최적해를 항상 보장하는 것은 아닙니다.
이론적으로는 매우 천천히 냉각하면 좋은 성질이 있지만, 실제 문제에서는 계산 시간 제약 때문에 그렇게 이상적으로 돌리기 어렵습니다.

그리고 문제에 따라서는 neighbor 설계가 서툴면 탐색 효율이 크게 떨어집니다.
즉, SA는 이름만 가져다 붙인다고 잘 되는 알고리즘이 아니라, 문제 구조를 반영해 탐색 방식을 잘 설계해야 성능이 살아납니다.

 

SA는 어디에 쓰일까?

대표적으로는 이런 문제들에서 자주 쓰입니다.

• 외판원 문제(TSP)
• 생산 및 작업 스케줄링
• 레이아웃/배치 최적화
• 파라미터 튜닝
• 조합 최적화 전반

쉽게 말해, 정답을 정확히 찾기엔 너무 복잡하지만 꽤 좋은 해를 현실적인 시간 안에 찾고 싶은 문제에 잘 맞습니다.

 

한 번에 이해하는 비유

SA를 등산에 비유하면 이렇습니다.

• 처음에는 안개가 짙어서 지금 서 있는 봉우리가 최고인지 알기 어렵습니다.
• 그래서 초반에는 조금 내려가더라도 다른 길로 많이 움직여 봅니다.
• 시간이 지나 시야가 맑아지면 점점 좋은 방향으로만 움직입니다.
• 마지막에는 그동안 봤던 곳 중 가장 높은 지점에 가까운 곳에 머무르게 됩니다.

이 비유 하나로 SA의 성격이 꽤 잘 설명됩니다.
초반엔 탐색, 후반엔 수렴입니다.

 

마무리

Simulated Annealing의 핵심은 단순합니다.

“처음에는 과감하게 흔들고, 나중에는 천천히 안정화한다.”

그래서 SA는 local minimum이 많은 문제, 미분 기반 접근이 어렵거나 상태 공간이 복잡한 문제, 그리고 exact solution보다 현실적인 시간 내의 good solution이 더 중요한 문제에서 여전히 매우 유용합니다.

정리하면 SA는 무조건 좋은 방향만 고르는 알고리즘이 아니라, 때로는 돌아가는 선택도 허용하면서 더 큰 그림에서 좋은 해를 찾는 전략이라고 볼 수 있습니다.

처음 휴리스틱 최적화를 접하는 분이라면, GA나 DE보다 먼저 SA를 이해해 두는 것이 전체 최적화 알고리즘의 감을 잡는 데도 꽤 도움이 됩니다.

 

 

2026.04.07 - [기억하고 싶은 지식/python] - [simanneal / scipy_dual_annealing] Python으로 Simulated Annealing 시작하기: SA 패키지 사용법과 하이퍼파라미터 완전 정리

[simanneal / scipy_dual_annealing] Python으로 Simulated Annealing 시작하기: SA 패키지 사용법과 하이퍼파라미