Optimisation de fonction, algorithmes génétiques et wow: com

[Jaaxx]

Soit F(P1,P2,....,Pn,A1,A2,.....Am) une fonction sur l'ensemble des entiers naturels N, avec n variables de type P et m de type A.
Comment optimiser cette fonction pour maximiser les variables P et minimiser les variables A ?

Stop! on arrête tout. Ce n'est pas un article sur de l'algèbre!! c'est un article sur World Of Warcraft..... Ou plutôt comment concilier des maths et du développement informatique tout en jouant à WOW.
Il y a un Haut Fait de guilde intitulé Maitrise des Mixtures. Il s'agit d'élaborer 1000 flacons. Il y a 6 recettes de flacons différents, réalisables en utilisant 7 types de plantes. Chaque recette de flacons est différente des autres, et ne nécéssite pas les mêmes types de plantes.

La fonction à optimiser est celle qui permettra de créer le plus de flacons en utilisant le moins de plantes possibles. Il n'y a pas d'obligation concernant le type de flacons crées, il faut juste en réaliser 1000.

Liste des flacons

1. Flacon de force titanesque: http://fr.wowhead.com/item=58088
2. Flacon des vents: http://fr.wowhead.com/item=58087
3. Flacon de l'esprit draconique: http://fr.wowhead.com/item=58086
4. Flacon de l'eau courante: http://fr.wowhead.com/item=67438
5. Flacon de peau d'acier: http://fr.wowhead.com/item=58085
6. Flacon d'amélioration: http://fr.wowhead.com/item=58149

Liste des plantes

1. Cendrelles: http://fr.wowhead.com/item=52983
2. Voile d'Azshara: http://fr.wowhead.com/item=52985
3. Vignétincelle: http://fr.wowhead.com/item=52984
4. Pétale de cœur: http://fr.wowhead.com/item=52986
5. Fouettine: http://fr.wowhead.com/item=52988
6. Jasmin crépusculaire: http://fr.wowhead.com/item=52987
7. Vie volatile: http://fr.wowhead.com/item=52329

Les vies volatiles ne sont pas vraiment des plantes mais un résidu de leur ramassage. Obtenir des plantes demande un certain temps et l'obtention des vies est aléatoire. Il faut donc vraiment optimiser leur utilisation pour réaliser le plus de flacons possibles.
La méthode que j'ai choisie n'est peut être pas la meilleure dans ce cas, mais c'est celle que j'avais envie d'utiliser. Il semble quand même qu'elle s'y prète! c'est la méthode des Algorithmes Génétiques.
Plus d'informations sur http://fr.wikipedia.org/wiki/Algorithme ... C3%A9tique
exemple 1: Rapporteurs de Golond : http://www.kilomaths.com/2010/05/rappor ... enetiques/
exemple 2: http://www.benoitlavorata.com/blog/?p=127

On va évaluer une population d'individus et voir si cette population tend vers une limite au fil des générations....
Il va y avoir des cycles d'évaluation/sélection/reproductions/mutations effectués sur cette population, chaque cycle représentant une génération. Des individus vont survivre, plus ou moins longtemps, d'autres éliminés et au bout d'un certain nombre de générations je devrais obtenir la formule qui me donne le plus de flacons possible.

Définitions et Codage
Soit une population finie d'individus. Ces individus ont un code génétique qui leur permet de créer des protéines (les flacons) en utilisant des acides aminés (les plantes).Mais les stocks des différents acides ne sont pas illimités, ils sont dépendants de l'environnement (lire la cueillette).
J'ai choisi un codage dont il restera à évaluer la pertinence: il y a un chromosome par individu (John Holland, théoricien des AG, appelait ça des Schèmes). Ce chromosome contient 6 gènes. Chaque gène code le nombre de protéines (flacons) qu'il doit créer.

Evaluation de la population
Imaginons l'individu Bisco. son chromosome est: [5]--[0]--[2]--[0]--[4]--[1]
Bisco doit donc créer:
5 Flacons de force titanesque + 2 Flacons de l'esprit draconique + 4 Flacons de peau d'acier + 1 Flacon d'amélioration.

La machinerie cellulaire de Bisco va utiliser les 6 recettes à sa disposition pour créer ces flacons (protéines). Ainsi il y aura 16 flacons de crées. Mais pour cela elle va consommer des plantes (acides aminés): par exemple la Cendrelle, il en faut 8 par Flacon de force titanesque, 0 par Flacon de l'esprit draconique, 8 par Flacon de peau d'acier et 8 par Flacon d'amélioration. Soit une consommation totale en Cendrelle de 5*8+2*0+4*8+1*8=80. Chaque plante se verra attribuer une consommation particulière.
L'AG va donc devoir calculer le nombre de flacons et la consommation en plantes de chaque individu de la population. Il va évaluer chaque individu. L'évaluation est une notion trés importante des AG, c'est même la première, car elle représente la fonction que l'on veut optimiser!!! Mais elle est a la discrétion du développeur! Dans mon cas je veux tester avec une évaluation qui tri les individus suivant leur production de flacons et leur consommation en plantes.
Bisco créera 12 flacons pour une consommation de 288 plantes (égale à la somme totale des consommations particulières de chaque plantes). Mais les stocks de plantes(acides aminés) mise à disposition de Bisco sont limitées: peut être va t'il être trop gourmand et consommer au dessus de ses moyens? Cela dépendra des résultats des cueillettes, donc il faudra qu'avant de faire tourner l'AG on saisisse les stocks dans des variables........
La fonction d'évaluation va faire un premier tri: d'un coté les bons individus, qui se contentent de leurs stocks, et de l'autre les mauvais qui sont gourmands. Puis un second tri sera effectué sur les bons: ils seront ordonnés par nombre de flacons décroissant et consommations croissante. Ainsi on obtient une liste d'individus, les meilleurs auront un rang flaible, les moins bons un rang plus élevé. Un second tri du même genre sera réalisé sur les mauvais individus (les moins gourmands seront de rang faible).

Rang 1: Individu Toto , nb Flacons=17 , conso totale=455
Rang 2: " " Tutu , nb Flacons=16 , conso totale=423
Rang 3: " " Titi , nb Flacons=16 , conso totale=444
|
|
Rang i: " " Bisco , nb Flacons=12 , conso totale=288
|
------ indice à partir duquel les individus sont gourmands -------
|
Rang n: " " Tété , nb Flacons=10 , conso totale=5169

Le meilleur Individu sera Toto, le pire Tété ^^

Sélection
La population est maintenant classée selon les résultats de la fonction d'évaluation. Il est temps d'envisager la reproduction de ses éléments! On va dans un premier temps sélectionner les individus aptes à se reproduire. On va ici faire un peu d'eugenisme.... Mais les algorithmes génétiques ne sont pas developpés par des Alexis Carrel, c'est juste la théorie sous-jacente des AG qui introduit cette notion! Les AG ne sont pas destinés à recevoir le prix Nobel de médecine ou à faire de la politique. Bref!!
Il y a diverses méthodes de sélection des individus. Je vais essayer avec la méthode des rangs, qui scinde la population en 2, en ne gardant que les individus de rangs inférieurs ou égaux à R. R sera égal à la moitié de la population courante pour simplifier l'AG et la méthode de reproduction.

Rang 1: Individu Toto , nb Flacons=17 , conso totale=455
Rang 2: " " Tutu , nb Flacons=16 , conso totale=423
Rang 3: " " Titi , nb Flacons=16 , conso totale=444
|
|
Rang R: " " Bisco , nb Flacons=12 , conso totale=288

Bisco a de la chance, il est le dernier retenu......

Reproduction
Il est maintenant temps de faire se reproduire tout ce joli monde. La reproduction va assurer le renouvellement de la population et son brassage génétique. Peut être les enfants crées, ne produiront pas un monde meilleur mais plutôt une optimisation de la fonction d'évaluation.
Il y a diverses solution pour faire se reproduire les individus. On peut choisir les couples au hasard ou non. Je vais tester en prenant l'individu de Rang 1 et celui de Rang 2, puis Rang 3 et Rang 4, ....... pour finir avec Rang R-1 et Rang R.
Ressortons Bisco de son placard, non de la sélection (Rang R)! L'individu de Rang R-1 se prénomme Nifion. Ils vont gentiment brasser leurs gênes en engendrant 2 enfants Bap et Meldz.
Pour le brassage des gênes, plusieurs solutions existent (une fois de plus). Je vais choisir le croisement à en 2 points! Ces 2 points sont générés aléatoirement mais coupent toujours les chromosomes en 3 parties.

Bisco dont le chromosome est: [5]--[0]-*-[2]--[0]--[4]-*-[1]
Nifion dont le chromosome est: [0]--[4]-*-[3]--[6]--[2]-*-[0]

Point de scission n°1 *
Point de scission n°2 *

Les parties sont ensuite regroupées pour reconstituer les chromosomes des 2 enfants:

Bap aura le chromosome [5]--[0]--[3]--[6]--[2]--[1]
Meldz aura le chromosome [0]--[4]--[2]--[0]--[4]--[0]

en gras les gènes provenant de Nifion, normaux ceux provenant de Bisco.

Et ainsi de suite, jusqu'à avoir balayé la liste des géniteurs et avoir assuré leur descendance. Un couple qui engendre 2 enfant permet de maintenir le cardinal de la population et a simplifier le codage de l'AG.

Mutation
Introduire le phénomène de mutation permet d'apporter un peu de diversité génétique. En effet la population peut tendre vers des individus qui représentent une solution à la fonction à optimiser alors que ces individus ne sont pas nécessairement les meilleurs: on a affaire à des optima locaux. Dans ces cas d'optima locaux, l'AG risque de stagner. La mutation relancera le processus de convergence vers la meilleure solution.
On peut aussi implémenter un processus d'Exogamie en injectant des individus nouveaux au fil des générations. Ou marier exogamie et mutation.
La fréquence de mutation fait partie des paramètres choisis par le programmeur. Elle peut être fixe ou variable dans le temps. On parcoure les enfants engendrés et on applique ou non la mutation par un tirage aléatoire fonction de la fréquence. Ensuite on applique la mutation: j'ai choisi de choisir un gène au hasard et de lui appliquer un buff +1 ou un débuff -1 ^^.

Bap: [5]--[0]--[3]--[6]--[2]--[1] Gène mutant= rand(1,6)=4 , modification: débuff -1
Bap: [5]--[0]--[3]--[5]--[2]--[1] Le chromosome mutant est en gras.

Same player shoot again, ou comment reboucler le tout
Une génération vient de passer. Du sang, des pleurs, des rires, on disparait, on se reproduit, telle est la dure loi de l'AG.
Et le cycle de la vie recommence, la nouvelle population repart pour un tour du circuit. Au fil des générations, cette population, au cardinal constant, devrait donner des individus satisfaisant au mieux l'optimisation. Ou plutot devraient apparaitre des groupes d'individus partageant les mêmes chromosomes, chaque groupe pouvant être une solution.

Groupe Afortepoitrine
Rhia: [4]--[4]--[6]--[0]--[3]--[5]
Loutre: [4]--[4]--[6]--[0]--[3]--[5]
Kah: [4]--[4]--[6]--[0]--[3]--[5]
Didine: [4]--[4]--[6]--[0]--[3]--[5]
Liline: [4]--[4]--[6]--[0]--[3]--[5]

Groupe Pasunfion
Jaaxx: [5]--[3]--[5]--[1]--[5]--[3]

On choisira le groupe le plus dense (dans l'exemple c'est celui où il y a le plus de mamelles), et on demandera a un spé-flacon de crafter le nombre de recettes défini par les gènes.

Programmation et emmerdements
J'avais commencé le codage de l'AG avec l'environnement Processing. Mais c'est une surcouche de Java qui me pose des problèmes. J'ai tout recommencé en PHP, mais il faut redébugguer, etc etc. Le pb de php c'est qu'il n'est pas vraiment fait pour afficher des données variant dans le temps, il faudra peut etre recourir a d'autres outils de programmation.

Coté AG il y a beaucoup de parametres a tester: le cardinal de la population, le nombre de génération, les taux de mutation, les choix des modes de sélection et de reproduction.
Rien n'indique que l'AG convergera vers une solution optimale.

Et la suite? les résultats, les graphiques, les analyses
J'espère être capable de mener à bien ce petit projet et de proposer dans une suite de l'article des exemples en images des processus impliqués dans l'AG..... et aussi tester des solutions IG, mais ceci est une autre histoire!!!!

Curraheeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee

=============================================================

MAJ du 14/02
Apres corrections des bugs, l'AG s'est mis à converger. Sur un stock de plantes bien défini, l'AG ne donne pas toujours la solution optimale. Tout dépend du nombre de générations à évaluer, du cardinal de la population et du taux de mutations. De plus l'AG converge, pour chaque simulation, vers un seul groupe de solutions alors qu'avec ce stock il y a un ensemble de solutions optimales. Je pense qu'il faudrait ajouter un tirage aléatoire des couples géniteurs ou ajouter un phénomène de spéciation.
L'évaluation de type nombre de flacons, consommation en plantes de chaque individu n'est peut être pas pertinente. A tester l'évaluation via le ratio nombre de flacons / consommation en plantes.
Néanmoins, l'AG semble être assez robuste, les résultats étant très proches pour chaque simulation (à conditions identiques).

Du coté de la programmation, il faut que j'arrive à faire des graphiques, qui permettront d'appréhender le fonctionnement de l'AG et l'influence des paramètres.

Edit 17/02
Je pense que je vais devoir repasser vers Processing et recoder tout ça: plus facile pour les sorties graphiques.....

Edit Delirium
Copier/coller d'un de mes articles FB, remis en page pour le forum.......

[Tété]

Ce mec est fou ... ou génial ...

Quelque soit le resultat, dtf, faut que je farm :cheers:

[Biafoune]

J'ai pas tout lu encore, mais fais gaffe : légende pour Bisco : * c'est pareil que x

Bizzzz

[Woland]

J'ai lu, mais pas compris grand chose ... à part le tenant et l'aboutissant ^^

Mais +1 à Tété : Ce mec est un ouf !

[Nazk]

Jaaxx, je persiste à penser que tu t'es vraiment tromper de jeu ^^
Eve Online avec ses calculs, ses ratios, ses productions, ses réactions en chaine, ses milliers d'AH, et son économie reine à été conçu pour toi !
Je te propose de jeter un coup d'oeil à ce petit guide pour te faire une idée, surtout les parties Manufacturing Research ..




Regarde ça aussi :

[Jaaxx]

[Nazk]

quelques articles intéressants :

[Carlotta]

Nazk, peux-tu redimentionner cette image, c'est pénible pour suivre ce que tu dis. Merci

[Nazk]

Ok !

[Carlotta]

Alors JAcques, on en arrive ou à la fin ? ^^

[Ack]

Si je peux me permettre, quitte a farmer pour un Hf autant farmer utilement. Si on veut de l'optimisation voyons un peu les flacons :

Flacon de peau d'acier: http://fr.wowhead.com/item=58085 = C'est juste indispensable on en consomme FORCEMENT en raid et beaucoup ;
Flacon de l'esprit draconique: http://fr.wowhead.com/item=58086 = Pareil qu'au dessus : Flacon utiliser pour TOUS les raids par les healers et les casters donc grosse consommation ;
Flacon de force titanesque: http://fr.wowhead.com/item=58088 = Flacon assez utile étant donné la récurence de nos CaCs Pal / war / dk ;
Flacon des vents: http://fr.wowhead.com/item=58087 = Flacon utile mais en moindre quantité puisque pas de rogue dans notre roster, et peu de sham amélio et de hunt ;
Flacon de l'eau courante: http://fr.wowhead.com/item=67438 = Flacon juste inutile l'impact de l'intel étant tellement supérieur que celui de l'esprit je n'imagine personne les utilisant sauf par défaut ;
6. Flacon d'amélioration: http://fr.wowhead.com/item=58149 = Flacon assez spécial, assez inutile d'en faire plusieurs étant donné que ça n'est pas consommé et que c'est un BoP.

Voila donc plutôt se concentrer principalement sur les 2 premiers flacons (les plus utilisés/important) en terme de quantité et ensuite sur les 2 suivants dans des quantités moindre. Quant aux deux derniers, assez inutile de gacher des vies la dedans (exception faite de ceux qui veulent le flacons pvp pour eux bien sur !)

[Jaaxx]

Tout à fait Tutur, mais là c'est juste à but didactique pour moi, j'aurai tout aussi bien pu travailler sur une vulgaire fonction du style sinus, .....
Je ne me suis pas posé la question du choix de tel ou tel flacons, mais c'est implémentable dans l'AG.
D'ailleurs j'ai posé l'hypothèse que toutes les plantes avaient le même cout, or certaines sont plus difficiles à farmer, tels les jasmins. J'ai fait aussi l'impasse sur le coût des vies volatiles (meilleur drop loot a Uldum imo). Calculer ces couts necessiterait de faire des stats sur une assez longue periode. Impasse sur tout cela ^^ (on en a débattu sur TS avec PAgounette).
J'ai commencé a travailler sur cet AG avant la normalisation du nombre de compos par flacons. De {0,12,8,6} on est passé à {0,8}, normalisation qui simplifie le choix des flacons a crafter en fonction des ressources (toujours en ne prenant pas en compte ta remarque Ackounet).

Par contre, à l'HV, tous partent trés bien, faut juste cibler le bon jour et la bonne heure :cheers:

Eric: pour l'instant, c'est un peu en stand-by..... ^^

[Pagromf]

[Jaaxx]

Tu voudrais donc, Pagounet, que je lève le stand-by en le prenant par les 2 bouts ?
Pas bête le coup de l'HV, surtout qu'il y a quelques addons qui font des stats pour nous