Metaheurística em inteligência artificial

CENTRO UNIVERSITÁRIO DO LESTE DO MINAS GERAIS – UNILESTEMG COMPUTAÇÃO DE SISTEMAS DE INFORMAÇÃO – CSI 6º PERÍODO

TRABALHO DE INTELIGÊNCIA ARTIFICIAL ASSUNTO: METAHEURÍSTICA: DA TEORIA A PRÁTICA ALUNO: MARCOS GERALDO DE CASTRO JUSTINO CORONEL FABRICIANO, 7 DE MAIO DE 2010

Metaheurística A definição de metaheuristica pode‐se dizer que são metodos que podem lidar com qualquer problema de otimização e que não seja atrelado a um problema específico, define métodos aplicáveis a um extenso conjunto de problemas. Veremos alguns tipos de metaheurísticas: • Metaheurística de busca por entornos: Percorrem o espaço de busca levando em conta a “vizinhança” da solução em mãos, definida como o conjunto de soluções que podem ser obtidas a partir da aplicação de algum operador a solução atual. • Metaheurística de relaxação: Simplificam o problema e utilizam a solução como o guia para o problema original. • • Metaheurística construtiva: Definem de forma meticulosa o valor de cada componente de solução. Metaheurística evolutiva; Lidam com uma população de soluções, que evolui, através da interação de seus elementos. Definido alguns tipos de metaheurística, destacamos alguns exemplos de cada uma delas: Busca por entornos • • • GLS: busca monotônica, altera a função objetivo ao encontrar uma solução ótima; Busca Tabu: não monotônica, classifica como tabu os componentes de soluções adicionados ou removidos recentemente; Busca Reativa: Busca Tabu com detecção de ciclos.

Relaxação: • Relaxação Lagrangeana: remove algumas restrições de um problema de programação linear, atribui um peso a cada uma delas e altera a função objetivo para penalizar as soluções que seriam inviáveis no problema original. Construtiva: • GRASP (Greedy Randomized Adaptive Search Procedure): cada iteração é composta por uma fase construtiva e uma fase de busca por entornos. Em cada iteração da