Os algoritmos genéticos são adequados para problemas como o problema de Knuth?
Todos nós sabemos que os algoritmos genéticos podem fornecer uma solução ótima ou quase ótima. Portanto, em alguns problemas como os NP-difíceis, com uma compensação entre o tempo e a solução ótima, a solução quase ótima é boa o suficiente.
Como não há garantia de encontrar a solução ótima, o GA é considerado uma boa escolha para resolver o problema de Knuth?
De acordo com Artificial intelligence: A modern approach (terceira edição), seção 3.2 (p. 73):
Knuth conjecturou que, começando com o número 4, uma sequência de operações fatoriais, raiz quadrada e piso alcançará qualquer número inteiro positivo desejado.
Por exemplo, 5 pode ser alcançado a partir de 4:
floor (sqrt (sqrt (sqrt (sqrt (sqrt ((4!))!))))))
Então, se temos um número (5) e queremos saber a seqüência das operações dos 3 mencionados para chegar ao número dado, cada gene do cromossomo será um número que representa uma determinada operação com um número adicional para (sem operação) e a função de adequação será a diferença absoluta entre o número dado e o número que obtemos aplicando as operações em uma determinada ordem para cada cromossomo (para min). Vamos considerar que o número de iterações (gerações) é feito sem solução ótima e o número mais próximo que temos é 4 (com adequação 1), o problema é que podemos obter 4 sem aplicar nenhuma operação em 4, enquanto para 5 precisamos muitas operações, de modo que a solução quase ótima não está nem perto da solução.
Então, o GA não é adequado para esse tipo de problema? Ou a representação cromossômica sugerida e a função de aptidão não são boas o suficiente?
Respostas
Antes de tentar responder à sua pergunta mais diretamente, deixe-me esclarecer uma coisa.
As pessoas costumam usar o termo algoritmos genéticos (AGs), mas, em muitos casos, o que eles realmente significam são algoritmos evolutivos (EAs), que é uma coleção de algoritmos de otimização baseados em população (ou seja, várias soluções são mantidas ao mesmo tempo) e abordagens inspiradas no darwinismo e na sobrevivência do mais apto . GAs é uma dessas abordagens, onde os cromossomos são binários e você tem a mutação e a operação de cruzamento. Existem outras abordagens, como estratégias de evolução ou programação genética .
Como você também notou, EAs são meta-heurísticas e, embora existam algumas pesquisas sobre suas propriedades de convergência [ 1 ], na prática, elas podem não convergir. No entanto, quando qualquer outra abordagem potencial falhou, os EAs podem ser definitivamente úteis.
No seu caso, o problema é realmente encontrar uma expressão de forma fechada (ou analítica ) de uma função, que é composta de outras funções menores. É para isso que a programação genética (em particular, GP baseada em árvore) foi criada. Na verdade, o problema de Knuth é uma instância particular do problema de regressão simbólica , que é um problema típico ao qual GP é aplicado. Portanto, GP é provavelmente a primeira abordagem que você deve tentar.
Enquanto isso, implementei um programa simples no DEAP que tenta resolver o problema de Knuth. Veja aqui . A adequação da melhor solução encontrada até agora (com alguma semente) é 4 e a solução é floor(sqrt(float(sqrt(4))))(aqui floatapenas converte a entrada em um número de ponto flutuante, para garantir a segurança do tipo). Usei a diferença como função de aptidão e executei o algoritmo GP por 100 gerações com 100 indivíduos para cada geração (o que não é muito!). Não ajustei muito os hiperparâmetros, então, talvez, com a semente e hiperparâmetros certos, você possa encontrar a solução certa.
Para atender às suas preocupações, em princípio, você poderia usar essa codificação, mas, como você observou, o GA poderia de fato retornar $4$ como a melhor solução (que não está tão longe de $5$), que você pode evitar que eu mate, a cada geração, quaisquer indivíduos que tenham exatamente esse valor.
Não gastei muito tempo em minha implementação e pensando sobre esse problema, mas, como disse acima, mesmo com programação genética e usando apenas as operações de Knuth, ele poderia ficar preso em ótimos locais. Você pode tentar aumentar minha (ou sua) implementação com outras operações, como multiplicação e adição, e ver se algo melhora.