Algoritmo di ricerca evolutivo (Evolutionary Search) in C++: spiegazione, esempio e codice

L'algoritmo di ricerca evolutiva è un metodo di ottimizzazione basato sul meccanismo dell'evoluzione naturale. Questo algoritmo simula il processo di evoluzione degli individui all'interno di una popolazione attraverso le generazioni per trovare la soluzione migliore per un problema.

Come funziona

1. Inizializzazione della popolazione: crea una popolazione iniziale di individui generati casualmente.
2. Valutazione: valutare la qualità di ciascun individuo nella popolazione in base alla funzione obiettivo o ai criteri di valutazione.
3. Selezione: selezionare un sottoinsieme dei migliori individui della popolazione attuale in base a probabilità o criteri di selezione.
4. Evoluzione: crea una nuova generazione applicando operazioni di crossover e mutazione agli individui selezionati.
5. Iterazione: ripetere i passaggi da 2 a 4 su più generazioni finché non si ottiene una soluzione soddisfacente o si raggiunge un numero predefinito di iterazioni.

Esempio: ottimizzazione della Fibonacci funzione utilizzando la ricerca evolutiva

Consideriamo il problema di ottimizzazione della Fibonacci funzione F(x) = F(x-1) + F(x-2) con F(0) = 0, F(1) = 1. Vogliamo trovare il valore di x per il quale F(x) è massimizzato. Il metodo di ricerca evolutiva può generare una popolazione di valori x casuali, farli evolvere attraverso le generazioni per trovare il valore x ottimale.

Esempio di codice 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 questo esempio, utilizziamo il metodo di ricerca evolutiva per ottimizzare la Fibonacci funzione. Generiamo una popolazione di valori x casuali, li evolviamo attraverso le generazioni selezionando i migliori individui e applicando operazioni di crossover e mutazione.