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