Inteligencia computacional

Inteligência Computacional para Otimização, Notas de aula, 2011/1 c ∞ Departamento de Computação, Universidade Federal de Ouro Preto.

Inteligência Computacional para Otimização
Marcone Jamilson Freitas Souza, Departamento de Computação, Instituto de Ciências
Exatas e Biológicas, Universidade Federal de Ouro Preto, 35400-000 Ouro Preto, MG. Homepage: http://www.iceb.ufop.br/decom/prof/marcone, E-mail: [e-mail]

Sumário
1 Introdução

2

2 Heurísticas Construtivas

3

3 Heurísticas de Refinamento
3.1 Método da Descida/Subida (Descent/Uphill Method) .
3.2 Método de Primeira Melhora . . . . . . . . . . . . . .
3.3 Método de Descida/Subida Randômica . . . . . . . . .
3.4 Método Não Ascendente/Descendente Randômico . . .
3.5 Descida em Vizinhança Variável . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

9
10
13
13
14
14

4 Metaheurísticas
4.1 Multi-Start . . . . . . . . . . . . . . . . .
4.2 Simulated Annealing . . . . . . . . . . . .
4.3 Busca Tabu . . . . . . . . . . . . . . . . .
4.4 GRASP . . . . . . . . . . . . . . . . . . .
4.5 Busca em Vizinhança Variável . . . . . . .
4.6 Iterated Local Search . . . . . . . . . . . .
4.7 Guided Local Search . . . . . . . . . . . .
4.8 Algoritmos Genéticos . . . . . . . . . . . .
4.8.1 Descrição genérica do método . . .
4.8.2 Representação genética de soluções
4.8.3 Operador crossover clássico . . . .
4.8.4 Operador mutação clássico . . . .
4.8.5 Operadores crossover para o PCV
4.9 Scatter Search . . . . . . . . . . . . . . . .
4.10 Colônia de Formigas . . . . . . . . . . . .
4.11 Algoritmos Meméticos . . . . . . . . . . .
4.12 Annealing Microcanônico . . . . . . . . .
4.13 Otimização Microcanônica . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.