[C++로 배우는 알고리즘과 자료구조 심화] Day 28: 시뮬레이티드 어닐링 (Simulated Annealing)

시뮬레이티드 어닐링 (Simulated Annealing)

시뮬레이티드 어닐링(Simulated Annealing, SA)은 금속의 냉각 및 결정화 과정에서 영감을 받은 확률적 최적화 알고리즘입니다. 이 알고리즘은 전역 최적해를 찾기 위해 국부 최적해에서 탈출할 수 있도록 고안되었습니다.

시뮬레이티드 어닐링의 주요 단계

1. 초기화: 초기 해와 초기 온도를 설정합니다.
2. 이웃 해 생성: 현재 해의 이웃 해를 무작위로 생성합니다.
3. 해 수용: 새로운 해가 더 나은 해이면 수용합니다. 그렇지 않으면, 확률적으로 수용합니다.
4. 온도 감소: 온도를 점진적으로 낮춥니다.
5. 종료 조건 확인: 종료 조건(예: 온도가 충분히 낮아지거나 최대 반복 횟수에 도달)을 확인합니다.

문제 예시: 여행하는 외판원 문제 (TSP)

시뮬레이티드 어닐링을 사용하여 여행하는 외판원 문제(TSP)를 해결합니다. TSP는 주어진 도시들을 모두 한 번씩 방문하고 처음 도시로 돌아오는 최소 경로를 찾는 문제입니다.

시뮬레이티드 어닐링 구현

다음은 C++로 시뮬레이티드 어닐링을 사용하여 TSP를 해결하는 예제입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <limits>

const int NUM_CITIES = 10;
const double INITIAL_TEMPERATURE = 1000.0;
const double FINAL_TEMPERATURE = 1e-3;
const double COOLING_RATE = 0.995;
const int ITERATIONS_PER_TEMP = 100;

// 도시 좌표
std::vector<std::pair<int, int>> cities = {
    {0, 0}, {1, 2}, {2, 4}, {3, 6}, {5, 8}, {6, 7}, {7, 5}, {8, 3}, {9, 1}, {10, 0}
};

// 경로 거리 계산 함수
double calculateDistance(const std::vector<int>& path) {
    double distance = 0.0;
    for (int i = 0; i < path.size() - 1; ++i) {
        int x1 = cities[path[i]].first;
        int y1 = cities[path[i]].second;
        int x2 = cities[path[i + 1]].first;
        int y2 = cities[path[i + 1]].second;
        distance += std::sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    }
    // 시작 도시로 돌아오기
    int x1 = cities[path.back()].first;
    int y1 = cities[path.back()].second;
    int x2 = cities[path.front()].first;
    int y2 = cities[path.front()].second;
    distance += std::sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    return distance;
}

// 이웃 해 생성 함수
std::vector<int> generateNeighbor(const std::vector<int>& path) {
    std::vector<int> newPath = path;
    int i = rand() % path.size();
    int j = rand() % path.size();
    std::swap(newPath[i], newPath[j]);
    return newPath;
}

// 시뮬레이티드 어닐링 함수
std::vector<int> simulatedAnnealing() {
    std::vector<int> currentPath(NUM_CITIES);
    for (int i = 0; i < NUM_CITIES; ++i) {
        currentPath[i] = i;
    }
    std::random_shuffle(currentPath.begin(), currentPath.end());
    double currentDistance = calculateDistance(currentPath);
    std::vector<int> bestPath = currentPath;
    double bestDistance = currentDistance;
    double temperature = INITIAL_TEMPERATURE;

    while (temperature > FINAL_TEMPERATURE) {
        for (int i = 0; i < ITERATIONS_PER_TEMP; ++i) {
            std::vector<int> newPath = generateNeighbor(currentPath);
            double newDistance = calculateDistance(newPath);
            if (newDistance < currentDistance || exp((currentDistance - newDistance) / temperature) > static_cast<double>(rand()) / RAND_MAX) {
                currentPath = newPath;
                currentDistance = newDistance;
                if (newDistance < bestDistance) {
                    bestPath = newPath;
                    bestDistance = newDistance;
                }
            }
        }
        temperature *= COOLING_RATE;
    }

    return bestPath;
}

int main() {
    srand(time(0));

    std::vector<int> bestPath = simulatedAnnealing();
    double bestDistance = calculateDistance(bestPath);

    std::cout << "최적 경로: ";
    for (int city : bestPath) {
        std::cout << city << " ";
    }
    std::cout << std::endl;
    std::cout << "최적 경로의 거리: " << bestDistance << std::endl;

    return 0;
}

 

설명

1. 입력:
   • cities: 도시 좌표 리스트
   • NUM_CITIES: 도시의 수
   • INITIAL_TEMPERATURE: 초기 온도
   • FINAL_TEMPERATURE: 최종 온도
   • COOLING_RATE: 온도 감소율
   • ITERATIONS_PER_TEMP: 각 온도에서 반복할 횟수
2. 경로 거리 계산:
   • calculateDistance 함수는 주어진 경로의 총 거리를 계산합니다.
3. 이웃 해 생성:
   • generateNeighbor 함수는 현재 경로의 두 도시를 무작위로 교환하여 새로운 경로를 생성합니다.
4. 시뮬레이티드 어닐링 수행:
   • simulatedAnnealing 함수는 초기 해와 초기 온도를 설정하고, 각 온도에서 새로운 경로를 생성하여 현재 경로와 비교합니다.
   • 새로운 경로가 더 나은 해이면 수용하고, 그렇지 않으면 확률적으로 수용합니다.
   • 온도를 점진적으로 감소시켜 최적해를 찾습니다.

시뮬레이티드 어닐링의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 29: 병렬 알고리즘(Parallel Algorithms)"에 대해 학습하겠습니다.