Corso di Algoritmi e Strutture Dati(Soft Computing)

Nome piu attinente ai contenuti del corso:

(Algoritmi per il) Soft Computing

1

Docente:Leonardo Vanneschi

Ufficio n. 472, U7, quarto piano

email: vanneschi@disco.unimib.it

homepage: http://www.disco.unimib.it/vanneschi(al momento http://old.disco.unimib.it/Vanneschi)

L’email sara uno degli strumenti principali di comunicazione tra studenti e docenteper tutta la durata del corso, quindi, per favore, tutti gli studenti sono pregati diinviarmi una piccola email (vuota) in modo che io possa creare una specie di mailinglist. Altri mezzi per comunicare:

• Pagina web del corso.

• Pagina web del docente.

2

Contenuti della prima lezione

• Orario del corso.

• Testi consigliati.

• Modalita d’esame.

• Contenuti e motivazioni del corso.

• ...

3

Orario del corso

Orario delle lezioni:

• Martedi, ore 11:30 - 13:30, aula U1-06

• Giovedi, ore 9:30 - 11:30, aula U1-06

Esercitazioni:

• Martedi 21 novembre, ore 11:30 - 13:30, LAB 721, U7, 2o piano

• Martedi 28 novembre, ore 11:30 - 13:30, LAB 721, U7, 2o piano

• Martedi 5 dicembre, ore 11:30 - 13:30, LAB 721, U7, 2o piano

• Martedi 16 gennaio, ore 11:30 - 13:30, LAB 721, U7, 2o piano

• Martedi 23 gennaio, ore 11:30 - 13:30, LAB 721, U7, 2o piano

• Martedi 30 gennaio, ore 11:30 - 13:30, LAB 721, U7, 2o piano

4

Importante

Prima della prima esercitazione (che avverra martedi 21 novembre), verificare di:

• Avere accesso alle macchine dei LAB 721 (login e password).

• Poter compilare ed eseguire programmi scritti in Java oppure in C

(a scelta degli studenti).

5

Testi Consigliati

• “Soft Computing: Integrating Evolutionary, Neural and Fuzzy Systems”,A. Tettamanzi, M. TomassiniSpringerCollocazione in biblioteca: CCD 006.3 TETA.SOF/2001.

Introduzione generale per quasi tutti gli argomenti del corso. La lettura diquesto testo e necessaria, ma non sufficiente per superare l’esame.

• “Genetic Algorithms in Search, Optimization and Machine Learning”,D. E. GoldbergAddison-WesleyCollocazione in biblioteca: CCD 006.3 GOLD.GEN/1989.

Tratta la maggior parte degli argomenti che verranno presentati a lezione sugliAlgoritmi Genetici.

6

• “Genetic Programming, an Introduction”

W. Banzhaf, P. Nordin, R. E. Keller, F. D. Francone

Morgan Kauffmann

Collocazione in biblioteca: CCD 006.31 BANW.GEN/1998

Ottimo testo introduttivo alla Programmazione Genetica, ma non contiene tutto

cio che verra trattato durante il corso su questo argomento

• “An Introduction to Neural Networks”

K. Gurney

UCL Press

Presente in biblioteca

Tratta la maggior parte degli argomenti che verranno presentati a lezione sulle

Reti Neurali.

7

• “Simulated Annealing and Boltzmann Machines”E. Aarts, J. KorstJohn Wiley and SonsPresente in biblioteca.

Tratta la maggior parte degli argomenti che verranno presentati a lezione du-rante la prima parte del corso.

• Internet ... (!) .... ma Attenzione!Internet e fonte di informazioni, ma non necessariamente di verita. Per questo,cercare sempre di leggere riferimenti che sono stati pubblicati su atti di congressicon revisione oppure su riviste scientifiche (articoli, tutorials, surveys, ecc.).

• ... Ma il riferimento piu importante sono i vostri appunti !Nessun testo potra mai sostituirli perche: (1) Li avete scritti voi ! (2) Ci sonodegli argomenti che verranno trattati durante il corso e che non sono contenutiin nessuno dei testi elencati sopra.

8

Modalita d’esame

L’esame e composto da due parti:

• Un progetto su uno specifico argomento del corso (spesso Algoritmi Genetici

o Programmazione Genetica).

• Una prova orale su tutto il programma del corso.

Il voto finale e la media tra il voto del progetto e il voto dell’orale.

9

Modalita d’esame (2)

Inoltre le modalita d’esame prevedono le seguenti regole che devono essere tassati-

vamente rispettate:

• Il tema specifico del progetto deve essere approvato dal docente prima che lo

studente inizi a lavorare sul progetto. In altri termini, e vietato presentarsi

all’orale con un progetto il cui argomento non sia stato accettato dal docente.

• Si puo sostenere l’orale solo dopo aver terminato il progetto. In altri termini,

non si puo sostenere prima l’orale e poi fare il progetto:

10

Progetto

• Vi saranno temi proposti dal docente, ma possono essere accettati (e sono i

benvenuti!) anche temi proposti dagli studenti.

• I progetti possono essere fatti a gruppi (ogni gruppo massimo 3 persone) ma

deve risultare chiaro il contributo di ogni persona al lavoro. L’esame (e quindi

il voto) e “ad personam”.

• E possibile fare i progetti in collaborazione con il corso di Robotica (prof. Mar-

chese). In tal caso il progetto sara un po’ piu difficile, ma vale come esame per

il corso di Robotica (in una volta sola avete fatto tutto l’esame di robotica piu

meta esame di Soft Computing).

11

Motivazioni del corso

Nonostante gli sviluppi spettacolari dell’Informatica negli ultimi anni (diciamo dagli

anni ’70 ad oggi), ancora oggi vi sono numerosi problemi che sono difficili o impossibili

da risolvere tramite tecniche algoritmiche“classiche”.

Un tipico esempio sono i cosiddetti problemi NP-completi, ovvero quelli per cui non

e noto un algoritmo che risolve il problema in un tempo polinomiale (o meno che

esponenziale) rispetto alle dimensioni dei dati.

12

Esempi di problemi NP-completi

Tipici esempi di problemi NP-completi sono:

• Commesso viaggiatore: calcolare il percorso piu breve che tocchi N citta e ritorni

al punto iniziale.

• Zaino: dato uno zaino che puo portare al massimo un peso P, ed un insieme

N di oggetti di cui si conosce il peso ed il valore, calcolare il massimo valore

complessivo degli oggetti che possono essere inseriti nello zaino.

Questi problemi non sono solo problemi teorici, ma hanno anche applicazioni pratiche. Ad esem-pio, una applicazione del commesso viaggiatore e quella di programmare N lavori diversi su unastessa macchina dove siano noti i costi ci j per passare da un lavoro i a un lavoro j.

Altro esempio e quello di programmare una macchina automatica (tipo trapano) che deve spostarsiper fare N buchi su una lastra. Il costo di ogni spostamento della macchina e noto e deve essereminimizzato.

13

Altri problemi

Altri problemi“pratici”difficili o impossibili da risolvere tramite tecniche algoritmiche

classiche:

• Riconoscimento dei volti.

• Scrivere il programma che guida un robot in uno spazio 3D dinamico.

• Riconoscere una data immagine indipendentemente dalle condizioni di illumi-

nazione e da altri fattori.

• Trovare la giusta miscela di sostanze chimiche, presenti all’interno di un database

molto grande, per creare un farmaco con determinate proprieta.

• ...

14

Machine Learning

Fin dalle origini dell’Informatica, si e fatta strada l’idea che uno dei modi piu promet-

tenti di risolvere (o approssimare) questi problemi (difficili o impossibili da risolvere

con tecniche algoritmiche classiche) fosse quello di tentare di dare ai sistemi infor-

matici la capacita di apprendere.

Questo campo di studio si chiama Machine Learning ed e stato definito per la prima

volta da Samuel nel 1959 e poi ripreso ed approfondito da Mitchell in tempi piu

recenti (anni ’90).

La definizione piu accettata di Machine Learning e stata data da Mitchell: “lo studio

di algoritmi in grado di migliorarsi automaticamente attraverso l’esperienza”.

L’idea e quella di arrivare a risolvere un problema complesso senza dover dire al

sistema come lo si risolve.

15

Tecniche di Machine Learning

Esistono molte tecniche di Machine Learning. Tra esse, alcune partono dall’idea che

apprendere e migliorare attraverso l’esperienza sia una capacita tipica degli esseri viventi

e quindi tentano di costruire dei sistemi informatici ispirandosi alla biologia degli es-

seri viventi:

• Le Reti Neurali sono ispirate dalla struttura del cervello umano e tentano di

simularne (in maniera elementare) il funzionamento.

• Gli Algoritmi Genetici si ispirano alla teoria dell’evoluzione di Darwin ed hanno

come scopo quello di far evolvere i sistemi informatici con regole analoghe

(anche se semplificate) a quelle che hanno portato all’evoluzione delle specie

degli esseri viventi.

16

• La Logica Fuzzy ha come scopo quello di creare dei sistemi informatici in grado

di simulare la capacita che hanno gli esseri viventi di trattare concetti come

l’incertezza e l’informazione imprecisa.

• La Ricerca Locale e il Simulated Annealing hanno come scopo quello di creare

dei sistemi informatici che simulino il senso dell’orientamento degli esseri viventi.

17

Soft Computing

Tutti questi appocci hanno la caratteristica che, se non riescono a trovare una

soluzione perfetta ad un dato problema, forniscono una soluzione approssimata (o

imprecisa).

Questa e la caratteristica tipica dell’insieme di tecniche che vanno sotto il nome di

Soft Computing.

Il Soft Computing e particolarmente utile quando non sono richieste soluzioni precise,

ma si possono accettare anche soluzioni approssimate.

18

Esempio

Ad esempio, se si vuole far muovere un robot in una stanza in modo che esso

eviti gli ostacoli che sono presenti in quella stanza, non e necessario trovare un

particolare percorso (soluzione precisa), ma un qualunque percorso in grado di evitare

gli ostacoli.

19

Altro esempio

Supponiamo, ad esempio, che lo scopo di un’applicazione sia classificare un oggetto

in base al risultato di un certo calcolo, nel seguente modo:

• Se il risultato ha valore tra 1 e 10, l’oggetto deve essere posto nella classe A.

• Se il risultato ha valore tra 10 e 20, l’oggetto deve essere posto nella classe B.

• Se il risultato ha valore tra 20 e 30, l’oggetto deve essere posto nella classe C.

Supponiamo adesso che il risultato esatto del calcolo sia 5. L’oggetto dovrebbe

essere posto nella classe A. Un qualsiasi algoritmo che fornisca come risultato, ad

esempio, 7 ci fa comunque inserire (correttamente!) l’oggetto nella classe A.

20

Soft Computing e Machine Learning

In altri termini, il Soft Computing trova una sua applicazione nei casi in cui soluzioni

approssimate possano risolvere bene (in maniera soddisfacente) i problemi.

Esistono altre tecniche di Machine Learning che non sono di Soft Computing, ovvero

che sono concepite per restituire sempre una soluzione perfetta, come ad esempio

gli alberi di decisione o la programmazione logica induttiva. Queste tecniche non

verranno trattate in questo corso.

21

22

Campi di applicazione del Soft Computing

• Robotica– Calcolo di cammini– Ottimizzazione di movimenti– Trattamento di segnali provenienti da sensori– ...

• Ingegneria– Generazione automatica di circuiti elettrici integrati– Gestione di dispositivi meccanici (elettrodomestici, treni, ...)– ...

• Biologia– Studio delle proprieta della catena del DNA e del genoma umano– ...

23

• Chimica– Generazione automatica di farmaci o altri composti chimici a partire dai loro

componenti elementari– ...

• Medicina– Riconoscimento di immagini radiologiche– ...

• Economia– Simulazione e previsione degli andamenti dei mercati finanziari– ...

24

• Marketing– Studi su come indirizzare le campagne pubblicitarie o sulla disposizione dei

prodotti nei negozi– ...

• Sicurezza– Controllo del traffico tramite analisi filmati– Riconoscimento volti (sicurezza)– Tracking– ...

• ...

25

Ambizioni di questo corso

• Fornire agli studenti gli strumenti per poter affrontare un insieme molto vasto

di applicazioni senza entrare nei dettagli specifici di ogni applicazione, ma ri-

manendo indipendenti dalle applicazioni (ovvero il piu possibile generali).

• Far arrivare agli studenti il messaggio che per poter applicare le tecniche di Soft

Computing a problemi del mondo reale in modo ancora piu efficace di quanto

non si faccia oggi, occorre migliorare queste tecniche, che ancora oggi sono

ad un livello non completamente maturo: occorre ancora fare molta ricerca in

questo settore.

– C’e bisogno di persone giovani, dinamiche e con tanto entusiasmo, che abbiano lacapacita di portare avanti idee nuove. Non abbiate paura delle vostre idee!

26

Rischi

Essere“generali” (ovvero indipendenti dalle applicazioni) non deve significare essere

“superficiali”,“teorici”,“fumosi”,“inconcludenti”, ...

Le esercitazioni in laboratorio e i progetti dovrebbero restituire un po’ di concretezza

ad un corso che, volendo rimanere generale e volendosi mantenere sulla frontiera

della ricerca potrebbe anche sembrare troppo teorico.

Occorre sempre ricordarsi che per poter applicare una tecnica a livello industriale,

occorre conoscerla in profondita!

27

Soft Computing e Problemi di Ottimizzazione Combinatoria

In precedenza abbiamo detto che il Soft Computing nasce per risolvere determi-

nati problemi che sono difficili o impossibili da risolvere con tecniche algoritmiche

classiche.

L’approccio che seguiremo in questa lezione e quello di avvicinarci a queste tec-

niche partendo dalla definizione formale di un insieme tipico di questi problemi, detti

problemi di ottimizzazione combinatoria.

Partiremo con lo studio di questa classe di problemi perche essi possono essere definiti

in maniera molto semplice e quindi si prestano piuttosto bene ad essere usati per

introdurre alcune tecniche di Soft Computing.

28