APLICAÇÃO DO ALGORITMO GENÉTICO DE CHAVES ALEATÓRIAS VICIADAS NO PROBLEMA DA MOCHILA NÃO LINEAR SEPARÁVEL

Abstract

O problema da mochila não linear separável (NLKP) é uma variação do problema clássico da mochila no qual a função objetivo e/ou a restrição são não lineares e todas as funções são separáveis. A versão do NLKP quando a função objetivo é não convexa não tem sido muito estudada na literatura e não são conhecidos algoritmos exatos para encontrar soluções ótimas para aplicações práticas em um tempo computacional adequado. Procedimentos meta-heurísticos são usados nestes casos e uma recente estrutura algorítmica chamada Algoritmo Genético de Chaves Aleatórias Viciadas (BRKGA) foi utilizada ao longo deste trabalho a fim de resolver o NLKP. O procedimento BRKGA pe inspirado no Algoritmo Genético de Chaves Aleatórias, onde cada cromossomo é tomado como um vetor de números reais gerados aleatoriamente no intervalo [0,1). As nossas experiências computacionais consistiram na implementação de um decodificador BRKGA e aplicá-lo a várias instâncias a partir da literatura ao NLKP. Resultados computacionais satisfatórios foram observados para pequenas e médias instâncias em comparação com uma heurística construtiva específica para o problema.