close

C++ の進化的検索 (Evolutionary Search) アルゴリズム- 説明、例、コード

進化的探索アルゴリズムは、自然進化のメカニズムに基づいた最適化手法です。 このアルゴリズムは、問題に対する最適な解決策を見つけるために、世代を超えた集団内の個人の進化プロセスをシミュレートします。

使い方

  1. 集団の初期化: ランダムに生成された個人の初期集団を作成します。
  2. 評価: 目的関数または評価基準に基づいて、母集団内の各個人の質を評価します。
  3. 選択: 確率または選択基準に基づいて、現在の母集団から最良の個人のサブセットを選択します。
  4. 進化: 選択した個体に交叉操作と突然変異操作を適用して新しい世代を作成します。
  5. 反復: 満足のいく解が得られるか、事前に定義された反復回数に達するまで、ステップ 2 ～ 4 を複数世代にわたって繰り返します。

例: Fibonacci 進化的検索を使用した関数の最適化

Fibonacci F(0) = 0、F(1) = 1 の関数 F(x) = F(x-1) + F(x-2) の最適化問題を考えます 。 F(x) が最大化されます。 進化的検索手法では、ランダムな 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;  
}

この例では、進化的検索手法を使用して Fibonacci 関数を最適化します。 ランダムな x 値の母集団を生成し、最良の個体を選択し、交叉操作と突然変異操作を適用することで、世代を超えて進化させます。