Les algorithmes génétiques conviennent-ils à des problèmes tels que le problème de Knuth?
Nous savons tous que les algorithmes génétiques peuvent donner une solution optimale ou quasi optimale. Ainsi, dans certains problèmes comme les problèmes NP-difficiles, avec un compromis entre le temps et la solution optimale, la solution quasi optimale est suffisante.
Puisqu'il n'y a aucune garantie de trouver la solution optimale, GA est-il considéré comme un bon choix pour résoudre le problème Knuth?
D'après Intelligence artificielle: une approche moderne (troisième édition), section 3.2 (p. 73):
Knuth a supposé que, en commençant par le nombre 4, une séquence d'opérations factorielles, de racine carrée et de plancher atteindra n'importe quel entier positif souhaité.
Par exemple, 5 peut être atteint à partir de 4:
étage (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Donc, si nous avons un nombre (5) et que nous voulons connaître la séquence des opérations des 3 mentionnés pour atteindre le nombre donné, chaque gène du chromosome sera un nombre qui représente une certaine opération avec un nombre supplémentaire pour (pas d'opération) et la fonction de fitness sera la différence absolue entre le nombre donné et le nombre que nous obtenons en appliquant les opérations dans un certain ordre pour chaque chromosome (à min). Considérons que le nombre d'itérations (générations) se fait sans solution optimale et que le nombre le plus proche que nous ayons est 4 (avec fitness 1), le problème est que nous pouvons obtenir 4 en n'appliquant aucune opération sur 4 alors que pour 5 nous avons besoin de nombreuses opérations, de sorte que la solution quasi optimale n'est même pas proche de la solution.
Alors, GA ne convient-il pas à ce genre de problèmes? Ou la représentation chromosomique et la fonction de fitness suggérées ne sont pas assez bonnes?
Réponses
Avant d'essayer de répondre plus directement à votre question, permettez-moi de clarifier quelque chose.
Les gens utilisent souvent le terme algorithmes génétiques (AG), mais, dans de nombreux cas, ce qu'ils signifient vraiment, ce sont des algorithmes évolutifs (EA), qui sont un ensemble d'algorithmes d'optimisation basés sur la population (c'est-à-dire que plusieurs solutions sont maintenues en même temps) et approches inspirées du darwinisme et de la survie du plus apte . GA est l'une de ces approches, où les chromosomes sont binaires et vous avez à la fois la mutation et l'opération de croisement. Il existe d'autres approches, telles que les stratégies d'évolution ou la programmation génétique .
Comme vous l'avez également remarqué, les EA sont des méta-heuristiques et, bien qu'il y ait quelques recherches sur leurs propriétés de convergence [ 1 ], en pratique, elles peuvent ne pas converger. Cependant, lorsqu'une autre approche potentielle a échoué, les évaluations environnementales peuvent être définitivement utiles.
Dans votre cas, le problème est vraiment de trouver une expression de forme fermée (ou analytique ) d'une fonction, qui est composée d'autres fonctions plus petites. C'est vraiment pour cela que la programmation génétique (en particulier la GP basée sur les arbres) a été créée. En fait, le problème de Knuth est une instance particulière du problème de régression symbolique , qui est un problème typique auquel GP est appliqué. Donc, GP est probablement la première approche que vous devriez essayer.
Pendant ce temps, j'ai implémenté un programme simple dans DEAP qui tente de résoudre le problème Knuth. Vérifiez-le ici . L'aptitude de la meilleure solution qu'il a trouvée jusqu'à présent (avec une graine) est de 4 et la solution est floor(sqrt(float(sqrt(4))))(ici floatconvertit simplement l'entrée en un nombre à virgule flottante, pour assurer la sécurité du type). J'ai utilisé la différence comme fonction de fitness et j'ai exécuté l'algorithme GP pendant 100 générations avec 100 individus pour chaque génération (ce qui n'est pas beaucoup!). Je n'ai pas beaucoup modifié les hyper-paramètres, alors peut-être qu'avec la bonne graine et les bons hyper-paramètres, vous pouvez trouver la bonne solution.
Pour répondre à vos préoccupations, en principe, vous pouvez utiliser cet encodage, mais, comme vous le constatez, l'AG pourrait effectivement renvoyer $4$ comme la meilleure solution (qui n'est pas si loin de $5$), ce que vous pourriez éviter de tuer, à chaque génération, des individus qui ont juste cette valeur.
Je n'ai pas passé trop de temps sur ma mise en œuvre et à réfléchir à ce problème, mais, comme je l'ai dit ci-dessus, même avec la programmation génétique et en utilisant uniquement les opérations de Knuth, cela pourrait rester coincé dans les optima locaux. Vous pouvez essayer d'augmenter mon (ou votre) implémentation avec d'autres opérations, telles que la multiplication et l'addition, et voir si quelque chose s'améliore.