Perfil del docente y uso de las TIC

Segundo GOLDBARG e LUNA (2000), o termo heurística é derivado do grego heriskein, que significa descobrir ou achar. Segundo os mesmos autores, o significado da palavra em Pesquisa Operacional vai um pouco além de sua raiz etimológica e define uma heurística como “um método de busca de soluções em que

não existe qualquer garantia de sucesso”. O sucesso do método pode ser expresso

quantitativa ou qualitativamente. Em um problema de otimização o sucesso pode ser representado pela obtenção da solução ótima. Alguns autores entendem que a possibilidade de fracasso seja extensiva até para a obtenção de uma solução viável (GOLDBARG e LUNA, 2000). Entretanto, GOLDBARG e LUNA (2000), afirmam não comungarem da idéia e aprofundam a definição da seguinte forma: “uma

heurística é uma técnica que busca alcançar uma boa solução utilizando um esforço computacional considerado razoável, sendo capaz de garantir a viabilidade ou a otimalidade da solução encontrada ou ainda, em muitos casos, ambas, especialmente nas ocasiões em que essa busca partir de uma solução viável e próxima ao ótimo”.

Segundo Zanakis et al.(1981), citado por IGNACIO et al. (2000) uma heurística pode ser definida como "um procedimento simples e rápido, geralmente

baseada no sentido comum e se supõe que ofereça uma boa solução (não necessariamente a ótima) no tratamento de problemas complexos".

Murray e Church (1995a), citados por MURRAY (1999), generalizaram o processo de solução das heurísticas busca aleatória, interchange, simulated

sido desenvolvido para ilustrar o processo geral de solução daquelas heurísticas, ele se aplica a maioria das outras técnicas heurísticas. De acordo com a Figura 1, o processo de busca inicia com a geração de uma solução inicial viável, gerada aleatoriamente ou baseada em algoritmos de geração apropriados. Um critério de parada é então utilizado para testar se a busca continua ou não. Se o critério é atendido, o processo é interrompido; caso contrário um processo para modificar a solução corrente é empregado para identificar uma nova solução viável. Se a solução viável alternativa é encontrada, então a nova solução é aceita. Caso contrário, a nova solução é eliminada, e o processo continua com a solução não modificada. Novamente, o critério de parada é testado para decidir se o processo será interrompido ou seguirá com a busca. Segundo MURRAY (1999), as principais diferenças entre as técnicas heurísticas estão na forma de modificação da solução corrente e no critério de avaliação empregado para determinar se a nova solução é aceita ou não. Outra observação em relação ao processo de busca ilustrado na Figura 1, refere-se à viabilidade da solução. Devido à dificuldade em identificar soluções viáveis em muitos problemas, é comum a alteração dessa regra para aceitar soluções inviáveis, porém, aplicando-se a elas uma penalidade por violar alguma restrição do problema, conforme encontrado em BOSTON e BETTINGUER (1999). Este método, além de melhorar a performance da heurística, ao dispensar o teste de viabilidade da solução, pode funcionar como um artifício para direcionar busca para diferentes regiões do espaço de solução.

Iniciar Gerar solução inicial viável Continiuar a busca heurística? Modificar a solução corrente para produzir

uma solução viável alternativa

Aceitar a nova solução como solução viável

corrente

Rejeitar a solução - reter a solução viável anterior Aceitar a solução identificada Fim Sim Não Sim Não

Figura 1 - Processo geral de solução das heurísticas.

Em geral, as heurísticas requerem decisões em relação ao seguintes elementos (YOUSSEF et al, 2001):

• um mecanismo para geração da solução inicial de onde a busca iterativa irá partir;

• uma função de avaliação para avaliar as soluções encontradas durante a busca; • operadores de pertubação (movimentos) para criar novas soluções a partir de

uma dada solução corrente;

• escolha dos parâmetros do algoritmo; e • critério de parada.

Para IGNÍZIO E CAVALIER (1994), as heurísticas são as abordagens mais promissoras para solução de problemas de Programação Inteira. Segundo estes autores, enquanto os algoritmos exatos para solução de problemas de Programação Inteira garantem uma solução ótima para alguns problemas, as heurísticas não podem provar a otimalidade das suas soluções, mas oferecem, entretanto, soluções aceitáveis, inclusive para problemas complexos e de grande porte, com baixo custo computacional.

Segundo GOLDBARG e LUNA (2000), os primeiros métodos heurísticos eram associados a estratégias de enumeração incompleta, solução parcial ou relaxações e dentre muitas classificações possíveis para as heurísticas, sugeriram a apresentada na Figura 2.

A Figura 2 resume as várias abordagens conhecidas para os procedimentos heurísticos de solução. As heurísticas da linha clássica exploram, de modo casual, a estrutura do problema sem definir claramente uma estratégia universal de solução (GOLDBARG e LUNA, 2000). As primeiras heurísticas relatadas na literatura eram destinadas à solução de problemas específicos e não eram, via de regra, passíveis de serem utilizadas em outros problemas; as heurísticas clássicas de roteamento são um bom exemplo disso (GOLDBARG e LUNA, 2000). Entretanto, nos últimos 30 anos, pesquisadores da área de Pesquisa Operacional adaptaram idéias de outras áreas no desenvolvimento de metaheuríst icas (SOUZA e MOCCELLIN, 2000).

- Simulated Annealing - Tabu Search Clássica Reativa - GRASP - Miope Construtiva Por economia - Busca local Método descendente Método aleatório - Particionamento - Grupamento Procedimentos aproximativos Heurísticas Relaxações

Estocásticas Analógicas Clássicas Lagrangeana Linear

- Subgradiente - Ajuste Múltiplo - Dual Ascent - Redes neuronais - Computação evolutiva Algoritmos Genéticos Scatter Search Colônia de Formigas

Figura 2: Classificação das abordagens aproximativas (GOLDBARG e LUNA, 2000).

Segundo GOLDBARG e LUNA (2000), o termo metaheurística é reservado para um grupo especial das chamadas heurísticas estocásticas e

analógicas. As metaheurísticas são técnicas que, superpondo-se a métodos heurísticos de busca em vizinhança, guiam a busca com vistas à superação da

otimalidade local e à obtenção de soluções de qualidade superior (SOUZA e MOCCELLIN, 2000). Dentre as mais populares, inclui-se Simulated Annealing

(KIRKPARTRICK, 1983), Algoritmos Genéticos (HOLLAND, 1975) e Busca Tabu (GLOVER e LAGUNA, 1997). Segundo SOUZA e MOCCELLIN (2000),

tais métodos consistem de procedimentos de busca no espaço de soluções, definidos por estratégias que exploram apropriadamente a topologia de tal espaço. Segundo este mesmo autor, o sucesso das metaheurísticas se deve a fatores como: i) alusão a mecanismos de otimização da natureza (nos casos do

Algoritmo Genético e Simulated Annealing); ii) aplicabilidade geral da abordagem, i.e. existe invariavelmente uma estratégia geral de solução, cabendo apenas adaptá-la ao caso específico; iii) facilidade de implementação;

e iv) qualidade da solução obtida aliada a um esforço computacional