Investigação da Adição de Métodos de Aprendizado e Programação Matemática em uma Arquitetura de Hibridização de Meta-heurísticas para Problemas de Otimização com Decisões em Múltiplos Níveis
Hibridização de Meta-heurística, Matheurística, Aprendizado por Oposição, Aprendizado Ortogonal, Problema do Caixeiro Viajante Alugador com Passageiros, Cabeamento de Usinas Eólicas.
A hibridização de meta-heurísticas é um tópico que vem sendo estudado por diversos pesquisadores dado ao seu potencial de produzir heurísticas mais eficientes do que aquelas baseadas em uma única técnica. Tal hibridização, entretanto, não é uma tarefa fácil, uma vez que existem diversas maneiras de operacionaliza-la. A tarefa se torna ainda mais difícil quando existem três ou mais métodos meta-heurísticos a serem hibridizados ou quando se deseja adicionar métodos de Programação Matemática, construindo, assim, matheurísticas. Diversos métodos foram propostos para hibridizar meta-heurísticas, incluindo algumas técnicas que automatizam a hibridização, como é o caso de arquiteturas multi-agentes. Um pequeno número destas arquiteturas se utiliza de técnicas de aprendizado e um número ainda mais restrito lida com matheurísticas. Este trabalho estende os recursos da Arquitetura Multi-agentes para Hibridização de Meta-heurísticas incluindo técnicas de aprendizado e de Programação Matemática. A forma da aplicação das técnicas de aprendizado é inovadora contemplando à escolha feita pelos agentes de heurísticas a serem aplicadas em diferentes momentos da busca. Este trabalho propõe uma nova forma de hibridização hierárquica para problemas de Otimização Combinatória que possuem múltiplos níveis de decisão. As propostas algorítmicas são testadas no Problema do Caixeiro Viajante Alugador com Passageiros e no Problema de Cabeamento em Usinas Eólicas. Este problemas pertencem à classe NP-difícil e exigem a tomada de decisão em mais de um nível. No caso do Caixeiro Viajante Alugador com Passageiros a tomada de decisão se dá em três níveis: rota, tipos de carros utilizados e atendimento de demanda por caronas. No caso do cabeamento em usinas eólicas são exigidas decisões do local de cabeamento e tipo de cabo a ser empregado em cada trecho. Os experimentos para o Caixeiro Viajante Alugador com Passageiros foram feitos para três classes de instâncias, em um total de noventa e nove casos de teste com tamanho variando de 4 a 80 cidades, 2 a 5 veículos e 10 a 240 pessoas demandando transporte. O Problema de Cabeamento em Usinas Eólicas foi alvo de experimentos que envolveram um conjunto de 200 instâncias. Essas instâncias são simulações de situações reais desenvolvidas em colaboração com especialistas da área. As abordagens propostas neste trabalho são comparadas a algoritmos do estado-da-arte para ambos os problemas.