시뮬레이티드 어닐링

시뮬레이티드 어닐링(Simulated Annealing)은 물리학의 금속 열처리 과정을 모방한 최적화 알고리즘입니다.
최적화 문제에서 전역 최적해를 찾는 것이 목적이며, 지역 최적해에 빠지지 않도록 설계된 방식으로 복잡한 문제 해결에 효과적입니다. 이번 포스팅에서는 시뮬레이티드 어닐링의 개념, 원리, 구현 방법 및 사용 사례에 대해 알아보겠습니다.

---

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

시뮬레이티드 어닐링은 전역 최적화 기법 중 하나로, 특정 문제에서 전역 최적해를 찾기 위해 탐색 범위를 광범위하게 다루는 알고리즘입니다. 금속의 냉각과 경화 과정을 모방해 점진적으로 탐색 공간을 좁히며 최적의 해를 찾아가는 방식입니다.

시뮬레이티드 어닐링의 핵심 원리

1. 초기 고온에서 시작해 점차 온도를 낮추며, 해를 찾습니다.
2. 초기에는 탐색 범위가 넓고 다양한 해를 탐색할 수 있습니다.
3. 온도가 낮아질수록 해의 범위를 줄여 최적해로 수렴하도록 합니다.

---

2. 시뮬레이티드 어닐링의 알고리즘 원리

시뮬레이티드 어닐링은 온도(T)를 변화시키면서 해(Solution)를 점진적으로 개선합니다.

2.1 초기화 (Initialization)

초기 해와 높은 초기 온도(T)로 시작합니다. 초기 온도가 높을수록 초기 탐색 범위가 넓어지므로 다양한 해를 탐색할 수 있습니다.

2.2 인접 해 탐색 (Neighbor Search)

현재 해를 기준으로 인접한 해를 임의로 선택해 탐색합니다. 이때, 변경된 해의 적합도(Fitness)를 계산합니다.

2.3 수락 확률 (Acceptance Probability)

새로운 해가 현재 해보다 좋은 경우 무조건 수락하며, 더 나쁜 해일 경우 온도와 차이에 따라 일정 확률로 수락합니다. 확률 PPP는 다음 수식으로 표현됩니다.

여기서, ΔE\Delta EΔE는 새로운 해의 적합도가 현재 해보다 나쁜 정도이며, TTT는 현재 온도입니다. 이 확률은 온도가 낮아질수록 감소하여, 점점 더 좋은 해로 수렴하도록 유도합니다.

2.4 온도 감소 (Cooling Schedule)

온도를 서서히 감소시키며 탐색 범위를 좁힙니다. 온도 감소 방법으로는 선형 감소, 지수적 감소 등의 방식이 있으며, 일반적으로 지수적 감소가 많이 사용됩니다.

2.5 종료 조건 (Termination)

온도가 매우 낮아지거나, 일정 횟수 동안 더 좋은 해가 발견되지 않으면 알고리즘을 종료합니다.

---

3. 시뮬레이티드 어닐링 구현 (C# 예시)

다음은 시뮬레이티드 어닐링을 사용해 함수의 최소값을 찾는 예시입니다.

using System;

public class SimulatedAnnealing
{
    private static readonly Random random = new Random();
    private const double InitialTemperature = 1000;
    private const double CoolingRate = 0.99;
    private const double MinTemperature = 1e-3;

    public static double Optimize(Func<double, double> function, double startX)
    {
        double temperature = InitialTemperature;
        double currentX = startX;
        double bestX = startX;
        double bestScore = function(bestX);

        while (temperature > MinTemperature)
        {
            double newX = currentX + (random.NextDouble() * 2 - 1); // Random neighbor
            double newScore = function(newX);

            if (newScore < bestScore || AcceptWorseSolution(bestScore, newScore, temperature))
            {
                currentX = newX;
                bestX = newX;
                bestScore = newScore;
            }

            temperature *= CoolingRate;
        }

        return bestX;
    }

    private static bool AcceptWorseSolution(double currentScore, double newScore, double temperature)
    {
        double probability = Math.Exp((currentScore - newScore) / temperature);
        return probability > random.NextDouble();
    }

    public static void Main()
    {
        Func<double, double> function = x => x * x + 4 * Math.Cos(x); // Sample function
        double result = Optimize(function, startX: 0);
        Console.WriteLine($"최적의 x값: {result}");
    }
}

코드 설명

• 초기화: 높은 온도로 시작하며, 목표 함수의 최솟값을 찾기 위한 초기 startX를 설정합니다.
• 인접 해 탐색: 무작위 인접 위치를 통해 새로운 해를 탐색합니다.
• 수락 조건: 더 나쁜 해일 경우 AcceptWorseSolution 함수를 통해 온도에 따라 확률적으로 선택합니다.
• 온도 감소: CoolingRate에 따라 온도를 점차 감소시켜 점점 좋은 해로 수렴합니다.

실행 결과

이 알고리즘은 x^2 + 4 * cos(x)라는 함수를 기준으로 최적의 x 값을 찾습니다.

---

4. 시뮬레이티드 어닐링의 장점과 단점

장점

• 지역 최적해에서 벗어날 가능성이 높아 전역 최적해를 찾는 데 유리합니다.
• 고차원, 비선형 문제에서 효과적으로 적용됩니다.
• 단순한 알고리즘 구조로 다양한 문제에 쉽게 적용 가능합니다.

단점

• 파라미터 설정(초기 온도, 냉각률 등)이 결과에 큰 영향을 미치며, 경험적 조정이 필요합니다.
• 탐색 속도가 느릴 수 있습니다.

---

5. 시뮬레이티드 어닐링의 사용 사례

1. 산업 최적화 문제: 설비 배치, 공정 스케줄링 등 비용 절감과 효율화를 목표로 합니다.
2. 경로 탐색 문제: 물류 경로 최적화(TSP)와 같은 문제에서 전역 최적화를 목표로 사용됩니다.
3. 기계 학습 하이퍼파라미터 튜닝: 기계 학습 모델의 하이퍼파라미터를 최적화해 모델 성능을 높입니다.
4. 회로 설계 최적화: 전자 회로의 배치를 최적화해 전력 소비를 줄이고 성능을 극대화합니다.

---

시뮬레이티드 어닐링은 자연적인 물리 현상을 모방한 알고리즘으로, 비선형적인 문제 해결에 효과적입니다. 이 알고리즘의 원리와 작동 방식을 이해하고 적용할 수 있다면, 다양한 최적화 문제에 대해 유용한 해결책을 도출할 수 있을 것입니다!