PROGRAMA DE DISCIPLINA
Disciplina
Técnicas Metaheurísticas para Otimização Combinatória	Código
BCC466	
Departamento
DEPARTAMENTO DE COMPUTAÇÃO	Unidade
INSTITUTO DE CIÊNCIAS	
Carga Horária
Semanal	Teórica
02	Prática
02	Total
04	
                 EXATAS E BIOLÓGICAS 	
Pré-requisitos
1  Algoritmos e Estrutura de Dados I 	Pré-requisitos

2   Programação de Computadores II	

3    	
4        	
Duração/Semana
15	No  de  Créditos
03	Carga Horária Semestral
60	

Ementa	
Introdução aos métodos heurísticos.	
Algoritmos metaheurísticos ou heurísticas inteligentes: definição, diferenças entre metaheurísticas	
 e heurísticas convencionais.	
Principais metaheurísticas: Simulated Annealing, Busca Tabu, Algoritmos Genéticos, GRASP, 	
 Variable Neighborhood Search, Iterated Local Search, Colônia de Formigas etc.	
  Aplicações de metaheurísticas à resolução de problemas de otimização combinatória.	
       	
       	
       	
       	

 Cursos para os quais é ministrada
1   Ciência da Computação 	Período
-	Natureza
  Eletiva	

2   Engenharia de Produção	
-	
  Eletiva	

3   	

4   	

5   	

6  	

 Aprovado pela Assembléia do DECOM 
 DATA:	Aprovado pelo Colegiado de curso 
 DATA:	Aprovado pelo CEPE:
 DATA: 	
 
______________________
Presidente da Assembléia	
 ____________________
Presidente do Colegiado	
_________________
Presidente do CEPE	

Objetivos: 
•	Especificar a natureza dos problemas combinatórios e a sua dificuldade de resolução
•	Fundamentar os métodos heurísticos de solução de problemas combinatórios
•	Apresentar os métodos heurísticos clássicos, assim como as principais metaheurísticas
•	Mostrar como construir um algoritmo heurístico para resolver um problema combinatório
•	Mostrar métodos de comparação de desempenho de algoritmos

Metodologia de Ensino: 

1)	Aulas teóricas: Aulas expositivas sobre o conteúdo programático.
2)	Aulas práticas: Aulas de laboratório mostrando a implementação computacional, em linguagem de programação de alto nível, das técnicas heurísticas estudadas na resolução de problemas clássicos de otimização combinatória.

Recursos Utilizados:

Laboratório de computação, no qual estará disponível uma linguagem de programação de alto nível para o desenvolvimento de programas, bem como um pacote de programação linear inteira, tal como o LINGO, em sua versão educacional ou de estudante, para comparar os resultados obtidos (em instâncias de pequeno porte) pelos algoritmos heurísticos com os dos algoritmos exatos.
	
Procedimentos de Avaliação:
   A nota N a ser dada para cada aluno ao final do curso será obtida com base na seguinte fórmula:
N = A*0,2 + I*0,3 + AP*0,2 + P*0,3
em que A é um artigo científico produzido pelo aluno (com valor 10) referente à utilização de uma técnica metaheurística aplicada à resolução de um problema combinatório específico apresentado pelo professor, AP é a nota (em 10) relativa à apresentação desse artigo, I é a nota (em 10) referente à implementação computacional da técnica escolhida para resolver a aplicação indicada e P a nota relativa à participação do aluno em tarefas indicadas pelo professor durante o curso.

   Dada a natureza da disciplina, o exame especial consistirá na realização de uma avaliação com as seguintes características:
1)	A produção de artigo científico será substituída por uma prova teórica abrangendo conceitos sobre um modelo metaheurístico relativo a um problema combinatório clássico
2)	A implementação computacional será substituída por uma prova prática relacionada ao modelo heurístico da prova teórica.
3)	A apresentação será substituída pela expressão oral da prova teórica e detalhes da implementação realizada.	

Programa   Analítico das Aulas de Preleção

Unidades e Assuntos	No de Aulas	Referências
Bibliográficas	No de Aulas Acumulado	
1. Introdução aos Métodos aproximados ou heurísticos:	2	2, 3, 5, 13, 14	02	
   Justificativa de uso a problemas combinatórios				
				
2. Métodos de Busca Local	4	2, 3, 5, 13, 14	06	
2.1 Métodos Construtivos				
2.2 Métodos de refinamento:				
2.2.1 Representação e avaliação de uma solução				
2.2.2 Noção de vizinhança				
2.2.3 Método da Descida				
2.2.4 Método Randômico de Descida				
2.2.4 Primeiro de Melhora				
				
3. Algoritmos metaheurísticos ou heurísticas inteligentes:	2	2, 13, 14	08	
    Histórico, fundamentação, diferenças entre metaheurís-				
    ticas e heurísticas convencionais.				
				
4. Simulated Annealing	4	2, 3, 10, 13, 14	12	
				
5. Busca Tabu:	6	2, 3, 4, 5, 13, 14	18	
				
6. Algoritmos Genéticos	6	2, 3, 12,13, 14	24	
				
7. Greedy Randomized Adaptive Search Procedures	4	8, 13, 14	28	
    (GRASP)				
				
8. Iterated Local Search	2	14, 15	30	
				
9. Método de Pesquisa em Vizinhança Variável (VNS)	4	7, 13, 14	34	
				
10. Colônia de Formigas	4	13, 14	38	
				
11. Guided Local Search (GLS)	2	14, 16	40	
				
12. Algoritmos Meméticos 	2	9, 14	42	
				
13. Aplicações de metaheurísticas a problemas clássicos de otimização combinatória:	18	1, 3, 5, 11,12, 13	60	
Caixeiro Viajante, Mochila, Programação de horários,				
Roteamento de Veículos, Recobrimento e particionamento,				
Alocação e sequenciamento de tarefas, Localização etc.				

BIBLIOGRAFIA
NO    DA REFERÊNCIA	
TÍTULO DA OBRA	
AUTOR	
01	Intelligent Scheduling Systems. Kluwer Academic Publishers, 1995	Brown, D.E. and Scherer, W.T.	
02	Computational Intelligence for Optimization. Kluwer Academic Publishers, 1997	Ansari, Nirwan and Hou, E.	
03	Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientif Publications, 1993	Reeves, C.R.	
04	Tabu Search. Kluwer Academic Publishers, 1997.	Glover, F. and Laguna, M.	
05	Tabu Search. Annals of Operations Research, v.41, J.C.Baltzer,1993	Glover, F., Laguna, M. & Taillard, E.	
06	Scatter Search and Star Paths: Beyond the genetic metaphor. OR Spektrum, 17:125-137, 1995 	Glover, F.	
07	Variable Neighborhood Search. Computers and Operations Research, 24:1097-1100, 1997	Mladenovic, N. and Hansem, P.	
08	GRASP. Journal of Global Optimization, 6:109-133, 1995	Feo, T.A. and Resende, M.G.C	
09	Memetic Algorithms: A Short Introduction. In http://alife.ccp14.ac.uk/memetic/~moscato/memetic_home.html	Moscato, P.	
10	Inteligência Computacional. In http://www.caa.uff.br/~jrat	Torreão, J.R.A.	
11	Artigos diversos sobre aplicações de metaheurísticas 	diversos	
12	Otimização Combinatória e Programação Linear. Editora Campus, 2005	Goldbarg, M.C. e Luna, H.P.L.	
13	Metaheuristics and Applications. Advanced School on Artificial Intelligence. Estoril, Portugal, 1996	Ribeiro, C.C.	
14	Inteligência Computacional para Otimização. Notas de aula, Universidade Federal de Ouro Preto, 2007. Disponível em http://www.decom.ufop.br/prof/marcone/InteligenciaCompucional/InteligenciaComputacional.pdf	Souza, M.J.F.	
15	Iterated Local Search. In: Handbook of Metaheuristics. Kluwer Academic Publishers, 2003	Glover, F. and Kochenberger, G.	
16	Guided Local Search for Combinatorial Optimisation Problems. PhD Thesis. Department of Computer Science. University of Essex, 1997.	Voudouris, Christos	
Aprovado pela Assembéia do DECOM
DATA : 	Aprovado pelo Colegiado de curso
DATA :	

_____________________
Presidente da Assembléia	
______________________
Presidente do Colegiado