Algoritmo ubriaco

In questi giorni, oltre al racconto di Strabuccino che procede stralentissimamente, sto continuando a inserire dati nel programma delle epigrafi, ad aggiungervi funzionalità e a correggere bachi.

Ieri mi sono appunto concentrato sul correggere un problema, non proprio un baco perché funzionava, e in altri piccoli miglioramenti.

Il problema era alla creazione di nuove “Entità” (che è il brutto nome che ho scelto per indicare gli oggetti che contengono un’intera serie di associazioni epigrafi x capitolo (*1)): la creazione era casuale e, solo una volta terminata, verificavo se fosse accettabile o no. Se non era valida (ovvero se la stessa epigrafe veniva usata per più capitoli) ripartivo da capo. Mi rendevo conto che non era efficiente ma solo quando ho aggiunto il capitolo 12 (più o meno non ricordo esattamente) la lentezza si è fatta esasperante. All’epoca risolsi agendo sui dati: inserendo delle epigrafi vuote specifiche per ogni capitolo. In questa maniera la probabilità che casualmente venisse scelta una combinazione non valida diminuiva drasticamente.
Ovviamente io non voglio epigrafi vuote quando ve ne sono di buone ma ero fiducioso che l’algoritmo genetico le avrebbe fatte “emergere”. E in effetti sembrava funzionare.
Quando però ho inserito il capitolo 14 (e quindi anche il 13) il problema si è ripresentato: infatti non l’avevo risolto ma avevo semplicemente diminuito la probabilità che si verificasse.

Così mi sono deciso a cambiare il codice per far sì che venissero create solo “entità” valide.
A questo punto ho raccolto qualche statistica. Sfortunatamente quelle più vecchie non sono confrontabili perché basate su epigrafi per meno capitoli…

La prima prova del nuovo codice ha impiegato 1 minuto e 1 secondo, ha trovato una soluzione da 312.5 punti con ben 27 epigrafi vuote (FIT) associate ai capitoli.
Poi ho iniziato a rimuovere le epigrafi vuote (che spesso avevo aggiunto solo per rendere più improbabili combinazioni non valide ma che col nuovo algoritmo non erano più necessarie tranne alcuni casi speciali (*2)) e mi sono divertito a osservare i miglioramenti.
-1 (meno cioè le epigrafi vuote per il primo capitolo): 54s, 314.9 punti e 26 FIT.
-3 (e -2): 46s, 316.3 p., 25 FIT
-5 (e -4): 1m 1s, 318.9, 19 FIT
-7 e -6: 40s, 319.6, 23 FIT
-9 e -8: 46s, 316.6, 24 FIT
-11 e -10: 43s, 324.8, 21 FIT
-13 e -12: 38s, 320.8, 15 FIT
-14: 39s, 321.0, 14 FIT

Non male: la velocità è quasi triplicata e le soluzioni trovate tendono a migliorare leggermente. Apparentemente anche le epigrafi vuote sono appetibili: la mia ipotesi è che quando un epigrafe vuota prende il posto di un epigrafe valida ma che vale poco può comunque far scattare un bonus di 2 punti per l’epigrafe di un solo autore. Ok non si capisce, ecco un esempio: se ho due epigrafi di Russell di cui una vale 3 punti e un’altra 1 in totale ho 4 punti. Se però la seconda la sostituisco con un epigrafe vuota allora la prima prende un bonus di 2 punti come unica epigrafe di un autore: la prima va a valere così 3+2 punti (5) e anche se la seconda vale 0 in quanto vuota, il totale diviene 5 e non 4. Forse dovrei provare a ridurre tale bonus a 1 o forse a toglierlo del tutto, non so…

La seconda ottimizzazione non era tanto di pura efficienza quanto di logica del codice.
Un problema è infatti che elimino solamente le entità col punteggio minore: in questa maniera temevo di perdere delle singole associazioni buone ExC (epigrafe x capitolo) dando troppo “vantaggio” a quelle complessivamente migliori.
Allora ho attivato un filtro sull’età delle entità che del resto avevo già previsto: dopo 5 generazioni un’entità comunque viene eliminata.
Fatta la modifica ho eseguito 4 prove.
Il risultato migliore è stato:
38s, 324.7, 12 FIT
Mediamente:
40s, 322, 16 FIT

Insomma non ha impattato molto anche perché a causa della rapida crescita della popolazione (più o meno del 50% a ogni generazione) la quantità di entità che eliminavo a partire dalla sesta era molto piccola rispetto alla popolazione totale.

A questo punto ho aggiunto una ottimizzazione più drastica che permetta di rimettere in gioco associazioni non contenute da nessuno dei due genitori (v. anche il precedente Epigrafi genetiche).
Delle specie di “mutazioni” casuali, una o meno per ogni entità neonata, che mi avrebbe dovuto permettere di rimettere in gioco associazioni valide sparite dal “bacino genetico” esistente per qualsiasi motivo (magari perché presenti in un entità complessivamente scadente).
Ho fatto un unico esperimento il cui risultato non è stato particolarmente esaltante:
58s, 317.9 e 12 FIT.
L’incremento del tempo di generazione impatta notevolmente e, almeno in questo singolo tentativo, sembrerebbe che il risultato migliore trovato sia un po’ sotto la media.
Nonostante questo non ho minimamente pensato che fosse una cattiva modifica e, al contrario, ho pensato a una nuova ottimizzazione.

L’idea è quella di non eliminare solo le combinazioni peggiori (che potrebbero comunque contenere singole associazioni ExC valide) ma avere un qualcosa di più progressivo e, contemporaneamente aggressivo.
In pratica ho diviso tutte le entità in sei fasce basate su media dei punti e varianza.
Della fascia peggiore (con punteggio minore della media meno due volte la varianza) elimino i 6/7 delle entità, per quella successiva i 5/7, poi 4/7, 3/7, 2/7 e 1/7 per le migliori.
Insomma elimino un maggior numero complessivo di entità e lo faccio in maniera meno draconiana, non punendo cioè solo quelle col punteggio peggiore. Volendo introduco un po’ di sorte: anche una combinazione infelice se ha fortuna può sopravvivere e magari riprodursi così come una combinazione felice ma sfortunata può morire prematuramente.
Ecco i risultati di due prove:
5.8s, 313.7, 18 FIT e 9 G (generazioni)
6.0s, 320.6, 15 FIT, 9 G
Il tempo, che è proporzionale alla popolazione, è crollato a un decimo della precedente versione.
Anche la qualità della migliore soluzione trovata è diminuita ma non tantissimo.
Allora ho iniziato ad aumentare il numero di generazioni…
9.8s, 324.8, 14 FIT, 11G
9.5s, 321.9, 13 FIT, 11G
Con 11 generazioni, con 1/5 del tempo, riesco già a ottenere soluzioni di qualità analoga a quelle di prima di quest’ultima modifica!
Proviamo con 13 generazioni:
15.3s, 333.3, 16 FIT, 13G
15.8s, 330.5, 14 FIT, 13G
14.8s, 330.1, 14 FIT, 13G

Con tredici generazioni, e un terzo del tempo della precedente versione, ottengo soluzioni significativamente migliori!

Conclusione: non male: oggi ho ottenuto sia la botte piena che l’algoritmo ubriaco!

PS: Dopo pranzo non ho resistito alla tentazione di fare qualche altro esperimento. In particolare mi chiedevo, a parità di tempo, che punteggio avrei ottenuto?
Ho fatto delle prove e ho visto che con 17G avevo tempo di calcolo di 46.5s con soluzioni di punteggio intorno a 345!
Successivamente ho provato a usare il profilatore di NetBeans e ho scoperto che parecchio tempo veniva perso nel verificare che un oggetto appartenesse a un ArrayList: evidentemente veniva fatta una semplice scansione sequenziale. Così vi ho associato un HashSet e in questa maniera ho risparmiato un 30%, forse più!
Non sono sicuro perché nel frattempo avevo aggiunto il capitolo 15: comunque adesso, nonostante il capitolo extra, sempre per calcolare 17G impiega sui 39s, insomma significativamente meno di quando i capitoli erano 14!

Nota (*1): per capitolo intendo sia capitoli, che hanno fino a tre epigrafi associate, e sottocapitoli che ne hanno solo una.
Nota (*2): troppo complesso da spiegare qui!

Share