Investigando Métodos de Aprendizado em uma Arquitetura de Hibridização de Meta-heurísticas para Problemas com Decisões em Múltiplos Níveis
Hibridização de Meta-heurísticas, Matheurística, Aprendizado por Oposição, Aprendizado Ortogonal, Problema do Caixeiro Viajante Alugador com Passageiros.
Este trabalho estende os recursos de uma arquitetura multiagente para hibridização de meta-heurísticas incluindo técnicas de aprendizado e de Programação Matemática. As técnicas de aprendizagem abordadas são o Projeto Ortogonal e a Oposição. A forma da aplicação de tais técnicas é inovadora contemplando a aprendizagem dos agentes quanto à escolha de heurísticas a serem aplicadas em diferentes momentos da busca. Esta abordagem é comparada à utilização das técnicas de aprendizagem conforme o modo de aplicação tradicional verificado em trabalhos da literatura. Outra contribuição é a inclusão de técnicas de Programação Matemática, o que produz algoritmos matheurísticos. A utilização de métodos de Programação Matemática também é um elemento inovador uma vez que poucas arquiteturas para hibridização de meta-heurísticas contem tal recurso. Este trabalho propõe uma 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. Este problema, que pertence à classe NP-difícil, exige a tomada de decisão em três diferentes níveis: rota, tipo de carro utilizado e atendimento de demanda por caronas. São relatados os resultados de experimentos 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.