algoritmi genetici e giochi… peg solitaire attività formativa 2005/2006 docente: roberto...
TRANSCRIPT
Algoritmi genetici e giochi… PEG SOLITAIRE
Attività formativa2005/2006
Docente: Roberto Tauraso Studenti: Vincenzo Ferrazzano
Luca Burini
UNIVERSITA' DEGLI STUDI DI ROMA “TOR VERGATA”
Creare nuove soluzioni migliorando le precedenti
Informatica Biologia
Algoritmi di ottimizzazione
evoluzione
selezione naturale
riproduzione sessuataRicerca di soluzioni
PROBLEMA
Vincoli
Parametri
Variabili
Soluzione
ammissibile
Strategia risolutiva
FITNESS
Selezione
Riproduzione
EvoluzioneSoluzione
OTTIMA
1697
Pricipessa de Soubise
Scopo del gioco
Come si gioca
Apparentemente facile…
Considerazioni sulla soluzione ottima
Pedine sul ROSSO
11
Pedine sul BLU
11
Pedine sul VERDE
10
0 11V Rosso
0 10V Verde 0 11V Blu
Definizione mosse
Mossa v
Mossa r
Mossa b
31
31
31
11
10
11
V Rosso R V B
V Verde R V B
V Blu R V B
Modulo 2…
31
31
31
mod 2 11 mod 2
mod 2 10 mod 2
mod 2 11 mod 2
V Rosso R V B
V Verde R V B
V Blu R V B
31
31
31
mod 2 0mod 2
mod 2 1mod 2
mod 2 0mod 2
V Rosso
V Verde
V Blu
31
31
31
mod 2 11 31 mod 2
mod 2 10 31 mod 2
mod 2 11 31 mod 2
V Rosso
V Verde
V Blu
31
31
31
0
1
0
V Rosso
V Verde
V Blu
90°
Posizioni finali ammissibili
circa
577 116 156 815 309 849 672
partite possibili
5,77 * 105,77 * 102020
diverse alternative
Supponiamo di effettuare
una partita ogni microsecondo
5,77 * 10 14 secondi9,61 * 10 12 minuti1,63 *10 11 ore6,68 * 10 9 giorni
1,83 * 10 7 anni
Ricondurre il problema in forma trattabile da un GA1 2 1
3 4 3
5 6 5
6 7 6
5 6 5
3 4 3
3 1
4 2
1 3
2 4
1 2 1
1 3 3 1
Numeri uniformemente
distribuiti in {0,99}
StrategiaStrategia
Come scegliere quali pedine muovere? B C
D
E
A
Se B+C-A > D+E-AB+C-A < D+E-A
FITNESS: Numero di pedine rimaste sulla scacchiera
StrategStrategiaia
POPOLAZIONE: 15 individui con genoma casuale
Come funziona il nostro algoritmo…Come funziona il nostro algoritmo…
…
Ordinamento in base al FITNESS
Fit = 2
Fit = 5
Fit = 12
…
Fit = 12
Fit = 2
10 82 10
63 25 63
46 88 46
88 34 88
46 88 46
63 25 63
63 10
25 82
10 63
82 25
10 82 10
10 63 63 10
22 27 22
9 97 9
16 76 16
76 88 76
16 76 16
9 97 9
9 22
97 27
22 9
27 97
22 27 22
22 9 9 22
DNA
10 82 10
63 97 63
16 88 16
88 34 88
16 88 16
63 97 63
63 10
97 82
10 63
82 97
10 82 10
10 63 63 10
Nuovo individuo
Procedimento ripetuto 30 volte
Rimescolamento dei geni
(selezione naturale)
Successive iterazioni…
Strategia dettata dal DNA
Fino a che non rimangono 12 pedine sulla scacchiera
RISULTATI SPERIMENTALIRISULTATI SPERIMENTALI
k kp kt k
t
40 0,445722 0,656537 s 0,718544 s
45 0,462339 0,719447 s 0,886434 s
50 0,474158 0,852206 s 1,16918 s
60 0,498598 1,01548 s 1,60329 s
65 0,502652 1,06209 s 1,7593 s
70 0,505976 1,13447 s 2,0148 s
Soluzioni trovate
Partite giocatekp
1
1kn
k kik
i
t tn
2
1
1kn
k k kt ik
i
t tn
Tempo medio di esecuzione
-1,5
-1-0,5
00,5
1
1,52
2,53
3,5
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75
k
Tempo medio
Prestazioni
00,10,20,30,40,50,60,70,80,9
11,11,2
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75
k
Probabilità
Tempo medio
CONCLUSIONICONCLUSIONI
5,77 * 105,77 * 1020 20
partite possibilipartite possibili
18 miliardi di 18 miliardi di annianni
algoritmo
genetico
Qualche
secondo!!Sviluppi futuri
Elaborare delle strategie Variare parametri differentidi risoluzione ben codificate