Newsgroup: it.comp.ia
Titolo: Algoritmo genetico per uscire da labirinto

Sto realizzando un elaborato per un esame che consiste nel produrre un
algoritmo genetico, attraverso il quale degli "esserini" riproducendosi a
due a due imparino, generazione dopo generazione, ad uscire da un labirinto
con ostacoli, trappole, e cose varie...
Ho trovato in rete il link
http://home.online.no/~bergar/mazega.htm
che riporta un esempio di tale applicazione.
Qualcuno sa dove reperire altro materiale? Problemi simili, ricerche in
proposito, idee, suggerimenti, fantasie, ecc.? :-))
Ciao a tutti e grazie!
Kelir


http://home.online.no/~bergar/mazega.htm
L'ho guardato. Un programma assolutamente diseducativo :)
Non ho mai visto un compito affrontato in maniera tanto stupida (e una
concezione cosi' semplicistica dell'evoluzione). Fra l'altro, l'ho
guardato mezz'ora tentare e ritentare un labirinto semplicissimo, poi
mi sono voltato un attimo per guardare fuori dalla finestra, e quando
mi sono rivoltato l'aveva risolto. Secondo me bara :))
Comunque, scherzi a parte, la filosofia del tuo programma e' la
stessa? 
Ciao,
Anders

 stessa?
In linea di massima sì! Pensavo di complicarlo un po', ho un'idea ma non so
fino a che punto sia buona o meno! Provo ad esporla:
Per fare muovere i miei individui posso codificare la probabilità di
muoversi in una direzione rispetto ad un'altra in una stringa binaria... e
fino qui ok, così dovrebbero trovare le "tipologie di spostamento" più
efficaci.
Per complicare pensavo di inserire un doppio codice genetico, uno per fare
quanto spiegato sopra, ed un altro identico per decidere le direzioni in
caso di "trappola imminente".
Le trappole, letali per i miei individui, sono disseminate lungo il
labirinto, ed ogni individuo ha una visibilità limitata, cioè vede una
trappola se ce l'ha dinnanzi (diciamo a una o due unità di distanza).
Analogamente, si potrebbe fare un codice genetico triplo, con un'altra
sezione che regola le probabilità di spostamento in caso di ostacolo
imminente!
Per ora mi è venuto in mente questo, se hai (o chiunque ha) altri
suggerimenti... :-)
Ciao e grazie!
Kelir

 wrote in message 9g305n$ujs$1...@nreadB.inwind.it...


caso di "trappola imminente".
Ottimo, pero' in questo modo ottieni un codice che sa risolvere un
solo labirinto, piu' un codice riutilizzabile per ogni labirinto. Un
po' incoerente, non trovi?
Ciao,
Anders

 non si ottiene una certa stringa, decisa a priori).
Sě, risolvere un solo labirinto non č una gran cosa, in effetti :-)   Cmq
quello che ho in mente dovrebbe risolvere qualsiasi labirinto che sia "del
tipo" di quello di partenza, ovvero con una certa proporzione tra caselle
libere, caselle occupate da blocchi, e trappole.
Per evitare il problema della creazione di un codice genetico
"monolabirinto", si potrebbero esercitare le popolazioni di individui su piů
labirinti generati a random, e poi riprodurre quelli che hanno ottenuto
mediamente il fitness migliore, ovviamente con una funzione probabilistica.
Quindi: Generazione 1   --->   Test su k labirinti   --->   Generazione 2
  --->   Test su k labirinti   --->   Generazione 3   --->   ecc.
Per quanto riguarda la codifica del codice genetico invece sono ancora nella
fase "mumble mumble"... :-))   Sto perfezionando l'idea illustrata nel
messaggio precedente. I prossimi giorni la invio perfezionata!
Ciao e grazie!
Kelir

 :)
Ho visitato il sito e letto la documentazione! E' molto interessante, se ho
ben capito cerchi di migliorare geneticamente delle popolazioni di reti
simili alle neurali. Come elaborato, per semplicità (non per altro), pensavo
di rimanere nell'ambito degli algoritmi genetici "puri", senza sconfinare
nel mondo delle nn... altrimenti poi non ci sto con i tempi!
Cmq sicuramente rivisito il sito ed eventualmente ti chiedo :-)
Ciao e grazie!
Kelir

non impara a risolvere labirinti , ma a 
risolvere UN labirinto 


 


Io cado frequentemente in questo errore e non ho 
ancora ben focalizzato dove sbaglio: se ottengo una popolazione che sa risolvere 
un problema non è detto che la stessa possa risolvere un problema dello stesso 
tipo, ma diverso da quello iniziale. Se poi sottopongo le popolazioni migliori 
alla risoluzione di n problemi dovrei ottenere qualcosa che sappia risolvere 
ogni problema dello stesso tipo. Ma questo come è possibile? Non me lo spiego, e 
pertanto ho difficoltà anche nella scelta della fitness. E' sbagliato il mio 
approccio? Sbaglio le valutazioni?


 


Grazie


Massimiliano


 



 wrote in message
004001c0f667$5ce8d100






Ok per n problemi prefissati. Ma supponiamo di 
voler cercare una generazione che risolva OGNI problema dello stesso tipo o, più 
precisamente un'intera classe di problemi.
Ho l'impressione che qualsiasi 
generazione anche se ottimale non può risolvere tutti i problemi di una stessa 
classe, ma solo quelli simili.
Spero di sbagliarmi. Secondo voi è davvero 
possibile ottenere una generazione in grado di risolvere ogni tipo di labirinto, 
tanto per fare un esempio? Io spero di si, ma questo potrebbe essere possibile 
per tutti i problemi NP-C?


 


E' questo il punto: se gli individui, adattandosi, 
si riproducono e "imparano a risolvere", allora dovrebbero saper risolvere 
l'intera classe del problema iniziale. Eppure c'è qualcosa che non mi 
torna........  :-?


 


Massimiliano



 E' questo il punto: se gli individui, adattandosi, si riproducono e
"imparano a risolvere", allora dovrebbero saper risolvere l'intera classe
del problema iniziale. Eppure c'è qualcosa che non mi torna........  :-?
Scusa il ritardo, ho letto solo oggi il ng! Dunque, vediamo... io credo che
se esercitiamo i nostri individui su n problemi, dato che non possiamo
esercitarli su infiniti problemi, alla fine gli individui dell'ultima
generazione sapranno risolvere bene non un problema qualsiasi appartenente
alla classe (o quanto meno non è detto...) ma un problema che sia "simile"
agli n che abbiamo proposto, dove per simile intendo ovviamente rispetto ai
parametri che abbiamo scelto.
In ogni caso, il bello degli algoritmi genetici, è che se parametrizziamo
bene il problema, cioè scegliamo bene quali parametri mettere nel codice
genetico degli individui, in teoria anche se si presenta un problema un po'
diverso dagli n presentati, dopo un po' di generazioni, i nostri individui
dovrebbero adattarsi anche a questo nuovo problema...
Chiaramente se utlilizziamo il'algoritmo genetico solo per prudurre un solo
codice genetico finale che deve essere definitivo allora questo non è
possibile, se invece simuliamo ad esempio la crescita di una popolazione di
batteri (problema classico in letteratura), allora è possibile...
Questo è quello che penso :-)
Ciao!
Kelir





E' chiaro che un solo codice non potrebbe risolvere 
tutto.


 


Sono d'accordo con te che la scelta dei parametri e 
delle loro eventuali variazioni è fondamentale per la corretta evoluzione dei 
geni. Mi interesserebbe sapere se qualcuno è mai giunto ad una qualche 
conclusione (dimostrabile) che fornisca dei criteri di progettazione. Io non ho 
mai trovato niente in giro. Hai qualche riferimento da indicarmi?


 


Supponiamo di dover progettare un algoritmo 
genetico che non deve assolutamente fallire. Sono belle parole, ma pensi che sia 
possibile questo? E' solo una questione di corretto dimensionamento dei 
parametri? Se così fosse allora potrebbero esistere dei criteri di progettazione 
legati al problema da risolvere, ma che sono più sistematici e formalmente 
corretti rispetto invece all'approccio con progettazione e dimensionamento 
empirico dell'algoritmo........


Massimiliano


 



 Supponiamo di dover progettare un algoritmo genetico che non deve
assolutamente fallire. Sono belle parole, ma pensi che sia possibile questo?
E' solo una questione di corretto dimensionamento dei parametri? > Se così
fosse allora potrebbero esistere dei criteri di progettazione legati al
problema da risolvere, ma che sono più sistematici e formalmente corretti
rispetto invece all'approccio con progettazione e dimensionamento empirico
dell'algoritmo........
In teoria forse... non saprei, bisognerebbe studiare il tutto a livello
teorico, e dimostrare ogni punto :-))   Cmq sarebbe interessante!
Ciao!
Kelir