Come ottimizzare i set di feature con algoritmi genetici

Ottimizzazione dei set di feature con algoritmi genetici

Prerequisiti

Gli Algoritmi Genetici sono un argomento avanzato. Nonostante il contenuto sia stato preparato tenendo conto delle esigenze di un principiante, il lettore dovrebbe essere familiare con i fondamenti della Programmazione e degli Algoritmi di Base prima di iniziare questo articolo. Inoltre, considera di affinare le tue competenze matematiche; esse saranno di grande aiuto per comprendere gli esempi.

Introduzione all’ottimizzazione

L’ottimizzazione comporta l’arte di migliorare le prestazioni. In qualsiasi processo, ci troviamo di fronte a una serie di input e output, come illustrato nel diagramma.

L’ottimizzazione consiste nella ricerca dei valori di input che producono i risultati di output più favorevoli. Il concetto di favorevole può variare a seconda del problema specifico, ma in contesti matematici, di solito comporta la ricerca di una o più funzioni obiettivo da massimizzare o minimizzare attraverso l’aggiustamento dei parametri di input.

Consideriamo y =f(x); se f'(x)=0 in un punto x=x*, allora l’ottimo (max o min) o il punto di flessione esiste in quel punto.

A una più attenta esame, diventa evidente che la prima derivata non nulla dell’ordine superiore è tipicamente indicata come ‘n,’ tale che.

Se n è un numero dispari, x* è un punto di flessione.
Altrimenti, x* è un punto di ottimo locale.

Approfondendo questa idea…

Se il valore della successiva derivata di ordine superiore è +ve, x* è un punto di minimo locale.
Se il valore della successiva derivata di ordine superiore è -ve, x* è un punto di massimo locale.

Ad esempio:

Principi dell’ottimizzazione

Considera il seguente problema di ottimizzazione vincolata:

In base alle caratteristiche dei vincoli, viene identificata una regione ammissibile. Qualsiasi punto situato all’interno di questa regione ammissibile è considerato un potenziale candidato per la soluzione ottimale. I punti situati all’interno della regione ammissibile sono definiti punti liberi, mentre quelli situati sul confine della regione sono classificati come punti vincolati. Pertanto, una soluzione ottimale può manifestarsi come un punto libero o un punto vincolato all’interno della regione ammissibile. I metodi basati sul gradiente, in particolare le approcci basati sulle derivate, sono stati un mezzo convenzionale per affrontare i problemi di ottimizzazione non vincolata. Tuttavia, è importante notare che presentano diverse limitazioni e svantaggi.

Che cos’è un Algoritmo Genetico?

Nel corso della storia, la natura ha sempre fornito un’abbondante fonte di ispirazione per l’umanità. Gli Algoritmi Genetici (AG) sono algoritmi basati sulla ricerca radicati nei principi della selezione naturale e della genetica. Gli AG costituiscono un sottoinsieme del campo più ampio della computazione conosciuto come Computazione Evolutiva.

Gli Algoritmi Genetici (AG) sono stati originariamente sviluppati da John Holland, insieme ai suoi studenti e colleghi presso l’Università del Michigan, in particolare David E. Goldberg. Sin dalla loro creazione, gli AG sono stati applicati a una vasta gamma di problemi di ottimizzazione, ottenendo sempre un alto livello di successo.

Nei Gli Algoritmi Genetici (AG), viene stabilita una popolazione di soluzioni potenziali per un determinato problema. Queste soluzioni vengono quindi sottoposte a processi di ricombinazione e mutazione, che riflettono i principi presenti nella genetica naturale, dando origine alla creazione di nuovi discendenti. Questo processo iterativo si sviluppa attraverso diverse generazioni. Ogni individuo o soluzione candidata viene valutato in base al suo valore di fitness, determinato tipicamente dalle sue prestazioni nella funzione obiettivo. Gli individui più adatti hanno una maggiore probabilità di riprodursi e generare discendenti ancora più capaci. Questo si allinea con la Teoria Darwiniana della “Sopravvivenza del più adatto.”

In questo modo, gli AG evolvono e affinano continuamente la qualità degli individui o delle soluzioni attraverso le generazioni fino a quando non viene raggiunto un criterio di stop predefinito. Gli Algoritmi Genetici mostrano un notevole grado di casualità nelle loro operazioni, ma superano i semplici metodi di ricerca locale casuale, in quanto incorporano anche informazioni storiche per guidare la ricerca delle soluzioni ottimali.

Perché Algoritmo Genetico?

Gli Algoritmi Genetici (AG) possiedono la notevole capacità di fornire una soluzione “sufficientemente buona” in modo tempestivo, specialmente quando si affrontano problemi di grande scala in cui gli algoritmi tradizionali potrebbero avere difficoltà a fornire una soluzione. Gli AG offrono un framework versatile e generico per affrontare problemi di ottimizzazione complessi. Ecco alcuni vantaggi nell’utilizzo degli Algoritmi Genetici (AG):

Versatilità: Gli AG possono essere applicati a una vasta gamma di problemi di ottimizzazione, rendendoli una scelta versatile per vari settori, tra cui ingegneria, finanza, biologia e altro.
Ricerca globale: Gli AG eccellono nell’esplorare l’intero spazio di ricerca, consentendo di trovare soluzioni che potrebbero essere sfuggite agli algoritmi di ricerca locale. Ciò li rende adatti a problemi con molteplici ottimi locali.
Nessuna necessità di derivate: A differenza di molte tecniche di ottimizzazione, gli AG non richiedono le derivate della funzione obiettivo, rendendoli applicabili a problemi con paesaggi di fitness non continui, rumorosi o complessi.
Parallelismo: Gli AG possono essere parallelizzati in modo efficace, consentendo una convergenza più rapida su sistemi di calcolo ad alte prestazioni.
Natura stocastica: La natura stocastica degli AG garantisce che possano sfuggire agli ottimi locali ed esplorare più a fondo lo spazio di ricerca.
Adattabilità: Gli AG possono adattare e regolare le loro strategie di ricerca nel tempo, il che è particolarmente utile per problemi di ottimizzazione dinamica o in cambiamento.
Diversità delle soluzioni: Gli AG mantengono una popolazione diversificata di soluzioni, il che può aiutare a trovare una vasta gamma di possibili soluzioni e prevenire la convergenza prematura.
Interpretabilità: In alcuni casi, gli AG possono fornire approfondimenti sulla struttura dello spazio delle soluzioni, aiutando gli utenti a comprendere meglio il problema.
Problematiche combinatorie: Gli AG si adattano bene ai problemi di ottimizzazione combinatoria, come il problema del commesso viaggiatore e la pianificazione dei lavori.
Evoluzione parallela: Gli AG possono essere utilizzati per evolvere contemporaneamente più soluzioni, il che è prezioso nell’ottimizzazione multi-obiettivo e in altri scenari complessi.

È importante notare che sebbene i GAs offrano questi vantaggi, non sono sempre la scelta migliore per ogni problema di ottimizzazione e le loro prestazioni possono variare a seconda delle caratteristiche del problema. Un’adeguata analisi del problema e la selezione dell’algoritmo sono essenziali per ottenere risultati ottimali.

Terminologia degli Algoritmi Genetici

Popolazioni e generazioni: Una popolazione è un array di individui. Ad esempio, se la dimensione della popolazione è 100 e il numero di variabili nella funzione di fitness è 3, si rappresenta la popolazione con una matrice 100×3. Lo stesso individuo può apparire più di una volta nella popolazione. Ad esempio, l’individuo (2, -3, 1) può apparire in più righe dell’array. Ad ogni iterazione, l’algoritmo genetico esegue una serie di calcoli sulla popolazione corrente per produrre una nuova popolazione. Ogni popolazione successiva è chiamata una nuova generazione.
Genitori e figli: Per creare la prossima generazione, l’algoritmo genetico seleziona determinati individui nella popolazione corrente, chiamati genitori, e li utilizza per creare individui nella prossima generazione, chiamati figli. Tipicamente, l’algoritmo ha maggiori probabilità di selezionare genitori con valori di fitness migliori.
Individui: Un individuo è qualsiasi punto a cui è possibile applicare la funzione di fitness. Il valore della funzione di fitness per un individuo è il suo punteggio. Ad esempio, se la funzione di fitness è:
- f(x1,x2,x3)=(2×1+1)2+(3×2+4)2+(x3−2)2
- Il vettore (2, -3, 1), la cui lunghezza è il numero di variabili nel problema, è un individuo. Il punteggio dell’individuo (2, –3, 1) è f(2, –3, 1) = 51.

Un individuo viene talvolta chiamato genoma o cromosoma, e le voci del vettore di un individuo come geni.

Funzioni di fitness: La funzione di fitness è la funzione che si desidera ottimizzare. Per gli algoritmi di ottimizzazione standard, questa è nota come funzione obiettivo.
Valori di fitness e migliori valori di fitness: Il valore di fitness di un individuo è il valore della funzione di fitness per quell’individuo. Il miglior valore di fitness per una popolazione è il valore di fitness più piccolo o più grande per qualsiasi individuo nella popolazione, a seconda del problema di ottimizzazione.
Convergenza: Il punto in cui l’GA raggiunge una soluzione che soddisfa i criteri di terminazione. Questa può essere una soluzione ottimale o quasi ottimale.
Spazio di ricerca: L’insieme di tutte le possibili soluzioni per il problema di ottimizzazione.
Diversità: La diversità si riferisce alla distanza media tra gli individui in una popolazione. Una popolazione ha una diversità elevata se la distanza media è grande; altrimenti, ha una diversità bassa. La diversità è essenziale per l’algoritmo genetico perché consente all’algoritmo di cercare in una regione di spazio più ampia.
Genotipo: La rappresentazione interna di un cromosoma (ad esempio, una stringa binaria o numerica).
Fenotipo: La soluzione effettiva rappresentata da un cromosoma. Viene ottenuta decodificando il genotipo.
Tasso di crossover: La probabilità che due genitori subiscano un crossover per produrre discendenti in una nuova generazione.
Tasso di mutazione: La probabilità che un gene (o una porzione del cromosoma) subisca una mutazione in una nuova generazione.

Algoritmo Genetico Fondamentale (GA): Pseudocodice

Strategie Dettagliate di un Algoritmo Genetico Fondamentale (GA)

Codifica e Popolazione

Il cromosoma codifica una soluzione nello spazio di ricerca

Di solito come stringhe di 0 e 1
Se l è la lunghezza della stringa, il numero di cromosomi diversi (o stringhe) è 2^l

Popolazione

Un insieme di cromosomi in una generazione
La dimensione della popolazione è di solito costante
La pratica comune è quella di scegliere la popolazione iniziale in modo casuale.

Valutazione della Fitness

La funzione di fitness/obiettivo è associata ad ogni cromosoma.
Ciò indica il grado di bontà della soluzione codificata.
Se si vuole risolvere un problema di minimizzazione, allora fitness = 1 / obiettivo o fitness = -1 * obiettivo.
Se si vuole risolvere un problema di massimizzazione, allora fitness = obiettivo

Selezione

Numero maggiore di copie per le stringhe migliori.
Numero minore di copie per le stringhe peggiori.
Sistema di selezione proporzionale.
- Il numero di copie prese è direttamente proporzionale alla sua fitness.
- Imita in parte la procedura di selezione naturale.
Selezione a ruota della roulette e selezione a torneo sono due procedure di selezione comunemente utilizzate.

Crossover

Scambio di informazioni genetiche.
Avviene tra cromosomi genitori selezionati casualmente.
Crossover a punto singolo e crossover uniforme sono gli schemi più comunemente utilizzati.
Operazione probabilistica.

Mutazione

Alterazione casuale nella struttura genetica.
Introduce diversità genetica nella popolazione.
Esplorazione di nuove aree di ricerca.
La mutazione di un gene binario comporta una semplice negazione del bit.
La mutazione di un gene codificato in forma reale può essere definita in vari modi.
Operazione probabilistica.

Elitismo

Una strategia che prevede di preservare gli individui con le prestazioni migliori da una generazione all’altra.
Gli individui più adatti sono garantiti di sopravvivere e diventare parte della generazione successiva senza subire alcuna operazione genetica come crossover o mutazione.
L’elitismo garantisce che le migliori soluzioni trovate finora non vengano perse durante il processo evolutivo e possano continuare a contribuire alla popolazione.
Assicura un miglioramento costante e una convergenza accelerata.

Criteri di terminazione

Il ciclo di selezione, crossover e mutazione viene ripetuto un certo numero di volte fino a quando non si verifica una di queste condizioni.
Il valore medio della fitness di una popolazione è più o meno costante per diverse generazioni.
Viene raggiunto il valore desiderato della funzione obiettivo da almeno una stringa nella popolazione.

Il numero di generazioni (o iterazioni) è maggiore di una soglia (comunemente utilizzata).

Variazioni negli Algoritmi Genetici (GA)

Differential Evolution (DE): DE è una variante di GA specificamente progettata per problemi di ottimizzazione con valori reali. Utilizza operatori di mutazione e ricombinazione basati su vettori.
Estimation of Distribution Algorithms (EDAs): Gli EDAs modellano e apprendono la distribuzione di probabilità delle soluzioni promettenti nella popolazione e utilizzano questa distribuzione per generare nuove soluzioni candidate.
Self-Adaptive Genetic Algorithms: Consentono all’algoritmo di adattare i suoi operatori genetici (tassi di mutazione, tipi di crossover) in base alle caratteristiche della popolazione in evoluzione, garantendo una convergenza efficiente.
Niching Algorithms: Questi algoritmi si concentrano sulla ricerca di molteplici soluzioni diverse in un’unica esecuzione, spesso in problemi di ottimizzazione multimodale in cui ci sono più picchi o modalità nel paesaggio della fitness.
Multi-objective Evolutionary Algorithms (MOEAs): I MOEAs affrontano problemi con obiettivi multipli in conflitto. Mirano a trovare un insieme di soluzioni Pareto-ottimali che rappresentano compromessi tra questi obiettivi.
Algoritmi ibridi: Integrazione di GA con altre tecniche di ottimizzazione, modelli di apprendimento automatico o euristiche specifiche del dominio per migliorare le prestazioni e la robustezza.

Ho cercato di fornire una panoramica sintetica sugli Algoritmi Genetici e sull’Ottimizzazione. Tuttavia, se avete domande specifiche o avete bisogno di informazioni più dettagliate su questo argomento esteso, non esitate a chiedere nei commenti.

Apprezzo il vostro tempo e attenzione! Potete contattarmi su Linkedin.

Algorithm,Genetic Algorithm