Quando os algoritmos genéticos são uma boa opção para otimização?

20

Os algoritmos genéticos são uma forma de método de otimização. Frequentemente, a descida do gradiente estocástico e seus derivados são a melhor opção para otimização de funções, mas algoritmos genéticos ainda são usados ​​algumas vezes. Por exemplo, a antena da sonda ST5 da NASA foi criada com um algoritmo genético:

Antena ST5

Quando os métodos de otimização genética são uma escolha melhor do que os métodos mais comuns de descida por gradiente?

Gus
fonte
7
+1 no exemplo, encontrei o artigo original: alglobus.net/NASAwork/papers/Space2006Antenna.pdf
Tim

Respostas:

19

Os algoritmos genéticos (AG) são uma família de heurísticas que são empiricamente boas em fornecer uma resposta decente em muitos casos, embora raramente sejam a melhor opção para um determinado domínio.

Você menciona algoritmos baseados em derivadas, mas mesmo na ausência de derivadas, existem muitos algoritmos de otimização sem derivadas que têm um desempenho muito melhor que os GAs. Veja esta e esta resposta para algumas idéias.

O que muitos algoritmos de otimização padrão têm em comum (mesmo métodos livres de derivativos) é a suposição de que o espaço subjacente é uma variedade suave (talvez com algumas dimensões discretas), e a função de otimizar é um pouco comportada.

No entanto, nem todas as funções são definidas em um coletor suave. Às vezes, você deseja otimizar sobre um gráfico ou outras estruturas discretas (otimização combinatória) - aqui existem algoritmos dedicados, mas os GAs também funcionam.

Quanto mais você avança para funções definidas em estruturas complexas e discretas, mais AGs podem ser úteis, especialmente se você puder encontrar uma representação na qual os operadores genéticos trabalhem da melhor maneira possível (o que exige muito conhecimento de domínio e ajuste de mão).

Obviamente, o futuro pode levar a esquecer completamente os AGs e desenvolver métodos para mapear espaços discretos em espaço contínuo e usar o mecanismo de otimização que temos na representação contínua.

lacerbi
fonte
2

Os métodos genéticos são adequados para a otimização multicritério quando a descida em gradiente é dedicada à otimização de monocriteria. A descida em gradiente permite encontrar o mínimo de funções quando existem derivadas e existe apenas uma solução ótima (se nós, exceto os mínimos locais). Um algoritmo genético pode ser usado em problemas multicritério e levar a um continuum de soluções, cada uma sendo indivíduos de uma população, tendo evoluído de uma população inicial. Os valores a serem otimizados são os fenótipos dos indivíduos e pode haver vários fenótipos. Geralmente, nenhum indivíduo tem simultaneamente o melhor valor de cada fenótipo; portanto, não há apenas uma solução. Os indivíduos da população final, que são todas soluções da otimização, fazem parte da "frente de Pareto" e são marcados como "Pareto no primeiro lugar" indivíduos. Isso significa que, em comparação com todos os outros indivíduos com o mesmo desempenho para cada fenótipo, eles são pelo menos melhores para um fenótipo do que os outros.

manu190466
fonte
Ok para um voto negativo, mas você poderia explicar onde estou errado?
precisa saber é o seguinte
5
Este site valoriza respostas que fornecem contexto e plano de fundo. Consulte esta página de ajuda para saber como fornecer respostas que serão adicionadas ao nosso repositório de respostas úteis para perguntas interessantes. Explicar sua resposta também é uma boa maneira de testar seu próprio entendimento. Por exemplo, nesse caso, você pode querer expandir como os algoritmos genéticos "são adequados para a otimização de vários critérios", pois a página da Wikipedia parece implicar funções de aptidão com valor único como objetivos para algoritmos genéticos.
EdM
0

Melhor em que sentido?

Na minha experiência, os AGs são um dos otimizadores mais pragmáticos. Embora muitos algoritmos mais precisos exijam tempo e esforço para formalizar problemas reais no mundo matemático, os AGs podem lidar com qualquer função de custo com regras e restrições complexas (os GAs são relacionados por uma abordagem de execução posteriormente e não por cálculos específicos). Esse processo é direto e você pode tentar várias abordagens para o trabalho exploratório.

Aprecio também a possibilidade de reinjetar soluções anteriores do algoritmo para execuções futuras, o que é bom para tarefas repetidas.

Conceitualmente, um algoritmo genético pode ser representado por um hashmap de funções e combina com linguagens funcionais, bem como o Clojure, que também é uma linguagem na qual você pode obter grandes resultados rapidamente.

Algoritmos genéticos também podem ser aninhados: a função de custo de um AG pode ser um AG! Esses algoritmos aproveitam o hardware e a infraestrutura modernos, que permitem calcular uma população muito grande para que, mesmo com operações simples de mutação / seleção, você ainda possa obter bons resultados.

Mesmo para problemas simples, como encontrar o mínimo de uma função de onda, os AGs não são tão ruins e podem alcançar uma precisão decente em um tempo aceitável.

Então, sim, as soluções analíticas podem ter um tempo de execução e precisão mais rápidos, mas o tempo necessário para produzi-las supera os benefícios geralmente esperados! Então quando ? Quase todas as vezes para mim, pelo menos para meta-otimização.

Joseph Yourine
fonte
O principal argumento desse argumento parece ser que os algoritmos genéticos são otimizadores de caixa preta. Mas existem muitos otimizadores de caixa preta por aí. Por que isso seria melhor do que outras opções? Além disso, não acho que seja realmente o caso de os GA poderem lidar com restrições com facilidade. Por exemplo, se a função for indefinida, exceto por um subespaço 3D em um mundo 4D, certamente um GA de baunilha falhará.
Cliff AB
@CliffAB Na verdade, eu não disse nada sobre isso e talvez mais o contrário. No GA, você tem muito controle sobre o cálculo do núcleo, o GA em si é uma sequência de etapas e pedidos leves. Ao definir funções de custo, você pode manipular qualquer coisa na função, mesmo restrições externas que você pode consultar. Meus argumentos principais são: lide com muitos problemas, você não precisa se preocupar com a compatibilidade com a estrutura (você só tem que devolver um custo), encontre uma solução decente da vida real na maioria dos casos de negócios, mesmo que nem sempre o melhor
Joseph Yourine 15/06