Devoir 2014

Application des algorithmes génétiques

Minimisation en 2 dimensions


Le sujet est là, mais il est possible, que quelques détails y seront modifiés/ajoutés, si vous posez des questions...


Généralités

Votre devoir de cette année est consacré à l'application des algorithmes génétiques à un très simple, académique problème d'optimisation : la minimisation de la fonction de Rastrigin. Voici sa forme en 2 dimensions :

$\displaystyle{R(x,y) = 20 + x^2 + y^2 - 10\cdot(\cos(2\pi x)+\cos(2\pi y))}\,.$

(En 3 dimensions, ou plus, Wikipédia vous donne la formule générale).

C'est une fonction assez "méchante", voici son graphique 3D ($Z=f(X,Y)$) et les isolignes (contours) ; la fonction possède un minimum global et plusieurs minima locaux, assez profonds :

 

Vous n'avez pas encore vu les A.G. en cours, jetez-y un coup d'oeil, lisez la littérature. Cette approche est ou sera encore couverte [sauf erreur de ma part] également par Arnaud L. dans son cours sur les Métaheuristiques. Plein de choses à apprendre...

Programmation

Les graphiques montrent l'espace -4 : 4, mais vou devez chercher le minimum entre -5 à 5 selon chaque axe. Il existent de nombreux frameworks facilitant la tâche, en Python vous avez PyGene, Pyevolve, DEAP, etc. En particulier Pyevolve est très bien documenté, et peut vous inspirer.

Je suggère également une solide "usine" : HeuristicLab avec des exemples, documentation, etc. Le paquetage est basé sur la plate-forme .net, donc c'est plutôt Windows, même s'ils mentionnent Mono... Je n'ai pas eu le temps de creuser.

mine assez riche, même si partiellement obsolète.

La construction des "chromosomes" est à vous, sans cela il est difficile de parler de mutations et de cross-overs. Utilisez - par exemple - le codage binaire, avec un nombre fixe de bits pour chaque coordonnée (axe). Lisez des articles comme celui de Jenna Carr et de Leo Budin.


Le programme doit tourner soit jusqu'à la convergence vers le minimum avec une précision prédéfinie, ou jusqu'à l'arrêt par l'utilisateur. Il doit afficher dynamiquement le minimum courant (la valeur et les coordonnées), éventuellement quelques autres paramètres, mais ceci ne doit pas ralentir trop l'exécution.

À la fin, l'utilisateur sera informé de la valeur et des coordonnées, et d'utres détails, comme le nombre de générations, des populations globales, etc.

Modalités



Retour