 |
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 2010
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.
Programa
| Aula |
Assunto (draft)
|
| 1 |
Apresentação dos
objetivos e programa da disciplina, metodologia de ensino, forma de
avaliação etc. Slides: Aula1
|
| 2 |
Problemas e Espaços de
Problemas. Definição do Problema como uma busca em um
Espaço de Estados. Slides: Aula2 |
| 3 |
Algoritmos de busca
básicos. Busca em profundidade, (Depth-First Search), busca em
largura (Breadth-First Search) |
| 4 |
Busca Heurística. Slides:
Aula3 |
| 5 |
Busca local: Otimalidade local x
otimalidade global. Slides: Aula4 |
| 6 |
Conceito de
metaheurística. Generalizações da busca local |
| 7 |
Simulated Annealing |
| 8 |
Busca Tabu |
| 9 |
Técnicas Multistart –
GRASP |
| 10 |
Vida Artificial |
| 11 |
Computação
Evolutiva |
| 12 |
Nuvem de Partículas |
| 13 |
Consolidação |
| 14 |
Avaliação |
| 15-20 |
Seminários |
| 21-24 |
Preparação de
Workshop |
| 25-28 |
Workshop |
| 30 |
Entrega de artigo |
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 (30%)
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 (70%)
- 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