Tutorial das procuras Melhorativas

Este tutorial cobre os algoritmos de procura melhorativas. O nome "melhorativo" significa que a solução vai sendo melhorada. Parte-se de uma ou mais soluções completas, ou seja, temos todos os passos (ações) necessários para atingir o objetivo. No entanto procuramos melhorar por alteração de um ou mais passos (ações), ou então juntar partes de duas soluções para criar uma nova.

Como o objetivo está sempre atingido, pretendemos aqui optimizar a qualidade da solução.

Propõe-se que faça este tutorial da seguinte forma:

• Veja o material existente, tanto na bibliografia como nos vídeos se disponível;
• Veja os exemplos passo a passo e procure responder às questões antes de ver as respostas;
• Continue com os exemplos de execução, para mais testes práticos e consolidação da matéria.

Procuras Melhorativas (Algoritmos Evolutivos)

Leituras:

• Russell & Norvig: Capítulo 4 (secção 1)
• Eiben & Smith: Capítulos 2 a 6
• Bruke & Kendall: Capítulos: 5, 7 a 13

Nota: este tutorial tem de ser melhorado nos exemplos passo-a-passo, tendo apenas a escalada do monte e uma versão limitada do algoritmo genético. Na execução (TProcuraMelhorativa) é preciso mais algoritmos. Atualmente os algoritmos evolutivos têm uma boa implementação, tendo naturalmente ainda espaço para evoluir.

Vídeos (PVP 4B):

Exemplos passo a passo (PnP):

• 4 damas genético

Procuras Melhorativas (Algoritmos alternativos)

Exemplos passo a passo (PnP):

• 4 damas escalada

Exemplos de execução

1. 8 Damas CI (TCodificacaoInteira)
2. 8 Damas CP (TCodificacaoPermutacao)
3. Partição CB (TCodificacaoBinaria)