Transcript Temi Avanzati di Intelligenza Artificiale

Temi Avanzati di
Intelligenza Artificiale
Prof. Vincenzo Cutello
Department of Mathematics and Computer Science
University of Catania
Temi Avanzati di Intelligenza Artificiale - Intro
1
Aims


Introduce the main concepts, techniques and
applications in the field of evolutionary computation.
Give students some practical experience on when
evolutionary computation techniques are useful, how
to use them in practice and how to implement them
with different programming languages.
Temi Avanzati di Intelligenza Artificiale - Intro
2
Learning Outcomes
On completion of this course, the student should be able to:




Understand the relations between the most important evolutionary
algorithms presented in the course, new algorithms to be found in the
literature now or in the future, and other search and optimisation
techniques.
Understand the implementation issues of evolutionary algorithms.
Determine the appropriate parameter settings to make different
evolutionary algorithms work well.
Design new evolutionary operators, representations and fitness functions
for specific practical and scientific applications.
Temi Avanzati di Intelligenza Artificiale - Intro
3
Detailed Syllabus (I)
Introductoin to Evolutionary Computation





Biological and artificial evolution
Evolutionary computation and AI
Different historial branches of EC, e.g., GAs, EP, ES, GP, etc.
A simple evolutionary algorithm
Search Operators







Recombination/Crossover for strings (e.g., binary strings), e.g., one-point,
multi-point, and uniform crossover operators
Mutation for strings, e.g., bit-flipping
Recombination/Crossover and mutation rates
Recombination for real-valued representations, e.g., discrete and
intermediate recombinations
Mutation for real-valued representations, e.g., Gaussian and Cauchy
mutations, self-adaptive mutations, etc.
Why and how a recombination or mutation operator works
Temi Avanzati di Intelligenza Artificiale - Intro
4
Detailed Syllabus (II)

Selection Schemes





Fitness proportional selection and fitness scaling
Ranking, inclduing linear, power, exponential and other ranking
methods
Tournament selection
Selection presure and its impact on evolutionary search
Search Operators and Representations




Mixing different search operators
An anomaly of self-adaptive mutations
The importance of representation, e.g., binary vs. Gray coding
Adaptive representations
Temi Avanzati di Intelligenza Artificiale - Intro
5
Detailed Syllabus (III)



Evolutionary Combinatorial Optimisation

Evolutionary algorithms for TSPs

Evolutionary algorithms for lecture room assignment

Hybrid evolutionary and local search algorithms
Co-evolution

Cooperative co-evolution

Competitive co-evolution
Niching and Speciation

Fitness sharing (explicit and implicit)

Crowding and mating restriction
Temi Avanzati di Intelligenza Artificiale - Intro
6
Detailed Syllabus (IV)

Constraint Handling




Common techniques, e.g., penalty methods, repair methods, etc.
Analysis
Some examples
Genetic Programming






Trees as individuals
Major steps of genetic programming, e.g., functional and terminal
sets, initialisation, crossover, mutation, fitness evaluation, etc.
Search operators on trees
Automatically defined functions
Issues in genetic programming, e.g., bloat, scalability, etc.
Examples
Temi Avanzati di Intelligenza Artificiale - Intro
7
Detailed Syllabus (IV)

Multiobjective Evolutionary Optimisation



Learning Classifier Systems




Basic ideas and motivations
Main components and the main cycle
Credit assignment and two approaches
Theoretical Analysis of Evolutionary Algorithms





Pareto optimality
Multiobjective evolutionary algorithms
Schema theorems
Convergence of EAs
Computational time complexity of EAs
No free lunch theorem
Summary
Temi Avanzati di Intelligenza Artificiale - Intro
8
Recommended Books
Title
Author(s)
Publisher
Comments
Handbook on Evolutionary
Computation
T. Baeck, D. B. Fogel,
and Z. Michalewicz
(eds.)
IOP Press, 1997.
Very good reference to evolutionary
computation. Should read relevant
sections after each lecture.
Genetic Algorithms + Data
Structures = Evolution
Programs (3rd edition)
Z Michalewicz
Springer-Verlag,
Berlin, 1996
Recommended reference book for this
module. It is more up-to-date than
Goldberg's book.
Addison-Wesley,
1989
Good introductory book on genetic
algorithms and classifier systems, but
no other topics. Somewhat out of date.
Genetic Algorithms in
Search, Optimisation &
Machine Learning
D E Goldberg
Genetic Programming: An
Introduction
W Banzhaf, P Nordin,
R E Keller & Frank D
Francone
Morgan Kaufmann,
1999
A good introductory book on genetic
programming.
Evolutionary Computation:
Theory and Applications
X. Yao (ed)
World Scientific
Publ. Co.,
Singapore, 1999.
Good reference for more advanced
topics.
Various articles in journals
and conference
proceedings
A list of papers will be specified as the
module progresses.
Temi Avanzati di Intelligenza Artificiale - Intro
9