Glossario · method

Algoritmo Genetico

Metaeuristica basata su popolazione che imita la selezione naturale e la trasmissione genetica, facendo evolvere iterativamente una popolazione di soluzioni candidate tramite operatori di selezione, crossover e mutazione.

Genetic AlgorithmGAAlgoritmo EvolutivoMetaeuristica Basata su PopolazioneNSGA-II

L'algoritmo genetico è stato introdotto da Holland (1975) e reso popolare da Goldberg (1989). L'algoritmo mantiene molte soluzioni candidate (individui) contemporaneamente; ogni individuo è codificato come cromosoma (binario, intero, permutazione o reale). Ogni iterazione applica tre operatori principali: selezione (roulette, torneo, basata sul rango), crossover (un punto, multipunto, uniforme o PMX/OX per permutazioni) e mutazione (bit-flip, swap, inversione). La funzione di fitness deriva dall'obiettivo e guida la pressione selettiva. L'elitismo conserva i migliori individui; meccanismi di diversità (niching, crowding) prevengono la convergenza prematura. La teoria della convergenza si basa sullo schema theorem (Holland 1975); il teorema No Free Lunch (Wolpert e Macready 1997) mostra che nessuna metaeuristica domina universalmente. L'estensione multi-obiettivo NSGA-II (Deb Pratap Agarwal Meyarivan 2002) è lo standard industriale per approssimare frontiere di Pareto. I problemi di permutazione (TSP, scheduling) richiedono operatori specializzati. Gli algoritmi genetici non garantiscono l'ottimo globale ma forniscono buone soluzioni in tempo ragionevole e sono preferiti per problemi combinatori, misti interi e black-box. Riferimenti: Goldberg (1989), Eiben e Smith (2015).

Örnek

Un'officina di mobili con 30 lavori su 6 macchine cerca una sequenza che minimizzi il makespan. La programmazione intera esatta richiede ore su istanze grandi; un algoritmo genetico con popolazione 80, codifica a permutazione, crossover OX e mutazione swap raggiunge un makespan inferiore del 22 per cento rispetto all'euristica iniziale in 200 generazioni e 14 minuti. La soluzione non è dimostrabilmente ottima ma è sufficientemente buona per la pianificazione giornaliera e applicabile dal pianificatore dell'officina.