Hibridação de um Algoritmo Genético com um
Método de Pesquisa em Padrão usando uma
Lagrangeana Aumentada
1Roman
Denysiuk, 2Isabel Espírito Santo, 2Lino Costa,2Edite Fernandes
1,2Centro
de Investigação Algoritmi
Minho University, Braga, Portugal
[email protected], 1{iapinho;lac;emgpf}@dps.uminho.pt
Os algoritmos genéticos, como a maioria dos algoritmos baseados em populações, são eficazes na identificação de zonas promissoras do espaço de
procura, mas menos bons em termos de precisão. Por outro lado, os algoritmos de procura local, como a pesquisa em padrão têm um bom
desempenho na melhoria da precisão da aproximação. Por isso, uma ideia promissora é combinar técnicas de optimização global e local. É proposto
um novo algoritmo genético híbrido com procura local que utiliza uma técnica baseada numa Lagrangeana aumentada para o tratamento de
restrições. Neste estudo, são testados diferentes esquemas relativos à escolha da população, bem como da forma como são integradas a procura
global e local. Foram usados perfis de desempenho (Dolan e Moré, 2002) para avaliar as várias versões do algoritmo proposto para um conjunto de
problemas de teste.
Algoritmo 1 - HGPSAL
Algoritmo 2
Algoritmo Genético
• Selecção por torneio
• SBX crossover
• Mutação polinomial
• Elitismo
Resultados
•
•
•
Foram resolvidos 24 problemas-teste de optimização global
Os problemas foram codificados em MatLab
Foram feitas 10 execuções de cada problema
• Versão 1 – melhorar o melhor ponto obtido por GA com HJ
• Versão 2 - melhorar os melhores 10% pontos da população obtidos por GA com HJ
• Versão 3 - melhorar os melhores 25% pontos da população obtidos por GA com HJ
• Versão 4 - melhorar os melhores 50% pontos da população obtidos por GA com HJ
Problema g02
Conclusões
• Um tamanho de população de s=min(200,10n) parece ser mais adequado para a generalidade dos problemas;
• A utilização de um número excessivo de pontos da população para serem melhorados por HJ conduz a resultados fracos;
• Prentede-se, de futuro, comparar com outras abordagens estocásticas, resolver outros problemas e melhorar a integração entre a pesquisa local e global.
2ª Escola Luso-Brasileira de Computação Evolutiva, 15 a 18 de Julho, Guimarães