[c++] 유전 알고리즘을 이용한 검색

15 Dec 2023

유전 알고리즘은 생물의 진화 원리를 모방하여 최적화 문제를 해결하는 데 사용되는 컴퓨터 알고리즘입니다. 이 알고리즘은 유전자와 진화의 개념을 사용하여 여러 가지 후보 해결책을 생성하고, 각 해결책의 적합도를 평가하여 최적의 해결책을 찾아내는데 활용됩니다.

장점

유전 알고리즘은 다양한 문제에 대해 적용할 수 있으며, 초기 조건에 상대적으로 덜 민감하여 최적화 문제를 해결하는 데 유용합니다. 또한 다른 최적화 알고리즘에 비해 전역 최적해를 더 빨리 찾을 수 있는 장점이 있습니다.

c++로의 적용

아래는 c++를 이용하여 간단한 유전 알고리즘을 구현한 예시 코드입니다.

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

// 후보해
struct CandidateSolution {
    std::vector<int> genes;
    int fitness;
};

// 초기 해 생성
std::vector<CandidateSolution> initializePopulation(int populationSize) {
    std::vector<CandidateSolution> population;
    for (int i = 0; i < populationSize; ++i) {
        CandidateSolution solution;
        // 각 후보해의 유전자 초기화
        for (int j = 0; j < solution.genes.size(); ++j) {
            solution.genes[j] = rand() % 2;  // 랜덤으로 0 또는 1로 초기화 (이진 문자열)
        }
        solution.fitness = 0;  // 적합도 초기화
        population.push_back(solution);
    }
    return population;
}

// 적합도 측정
void calculateFitness(CandidateSolution& solution) {
    int total = 0;
    for (int gene : solution.genes) {
        total += gene;
    }
    solution.fitness = total;
}

// 유전 알고리즘 메인 함수
void geneticAlgorithm(int populationSize, int generations) {
    std::vector<CandidateSolution> population = initializePopulation(populationSize);
    for (int gen = 0; gen < generations; ++gen) {
        for (CandidateSolution& solution : population) {
            calculateFitness(solution);
        }
        // 적합도순으로 정렬하여 상위 해 선택
        std::sort(population.begin(), population.end(), [](const CandidateSolution& a, const CandidateSolution& b) {
            return a.fitness > b.fitness;
        });
        // 교배 및 돌연변이 연산
        // 생략
    }
}

int main() {
    geneticAlgorithm(100, 1000);
    return 0;
}

위의 코드는 간단한 이진 문자열을 이용한 유전 알고리즘 예제로, 실제로는 문제에 따라 유전자와 적합도 계산 방법을 재정의하여 적용해야 합니다.

유전 알고리즘은 다양한 최적화 문제에 적용되며, c++를 이용하여 손쉽게 구현할 수 있습니다.

참고 문헌

Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley professional.
Drozdik, J. (2001). Mastering c++ standard library. Sybex.