[C++로 배우는 알고리즘과 자료구조 심화] Day 27: 유전 알고리즘 (Genetic Algorithms)

유전 알고리즘 (Genetic Algorithms)

유전 알고리즘(Genetic Algorithms, GA)은 자연 선택의 원리를 모방한 최적화 알고리즘입니다. 유전 알고리즘은 주로 복잡한 최적화 문제를 해결하는 데 사용되며, 초기 해 집합(개체군)을 생성하고 이를 진화시키는 과정을 반복하여 최적해를 찾아갑니다.

유전 알고리즘의 주요 단계

1. 초기화: 초기 개체군을 무작위로 생성합니다.
2. 선택: 적합도에 따라 부모 개체를 선택합니다.
3. 교차 (Crossover): 부모 개체의 유전자를 교환하여 자손을 생성합니다.
4. 돌연변이 (Mutation): 자손의 유전자 일부를 무작위로 변경하여 다양성을 유지합니다.
5. 적합도 평가: 각 개체의 적합도를 계산합니다.
6. 종료 조건 확인: 최적해를 찾았거나 최대 세대 수에 도달하면 알고리즘을 종료합니다.

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

유전 알고리즘을 사용하여 여행하는 외판원 문제(TSP)를 해결합니다. TSP는 주어진 도시들을 모두 한 번씩 방문하고 처음 도시로 돌아오는 최소 경로를 찾는 문제입니다.

유전 알고리즘 구현

다음은 C++로 유전 알고리즘을 사용하여 TSP를 해결하는 예제입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

const int POPULATION_SIZE = 100;
const int GENERATIONS = 1000;
const double MUTATION_RATE = 0.01;

// 랜덤 엔진 설정
std::random_device rd;
std::mt19937 gen(rd());

// 도시 좌표
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<std::vector<int>> initializePopulation(int populationSize, int cityCount) {
    std::vector<std::vector<int>> population(populationSize, std::vector<int>(cityCount));
    for (int i = 0; i < populationSize; ++i) {
        for (int j = 0; j < cityCount; ++j) {
            population[i][j] = j;
        }
        std::shuffle(population[i].begin(), population[i].end(), gen);
    }
    return population;
}

// 적합도 평가 함수
std::vector<double> evaluateFitness(const std::vector<std::vector<int>>& population) {
    std::vector<double> fitness(population.size());
    for (int i = 0; i < population.size(); ++i) {
        fitness[i] = 1.0 / calculateDistance(population[i]);
    }
    return fitness;
}

// 룰렛 휠 선택 함수
std::vector<int> selectParents(const std::vector<double>& fitness) {
    std::vector<int> parents(2);
    std::discrete_distribution<> dist(fitness.begin(), fitness.end());
    parents[0] = dist(gen);
    parents[1] = dist(gen);
    return parents;
}

// 교차 연산 함수
std::vector<int> crossover(const std::vector<int>& parent1, const std::vector<int>& parent2) {
    int cityCount = parent1.size();
    std::vector<int> child(cityCount, -1);
    std::uniform_int_distribution<> dist(0, cityCount - 1);
    int start = dist(gen);
    int end = dist(gen);

    if (start > end) std::swap(start, end);

    for (int i = start; i <= end; ++i) {
        child[i] = parent1[i];
    }

    int currentIndex = 0;
    for (int i = 0; i < cityCount; ++i) {
        if (std::find(child.begin(), child.end(), parent2[i]) == child.end()) {
            while (child[currentIndex] != -1) {
                currentIndex++;
            }
            child[currentIndex] = parent2[i];
        }
    }
    return child;
}

// 돌연변이 연산 함수
void mutate(std::vector<int>& individual) {
    std::uniform_real_distribution<> dist(0.0, 1.0);
    for (int i = 0; i < individual.size(); ++i) {
        if (dist(gen) < MUTATION_RATE) {
            std::uniform_int_distribution<> swapDist(0, individual.size() - 1);
            int swapIndex = swapDist(gen);
            std::swap(individual[i], individual[swapIndex]);
        }
    }
}

// 새로운 세대 생성 함수
std::vector<std::vector<int>> createNewGeneration(const std::vector<std::vector<int>>& population, const std::vector<double>& fitness) {
    std::vector<std::vector<int>> newGeneration(population.size());
    for (int i = 0; i < population.size(); ++i) {
        std::vector<int> parents = selectParents(fitness);
        std::vector<int> child = crossover(population[parents[0]], population[parents[1]]);
        mutate(child);
        newGeneration[i] = child;
    }
    return newGeneration;
}

int main() {
    int cityCount = cities.size();
    std::vector<std::vector<int>> population = initializePopulation(POPULATION_SIZE, cityCount);

    for (int generation = 0; generation < GENERATIONS; ++generation) {
        std::vector<double> fitness = evaluateFitness(population);
        population = createNewGeneration(population, fitness);
        std::cout << "세대 " << generation + 1 << "의 최적 거리: " << 1.0 / *std::max_element(fitness.begin(), fitness.end()) << std::endl;
    }

    return 0;
}

 

설명

1. 입력:
   • cities: 도시 좌표 리스트
   • POPULATION_SIZE: 개체군 크기
   • GENERATIONS: 세대 수
   • MUTATION_RATE: 돌연변이 확률
2. 유전 알고리즘의 주요 단계:
   • initializePopulation: 초기 개체군을 무작위로 생성합니다.
   • evaluateFitness: 각 개체의 적합도를 계산합니다.
   • selectParents: 적합도에 따라 부모 개체를 선택합니다.
   • crossover: 부모 개체의 유전자를 교환하여 자손을 생성합니다.
   • mutate: 자손의 유전자 일부를 무작위로 변경합니다.
   • createNewGeneration: 새로운 세대를 생성합니다.
3. 유전 알고리즘 수행:
   • 각 세대마다 적합도를 평가하고 새로운 세대를 생성하여 최적해를 찾아갑니다.

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