Algoritm de căutare evolutivă (Evolutionary Search) în C++- Explicație, Exemplu și Cod

Algoritmul Evolutionary Search este o metodă de optimizare bazată pe mecanismul evoluției naturale. Acest algoritm simulează procesul de evoluție al indivizilor dintr-o populație de-a lungul generațiilor pentru a găsi cea mai bună soluție pentru o problemă.

Cum functioneaza

1. Inițializarea populației: Creați o populație inițială de indivizi generați aleatoriu.
2. Evaluare: Evaluați calitatea fiecărui individ din populație pe baza funcției obiective sau a criteriilor de evaluare.
3. Selecție: Selectați un subset al celor mai buni indivizi din populația curentă pe baza probabilităților sau a criteriilor de selecție.
4. Evoluție: Creați o nouă generație aplicând operațiuni de încrucișare și mutație indivizilor selectați.
5. Iterație: Repetați pașii de la 2 la 4 pe mai multe generații până când se obține o soluție satisfăcătoare sau se ajunge la un număr predefinit de iterații.

Exemplu: Optimizarea Fibonacci funcției folosind Căutarea evolutivă

Se consideră problema de optimizare a Fibonacci funcției F(x) = F(x-1) + F(x-2) cu F(0) = 0, F(1) = 1. Vrem să aflăm valoarea lui x pentru care F(x) este maximizat. Metoda de căutare evolutivă poate genera o populație de valori aleatoare x, le poate evolua de-a lungul generațiilor pentru a găsi valoarea x optimă.

Exemplu de cod în 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;  
}  

În acest exemplu, folosim metoda Evolutionary Search pentru a optimiza Fibonacci funcția. Generăm o populație de valori aleatoare x, le evoluăm de-a lungul generațiilor selectând cei mai buni indivizi și aplicând operații de încrucișare și mutație.