A Reconexão de Caminhos e Busca Dispersa

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO

CURSO DE CIÊNCIA DA COMPUTAÇÃO

LUIZ COUTO MEIRELLES JÚNIOR

PATH RELINKING / SCATTER SEARCH

RECONEXÃO DE CAMINHOS / BUSCA DISPERSA

Vitória

2016

LUIZ COUTO MEIRELLES JÚNIOR

PATH RELINKING / SCATTER SEARCH: RECONEXÃO DE CAMINHOS / BUSCA DISPERSA

Trabalho de apresentação do curso de graduação apresentado à Universidade Federal do Espírito Santo, para introduzir Otimização e suas Meta Heurísticas sobre Reconexão de Caminhos e Busca Dispersa.

Orientador: Maria Cristina Rangel

Vitória

2016

“Participar na produção em massa pode permitir que um homem continue a ser um ser humano decente; na verdade, é algo tão vil que não o afecta necessariamente. Mas participar na produção em massa não permite que ele continue a ser um operário humano decente. A eficiência é menos complexa, hoje em dia. A ineficiência pode, por isso, passar facilmente por eficiência e ser, na verdade, eficiente.“

Fernando Pessoa, in 'Heróstato'

RESUMO

Reconexão de Caminhos e Busca Dispersa trabalham combinando soluções (busca local). A combinação entre soluções, bem como a aplicação de processos heurísticos contribuem para melhoria das soluções produzidas e significativamente para a qualidade de um método heurístico. Uma coleção com soluções diversas de boa qualidade frequentemente contém informações úteis para a construção de soluções ótimas.

ABSTRACT

Path Relinking and Scatter Search works combining solutions (local search). The combination of solutions and the application of heuristic processes contribute to improvement of solutions and produced significantly to the quality of a heuristic method. A collection of various solutions of good quality often contains useful information for the construction of optimal solutions.

SUMÁRIO

1 INTRODUÇÃO        6

2 DEFINIÇÕES        7

2.1 RECONEXÃO DE CAMINHOS        7

2.2 BUSCA DISPERSA        8

3 APLICAÇÕES (EXEMPLOS)        10

3.1 APLICAÇÃO RECONEXÃO DE CAMINHOS        10

3.2 APLICAÇÃO BUSCA DISPERSA        11

4 CONCLUSÃO        13

ANEXOS        15

ANEXO A        15

ANEXO B        15

1 INTRODUÇÃO

Meta Heurísticas, são técnicas abstratas utilizadas para problemas de otimização e são geralmente aplicadas a problemas que não se conhece um algoritmo eficiente (ter a resposta exata). Podem ser modeladas como problemas de maximizar ou minimizar uma função cujas variáveis tem certas restrições. De maneira geral, usam combinações de soluções e conhecimento histórico (soluções anteriores) para se guiarem e realizar suas buscas pela “vizinhança” evitando paradas prematuras em ótimos locais.

2 DEFINIÇÕES

Um algoritmo de busca local define, para cada solução, uma vizinhança composta por um conjunto de soluções com características “muito próximas". Dada uma solução corrente, uma das formas de implementar um algoritmo de busca local é percorrer a vizinhança dessa solução em busca de outra com valor menor (para um problema de minimização). Se tal solução vizinha for encontrada, torna-se a nova solução corrente e o algoritmo continua. Caso contrário, a solução corrente é um ótimo local em relação à vizinhança adotada. Segundo Glover pode-se estabelecer critérios para combinação promovendo assim uma solução mais adequada, conforme mostra ANEXO B.

2.1 RECONEXÃO DE CAMINHOS

Soluções em Reconexão de Caminhos são combinadas através da geração de caminhos entre elas (e passando por elas). Esses caminhos correspondem a movimentos em um espaço de vizinhanças. Durante a conexão entre soluções, pode-se eliminar (caso exista) a restrição de que as soluções devem ser viáveis. O algoritmo não ficará “desorientado“, uma vez que a viabilidade será recuperada em algum momento Podem ser consideradas mais de duas soluções por vez: partindo-se de uma delas, alteramos gradualmente suas características, de modo a incorporar atributos das demais soluções, dando preferência às soluções de menor custo e aos atributos consistentes. Exemplo: escolha sempre o vizinho mais próximo da solução de destino. Ao atingi-la, continue se distanciando da solução de origem, evitando se distanciar muito da solução de destino.

[pic 1]

Exemplo da construção de um caminho.

2.2 BUSCA DISPERSA

A Busca Dispersa proporciona o uso de estratégias flexíveis, que permitem o desenvolvimento de diferentes algoritmos com distintos graus de complexidade para as diferentes etapas da busca. E constrói soluções pela combinação de outras soluções, sendo projetada para trabalhar com um conjunto de soluções denominado Conjunto Referência, que contém boas soluções obtidas ao longo da busca, tendo critérios na diversidade. O método basicamente gera combinações de soluções referência para criar novas soluções do espaço de busca.

[pic 2]

Exemplo da Busca Dispersa

3 APLICAÇÕES (EXEMPLOS)

Para informações sobre quais aplicações podem se usar consulte o ANEXO A cuja tabela retirada do artigo do próprio autor (Glover) do método está disponível.

3.1 APLICAÇÃO RECONEXÃO DE CAMINHOS

A Meta Heurística Busca Dispersa pode ser usada no Problema de Clusterização (PC).

O PC consiste em agrupar os objetos de uma base de dados em subconjuntos disjuntos denominados clusters, de forma que os objetos (pontos) pertencentes a um mesmo cluster sejam similares entre si e, ao mesmo tempo, os objetos pertencentes a clusters diferentes apresentem alta dissimilaridade. Existe uma gama de aplicações do PC, como em Reconhecimento de Padrões, Formação de Células de Manufatura, Roteamento de Tráfego em Redes, Data Mining e etc. O critério de semelhança faz parte da definição do problema.