Publicado no Encontro de Saberes 2017
Evento: XXV Seminário de Iniciação Científica
Área: CIÊNCIAS EXATAS E DA TERRA
Subárea: Ciência da Computação
Órgão de Fomento: Universidade Federal de Ouro Preto
| Título |
| Aprimoramento do Algoritmo Variable Neighborhood Search implementado na metodologia CSO – Controle Supervisório e Otimização |
| Autores |
|
LUCAS DE JESUS SOUSA (Autor) Tatiana Alves Costa (Orientador) Wilingthon Guerra Zvietcovich (Co-Orientador) |
| Resumo |
| Este trabalho propõe a implementação de um conjunto de ações que visam o aprimoramento do algoritmo Variable Neighborhood Search (VNS), utilizado como técnica de otimização pela metodologia CSO – Controle Supervisório e Otimização. A CSO foi proposta pelos autores como sendo uma nova abordagem para se tratar problemas de sequenciamento de tarefas em sistemas flexíveis de manufatura. De acordo com esta abordagem, o algoritmo de otimização tem por finalidade realizar a busca pelo sequenciamento ótimo da produção, enquanto o controle supervisório tem o papel de codificar todas as restrições do problema. O algoritmo VNS é parte fundamental da metodologia CSO, uma vez que uma implementação eficiente deste método implica na obtenção de soluções de melhor qualidade, encontradas em um menor tempo de processamento. Ao longo desde trabalho foram feitas algumas adaptações na estrutura do VNS utilizado na metodologia CSO, a fim de torná-lo mais eficiente, permitindo uma busca mais eficaz no espaço de soluções do problema. O VNS adaptado trabalha em conjunto com um algoritmo de seleção clonal, que é utilizado para gerar soluções iniciais para o problema. Além disso, o novo VNS implementa funções oriundas da metaheurística Busca Tabu, permitindo que o algoritmo adaptado aceite, durante a busca, soluções que possam levar a uma piora no valor da função objetivo atual do problema. Isso evita que o algoritmo fique preso em ótimos locais. Os conceitos de lista e movimentos tabus também foram utilizados, no sentido de se evitar a ciclagem no código. Soluções com o mesmo valor de função objetivo também foram consideradas durante a busca, uma vez que, soluções diferentes podem levar a um mesmo valor de função objetivo. As duas versões do algoritmo VNS, original e adaptado, foram testadas em problemas testes bem bem conhecidos na literatura e os resultados obtidos demonstraram que o segundo algoritmo converge mais rapidamente que o primeiro, em todos os casos analisados. |
