Comment classer mon problème d'optimisation d'entrée d'émulateur et avec quel algorithme dois-je l'aborder?

En raison de la nature de la question, je dois inclure beaucoup d'informations de base (parce que ma question est: comment puis-je restreindre cela?) Cela dit, cela peut être résumé (à ma connaissance) comme:

Quelles méthodes existent pour trouver des optimums locaux sur des espaces de recherche combinatoire extrêmement grands?

Contexte

Dans la communauté de superplay assistée par outils, nous cherchons à fournir des entrées spécialement conçues (non générées en temps réel) à une console de jeu vidéo ou à un émulateur afin de minimiser certains coûts (généralement le délai de réalisation). La façon dont cela se fait actuellement consiste à jouer le jeu image par image et en spécifiant l'entrée pour chaque image, en refaisant souvent plusieurs fois des parties de l'analyse (par exemple, l' analyse récemment publiée pour The Legend of Zelda: Ocarina of Time a un total de 198 590 tentatives).

Faire en sorte que ces pistes atteignent leur objectif se résume généralement à deux facteurs principaux: la planification de l'itinéraire et la traversée. Le premier est beaucoup plus "créatif" que le second.

La planification de l'itinéraire consiste à déterminer dans quelle direction le joueur doit naviguer dans l'ensemble pour terminer le jeu, et est souvent la partie la plus importante de la course. Cela revient à choisir la méthode de tri à utiliser, par exemple. Le meilleur tri de bulles au monde ne va tout simplement pas surpasser un tri rapide sur 1 million d'éléments.

Cependant, dans le désir de perfection, la traversée (comment se déroule l'itinéraire) est également un facteur important. Poursuivant l'analogie, c'est ainsi que l'algorithme de tri est implémenté. Certains itinéraires ne peuvent même pas être effectués sans des cadres d'entrée très spécifiques. Il s'agit du processus d'assistance d'outils le plus fastidieux et c'est ce qui fait que la production d'un cycle complet prend des mois, voire des années. Ce n'est pas un processus difficile (pour un humain) car cela revient à essayer différentes variantes de la même idée jusqu'à ce qu'une soit jugée la meilleure, mais les humains ne peuvent essayer que de nombreuses variations de leur durée d'attention. L'application de machines à cette tâche semble appropriée ici.

Mon objectif est maintenant d'essayer d'automatiser le processus de traversée en général pour la console Nintendo 64 . L'espace de recherche pour ce problème est beaucoup trop grand pour attaquer avec une approche par force brute. Un segment à n trames d'une exécution N64 a 2 ³⁰ⁿ entrées possibles, ce qui signifie que 30 trames d'entrée (une seconde à 30 images par seconde) ont 2 ⁹⁰⁰ entrées possibles; il serait impossible de tester ces solutions potentielles, sans parler de celles pour un cycle complet de deux heures.

Cependant, je ne suis pas intéressé à tenter (ou plutôt, je ne vais même pas essayer) une optimisation globale totale d'une exécution complète. Je voudrais plutôt, étant donné une entrée initiale, approximer l' optimum local pour un segment particulier d'une analyse (ou les n optimaux locaux les plus proches, pour une sorte d'optimisation semi-globale) . C'est-à-dire, étant donné une route et une traversée initiale de cette route: recherchez les voisins de cette traversée pour minimiser les coûts, mais ne dégénérez pas en essayant tous les cas qui pourraient résoudre le problème.

Mon programme devrait donc prendre un état de départ, un flux d'entrée, une fonction d'évaluation et produire l'optimum local en minimisant le résultat de l'évaluation.

État actuel

Actuellement, j'ai tout le cadre pris en charge. Cela inclut l'évaluation d'un flux d'entrée via la manipulation de l'émulateur, l'installation et le démontage, la configuration, etc. Et en tant qu'espace réservé, l'optimiseur est un algorithme génétique très basique. Il évalue simplement une population de flux d'entrée, stocke / remplace le gagnant et génère une nouvelle population en mutant le flux gagnant. Ce processus se poursuit jusqu'à ce que certains critères arbitraires soient remplis, comme l'heure ou le numéro de génération.

Notez que la partie la plus lente de ce programme sera, de loin, l'évaluation d'un flux d'entrée . En effet, cela implique d'émuler le jeu pour n images. (Si j'avais le temps, j'écrirais mon propre émulateur qui fournirait des crochets dans ce genre de choses, mais pour l'instant je me retrouve avec la synthèse des messages et la modification de la mémoire pour un émulateur existant à partir d'un autre processus.) Sur mon ordinateur principal, qui est assez moderne, l'évaluation de 200 images prend environ 14 secondes. En tant que tel, je préférerais un algorithme (étant donné le choix) qui minimise le nombre d'évaluations de fonctions.

J'ai créé un système dans le cadre qui gère les émulateurs simultanément. En tant que tel, je peux évaluer un certain nombre de flux à la fois avec une échelle de performances linéaire, mais pratiquement le nombre d'émulateurs en cours d'exécution ne peut être que de 8 à 32 (et 32 ​​le pousse vraiment) avant que les performances du système ne se détériorent. Cela signifie (étant donné le choix), un algorithme qui peut effectuer le traitement pendant qu'une évaluation est en cours serait très bénéfique, car l'optimiseur peut faire de gros efforts pendant qu'il attend une évaluation.

A titre de test, ma fonction d'évaluation (pour le jeu Banjo Kazooie ) consistait à additionner, par image, la distance du joueur à un point de but. Cela signifiait que la solution optimale était de se rapprocher le plus rapidement possible de ce point. Limitant la mutation au stick analogique uniquement, il a fallu un jour pour obtenir une solution correcte . (C'était avant d'implémenter la simultanéité.)

Après avoir ajouté la simultanéité, j'ai activé la mutation des pressions sur le bouton A et j'ai fait la même fonction d'évaluation dans une zone qui nécessitait un saut. Avec 24 émulateurs en cours d'exécution, il a fallu environ 1 heure pour atteindre l'objectif à partir d'un flux d'entrée initialement vierge, mais il faudrait probablement qu'il s'exécute pendant des jours pour arriver à quelque chose de proche de l'optimal.

Problème

Le problème auquel je suis confronté est que je ne connais pas suffisamment le domaine de l'optimisation mathématique pour savoir comment modéliser correctement mon problème d'optimisation ! Je peux à peu près suivre l'idée conceptuelle de nombreux algorithmes tels que décrits sur Wikipedia, par exemple, mais je ne sais pas comment classer mon problème ou sélectionner l'algorithme de pointe pour cette catégorie.

D'après ce que je peux dire, j'ai un problème combinatoire avec un quartier extrêmement vaste . En plus de cela, la fonction d'évaluation est extrêmement discontinue, sans gradient et avec de nombreux plateaux . De plus, il n'y a pas beaucoup de contraintes, mais je serai heureux d'ajouter la possibilité de les exprimer si cela aide à résoudre le problème; Je voudrais permettre de spécifier que le bouton Démarrer ne doit pas être utilisé, par exemple, mais ce n'est pas le cas général.

Question

Ma question est donc: comment modéliser cela? Quel genre de problème d'optimisation essaie-je de résoudre? Quel algorithme dois-je utiliser? Je n'ai pas peur de lire des articles de recherche, alors faites-moi savoir ce que je dois lire!

Intuitivement, un algorithme génétique ne pourrait pas être le meilleur, car il ne semble pas vraiment apprendre. Par exemple, si appuyer sur Démarrer semble toujours aggraver l'évaluation (car cela met le jeu en pause), il devrait y avoir une sorte de concepteur ou de cerveau qui apprend: "appuyer sur Démarrer à tout moment est inutile." Mais même cet objectif n'est pas aussi trivial qu'il y paraît, car parfois, appuyer sur le démarrage est optimal, comme dans les soi-disant «sauts en arrière-longs sauts» dans Super Mario 64 ! Ici, le cerveau devrait apprendre un schéma beaucoup plus complexe: "appuyer sur Start est inutile, sauf lorsque le joueur est dans cet état très spécifique et continuera avec une combinaison de pressions sur les boutons ."

Il semble que je devrais (ou la machine pourrait apprendre à) représenter l'entrée d'une autre manière plus adaptée à la modification. L'entrée par image semble trop granulaire, car ce qui est vraiment nécessaire, ce sont des "actions", qui peuvent s'étendre sur plusieurs images ... pourtant de nombreuses découvertes sont faites image par image, donc je ne peux pas totalement l'exclure (le la pause susmentionnée en arrière-long-saut nécessite une précision au niveau de la trame). Il semble également que le fait que les entrées soient traitées en série devrait être quelque chose qui peut être capitalisé, mais je ne sais pas comment.

Je lis actuellement sur la recherche taboue (réactive), la recherche de quartier à très grande échelle, l'optimisation basée sur l'enseignement et l'apprentissage et l'optimisation des colonies de fourmis.

Ce problème est-il simplement trop difficile à résoudre avec autre chose que des algorithmes génétiques aléatoires? Ou s'agit-il en fait d'un problème trivial résolu depuis longtemps? Merci d'avoir lu et merci d'avance pour toutes les réponses.

D'après les informations que vous donnez dans votre question, je ne vois pas comment appliquer les méthodes d'optimisation standard (que je connais). Vos objets ne sont pas si compliqués (plus à ce sujet plus tard) mais votre fonction cible est désagréable: ses valeurs sont définies par un système externe hors de votre contrôle, il est peu probable qu'elles aient de belles propriétés, etc. Par conséquent, je pense que l'utilisation d'algorithmes génétiques n'est pas impossible et peut-être même une bonne approche ici; elles fonctionnent souvent mieux que d'autres méthodes si vous n'avez aucune idée de la structure de votre problème. Il y a beaucoup à considérer

• espace objet,
• fonction cible et
• les paramètres de votre algorithme génétique,

permettez-moi donc d'élaborer.

Quels sont tes objets?

Vous avez déjà répondu à cela: vous regardez une séquence d'actions, chacune prenant une image. Je pense que cela peut être trop fin; essayez peut-être une séquence d'actions, chacune d'une durée (en nombre d'images). Cela permettrait d'avoir des mutations comme "marcher un peu plus longtemps" pour avoir des probabilités différentes que "insérer une pression de A" de manière naturelle. Essayez ce qui fonctionne le mieux; vous devrez peut-être revoir cet article après avoir pensé aux autres ingrédients.

Quelle est votre fonction cible?

Celui-ci est vraiment crucial. Que voulez-vous optimiser? Temps de but? Nombre d'actions différentes? Le nombre d'étoiles collectées? Une combinaison de plusieurs facteurs? Dès que vous obtenez plusieurs cibles, les choses deviennent velues - il n'y a (généralement) plus d'optima!

Vous avez mentionné le temps de l'objectif. Ce n'est probablement pas du tout une bonne fonction cible. Pourquoi? Parce que la plupart des séquences n'atteindront même pas le but, elles resteront donc constantes, créant un paysage de fitness comme celui-ci (croquis conceptuel en une dimension):

^{[ source ]}

Il y a d'énormes zones où la fonction cible est . Les algorithmes génétiques sont tous des signaux : de petits changements dans la solution doivent indiquer une amélioration (ou une baisse) de la qualité si et seulement si le changement est "dirigé" vers une solution optimale (idéalement). Si ce n'est pas le cas (radicalement), vous n'avez guère plus qu'une recherche aléatoire, frappant une bonne solution avec une probabilité proche de . Qu'est-ce que cela signifie pour notre fonction cible? Cela doit être quelque chose qui s'améliore chaque fois qu'une solution s'améliore légèrement, même si la qualité globale est encore faible . Et alors$0$$0$

$\qquad \displaystyle \frac{1}{1 + \text{final distance to goal}} + \frac{1}{1 + \text{time to goal}}$

utiliser "l'infini" comme temps pour atteindre le but si le but n'est pas atteint, c'est-à-dire mettre le deuxième sommet à . Tant que l'objectif n'est pas atteint, le fait de se rapprocher déplace la condition physique jusqu'à . Toutes les séquences qui atteignent l'objectif ont une ligne de base de et s'améliorent encore plus vite.1 $0$$1$$1$

Alors, comment mesurez-vous la distance? La distance linéaire peut sembler tentante mais a ses problèmes; encore une fois, de mauvais signaux peuvent être envoyés. Considérez ce scénario simple:

^{[ source ]}

Chaque séquence qui commence par un saut dans le couloir supérieur s'améliore jusqu'à ce qu'elle atteigne un endroit juste au-dessus du but, mais elle ne peut jamais atteindre le but! Pire encore, parmi toutes les séquences qui n'atteignent pas l'objectif, celles qui montent sont aussi bonnes que celles qui descendent, donc l'AG ne peut pas rejeter les séquences qui sont clairement condamnées. En d'autres termes, la distance linéaire crée des optima locaux particulièrement mauvais qui peuvent piéger l'AG s'il y a des impasses dans le niveau.

Par conséquent, je vous suggère de superposer une grille sur votre niveau et de connecter les points voisins si le personnage du jeu peut passer de l'un à l'autre. Ensuite, vous calculez la distance du but par la longueur du chemin le plus court du point le plus proche de l'endroit où la séquence atterrit le personnage au point le plus proche du but. Ceci est facile à calculer et entrer dans les zones mortes (optima locaux) est immédiatement puni¹. Bien sûr, vous devez avoir accès à des données de niveau, mais je suppose que vous les avez.

Comment fonctionne votre GA?

Nous pouvons maintenant accéder à l'algorithme génétique réel. Les considérations clés sont la population, la sélection, la reproduction / mutation et le critère d'arrêt.

Population

Quelle sera la taille de votre population? S'il est trop petit, il peut ne pas fournir la diversité nécessaire pour parvenir à une bonne solution. Si elle est trop grande, vous êtes plus susceptible de transporter des déchets inutiles, ce qui ralentit le processus.

Comment initialisez- vous votre population? Choisissez-vous des séquences d'actions aléatoires? Si oui, de quelle longueur? Avez-vous un (petit) nombre de solutions raisonnables générées manuellement avec, peut-être celles qui atteignent l'objectif?

Sélection

Quels individus sont sélectionnés pour leur survie / reproduction? Le meilleur? Organisez-vous des tournois ? Décidez-vous au hasard de la survie d'un individu par rapport à sa forme physique ? Voulez-vous que les meilleurs survivent dans tous les cas ou peuvent-ils mourir (peut être utile pour quitter les optima locaux) ²?$k$

Le concept de base ici est la pression de sélection : est-il difficile de survivre? Rendez-le trop petit et vous n'éliminez pas les solutions de merde. Faites-le trop haut et vous rendrez difficile le changement (en particulier le déplacement entre les optima locaux).

Reproduction et mutation

Une fois que vous avez sélectionné vos survivants d'un tour, vous devez créer la prochaine génération à partir d'eux (les parents survivent-ils et font-ils partie de la prochaine génération?). Il existe deux stratégies principales: la mutation et la recombinaison.

La mutation est assez claire, bien que les détails puissent différer. Pour chaque position dans la séquence d'un individu, mute-la avec une certaine probabilité. Vous pouvez le faire indépendamment pour chaque position, ou choisir le nombre de mutations au hasard, ou vous pouvez effectuer différentes mutations avec différentes probabilités (comme insérer un nouvel élément, en supprimer un, en changer un, ...). La mutation concerne généralement de petits changements.

La recombinaison, qui combine des aspects de deux ou plusieurs solutions à une nouvelle, est plus délicate mais peut permettre de grandes étapes, c'est-à-dire quitter une "montagne de fitness" et se déplacer directement sur la pente d'une autre (qui peut être plus élevée). Une idée classique est le crossover ; Je ne sais pas si cela a du sens ici (il me semble que l'échange du préfixe d'une séquence donnée pour autre chose dévalorisera probablement le suffixe). Peut-être pouvez-vous utiliser des connaissances sur le niveau et les positions du personnage de jeu à différents points de la séquence pour guider cela, c'est-à-dire créer des points de croisement uniquement là où le personnage est à la même position dans les deux séquences.

Résiliation

Quand arrêtez-vous? Après générations? Lorsque la forme physique maximale ne s'est pas améliorée depuis rounds? Arrêtez-vous tôt si une certaine forme physique (avec la fonction ci-dessus, ) n'a pas été atteinte après tours afin d'éliminer précocement les populations inutiles?k 1 $N$$k$$1$$n$

Comme vous pouvez le voir, toutes ces choses se mêlent pour influencer les performances réelles. Si vous gérez plusieurs populations en parallèle, vous pouvez même penser à mettre en œuvre la dérive génétique due à la migration et / ou aux catastrophes. Il y a peu de théorie pour vous guider, vous devez donc essayer différentes configurations et regarder où cela vous mène. Espérons que ce qui fonctionne pour un niveau fonctionnera également pour les autres. Bricolage heureux!

Nota bene: Regardez BoxCar 2D à la lumière de ce qui précède. Ils font assez bien certaines choses (d'autres non) et vous pouvez avoir une intuition sur la façon dont les paramètres d'un GA peuvent influencer ses performances.

1. En fait, construire une séquence avec avidité en utilisant cette forme physique, c'est-à-dire choisir l'action qui minimise la distance par rapport au but parmi toutes les prochaines actions possibles, peut très bien fonctionner. Essayez cela avant d'utiliser GA!
2. Bien sûr, en tant qu'observateur, vous vous souvenez toujours de la meilleure solution jamais rencontrée.

Pour plus de détails sur la méthode d'optimisation basée sur l'enseignement et l'apprentissage (TLBO) et son code, reportez-vous à l'article suivant:

Un algorithme d'optimisation élitiste basé sur l'enseignement et l'apprentissage pour résoudre des problèmes d'optimisation contraints complexes par R. Venkata Rao et V. Patel; Journal international des calculs d'ingénierie industrielle 3 (4): 535–560 (2012)

Pour une lecture supplémentaire:

• Algorithme d'optimisation basé sur l'enseignement et l'apprentissage pour des problèmes d'optimisation de paramètres réels non contraints et contraints par R. Venkata Rao, VJ Savsani et J. Balic; Optimisation de l'ingénierie (2012)
• Optimisation de la conception mécanique à l'aide de techniques d'optimisation avancées par R. Venkata Rao, JV Savsani; Springer-Verlag Londres (2012); ISBN 978-1-4471-2747-5
• Optimisation multi-objectif des échangeurs de chaleur en utilisant un algorithme d'optimisation basé sur l'enseignement-apprentissage modifié par R. Venkata Rao et V. Patel; Modélisation mathématique appliquée (2012)
• Optimisation multi-objectif de refroidisseurs thermoélectriques à deux étages utilisant un algorithme d'optimisation basé sur l'enseignement-apprentissage modifié par R. Venkata Rao et V. Patel; Applications d'ingénierie de l'intelligence artificielle (2012)