Newsgroup: it.comp.ia
Titolo: GA e matematica

Salve a tutti,
mi sto avvicinando da poco all'IA, quindi chiedo scusa se la domanda 
sara' (forse) banale.
riguardo ai GA non ho capito se la soluzione finale di un problema e' 
sempre unica.
ho letto che la ricerca di una soluzione puo' concludersi quando, ad 
esempio, si rimane finalmente al di sotto di una certa soglia fissata a 
priori. (tipo: mi basta vincere questa partita di scacchi con 7 mosse, 
nonostante sia possibile anche con meno).
pero' non ho capito se e' possibile arrivare alla soluzione migliore in 
assoluto.
voglio dire: poniamo il caso di avere un quadrato in cui vi sono un 
certo numero di cerchi di varie dimensioni. e' possibile usare un GA per 
trovare *IL* cerchio piu' grande possibile che non si sovrapponga agli 
altri cerchi ? oppure posso trovarne uno ma *senza* la certezza che sia 
veramente il piu' grande possibile?
nel caso degli scacchi e' chiaro che si puo' predire il numero minimo di 
mosse per vincere utilizzando un algoritmo non genetico, perche' il 
numero di mosse, per quanto alto, e' finito. invee i GA "preparano" una 
popolazione inizialmente random che andra' poi migliorata, per cui non 
possiamo dire che non esiste una soluzione migliore di quella trovata 
dal GA. o sbaglio ?
in matematica un teorema e' vero solo se dimostrato. un GA invece si 
accontenta di verificare che il teorema e' valido fino a un "certo 
punto". e' cosi'?
nn so se e' chiaro...
darko
-- 
"A celestial voyage
To feel the bliss of liquid
Healing nectar inside"
http://www.autistici.org/darko

 dal GA. o sbaglio ?
Esatto: a parer mio, non sbagli.
Spero di averti chiarito un po di idee
Saluti

 ottimo però non ne hai la certezza.
tnx x la risposta!
pero' non capisco se, partendo da una popolazione di soluzioni che *non* 
comprende la soluzione ottimale, si puo' arrivare sempre ad una 
soluzione quanto meno molto vicina a quella ottimale.
intendo dire: al tendere verso infinito delle mutazioni, si ha un 
avvicinamento verso la soluzione ottimale? oppure si raggiunge la 
certezza di avere la soluzione migliore *tra* quelle della popolazione 
iniziale e quindi magari molto distante dalla soluzione ottimale?


 avvicinamento verso la soluzione ottimale? 
Certo, ci si avvicina sempre di piů alla soluzione ottima (al limite l'algoritmo si potrebbe 
  fermare in un minimo locale) e il perchč lo deduci dalla *funzione di fitness*: questa 
funzione permette di generare insiemi di soluzioni sempre migliori.
Le funzioni di fitness sono importantissime nei GA, con una ricerca in rete troverai 
sicuramente qualcosa di utile.
Saluti

 rete troverai sicuramente qualcosa di utile.
ottimo. grazie mille.
byez


 soluzione quanto meno molto vicina a quella ottimale.
In teoria al tendere ad infinito delle iterazioni gli algoritmi genetici 
(se implementati in un certo modo e se il numero di soluzioni possibili 
è finito) convergono alla soluzione ottimale.
In pratica però potrebbe volerci un tempo enorme.
Il fatto che un algoritmo genetico produca una soluzione "accettabile" 
in un tempo ragionevole dipende dai dettagli implementativi, dalla 
potenza di calcolo a disposizione ma soprattutto dal particolare dominio 
di applicazione. Infatti gli algoritmi genetici sono stati usati su 
praticamente tutti i domini pensabili, su alcuni hanno dato buoni 
risultati mentre su altri sono andati molto male.
Gli algoritmi genetici sono tecniche euristiche che richiedono alcune 
assunzioni deboli (ovvero non stringenti) sul dominio.
Se il dominio approssimativamente rispetta tali assunzioni gli algortmi 
genetici in genere funzionano, se non le rispetta, nel caso peggiore, un 
algoritmo genetico ha le stesse prestazioni di una ricerca casuale.