close

C++의 진화 검색 (Evolutionary Search) 알고리즘- 설명, 예제 및 코드

Evolutionary Search 알고리즘은 자연 진화의 메커니즘을 기반으로 한 최적화 방법입니다. 이 알고리즘은 문제에 대한 최상의 솔루션을 찾기 위해 여러 세대에 걸쳐 인구 내 개인의 진화 과정을 시뮬레이션합니다.

작동 방식

  1. 인구 초기화: 무작위로 생성된 개인의 초기 인구를 만듭니다.
  2. 평가: 목적 함수 또는 평가 기준에 따라 모집단의 각 개인의 품질을 평가합니다.
  3. 선택: 확률 또는 선택 기준에 따라 현재 모집단에서 최고의 개인 하위 집합을 선택합니다.
  4. 진화: 선택한 개체에 교차 및 돌연변이 작업을 적용하여 새로운 세대를 만듭니다.
  5. 반복: 만족스러운 솔루션을 얻거나 미리 정의된 반복 횟수에 도달할 때까지 여러 세대에 걸쳐 2~4단계를 반복합니다.

예: Fibonacci Evolutionary Search를 사용하여 함수 최적화

Fibonacci F(0) = 0, F(1) = 1인 함수 F(x) = F(x-1) + F(x-2)의 최적화 문제를 고려하십시오. F(x)가 최대화됩니다. Evolutionary Search 방법은 무작위 x 값의 모집단을 생성하고 여러 세대에 걸쳐 진화시켜 최적의 x 값을 찾을 수 있습니다.

C++의 코드 예제 

#include <iostream>  
#include <vector>  
#include <cstdlib>  
#include <ctime>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int evolutionSearchFibonacci(int populationSize, int numGenerations) {  
    srand(time(0));  
  
    std::vector<int> population(populationSize);  
    for(int i = 0; i < populationSize; ++i) {  
        population[i] = rand() % populationSize;  
    }  
  
    for(int gen = 0; gen < numGenerations; ++gen) {  
        int bestIndex = 0;  
        for(int i = 1; i < populationSize; ++i) {  
            if(fibonacci(population[i]) > fibonacci(population[bestIndex])) {  
                bestIndex = i;  
            }  
        }  
  
        // Crossover and mutation operations can be applied here  
  
        // Example: Replace the worst individual with the best individual  
        population[0] = population[bestIndex];  
    }  
  
    return population[0];  
}  
  
int main() {  
    int populationSize = 50;  
    int numGenerations = 100;  
    int result = evolutionSearchFibonacci(populationSize, numGenerations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}

이 예에서는 Evolutionary Search 방법을 사용하여 Fibonacci 기능을 최적화합니다. 무작위 x 값의 모집단을 생성하고, 최고의 개인을 선택하고 교차 및 돌연변이 작업을 적용하여 여러 세대에 걸쳐 진화시킵니다.