Introduction

Une autre catégorie de problèmes d'optimisation implique des variables qui ne sont pas continues. Il existe de nombreux exemples de choses qui ne peuvent exister que dans certains états : évidemment, toutes les variables entières sont limitées à des nombres entiers et un interrupteur ne peut être qu'allumé ou éteint. Ou encore, une séquence d'ADN : elle consiste en une combinaison en série de seulement quatre bases. Ces types de problèmes d'optimisation sont délicats parce que nous ne pouvons plus "gravir la colline" en apportant des changements incrémentaux à notre ensemble de variables et en nous déplaçant le long du gradient.

L'exemple de l'ADN nous fournit un point de départ pour une méthode numérique permettant de résoudre ce type de problèmes. On pourrait considérer l'évolution comme l'algorithme d'optimisation discrète de la nature : l'aptitude d'une "solution" donnée dépend en grande partie de son code génétique, qui ne peut prendre que des états définis. Alors, comment la nature améliore-t-elle continuellement ses conceptions ?

L'algorithme de la nature comporte quelques éléments clés, mais l'idée principale est qu'il s'agit d'une population. Au lieu de partir d'un point donné et d'améliorer progressivement une solution unique, la nature s'améliore en mélangeant et en associant différentes solutions au sein d'une grande population. Telle sera notre approche. Nous ferons évoluer des solutions optimales (ou quasi optimales) à partir d'un ensemble de nombreuses solutions initiales, certaines bonnes et d'autres mauvaises.

Cette catégorie de méthodes relève de l'informatique évolutive, dont les plus importantes sont les algorithmes génétiques.

Références

La majeure partie du matériel de cette section du cours est basée sur le travail de Melanie Mitchell et sur deux excellents livres qu'elle a publiés sur les algorithmes génétiques et la théorie de la complexité :

• Mitchell, M. (1996). An Introduction to Genetic Algorithms, MIT.
• Mitchell, M. (2009). Complexity : A Guided Tour, Oxford University Press.

L'exemple d'optimisation discrète impliquant un parc éolien est basé sur une série d'articles tirés de la littérature, en commençant par l'article original de Mosetti, et. al.

• Mosetti, G., Poloni, C., & Diviacco, B. "Optimization of wind turbine positioning in large wind farms by means of a genetic algorithm". Journal of Wind Engineering and Industrial Aerodynamics, Volume 51, Issue 1, 1994, pp 105-116.
• Grady, S.A., Hussaini, M.Y., & Abdullah, M.M. "Placement of wind turbines using genetic algorithms". Renewable Energy, Volume 30, 2005, pp 259-270.
• Marmidis, G., Lazarou, S., & Pyrgioti, El. "Optimal placement of wind turbines in a wind park using Monte Carlo simulation". Renewable Energy, Volume 33, Issue 7, 2008, pp 1455-1460.

Diapositives de l'exposé

Code

Il y a deux morceaux de code aujourd'hui.

1. GAStudents.java est l'endroit où vous allez implémenter les opérateurs génétiques. J'ai déjà pris en charge les autres éléments (encodage du problème, génération aléatoire d'une population initiale, évaluation de l'aptitude d'une stratégie donnée et roulette pour la sélection des parents). Je vous encourage à parcourir le code avant de commencer afin d'avoir une vue d'ensemble de la manière dont les choses fonctionnent.
2. DrawStudents.java nous permet de tester notre stratégie optimale dans diverses conditions qui nous donneront un aperçu du fonctionnement de la stratégie optimale. Vous n'en avez pas besoin tant que vous n'avez pas soumis votre meilleure stratégie GA en ligne et que vous n'êtes pas satisfait de son score.

Dans le laboratoire

Mise en œuvre des opérateurs génétiques

Tâche 1

Mise en œuvre du croisement à deux points à partir de la ligne 141 de GAStudents.java.

Tâche 2

Mettez en œuvre la mutation à partir de la ligne 171 de GAStudents.java. N'oubliez pas que l'alphabet va de 0 à 6 (et pas seulement 0 et 1). Assurez-vous que l'opérateur est appliqué à chaque gène de la séquence d'une stratégie donnée !

Élaboration d'une solution

Tâche 3

• Une fois que votre code fonctionne, exécutez-le. Cela prendra un certain temps, très probablement entre 3000 et 4000 générations. Votre meilleure solution devrait atteindre 10 % entre 500 et 700 générations. Si ce n'est pas le cas, revérifiez votre code et relancez votre simulation.
• Lorsque la meilleure solution d'une génération donnée est constamment supérieure à 80-85%, par exemple, vous pouvez arrêter le code. Un score parfait serait de 100 %, de sorte que cette stratégie dérivée de l'AG se rapproche de l'optimal et devrait être comparable à des stratégies humaines raisonnables. Mais pourquoi ? Les stratégies sont-elles les mêmes ? Branchez-le sur l'application web et regardez-le fonctionner.
• Lorsque vous aurez atteint ce point, montrez vos résultats à l'enseignant. Vous devez atteindre ce point pour obtenir tous les points du laboratoire.

En tant que devoirs

Comprendre Robby

La solution optimale (~95% ?) obtenue par l'algorithme génétique est sournoisement bonne. Il faudra peut-être de nombreuses exécutions pour trouver une solution qui permette d'obtenir les derniers points de pourcentage, mais cela en vaut la peine, car il se passera alors quelque chose de vraiment intéressant. L'objectif ici est de comprendre la magie de cette solution optimale.

Une fois que votre solution GA optimale obtient un score de 90 %, soumettez-la à l'application web et préparez un bref rapport répondant aux questions suivantes. Veillez à inclure votre solution optimale dans votre rapport !

Tâche 4 - Pas de canettes à proximité

• Lorsqu'il n'y a pas de boîtes de conserve à proximité de Robby, une stratégie humaine courante consiste à attribuer un mouvement aléatoire, mais que suggère l'AG ? Si cette situation persiste, Robby effectuera plusieurs fois la même action et finira par rencontrer un mur. S'il n'y a toujours pas de boîtes de conserve à proximité, que voulez-vous qu'il fasse ? Que fait-il ? De nouveau, si la situation se répète, Robby effectuera toujours la même action et finira par rencontrer un autre mur. S'il n'y a toujours pas de boîtes de conserve à proximité, que voulez-vous qu'il fasse ? Que fait-il ? Encore une fois, si la situation se répète, Robby effectuera toujours la même action et finira par rencontrer un autre mur. S'il n'y a toujours pas de boîtes de conserve à proximité, que voulez-vous qu'il fasse ? Que fait-il ?
• Exécutez DrawStudents.java en utilisant le scénario de test 2 pour voir comment votre Robby optimal se comporte dans une pièce presque vide. Un modèle devrait maintenant être apparent quant à la manière dont Robby recherche les boîtes de conserve. Expliquez la stratégie de Robby pour chercher des boîtes de conserve.

Tâche 5 - De nombreuses boîtes de conserve à proximité

• Lorsqu'il y a des boîtes de conserve aux positions E, W et C, une stratégie humaine courante consiste à ramasser la boîte de conserve à la position actuelle, puis à se déplacer vers un autre site où se trouve une boîte de conserve, mais que suggère l'AG ?
• Exécutez DrawStudents.java en utilisant le scénario de test 3 pour voir comment Robby se comporte dans cette situation. Vous pouvez également vérifier le cas de test 4. Expliquez la stratégie de Robby lorsqu'il voit de nombreuses boîtes de conserve.

Tâche 6 - Le hasard

• Combien de 4 et de 6 apparaissent dans la séquence génétique optimale ? Au début, ils apparaissent environ 1/7ème du temps. Qu'en est-il lors de la convergence ? Pourquoi y aurait-il des 4 ? Combien de mouvements réellement aléatoires Robby effectue-t-il et dans quelles situations ?
• Appelez la fonction analyze (ligne 47) dans DrawStudents.java pour voir quels gènes contiennent des 4 ou des 6.

Tâche 7 - Spécificité

• La principale différence entre la stratégie humaine et la stratégie de l'AG est la coopération entre les gènes. Les stratégies humaines courantes sont basées uniquement sur ce que Robby voit actuellement, mais la stratégie de l'AG est d'une certaine manière plus profonde : elle attribue des actions basées sur le comportement de Robby dans d'autres situations, ce qui est évidemment plus efficace. Mais il convient également de noter que l'AG a fait évoluer la stratégie de Robby pour un environnement particulier et qu'elle ne fonctionnera pas aussi bien dans d'autres environnements. Comparez la stratégie de l'AG et la stratégie humaine dans une pièce remplie de boîtes de conserve.
• Exécutez DrawStudents.java en utilisant le cas de test 5. Exécutez le code plusieurs fois. Quelle est la meilleure stratégie ?

Défi ouvert

Tâche 8 (Facultatif)

• Pouvez-vous trouver une stratégie plus performante que celle de l'AG ? Y a-t-il des ajustements que vous pourriez apporter à la solution de l'AG pour obtenir un score légèrement supérieur ?
• Faites tout ce que vous pouvez pour obtenir la note la plus élevée possible et soumettez-la à l'application web.