시뮬레이티드 어닐링

컴퓨터과학·AI

한 줄 정의: 금속을 뜨겁게 달궜다가 천천히 식히면 더 안정된 결정 구조가 되는 원리(담금질)를 본떠, 처음에는 나쁜 방향으로도 과감히 옮겨 다니다가 점점 신중해지면서 최적에 가까운 답을 찾는 탐색 기법입니다.

쉽게 풀면

산 여러 개가 있는 지형에서 가장 높은 봉우리를 찾는다고 해봅시다. 무조건 "지금보다 높은 쪽"으로만 가면 근처의 작은 언덕 꼭대기에 갇혀 진짜 최고봉을 놓칠 수 있습니다(이런 함정을 국소최적해라고 부릅니다). 시뮬레이티드 어닐링은 처음에는 "온도"가 높다고 보고, 가끔은 일부러 낮은 쪽으로도 내려가 보면서 더 넓은 지역을 탐색합니다. 시간이 지나 온도가 식을수록 낮은 쪽으로 가는 것을 점점 허용하지 않고, 결국 가장 높은 봉우리 근처에 안착하게 됩니다. 당장 손해를 보는 선택도 확률적으로 받아들인다는 점이 탐욕 알고리즘과 가장 큰 차이입니다.

왜 중요한가

많은 실세계 최적화 문제는 변수 조합이 기하급수적으로 늘어나 모든 경우를 계산하는 것이 불가능하기 때문에, 시뮬레이티드 어닐링처럼 확률적으로 탐색 범위를 넓히면서도 점차 수렴시키는 메타휴리스틱 기법이 필요합니다. 국소최적해에 쉽게 갇히는 단순 탐욕 탐색의 한계를 보완할 수 있어, 조합 최적화·일정 계획·회로 설계·하이퍼파라미터 탐색 등 정확한 해를 구하기 어려운 다양한 공학·전산학 문제에서 실용적인 대안으로 폭넓게 다뤄집니다.

논문에서는 이렇게 쓰입니다

"공장 내 설비 배치 문제는 조합의 경우의 수가 방대하여, 시뮬레이티드 어닐링을 적용해 이동 거리를 최소화하는 배치안을 탐색하였다."

이 문장은 "가능한 조합이 너무 많아 일일이 다 계산할 수 없는 문제를, 시뮬레이티드 어닐링으로 충분히 좋은 해를 근사적으로 찾아냈다"는 뜻입니다. 최적화 문제(배치, 일정 계획, 회로 설계, 하이퍼파라미터 탐색 등)에서 정확한 최적해 대신 실용적으로 괜찮은 해를 빠르게 구할 때 자주 쓰입니다.

"차량 경로 문제의 초기 해를 시뮬레이티드 어닐링으로 개선하여 총 운행 거리를 기존 대비 유의하게 단축하였다."

배송 순서를 정하는 조합 문제에서, 시뮬레이티드 어닐링을 이용해 더 짧은 경로를 찾아냈다는 뜻입니다.

"인공신경망의 구조 탐색 과정에서 시뮬레이티드 어닐링 기반 탐색 전략을 도입하여 국소최적해에 빠지는 문제를 완화하였다."

신경망 구조를 탐색할 때 시뮬레이티드 어닐링을 적용해, 탐색이 특정 구조에 너무 일찍 고정되는 문제를 줄였다는 의미입니다.

조금 더 깊게 보면

시뮬레이티드 어닐링의 핵심은 현재 해보다 나쁜 해로 옮겨갈 확률을 온도 매개변수에 따라 정하는 수용 확률 함수에 있으며, 이 확률은 통상 온도가 높을수록 크고 온도가 낮아질수록 작아지도록 설계됩니다. 온도를 얼마나 빨리 낮출지를 정하는 냉각 일정(cooling schedule)이 결과 품질과 계산 시간을 좌우하는 가장 중요한 설계 요소이며, 너무 빨리 식히면 국소최적해에 갇히고 너무 천천히 식히면 계산 시간이 지나치게 늘어나는 절충 관계가 존재합니다. 이 때문에 논문에서는 초기 온도, 냉각률, 반복 횟수 등 구체적인 파라미터 설정을 함께 보고하는 경우가 많습니다.

주의할 점

시뮬레이티드 어닐링은 항상 진짜 최적해를 보장하지는 않으며, "온도를 얼마나 빨리 식힐지" 같은 설정값에 따라 결과 품질과 계산 시간이 크게 달라집니다. 비슷한 목적의 유전 알고리즘과 함께 대표적인 메타휴리스틱(발견적 최적화) 기법으로 묶여 비교되곤 합니다.