Che cos'è l'algoritmo genetico?
L'algoritmo genetico è un metodo per risolvere problemi di ottimizzazione vincolati e non vincolati, basato sulla selezione naturale, il processo che guida l'evoluzione biologica. L'algoritmo genetico modifica ripetutamente una popolazione di soluzioni individuali. A ogni passaggio, l'algoritmo genetico seleziona dalla popolazione attuale gli individui che diventeranno genitori e li utilizza per generare i figli della generazione successiva. Nel corso delle generazioni successive, la popolazione "evolve" verso una soluzione ottimale. È possibile applicare l'algoritmo genetico per risolvere una varietà di problemi di ottimizzazione che non sono adatti agli algoritmi di ottimizzazione standard, inclusi problemi in cui la funzione obiettivo è discontinua, non differenziabile, stocastica o altamente non lineare. L'algoritmo genetico può risolvere problemi di programmazione mista di numeri interi, in cui alcuni componenti possono avere solo valori interi.
Questo diagramma di flusso delinea i principali passaggi algoritmici. Per i dettagli, vedere Come funziona l'algoritmo genetico .
L'algoritmo genetico utilizza tre tipi principali di regole in ogni fase per creare la generazione successiva dalla popolazione attuale:
Le regole di selezione selezionano gli individui, chiamati genitori, che contribuiscono alla popolazione nella generazione successiva. La selezione è generalmente stocastica e può dipendere dai punteggi dei singoli individui.
Le regole del crossover uniscono due genitori per formare i figli della generazione successiva.
Le regole di mutazione applicano modifiche casuali ai singoli genitori per formare i figli.
L'algoritmo genetico differisce da un algoritmo di ottimizzazione classico basato sulle derivate in due modi principali, come riassunto nella seguente tabella:
| Algoritmo classico | Algoritmo genetico |
|---|---|
Genera un singolo punto a ogni iterazione. La sequenza di punti si avvicina a una soluzione ottimale. | Genera una popolazione di punti a ogni iterazione. Il punto migliore nella popolazione si avvicina alla soluzione ottimale. |
Seleziona il punto successivo nella sequenza mediante un calcolo deterministico. | Seleziona la popolazione successiva mediante un calcolo che utilizza generatori di numeri casuali. |
In genere converge rapidamente verso una soluzione locale. | In genere sono necessarie numerose valutazioni di funzioni per convergere. Potrebbe convergere o meno verso un minimo locale o globale. |
