Melhorando a Otimização com Algoritmos Assistidos por Surrogates

Quando tentamos descobrir as melhores soluções para problemas complexos, muitas vezes nos deparamos com os chamados problemas de otimização caros. Esses problemas demandam muito tempo e recursos para avaliar completamente cada possível solução. Os Algoritmos Evolutivos assistidos por substitutos (SAEAs) surgiram como ferramentas úteis para enfrentar esses desafios. Eles combinam os pontos fortes dos algoritmos evolutivos tradicionais com modelos econômicos que podem prever resultados sem precisar fazer todos os cálculos.

Este estudo foca em melhorar os SAEAs usando soluções que ainda não foram avaliadas. A ideia principal é aprimorar a forma como escolhemos novas soluções no Processo de Otimização. O método tradicional avalia apenas um número limitado de soluções, o que pode reduzir a qualidade geral das soluções geradas. Este artigo sugere um método para utilizar de maneira eficiente as soluções não avaliadas, a fim de melhorar o processo de otimização.

#Contexto

#Problemas de Otimização Caros

Problemas de otimização caros aparecem em várias áreas, incluindo engenharia, finanças e pesquisa científica. Esses problemas frequentemente envolvem funções complexas que são difíceis de avaliar rapidamente. Por exemplo, uma função pode exigir simulações extensas ou testes laboratoriais, tornando impraticável avaliar cada solução possível. Portanto, é necessária uma abordagem melhor para lidar com esses desafios.

#Algoritmos Evolutivos

Algoritmos evolutivos são comumente usados para encontrar soluções ótimas para problemas difíceis. Eles imitam o processo de seleção natural, usando técnicas como reprodução, mutação e seleção para evoluir soluções ao longo do tempo. Embora sejam ferramentas poderosas, eles têm suas limitações quando aplicados a problemas de otimização caros. Um grande problema é que eles muitas vezes não conseguem avaliar completamente cada solução candidata.

#Modelos Substitutos

Para contornar os altos custos de avaliar soluções diretamente, modelos substitutos são usados. Esses modelos aproximam a função real que precisa ser otimizada, permitindo avaliações mais rápidas. Eles podem ser treinados com dados de soluções previamente avaliadas para prever o desempenho de soluções não avaliadas. Assim, os modelos substitutos podem ajudar a guiar a busca por melhores soluções sem precisar avaliar cada uma em detalhes.

#Declaração do Problema

Um dos principais desafios dos SAEAs atuais é a falta de Diversidade na população de soluções. Quando apenas um pequeno número de soluções é avaliado por geração, a população pode se tornar semelhante, levando a um desempenho ruim. Isso resulta em soluções geradas que não exploram efetivamente o espaço de busca.

Este artigo aborda esse problema propondo uma estrutura que integra soluções não avaliadas no processo de seleção. Usando modelos substitutos, podemos identificar soluções promissoras sem precisar avaliar cada uma delas. Essa abordagem não só economiza recursos computacionais, mas também aumenta a diversidade da população, que é crucial para uma otimização eficaz.

#Metodologia

#Estrutura Proposta

A estrutura proposta usa soluções não avaliadas junto com soluções avaliadas para gerar novas soluções. A cada geração, a melhor solução avaliada é escolhida para avaliação real. Junto a isso, algumas soluções não avaliadas, com alto potencial, são usadas diretamente para produzir novas soluções sem precisar de avaliação. Essa abordagem dupla melhora a exploração do espaço de busca enquanto mantém a eficiência.

#Modelos Substitutos

Para garantir a seleção eficaz de soluções avaliadas e não avaliadas, dois tipos de modelos substitutos são introduzidos. Esses modelos focam em entender a relação entre soluções ao invés de avaliá-las isoladamente.

1. Critério Baseado em Fitness: Este modelo avalia pares de soluções com base em seus valores de fitness. Ajuda a identificar quais soluções são superiores em relação a outras.

2. Critério Baseado em Categoria: Este modelo categoriza soluções com base em seus níveis de fitness e atribui rótulos às relações entre soluções. Ele fornece uma visão mais ampla ao entender como as soluções se comparam entre diferentes grupos.

Ambos os modelos são projetados para trabalhar juntos, permitindo que o algoritmo tome decisões mais informadas ao selecionar soluções para otimização.

#Integração de Soluções Não Avaliadas

A estrutura utiliza soluções não avaliadas para impulsionar a geração de novas soluções. Após as avaliações iniciais, um segmento da população que não foi formalmente avaliado ainda é incluído. Os modelos substitutos, então, ajudam na criação de soluções filhas ao aproveitar dados tanto avaliados quanto não avaliados. Essa integração garante que o algoritmo não dependa apenas de algumas soluções avaliadas, mas sim se beneficie de um maior grupo de candidatos potenciais.

#Processo de Seleção

O processo de seleção envolve gerar um conjunto de soluções de teste usando várias heurísticas. Uma vez geradas, os modelos substitutos são aplicados para avaliar a qualidade dessas soluções. A melhor solução é escolhida para avaliação real, e certas soluções não avaliadas são selecionadas para contribuir diretamente para a próxima geração de soluções. Essa combinação visa melhorar a diversidade da população e acelerar a convergência em direção às soluções ótimas.

#Estudo Experimental

#Conjuntos de Teste

Para validar a estrutura proposta, experimentos foram realizados usando dois conjuntos de teste bem conhecidos. Esses conjuntos consistem em uma variedade de funções com diferentes características, permitindo uma avaliação abrangente do desempenho do algoritmo em cenários variados.

1. Conjunto de Teste LZG: Inclui funções que apresentam uma mistura de paisagens, desde unimodais até multimodais.

2. Conjunto de Teste YLL: Contém funções com várias características, incluindo paisagens em passos e funções com ruído aleatório.

#Algoritmos para Comparação

O desempenho da estrutura proposta foi comparado com vários algoritmos estabelecidos, divididos em três categorias principais:

1. Algoritmos Evolutivos Básicos: Como CMA-ES e EDA/LS. Esses algoritmos não são especificamente projetados para otimização cara, mas servem como base de comparação.

2. Algoritmos de Otimização Bayesiana: Como Skopt, que utilizam modelos probabilísticos para aprimorar o processo de busca.

3. Algoritmos Evolutivos Assistidos por Substitutos: Incluindo FCPS-CoDE e GPEME, conhecidos por sua integração de modelos substitutos na avaliação de soluções candidatas.

Cada algoritmo foi executado várias vezes para considerar variações nos resultados, garantindo uma análise robusta.

#Resultados

Os resultados dos experimentos mostraram que a abordagem proposta superou os outros algoritmos na maioria dos cenários. Por exemplo, ela consistentemente alcançou valores de função objetivo mais baixos nas funções de teste, indicando um desempenho superior. Análises estatísticas, incluindo o teste de Friedman e o teste de soma de postos de Wilcoxon, confirmaram essas conclusões, demonstrando a eficácia do uso de soluções não avaliadas no processo de otimização.

#Importância da Diversidade

Os experimentos destacaram a importância de manter a diversidade dentro da população de soluções. Quando apenas uma ou poucas soluções são selecionadas para avaliação, o algoritmo tende a perder variedade, levando à estagnação. Ao incorporar soluções não avaliadas, o algoritmo pode explorar um espaço de busca mais amplo, reduzindo as chances de ficar preso em ótimos locais.

Além disso, a capacidade de aproveitar modelos substitutos para avaliar o fitness e a categorização das soluções melhora o processo de tomada de decisão. Essa estratégia permite que o algoritmo faça seleções informadas que guiam melhor a busca por soluções ótimas.

#Conclusão

Em conclusão, o método proposto de integrar soluções não avaliadas no framework do algoritmo evolutivo assistido por substitutos apresenta uma melhoria significativa em relação aos métodos tradicionais. Ao focar nas relações entre as soluções em vez de avaliá-las isoladamente, o algoritmo pode manter a diversidade na população enquanto otimiza o uso de recursos. O uso de modelos substitutos permite previsões eficazes, aprimorando ainda mais a capacidade do algoritmo de encontrar soluções ótimas em problemas de otimização caros.

Pesquisas futuras podem expandir esse trabalho explorando estratégias adicionais para utilizar de forma eficaz soluções não avaliadas. Também há potencial para aplicar a estrutura proposta a outros tipos de algoritmos e domínios de problemas, o que pode levar a mais avanços nas técnicas de otimização.