Investigação Experimental usando Algoritmos Populacionais em Ambientes Ruidosos.
Nome: EDUARDO MENDEL DO NASCIMENTO
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 01/07/2011
Orientador:
Nome |
Papel |
|---|---|
| THOMAS WALTER RAUBER | Orientador |
Banca:
| Nome |
Papel |
|---|---|
| FLÁVIO MIGUEL VAREJÃO | Examinador Interno |
| ISABEL CRISTINA MELLO ROSSETI | Examinador Externo |
| THOMAS WALTER RAUBER | Orientador |
Resumo: O objetivo principal deste trabalho é a realização de um estudo investigativo experimental de algoritmos populacionais em ambientes ruidosos. Quatro versões do algoritmo Particle Swarm (PSO) foram adotadas nos experimentos. São elas: PSO canônico (topologia global), PSO padrão (topologia local), Bare Bones (BBPSO) e Fully Informed Particle Swarm (FIPS). Através de cooperação, as abordagens de otimização baseadas em população frequentemente encontram soluções satisfatórias com eficácia e eficiência. Entretanto, a maioria das versões desenvolvidas nos últimos anos apresenta dificuldades na otimização de funções com muitos mínimos locais em espaços de alta dimensão. Foi analisado o comportamento de uma estratégia denominada de estratégia de jump em ambientes incertos com a finalidade de estudar melhorias no desempenho dos métodos investigados, tanto no contexto estático quanto ruidoso.
Inicialmente, os algoritmos populacionais foram investigados com a estratégia de jump com objetivo de escapar de mínimos locais. O jump é utilizado quando não são observadas melhorias durante o processo de otimização. Essa abordagem foi apresentada primeiramente com base nas distribuições de probabilidade Gaussiana e de Cauchy. Testes experimentais foram conduzidos em um conjunto bem conhecido de problemas multimodais, com muitos mínimos locais. Os resultados obtidos sugerem que as versões híbridas dos algoritmos populacionais são capazes de superar o desempenho de suas respectivas versões originais. Conclui-se que a estratégia de jump é bastante eficaz no combate à convergência prematura. A melhoria no desempenho é consequência de um pequeno, mas importante, número de saltos bem sucedidos.
Em virtude dos resultados promissores obtidos com os algoritmos populacionais combinados com a estratégia de jump, essa abordagem foi expandida e, ao invés, de gerar números randômicos segundo distribuições de probabilidade, optou-se por utilizar sequências caóticas. As quatro versões do PSO foram novamente investigadas com objetivo de analisar a habilidade da estratégia modificada em permitir que indivíduos em regime de estagnação escapem de atratores sub-ótimos. Resultados de simulação demonstram que a adição de saltos caóticos impulsiona o desempenho dos algoritmos em comparação com as abordagens utilizando distribuição de probabilidade. Além disso, a estratégia populacional com caos possui custo computacional inferior.
Na sequência do trabalho, o foco é a investigação da introdução de jump com caos nos algoritmos populacionais aplicados, entretanto, a problemas de otimização ruidosos, com adição de incerteza às funções de teste. O método híbrido é analisado experimentalmente em diversas funções benchmarks. Resultados de simulação indicam que a adição da estratégia de jump é benéfica em termos de robustez. Em ambientes ruidosos, um algoritmo para ser considerado robusto precisa alcançar sistematicamente uma solução satisfatória. Não é suficiente obter bons resultados sob baixos níveis de ruídos e degradar a solução à proporção que o nível de ruído aumenta. Conclui-se que embora o desempenho dos algoritmos populacionais deteriore com o aumento no nível de ruído, as soluções encontradas pelas versões modificadas são superiores às soluções obtidas pelas versões originais. A estratégia de saltos, adicionada aos algoritmos populacionais, aplicada tanto em funções estáticas quanto em funções ruidosas demonstrou ser bastante eficiente e eficaz, pois aumenta a chance do algoritmo escapar de mínimos locais. A abordagem analisada é simples e de fácil implementação, sem nenhum acréscimo de esforço computacional. O uso de sequências caóticas em substituição às distribuições de probabilidade contribui para a eficiência da abordagem.
