Panoramica sull'algoritmo genetico
Le tecniche di ottimizzazione sono le tecniche utilizzate per scoprire la migliore soluzione tra tutte le possibili soluzioni disponibili sotto i vincoli presenti. Quindi l'algoritmo genetico è uno di questi algoritmi di ottimizzazione che è costruito sulla base del naturale processo evolutivo della nostra natura. L'idea di selezione naturale ed eredità genetica è qui utilizzata. Utilizza la ricerca casuale guidata, a differenza di altri algoritmi, vale a dire, trovare la soluzione ottimale iniziando con una funzione di costo iniziale casuale e quindi cercando solo nello spazio che aveva il minor costo (nella direzione guidata). Adatto quando si lavora con set di dati enormi e complessi.
Che cos'è un algoritmo genetico?
L'algoritmo genetico si basa sulla struttura genetica e sul comportamento del cromosoma della popolazione. Le seguenti cose sono alla base degli algoritmi genetici.
- Ogni cromosoma indica una possibile soluzione. Quindi la popolazione è una raccolta di cromosomi.
- Ogni individuo nella popolazione è caratterizzato da una funzione di fitness. Una migliore forma fisica è la soluzione.
- Tra gli individui disponibili nella popolazione, gli individui migliori vengono utilizzati per la riproduzione della prole di prossima generazione.
- La prole prodotta avrà caratteristiche di entrambi i genitori ed è il risultato di una mutazione. Una mutazione è un piccolo cambiamento nella struttura del gene.
Fasi dell'algoritmo genetico
Di seguito sono riportate le diverse fasi dell'algoritmo genetico:
1. Inizializzazione della popolazione (codifica)
- Ogni gene rappresenta un parametro (variabili) nella soluzione. Questa raccolta di parametri che costituisce la soluzione è il cromosoma. La popolazione è una raccolta di cromosomi.
- Ordine dei geni sulle materie cromosomiche.
- Il più delle volte i cromosomi sono rappresentati in binario come 0 e 1, ma ci sono anche altre codifiche possibili.
2. Funzione fitness
- Tra i cromosomi disponibili, dobbiamo selezionare quelli migliori per la riproduzione della prole, quindi ad ogni cromosoma viene assegnato un valore di fitness.
- Il punteggio di fitness aiuta a selezionare le persone che verranno utilizzate per la riproduzione.
3. Selezione
- L'obiettivo principale di questa fase è trovare la regione in cui le possibilità di ottenere la soluzione migliore sono maggiori.
- L'ispirazione per questo proviene dalla sopravvivenza del più adatto.
- Dovrebbe essere un equilibrio tra esplorazione e sfruttamento dello spazio di ricerca.
- GA tenta di spostare il genotipo a una forma fisica superiore nello spazio di ricerca.
- Una distorsione troppo forte nella selezione del fitness può portare a soluzioni non ottimali.
- La selezione di un pregiudizio di fitness insufficiente provoca una ricerca non focalizzata.
- Pertanto viene utilizzata la selezione proporzionale del fitness, nota anche come selezione della ruota della roulette, è un operatore genetico utilizzato negli algoritmi genetici per la selezione di soluzioni potenzialmente utili per la ricombinazione.
4. Riproduzione
La generazione di discendenti avviene in 2 modi:
- Crossover
- Mutazione
a) Crossover
Il crossover è lo stadio più vitale dell'algoritmo genetico. Durante il crossover, viene selezionato un punto casuale mentre si accoppiano una coppia di genitori per generare prole.
Esistono 3 principali tipi di crossover.
- Crossover a punto singolo: un punto sui cromosomi di entrambi i genitori viene raccolto casualmente e designato un "punto di crossover". I bit a destra di quel punto vengono scambiati tra i due cromosomi genitori.
- Crossover a due punti : due punti di crossover vengono scelti casualmente dai cromosomi genitori. I bit tra i due punti vengono scambiati tra gli organismi genitori.
- Crossover uniforme: in un crossover uniforme, in genere, ogni bit viene scelto da entrambi i genitori con uguale probabilità.
La nuova prole viene aggiunta alla popolazione.
b) Mutazione
In alcune nuove prole formate, alcuni dei loro geni possono essere sottoposti a una mutazione con una bassa probabilità casuale. Ciò indica che alcuni bit nel cromosoma dei bit possono essere capovolti. La mutazione si prende cura della diversità della popolazione e ferma la convergenza prematura.
5. Convergenza (quando fermarsi)
Poche regole seguite che indicano quando fermarsi sono le seguenti:
- Quando non vi è alcun miglioramento nella qualità della soluzione dopo aver completato un certo numero di generazioni prefissate.
- Quando viene raggiunta una gamma dura e veloce di generazioni e tempo.
- Fino ad ottenere una soluzione accettabile.
Applicazione dell'algoritmo genetico
In questa sezione, discuteremo alcune delle aree in cui l'algoritmo genetico viene frequentemente applicato.
1. In viaggio e spedizione del percorso
Il problema del commesso viaggiatore è una delle principali applicazioni dell'algoritmo genetico. Ad esempio, quando viene richiesto a un pianificatore di viaggio di pianificare un viaggio, prendeva l'aiuto di un algoritmo genetico che non solo aiuta a ridurre il costo complessivo del viaggio, ma anche a ridurre i tempi.GE viene anche utilizzato per pianificare la consegna di prodotti da un luogo all'altro nel modo più efficiente.
2. Robotica
L'algoritmo genetico è ampiamente utilizzato nel campo della robotica. I robot differiscono l'uno dall'altro per lo scopo per cui sono stati progettati. Ad esempio, pochi sono creati per un'attività di cottura, pochi sono progettati per attività di insegnamento, ecc.
- Selezione di funzionalità importanti nel set di dati indicato.
- Nel metodo tradizionale, le funzionalità importanti nel set di dati vengono selezionate utilizzando il metodo seguente. cioè, guardi l'importanza di quel modello, quindi imposterai un valore di soglia per le caratteristiche e se la caratteristica ha un valore di importanza maggiore di una soglia, viene considerata.
- Ma qui usiamo un metodo chiamato problema a zaino.
- Inizieremo di nuovo con la popolazione di un cromosoma, in cui ogni cromosoma sarà una stringa binaria. 1 indica "inclusione" della funzione nel modello e 0 indica "esclusione" della funzione nel modello.
- La funzione di fitness qui sarà la nostra metrica di precisione della competizione. Più il nostro set di cromosomi è accurato nel prevedere il valore, più si adatta.
- Esistono molte altre applicazioni di algoritmi genetici come analisi del DNA, applicazioni di pianificazione, progettazione ingegneristica.
Conclusione
Nello scenario attuale, GE viene utilizzato in grandi aziende manifatturiere come aeromobili ecc. Al fine di ottimizzare il tempo e l'utilizzo delle risorse. Altri scienziati stanno lavorando per trovare nuovi modi per combinare algoritmi genetici con altre tecniche di ottimizzazione.
Articoli consigliati
Questa è una guida a Cos'è l'algoritmo genetico? Qui discutiamo l'introduzione, le fasi e le applicazioni dell'algoritmo genetico. Puoi anche consultare i nostri altri articoli suggeriti:
- Algoritmi di routing
- Tipi di algoritmi
- Algoritmi di rete neurale
- Algoritmi di data mining
- guida agli esempi dell'algoritmo C ++