Algoritam evolucijskog pretraživanja (Evolutionary Search) u C++- objašnjenje, primjer i kod

Algoritam evolucijskog pretraživanja je metoda optimizacije koja se temelji na mehanizmu prirodne evolucije. Ovaj algoritam simulira proces evolucije pojedinaca unutar populacije kroz generacije kako bi se pronašlo najbolje rješenje za problem.

Kako radi

1. Inicijalizacija populacije: Stvorite početnu populaciju nasumično generiranih jedinki.
2. Evaluacija: Ocijenite kvalitetu svakog pojedinca u populaciji na temelju objektivne funkcije ili kriterija procjene.
3. Odabir: Odaberite podskup najboljih pojedinaca iz trenutne populacije na temelju vjerojatnosti ili kriterija odabira.
4. Evolucija: Stvorite novu generaciju primjenom operacija križanja i mutacije na odabrane jedinke.
5. Ponavljanje: Ponavljajte korake 2 do 4 tijekom više generacija dok se ne postigne zadovoljavajuće rješenje ili dok se ne postigne unaprijed definirani broj ponavljanja.

Primjer: Optimiziranje Fibonacci funkcije pomoću evolucijskog pretraživanja

Razmotrimo problem optimizacije funkcije Fibonacci F(x) = F(x-1) + F(x-2) s F(0) = 0, F(1) = 1. Želimo pronaći vrijednost x za koju F(x) je maksimiziran. Metoda evolucijskog pretraživanja može generirati populaciju nasumičnih x vrijednosti, razvijati ih kroz generacije kako bi se pronašla optimalna x vrijednost.

Primjer koda u 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;  
}  

U ovom primjeru koristimo metodu evolucijskog pretraživanja za optimizaciju Fibonacci funkcije. Generiramo populaciju nasumičnih x vrijednosti, razvijamo ih kroz generacije odabirom najboljih jedinki i primjenom operacija križanja i mutacije.