METAHEURISTIVA

INSTITUTO DE ENSINO E PESQUISA OBJETIVO - IEPO

Curso de Graduação em Ciência da Computação

ALCILENE FIALHO SOUZA

METAHEURISTICA

Palmas – TO

2013

ALCILENE FIALHO SOUZA

METAHEURISTICA

Artigo apresentado ao Instituo de Ensino e Pesquisa Objetivo

Professor Orientador: Wilson Costa

Palmas - TO

2013

2

ALCILENE FIALHO SOUZA

METAHEURISTICA

Alcilene Fialho Souza

Wilson Costa

Professor-Orientador

Palmas, 22 de junho de 2013.

3

INDICE

1.. Introdução............................................................................................4

2. O Que é Meta-Heurística .....................................................................5

3. Meta-heurística – Visão Geral..............................................................5

4. Meta-heurística construtivas.................................................................6

5. Meta-heurística de relaxação................................................................6

6 Meta-heurística de busca por entornos ................................................7

7. Sistemas Legados................................................................................9

8. Meta-heurística evolutivas....................................................................9

9. Outros tipos de Meta-heurística..........................................................11

10.Conclusão .........................................................................................14

11. Bibliografia........................................................................................15

4

1. Introdução

O emprego de metaheurísticas busca soluções para problemas e que tem-se revelado bastante eficaz, superando, inclusive, métodos tradicionais de otimização que envolvem processos mais determinísticos, como o uso de programação linear e inteira e programação por restrições. O uso de heurísticas tipo evolutiva usando algoritmos genéticos. Diversas técnicas na solução de um mesmo problema, permite comparar a eficácia e a eficiência das técnicas aplicadas a este problema específico, além de comparar as diferentes abordagens de uma mesma técnica, verificando os possíveis ganhos obtidos com o uso da hibridização.

5

2. O Que é Meta-heurísticas

As meta-heurísticas são estruturas algorítmicas gerais adaptáveis a diversos problemas de otimização. Muitos desses métodos têm sido amplamente estudados nas últimas décadas, resultando em algoritmos heurísticos de alta qualidade, que frequentemente superam até mesmo heurísticas especializadas. Porém, uma mesma meta-heurística dificilmente é adequada a diversos tipos de problemas. Além disso, implementações de meta-heurísticas normalmente requerem conhecimentos específicos consistentes sobre o problema que se deseja tratar.

As meta-heurísticas são estruturas algorítmicas gerais adaptáveis a diversos problemas de otimização. Muitos desses métodos têm sido amplamente estudados nas últimas décadas, resultando em algoritmos heurísticos de alta qualidade, que freqüentemente superam até mesmo heurísticas especializadas. Porém, uma mesma meta-heurística dificilmente é adequada a diversos tipos de problemas. Além disso, implementações realmente fortes de meta-heurísticas normalmente requerem conhecimentos específicos consistentes sobre o problema que se deseja tratar.

3. Meta-heurísticas – Visão Geral

Ainda que todos os procedimentos descritos por meta-heurísticas possam ser vistos como estratégias de busca, algumas características desses processos permitem classificar a maioria das meta-heurísticas em tipos bastante distintos, de acordo com a abordagem utilizada: evolução de populações compostas por soluções, construção gradual inteligente, busca por entornos e relaxação.

6

4. Meta-heurísticas construtivas

Uma meta-heurística construtiva estabelece estratégias para a construção de uma solução através da definição, de forma meticulosa, do valor de cada uma de suas componentes. Dentre essas meta-heurísticas, a mais clássica é a estratégia gulosa, formada por um processo iterativo que, em cada passo, adiciona um elemento à solução parcial, de forma a obter os melhores resultados imediatos possíveis. Um exemplo híbrido mais eficaz é a meta-heurística GRASP, formada pela repetição de um algoritmo de duas fases: construção gradual inteligente e busca por entornos. Na meta-heurística GRASP, a fase construtiva é um processo iterativo que parte de uma solução parcial vazia e, em cada passo: identifica todos os elementos que podem ser incorporados à solução parcial sem torná-la inviável; cria um subconjunto desses elementos, contendo apenas aqueles que causam aumento mínimo de custo (este é o aspecto “guloso” da meta-heurística); seleciona aleatoriamente um elemento desse subconjunto, acrescentando-o à solução parcial.

5. Meta-heurísticas de relaxação

As meta-heurísticas de relaxação realizam alterações na modelagem original do problema a ser resolvido, construindo, desta maneira, um problema mais simples, cuja solução pode ser encontrada com eficiência, fornecendo informações que guiarão o algoritmo na busca da solução do problema original. A qualidade de uma meta-heurística de relaxação, portanto, está relacionada quase exclusivamente à eficiência do processo de resolução do problema

7

relaxado e à