Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Per gli Studenti
Soft computing

Codice ins.

Insegnamento

CFU ins.

Tipo ins.

Anno

Sem.

SSD ins.

Responsabile insegnamento

F1801Q112

Soft Computing

6

OBS

2

2

INF/01

MAURI Giancarlo

 

Soft Computing

 

 

 

 

 

 

Contenuti:
Il corso introduce alcune tecniche di Soft Computing, accennando ad alcuni domini applicativi.

  • Vengono introdotti i principali algoritmi meta-euristici:
    • Ricerca Locale,
    • Hill Climbing,
    • Simulated Annealing,
    • Tabu Search.
  • Il corso prosegue con la trattazione di alcuni dei più noti algoritmi evolutivi:
    • Algoritmi Genetici,
    • Programmazione Genetica,
    • Particle Swarm Optimization,
    • Ant Colony Optimization.
  • Viene quindi svolta una introduzione a:
    • reti neurali auto-organizzanti,
    • logica fuzzy.

Obiettivi formativi:
ll corso ha come obiettivo principale quello di fornire una conoscenza introduttiva di alcune tecniche per la risoluzione di problemi di ottimizzazione, note collettivamente con il nome di Soft Computing. Mediante la partecipazione alle attività previste per l'insegnamento lo studente svilupperà competenze per applicare tecniche di Soft Computing a problemi reali.

Prerequisiti:
Verrà richiesta la scrittura di semplici programmi in un linguaggio di programmazione ad alto livello, quasi certamente C/C++. È quindi richiesta la conoscenza (o lo studio individuale) del C/C++.
Sono inoltre richieste le conoscenze di base di apprendimento automatico.

Metodi didattici:
Il corso consisterà di lezioni frontali ed esercitazioni.

Programma esteso

  1. Concetti introduttivi e motivazioni del corso
    • Definizione e concetti fondamentali del Machine Learning
    • Definizione informale del Soft Computing
    • Cenni sui domini applicativi del Soft Computing
  2. Spazi di Ricerca e Tecniche di Ottimizzazione
    • Problemi di Ottimizzazione Combinatoria e loro complessità
    • No Free Lunch Theorem
    • Ricerca Locale
    • Paesaggi di fitness, loro significato e importanza, loro struttura topologica
    • Simulated Annealing
      • Definizioni generali e funzionamento
      • Teoria del Simulated Annealing e suo comportamento asintotico
    • Cenni al Tabu Search
  3. Algoritmi Genetici
    • Operatori genetici: selezione; crossover;mutazione
    • Funzionamento generale dell'Algoritmo Genetico "standard" [Holland, 1975]
    • Genotipo e Fenotipo
    • Teorema degli Schemi
    • Problema del k-Armed Bandit.
    • Comportamento asintotico degli Algoritmi Genetici
    • Cromosoma diploide (modello di Bagley, primo e secondo modello di Hollstien-Holland)
    • Operatori di inversione e riordinamento (modelli di Bagley, Frantz)
    • Partially matched crossover, cycle crossover (Goldberg)
    • Ripartizione degli individui in specie
      • fitness sharing (Goldberg)
      • riproduzione stretta (modelli di Hollstien e Brooker)
    • Ottimizzazione Multiobiettivo
      • VEGA (Shaffer)
      • Modello di Baker
    • Valutazione sperimentale delle prestazioni di un Algoritmo Genetico (funzioni di test diWhitley).
    • Modellazione di GAs con catene di Markov
      • Definizione di matrice primitiva e stocastica
      • Teorema di Perron-Frobenius
      • Costruzione della matrice di transizione della catena di Markov associata ad un GA
      • Risultati di convergenza quasi certa di un GA con utilizzo dell'elitismo
    • Implementazione di GA: GAlib
  4. Swarm Intelligence
    • Introduzione e motivazioni
    • Outline della metafora biologica: il comportamento degli sciami
    • Ottimizzazione continua
    • Particle Swarm Optimization (PSO)
      • Versione base
      • Possibili estensioni
      • Possibili applicazioni
    • Ant Colony Optimization
  5. Programmazione Genetica
    • Rappresentazione e principali differenze con gli Algoritmi Genetici
    • Operatori Genetici
    • Calcolo della Fitness
    • Proprietà di Chiusura e Sufficienza
    • Stati stabili
    • Funzioni Automaticamente Definite (ADF)
    • GP Benchmarks (even parity, multiplexer, symbolic regression, artificial ant on the Santa Fe trail)
    • Difficoltà dei problemi in GP
      • fitness distance correlation
      • funzioni sintetiche (trap functions, royal trees)
    • Cenni a altri tipi di Algoritmi Evolutivi
      • Strategie di evoluzione
      • Programmazione evolutiva
  6. Reti neurali auto-organizzanti
    • Reti ad apprendimento competitivo.
    • Reti di Kohonen o Self Organizing Maps (SOM).
  7. Logica fuzzy

 Testi di riferimento:

  1. D. E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning” Addison-Wesley
  2. A.Tettamanzi, M.Tomassini. "Soft Computing: Integrating Evolutionary, Neural and Fuzzy Systems”, Springer
  3. M. Dorigo, T. Stützle.  "Ant Colony optimization”, MIT Press
  4. E. Aarts, J. Korst. “Simulated Annealing and Boltzmann Machines”, John Wiley and Sons
  5.  W. Banzhaf, P. Nordin, R. E. Keller, F. D. Francone. “Genetic Programming, an Introduction”, Morgan Kauffmann
  6. Clerc, M., editor (2006). Particle Swarm Optimization. ISTE.
  7. Kennedy, J. and Eberhart, R. (1995). Particle swarm optimization. In Proc. IEEE Int. conf. on Neural Networks, volume 4, pages 1942-1948. IEEE Computer Society.
  8. Banks, A., Vincent, J., and Anyakoha, C. (2007). A review of particle swarm optimization. part i: background and development. Natural Computing Journal, 6:467

Modalità di verifica dell'apprendimento:
Esame finale

Tipo esame:
 

  • esame scritto sulle parti teoriche
  • esame del materiale consegnato relativo alle esercitazioni

Tipo valutazione:
Il voto finale sarà una media pesata dei voti riportati nello scritto e sul materiale relativo alle esercitazioni.

Contents:

This course introduces a few Soft Computing techniques, also mentioning some application domains.

  • Meta-heuristics are first introduced:
    • Local search,
    • Hill Climbing,
    • Simulated Annealing,
    • Tabu Search.
  • Then some well-known evolutionary algorithms are presented:
    • Genetic algoritms,
    • Genetic programming,
    • Particle Swarm Optimization,
    • Ant Colony Optimization.
  • Then an introduction is presented to:
    • self-organizing neural nets,
    • fuzzy logic.

Goals: 
The main objective of the course is to provide an introductory knowledge to some methodologies for solving optimization problems, which are collectively known under the name of Soft Computing. By attending all course activities, students will develop competencies to apply Soft Computing techniques to real problems.

Prerequisites: 
It will be required to write simple programs in an high level language, almost certainly C/C++. It is therefore required some knowledge (or individual study) of C/C++.
Basic knowledge of machine learning techniques is also required.

Teaching methods: 
The course will consist of lectures and exercise sessions

Extended program:
 

  1. Basic concepts and motivations
    • Basic concepts  of Machine Learning
    • Informal definition of Soft Computing
    • Notes ontheapplication domains of Soft Computing
  2. Search spaces and optimization techniques
    • Combinatorial optimization problems and their complexity
    • No Free Lunch Theorem
    • Local Search
    • Fitness landscapes
    • Simulated Annealing
      • Basic definitions
      • Theory of Simulated Annealing and its asymptotic behaviour
    • Tabu Search Basics
  3. Genetic Algorithms
    • Genetic Operators: selection; crossover;mutation
    • The "standard" Genetic Algorithms [Holland, 1975]
    • Genotypeand phenotype
    • The SchemeTheorem
    • k-Armed BanditProblem
    • Asymptotic behaviour of Genetic Algorithms
    • Diploidchromosome (Bagley's model, firstand second Hollstien-Holland model)
    • Inversionand reorderingoperators (Bagley's and Frantz's models)
    • Partially matched crossover, cycle crossover (Goldberg)
    • Multiobjective optimization
      • VEGA (Shaffer)
      • Baker's Model
    • Experimentalevaluation of GAperformances (Whitley's test functions)
    • Modeling GAs with Markov chains
      • Primitivestochasticmatrices
      • Perron-FrobeniusTheorem
      • Building thetransitionmatrixof Markov chainassociated toa GA
      • GA convergence results
    • GAImplementation:GAlib
  4. Swarm Intelligence
    • Introductionand motivations
    • Thebiologicalmetaphor: the behaviour of swarms
    • Particle Swarm Optimization (PSO)
      • Basicversion
      • Extensions
      • Applications
    • Ant Colony Optimization
  5. GeneticProgramming (GP)
    • Comparison with GAs
    • GeneticOperators
    • Fitness computation
    • Closure properties
    • Steady States
    • Automatically Defined Functions (ADF)
    • GP Benchmarks (even parity, multiplexer, symbolic regression, artificial ant on the Santa Fe trail).
    • Difficulty ofproblems in GP
      • fitness distance correlation
      • syntheticfunctions (trap functions, royal trees)
    • Other variants of evolutionary algorithms
      • Evolution Strategies
      • Evolutionary Programming
  6. Self-organizing neural networks
    • Competitive learning networks
    • Kohonennetworksor Self Organizing Maps (SOM)
  7. FuzzyLogic

Textbooks:

  1. D. E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning” Addison-Wesley
  2. A.Tettamanzi, M.Tomassini. "Soft Computing: Integrating Evolutionary, Neural and Fuzzy Systems”, Springer
  3. M. Dorigo, T. Stützle.  "Ant Colony optimization”, MIT Press
  4. E. Aarts, J. Korst. “Simulated Annealing and Boltzmann Machines”, John Wiley and Sons
  5.  W. Banzhaf, P. Nordin, R. E. Keller, F. D. Francone. “Genetic Programming, an Introduction”, Morgan Kauffmann
  6. Clerc, M., editor (2006). Particle Swarm Optimization. ISTE.
  7. Kennedy, J. and Eberhart, R. (1995). Particle swarm optimization. In Proc. IEEE Int. conf. on Neural Networks, volume 4, pages 1942-1948. IEEE Computer Society.
  8. Banks, A., Vincent, J., and Anyakoha, C. (2007). A review of particle swarm optimization. part i: background and development. Natural Computing Journal, 6:467

Assessment methods:
final exam

Examination:
Written examination on the theoretical parts,
Examination of the material delivered by students about the practices

 Evaluation Type:
The final mark will be a weighted average of the marks of the written and of the practices examinations.

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 27/09/2012