CI801 - Tópicos Especiais em Inteligência Artificial

Professora: Aurora Pozo

Carga horária: 60 horas - 4 créditos

Primeiro semestre de 2014

Tema: Metaheurísticas

 

 

Ementa

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 da: Representação de soluções, Vizinhança, Busca local até as algoritmos genéticos e outros métodos populacionais assim como recozimento simulado, busca tabu, GRASP. Aplicar em vários contextos os conceitos teóricos desenvolvidos.

 

Programa

 

 

Avaliação

u  Prova Escrita  (40%) + (20%) exercícios semanais

u  TRABALHO (40%): o trabalho será dividido em 2 passos

u  Passo 1: Escolha de um problema, consiste em escolher um artigo atual relatando o problema e as técnicas que existem para resolver. Baseado nisto deve ser escolhida a metaheurística para resolvê-lo, explicando os primeiros passos como representação e operadores. Apresentação oral. 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.

 

u  Passo 2: Implementação computacional, preferencialmente na linguagem C, da técnica aplicada ao problema. Apresentação de um artigo relatando os resultados obtidos (formato de artigo: introdução, trabalhos relacionados, proposta, experimentos, discussão e resultados). O artigo deve ter entorno de 8-10 páginas, 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"Apresentação oral e escrita do trabalho

Bibliografia

• 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
• Sean Luke, 2013, Essentials of Metaheuristics, Lulu, second edition, available for free at http://cs.gmu.edu/~sean/book/metaheuristics/
• 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.

  

Links

General Guidelines for Term Project Paper Review

Paper Review Form