Evolutionär sökalgoritm (Evolutionary Search) i C++- Förklaring, exempel och kod

Den evolutionära sökalgoritmen är en optimeringsmetod baserad på mekanismen för naturlig evolution. Denna algoritm simulerar evolutionsprocessen för individer inom en population över generationer för att hitta den bästa lösningen för ett problem.

Hur det fungerar

1. Populationsinitiering: Skapa en initial population av slumpmässigt genererade individer.
2. Utvärdering: Utvärdera kvaliteten på varje individ i befolkningen utifrån den objektiva funktionen eller utvärderingskriterierna.
3. Urval: Välj en undergrupp av de bästa individerna från den aktuella populationen baserat på sannolikheter eller urvalskriterier.
4. Evolution: Skapa en ny generation genom att tillämpa korsnings- och mutationsoperationer på de utvalda individerna.
5. Iteration: Upprepa steg 2 till 4 över flera generationer tills en tillfredsställande lösning har uppnåtts eller ett fördefinierat antal iterationer har uppnåtts.

Exempel: Optimera Fibonacci funktionen med Evolutionary Search

Betrakta optimeringsproblemet för Fibonacci funktionen F(x) = F(x-1) + F(x-2) med F(0) = 0, F(1) = 1. Vi vill hitta värdet på x för vilket F(x) är maximerad. Metoden Evolutionary Search kan generera en population av slumpmässiga x-värden, utveckla dem över generationer för att hitta det optimala x-värdet.

Kodexempel i 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;  
}  

I det här exemplet använder vi metoden Evolutionary Search för att optimera funktionen Fibonacci. Vi genererar en population av slumpmässiga x-värden, utvecklar dem över generationer genom att välja de bästa individerna och tillämpa korsnings- och mutationsoperationer.