Realizzare un programma che impari, grazie ad algoritmi evolutivi, a completare un percorso evitando ostacoli, e successivamente ottimizzi la distanza da percorrere.
Viene generato un grid 50x50 con dei muri ogni 10 blocchi, il programma deve partire dal blocco in alto a sinistra e raggiungere la linea di arrivo.
Imposto un algoritmo genetico (cosa sono):
Creo una generazione di 5000 individui random e seleziono il migliore.
A partire da quest'ultimo creo una nuova generazione in cui ogni individuo conserva dal 10% al 90% delle sue mosse,
per poi generare casualmente quelle successive.
Ogni volta che un individuo va contro un ostacolo o prova ad uscire dal grid muore, inoltre gli individui successivi si ricordano del luogo
in cui è morto e della mossa scelta da lui per non ripetere gli stessi errori.
Ripeto il procedimento finché non viene raggiunto l'obiettivo, oppure viene raggiunta la sessantesima generazione.
Il percorso viene completato, ma la versione web di questo programma é eccessivamente lenta, per questo per la seconda parte del progetto, l'ottimizzazione del percorso, ho usato il C++.
L'algoritmo é simile alla versione web, ma dopo il completamento del percorso il programma continua a cercare di ottimizzarlo diminuendo la sua lunghezza. Inoltre, il numero di individui per generazione é 15000 e la ricerca continua fino alla trecentesima generazione.
🌙 Modalità notte