Introduzione agli algoritmi genetici nell'apprendimento automatico

introduction genetic algorithms machine learning

miglior programma per il monitoraggio della temperatura della cpu

Questo tutorial sugli algoritmi genetici spiega in dettaglio cosa sono gli algoritmi genetici e il loro ruolo nell'apprendimento automatico :

Nel Tutorial precedente , abbiamo imparato a conoscere i modelli di reti neurali artificiali - Perceptron multistrato, Backpropagation, Radial Bias e Kohonen Self Organizing Maps inclusa la loro architettura.

Ci concentreremo sugli algoritmi genetici che sono arrivati ​​molto prima delle reti neurali, ma ora GA è stata rilevata da NN. Tuttavia, GA ha ancora applicazioni nella vita reale come problemi di ottimizzazione come la pianificazione, i giochi, la robotica, la progettazione hardware, i problemi dei venditori ambulanti, ecc.

Gli algoritmi genetici sono algoritmi basati sull'idea evolutiva della selezione naturale e della genetica. I GA sono algoritmi di ricerca euristica adattiva, ovvero gli algoritmi seguono uno schema iterativo che cambia nel tempo. È un tipo di apprendimento per rinforzo in cui il feedback è necessario senza indicare il percorso corretto da seguire. Il feedback può essere positivo o negativo.

=> Leggi la serie completa di formazione sull'apprendimento automatico

Cosa imparerai:

• Perché utilizzare algoritmi genetici
  • Sfondo biologico di algoritmi genetici
• Cosa sono gli algoritmi genetici
  • Correlazione di un cromosoma con GA
  • Terminologia importante in GA
  • Un semplice algoritmo genetico
  • Metodo di selezione della ruota della roulette
  • Altri metodi di selezione
  • Crossover
  • Mutazione
  • Quando fermare l'algoritmo genetico
• Vantaggi e svantaggi dell'algoritmo genetico
• Applicazioni di algoritmi genetici
• Conclusione
  • Lettura consigliata

Perché utilizzare algoritmi genetici

I GA sono algoritmi più robusti che possono essere utilizzati per vari problemi di ottimizzazione. Questi algoritmi non si discostano facilmente in presenza di rumore, a differenza di altri algoritmi AI. Gli GA possono essere utilizzati nella ricerca di ampi spazi o spazi multimodali.

Sfondo biologico di algoritmi genetici

La genetica deriva dalla parola greca 'genesi' che significa crescere. La genetica decide i fattori di ereditarietà, le somiglianze e le differenze tra i discendenti nel processo di evoluzione. Anche gli algoritmi genetici derivano dall'evoluzione naturale.

Alcune terminologie in un cromosoma biologico

• Cromosomi: Tutte le informazioni genetiche di una specie sono memorizzate nei cromosomi.
• Geni: I cromosomi sono divisi in più parti chiamate geni.
• Alleli: I geni identificano le caratteristiche di un individuo. La possibilità di una combinazione di geni per formare proprietà è chiamata alleli. Un gene può avere alleli diversi.
• Pool genico: Tutte le possibili combinazioni di geni che sono tutti alleli in un pool di popolazione sono chiamate pool genici.
• Genoma: L'insieme di geni di una specie è chiamato genoma.
• Locus: Ogni gene ha una posizione in un genoma chiamato locus.
• Genotipo: Una combinazione completa di geni in un individuo è chiamata genotipo.
• Fenotipo: Un insieme di genotipi in una forma decodificata è chiamato fenotipo.

Cosa sono gli algoritmi genetici

Gli algoritmi genetici stimolano il processo come nei sistemi naturali per l'evoluzione. Charles Darwin ha affermato la teoria dell'evoluzione che nell'evoluzione naturale, gli esseri biologici si evolvono secondo il principio della 'sopravvivenza del più adatto'. La ricerca GA è progettata per incoraggiare la teoria della 'sopravvivenza del più adatto'.

I GA eseguono una ricerca casuale per risolvere i problemi di ottimizzazione. GA utilizza tecniche che utilizzano le informazioni storiche precedenti per indirizzare la propria ricerca verso l'ottimizzazione nel nuovo spazio di ricerca.

Correlazione di un cromosoma con GA

Il corpo umano ha cromosomi che sono fatti di geni. Un insieme di tutti i geni di una specie specifica è chiamato genoma. Negli esseri viventi, i genomi sono immagazzinati in vari cromosomi mentre in GA tutti i geni sono immagazzinati nello stesso cromosoma.

Confronto tra evoluzione naturale e terminologia dell'algoritmo genetico

Terminologia importante in GA

• Popolazione: È un gruppo di individui. La popolazione include il numero di individui sottoposti a test, le informazioni sullo spazio di ricerca ei parametri del fenotipo. In genere, la popolazione viene inizializzata in modo casuale.
• Individui: Gli individui sono un'unica soluzione nella popolazione. Un individuo ha una serie di parametri chiamati geni. Geni combinati per formare cromosomi.
• Geni: I geni sono elementi costitutivi degli algoritmi genetici. Un cromosoma è costituito da geni. I geni possono determinare la soluzione al problema. Sono rappresentati da una stringa di bit (0 o 1) di lunghezza casuale.
• Fitness: L'idoneità indica il valore del fenotipo del problema. La funzione fitness indica quanto la soluzione è vicina alla soluzione ottimale. La funzione fitness è determinata in molti modi, come la somma di tutti i parametri relativi al problema - distanza euclidea, ecc. Non esiste una regola per valutare la funzione fitness.

Un semplice algoritmo genetico

Un semplice GA ha una popolazione di singoli cromosomi. Questi cromosomi rappresentano possibili soluzioni. Gli operatori di riproduzione vengono applicati su questi set di cromosomi per eseguire mutazioni e ricombinazioni. Pertanto, è importante trovare operatori di riproduzione appropriati poiché il comportamento di GA dipende da esso.

Un semplice algoritmo genetico è il seguente:

# 1) Inizia con la popolazione creata in modo casuale.

#Due) Calcola la funzione fitness di ogni cromosoma.

# 3) Ripeti i passaggi finché non vengono creati n discendenti. I discendenti vengono creati come mostrato di seguito.

• Seleziona una coppia di cromosomi dalla popolazione.
• Crossover la coppia con probabilità p_cper formare prole.
• Mutate il crossover con probabilità p_m.

# 4) Sostituisci la popolazione originale con la nuova popolazione e vai al passaggio 2.

Vediamo i passaggi seguiti in questo processo di iterazione. Viene generata la popolazione iniziale di cromosomi. La popolazione iniziale dovrebbe contenere abbastanza geni in modo che qualsiasi soluzione possa essere generata. Il primo pool di popolazione viene generato in modo casuale.

• Selezione: Il miglior set di geni viene selezionato in base alla funzione fitness. Viene scelta la corda con la migliore funzione fitness.
• Riproduzione: I nuovi discendenti sono generati dalla ricombinazione e dalla mutazione.
• Valutazione: I nuovi cromosomi generati vengono valutati per la loro forma fisica.
• Sostituzione: In questa fase, la vecchia popolazione viene sostituita con la popolazione appena generata.

Metodo di selezione della ruota della roulette

La selezione della ruota della roulette è il metodo di selezione ampiamente utilizzato.

Il processo di selezione è breve come mostrato di seguito:

In questo metodo, viene eseguita una ricerca lineare tramite la ruota della roulette. Gli slot nella ruota vengono pesati in base al valore di fitness individuale. Il valore target viene impostato in modo casuale in base alla proporzione della somma dell'idoneità nella popolazione.

La popolazione viene quindi ricercata fino al raggiungimento del valore target. Questo metodo non garantisce il più adatto degli individui ma ha una probabilità di essere il più adatto.

Vediamo i passaggi coinvolti nella selezione della ruota della roulette.

Il valore atteso di un individuo = Forma fisica / forma fisica individuale della popolazione. Gli slot per le ruote vengono assegnati alle persone in base alla loro forma fisica. La ruota viene ruotata N volte dove N è il numero totale di individui nella popolazione. Quando una rotazione è finita, l'individuo selezionato viene inserito in un pool di genitori.

1. Lascia che il valore totale atteso di un numero di individui nella popolazione sia S.
2. Ripeti i passaggi 3-5 n volte.
3. Seleziona un numero intero compreso tra 0 e S.
4. Fai scorrere gli individui nella popolazione, somma i valori attesi fino a quando la somma è maggiore di s.
5. Viene selezionato l'individuo il cui valore atteso pone la somma oltre il limite s.

Svantaggi della selezione della ruota della roulette:

1. Se la forma fisica è molto diversa, la circonferenza della ruota della roulette sarà occupata al massimo dal cromosoma della funzione fitness più alta, quindi gli altri hanno poche possibilità di essere selezionati.
2. È rumoroso.
3. L'evoluzione dipende dalla varianza nell'idoneità della popolazione.

Altri metodi di selezione

Ci sono molti altri metodi di selezione usati in 'Selezione' passo dell'Algoritmo Genetico.

Discuteremo gli altri 2 metodi ampiamente utilizzati:

# 1) Selezione del grado: In questo metodo, a ogni cromosoma viene assegnato un valore di fitness dalla classifica. La forma fisica peggiore è 1 e la forma fisica migliore è N. È un metodo di convergenza lenta. In questo metodo, la diversità viene preservata portando a una ricerca di successo.

I potenziali genitori vengono selezionati e poi si tiene un torneo per decidere quale delle persone sarà un genitore.

# 2) Selezione del torneo: In questo metodo, viene applicata una strategia di pressione selettiva alla popolazione. L'individuo migliore è quello con la forma fisica più alta. Questo individuo è il vincitore della competizione del torneo tra gli individui Nu nella popolazione.

La popolazione del torneo insieme al vincitore viene nuovamente aggiunta al pool per generare nuovi discendenti. La differenza nei valori di fitness del vincitore e degli individui nella vasca di accoppiamento fornisce una pressione selettiva per risultati ottimali.

Crossover

È un processo di prendere 2 individui e produrre un bambino da loro. Il processo di riproduzione dopo la selezione fa cloni delle buone punture. L'operatore di crossover viene applicato sulle corde per produrre una prole migliore.

L'implementazione dell'operatore di crossover è la seguente:

1. Due individui vengono selezionati casualmente dalla popolazione per produrre prole.
2. Un cross-site viene selezionato casualmente lungo la lunghezza della stringa.
3. I valori nel sito vengono scambiati.

Il crossover eseguito può essere un crossover a punto singolo, crossover a due punti, crossover multipunto, ecc. Il crossover a punto singolo ha un sito di crossover mentre un sito di crossover a due punti ha 2 siti in cui i valori vengono scambiati.

Possiamo vederlo nell'esempio seguente:

Crossover a punto singolo

Crossover a due punti

Probabilità di crossover

P_c, la probabilità di crossover è il termine che descrive la frequenza con cui verrà eseguito il crossover. Probabilità dello 0% significa che i nuovi cromosomi saranno una copia esatta dei vecchi cromosomi, mentre la probabilità del 100% significa che tutti i nuovi cromosomi sono realizzati mediante crossover.

Mutazione

La mutazione viene eseguita dopo il crossover. Mentre il crossover si concentra solo sulla soluzione corrente, l'operazione di mutazione ricerca l'intero spazio di ricerca. Questo metodo serve per recuperare le informazioni genetiche perse e per distribuire le informazioni genetiche.

Questo operatore aiuta a mantenere la diversità genetica nella popolazione. Aiuta a prevenire i minimi locali e impedisce di generare soluzioni inutili da qualsiasi popolazione.

La mutazione viene eseguita in molti modi, ad esempio invertendo il valore di ogni gene con una piccola probabilità o eseguendo la mutazione solo se migliora la qualità della soluzione.

Alcuni dei modi di mutazione sono:

• Capovolgimento: Modifica da 0 a 1 o da 1 a 0.
• Scambio: Vengono scelte due posizioni casuali e i valori vengono scambiati.
• Inversione: Viene scelta la posizione casuale e i bit accanto ad essa vengono invertiti.

Vediamo alcuni esempi di ciascuno:

Flipping

Scambio

Inversione

Probabilità di mutazione

P_m, la probabilità di mutazione è un termine che decide la frequenza con cui i cromosomi verranno mutati. Se la probabilità di mutazione è del 100%, significa che l'intero cromosoma è cambiato. Se una mutazione non viene eseguita, la nuova prole viene generata direttamente dopo il crossover.

Un esempio di algoritmo genetico generale Probabilità di mutazione: P_m, la probabilità di mutazione è un termine che decide la frequenza con cui i cromosomi verranno mutati. Se la probabilità di mutazione è del 100%, significa che l'intero cromosoma è cambiato.

Se una mutazione non viene eseguita, la nuova prole viene generata direttamente dopo il crossover. La popolazione iniziale di cromosomi è indicata come A, B, C, D. La dimensione della popolazione è 4.

La funzione fitness è considerata come un numero di 1 nella stringa.

La somma della forma fisica è 12, il che implica che la funzione fitness media sarebbe ~ 12/4 = 3

Probabilità di crossover = 0,7

Probabilità di mutazione = 0,001

# 1) Se si selezionano B e C, il crossover non viene eseguito poiché il valore di fitness di C è inferiore al fitness medio.

#Due) B è mutato => B: 11101110 -> B^': 01101110 per preservare la diversità della popolazione

# 3) B e D sono selezionati, il crossover viene eseguito.

B: 11101110 E: 10110100 -> D: 00110100 F: 01101110

# 4) Se E è mutato, allora

E: 10110100 -> E^': 10110000

I cromosomi corrispondenti sono mostrati nella tabella sottostante. L'ordine viene inserito in modo casuale.

Sebbene l'individuo più in forma con un valore di fitness di 6 sia perso, l'idoneità media complessiva della popolazione aumenta e sarebbe: 14/4 = 3,5

Quando fermare l'algoritmo genetico

Un algoritmo genetico viene interrotto quando vengono soddisfatte alcune condizioni elencate di seguito:

# 1) Migliore convergenza individuale: Quando il livello di forma fisica minimo scende al di sotto del valore di convergenza, l'algoritmo viene interrotto. Porta a una convergenza più rapida.

# 2) Peggiore convergenza individuale: Quando gli individui meno in forma nella popolazione raggiungono il valore di fitness minimo al di sotto della convergenza, l'algoritmo viene interrotto. In questo metodo, lo standard minimo di fitness viene mantenuto nella popolazione. Significa che l'individuo migliore non è garantito ma saranno presenti individui con un minimo di fitness.

# 3) Somma della forma fisica: In questo metodo, se la somma dell'idoneità è minore o uguale al valore di convergenza, la ricerca viene interrotta. Garantisce che tutta la popolazione rientri nella fascia di fitness.

# 4) Fitness mediano: In questo metodo, almeno la metà degli individui nella popolazione sarà migliore o uguale al valore di convergenza.

Alcuni criteri di convergenza o condizioni di arresto possono essere:

• Quando si è evoluto un numero specificato di generazioni.
• Quando il tempo specificato per eseguire l'algoritmo è stato raggiunto.
• Quando il valore di fitness della popolazione non cambia ulteriormente con le iterazioni.

Vantaggi e svantaggi dell'algoritmo genetico

I vantaggi di un algoritmo genetico sono:

1. Ha uno spazio di soluzione più ampio.
2. È più facile scoprire l'ottimo globale.
3. Parallelismo: Più GA possono essere eseguiti insieme utilizzando la stessa CPU senza interferire tra loro. Corrono parallelamente in isolamento.

Limitazioni di GA:

1. L'identificazione della funzione fitness è una limitazione.
2. La convergenza degli algoritmi può essere troppo veloce o troppo lenta.
3. Esiste una limitazione nella selezione dei parametri come crossover, probabilità di mutazione, dimensione della popolazione ecc.

Applicazioni di algoritmi genetici

GA è efficace per risolvere problemi di alta dimensione. Un GA viene utilizzato efficacemente quando lo spazio di ricerca è molto ampio, non sono disponibili tecniche matematiche di risoluzione dei problemi e altri algoritmi di ricerca tradizionali non funzionano.

Alcune applicazioni in cui viene utilizzato GA:

• Problema di ottimizzazione: Uno dei migliori esempi dei problemi di ottimizzazione è il problema del venditore di viaggi che utilizza GA. Altri problemi di ottimizzazione come la pianificazione del lavoro, GA per l'ottimizzazione della qualità del suono sono ampiamente utilizzati.
• Modello del sistema immunitario: Gli GA vengono utilizzati per modellare vari aspetti del sistema immunitario per singoli geni e famiglie multi-gene durante il tempo evolutivo.
• Apprendimento automatico: Le GA sono state utilizzate per risolvere problemi relativi a classificazione, previsione, creare regole per l'apprendimento e la classificazione .

Conclusione

Gli algoritmi genetici si basano sul metodo dell'evoluzione naturale. Questi algoritmi sono diversi dagli altri algoritmi di classificazione in quanto utilizzano parametri codificati (0 o 1), ci sono più numeri di individui in una popolazione e utilizzano il metodo probabilistico per la convergenza.

Con il processo di crossover e mutazione, gli GA convergono alle generazioni successive. L'esecuzione di un algoritmo GA non garantisce sempre una soluzione di successo. Gli algoritmi genetici sono altamente efficienti nell'ottimizzazione - problemi di pianificazione del lavoro.

Spero che questo tutorial abbia arricchito le tue conoscenze sul concetto di algoritmi genetici !!

=> Visita qui per l'esclusiva serie di machine learning

Lettura consigliata

• Test basati su modelli utilizzando algoritmi genetici
• Data mining vs machine learning vs intelligenza artificiale vs deep learning
• Tutorial sull'apprendimento automatico: introduzione al machine learning e alle sue applicazioni
• Tipi di machine learning: apprendimento supervisionato e non supervisionato
• Una guida completa alla rete neurale artificiale nell'apprendimento automatico
• 11 strumenti software di machine learning più popolari nel 2021
• Le 13 migliori aziende di machine learning (elenco aggiornato 2021)
• Cos'è Support Vector Machine (SVM) nel machine learning