|
|
UNIVERSIDADE FEDERAL DO PARANÁ
DEPARTAMENTO DE INFORMÁTICA
|
COMPUTAÇÃO BIOINSPIRADA
Professora: Aurora Pozo
Carga horária: 60 horas - 4
créditos
Primeiro semestre de 2018
Proporcionar aos alunos o
ferramental teórico e as experiências práticas necessárias ao projeto e análise
de algoritmos bioinspirados. Debater as principais
meta-heurísticas da literatura partindo da: Representação de soluções,
Vizinhança, Busca local até os algoritmos genéticos e outros métodos bioinspirados assim como recozimento simulado, busca tabu,
GRASP. Aplicar em
vários contextos os conceitos teóricos desenvolvidos.
Programa
|
Aula
|
Assunto
|
|
1
|
Apresentação dos objetivos e programa da disciplina,
metodologia de ensino, forma de avaliação etc.
|
|
2
|
Generalizações da busca local.
|
|
3
|
Simulated Annealing
|
|
4
|
Tabu
Search, Iterated Local Search
|
|
5
|
Estratégias Evolutivas
|
|
6,7
|
Algoritmos Genéticos
|
|
8
|
Evolução Diferencial
|
|
9
|
Particle Swarm Optimization
|
|
10
|
Greedy Randomized
Adaptive Search Procedures (GRASP)
|
|
11
|
Ant Colony Optimization
|
|
|
|
|
|
|
|
|
|
|
Apresentação
de Passo
|
|
Apresentação de Finais com consolidação Resultados
|
|
Entrega
de artigo
|
Avaliação
u A avaliação consistirá de um projeto: P1, mais a participação e desempenho
nas atividades avaliativas em sala de aulas computacionais (T1, T2,...,T8).
u O projeto P1 tera peso de 30%.
u Para os testes {T1...T8}, serão consideradas as 7 (sete) melhores notas e
feita a média MT= soma [ 7_melhores_T ] / 7, que terá
peso 30%.
u Prova Escrita PE
(40%)
u A média parcial (MP) será dada por:
u MP = 0,30 x P1
+ 0,30 x MT + 0,4 x PE
u Projeto P1: Implementação computacional da técnica aplicada a um
problema. Apresentação de um artigo relatando os resultados obtidos (formato de
artigo: introdução, trabalhos relacionados, proposta, experimentos, discussão e
resultados). Apresentação oral e escrita do trabalho
- Sean
Luke, 2013, Essentials of Metaheuristics, Lulu, second edition,
available for free at http://cs.gmu.edu/~sean/book/metaheuristics/
- Manual
de Computação Evolutiva e metaheuristicas. Antonio Gaspar Cunha, Ricardo Takahashi, Carlos Henggeler Antunes.Belo
Horizonte Editora UFMG Coimbra, Imprensa da Universidade de Coimbra, 2013
- http://www.inf.ufpr.br/aurora/disciplinas/topicosia2/livros/
- http://www.inf.ufpr.br/aurora/disciplinas/topicosia2/aulas/
- http://www.decom.ufop.br/prof/marcone
- GOLDBERG,
D. E. Genetic algorithms in search, optimization and machine learning.
Alabama: Addison Wesley, 1989. 413p.
- Aarts, E.
H. L. e J. K. Lenstra, (1996), Local Search in
Combinatorial Optimization, John Wiley, Chichester.
- Chatterjee,
S., Carrera, C., e L. A. Lynch, (1996), Genetic Algorithm and Traveling
Salesman Problem, EJOR 93, 490-510.
- Colorni,
A., Dorigo, M., Maniezzo, V., e M. Trubian, (1994), Ant System for Job Shop Scheduling,
Belgian Journal of Operations Research, Estatistic,
and Computer Science 34, 39-53
- Costa,
A., e A. Hertz, (1997), Ants Can Colour Graphs, Opns.
Res. Soc. 48, 295-305.
- Davis L. (1987), Genetic
Algorithms and Simulated Annealing, Pitman, London.
- Glover, F., (1990), Tabu Search: A Tuturial, Center of Applied Artificial Intelligence, University
of Colorado, USA.
- Hansen, P., e N. Mladenovic,
(1997a), An Introduction to Variable Neighborhood
Search, Les Cahiers du Gerad, G-97-51.
- Osman, I. H., e J. P. Kelly
(1996), Meta-Heuristics: Theory and Applications, Kluwer, Boston, 571-587.
- Reeves, C. R., (1993), Modern
Heuristic Techniques for Combinatorial Problems, Blackwell Scientific
Publication.
- Taillard, E.
D., (1999), Ant Systems, Techinical Report
IDSIA-05-99, Instituto Dalle Molle
di Studi sull’Intelligenza
Artificiale (IDSIA), Lugano, Switzerland.
General Guidelines for Term Project
Paper Review
Paper Review Form