시뮬레이티드 어닐링(Simulated Annealing) 알고리즘: 글로벌 최적화 방법

시뮬레이티드 어닐링이란?

시뮬레이티드 어닐링(Simulated Annealing, SA)은 메타휴리스틱 최적화 기법 중 하나로, 주로 복잡한 전역 최적화 문제를 해결하는 데 사용됩니다. 물리학에서 유래된 이 기법은 금속을 천천히 냉각시키는 과정을 본떠 개발되었습니다. 금속을 서서히 냉각시키면 그 구조가 더 안정적이고 에너지가 낮은 상태로 형성되듯이, SA 알고리즘도 탐색 공간을 천천히 줄이며 글로벌 최적해를 찾아냅니다.

작동 원리

초기화 단계

먼저, 초기 해를 설정합니다. 이 초기 해는 문제의 탐색 공간 안에서 무작위로 선택될 수 있습니다. 초기 해를 설정한 후, 초기 온도 (Temperature)를 설정합니다. 온도 값은 알고리즘의 동작 방식에 큰 영향을 미치며, 초기에는 높은 값에서 시작하여 점차 감소하게 됩니다.

인접 해 생성

현재 해(현재 위치)를 기반으로 인접 해를 생성합니다. 인접 해는 현재 해에서 약간의 변화를 준 것으로, 탐색 공간 내의 인접한 해들을 의미합니다. 예를 들어, 현재 해가 x라면 인접 해는 x + δ (δ는 작은 값)입니다.

에너지 함수

각 해에는 에너지 또는 코스트 함수 값이 할당됩니다. 이 값은 해당 해가 문제를 얼마나 잘 해결하는지를 나타냅니다. 예를 들어, 최적화 문제가 최소화 문제라면, 낮은 에너지 값을 가진 해가 더 좋은 해가 됩니다.

해 수락 조건

어떤 해를 다음 단계의 해로 수락할지 결정하는 방법은 다음과 같습니다:

• 에너지 감소: 만약 인접 해의 에너지(코스트) 값이 현재 해의 값보다 낮다면, 인접 해를 다음 단계의 해로 수락합니다.
• 확률적 수락: 만약 인접 해의 에너지 값이 현재 해의 값보다 높더라도, 특정 확률에 의해 그 해를 수락할 수 있습니다. 이 확률은 다음과 같이 계산됩니다: P = exp(-(E_new - E_current) / T) 여기서 E_new는 인접 해의 에너지 값, E_current는 현재 해의 에너지 값, T는 현재 온도입니다. 이렇게 하면 초기에 높은 온도에서는 많은 해가 수락되지만, 시간이 지남에 따라 점점 적은 해가 수락되므로 탐색 공간을 효율적으로 탐색할 수 있습니다.

온도 감소

온도는 선형 또는 지수적으로 감소합니다. 이 과정에서는 냉각 스케줄(Cooling Schedule)이라는 개념이 사용됩니다. 온도 감소 함수의 예는 다음과 같습니다:

• 선형 감소: T = T - alpha
• 지수 감소: T = T * alpha (0 < alpha < 1)

이 과정을 반복하며 온도가 충분히 낮아지면 알고리즘은 종료되며, 최적 해를 출력합니다.

장단점

장점

1. 글로벌 최적화 가능성: SA는 국부 최적해에 빠지지 않고 글로벌 최적해를 찾을 가능성이 높습니다.
2. 유연성: 다양한 최적화 문제에 쉽게 적용할 수 있습니다.
3. 단순 구현: 알고리즘이 비교적 단순하고 직관적이라 구현이 용이합니다.

단점

1. 시간 소모: 탐색 속도가 느리고 많은 반복이 필요합니다.
2. 파라미터 의존성: 초기 온도, 냉각 스케줄 등 여러 파라미터에 성능이 크게 좌우됩니다.
3. 최적성 보장 불가: 항상 최적 해를 보장하지 않으며, 결과는 초기 조건과 확률적 수락에 따라 달라질 수 있습니다.

실용 예제

SA 알고리즘은 다양한 문제에 적용될 수 있습니다. 그 중 몇 가지 예를 살펴보겠습니다.

여행자 문제

모든 도시를 한 번씩 방문하여 다시 출발지로 돌아오는 최소 경로를 찾는 문제입니다. 이 문제에서 SA는 무작위로 도시 순서를 바꾸고, 이 변화를 수락하거나 거절하는 방식으로 최적 경로를 찾아냅니다.

생산 스케줄링

다른 작업을 일정에 맞게 배치하는 문제입니다. SA를 이용하여 작업을 무작위로 배치한 뒤, 에너지 함수(예: 총 소요 시간)를 최소화하는 방향으로 탐색합니다.

함수 최적화

복잡한 함수의 최적 점을 찾는 데 사용됩니다. 예를 들어, 비선형 함수의 최소값을 찾는 문제에서도 효과적입니다.

Python 코드 예제

python
import numpy as np

def simulated_annealing(objective, bounds, n_iterations, step_size, temp):
    # Generate an initial point
    best = bounds[:, 0] + (bounds[:, 1] - bounds[:, 0]) * np.random.rand(len(bounds))
    best_eval = objective(best)
    curr, curr_eval = best, best_eval
    for i in range(n_iterations):
        candidate = curr + step_size * (np.random.rand(len(bounds)) - 0.5)
        candidate_eval = objective(candidate)
        if candidate_eval < best_eval:
            best, best_eval = candidate, candidate_eval
        diff = candidate_eval - curr_eval
        t = temp / float(i + 1)
        metropolis = np.exp(-diff / t)
        if diff < 0 or np.random.rand() < metropolis:
            curr, curr_eval = candidate, candidate_eval
    return [best, best_eval]

# Objective function
def objective(x):
    return x[0]**2 + x[1]**2

# Bounds of the search space
bounds = np.asarray([[-5.0, 5.0], [-5.0, 5.0]])

# Run the simulated annealing algorithm
best, score = simulated_annealing(objective, bounds, n_iterations=1000, step_size=0.1, temp=10.0)
print('Best:', best)
print('Score:', score)

결론

시뮬레이티드 어닐링은 복잡한 최적화 문제에서 글로벌 최적해를 찾는 강력한 도구입니다. 다양한 최적화 문제에 쉽게 적용할 수 있으며, 단순한 구현 방법에도 불구하고 효율적인 결과를 제공합니다. 그러나 시간 소모와 파라미터 의존성 등의 단점도 고려해야 하며, 이를 해결하기 위한 연구가 계속되고 있습니다.