Evolutionärer Suchalgorithmus (Evolutionary Search) in C++ – Erklärung, Beispiel und Code

Der Evolutionary Search-Algorithmus ist eine Optimierungsmethode, die auf dem Mechanismus der natürlichen Evolution basiert. Dieser Algorithmus simuliert den Evolutionsprozess von Individuen innerhalb einer Population über Generationen hinweg, um die beste Lösung für ein Problem zu finden.

Wie es funktioniert

1. Populationsinitialisierung: Erstellen Sie eine anfängliche Population zufällig generierter Individuen.
2. Bewertung: Bewerten Sie die Qualität jedes Einzelnen in der Bevölkerung anhand der objektiven Funktion oder der Bewertungskriterien.
3. Auswahl: Wählen Sie anhand von Wahrscheinlichkeiten oder Auswahlkriterien eine Teilmenge der besten Personen aus der aktuellen Population aus.
4. Evolution: Erstellen Sie eine neue Generation, indem Sie Crossover- und Mutationsoperationen auf die ausgewählten Individuen anwenden.
5. Iteration: Wiederholen Sie die Schritte 2 bis 4 über mehrere Generationen, bis eine zufriedenstellende Lösung erreicht ist oder eine vordefinierte Anzahl von Iterationen erreicht ist.

Beispiel: Optimierung der Fibonacci Funktion mithilfe der evolutionären Suche

Betrachten Sie das Optimierungsproblem der Fibonacci Funktion F(x) = F(x-1) + F(x-2) mit F(0) = 0, F(1) = 1. Wir wollen den Wert von x finden, für den F(x) wird maximiert. Die Methode der evolutionären Suche kann eine Population zufälliger x-Werte generieren und diese über Generationen hinweg weiterentwickeln, um den optimalen x-Wert zu finden.

Codebeispiel in 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;  
}  

In diesem Beispiel verwenden wir die Methode Evolutionary Search, um die Fibonacci Funktion zu optimieren. Wir generieren eine Population zufälliger x-Werte und entwickeln sie über Generationen hinweg weiter, indem wir die besten Individuen auswählen und Crossover- und Mutationsoperationen anwenden.