Simulated Annealing과 MCMC: 확률적 탐색과 샘플링 설계

확률적 선택으로 탐색과 추론을 다루는 방식

결정론적 절차만으로는 지역 최적해를 벗어나기 어렵거나, 복잡한 분포를 직접 계산하기 힘든 문제가 있다. 스토캐스틱 알고리즘은 탐색과 추론 과정에 확률적 선택을 넣어 해 공간을 다루는 알고리즘군이다. 지역 최적해 탈출, 불확실성 정량화, 복잡한 분포의 샘플링에 적합하다.

Simulated Annealing(SA)은 물리학의 담금질에서 가져온 전역 최적화 휴리스틱이다. 현재 해 (x)에서 이웃 (x')로 옮길 때 비용 증가량 (\Delta E)가 있더라도 (p = exp(-\Delta E / T))의 확률로 이동을 허용한다. 온도 (T)는 냉각 스케줄에 따라 점차 낮아진다.

Markov Chain Monte Carlo(MCMC)는 목표 분포 (\pi(x))의 샘플을 얻기 위해 마르코프 연쇄를 만드는 샘플링 프레임워크다. Metropolis–Hastings에서는 수용 확률 (\alpha = min(1, [\pi(x') q(x|x')] / [\pi(x) q(x'|x)]))를 사용한다. 충분히 긴 반복 뒤 연쇄의 정지 분포는 (\pi(x))에 수렴한다.

난수와 제안 규칙이 탐색 품질을 만든다

재현 가능한 실험과 디버깅, 결과 비교를 위해서는 고품질 난수 생성기(PRNG)와 시드 관리가 필요하다. 제안 분포 (q(\cdot))의 설계도 탐색 효율에 직접 영향을 준다.

SA에서는 문제 구조에 맞는 이웃 생성 규칙이 핵심이다. MCMC에서는 대칭 또는 비대칭 제안 분포를 어떻게 구성할지가 혼합성과 수렴에 영향을 준다. SA는 높은 (T)에서 탐색성을 확보하고 낮은 (T)에서 수렴성을 강화한다. MCMC는 혼합성(mixing)과 자기상관 감소가 중요하며, burn-in, thinning, 체인 병렬 실행을 통해 수렴성을 높일 수 있다.

SA의 설계 변수는 초기 온도 (T0), 냉각율 (\alpha), 반복 예산, 재가열(reheating) 전략이다. MCMC는 제안 분포 스케일, 목표 수용률, 체인 길이, 적응형 조율을 함께 다뤄야 한다. 목표 수용률은 대략 0.2~0.4 범위를 사용하며, AMH 등의 적응형 기법을 적용할 때는 수렴성 보장 조건을 지켜야 한다.

수렴을 확인하고 중단에도 대비한다

SA에서는 다중 시작 결과, 최적값 추정의 안정성, 반복에 따른 비용 감소 추세를 함께 확인한다. MCMC는 Gelman–Rubin R-hat, 유효 샘플 크기(ESS), 트레이스 플롯, 포스터리어 체크로 수렴을 검증한다.

비용 또는 로그우도 계산이 Inf/NaN으로 실패하면 해당 제안을 거절하고, 수치 계산은 안정적인 로그 스케일로 처리하는 편이 낫다. 경계 제약이 있는 문제에는 투영(project) 또는 반사(reflection) 이웃·제안 규칙을 적용한다. 난수 시드를 고정하고 체크포인트를 저장하면 중단 뒤에도 복구할 수 있다.

⤢✕

최적 후보를 찾는 SA와 분포를 표본화하는 MCMC

항목	Simulated Annealing	MCMC (Metropolis–Hastings 계열)
성능	전역 최적 근사 탐색에 강점, 조합최적화 효율적	복잡 분포 샘플링에 강점, 고차원에서 조율 필요
확장성	다중 시작/분산 탐색으로 선형 확장 용이	다중 체인/병렬 템퍼링, 로그우도 분산 합산으로 확장
일관성	스케줄 적합 시 양호, 이론적 전역 최적 보장은 제한	정칙 조건하 점근적 일관성 보장
안정성	스케줄 민감도 높음, 과도 냉각 시 조기 수렴 위험	제안 스케일/혼합 민감, 자기상관 관리 필요
운영 편의	구현 단순, 도메인 제약 반영 용이	진단/사후 분석 도구 다수, 학습 곡선 존재

SA는 다중 시작 병렬 실행, 분할 정복 탐색, 베이지안 최적화와의 하이브리드 구성이 가능하다. MCMC는 다중 체인 병렬화, 병렬 템퍼링(PT), 분산 로그우도 계산으로 대용량 데이터를 다룬다.

제약이 강한 최적화와 불확실성 추론

제조·물류 스케줄링에서는 SA로 Job-shop/Flow-shop makespan과 지연 패널티를 줄일 수 있다. 교대, 셋업타임, 자원 캘린더 같은 제약 조건은 이웃 연산자에 반영한다.

시설 배치, VLSI 배선, 차량경로(VRP)에서는 SA가 초기 해 생성과 미세 조정에 쓰인다. 반면 MCMC는 A/B 테스트의 전환율 포스터리어 추정과 의사결정 임계값 설정, 마케팅·리스크 계층모형의 집단-개인 파라미터 추정 및 신뢰구간 도출에 맞는다.

비선형 또는 미분 불가 모델의 사후 분포를 얻거나, 시뮬레이터 기반 추론을 수행할 때는 ABC-MCMC 결합도 사용할 수 있다.

스케줄링에서는 기존 휴리스틱 대비 총 소요시간이 5~20% 개선될 수 있으며, 동일 계산 예산 기준 보고 사례가 다수 있다. 베이지안 추론에서는 ESS 향상에 따라 신뢰구간 길이를 줄이고 의사결정 오류율을 관리할 수 있다. 복잡한 제약과 비선형 문제에서 해의 견고성과 설명 가능성을 높이고, 불확실성을 명시적으로 모델링해 리스크를 인지·완화하는 효과도 기대할 수 있다.

냉각·제안·진단을 운영 흐름에 넣기

SA에서는 기하 냉각을 적용할 때 (\alpha=0.95~0.99) 범위를 기본으로 두고, 적응형 또는 재가열 전략으로 국소 최적해 탈출을 강화할 수 있다. 스왑, 인서트, 2-opt 같은 문제 구조 보존 연산자와 다중 규모 변이를 조합한다. 다중 시작과 함께 개선 없는 K회 반복 시 종료하거나 베이스라인 대비 개선률을 종료 기준으로 삼는다.

MCMC에서는 목표 수용률을 유지하도록 제안 스케일을 조율한다. 사전 예열 단계의 적응은 허용하되 정규화된 수렴성 보장에 유의해야 한다. 배포 파이프라인에는 R-hat<1.01, 파라미터별 ESS, 트레이스와 ACF 점검을 포함한다. 고차원 또는 강한 상관 구조에서는 HMC/NUTS 같은 그래디언트 기반 MCMC를 고려하며, 자동 미분 도입 비용과 성능 이득을 함께 평가한다.

공통적으로 시드와 실행 환경을 고정하고, 로그 스케일 계산과 NaN/Inf 방지 처리를 적용한다. 체크포인트와 중단 재시작을 지원하며 config, RNG 상태, 코드 해시를 기록해 결과 재현성을 관리한다.

Python으로 실행해 보는 확률적 탐색과 샘플링

전제조건: Python 3.10+, numpy>=1.24

Rastrigin 함수의 SA 최소화

import numpy as np

def rastrigin(x):
    A = 10
    x = np.asarray(x)
    return A * x.size + np.sum(x**2 - A * np.cos(2*np.pi*x))

rng = np.random.default_rng(42)

def sa_optimize(f, x0, T0=1.0, alpha=0.98, iters=10000, step=0.1):
    x = x0.copy()
    fx = f(x)
    T = T0
    best_x, best_fx = x.copy(), fx
    for t in range(1, iters+1):
        # 이웃 생성: 가우시안 변이
        x_prop = x + rng.normal(0, step, size=x.shape)
        f_prop = f(x_prop)
        dE = f_prop - fx
        if dE <= 0 or rng.random() < np.exp(-dE / max(T, 1e-12)):
            x, fx = x_prop, f_prop
            if fx < best_fx:
                best_x, best_fx = x.copy(), fx
        # 기하 냉각
        T *= alpha
        # 간단한 안정화: 주기적 step 감소
        if t % 2000 == 0:
            step *= 0.9
    return best_x, best_fx

x0 = rng.uniform(-5, 5, size=5)
bx, bf = sa_optimize(rastrigin, x0, T0=2.0, alpha=0.995, iters=20000, step=0.3)
print("best f:", bf, "best x:", bx)

rastrigin은 글로벌 최소값이 0인 다봉형 함수라 냉각율과 step 설정에 민감하다. NaN/Inf가 발생하면 제안을 거절하고 step을 축소한다.

Metropolis–Hastings로 N(0,1) 표본 생성

import numpy as np

rng = np.random.default_rng(123)

def log_pi(x):  # 로그 타깃: 표준정규
    return -0.5 * x**2  # 정규화 상수 불필요

def mh_sample(n=20000, burn=2000, prop_scale=1.0):
    x = 0.0
    samples = []
    accept = 0
    for i in range(n):
        x_prop = x + rng.normal(0, prop_scale)
        lp_cur = log_pi(x)
        lp_prop = log_pi(x_prop)
        alpha = min(1.0, np.exp(lp_prop - lp_cur))  # 대칭 제안분포
        if rng.random() < alpha:
            x = x_prop
            accept += 1
        if i >= burn:
            samples.append(x)
    acc_rate = accept / n
    return np.array(samples), acc_rate

samps, acc = mh_sample(n=30000, burn=5000, prop_scale=1.1)
print("accept rate:", round(acc, 3), "mean:", samps.mean(), "std:", samps.std())

로그 스케일 계산은 수치 안정성에 도움이 된다. 수용률이 높으면 제안 스케일을 확대하고, 낮으면 축소한다. 목표 수용률은 0.2~0.4 범위를 권장한다.