 |
UNIVERSIDADE
FEDERAL
DO
PARANÁ
DEPARTAMENTO DE INFORMÁTICA |
CI801 - Tópicos Especiais em
Inteligência Artificial
Professora: Aurora Pozo
Carga horária: 60 horas - 4 créditos
Primeiro semestre de 2012
Tema: Metaheurísticas
Proporcionar aos
alunos o ferramental teórico e as experiências
práticas necessárias ao projeto e análise de
algoritmos metaheurísticos. Debater as principais
metaheurísticas da literatura partindo dos algoritmos
construtivos aproximados. Representação de
soluções. Vizinhança. Busca local ate as
Metaheurísticas simulated annealing, busca tabu, GRASP,
algoritmos genéticos e outros métodos populacionais.
Aplicar em vários contextos os conceitos teóricos
desenvolvidos.
Livro texto: Essentials of Metaheuristics, Sean Luke.
Programa
| Aula |
Assunto
|
| 1 |
Apresentação dos
objetivos e programa da disciplina, metodologia de ensino, forma de
avaliação etc. Conceito de
metaheurística. Generalizações da busca local.
Slides: Slides: Aula1
|
| 2 |
Simulated Annealing e Busca Tabu
Aula2,Aula3 |
| 3 |
Busca Local Iterativa. Slides: Aula4 |
| 4 |
Métodos Populacionais. Slides: Aula5 |
| 5 |
Algoritmos Geneticos. Slides: Aula6 |
| 6 |
Consolidação: aula de exercicios |
| 7 |
Aula prática em Laboratorio AG
|
| 8 |
Programação Genetica. Slides: Aula9 |
| 9 |
Aula prática em Laboratorio PSO |
| 10 |
Algoritmos Construtivos, Grasp, Path-Relink |
| 11 |
Otimização por
Colonia de Formigas. Slides: Aula12 |
| 12 |
Outros Algoritmos
|
| 13 |
Consolidação: aula de exercicios |
| 14 |
Avaliação : DATA PREVISTA 30/04/2012
|
|
Seminários : Distribuição dos
Trabalhos, http://archive.ics.uci.edu/ml/datasets.html.
Esp. Precisão
|
|
Apresentação de
Resultados Parciais: 28/05 e 30/05 Resultados,(Dados, Artigo) |
|
Apresentação de Finais com
consolidação Resultados 18/06 e 20/06
|
|
Entrega de artigo 21/06
|
Seminários -
Apresentação: Cada estudante apresentará
um artigo de revista ou um conjunto pequeno de artigos de
conferência, de preferência do mesmo grupo de autores,
sobre um mesmo tópico. Os estudantes são livres para
escolher os artigos que desejem apresentar desde que eles estejam no
escopo do curso e aprovados pelo professor. Os estudantes determinaram
e submeterão, por email ou copia impressa, o artigo que
apresentarão. Cada aluno terá 30 minutos para apresentar
seu artigo. Existirá uma discussão de 5 mins após
cada apresentação. Os alunos são
responsáveis por fornecer o material de sua
apresentação uma semana antes a toda a turma.
Se aconselha ler o artigo "How
to
Present
a
Paper
in
Theoretical
Computer
Science:
A
Speaker's
Guide
for
Students" para uma apresentação
bem sucedida.
Seminários -
Participação: Alem de sua
apresentação, se espera que cada estudante leia os
artigos que serão apresentados pelos seus colegas antes da
apresentação. Após cada
apresentação, existira uma discussão. Cada aluno
será avaliado com referência à
participação
nos seminários.
Workshop: Será organizado
um workshop durante as ultimas semanas do semestre. Cada aluno
realizara um experimento, testando novas idéias (de
preferência) na área do tópico da
apresentação. Então cada aluno prepara um artigo,
relatando seu experimento, assim com a interpretação dos
resultados e idéias sobre pesquisas futuras. O artigo deve ter
entorno de 8-10 paginas, em 11 “Times New Roman ” .
Cada aluno terá 30 minutos para apresentar o artigo.
Se aconselha ler o artigo "How
to
give
a
good
research
talk".
Avaliação
1) Prova Escrita (40%) + (10%) participação
2 ) Escolha de um problema e uma técnica metaheurística
para resolvê-lo
Implementação computacional,
preferencialmente na linguagem C, da técnica aplicada ao problema
Apresentação de um artigo relatando os
resultados obtidos (escrito, relatorio tecnico)
Apresentação oral do trabalho (50%)
- 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
- Artificial
Intelligence: A Modern Approach Stuart. Russell and Peter Norvig,
Prentice Hall, 1995.
- Inteligência
Artificial. Elaine Rich e Kevin Knight, Makron
Books, 1993.
- 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
