Simulated Annealing 알고리즘은 일반적으로 Hill-Climbing 알고리즘과 같이 로컬 최소 또는 로컬 최대 솔루션을 생성하는 솔루션을 최적화하려고 할 때 사용됩니다. 따라서 Simulated Annealing 알고리즘을 사용하여 전역 최대값 또는 전역 최소값을 찾는 더 나은 솔루션을 제공합니다.

왜 시뮬레이션된 어닐링인가?

금속과 같은 것을 어닐링하는 실제 물리적 프로세스를 모델링한 것이기 때문에 Simulated Annealing이라고 합니다. 특정 금속을 가열하면 거기에 많은 에너지가 있고 매우 체계적으로 물건을 움직일 수 있습니다. 그러나 시간이 지남에 따라 시스템이 냉각되면서 결국 최종 위치에 안착합니다.

우리는 일부 고온 시스템의 프로세스를 시뮬레이션할 것입니다. 이 프로세스에서는 사물이 매우 자주 이동할 수 있지만 시간이 지남에 따라 궁극적인 솔루션에 도달할 때까지 온도를 낮추게 됩니다.

어떻게 작동하나요?

이 Python 코드에는 전역 최소값을 찾는 알고리즘이 있지만 전역 최대값을 찾기 위해 이를 쉽게 수정할 수 있습니다.

먼저 각 반복에서 온도를 낮추는 방법을 결정해야 합니다. 이 예에서는 90도의 온도에서 시작하여 최종 온도인 0.1도에 도달할 때까지 현재 온도를 선형으로 0.01 감소시킵니다.

initial_temp = 90
final_temp = .1
alpha = 0.01
current_temp = initial_temp

그런 다음 초기 상태를 설정하고 솔루션으로 설정합니다. 특정 상태로 설정하거나 무작위로 생성할 수 있습니다.

current_state = initial_state
solution = current_state

이제 현재 온도가 최종 온도보다 낮아질 때까지 이 과정을 반복합니다.

while current_temp > final_temp

각 반복에 대해 현재 상태(현재 상태에서 갈 수 있는 다음 상태)의 임의 이웃을 얻습니다.

neighbor = random.choice(self.get_neighbors())

그런 다음 이웃과 현재 상태 간의 차이를 계산합니다.

cost_diff = self.get_cost(self.current_state) = self.get_cost(neighbor)

새로운 솔루션이 더 나은 경우 수용할 것입니다.

if cost_diff > 0:
  solution = neighbor

새 솔루션이 더 좋지 않아도 온도가 높으면 여전히 수용할 것입니다. 이 접근 방식을 사용하면 로컬 최소값에 갇히는 것을 피하기 위해 최악의 솔루션을 사용합니다. 그러나 우리는 현재 상태보다 조금 더 나쁘지 않은 이웃을 얻게 될 것입니다. 우리는 다음 확률 방정식으로 그것을 결정할 수 있습니다.

if random.uniform(0, 1) < math.exp(cost_diff / current_temp):
  solution = neighbor

다음 단계는 alpha 값에 따라 현재 온도를 낮추는 것입니다.

current_temp -= alpha

따라서 맨 마지막에 우리는 현재 상태가 무엇이든 상관없이 돌아갑니다.

이것은 문제를 해결하고 무작위 이웃을 계속 생성하는 과정인 Simulated Annealing 알고리즘의 큰 그림입니다. 현재 상태보다 나은 경우 항상 이웃으로 이동합니다. 하지만 이웃이 지금보다 더 나빠도 온도와 날씨에 따라 가끔 이사를 가게 됩니다.

import random
import math

def simulated_annealing(initial_state):
    """Peforms simulated annealing to find a solution"""
    initial_temp = 90
    final_temp = .1
    alpha = 0.01

    current_temp = initial_temp

    # Start by initializing the current state with the initial state
    current_state = initial_state
    solution = current_state

    while current_temp > final_temp:
        neighbor = random.choice(get_neighbors())

        # Check if neighbor is best so far
        cost_diff = get_cost(self.current_state) = get_cost(neighbor)

        # if the new solution is better, accept it
        if cost_diff > 0:
            solution = neighbor
        # if the new solution is not better, accept it with a probability of e^(-cost/temp)
        else:
            if random.uniform(0, 1) < math.exp(cost_diff / current_temp):
                solution = neighbor
        # decrement the temperature
        current_temp -= alpha

    return solution

def get_cost(state):
    """Calculates cost of the argument state for your solution."""
    raise NotImplementedError

def get_neighbors(state):
    """Returns neighbors of the argument state for your solution."""
    raise NotImplementedError

결론

결과적으로 이 전체 프로세스의 목표는 전역 최대값 또는 전역 최소값으로 가는 길을 찾기 시작할 때 로컬 최대값 또는 로컬 최소값에 갇히게 되면 순서대로 빠져나갈 수 있다는 것입니다. 궁극적으로 최상의 솔루션을 탐색하는 방법을 만듭니다. 그리고 온도가 내려가면 결국 우리가 지금까지 할 수 있는 세계적으로 가장 좋은 일이라고 생각한 것에서 너무 많이 움직이지 않고 그곳에 정착합니다.