Seleção Automática de Heurísticas para Alguns Problemas da Otimização Combinatória

O problema de seleção de algoritmos consiste em selecionar o melhor algoritmo para uma dada instância de um problema computacional, de acordo com alguma característica da instância. Apresenta-se, nesta tese, a análise e o desenvolvimento de agentes de natureza híbrida na seleção automática de heurísticas para instâncias de problemas da otimização combinatória, especialmente os problemas Max-SAT e Cobertura de Vértices Mínima. Primeiramente, é realizada uma análise teórica e experimental de um método de seleção de algoritmos para o problema Max-SAT, que escolhe entre resolver uma instância exata ou aproximadamente, com ganho de complexidade. Algumas inconsistências na formulação original foram detectadas e corrigidas. Uma modificação do método foi proposta para resolver um problema de natureza experimental, detectado no mecanismo de seleção do método. Em sequência, foi desenvolvido um modelo para seleção automática de heurísticas para os problemas Max-SAT e Cobertura de Vértices Mínima. O seu principal compontente, uma sequência de vértices a serem visitados e a ação tomada sobre eles, é chamado de heurística. A busca pela heurística que melhor resolve uma dada instância é realizada por meio de um Algoritmo Genético. Para um conjunto bem conhecido de heurísticas e instâncias de benchmark, demonstra-se que o modelo proposto apresenta bons resultados experimentais para os dois problemas, obtendo resultados melhores em uma fração significativa de casos.