Busca difusa

Busca Difusa

por

Leandro Paiva e Roberto Félix

Introdução

Scatter Search, ou Busca Difusa (também conhecida por Busca Dispersa), é do ponto de vista de classificação, uma meta-heurística evolutiva que constrói soluções através da combinação de outras soluções, tendo como raízes as estratégias originalmente propostas nos anos 60 para combinação de regras de decisão e restrições. Foi neste contexto que em 1977, Glover publicou a primeira descrição da Busca Difusa.

A partir desta publicação, ficou definido que o objetivo destes procedimentos é possibilitar que soluções baseadas em combinação de elementos, gerem soluções melhores que aquelas baseadas nos elementos originais. Sendo assim, a Busca Difusa realiza uma exploração sistemática sobre uma série de boas soluções, chamada conjunto referencial.

Observou-se que apesar de sua classificação, a Busca Difusa difere de outros métodos evolutivos, como por exemplo, os Algoritmos Genéticos, pelo fato de não estar fundamentada na aleatoriedade sobre um grande conjunto de soluções, mas em seleções sistemáticas sobre um conjunto pequeno, o conjunto referencial. Posteriormente iremos definir que a sistematologia adotada para geração das soluções vai tentar reunir critérios de qualidade e diversidade, adotando como fator primordial o primeiro para seleção de boas soluções.

Após anos de estudos, surgiram no inicio da década de 90 as primeiras aplicações, e desde então a Busca Difusa vem sendo aplicada com êxito na resolução de vários problemas de otimização.

Em 1996 ouviu-se falar pela primeira vez de uma combinação de soluções da Busca Difusa, chamada Path Relinking (Glover, 1996), um método também evolutivo que se baseia na geração de novas soluções mediante a exploração de trajetórias que conectam soluções de boa qualidade. Abordaremos o Path Relinking mais adiante, de uma maneira mais