Un algoritmo genetico è un algoritmo di ricerca euristico adattivo ispirato alla teoria dell'evoluzione della Natura di Darwin .' Viene utilizzato per risolvere problemi di ottimizzazione nell'apprendimento automatico. È uno degli algoritmi importanti in quanto aiuta a risolvere problemi complessi che richiederebbero molto tempo per essere risolti.

Gli algoritmi genetici vengono ampiamente utilizzati in diverse applicazioni del mondo reale, ad esempio, Progettazione di circuiti elettronici, decifrazione di codici, elaborazione di immagini e creatività artificiale.

In questo argomento spiegheremo in dettaglio l'algoritmo genetico, comprese le terminologie di base utilizzate nell'algoritmo genetico, come funziona, i vantaggi e i limiti dell'algoritmo genetico, ecc.

Cos'è un algoritmo genetico?

Prima di comprendere l'algoritmo genetico, comprendiamo innanzitutto le terminologie di base per comprendere meglio questo algoritmo:

Popolazione:La popolazione è il sottoinsieme di tutte le soluzioni possibili o probabili che possono risolvere il problema dato.Cromosomi:Un cromosoma è una delle soluzioni nella popolazione per un dato problema e la raccolta di geni genera un cromosoma.Gene:Un cromosoma è diviso in un gene diverso o è un elemento del cromosoma.Alleli:L'allele è il valore fornito al gene all'interno di un particolare cromosoma.Funzione fitness:La funzione fitness viene utilizzata per determinare il livello di fitness dell'individuo nella popolazione. Significa la capacità di un individuo di competere con altri individui. In ogni iterazione, gli individui vengono valutati in base alla loro funzione fisica.Operatori genetici:In un algoritmo genetico, l'individuo migliore si accoppia per rigenerare la prole meglio dei genitori. Qui gli operatori genetici svolgono un ruolo nel modificare la composizione genetica della generazione successiva.Selezione

Dopo aver calcolato l'idoneità di ogni esistente nella popolazione, viene utilizzato un processo di selezione per determinare quale delle individualità della popolazione riuscirà a riprodursi e produrre il seme che formerà la generazione successiva.

Tipi di stili di selezione disponibili

Selezione della ruota della roulette Selezione evento Selezione basata sul rango

Quindi, ora possiamo definire un algoritmo genetico come un algoritmo di ricerca euristico per risolvere problemi di ottimizzazione. È un sottoinsieme di algoritmi evolutivi, che viene utilizzato nell'informatica. Un algoritmo genetico utilizza concetti di selezione genetica e naturale per risolvere problemi di ottimizzazione.

ops concetti in Java

Come funzionano gli algoritmi genetici?

L’algoritmo genetico lavora sul ciclo generazionale evolutivo per generare soluzioni di alta qualità. Questi algoritmi utilizzano diverse operazioni che migliorano o sostituiscono la popolazione per fornire una soluzione di adattamento migliore.

Fondamentalmente prevede cinque fasi per risolvere i complessi problemi di ottimizzazione, che sono indicati di seguito:

Inizializzazione Compito di forma fisica Selezione Riproduzione Terminazione

1. Inizializzazione

Il processo di un algoritmo genetico inizia generando l’insieme di individui, che viene chiamato popolazione. Qui ogni individuo è la soluzione per il problema dato. Un individuo contiene o è caratterizzato da un insieme di parametri chiamati Geni. I geni sono combinati in una stringa e generano cromosomi, che è la soluzione al problema. Una delle tecniche più popolari per l'inizializzazione è l'uso di stringhe binarie casuali.

2. Compito di idoneità

La funzione Fitness viene utilizzata per determinare quanto è in forma un individuo? Significa la capacità di un individuo di competere con altri individui. In ogni iterazione, gli individui vengono valutati in base alla loro funzione fisica. La funzione fitness fornisce un punteggio fitness a ciascun individuo. Questo punteggio determina ulteriormente la probabilità di essere selezionati per la riproduzione. Più alto è il punteggio di fitness, maggiori sono le possibilità di essere selezionati per la riproduzione.

3. Selezione

La fase di selezione prevede la selezione degli individui per la riproduzione della prole. Tutti gli individui selezionati vengono poi disposti a coppia di due per aumentare la riproduzione. Quindi questi individui trasferiscono i loro geni alla generazione successiva.

Sono disponibili tre tipi di metodi di selezione:

• Selezione della ruota della roulette
• Selezione del torneo
• Selezione basata sul rango

4. Riproduzione

Dopo il processo di selezione, la creazione di un figlio avviene nella fase di riproduzione. In questa fase, l'algoritmo genetico utilizza due operatori di variazione applicati alla popolazione madre. Di seguito i due operatori coinvolti nella fase di riproduzione:

Incrocio:Il crossover gioca un ruolo molto significativo nella fase di riproduzione dell'algoritmo genetico. In questo processo, all'interno dei geni viene selezionato casualmente un punto di crossover. Quindi l'operatore crossover scambia le informazioni genetiche di due genitori della generazione attuale per produrre un nuovo individuo che rappresenta la prole.

I geni dei genitori vengono scambiati tra loro fino al raggiungimento del punto di crossover. Questa prole appena generata viene aggiunta alla popolazione. Questo processo è anche chiamato crossover. Tipi di stili crossover disponibili:
• Incrocio di un punto
• Incrocio a due punti
• Incrocio di livrea
• Crossover di algoritmi ereditabili
Mutazione
L'operatore della mutazione inserisce geni casuali nella prole (nuovo bambino) per mantenere la diversità nella popolazione. Può essere fatto capovolgendo alcuni bit nei cromosomi.
La mutazione aiuta a risolvere il problema della convergenza prematura e migliora la diversificazione. L'immagine seguente mostra il processo di mutazione:
Tipi di stili di mutazione disponibili,
Mutazione del flip bit Mutazione gaussiana Mutazione di scambio/scambio

5. Risoluzione

Dopo la fase di riproduzione viene applicato un criterio di arresto come base per la terminazione. L'algoritmo termina una volta raggiunta la soluzione di idoneità soglia. Identificherà la soluzione finale come la migliore soluzione nella popolazione.

arraylist ordinato java

Flusso di lavoro generale di un semplice algoritmo genetico

Vantaggi dell'algoritmo genetico

• Le capacità parallele degli algoritmi genetici sono le migliori.
• Aiuta a ottimizzare vari problemi come funzioni discrete, problemi multi-obiettivo e funzioni continue.
• Fornisce una soluzione a un problema che migliora nel tempo.
• Un algoritmo genetico non necessita di informazioni derivate.

Limitazioni degli algoritmi genetici

• Gli algoritmi genetici non sono algoritmi efficienti per risolvere problemi semplici.
• Non garantisce la qualità della soluzione finale a un problema.
• Il calcolo ripetitivo dei valori di fitness può generare alcune sfide computazionali.

Differenza tra algoritmi genetici e algoritmi tradizionali

• Uno spazio di ricerca è l’insieme di tutte le possibili soluzioni al problema. Nell'algoritmo tradizionale viene mantenuto un solo insieme di soluzioni, mentre in un algoritmo genetico possono essere utilizzati diversi insiemi di soluzioni nello spazio di ricerca.
• Gli algoritmi tradizionali necessitano di più informazioni per eseguire una ricerca, mentre gli algoritmi genetici necessitano di una sola funzione obiettivo per calcolare l'idoneità di un individuo.
• Gli algoritmi tradizionali non possono funzionare in parallelo, mentre gli algoritmi genetici possono funzionare in parallelo (il calcolo dell'idoneità delle individualità è indipendente).
• Una grande differenza negli algoritmi genetici è che invece di operare direttamente sui risultati del cercatore, gli algoritmi ereditari operano sulle loro rappresentazioni (o rendering), spesso definite cromosomi.
• Una delle grandi differenze tra l’algoritmo tradizionale e l’algoritmo genetico è che non opera direttamente sulle soluzioni candidate.
• Gli algoritmi tradizionali possono generare un solo risultato alla fine, mentre gli algoritmi genetici possono generare più risultati ottimali da generazioni diverse.
• L'algoritmo tradizionale non ha maggiori probabilità di generare risultati ottimali, mentre gli algoritmi genetici non garantiscono di generare risultati globali ottimali, ma esiste anche una grande possibilità di ottenere il risultato ottimale per un problema poiché utilizza operatori genetici come Crossover e Mutazione.
• Gli algoritmi tradizionali sono di natura deterministica, mentre gli algoritmi genetici sono di natura probabilistica e stocastica.