Busca difusa

Disponível somente no TrabalhosFeitos
  • Páginas : 18 (4373 palavras )
  • Download(s) : 0
  • Publicado : 30 de maio de 2012
Ler documento completo
Amostra do texto
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égiasoriginalmente 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. Sendoassim, 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 umconjunto 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 maisdetalhada.


Em Laguna e Martí (2003) lançaram o primeiro livro sobre Busca Difusa. Nele, os autores realizam um estudo detalhado sobre Busca Difusa, começando por alguns tutoriais básicos, revisando as estratégias mais avançadas e chegando até as linhas de investigação atuais.





O Algoritmo



O algoritmo da Busca Difusa inicia gerando um pequeno grupo de soluções, as quaisserão encaminhadas para uma função que irá gerar um conjunto maior de soluções.


As novas soluções geradas passarão por um método de busca local e serão encaminhadas para uma função que atualiza o conjunto referencial. O conjunto referencial é um conjunto de tamanho b, onde b é um número tipicamente pequeno, por volta de 20, que conterá as melhores soluções encontradas para o problema aolongo da execução do algoritmo.


É importante notar que nem todas as soluções farão parte do conjunto referencial, a função que o atualiza se encarregará de selecionar quais deverão entrar usando critérios de qualidade e diversidade.


Uma vez que o conjunto referencial esteja completamente preenchido, uma função receberá as soluções nele contidas e irá gerar a partir delassubconjuntos. Esses subconjuntos serão combinados para a geração de novas soluções, que por sua vez serão submetidas, na intensificação, a um método de busca local, o mesmo utilizado anteriormente no algoritmo.


Após passarem pela busca local, as soluções serão encaminhadas para o atualizador do conjunto referencial, como feito anteriormente.


Os passos de gerar subconjuntos,combinar soluções, intensificá-las e atualizar o conjunto referencial, se repetem até que seja satisfeita uma das duas condições de parada do algoritmo:
i. Se em uma dada iteração, nenhuma solução conseguir entrar no conjunto referencial.


Ou


ii. Se for atingido um número específico de iterações.



Figura 1



























“O...
tracking img