Gruppo di lavoro su Python e algoritmi genetici
Programma:
Gli algoritmi genetici permettono di affrontare problemi di ottimizzazione di alta complessità, tipicamente non lineare o polinomiale,
utilizzando il principio di "selezione del più adatto", ispirato alla teoria evoluzionistica di Darwin.
In questo moulo discuteremo le basi degli algoritmi genetici affrontando alcuni esempi specifici, di complessità via via crescente. Nello stesso tempo, introdurremo
alcuni moduli utili di Python, che sarà il linguaggio di programmazione utilizzato nel corso. Gli studenti dovranno poi cimentarsi in un caso
realistico, che verrà assegnato loro durante il corso, e portarne una presentazione/relazione individuale all'esame.
Orari secondo semestre 2022 (il corso si terrà nel nuovo Laboratorio di Calcolo, il Lunedì dalle 15.30 alle 18.30):
- Lunedì 2 Maggio: introduzione agli algoritmi genetici, loro funzionamento e basi. Teorema degli algoritmi genetici (referenze: Goldberg, Genetic algorithms in search, optimization and machine learning; Mitchell, An introduction to genetic algorithms).
Generazione numeri random e modulo random di Python.
- Lunedì 9 Maggio:
Esempio di codice per un algoritmo genetico.
Introduzione ad alcuni moduli/funzioni di Python utili per il corso: sys.argv,
argparse,
gestione errori del codice, in particolare try / except.
Buone pratiche di programmazione: documentazione Doxygen e
unit testing.
- Lunedì 16 Maggio:
Debugging del codice con
pdb (riassunto dei comandi utili).
Panoramica sui diversi tipi di crossover e loro applicazioni (alcuni appunti).
Il problema del venditore itinerante (travelling-salesman problem, TSP). Risoluzione tramite algoritmi genetici a cura degli studenti.
- Lunedì 23 Maggio:
Termine risoluzione problema del venditore itinerante.
Basi di crittografia per testi mono- e poli-alfabetica
(presentazione).
Implementazione di un modulo Python per la codifica e decodifica di testi usando i metodi presentati.
- Lunedì 30 Maggio: Utilizzo di base di git (si veda qui).
Warm-up: utilizzo degli algoritmi genetici per la decrittazione di testi
(tema d'esame 2021). Lavoro da parte degli studenti.
- Lunedì 6 Giugno: Assegnazione del tema di esame, formazione dei gruppi e inizio del lavoro da parte degli studenti.
Marco Zaro's homepage