[Lungo] Ancora sui tririduttori di 16 doppie
Nino
ha posto l'accento ed invitato ad un esame più generale e
profondo sul problema postato il 25-03 alle ore 20:44 del
Gino, la Gina e le monetine.
Livio dice giustamente che "La soluzione ottimale dovrebbe
approdare ad un tririduttore puro da 16 doppie".
Ma può esistere il riduttore perfetto n-3 di 16 doppie?
La risposta è no. Vediamo perchè.
Le colonne totali sono 2^16 = 65536.
Rispetto a qualsiasi colonna, le colonne "utili" sono:
1 che realizza 16 punti, 16 che garantiscono il 15, 120 per
il 14 e 560 che danno il 13. Totale = 697
Il riduttore n-3 teorico di 16 doppie dovrebbe quindi essere
di 65536/697 = 94,02582... colonne, e la presenza dei decimali
(oltre a semplici considerazioni sulla massima rappresentatività,
cioè sulla differenza dei segni nelle colonne) indica chiaramente
che qualsiasi riduttore non potrà essere perfetto.
Questo non esclude ovviamente che si possano costruire sistemi
"primato" con meno delle 256 colonne (8 bit) previsti dal problema,
anche se dubito si possano raggiungere aggregati esprimibili con
7 bit.
Ma limitiamoci ad utilizzare tririduttori da 256 colonne, come
quello 7/9 + 6/7 = 13/16 da me schematizzato in precedenza.
Livio dice che occorre fare una scelta ottimale per determinare
le 256 word che massimizzano la vincita media.
E propone un programma di ricerca operativa (che ovviamente io
non so fare) per poterle scovare.
Io mi limito quindi ad osservare che i 256 aggregati di 256
colonne che costituiscono tririduttori e che sono stati ricavati
mediante la medesima chiave, posseggono le stesse peculiarità
e presentano identica garanzia di vincita media.
Di seguito schematizzo i due esempi descritti nei post precedenti.
A B C D E F G H
1 X X 1 X 1 X 1 X 1 1 X 1 X 1 X
1 X X 1 1 X 1 X 1 X X 1 1 X 1 X
1 X 1 X X 1 1 X 1 X 1 X X 1 1 X
1 X 1 X 1 X X 1 1 X 1 X 1 X X 1
a b c d
1 X 1 X
1 X X 1
A' B' C' D' E' F' G' H'
1 X X 1 1 X 1 X
1 X 1 X X 1 1 X
1 X 1 X 1 X X 1
r1 r2 r3 r4
1 X X 1 1 X 1 X
1 X 1 X X 1 1 X
1 X 1 X 1 X X 1
TRIRIDOTTO 9D+7D = colonne 16*16 = 256 vincita media 13,46875
A B C D A B C D E F G H E F G H
a b c d b a d c a b c d b a d c
A' A' A' A' B' B' B' B' A' A' A' A' B' B' B' B'
----------------------- ------------------------
A B C D A B C D
r1 r2 r3 r4 r1 r2 r3 r4
A B C D A B C D E F G H E F G H
a b c d b a d c a b c d b a d c
A' A' A' A' B' B' B' B' A' A' A' A' B' B' B' B'
----------------------- ------------------------
E F G H E F G H
r1 r2 r3 r4 r1 r2 r3 r4
Con semplici inversioni (A'B' con C'D' - E'F' - G'H') e
permutazioni (A B C D e F G H I) dai 4 presentati
si ottengono i 256 tririduttori.
TRIRIDOTTO 13D+3D = colonne 128*2 = 256 vincita media 13,48438
A B C D A B C D E F G H E F G H
a b c d b a d c a b c d b a d c
----------------------- ------------------------
A B C D A B C D E F G H E F G H
a b c d b a d c a b c d b a d c
1 1 1 1 X X X X 1 1 1 1 X X X X
----------------------- ------------------------
r1 r1
A B C D A B C D E F G H E F G H
a b c d b a d c a b c d b a d c
----------------------- ------------------------
E F G H E F G H A B C D A B C D
a b c d b a d c a b c d b a d c
1 1 1 1 X X X X 1 1 1 1 X X X X
----------------------- ------------------------
r1 r1
Analogamente, permutando A B C D e F G H I
e sostituendo r1 con r2 - r3 - r4 si ricavano i
256 riduttori diversi, che nel loro insieme riproducono
l'integrale delle 16 doppie.
Ciao, Nino
Livio Zucca
> Scusate se inizio un nuovo thread, ma l'intervento di Livio
> ha posto l'accento ed invitato ad un esame più generale e
> profondo sul problema postato il 25-03 alle ore 20:44 del
> Gino, la Gina e le monetine.
>
> Livio dice giustamente che "La soluzione ottimale dovrebbe
> approdare ad un tririduttore puro da 16 doppie".
> Ma può esistere il riduttore perfetto n-3 di 16 doppie?
> La risposta è no. Vediamo perchè.
Devo premettere, caso mai non fosse chiaro, che non so nulla
sui sistemi ridotti o quel po' che so lo sto apprendendo ora.
Pero' mi ha colpito l'analogia con vari problemi di comunicazione
e trasmissione dati, con relative "compressioni" di cui mi e' capitato
di occuparmi. In fondo la comunicazione da Gino a Gina non e'
che una "trasmissione dati compressa" dove si accetta di perdere
"poco" in informazione guadagnando "molto" in banda.
> Le colonne totali sono 2^16 = 65536.
> Rispetto a qualsiasi colonna, le colonne "utili" sono:
> 1 che realizza 16 punti, 16 che garantiscono il 15, 120 per
> il 14 e 560 che danno il 13. Totale = 697
> Il riduttore n-3 teorico di 16 doppie dovrebbe quindi essere
> di 65536/697 = 94,02582... colonne, e la presenza dei decimali
> (oltre a semplici considerazioni sulla massima rappresentatività,
> cioè sulla differenza dei segni nelle colonne) indica chiaramente
> che qualsiasi riduttore non potrà essere perfetto.
Qui mi sembra di capire che definisci "perfetto" quel riduttore
che avesse bisogno esattamente di 256 colonne. Bastandone 94,02...
il sistema sara' quindi "ridondante". I 256 insiemi di word che non
si discostano di piu' di 3 bit dai loro "pivot" sono insiemi che
parzialmente si intersecano.
> [...]
> TRIRIDOTTO 9D+7D = colonne 16*16 = 256 vincita media 13,46875
> [...]
> TRIRIDOTTO 13D+3D = colonne 128*2 = 256 vincita media 13,48438
> [...]
E' dunque evidente che questi due sistemi derivati dalla combinazione
di due (perfetti?) sono entrambi "ridondanti". Essi danno una vincita
media leggermente diversa. Sorge dunque spontanea la domanda:
esiste un altro insieme di riduttori tale da fornire una vincita media
ancora superiore? Mi sembra probabile, anche se mi rendo conto che
per dimostrarne l'esistenza occorrera'... scovarli. :o))
Ciao!!! ((^__^))'
Livio
Giorgio Vecchi
> > [...]
> > TRIRIDOTTO 9D+7D = colonne 16*16 = 256 vincita media 13,46875
> > [...]
> > TRIRIDOTTO 13D+3D = colonne 128*2 = 256 vincita media 13,48438
> > [...]
>
> E' dunque evidente che questi due sistemi derivati dalla combinazione
> di due (perfetti?) sono entrambi "ridondanti". Essi danno una vincita
> media leggermente diversa. Sorge dunque spontanea la domanda:
> esiste un altro insieme di riduttori tale da fornire una vincita media
> ancora superiore? Mi sembra probabile, anche se mi rendo conto che
> per dimostrarne l'esistenza occorrera'... scovarli. :o))
>
E' proprio questo il punto. Il sistema ridotto ideale dovrebbe essere quello
che garantisce le seguenti "prestazioni":
1 volta su 256 ottengo 16
16 volte su 256 ottengo 15
120 volte su 256 ottengo 14
le rimanenti volte (119) su 256 ottengo 13.
Questo garantirebbe una vincita media pari a 13,60546875, che è il massimo
possibile. Si tratta appunto di trovarlo! :-)
Ciao :-)
Giorgio
Livio Zucca
> ... Il sistema ridotto ideale dovrebbe essere quello
> che garantisce le seguenti "prestazioni":
>
> 1 volta su 256 ottengo 16
> 16 volte su 256 ottengo 15
> 120 volte su 256 ottengo 14
> le rimanenti volte (119) su 256 ottengo 13.
>
> Questo garantirebbe una vincita media pari a 13,60546875, che è
> il massimo possibile. Si tratta appunto di trovarlo! :-)
Si tratta di muoversi su una collina n-dimensionale con n=256.
Le colline sono discrete, a gradoni, piramidi azteche.
Le soluzioni (vette piu' alte) sono probabilmente tante. (questo aiuta)
I massimi relativi ancor di piu'. Occorre poterne uscire facilmente,
anche se potremmo accontentarci di qualcuno di loro. (se solo
15 volte su 256 ottengo 15, la vincita media sara' 13.59).
Una Darwin Machine? :o))
Ciao!!! ((^__^))'
Livio
Livio Zucca
> 16 volte su 256 ottengo 15
> 120 volte su 256 ottengo 14
> le rimanenti volte (119) su 256 ottengo 13.
>
> Questo garantirebbe una vincita media pari a 13,60546875, che è il
> massimo possibile. Si tratta appunto di trovarlo! :-)
Puo' essere anche, come spesso succede ultimamente, che siano state
sviluppate delle teorie sotto il cappello di "compressione dati con
perdita di informazione", teorie che non conosco. Mi dicono che la
JPEG e' una compressione CON perdita, ad es.
Ciao!!! ((^__^))'
Livio
Nino
"Livio Zucca" ha scritto:
> "Nino" <a...@libero.it> ha scritto:
>
> Qui mi sembra di capire che definisci "perfetto" quel riduttore
> che avesse bisogno esattamente di 256 colonne.
No. Perfetto è il riduttore che è costituito esattamente da un numero
di colonne pari al rapporto fra le colonne dell'integrale e la somma
di tutte le vincite utili.
Ad es. è perfetto il sistema n-1 di 7 doppie: col.16, in quanto
garantisce 6 su 7 e le colonne utili son 8 ( 1 con 7 punti e 7 con 6);
Quindi: 2^7/8 = 16 come appunto sono le colonne del ridotto,
che non sono ridondanti, e ciascuna serve per garantire una sola
vincita.
Ovviamente, i sistemi perfetti sono pochissimi (2 doppie, 4 triple,
7 doppie, 15 doppie tutti n-1) e per gli altri è giocoforza
accontentarsi di avere ridondanze.
> I 256 insiemi di word che non
> si discostano di piu' di 3 bit dai loro "pivot" sono insiemi che
> parzialmente si intersecano.
>
> > [...]
> > TRIRIDOTTO 9D+7D = colonne 16*16 = 256 vincita media 13,46875
> > [...]
> > TRIRIDOTTO 13D+3D = colonne 128*2 = 256 vincita media 13,48438
> > [...]
>
> E' dunque evidente che questi due sistemi derivati dalla combinazione
> di due (perfetti?)
Come ho detto prima, il 9D e il 13D non sono perfetti (nè possono
esistere sistemi perfetti n-2 di 9D e n-3 di 13D); perfetti sono invece
il 7D e il 3D n-1.
> sono entrambi "ridondanti". Essi danno una vincita
> media leggermente diversa. Sorge dunque spontanea la domanda:
> esiste un altro insieme di riduttori tale da fornire una vincita media
> ancora superiore? Mi sembra probabile, anche se mi rendo conto che
> per dimostrarne l'esistenza occorrera'... scovarli. :o))
>
La sistemistica classica, studiata a tavolino con solo foglio e matita
(come ho sempre fatto io), ha dovuto purtroppo ultimamente lasciare
spazio ai miglioramenti (di tipo colonnare, ma non sempre di eleganza
strutturale) ottenuti con sofisticati programmi computerizzati.
Ma a mio avviso, il piacere di un primato ottenuto nei due modi
non dà la stessa intensità.
Ciao a tutti, Nino
Nino
"Giorgio Vecchi" ha scritto nel messaggio
>
> E' proprio questo il punto. Il sistema ridotto ideale dovrebbe essere
quello
> che garantisce le seguenti "prestazioni":
>
> 1 volta su 256 ottengo 16
> 16 volte su 256 ottengo 15
> 120 volte su 256 ottengo 14
> le rimanenti volte (119) su 256 ottengo 13.
>
> Questo garantirebbe una vincita media pari a 13,60546875, che è il massimo
> possibile. Si tratta appunto di trovarlo! :-)
>
Esatto, ma sono certo che non esiste.
Forse si potrà avvicinarsi...
Ciao, Nino
Livio Zucca
(bruteforce) che ho fatto questa notte? Il risultato mi ha sorpreso.
Dunque, ho costruito un sistema ridotto di 256 word con il seguente
metodo: ho tirato a sorte con una moneta ciascun bit di ciascuna
delle 256 word. (!)
Poi sono andato a calcolare la vincita media. Risultato: 13.41... (!)
Ho ripetuto l'esperimento ottenendo sempre risultati compresi
tra 13.40 e 13.42, assai vicini ai sistemi ridotti "pensati".
Ciao!!! ((^__^))'
Livio
Giorgio Vecchi
Ci ho provato anch'io. Trovo però risultati un po' diversi: circa 13.23 di
media. Non credo che la differenza tra i miei e i tuoi risultati sia
imputabile alla bontà del generatore casuale. Probabilmente c'è qualche
errore (mio e/o tuo) nei conteggi. Io, per ogni word possibile, calcolo il
numero dei bit diversi rispetto a ogni word del sistema ridotto. Prendo il
valore minore e in base a questo stabilisco il punteggio.
Ciao :-)
Giorgio
Silvio Sergio
> Poi sono andato a calcolare la vincita media. Risultato: 13.41... (!)
>
> Ho ripetuto l'esperimento ottenendo sempre risultati compresi
> tra 13.40 e 13.42, assai vicini ai sistemi ridotti "pensati".
confermo: 13.42 con scarto medio molto basso
--
Ciao, Silv:o)
Livio Zucca
Mi sembra che il metodo di calcolo sia lo stesso (nelle intenzioni :o))
Per ogni valore 0..65535, considerati equiprobabili, cerco quel
pivot tra i 256 che l'avrebbe rappresentato al meglio. Infatti quello
avrei usato in fase di codifica...
Mi sembra di aver detto la stessa cosa. 'Sta notte verifichero' i conti.
Anche 13.23 non sarebbe cmq da buttare via, visto che il primo
sistema pensato dava un 13 secco. Il Caos batte l'Ordine piu' spesso
di quanto non immaginiamo! :o)))
Ciao!!! ((^__^))'
Livio
Livio Zucca
Ho anche implementato una Darwin Machine, pero' impiego un sacco
di tempo per calcolare la vincita media. Cosi' nella notte il sistema
si e' evoluto poco ed e' arrivato a 13.45 in poche decine di generazioni.
Se a qualcuno venisse in mente un metodo rapido di calcolo...
Io, per ogni word possibile, per ogni pivot, per ogni bit, faccio
268435456 loop ogni volta solo per determinare la Vmed.
Ciao!!! ((^__^))'
Livio
Giorgio Vecchi
> "Silvio Sergio" <silvio...@libero.it> ha scritto:
> > Livio Zucca dice
> >> Poi sono andato a calcolare la vincita media. Risultato: 13.41... (!)
> >>
> >> Ho ripetuto l'esperimento ottenendo sempre risultati compresi
> >> tra 13.40 e 13.42, assai vicini ai sistemi ridotti "pensati".
> >
> > confermo: 13.42 con scarto medio molto basso
Mi adeguo, mi adeguo! Anche a me viene ~13.42. Un bughettino stupido:
generavo "word" di 17 bit! E il bit basso era sempre 0 ! Giocavo con mezzo
bit in meno! :-)
> Ho anche implementato una Darwin Machine, pero' impiego un sacco
> di tempo per calcolare la vincita media. Cosi' nella notte il sistema
> si e' evoluto poco ed e' arrivato a 13.45 in poche decine di generazioni.
>
> Se a qualcuno venisse in mente un metodo rapido di calcolo...
> Io, per ogni word possibile, per ogni pivot, per ogni bit, faccio
> 268435456 loop ogni volta solo per determinare la Vmed.
>
Non so se intendi questo: per confrontare tra loro 2 word puoi usare
l'operatore Xor e poi contare i bit 1 del risultato.
Ho buttato giů un programma per generare ridotti. Per ora č arrivato a un
po' piů di 13.48 di vincita media. Vi allego le 256 word, se qualcuno le
volesse controllare. :-) Alcune combinazioni vincono solo 12 punti.
0000000000000000
0000000011110101
0000000111101010
0000001011011111
0000001111010100
0000010011001001
0000010110111110
0000011010110011
0000011110101000
0000100010011101
0000100110010010
0000101010000111
0000101101111100
0000110001110001
0000110101100110
0000111001011011
0000111101010000
0001000001000101
0001000100111010
0001001000101111
0001001100100100
0001010000011001
0001010100001110
0001011000000011
0001011011111000
0001011111101101
0001100011100010
0001100111010111
0001101011001100
0001101111000001
0001110010110110
0001110110101011
0001111010100000
0001111110010101
0010000010001010
0010000101111111
0010001001110100
0010001101101001
0010010001011110
0010010101010011
0010011001001000
0010011100111101
0010100000110010
0010100100100111
0010101000011100
0010101100010001
0010110000000110
0010110011111011
0010110111110000
0010111011100101
0010111111011010
0011000011001111
0011000111000100
0011001010111001
0011001110101110
0011010010100011
0011010110011000
0011011010001101
0011011110000010
0011100001110111
0011100101101100
0011101001100001
0011101101010110
0011110001001011
0011110101000000
0011111000110101
0011111100101010
0100000000011111
0100000100010100
0100001000001001
0100001100000010
0100001111110111
0100010011101100
0100010111100001
0100011011010110
0100011111001011
0100100011000000
0100100110110101
0100101010101010
0100101110011111
0100110010010100
0100110110001001
0100111001111110
0100111101110011
0101000001101000
0101000101011101
0101001001010010
0101001101000111
0101010000111100
0101010100110001
0101011000100110
0101011100011011
0101100000010000
0101100100000101
0101100111111010
0101101011101111
0101101111100100
0101110011011001
0101110111001110
0101111011000011
0101111110111000
0110000010101101
0110000110100010
0110001010010111
0110001110001100
0110010010000001
0110010101110110
0110011001101011
0110011101100000
0110100001010101
0110100101001010
0110101000111111
0110101100110100
0110110000101001
0110110100011110
0110111000010011
0110111100001000
0110111111111101
0111000011110010
0111000111100111
0111001011011100
0111001111010001
0111010011000110
0111010110111011
0111011010110000
0111011110100101
0111100010011010
0111100110001111
0111101010000100
0111101101111001
0111110001101110
0111110101100011
0111111001011000
0111111101001101
1000000001000011
1000000100111001
1000001000110000
1000001100100111
1000010000011100
1000010100010010
1000011000001010
1000011100000001
1000011111110110
1000100011101011
1000100111100000
1000101011010101
1000101111001010
1000110010111111
1000110110110100
1000111010101001
1000111110011110
1001000010010011
1001000110001000
1001001001111101
1001001101110010
1001010001100111
1001010101011111
1001011001010100
1001011101101000
1001100001011110
1001100101011001
1001101001010011
1001101101001111
1001110001001000
1001110100111101
1001111000110010
1001111101000010
1010000000110111
1010000100101100
1010001000101011
1010001101000000
1010010000111010
1010010101000101
1010011001000110
1010011101001011
1010100001000100
1010100101010010
1010101001001001
1010101100111110
1010110001010111
1010110101001110
1010111001100000
1010111101011101
1011000001011000
1011000101100001
1011001001101110
1011001110000001
1011010010000000
1011010101111100
1011011001110001
1011011110010100
1011100010001001
1011100110000010
1011101010001110
1011101110010111
1011110010010101
1011110110001100
1011111010000011
1011111101111011
1100000001110001
1100000101100110
1100001001011011
1100001101010101
1100010001001101
1100010101001010
1100011000111111
1100011100110100
1100100000101100
1100100100100001
1100101000010110
1100101100001011
1100110000000000
1100110011110101
1100110111101111
1100111011100110
1100111111101000
1101000011011111
1101000111010100
1101001011001001
1101001110111110
1101010010110111
1101010110101100
1101011010100001
1101011110011101
1101100010011100
1101100110010001
1101101010011011
1101101110100010
1101110010101010
1101110111000000
1101111011011110
1101111111110001
1110000011101000
1110000111011101
1110001011010010
1110001111000111
1110010010111100
1110010110110001
1110011010100111
1110011110101010
1110100010011111
1110100110010100
1110101010010001
1110101110011010
1110110010010010
1110110110000111
1110111010001100
1110111110110110
1111000010101011
1111000110111000
1111001010110101
1111001111001010
1111010011010001
1111011000011110
1111101000101000
1111110100100100
Ciao :-)
Giorgio
Livio Zucca
> po' piů di 13.48 di vincita media. Vi allego le 256 word, se qualcuno le
> volesse controllare. :-) Alcune combinazioni vincono solo 12 punti.
Controllate! :o)
Le ho anche messe nella Darwin Machine che in un paio d'ore :o)
ha portato la vincita media da 13.481+ a 13.487+. Se non sbaglio e' il record!
Dovete per ora credermi sulla parola perche' ho azzerato il prog. prima di
salvare il sistema. :o( Ci riprovero' cercando di velocizzare il calcolo.
Ciao!!! ((^__^))'
Livio
iant
>Qualcuno vuole consolarmi (matematicamente) sull'esperimento
>(bruteforce) che ho fatto questa notte? Il risultato mi ha sorpreso.
Tranquillo Livio, e benvenuto nel meraviglioso mondo dei risultati
controintuitivi della sistemistica! ;-))
Non so se la consolazione (non ortodossamente) matematica che sto
per darti puo' essere soddisfacente, ma ci provo.
Se tu pensi che tra le superfici tridimensionali possibili ci sono
per esempio i gusci delle lumache e le piu' fantasiose conchiglie
marine, puoi dedurre che in generale la determinazione di un ottimo
assoluto su una superficie tridimensionale puo' essere un compito
molto oneroso. Immagina per le superfici 256-dimensionali!
Il fatto e' che le superfici 256-dimensionali, piu' che colline o
piramidi azteche, possono essere delle orribili (o meravigliose)
iperconchiglie con cunicoli dei quali molto difficilmente riuscirai
ad intravvedere l'ingresso, e se l'ottimo e' proprio li' in fondo
non lo troverai cosi' facilmente. Quindi e' possibile che
guadagnare anche un piccolo decimale nel valore della funzione
possa richiedere uno sforzo enorme.
Questo per spiegare la difficolta' di trovare la soluzione ottima.
>Dunque, ho costruito un sistema ridotto di 256 word con il seguente
>metodo: ho tirato a sorte con una moneta ciascun bit di ciascuna
>delle 256 word. (!)
>
>Poi sono andato a calcolare la vincita media. Risultato: 13.41... (!)
>
>Ho ripetuto l'esperimento ottenendo sempre risultati compresi
>tra 13.40 e 13.42, assai vicini ai sistemi ridotti "pensati".
Invece per spiegare il "piattume" della media puoi pensare che un
sistema triridotto puo' essere diverso di pochissimo da un sistema
composto dallo stesso numero di colonne ma che non e' un triridotto.
Se hai costruito il ridotto in modo casuale, e' estremamente
improbabile che tu abbia costruito un triridotto, cioe' un sistema
che dia **garanzia** di fare 13/16. Quello della garanzia di un
risultato e' un caposaldo irremovibile della sistemistica!!!
E' invece quasi certo che tu abbia ottenuto un sistema a garanzia
11/16, e hai ottime probabilita' di aver ottenuto un 12/16.
(Lo dico anche sulla base di simulazioni che ho fatto io.) A me
viene che ridotti di 256 colonne generati a caso lasciano "scoperte"
tra le 3000 e le 5000 colonne del sistema integrale, nel senso che
su quelle non si fara' 13/16 ma un po' meno, generalmente 11/16.
Quindi tenuto conto che nel complesso le colonne sono 65536, 5000
di queste che fanno 11 anziche' 13 spostano poco la media.
La verita' e' che la garanzia del 13/16 puo' addirittura andare in
controtendenza rispetto al valore medio di sistemi con garanzia
inferiore! Cioe' e' possibile avere sistemi a garanzia di 12/16 che
hanno rendita media *superiore* a sistemi con garanzia 13/16.
Dal mio punto di vista, potendo scegliere, io preferirei sempre
un sistema con garanzia minima superiore e garanzia media inferiore
piuttosto che il viceversa. Ma questa e' questione di carattere. ;-)
A presto,
iant
Nino
"Livio Zucca" dice:
Disordine e aumento dell'entropia...
Con il massimo ordine (256 colonne costituite dall'accorpamento
di 8 doppie integrali) si realizza la minima vincita media, che
è pari a 12 (0,39% per l'8 e il 16, 3,125% per il 9 e il 15,
10,937% per il 10 e il 14, 21,875% per l'11 e il 13 e 27,344%
per il 12).
Sarebbe sorprendente se scegliendo colonne a caso si realizzassero
composizioni ordinate.... e quindi a bassa vincita media.
Però, altrettanto sorprendente, sarebbe ritrovarsi bell'e pronto
e senza fatica un ridotto a garanzia di vincita programmata e
a livello di primato.
Mi ha incuriosito il programma per generare ridotti fatto da Giorgio
(però, le 256 word presentate configurano un probabilistico, essendo
n-4).
Mi scuso quindi se approfitto delle vostre capacità informatiche
e vi chiedo se qualcuno volesse gentilmente controllare per la
vincita media le 256 word che ho schematizzato di seguito ( a mano
è un lavoro improbo e dal risultato incerto).
0 1 1 0 1 0 1 0
0 1 1 0 0 1 0 1
0 1 0 1 1 0 0 1
0 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1
0 0 1 1 1 1 0 0
------------------------- + ---------------------------
0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0
0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1
0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1
0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
---------- ---------- ---------- ----------
0 1 1 0 1 0 1 0
0 1 1 0 0 1 0 1
0 1 0 1 1 0 0 1
0 1 0 1 0 1 1 0
colonne : 4*4*2 + 4*4*2 + 4*4*2 + 4*4*2
1 0 1 0 1 0 1 0
1 0 1 0 0 1 0 1
1 0 0 1 1 0 0 1
1 0 0 1 0 1 1 0
1 1 0 0 1 1 0 0
1 1 0 0 0 0 1 1
------------------------- + ---------------------------
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1
1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1
1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1
---------- ---------- ---------- ----------
1 0 0 1 0 1 0 1
0 1 1 0 0 1 0 1
0 1 0 1 1 0 0 1
0 1 0 1 0 1 1 0
colonne : 4*4*2 + 4*4*2 + 4*4*2 + 4*4*2
Ciao a tutti, Nino
Nino
"iant" ha scritto
> Ciao Livio.
>
> Invece per spiegare il "piattume" della media puoi pensare che un
> sistema triridotto puo' essere diverso di pochissimo da un sistema
> composto dallo stesso numero di colonne ma che non e' un triridotto.
>
> Se hai costruito il ridotto in modo casuale, e' estremamente
> improbabile che tu abbia costruito un triridotto, cioe' un sistema
> che dia **garanzia** di fare 13/16. Quello della garanzia di un
> risultato e' un caposaldo irremovibile della sistemistica!!!
>
SACROSANTO!! Come fondamentale è, a parità di garanzia minima di
vincita, il numero delle colonne, che deve essere il minimo.
> E' invece quasi certo che tu abbia ottenuto un sistema a garanzia
> 11/16, e hai ottime probabilita' di aver ottenuto un 12/16.
> (Lo dico anche sulla base di simulazioni che ho fatto io.) A me
> viene che ridotti di 256 colonne generati a caso lasciano "scoperte"
> tra le 3000 e le 5000 colonne del sistema integrale, nel senso che
> su quelle non si fara' 13/16 ma un po' meno, generalmente 11/16.
> Quindi tenuto conto che nel complesso le colonne sono 65536, 5000
> di queste che fanno 11 anziche' 13 spostano poco la media.
>
> La verita' e' che la garanzia del 13/16 puo' addirittura andare in
> controtendenza rispetto al valore medio di sistemi con garanzia
> inferiore! Cioe' e' possibile avere sistemi a garanzia di 12/16 che
> hanno rendita media *superiore* a sistemi con garanzia 13/16.
>
Anche questo è verissimo, si tratta di vedere cosa privilegiare.
Ovvio che in sistemistica vale la garanzia minima, sarebbe terribile
indovinare il pronostico e non vincere quello che si era preventivato.
Ciao, Nino
Livio Zucca
Non male: 13.500+
Le tue word si sono "evolute" nella Darwin Machine tutta la notte.
Ciao!!! ((^__^))'
Livio
0000000000100100
0000100011110111
0000000101101010
0000101011011111
0000001111010110
0000010011001001
0000110110111110
0000011010111011
0000011110111000
0000101010011101
0000100110011010
0000101010000011
0010101101111101
0000110001110101
0100110101100111
0000111001011011
0000111111000000
0001001001000101
0001000110110010
0001001000101111
0001001100100100
0001010000011000
0001010100001110
0001010000000011
0001011011111000
1001011111101101
0001100011100110
0001100111010111
0001101011001100
0001001111000001
0011110010011110
0001110110101011
0001111010100100
0001111110010100
0010000010001010
0010001101101111
0010011101110100
0011001100001000
0110010001011110
0011000101010011
0010011001001000
0000011100111101
0010100000110010
0011100100100111
0010101000011100
0010111100010001
0010111000000110
0010110011111001
0010110111110000
0010111011100111
0010111111011010
0011000111001111
0011000111010100
0011001010110001
0011001111101010
1011011000100011
0010010110011000
0011011010001101
0111010110000010
0011101001111111
0011100101101100
0001101001100001
1011111101010110
0011100101001011
0111110111000000
0111101000110101
0111111100101010
0100000000001011
0110000100010100
0100001100001101
0000000100000010
0101111011110111
1100010011101100
0100010111110001
0100011011000110
0100011111001011
0000100011000000
0100100110110101
0110101010101010
0100111110011111
0100110010010100
0100100110011001
0100111001111110
0100011111110011
0101000001101000
0100000101011101
0101001000011010
0101001101000111
0101110001111100
0101010100110001
0101011001100110
0101011100011011
0101100001010000
0111100100000001
1101100101111010
0101101010101111
1101101111100100
0101110111011001
0100101111101110
1101111011000011
0101101110111000
0110000010101101
0110000110100010
0111000010010111
0110001110101101
0110010010000001
0110010101110110
0110011001100111
0110011101100000
0100100001100101
0110100101001010
0110001000111111
0100101100110011
0110110000101001
0010110101011110
1110111100010010
0010111100001000
0110111111111101
0111000011110010
1111000111100001
0111001011011100
0111001111010001
1111010011000110
0111010011111011
0111011010110000
0111011110100111
0111100010000010
0111100111011110
0111101010000100
0111101101111001
0111110101101110
0111110101100011
0111111001011000
1111111001001111
1000001011000001
1000000100111001
1000001000110000
1010001100100111
1000010000011100
1000010100010011
0000011000001010
1000011110000001
1000011011110110
1000100111101001
1000101111100000
1000101011010101
1100001111001000
1000110010111011
1000110110111110
1000111010101001
1100011110011110
1001010010010011
0011000011000000
1001001001111101
1001001101110010
1001010001101111
0101010101011111
1001111000010100
0000011101101000
1001100011001110
1001100001011001
1001011001010011
1001101101001111
1001110001001000
1001100100111101
1101111000110010
1001111101000000
1010000010110111
1010000100101100
1010001001101011
1010001101010000
1011010111111000
1010010101000101
1010011000100110
1010011111001111
1010100001110100
1010100001010010
1010100001001001
1011101110111110
1111100001000111
1010110101000011
1010111001100000
1010111101011101
1011000001011110
1011000001100000
1011001011101110
1011001110000101
1011010010100011
1111010101111100
1011111000110101
1001011110010000
1011100110001001
1011100110000010
1011101000001010
1011101010010111
1011110010010101
1011110110001100
1001111010000111
1011111101111011
1100000001110000
1100000101100100
1100001011011011
1100001101010101
1100010101001101
1100010100001110
1100011100101111
1101111100110100
1100000000101100
1000100100100001
1100101000010110
1100101100001000
1100110000000000
1100100011110101
1110110111101111
1110101111100110
1100111111111001
0101000001111101
1101010111010100
1101011011001001
1101001110101110
1101010010110111
0101010110101101
1100011010100001
1111011100010101
1111110010011100
1101100110010001
0101101000001011
1101101110100010
1001110010101010
1101110111100000
1101111111011110
1101110101110001
1110100011101000
1110000101111101
0110101011110010
0110000111000111
1110010010111100
1110010100110101
1110011010100111
1110011110101010
1110100010011111
1110100110010100
1110101010010001
1110101110011011
1110110000000010
1100110110000011
1110011010001101
1110111110010100
1111000100101011
1111000010111000
1011001010110100
1111010111001010
1111010001010001
1111011000111110
1111101000101000
0111110100100100
Giorgio Vecchi
> "Giorgio Vecchi" <gve...@galactica.it> ha scritto:
> > Vi allego le 256 word, se qualcuno le volesse controllare. :-)
> > ...
>
> Non male: 13.500+
> Le tue word si sono "evolute" nella Darwin Machine tutta la notte.
>
Bene! Se si vince, facciamo a metà! :-))
Ciao :-)
Giorgio
Giorgio Vecchi
>
> Mi ha incuriosito il programma per generare ridotti fatto da Giorgio
> (però, le 256 word presentate configurano un probabilistico, essendo
> n-4).
Ciao, Nino. Devo confessare che non capisco bene il tuo linguaggio
(considera che io di sistemi ridotti non ne so proprio niente). Cosa intendi
per "configurano un probabilistico, essendo n-4"? E' un'offesa o un
complimento? ;-)
Ti posso comunque dire che il mio programma è quanto di più rozzo si possa
immaginare. Parte dalla prima word (la 000...000) e marca tutte le word (tra
le 65536) che otterrebbero 16, 15 e 14 punti. Poi ne prende un'altra di
quelle non marcate, fa la stessa cosa e così via finché non ne ha prese 256.
Poi cerca di massimizzare il numero di quelle marcate.
> Mi scuso quindi se approfitto delle vostre capacità informatiche
> e vi chiedo se qualcuno volesse gentilmente controllare per la
> vincita media le 256 word che ho schematizzato di seguito ( a mano
> è un lavoro improbo e dal risultato incerto).
>
> 0 1 1 0 1 0 1 0
> 0 1 1 0 0 1 0 1
> 0 1 0 1 1 0 0 1
> 0 1 0 1 0 1 1 0
> 0 0 1 1 0 0 1 1
> 0 0 1 1 1 1 0 0
> ------------------------- + ---------------------------
[cut]
Ecco, anche qui non mi è chiaro che cosa si deve fare. Se mi fai un
esempietto forse tutto si chiarisce. Forse, sforzandomi, ci potrei arrivare
da solo, ma considera che è domenica mattina e la pigrizia incombe. :-)
Una volta che hai chiarito come ottenere le 256 word, posso provare a
controllarle, anche se probabilmente lo può fare più rapidamente Livio, che
dovrebbe avere già implementato un modo per importare le word altrui! ;-)))
Ciao :-)
Giorgio
Dario Uri
> "Nino" <a...@libero.it> wrote
>
>>Mi ha incuriosito il programma per generare ridotti fatto da Giorgio
>>(però, le 256 word presentate configurano un probabilistico, essendo
>>n-4).
Il riduttore cosi' ottenuto, non da' l'assoluta certezza dello scarto
massimo di 3 punti, visto che garantisce solo un n-4, per questo credo
che Nino usi "probabilistico" anziche' "assoluto"
Non ho seguito bene il thread. Pero' vorrei buttare giu' qualche idea
sperando di non dire stupidaggini.
Allora, se ho ben capito tu costruisci la libreria delle 2^16 = 65536
parole, poi ne tieni una a caso e cancelli dalla libreria tutte quelle
che non sono piu' lontane di 3 bit dalla stringa scelta.
E' chiaro che alla prima operazione verranno scartate tutte quelle
"differenti" per:
1 bit = c(1,16)= 16
2 bit = c(2,16)= 120
3 bit = c(3,16)= 560
totale 696.
Ora con quale criterio il programma sceglie la prossima word?
Se la scelta e' random c'e' il rischio di selezionarne una non troppo
lontana dalla prima che coprirebbe molte stringhe gia' cancellate,
percio' sarebbe opportuno scegliere la piu' "differente" vale a dire la
stringa complementare, in pratica quella con tutti i bit invertiti di
segno, che sicuramente mi cancellera' altre 696 words dalla libreria.
Capito il concetto conviene allora lavorare solo sulle prime 32768
stringhe, selezionarne 128 (vedremo poi come ottimmizzare questa scelta)
eppoi integrarle con le 128 complementari, che coprono per simmetria le
seconde 32768.
Ora per ottimizzare la scelta, ogni volta bisognerebbe controllare fra
le rimaste nella libreria quella/e in grado di cancellarne il massimo.
E' chiaro che con questo procedimento se non mi limito a selezionare 256
stringhe, ma continuo fino all'esaurimento della libreria, ottengo un
tririduttore assoluto. Con questo criterio pero' rimarrebbe la scelta
aleatoria fra le words con la stessa "potenza" di copertura.
Un'idea per arrivare direttamente al risultato potrebbe essere quella di
scegliere le 256 stringhe equidistanti come posizione es:
65536/256 = 256 selezionando quelle in posizione:
128,384,640.......65408, ma....
In quale modo sono state generate le stringhe? se ad es. hai
semplicemente scritto i numeri da 1 a 65536 in binario, non si puo' fare
perche' la distribuzione degli "0" e degli "1" non e' omogenea.
Ogni volta che si arriva ad una potenza di 2, un bit "1" ne sostituisce
molti altri.
Cosa succede se la libreria fosse invece generata in codice Gray ?
Non lo so, ma mi piacerebbe se qualcuno verificasse....
Nino
"Giorgio Vecchi" dice
>
> Ciao, Nino. Devo confessare che non capisco bene il tuo linguaggio
> (considera che io di sistemi ridotti non ne so proprio niente). Cosa
intendi
> per "configurano un probabilistico, essendo n-4"? E' un'offesa o un
> complimento? ;-)
>
Non mi permetterei mai (per l'offesa ;-))
Semplicemente, come ha già spiegato iant, in sistemistica un sistema
ha valenza esclusivamente per quanto attiene la sua garanzia minima
di vincita. Quindi, nel caso specifico, i confronti possono essere fatti
solo con agglomerati omogenei (cioè, tra sistemi triridotti (detti n-3
perchè garantiscono almeno 3 punti in meno del massimo, cioè il 13).
Le tue 256 word non posseggono questa caratteristica, in quanto per il
13 ci sono lacune, e il sistema non è garantito, ma solo probabilistico.
La certezza al 100% è per il 12, cioè n-4, quattro punti in meno del
massimo, e le tue colonne andrebbero quindi confrontate con gruppi
colonnari con le medesime peculiarità (garanzia n-4): ovvio che, in
tal caso si può fare nettamente meglio, sistemisticamente, in quanto
sono sufficienti solo un centinaio di colonne (che forniscono
la stessa garanzia minima delle tue 256).
> Ti posso comunque dire che il mio programma è quanto di più rozzo si possa
> immaginare. Parte dalla prima word (la 000...000) e marca tutte le word
(tra
> le 65536) che otterrebbero 16, 15 e 14 punti.
Questo meccanismo in sistemistica si chiama "a massima rappresentatività".
Ma perchè non marca, ed esclude, anche le word che ottengono 13 punti,
prima di procedere alla scelta di un'altra word?
> > Mi scuso quindi se approfitto delle vostre capacità informatiche
> > e vi chiedo se qualcuno volesse gentilmente controllare per la
> > vincita media le 256 word che ho schematizzato di seguito ( a mano
> > è un lavoro improbo e dal risultato incerto).
> >
> > 0 1 1 0 1 0 1 0
> > 0 1 1 0 0 1 0 1
> > 0 1 0 1 1 0 0 1
> > 0 1 0 1 0 1 1 0
> > 0 0 1 1 0 0 1 1
> > 0 0 1 1 1 1 0 0
> > ------------------------- + ---------------------------
>
> [cut]
>
> Ecco, anche qui non mi è chiaro che cosa si deve fare. Se mi fai un
> esempietto forse tutto si chiarisce. Forse, sforzandomi, ci potrei
arrivare
> da solo, ma considera che è domenica mattina e la pigrizia incombe. :-)
>
Scrivo in orizzontale le prime (4*4*2) + (4*4*2) word relative al primo
gruppo schematizzato. Lo stesso va fatto per gli altri 3 gruppi.
0000000000000000
0000000000001111
0000001111000000
0000001111001111
0000001100110000
0000001100111111
0000000011110000
0000000011111111
1111000000000000
1111000000001111
1111001111000000
1111001111001111
1111001100110000
1111001100111111
1111000011110000
1111000011111111
1100110000000000
1100110000001111
1100111111000000
1100111111001111
1100111100110000
1100111100111111
1100110011110000
1100110011111111
0011110000000000
0011110000001111
0011111111000000
0011111111001111
0011111100110000
0011111100111111
0011110011110000
0011110011111111
0000001010011100
0000001010010011
0000000101011100
0000000101010011
0000001001101100
0000001001100011
0000000110101100
0000000110100011
1111001010011100
1111001010010011
1111000101011100
1111000101010011
1111001001101100
1111001001100011
1111000110101100
1111000110100011
1100111010011100
1100111010010011
1100110101011100
1100110101010011
1100111001101100
1100111001100011
1100110110101100
1100110110100011
0011111010011100
0011111010010011
0011110101011100
0011110101010011
0011111001101100
0011111001100011
0011110110101100
0011110110100011
> Una volta che hai chiarito come ottenere le 256 word, posso provare a
> controllarle, anche se probabilmente lo può fare più rapidamente Livio,
che
> dovrebbe avere già implementato un modo per importare le word altrui!
;-)))
>
Ciao, Nino
iant
"Livio Zucca" <liviozuc...@tiscalinet.it> ha scritto:
>
>"Giorgio Vecchi" <gve...@galactica.it> ha scritto:
>>
>> Ho buttato giů un programma per generare ridotti. Per ora č arrivato a un
>> po' piů di 13.48 di vincita media. Vi allego le 256 word, se qualcuno le
>> volesse controllare. :-) Alcune combinazioni vincono solo 12 punti.
>> ...
>
>Controllate! :o)
Le ho controllate anch'io. Ecco il dettaglio:
punti colonne
16 256
15 4096
14 25003
13 33724
12 2456
11 1
Vincita media: 13.48072
Poiche' ci sono 2457 colonne che vincono meno di 13 punti il
sistema non e' un triridotto.
>Le ho anche messe nella Darwin Machine che in un paio d'ore :o)
>ha portato la vincita media da 13.481+ a 13.487+. Se non sbaglio e' il record!
>Dovete per ora credermi sulla parola perche' ho azzerato il prog. prima di
>salvare il sistema. :o( Ci riprovero' cercando di velocizzare il calcolo.
Darwin Machine??? Intendi con quel termine l'implementazione di un
algoritmo genetico? Allora non sono l'unico pazzo!!! ;-))
Stimolato dai tuoi risultati ono andato a rispolverare la mia Darwin
Machine, adattandola al problema dei Gini, e finora ho ottenuto un
ridotto con media 13.511673
16 256
15 4078
14 25682
13 34447
12 1073
1073 combinazioni realizzano 12 punti => non e' un triridotto.
Credo sia l'attuale record. Lo posto, cosi' controllate anche voi,
(e potete usarlo per inizializzare le vostre Darwin Machine).
Saluti,
iant
0101110101001101
0011000111001110
0100101100001001
0111111000100000
0110100011001010
1011000100110101
1111010111011001
0100010100000000
1101011111010101
0110011101011000
1110010010111110
0011101111011011
1100100001101000
0110011111101011
0011010010000011
1110010100111011
1101111111101001
1111111001000011
0001110010101001
0100111111010011
0010101010110000
0000011111101010
0000100010100100
1011011001010000
1001011100110001
1000111000100101
1110100101000111
1101001001000110
0011001011010110
0111001010001000
0010010010011000
1011101001011110
0111100111011100
0101110001000011
0001011001111110
1000001111110011
0011011110000111
0010011000001110
0011101010100011
0001011100001000
1000110001100110
0110110001110111
1011101010001011
0100000111110100
0001101010111111
1110001110011010
1011110001101000
0010011000001011
0101010111110000
0111110001111010
0000000000111011
0001011101111000
0001010100011010
0101001010011101
1011001011110111
1001110111100100
1010011000100000
1011110100000111
1000101010111110
0001100100110001
0010010100101110
0111001001111010
1010101010000111
1111010101111101
0001100101010110
0010111101111000
1110101000111000
1001000100101101
0001101111000000
0001010011110010
0011000001001111
1000110010011001
1110110110000010
1101010101100111
0111111101000100
1110110010010011
0101000010010001
1110101011001100
1100100111100111
0010110111000101
0111100100000111
0101000101110010
1001001110100010
0110011111100110
1110010011111100
1010100100110010
1100110110101011
0111000100111011
0011100011000100
0101111011001110
1110100100100000
1000010110001000
1011000101000010
0010111100110011
0111001100110111
1100111100110111
0101011110111000
0110011101110001
0000101110101111
1001111101001101
1001000001100001
0010011011111101
1101011101101011
0110110011011011
0000001101000101
1110010000011111
1001111010000000
1000010000011100
0000010101011001
0001011001100111
1111000011100001
0110111110001100
0010101111100011
0010110000010101
1010100101111110
0111000000101001
0111100100010001
1110001100001100
1001100101011000
0100100011110111
1111011111010010
1001010111111111
1011100000011010
1111101110010101
1100110101111101
0100000100010100
0110000100100100
1111001011101100
0001100000100110
1100011011111111
1010010111001100
0101101101110100
1101111000010111
0000011010101101
0011000100010000
1000000110001111
0110101111101110
0001001011000100
0000011000010110
0110000111000000
1000000000111000
1000110011010101
1001010100110111
0011001110000110
0001101101101010
1010000110000001
1111110000001010
1000111011001111
1100001001010000
1101001110000110
0111011000001001
0111010110010111
0011010000111100
1101011110100001
1111110100101111
0100010011001000
0111111010111001
1110110101010001
1110000001000010
0101000001011100
0010001100011101
0000111111011100
1111110110100110
1011101101101000
0011000110111001
1101111000111001
1101000110001101
1011010100010110
1000010011000001
0000000000000011
1110101101001011
1011011011111011
0110001110100011
0010000011101010
1110100100010011
1111000001010011
1100101010000011
0011011111000001
0101111001000000
1111011100100110
0011010110011101
1011110111001011
0100110110010010
0011100110011111
0100100111111110
0010111011011111
1001111100110011
0110111110101001
1010011101010110
1101100011111101
1000001110110101
1000000101111001
1100000001001011
1100010001100100
0000101101001010
0010001000110001
1101111100011110
1111000110101111
1011110110110101
1001101001111001
0110001000101110
1010100011111001
1110110011100010
1100111001101010
0100000000001100
0100001101011111
0100010010110010
1101100110111000
1011111110111100
1001100000001000
0110111000010100
0010100001010010
0010110101100011
1111101111011001
0000111110011010
0011111101111101
0001110110110100
1001000011010010
1101010011001110
1100110110110101
0100011011100111
1100111011010110
0101101000110111
1010001001100111
0010000111101100
1011111011110111
0100001001110010
0111101001100101
0001110010000000
0011011010100100
1011011100000101
0000110101011110
1100101001111001
1000001011101000
0101001011111011
0101001000011010
1011000111101011
1111101111110010
0101000110001011
0100101011011001
0000110111110000
0010101101101001
1101011000000011
0101010010101101
1000101100010100
1111100010110100
1101110010011100
1010011110111010
1100000100101111
1101111000110110
1110011010000101
0100111100101100
1010000001001101
1110100000101101
1001000010111110
0011110111101110
Nino
"Dario Uri" dice
>
> Il riduttore cosi' ottenuto, non da' l'assoluta certezza dello scarto
> massimo di 3 punti, visto che garantisce solo un n-4, per questo credo
> che Nino usi "probabilistico" anziche' "assoluto"
>
Certo.
> Allora, se ho ben capito tu costruisci la libreria delle 2^16 = 65536
> parole, poi ne tieni una a caso e cancelli dalla libreria tutte quelle
> che non sono piu' lontane di 3 bit dalla stringa scelta.
> E' chiaro che alla prima operazione verranno scartate tutte quelle
> "differenti" per:
> 1 bit = c(1,16)= 16
> 2 bit = c(2,16)= 120
> 3 bit = c(3,16)= 560
> totale 696.
> Ora con quale criterio il programma sceglie la prossima word?
.
.
> Ora per ottimizzare la scelta, ogni volta bisognerebbe controllare fra
> le rimaste nella libreria quella/e in grado di cancellarne il massimo.
> E' chiaro che con questo procedimento se non mi limito a selezionare 256
> stringhe, ma continuo fino all'esaurimento della libreria, ottengo un
> tririduttore assoluto. Con questo criterio pero' rimarrebbe la scelta
> aleatoria fra le words con la stessa "potenza" di copertura.
>
Non è solo questo il problema.
Quello descritto è il metodo empirico più intuitivo per ottenere sistemi
ridotti; normalmente, però, non fornisce risultati apprezzabili ove si
consideri il numero delle colonne totali necessarie, che è normalmente
maggiorato rispetto ad un riduttore "primato".
Ciò è dovuto al fatto che la partenza più vantaggiosa di massima
rappresentatività conduce quasi sempre ad una pessima chiusura per
l'aggancio delle ultime colonne rimaste scoperte, che pur in numero
esiguo necessitano di molte colonne per la loro riduzione.
Per questo, la maggior parte dei programmi computerizzati specifici
utilizzano raggruppamenti mirati (oltre metà colonne del ridotto finale)
imposte e studiate a tavolino e si limitano ad ottimizzare solo la
riduzione delle poche colonne non agganciate, cercando il minor numero
di colonne necessarie a questo scopo (che vanno aggiunte alle prime,
con eventuale successiva compressione).
> Cosa succede se la libreria fosse invece generata in codice Gray ?
> Non lo so, ma mi piacerebbe se qualcuno verificasse....
>
A me Gray ricorda solo l'unità di misura della dose di radiazione
ionizzante assorbita....
Ciao, Nino
Livio Zucca
> "Giorgio Vecchi" dice
>>
>> Ciao, Nino. Devo confessare che non capisco bene il tuo linguaggio
> Scrivo in orizzontale le prime (4*4*2) + (4*4*2) word relative al primo
> gruppo schematizzato. Lo stesso va fatto per gli altri 3 gruppi.
>
> 0000000000000000
> 0000000000001111
> 0000001111000000
> ...
>> Una volta che hai chiarito come ottenere le 256 word, posso provare a
>> controllarle, anche se probabilmente lo può fare più rapidamente Livio,
>> che dovrebbe avere già implementato un modo per importare le word
>> altrui! ;-)))
Vero, ho costruito un macinino che analizza un file ascii come questi.
Ho anche tentatto di scrivere per esteso quest'ultimo di Nino, ma mi
si incrociano gli occhi. Facciamo cosi', se vi va: voi scrivete per
esteso il file di 256 righe e io lo metto nel macinino. :o)
(Prometto di farlo per ogni sistemino che vi venga in mente!)
Ciao!!! ((^__^))'
Livio
Livio Zucca
> Darwin Machine??? Intendi con quel termine l'implementazione
> di un algoritmo genetico? Allora non sono l'unico pazzo!!! ;-))
Ne parlavo qua:
http://www.geocities.com/liviozuc/darwin.html
Fammi sapere se stiamo parlando di cose analoghe.
> Stimolato dai tuoi risultati ono andato a rispolverare la mia Darwin
> Machine, adattandola al problema dei Gini, e finora ho ottenuto un
> ridotto con media 13.511673
Ora vado ad esaminarlo!
Ciao!!! ((^__^))'
Livio
Nino
dicevo:
queste sono le 256 word che, salvo errori di
copia/incolla, prego di controllare:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1
0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 0
1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1
1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0
1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0
1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1
1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1
0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1 0 0 1 1 0 0 0 0
0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1
0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0
0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1
0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1
0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1
0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1
1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0
1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1
1 1 1 1 0 0 0 1 0 1 0 1 1 1 0 0
1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1
1 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0
1 1 1 1 0 0 1 0 0 1 1 0 0 0 1 1
1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0
1 1 1 1 0 0 0 1 1 0 1 0 0 0 1 1
1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0
1 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1
1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0
1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1
1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0
1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 1
1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0
1 1 0 0 1 1 0 1 1 0 1 0 0 0 1 1
0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 0
0 0 1 1 1 1 1 0 1 0 0 1 0 0 1 1
0 0 1 1 1 1 0 1 0 1 0 1 1 1 0 0
0 0 1 1 1 1 0 1 0 1 0 1 0 0 1 1
0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0
0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1
0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0
0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1
1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0
1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1
1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0
1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1
1 0 1 0 0 1 1 1 0 0 1 1 1 0 1 0
1 0 1 0 0 1 1 1 0 0 1 1 0 1 0 1
1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 0
1 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1
0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1
0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0
0 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1
0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0
0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1
0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0
0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1
1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0
1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1
1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0
1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 1
1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0
1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1
1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 0 0 1 1 1 1 0 1 0 1
0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0
0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1
0 1 1 0 1 0 1 1 1 1 0 0 1 0 1 0
0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 1
0 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0
0 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1
0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0
0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 1
1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1
1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 0
1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1
1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0
1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1
1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1
1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0
0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1
0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0
0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0
0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1
0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0
0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1
0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0
1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1
1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0
1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1
1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0
1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1
1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0
1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1
1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0
0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1
0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1
0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 0
0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1
0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0
0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1
1 1 1 1 1 1 0 0 1 1 0 0 1 0 0 0
1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 1
1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0
1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1
1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0
1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1
1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0
1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1
1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0
1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1
1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0
1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1
0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1
0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0
0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1
0 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0
0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 1
0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0
0 0 1 1 0 0 0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0
0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1
0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0
0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0
1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1
1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0
1 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0
1 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1
1 1 1 1 1 1 0 1 1 0 0 1 0 1 0 0
1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1
1 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0
1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1
1 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0
1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1
1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0
1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1
1 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0
1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1
0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0
0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1
0 0 1 1 0 0 0 1 0 1 1 0 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1
0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0
0 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0
0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1
0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0
0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1
0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 0
0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1
0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0
0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 1
0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0
0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1
1 0 1 0 1 0 1 1 1 1 1 1 0 1 1 0
1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1
1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0
1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1
1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0
1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1
1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0
1 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1
0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0
0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1
0 1 0 1 1 0 1 1 0 0 0 0 0 1 1 0
0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1
0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0
0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1
0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0
0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 1
1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 0
1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1
1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0
1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1
1 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0
1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1
1 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0
1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1
0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0
0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1
0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0
0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1
0 1 1 0 0 1 0 0 1 1 0 0 0 1 1 0
0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1
0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0
0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1
1 0 1 0 1 0 0 1 0 1 1 0 1 1 1 0
1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1
1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0
1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1
1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0
0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1
0 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0
0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1
0 1 0 1 1 0 0 1 0 1 1 0 1 1 1 0
0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1
0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0
0 1 0 1 1 0 0 1 1 0 0 1 0 0 0 1
0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0
1 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1
1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0
1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1
1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 0
1 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1
1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0
1 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1
1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0
0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1
0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0
0 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0
0 1 1 0 0 1 1 0 0 1 0 1 0 0 0 1
0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0
0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1
0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 0
>
> > posso provare a
> > controllarle, anche se probabilmente lo può fare più rapidamente Livio,
> che
> > dovrebbe avere già implementato un modo per importare le word altrui!
> ;-)))
> >
Grazie, Nino
Nino Aspesi
>
> queste sono le 256 word che, salvo errori di
> copia/incolla, prego di controllare:
>
Infatti
Ho trovato 16 colonne con inversioni;
prego tenere conto di questo sviluppo
e non considerare il precedente:
1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0
1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1
1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0
1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1
1 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0
1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1
1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0
1 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1
0 1 0 1 1 0 1 1 1 1 1 1 0 0 1 0
0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1
0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0
0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1
0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0
0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1
0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0
0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 1
1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0
1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1
1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1
1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0
1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1
1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0
1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1
0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0
0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1
0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0
0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1
0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0
0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1
0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0
Scusate di nuovo
Nino
iant
>[...]
>Allora, se ho ben capito tu costruisci la libreria delle 2^16 = 65536
>parole, poi ne tieni una a caso e cancelli dalla libreria tutte quelle
>che non sono piu' lontane di 3 bit dalla stringa scelta.
Il concetto di costruire la libreria delle 2^16 word e poi prendere
una word a caso e' giusto, mentre quello di cancellare le word da essa
rappresentate non e' cosi' giusto, perche' quelle word potrebbero
tornarti comode in futuro. Provo a spiegarmi.
Come ho gia' scritto a Livio in un altro post, ogni word puo' essere
pensata come una pezza di forma frastagliata che copre 697 word del
sistema integrale. All'inizio e' molto facile mettere pezze che non
si sovrappongono, ma piu' vai avanti e piu' diventa difficile.
In particolare alla fine possono rimanerti diversi piccoli buchi,
cioe' diverse word isolate e molto distanti, che ti costringeranno
a scegliere quelle word come rappresentanti solo di se stesse.
E' invece possibile che ci sia una pezza tra quelle che hai cancellato
all'inizio che era in grado di rappresentare un numero maggiore di
word finali. Spero di essere stato chiaro.
Quindi il metodo corretto e' quello di usare due vettori, uno che
contiene il sistema integrale (e non lo tocchi mai!), e uno da cui
cancelli le word solo per tenere traccia di quanto hai gia' coperto.
La scelta della pezza migliore va sempre fatta su tutte le colonne.
Purtroppo, nonostante questa accortezza, questi metodi "incrementali"
non funzionano molto bene...
>[...]
>Ora per ottimizzare la scelta, ogni volta bisognerebbe controllare fra
>le rimaste nella libreria quella/e in grado di cancellarne il massimo.
Quello che tu hai descritto, e' il metodo che in ottimizzazione e'
noto come metodo "greedy" (goloso). In pratica tu ad ogni passo
cerchi di fare il meglio che puoi, e cioe' ottimizzi su scala locale.
Purtroppo questo metodo non ti garantisce di trovare l'ottimo
globale. (Diro' di piu': potrai trovare il ridotto ottimo globale
in questo modo solo nei casi in cui esiste il ridotto perfetto che,
per definizione, e' quello in cui non c'e' sovrapposizione tra le
word cancellate dalle diverse word del ridotto.)
In tutti gli altri casi puo' facilmente succedere che una serie
casuale di k word cancelli piu' word delle k word "migliori" in
senso greedy. Questa e' in generale la scoperta piu' fastidiosa
che si fa quando ci si imbatte nella ricerca al computer
di sistemi ridotti! ;-)
Detto questo, dopo molti tentativi ed esperienze fatte in passato,
il metodo che mi ha fatto trovare le soluzioni migliori (di gran
lunga migliori rispetto al greedy) e' stato quello di applicare un
algoritmo genetico, che per sua natura opera su scala globale,
esplora in modo casuale lo spazio delle soluzioni e "sfrutta" le
migliori soluzioni trovate per costruirne altre potenzialmente
migliori.
>E' chiaro che con questo procedimento se non mi limito a selezionare 256
>stringhe, ma continuo fino all'esaurimento della libreria, ottengo un
>tririduttore assoluto. Con questo criterio pero' rimarrebbe la scelta
>aleatoria fra le words con la stessa "potenza" di copertura.
Nel nostro caso specifico, inoltre, non e' detto che tu riesca a
rimanere al di sotto delle 256 colonne.
>Un'idea per arrivare direttamente al risultato potrebbe essere
>quella di scegliere le 256 stringhe equidistanti come posizione [...]
A tutta prima direi che sceglierle in modo ordinato non dovrebbe
essere troppo diverso da sceglierle a caso.
>Cosa succede se la libreria fosse invece generata in codice Gray ?
Sai che l'idea non e' male? Se ho un po' di tempo ci provo e ti
faccio sapere.
A presto,
Antonio
iant
>
>Mi scuso quindi se approfitto delle vostre capacità informatiche
>e vi chiedo se qualcuno volesse gentilmente controllare per la
>vincita media le 256 word che ho schematizzato di seguito ( a mano
Ho sviluppato e controllato il tuo sistema.
16 256
15 4096
14 25856
13 35328
Vincita media: 13.53125
Semplicemente S-T-R-A-O-R-D-I-N-A-R-I-O, record di vincita media
e garanzia del 13!
Intanto il mio programma dopo una giornata di duro lavoro e'
arrivato solo a garanzia del 12 (per 928 colonne) e vincita
media 13.517532. A conferma del fatto che una solida base
teorica e' ancora uno strumento potentissimo!
Ancora complimenti e a presto,
iant
Posto qui di seguito lo sviluppo del ridotto record di Nino:
1111000101010011
1111001001101100
1111001001100011
1111000110101100
1111000110100011
1100111010011100
1100111010010011
1100110101011100
1100110101010011
1100111001101100
1100111001100011
1100110110101100
1100110110100011
0011111010011100
0011111010010011
0011110101011100
0011110101010011
0011111001101100
0011111001100011
0011110110101100
0011110110100011
1010101010100001
1010101010101110
1010100101100001
1010100101101110
1010101001010001
1010101001011110
1010100110010001
1010100110011110
0101101010100001
0101101010101110
0101100101100001
0101100101101110
0101101001010001
0101101001011110
0101100110010001
0101100110011110
1001011010100001
1001011010101110
1001010101100001
1001010101101110
1001011001010001
1001011001011110
1001010110010001
1001010110011110
0110011010100001
0110011010101110
0110010101100001
0110010101101110
0110011001010001
0110011001011110
0110010110010001
0110010110011110
1010101111110010
1010101111111101
1010100000110010
1010100000111101
1010101100000010
1010101100001101
1010100011000010
1010100011001101
0101101111110010
0101101111111101
0101100000110010
0101100000111101
0101101100000010
0101101100001101
0101100011000010
0101100011001101
1001011111110010
1001011111111101
1001010000110010
1001010000111101
1001011100000010
1001011100001101
1001010011000010
1001010011001101
0110011111110010
0110011111111101
0110010000110010
0110010000111101
0110011100000010
0110011100001101
0110010011000010
0110010011001101
1111111111111000
1111111111110111
1111110000111000
1111110000110111
1111111100001000
1111111100000111
1111110011001000
1111110011000111
0000111111111000
0000111111110111
0000110000111000
0000110000110111
0000111100001000
0000111100000111
0000110011001000
0000110011000111
1100001111111000
1100001111110111
1100000000111000
1100000000110111
1100001100001000
1100001100000111
1100000011001000
1100000011000111
0011001111111000
0011001111110111
0011000000111000
0011000000110111
0011001100001000
0011001100000111
0011000011001000
0011000011000111
1111111010100100
1111111010101011
1111110101100100
1111110101101011
1111111001010100
1111111001011011
1111110110010100
1111110110011011
0000111010100100
0000111010101011
0000110101100100
0000110101101011
0000111001010100
0000111001011011
0000110110010100
0000110110011011
1100001010100100
1100001010101011
1100000101100100
1100000101101011
1100001001010100
1100001001011011
1100000110010100
1100000110011011
0011001010100100
0011001010101011
0011000101100100
0011000101101011
0011001001010100
0011001001011011
0011000110010100
0011000110011011
1010010000001010
1010010000000101
1010011111001010
1010011111000101
1010011100111010
1010011100110101
1010010011111010
1010010011110101
0101010000001010
0101010000000101
0101011111001010
0101011111000101
0101011100111010
0101011100110101
0101010011111010
0101010011110101
1001100000001010
1001100000000101
1001101111001010
1001101111000101
1001101100111010
1001101100110101
1001100011111010
1001100011110101
0110100000001010
0110100000000101
0110101111001010
0110101111000101
0110101100111010
0110101100110101
0110100011111010
0110100011110101
1010011010011001
1010011010010110
1010010101011001
1010010101010110
1010011001101001
1010011001100110
1010010110101001
1010010110100110
0101011010011001
0101011010010110
0101010101011001
0101010101010110
0101011001101001
0101011001100110
0101010110101001
0101010110100110
1001101010011001
1001101010010110
1001100101011001
1001100101010110
1001101001101001
1001101001100110
1001100110101001
1001100110100110
0110101010011001
0110101010010110
0110100101011001
0110100101010110
0110101001101001
0110101001100110
0110100110101001
0110100110100110
Livio Zucca
> dicevo:
>>
>> queste sono le 256 word che, salvo errori di
>> copia/incolla, prego di controllare:
>>
>
> Infatti
> Ho trovato 16 colonne con inversioni;
> prego tenere conto di questo sviluppo
> e non considerare il precedente:
>
> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
> 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0
Ecco il mio report sui tuoi dati, che ho gia' visto coincidente
con quello di Antonio:
***********************************
Vincita media = 13.53125
Punti/Colonne
16: 256
15: 4096
14: 25856
13: 35328
12: 0
11: 0
10: 0
***********************************
Sono basito! Non ci posso credere!
Nino batte computer... alla grande!
Complimentoni!!! ((^__^))'
Livio
Giorgio Vecchi
>
> ***********************************
> Vincita media = 13.53125
> Punti/Colonne
> 16: 256
> 15: 4096
> 14: 25856
> 13: 35328
> 12: 0
> 11: 0
> 10: 0
> ***********************************
>
>
> Sono basito! Non ci posso credere!
> Nino batte computer... alla grande!
>
>
> Complimentoni!!! ((^__^))'
> Livio
>
Prima di tutto mi unisco ai complimenti di Livio. Fa piacere vedere che una
soluzione elegante, pulita e *pensata* produce risultati migliori dei nostri
tentativi brutali basati su poche e confuse idee (almeno per quanto mi
riguarda).
Ieri sono stato via tutto il giorno. Rispondo adesso cumulativamente ad
alcune delle osservazioni che mi hanno riguardato:
> Dario:
> Ora con quale criterio il programma sceglie la prossima word?
In maniera del tutto empirica ho visto che a partire da esattamente 245 word
dopo il tentativo precedente, le cose migliorano rispetto, ad esempio, a
provare la successiva. Provando con 244 o 246 ottengo risultati
drasticamente peggiori!
> Nino:
> Ma perchè non marca, ed esclude, anche le word che ottengono 13 punti,
> prima di procedere alla scelta di un'altra word?
Lo avevo inizialmente fatto, ma il programma si bloccava presto. Questo
perché avevo imposto il vincolo che almeno le 16 word da 15 punti dovessero
essere marcate tutte. Rimuovendo questo vincolo e marcando quelle da 13 le
cose migliorano. Nel tempo in cui prima arrivavo a 13.480+, adesso arrivo a
13.490+. Allego le word che danno questo risultato, se potessero essere
ancora utili a qualcuno.
Ciao :-)
Giorgio
0000000000000000
0000000011110101
0000000111101010
0000001011011111
0000001111010100
0000010011001001
0000010110111110
0000011010110011
0000011110101000
0000100010011101
0000100110010010
0000101010000111
0000101101111100
0000110001110001
0000110101100110
0000111001011011
0000111101010000
0001000001000101
0001000100111010
0001001000101111
0001001100100100
0001010000011001
0001010100001110
0001011000000011
0001011011111000
0001011111101101
0001100011100010
0001100111010111
0001101011001100
0001101111000001
0001110010110110
0001110110101011
0001111010100000
0001111110010101
0010000010001010
0010000101111111
0010001001110100
0010001101101001
0010010001011110
0010010101010011
0010011001001000
0010011100111101
0010100000110010
0010100100100111
0010101000011100
0010101100010001
0010110000000110
0010110011111011
0010110111110000
0010111011100101
0010111111011010
0011000011001111
0011000111000100
0011001010111001
0011001110101110
0011010010100011
0011010110011000
0011011010001101
0011011110000010
0011100001110111
0011100101101100
0011101001100001
0011101101010110
0011110001001011
0011110101000000
0011111000110101
0011111100101010
0100000000011111
0100000100010100
0100001000001001
0100001011111110
0100001111110011
0100010011101000
0100010111011101
0100011011010010
0100011111000111
0100100010111100
0100100110110001
0100101010100110
0100101110011011
0100110010010000
0100110110000101
0100111001111010
0100111101101111
0101000001100100
0101000101011001
0101001001001110
0101001101000011
0101010000111000
0101010100101101
0101011000100010
0101011100010111
0101100000001100
0101100100000001
0101100111110110
0101101011101011
0101101111100000
0101110011010101
0101110111001010
0101111010111111
0101111110110100
0110000010101001
0110000110011110
0110001010010011
0110001110001000
0110010001111101
0110010101110010
0110011001100111
0110011101011100
0110100001010001
0110100101000110
0110101000111011
0110101100110000
0110110000100101
0110110100011010
0110111000001111
0110111100000100
0110111111111001
0111000011101110
0111000111100011
0111001011011000
0111001111001101
0111010011000010
0111010110110111
0111011010101100
0111011110100001
0111100010010110
0111100110001011
0111101010000000
0111101101110101
0111110001101010
0111110101011111
0111111001010100
0111111101001001
1000000000111110
1000000100110011
1000001000101000
1000001100011101
1000010000010010
1000010100000111
1000010111111100
1000011011110001
1000011111100110
1000100011011011
1000100111010000
1000101011000101
1000101110111010
1000110010101111
1000110110100100
1000111010011001
1000111110001110
1001000010000011
1001000101111000
1001001001101101
1001001101100010
1001010001010111
1001010101001100
1001011001000001
1001011100110110
1001100000101011
1001100100100000
1001101000010101
1001101100001010
1001101111111111
1001110011110100
1001110111101001
1001111011011110
1001111111010011
1010000011001000
1010000110111101
1010001010110010
1010001110100111
1010010010011100
1010010110010001
1010011010000110
1010011101111011
1010100001110000
1010100101100101
1010101001011010
1010101101001111
1010110001000100
1010110100111001
1010111000101110
1010111100100011
1011000000011000
1011000100001101
1011001000000010
1011001011110111
1011001111101100
1011010011100001
1011010111010110
1011011011001011
1011011111000000
1011100010110101
1011100110101010
1011101010011111
1011101110010100
1011110010001001
1011110101111110
1011111001110011
1011111101101000
1100000001011101
1100000101010010
1100001001000111
1100001100111100
1100010000110001
1100010100100110
1100011000011011
1100011100010000
1100100000000101
1100100011111010
1100100111101111
1100101011100100
1100101111011001
1100110011001110
1100110111000011
1100111010111000
1100111110101101
1101000010100010
1101000110010111
1101001010001100
1101001110000001
1101010001110110
1101010101101011
1101011001100000
1101011101010101
1101100001001010
1101100100111111
1101101000110100
1101101100101001
1101110000011110
1101110100010011
1101111000001000
1101111011111101
1101111111110010
1110000011100111
1110000111011100
1110001011010001
1110001111000110
1110010010111011
1110010110110000
1110011010100101
1110011110011010
1110100010001111
1110100110000100
1110101001111001
1110101101101110
1110110001100011
1110110101011000
1110111001001101
1110111101000010
1111000000110111
1111000100101100
1111001000100001
1111001101111011
1111111110110111
Giorgio Vecchi
>
> "Dario Uri" dice
>
> > Cosa succede se la libreria fosse invece generata in codice Gray ?
> > Non lo so, ma mi piacerebbe se qualcuno verificasse....
> >
>
> A me Gray ricorda solo l'unità di misura della dose di radiazione
> ionizzante assorbita....
> Ciao, Nino
>
Figurati che a me ricorda solo il nome di una cera per pavimenti! Però sono
andato a vedere di cosa si tratta. E' interessante, potete guardare qui:
http://www.nist.gov/dads/HTML/graycode.html .
Ho provato a infilarlo nel mio programma, ma le cose non migliorano, anzi
peggiorano. Ma
ormai non è più questo il punto. Il risultato di Nino, io non lo raggiungo
più! :-)
Ciao :-)
Giorgio
Nino
"Livio Zucca" ha scritto nel messaggio
>
> Sono basito! Non ci posso credere!
> Nino batte computer... alla grande!
>
>
Ringrazio tutti dei complimenti, ma il risultato
non deve meravigliare, in questo campo è normale
battere la macchina, se non è istruita bene....
D'altronde, come sistemista di bi- e tri-ridotti
sono veramente scarso e non mi sembra di aver fatto
un'opera d'arte ;-)
Per fortuna, in questo NG non bazzicano specialisti
come F. Santisi e F. Di Pasquale, che saprebbero
certamente fare meglio.
Nino
Nino
"iant" ha scritto nel messaggio
>
> Quello che tu hai descritto, e' il metodo che in ottimizzazione e'
> noto come metodo "greedy" (goloso). In pratica tu ad ogni passo
> cerchi di fare il meglio che puoi, e cioe' ottimizzi su scala locale.
>
> Purtroppo questo metodo non ti garantisce di trovare l'ottimo
> globale. (Diro' di piu': potrai trovare il ridotto ottimo globale
> in questo modo solo nei casi in cui esiste il ridotto perfetto che,
> per definizione, e' quello in cui non c'e' sovrapposizione tra le
> word cancellate dalle diverse word del ridotto.)
>
> In tutti gli altri casi puo' facilmente succedere che una serie
> casuale di k word cancelli piu' word delle k word "migliori" in
> senso greedy. Questa e' in generale la scoperta piu' fastidiosa
> che si fa quando ci si imbatte nella ricerca al computer
> di sistemi ridotti! ;-)
>
Per migliorare le cose, si possono abbinare i due metodi (cioè
iniziare a cancellare scegliendo un certo numero di word "migliori",
e poi proseguire a completare la copertura con la scelta casuale).
In certe circostanze ho utilizzato questo criterio per la riduzione
di sistemi Totogol (ove l'approccio pensato è molto più difficile
e complesso, visti i numeri molto più alti rispetto al Totocalcio
che sono in gioco), ottenendo spesso risultati apprezzabili.
In pratica, si potrebbe fermarsi al 80 -90% della copertura ottimizzata
(mettendo da parte le X colonne necessarie) e chiudere il rimanente
con la scelta casuale (che per agganciare il 10% utilizzerà praticamente
uno stesso numero X di colonne).
Una volta sommate, le colonne totali daranno il riduttore di partenza,
che potrà essere ulteriormente manipolato e migliorato operando
successive compressioni (per queste operazioni, si potranno selezionare
le colonne più significative, che agganciano , con una sola vincita,
almeno un determinato numero di colonne; quindi, verificare rispetto a
questo gruppo, quali sono le colonne scoperte del sistema integrale e
procedere alla riduzione casuale di queste ultime; ecc. ecc..
I probabili miglioramenti successivi sono dovuti al fatto che si
manipolano mano a mano gruppi sempre più piccoli di colonne, sui quali
la riduzione ottimizzata casuale risulta sempre più veloce ed efficiente).
> Detto questo, dopo molti tentativi ed esperienze fatte in passato,
> il metodo che mi ha fatto trovare le soluzioni migliori (di gran
> lunga migliori rispetto al greedy) e' stato quello di applicare un
> algoritmo genetico, che per sua natura opera su scala globale,
> esplora in modo casuale lo spazio delle soluzioni e "sfrutta" le
> migliori soluzioni trovate per costruirne altre potenzialmente
> migliori.
>
Penso sia un metodo sicuramente efficace, anche se le mie scarse
conoscenze non mi consentono di afferrare il meccanismo pratico di
esecuzione. Dubito infine, almeno per quanto attiene la specie umana,
che questa filosofia abbia sempre a condurre ad una evoluzione....
Ciao, Nino
Dario Uri
> http://www.nist.gov/dads/HTML/graycode.html .
> Ho provato a infilarlo nel mio programma, ma le cose non migliorano, anzi
> peggiorano. Ma
> piů! :-)
Piu' che battere record e' una mia curiosita', ad intuito ci dovrebbe
essere una regolarita' nella posizione del gruppo di colonne che formano
un riduttore in una libreria di stringhe generate con un criterio che
tenga presente la distrubuzione dei segni. Allora ho fatto una prova
all'incontrario. Ho generato (col metodo riflesso) le 128 7-tuple di 2^7
in un codice Gray, poi sono andato a vedere che posizione occupano le 16
stringhe del classico riduttore n-1 di 7 doppie... Sorpresa!? vediamo:
0000000 -A
0000001
0000011 ---B
0000010
0000110
0000111
0000101
0000100
0001100 ---B ***
0001101 ***
0001111 -A
0001110
0001010
0001011
0001001
0001000
0011000
0011001 -A
0011011
0011010 ---B
0011110
0011111
0011101
0011100
0010100
0010101 ---B
0010111
0010110 -A
0010010
0010011
0010001
0010000
0110000 ---B
0110001
0110011 -A
0110010
0110110
0110111
0110101
0110100
0111100 -A
0111101
0111111 ---B
0111110
0111010
0111011
0111001
0111000
0101000
0101001 ---B
0101011 ***
0101010 ***
0101110
0101111
0101101
0101100
0100100
0100101 -A
0100111
0100110 ---B
0100010
0100011
0100001
0100000
1100000
1100001
1100011
1100010
1100110 -A
1100111
1100101 ---B
1100100
1101100
1101101
1101111
1101110
1101010 ---B
1101011
1101001 -A
1101000
1111000
1111001
1111011
1111010
1111110
1111111 -A
1111101
1111100 ---B
1110100
1110101
1110111
1110110
1110010
1110011 ---B
1110001 ***
1110000 -A ***
1010000
1010001
1010011
1010010
1010110 ---B ***
1010111 ***
1010101 -A
1010100
1011100
1011101
1011111
1011110
1011010 -A
1011011
1011001 ---B
1011000
1001000
1001001
1001011
1001010
1001110
1001111 ---B
1001101
1001100 -A
1000100
1000101
1000111
1000110
1000010
1000011 -A
1000001
1000000 ---B
Ho scelto a caso 2 dei classici riduttori di 7 doppie.
Il primo riduttore e' segnato come A, i salti (contando le words
comprese fra queste) sono 9,6,9,6,5,10,5,10,9,6,9,6,5,10,5
Nel secondo riduttore B, si contano: 5,10,5,6,9,6,9,10,5,10,5,6,9,6,9 il
palindromo di quella sopra!
Gli asterischi invece intercettano le 8 stringhe di un biridotto.
Bhe' una certa regolarita' c'e'.
iant
>
>"Livio Zucca" ha scritto nel messaggio
>>
>> Sono basito! Non ci posso credere!
>> Nino batte computer... alla grande!
>>
>>
>
>Ringrazio tutti dei complimenti, ma il risultato
>non deve meravigliare, in questo campo è normale
>battere la macchina, se non è istruita bene....
Nino, sono lieto di annunciarti che, partendo dalla tua soluzione,
il mio programma e' stato in grado di spingere un pelino piu' in la'
l'attuale record.
A mio modo di vedere, questa e' una degli migliori conferme di
quanto sostieni: occorre istruire bene la macchina!
Il nuovo record e':
16 256
15 4096
14 25872
13 35312
Vincita media 13.531494
Il nuovo ridotto si ottiene dal tuo sostituendo due sole colonne:
1001011100000010 con 1001011110000011 e
0000110101100100 con 0000100101100101
Pertanto, se sei d'accordo, direi che la paternita' di questo
record e' 254/256 tua e 2/256 mia ;-)))
Un caro saluto,
iant
Nino
"iant" dice
>
> Nino, sono lieto di annunciarti che, partendo dalla tua soluzione,
> il mio programma e' stato in grado di spingere un pelino piu' in la'
> l'attuale record.
>
Bravo! Ero certo che si potesse migliorare la vincita media.
>
> Il nuovo record e':
>
> 16 256
> 15 4096
> 14 25872
> 13 35312
>
> Vincita media 13.531494
>
Penso che, insistendo un po', si possa alzare ancora, verso 13,55.
In quanto tempo il tuo programma ha ottenuto il record?
> Il nuovo ridotto si ottiene dal tuo sostituendo due sole colonne:
>
> 1001011100000010 con 1001011110000011 e
> 0000110101100100 con 0000100101100101
>
Ho dato un'occhiata a queste due nuove colonne, ma non ho assolutamente
capito i motivi ed il vantaggio della sostituzione; ovviamente, mi
adeguo e, a questo punto, per simmetria, potrebbero essere cambiate
almeno altre 3 coppie di colonne.
Credo che il tuo programma sia molto efficiente, senz'altro più valido
di tanti prodotti che sono in circolazione. Non hai mai pensato di
proporlo sul mercato? (purtroppo, il mercato sulla sistemistica è
ormai inflazionato, anche se di programmi non solo belli, ma anche
forniti di mezzi efficaci per la riduzione ce ne sono pochissimi...
mi viene in mente solo Ferlaino e Fabiani.)
> Pertanto, se sei d'accordo, direi che la paternita' di questo
> record e' 254/256 tua e 2/256 mia ;-)))
>
Facciamo metà per uno, va bene? ;-))
Ciao, Nino
iant
Nino ha scritto:
>
>Penso che, insistendo un po', si possa alzare ancora, verso 13,55.
Io insisto!
Ho la fortuna di avere a disposizione un PC (Pentium III 333MHz)
che deve rimanere acceso per erogare servizi che usano pochissimo
la CPU, e quindi posso lasciare il mio programma a girare piu' o
meno indefinitamente.
>In quanto tempo il tuo programma ha ottenuto il record?
Il record e' stato ottenuto in circa 13 ore. Da allora ne sono
passate altre 32 senza miglioramenti...
>> Il nuovo ridotto si ottiene dal tuo sostituendo due sole colonne:
>[...]
>a questo punto, per simmetria, potrebbero essere cambiate
>almeno altre 3 coppie di colonne.
Se mi dici quali colonne cambiare e come cambiarle posso poi
valutare la vincita media e vedere se costituisce un ulteriore
miglioramento.
Naturalmente se vuoi posso spedirti per posta il programma che fa
il calcolo della vincita media, cosi' puoi fare tutte le prove che
vuoi! a...@libero.it e' il tuo vero indirizzo?
>Credo che il tuo programma sia molto efficiente, senz'altro più
>valido di tanti prodotti che sono in circolazione.
> Non hai mai pensato di proporlo sul mercato?
No, non ho mai pensato di proporlo sul mercato. L'ho scritto 6-7
anni fa per diletto personale e credo sia giusto farlo rimanere
in quell'ambito. Oltretutto essendo basato su un metodo non
deterministico, non sarebbe possibile dare alcuna garanzia a priori
sul risultato, e questo lo rende improponibile sul mercato.
Ti ringrazio comunque per l'apprezzamento!
A presto,
iant
Nino
"iant" dice
>
> Se mi dici quali colonne cambiare e come cambiarle posso poi
> valutare la vincita media e vedere se costituisce un ulteriore
> miglioramento.
>
Le 256 colonne del mio sistema avevano una distribuzione totale di
segni 1 e 0 esattamente uguale (2048 ciascuno). Questo equilibrio
è stato alterato da una delle due colonne sostituite dal tuo
programma (una colonna con dieci 0 e sei 1 è stata cambiata con
una colonna con otto 1 e otto 0). Si potrebbe allora (ma non
scommetterei un euro sulla bontà di questo tentativo) provare a
ripristinare questo equilibrio di segni modificando le due colonne
complementari alle precedenti, e cioè:
0110100011110101 con 0110100001110100 e
1111001010010011 con 1111011010010010
> Naturalmente se vuoi posso spedirti per posta il programma che fa
> il calcolo della vincita media, cosi' puoi fare tutte le prove che
> vuoi! a...@libero.it e' il tuo vero indirizzo?
>
Ti ringrazio, mi farebbe molto piacere averlo (specialmente se accetta
l'inserimento di un numero variabile di bit, e non solo 16).
Il mio vero indirizzo è anas...@libero.it o anche anas...@tin.it
> No, non ho mai pensato di proporlo sul mercato. L'ho scritto 6-7
> anni fa per diletto personale e credo sia giusto farlo rimanere
> in quell'ambito. Oltretutto essendo basato su un metodo non
> deterministico, non sarebbe possibile dare alcuna garanzia a priori
> sul risultato, e questo lo rende improponibile sul mercato.
>
> Ti ringrazio comunque per l'apprezzamento!
>
Peccato, inserendo primati esistenti potrebbe magari migliorarne
qualcuno (ricordandosi sempre di mettere la paternità congiunta
con il precedente detentore ;-))
Saluti tristi (per la clamorosa sconfitta del Milan)
Nino
iant
>
>[...] Si potrebbe allora (ma non
>scommetterei un euro sulla bontà di questo tentativo) provare a
>ripristinare questo equilibrio di segni modificando le due colonne
>complementari alle precedenti, e cioè:
>0110100011110101 con 0110100001110100 e
>1111001010010011 con 1111011010010010
E invece avresti dovuto scommettere sul tuo intuito sistemistico.
E ben piu' di un euro!!!
16 256
15 4096
14 25888
13 35296
Vincita media 13.531738 Grandissimo!
Nel frattempo, durante la notte il mio programma aveva trovato
un miglioramento con media di 13.531616 modificando una colonna:
0101101100001101 con 0101101110001100
Mettendo insieme questo miglioramento con il tuo, siamo arrivati
a questo nuovo record:
16 256
15 4096
14 25896
13 35288
Vincita media 13.531860
Facciamo sempre fifty-fifty? ;-)
Ho notato che le colonne che producono miglioramenti abbassano
sempre esattamente di 8 il numero di colonne con punteggio 13
facedole passare a punteggio 14. Tu che sei un teorico hai una
possibile spiegazione? Il fatto che il miglioramento sia proprio
una potenza di 2 puo' essere solo un caso?
>> Naturalmente se vuoi posso spedirti per posta il programma [...]
>
>Ti ringrazio, mi farebbe molto piacere averlo [...]
OK, te lo mando in giornata. Giusto il tempo di renderlo un po'
piu' amichevole... :-)
>> No, non ho mai pensato di proporlo sul mercato [...]
>
>Peccato, inserendo primati esistenti potrebbe magari migliorarne
>qualcuno (ricordandosi sempre di mettere la paternità congiunta
>con il precedente detentore ;-))
Quello si puo' sempre fare nell'ambito del diletto.
Solo che io ho sempre trovato siti che indicavano i risultati
ottenibili con i ridotti record, e mai IL ridotto in se'.
Se per caso tu ne hai sottomano qualcuno... ;-)
(Io sono piu' interessato ai ridotti tipo Totogol o SuperEnalotto
cioe' legati a concorsi del tipo "indovina k numeri su un totale
di n", che trovo matematicamente piu' affascinanti del Totocalcio.)
Saluti,
iant
Dario Uri
o... ;-)
>
> (Io sono piu' interessato ai ridotti tipo Totogol o SuperEnalotto
> cioe' legati a concorsi del tipo "indovina k numeri su un totale
> di n", che trovo matematicamente piu' affascinanti del Totocalcio.)
In questo caso si parla di "Covering Design" ecco alcuni siti che
tengono i migliori risultati finora conseguiti:
http://www.ccrwest.org/cover.html
http://www.xs4all.nl/~rbelic/mainpage.htm
http://www.algonet.se/~peteros/index.htm
http://mladenmalik.www1.50megs.com/wheels7.html
Nino
"iant" ha scritto
>
> Ho notato che le colonne che producono miglioramenti abbassano
> sempre esattamente di 8 il numero di colonne con punteggio 13
> facedole passare a punteggio 14. Tu che sei un teorico hai una
> possibile spiegazione? Il fatto che il miglioramento sia proprio
> una potenza di 2 puo' essere solo un caso?
>
Certamente no! Dall'esame dei vari punteggi realizzati si rileva che
la rappresentatività è massima solo fino al 15 (R. teorico e pratico
=16). Per il 14, ad un aggancio teorico di 120 per colonna, il
risultato pratico è poco superiore a 101. Lo spettro di rappresentatività
in questo caso è variabile, in quanto alcune colonne (con differenza
di segni pari a 5) raggiungono il massimo, mentre quelle con differenza
di 4 segni hanno sovrapposizioni per la vincita del 14.
Per aumentare la vincita media occorre scovare le colonne a minore
significatività e sostituirle con altre più rappresentative.
Dalla struttura del sistema ridotto (che è diviso in 3 parti di
6/6/4 bit) si nota che le colonne finora sostituite per alzare la
vincita media riguardano la modifica di un bit nella sezione da 6
e di un bit nella sezione da 4 bit; quindi, i segni rimasti inalterati
in queste due sezioni sono 5 + 3 = 8 e questo è il guadagno dell'aggancio
per la vincita biridotta (almeno, credo che questa potrebbe essere la
spiegazione).
> Solo che io ho sempre trovato siti che indicavano i risultati
> ottenibili con i ridotti record, e mai IL ridotto in se'.
> Se per caso tu ne hai sottomano qualcuno... ;-)
>
Se è per questo, io ho in archivio praticamente tutti i primati assoluti
(almeno aggiornati al 2000), sia per il totocalcio (in formato .col),
sia per totogol e enalotto (nei formati .stg e .st6). A mio figlio
ho fatto realizzare programmini per convertire questi formati in testo.
Per il totocalcio dispongo anche di decine di primati miei a correzione
di errori n-1. Per correttezza, devo dire che buona parte dei primati
totogol e super-enalotto (alcuni sono stati nel frattempo superati)
sono opera di altri autori. Se vuoi, ti posso inviare qualche sviluppo.
> (Io sono piu' interessato ai ridotti tipo Totogol o SuperEnalotto
> cioe' legati a concorsi del tipo "indovina k numeri su un totale
> di n", che trovo matematicamente piu' affascinanti del Totocalcio.)
Dal punto di vista matematico non mi esprimo. Invece, come tipo di
gioco e convenienza pratica, secondo me, non c'è partita (a favore
del totocalcio). Non ti sei mai chiesto perchè questi giochi casuali
(lotto in primis) furoreggiano? A parte lo specchietto per le allodole
del premio elevatissimo (e immorale...), è perchè per "dare i numeri"
non occorre fatica ed approfondimento, e, in questo campo, Einstein e
lo scemo del villaggio sono sullo stesso piano.
Un po' come il successo per "Affari tuoi" di Bonolis.
Nel frattempo, ho effettuato queste altre sostituzioni:
1010010011111010 con 1010010001111011
0011111010011100 con 0011101010011101
1100000101101011 con 1100010101101010
e la vincita media diventa 13,532227.
Ho provato altre modifiche, ma mentre la vincita media aumenta, non
resta più la garanzia minima del 13.
Ciao a tutti e Buona Pasqua
Nino
iant
>Dalla struttura del sistema ridotto (che è diviso in 3 parti di
>6/6/4 bit) si nota che le colonne finora sostituite per alzare la
>vincita media riguardano la modifica di un bit nella sezione da 6
>e di un bit nella sezione da 4 bit; quindi, i segni rimasti inalterati
>in queste due sezioni sono 5 + 3 = 8 e questo è il guadagno dell'aggancio
>per la vincita biridotta (almeno, credo che questa potrebbe essere la
>spiegazione).
Mmmm. Credo di non aver capito il nesso tra i bit invariati e i
miglioramenti ottenuti... Comunque l'ultima sostituzione che e'
stata trovata dal mio programmino ha ottenuto un miglioramento
di 4 e non di 8 (sempre una potenza di 2, in ogni caso).
>[...] Se vuoi, ti posso inviare qualche sviluppo.
Mi farebbe molto piacere. (Soprattutto i ridotti e biridotti
assoluti del totogol.)
>[...] Invece, come tipo di gioco e convenienza pratica, secondo me,
> non c'è partita (a favore del totocalcio).
Secondo me il totogol e' leggermente meglio, perche'
1. C'e' la possibilita' di fare un pronostico in quanto l'uscita dei
vari segni NON e' equiprobabile (per via del regolamento), e ci
sono squadre oggettivamente piu' "gollose" (attacchi forti e/o
difese deboli)
2. Le vincite medie sono solitamente superiori.
E' quindi un modo migliore (anzi, "meno peggiore" ;-) di rischiare i
propri soldi.
>Non ti sei mai chiesto perchè questi giochi casuali
>(lotto in primis) furoreggiano? A parte lo specchietto per le allodole
>del premio elevatissimo (e immorale...), è perchè per "dare i numeri"
>non occorre fatica ed approfondimento, e, in questo campo, Einstein e
>lo scemo del villaggio sono sullo stesso piano.
Sono d'accordissimo con te. Con buona pace di ritardisti e affini.
>Nel frattempo, ho effettuato queste altre sostituzioni:
>1010010011111010 con 1010010001111011
>0011111010011100 con 0011101010011101
>1100000101101011 con 1100010101101010
>e la vincita media diventa 13,532227.
Ho applicato le sostituzioni al record in mio possesso e ho ottenuto
13.532211 anziche' 13,532227, quindi c'e' qualche altra colonna
diversa tra il tuo e il mio. Potresti postare il tuo record?
Ciao e buone feste anche a te,
iant
iant
>>[...] concorsi del tipo "indovina k numeri su un totale di n"
>
>In questo caso si parla di "Covering Design" ecco alcuni siti che
>tengono i migliori risultati finora conseguiti:
>
>http://www.ccrwest.org/cover.html
>http://www.xs4all.nl/~rbelic/mainpage.htm
>http://www.algonet.se/~peteros/index.htm
>http://mladenmalik.www1.50megs.com/wheels7.html
Era da un paio d'anni che non andavo a vedere quei siti. In
particolare l'ultimo non lo conoscevo proprio, e proprio li' ci
sono molti ridotti disponibili per il download.
Grazie per le segnalazioni!
Ciao,
iant
Dario Uri
Iant,
Anche in algonet ci sono molti sistemi scaricabili, basta cliccare nei
bottoni numerati nella parte alta dello schermo.
L'archivio disponibile piu' fornito, pero' e' a La Jolla, l'universita'
di San Diego, (primo sito) ma in questo momento sembra non connettersi.
ciao
Nino
"iant" ha scritto
>
> Ho applicato le sostituzioni al record in mio possesso e ho ottenuto
> 13.532211 anziche' 13,532227, quindi c'e' qualche altra colonna
> diversa tra il tuo e il mio. Potresti postare il tuo record?
>
0000000000000000
1111011010010010
1111000101011100
1111000101010011
1111001001101100
1111001001100011
1111000110101100
1111000110100011
1100111010011100
1100111010010011
1100110101011100
1100110101010011
1100111001101100
1100111001100011
1100110110101100
1100110110100011
0011101010011101
0011111010010011
0011110101011100
0011110101010011
0011111001101100
0011111001100011
0011110110101100
0011110110100011
1010101010100001
1010101010101110
1010100101100001
1010100101101110
1010101001010001
1010101001011110
1010100110010001
1010100110011110
0101101010100001
0101100000111101
0101101100000010
0101101110001100
0101100011000010
0101100011001101
1001011111110010
1001011111111101
1001010000110010
1001010000111101
1001011110000011
0011000000110111
0011001100001000
0011001100000111
0011000011001000
0011000011000111
1111111010100100
1111111010101011
1111110101100100
1111110101101011
1111111001010100
1111111001011011
1111110110010100
1111110110011011
0000111010100100
0000111010101011
0000100101100101
0000110101101011
0000111001010100
0000111001011011
0000110110010100
0000110110011011
1100001010100100
1100001010101011
1100000101100100
1100010101101010
1100001001010100
1100001001011011
1100000110010100
1100000110011011
0011001010100100
0011001010101011
0011000101100100
0011000101101011
0011001001010100
0011001001011011
0011000110010100
0011000110011011
1010010000001010
1010010000000101
1010011111001010
1010011111000101
1010011100111010
1010011100110101
1010010001111011
1010010011110101
0101010000001010
0101010000000101
0101011111001010
0101011111000101
0101011100111010
0101011100110101
0101010011111010
0101010011110101
1001100000001010
1001100000000101
1001101111001010
1001101111000101
1001101100111010
1001101100110101
1001100011111010
1001100011110101
0110100000001010
0110100000000101
0110101111001010
0110101111000101
0110101100111010
0110101100110101
0110100011111010
0110100001110100
1010011010011001
1010011010010110
1010010101011001
1010010101010110
1010011001101001
1010011001100110
1010010110101001
1010010110100110
0101011010011001
0101011010010110
0101010101011001
0101010101010110
0101011001101001
0101011001100110
0101010110101001
0101010110100110
1001101010011001
1001101010010110
1001100101011001
1001100101010110
1001101001101001
1001101001100110
1001100110101001
1001100110100110
0110101010011001
0110101010010110
0110100101011001
0110100101010110
0110101001101001
0110101001100110
0110100110101001
0110100110100110
Come vedi, ho tolto la tua ultima 0110101010011111
che sembra peggiorare un po' la vincita media.
Per le altre tue domande e osservazioni, a domani
Ciao, Nino
Nino
"iant" dice:
>
> Mmmm. Credo di non aver capito il nesso tra i bit invariati e i
> miglioramenti ottenuti... Comunque l'ultima sostituzione che e'
> stata trovata dal mio programmino ha ottenuto un miglioramento
> di 4 e non di 8 (sempre una potenza di 2, in ogni caso).
>
Se osservi bene, quest'ultima colonnina ha due segni diversi, rispetto
alla colonna che sostituisce, soltanto in una sezione (l'ultima di
4 bit).
> >[...] Se vuoi, ti posso inviare qualche sviluppo.
>
> Mi farebbe molto piacere. (Soprattutto i ridotti e biridotti
> assoluti del totogol.)
>
Ho provveduto a inviartene qualcuno al tuo indirizzo.
> >[...] Invece, come tipo di gioco e convenienza pratica, secondo me,
> > non c'è partita (a favore del totocalcio).
>
> Secondo me il totogol e' leggermente meglio, perche'
>
> 1. C'e' la possibilita' di fare un pronostico in quanto l'uscita dei
> vari segni NON e' equiprobabile (per via del regolamento), e ci
> sono squadre oggettivamente piu' "gollose" (attacchi forti e/o
> difese deboli)
>
Il totogol è a metà strada fra i giochi intelligenti (totocalcio)
e quelli stupidi (super-enalotto). In effetti, è possibile un minimo
di pronostico, sicuramente però meno affidabile che per il totocalcio.
Ho fatto una macro Excel che, esaminando i risultati passati, fornisce
una classifica delle varie partite del concorso, ordinandole secondo
la loro probabilità di fare gol. Normalmente, sulle prime 11 partite
indicate come più probabili, 4-5 rientrano nell'ottina vincente.
> 2. Le vincite medie sono solitamente superiori.
>
Semplicemente perchè è più difficile vincere l'8 (10 milioni di casi
contro 1,5 milioni del vecchio 13 totocalcio). E anche perchè il
pronostico è poco importante, e il fatto che il totogol sia un gioco
più aleatorio che di abilità lo dimostra la sostanziale stabilità
delle quote di vincita (specie per il 7 e il 6), che sono valutabili
con buona approssimazione a priori.
> E' quindi un modo migliore (anzi, "meno peggiore" ;-) di rischiare i
> propri soldi.
Non sono assolutamente d'accordo, l'unico gioco in cui si può
competere sperando a lungo termine di non perdere è il totocalcio,
che consente di bilanciare l'handicap dell'iniquità del montepremi
con lo studio dei picchetti tecnico e giocato, scommettendo contro
la concentrazione delle giocate dei partecipanti.
> >Non ti sei mai chiesto perchè questi giochi casuali
> >(lotto in primis) furoreggiano? A parte lo specchietto per le allodole
> >del premio elevatissimo (e immorale...), è perchè per "dare i numeri"
> >non occorre fatica ed approfondimento, e, in questo campo, Einstein e
> >lo scemo del villaggio sono sullo stesso piano.
>
> Sono d'accordissimo con te. Con buona pace di ritardisti e affini.
>
Paradossalmente, potrei considerarmi anch'io un po' affine ;-)
Ciao, Nino
iant
>> E' quindi un modo migliore (anzi, "meno peggiore" ;-) di
>> rischiare i propri soldi.
>
>Non sono assolutamente d'accordo, l'unico gioco in cui si può
>competere sperando a lungo termine di non perdere è il totocalcio,
>che consente di bilanciare l'handicap dell'iniquità del montepremi
>con lo studio dei picchetti tecnico e giocato, scommettendo contro
>la concentrazione delle giocate dei partecipanti.
Non mi voglio sbilanciare. Sicuramente la tua valutazione e' piu'
ponderata della mia. Istintivamente mi viene da pensare che, grazie
al maggior livello delle vincite, la speranza matematica del totogol
sia superiore a quella del totocalcio, pero' non ho mai avuto lo
stimolo per fare calcoli precisi.
>> >per "dare i numeri"
>> >non occorre fatica ed approfondimento, e, in questo campo, Einstein e
>> >lo scemo del villaggio sono sullo stesso piano.
>>
>> Sono d'accordissimo con te. Con buona pace di ritardisti e affini.
>
>Paradossalmente, potrei considerarmi anch'io un po' affine ;-)
Lungi da me iniziare uno di quei periodici, inutili e noiosi thread
sui ritardi nel lotto, che alla fine non riescono a convincere chi
non si riesce a convincere da solo che i numeri non hanno memoria,
e di contro avvelenano il clima nel newsgroup.
Mi fa pero' piacere leggere quel "paradossalmente" tra le tue parole!
;-))
Un caro saluto,
iant
iant
>"iant" <ia...@libero.nospam.it> ha scritto:
>
>> Darwin Machine??? Intendi con quel termine l'implementazione
>> di un algoritmo genetico? Allora non sono l'unico pazzo!!! ;-))
>
>
>Ne parlavo qua:
>http://www.geocities.com/liviozuc/darwin.html
>Fammi sapere se stiamo parlando di cose analoghe.
Ciao Livio. Ho letto il tuo articolo gia' diversi giorni fa, ma
solo ora ho avuto un po' di tempo per risponderti con calma.
Direi che di sicuro stiamo parlando di cose analoghe, cioe' di
metodi di ricerca guidati dall'introduzione di una componente
casuale nelle soluzioni che via via si esplorano.
Non credo pero' che stiamo parlando proprio della stessa cosa.
Per poter parlare di algoritmo evoluzionistico occorre infatti
capire in che modo si fa intervenire il caso nella ricerca della
soluzione, cioe' in che modo si prendono in prestito i meccanismi
della selezione naturale.
Sulle prime mi sembra che il metodo di cui parli tu sia un
metodo di ricerca casuale nello spazio delle soluzioni (noto
in letteratura come "Random Search"), e la selezione naturale
interviene solo nel fatto che si scelgono le soluzioni migliori.
Gli algoritmi genetici invece prendono a prestito anche i
meccanismi biologici che sono alla base della selezione naturale.
In particolare i meccanismi principali a cui mi riferisco sono 4:
a. Ogni individuo e' rappresentato solo ed esclusivamente dal
proprio DNA, relativamente alla possibilita' di tramandare
le proprie caratteristiche ai figli.
b. La bonta' di un DNA si verifica "sul campo". Cioe' se un DNA ha
generato un individuo adatto o inadatto lo decidera' solo la
relazione dell'individuo con l'ambiente e la pressione selettiva
da esso esercitata, e alla fine solo i piu' adatti sopravviveranno.
c. I caratteri degli individui piu' adatti vengono tramandati ai
figli mediante operazioni di incrocio (crossover) dei DNA dei
due genitori.
d. Esiste la possibilita' di mutazione di singoli elementi del DNA
che occasionalmente puo' far emergere individui con caratteri-
stiche diverse da quelle dei propri genitori, e che occasional-
mente puo' renderli piu' adatti alla sopravvivenza.
Detto questo, in due parole gli algoritmi genetici funzionano cosi':
1. Si istituisce un metodo di codifica delle soluzioni come
stringhe di bit, una sorta di "DNA", nel senso che data una
particolare stringa io ottengo una ben precisa soluzione
(e viceversa).
2. Si genera a caso una "popolazione", cioe' un insieme di stringhe
di bit che rispettino la codifica del punto 1.
3. Si decodificano le stringhe di bit generando le rispettive
soluzioni, e si valuta la bonta' di ciascuna di esse semplicemente
verificando il grado di soluzione che danno al problema. In gergo
si dice che si applica a tutti gli individui della popolazione
una "funzione di valutazione" (che e' quella da ottimizzare!).
4. Si selezionano le soluzioni migliori, diciamo A e B, e si generano
altre soluzioni mediante crossover tra i rispettivi DNA, cioe'
spezzando le due stringhe di bit in un punto e incrociandole. Es
A -> 110010101110
B -> 010101110011
le spezzo al quarto bit:
A -> 1100 10101110
B -> 0101 01110011
e genero due nuovi individui A' e B' effettuando il "crossover"
A' -> 1100 01110011
B' -> 0101 10101110
Siccome ogni bit rappresenta una certa caratteristica del genitore,
A' e B' avranno in se', mescolati, i caratteri dei genitori e forse
possono essere ancora piu' adatti a risolvere il problema.
L'operatore crossover, in sostanza, e' volto a creare
miglioramenti di soluzioni in prossimita' di quelle trovate
in precedenza, e quindi tende a trovare ottimi locali.
5. Occasionalmente una mutazione di uno o piu' bit (inversione di
valore 0-1) nella stringa di un individuo, puo' far si' che questo
abbia caratteristiche molto diverse dal genitore.
L'operatore mutazione e' volto a esplorare nuove porzioni dello
spazio di ricerca, e quindi tende a sbloccare il sistema dagli
ottimi locali.
Per dirla con il gergo dell'ottimizzazione, il metodo degli algoritmi
genetici ottiene un buon equilibrio tra "exploration" dello spazio di
ricerca ed "exploitation" delle buone soluzioni che via via si vanno
trovando.
Per una descrizione piu' approfondita e per esempi concreti di
applicazione basta cercare qualcosa con Google, la rete e' piena
di siti che parlano dell'argomento, ad esempio:
http://www.cs.colostate.edu/~genitor/MiscPubs/tutorial.pdf
Se vuoi posso anche mandarti via email un ebook di circa 6.5Mb
sull'argomento.
Sono sicuro che se sei rimasto sorpreso dai risultati della Random
Search, rimarrai stupefatto dall'applicazione degli algoritmi
genetici!
Un caro saluto,
iant
P.S.: Nello specifico del problema dei Gini, non e' necessario passare
alla codifica in quanto il problema e' gia' posto in termine di
stringhe di bit. E' quindi sufficiente generare una popolazione di
possibili ridotti e poi far evolvere quella popolazione con i
meccanismi che ti ho descritto.
Livio Zucca
>
> Direi che di sicuro stiamo parlando di cose analoghe, cioe' di
> metodi di ricerca guidati dall'introduzione di una componente
> casuale nelle soluzioni che via via si esplorano.
> Non credo pero' che stiamo parlando proprio della stessa cosa.
>
> Per poter parlare di algoritmo evoluzionistico occorre infatti
> capire in che modo si fa intervenire il caso nella ricerca della
> soluzione, cioe' in che modo si prendono in prestito i meccanismi
> della selezione naturale.
Mi fa piacere vedere che finalmente c'e' fermento sull'argomento.
IMHO tutti questi metodi si basano sul concetto clou del darwinismo
che possiamo sintetizzare con il ciclo:
A) Mutazione casuale
B) Selezione naturale
A supporto di questo concetto base possiamo cercare di rubare
alla natura altri meccanismi biologici, una volta che pero' ne abbiamo
compreso l'utilita' in un certo contesto e abbiamo speranze che
l'utilita' continui nel nostro contesto specifico.
Prendiamo ad esempio il meccanismo che chiami "crossover".
Che cosa rappresenta? Scimmiotta in qualche modo l'effetto che
in natura si ha con la riproduzione sessuata, metodo che e' stato
evidentemente favorito dall'evoluzione stessa essendo presente
(con numero sessi = 2) nella stragrande maggioranza delle specie
di una certa complessita', mentre la sua diffusione e' minore nelle
riproduzione di organismi relativamente semplici. (Ma quanto sono
relativamente semplici rispetto ad una nostra equazione?).
Per applicare quindi un tale metodo, mi farei prima alcune domande,
tipo "perche' le specie di una certa complessita' si riproducono
in modo sessuato?" e "perche i sessi sono sempre su base 2?"
(A parte un racconto di Isaac Asimov, non ho in mente alcuna
trattazione sulla possibilita' di una vita basata sulla triade anziche'
sulla coppia, sebbene in qualche caso dovrebbe pur avere qualche
vantaggio, forse con complessita' ancora maggiori).
L'unica risposta ragionevole che io abbia trovato alle domande
suddette e' che in natura c'e' il "rumore" che genera un certo
"tasso d'errore" nella "trasmissione" delle informazioni (DNA),
quello stesso rumore che genera l'invecchiamento. La riproduzione
sessuata con n=2 minimizza statisticamente l'effetto negativo del
rumore senza avere una grande ridondanza che ostacolerebbe la
mutazione casuale.
Se questa e' la risposta, allora c'e' da chiedersi che utilita' ci
darebbe una riproduzione sessuata (crossover) nella risoluzione
delle nostre equazioni, in cui la "trasmissione" e' cosi' pulita
che se vogliamo introdurre una mutazione, il rumore lo dobbiamo
fare noi.
Ciao!!! ((^__^))'
Livio
Paolo Licheri
"Livio Zucca"
> "perche' le specie di una certa complessita' si riproducono
> in modo sessuato?"
Evidentemente la Natura benigna ha voluto unire l'utile al dilettevole
:-)
ciao
paolo
iant
nel tuo messaggio hai scritto:
>
>IMHO tutti questi metodi si basano sul concetto clou del
>darwinismo che possiamo sintetizzare con il ciclo:
>
>A) Mutazione casuale
>B) Selezione naturale
Sintesi condivisibile sul piano qualitativo.
Pero' mi preme sottolineare che sul piano operativo non e' affatto
detto che ogni generica mutazione casuale che mi possa venire in mente
sia in grado di portare un'evoluzione solo per il fatto di essere
casuale. A mio avviso e' cruciale concentrarsi sul "come avviene
cio' che avviene", dopo aver capito "cosa avviene".
>A supporto di questo concetto base possiamo cercare di rubare
>alla natura altri meccanismi biologici, una volta che pero' ne
>abbiamo compreso l'utilita' in un certo contesto e abbiamo
>speranze che l'utilita' continui nel nostro contesto specifico.
Ma non esiste un <<nostro contesto specifico>> se ci poniamo
l'obiettivo di trovare una strategia *generale* per risolvere
problemi. O no?
>Prendiamo ad esempio il meccanismo che chiami "crossover".
>Che cosa rappresenta? Scimmiotta in qualche modo l'effetto che
>in natura si ha con la riproduzione sessuata, metodo che e' stato
>evidentemente favorito dall'evoluzione stessa essendo presente
>(con numero sessi = 2) nella stragrande maggioranza delle specie
>di una certa complessita'[...]
Non mi sembra una cosa da poco! Anche le strategie evolutive
sono state sottoposte alla selezione naturale. Mi sembra quindi
piuttosto sensato rivolgere l'attenzione alle strategie di
maggior successo, se si vuole trovare un buon metodo generale.
>Per applicare quindi un tale metodo, mi farei prima alcune domande,
>tipo "perche' le specie di una certa complessita' si riproducono
>in modo sessuato?"[...]
Io non sono un biologo, quindi non so darti una spiegazione
rigorosa, ma da quanto ho capito la riproduzione sessuata favorisce
una forma diversa di evoluzione rispetto alla semplice mutazione,
e cioe' lo scambio di patrimonio genetico diverso gia' sottoposto
a selezione, e quindi con buone probabilita' di essere portatore di
caratteristiche diverse, ciascuna gia' ben "collaudata", che possono
portare alla creazione di un individuo che si adatta meglio
all'ambiente.
>L'unica risposta ragionevole che io abbia trovato alle domande
>suddette e' che in natura c'e' il "rumore" [...]
>
>Se questa e' la risposta, allora c'e' da chiedersi che utilita' ci
>darebbe una riproduzione sessuata (crossover) nella risoluzione
>delle nostre equazioni, in cui la "trasmissione" e' cosi' pulita
>che se vogliamo introdurre una mutazione, il rumore lo dobbiamo
>fare noi.
Dal punto di vista algoritmico l'utilita' del crossover e' quella
di far si' che due soluzioni localmente buone possano generare una
soluzione globalmente buona.
(Se hai la pazienza di leggere il tutorial di cui ti ho dato il link,
troverai anche il cosiddetto teorema dello Schema, che fornisce una
spiegazione matematica del come e del perche' il crossover riesce ad
essere efficace).
A titolo di esempio, nel problema dei Gini se tu hai due ridotti che
coprono bene due parti diverse del sistema integrale e li incroci tra
loro, e' possibile che i ridotti emergenti coprano l'integrale meglio
dei due da cui provenivano. E questo puo' avvenire molto piu'
rapidamente che non aspettando mutazioni casuali che portino un buon
ridotto a migliorare.
Come ti dicevo nel post precedente, gli AG realizzano una strategia
mista di grande efficacia tra lo sfruttamento delle buone soluzioni
che si vanno via via trovando, grazie al crossover, e l'esplorazione
incessante dello spazio di ricerca, grazie alla mutazione.
Nella mia esperienza personale l'usuale andamento dell'evoluzione di
un AG e' questo: all'inizio si trovano molte soluzioni che evolvono
rapidamente ed e' la fase in cui agisce molto il crossover. Poi ci
sono delle fasi di stasi in cui gli incroci non portano miglioramenti
(minimi locali), ed e' in queste fasi che l'unica possibilita' di
miglioramento e' affidata alla mutazione che e' in grado di portare
in una zona non esplorata in precedenza. Non appena viene trovata una
soluzione migliore se ne trovano subito in rapida sequenza delle altre
perche' rientra in gioco il crossover e cosi' via. Naturalmente
l'andamento dell'evoluzione tende a diventare sempre piu' lento man
mano che le soluzioni trovate migliorano, e i miglioramenti stessi
sono sempre piu' lievi.
Spero di aver almeno in parte risposto alle tue perplessita'...
A presto,
iant