Combinação de Metaheurísticas e Busca Local Determinística Independente de Derivadas
Viviane Galvão1; Helio Barbosa2
1 UFJF; 2 LNCC e UFJF
doi:10.20906/CPS/CILAMCE2015-0376
Resumo
O objetivo, aqui, é resolver problemas de otimização em espaço de busca contínuo, que possuem análise de sua diferenciabilidade inviável e sua avaliação tem alto custo computacional. Como exemplo, pode-se citar o caso em que a função objetivo requer a execução de um simulador. Esse tipo de problema é chamado de caixa-preta e apenas técnicas de otimização que não utilizam informação da forma analítica da função objetivo podem ser adotadas. Neste contexto, o trabalho aqui apresentado propõe a combinação de métodos estocásticos e determinísticos para resolver os tipos de problemas citados. Como métodos estocásticos, foram estudadas as metaheurísticas de Otimização por Enxame de Partículas e Estratégia Evolutiva. A Otimização por Enxame de Partículas é um método que foi inspirado no comportamento social de bandos de pássaros a procura de alimentos, simulando dos mecanismos de inteligência coletiva. A Estratégia Evolutiva é um método baseado no modelo biológico de processos de adaptação e evolução de espécies, para o qual tem-se uma população de indivíduos sujeitos à mutação e seleção, onde os mais aptos tem mais chance de sobreviver. A estratégia determinística adotada aqui é uma Busca Padrão, um método que não faz uso das derivadas da função objetivo, que opera movimentos exploratórios através de dois passos: o passo de sondagem do espaço e o passo de avaliação, que é executado se o passo de sondagem falhar. A proposta da combinação dessas duas classes de métodos induz à junção das características positivas de tais com o intuito de obter melhores soluções com a mesma quantidade de cálculos da função objetivo, tornando a busca mais eficaz. Experimentos computacionais serão feitos para a resolução de problemas-testes disponíveis na literatura e os resultados encontrados serão utilizados para analisar o impacto no desempenho pela incorporação da busca local nas metaheurísticas consideradas aqui.
Palavras-chave: Otimização Sem Uso de Derivadas; Metaheurística; Busca Padrão