Les méthodes analytiques traditionnelles ne peuvent résoudre que des problèmes parfaitement
bien posés et dont on connait un algorithme de résolution.
Mais la plupart des problèmes
réels ne sont pas clairement posés, et leur solution, quand il en existe une,
n´est pas nécessairement calculable en un temps fini.
Un problème peut avoir plusieurs
solutions, ou même ne pas en avoir du tout, que faire dans ce cas sinon chercher le meilleur compromis
possible: ce n´est donc pas tellement la recherche de l´optimum qui compte, mais bien plutôt
d´améliorer ce qui est possible.
Leas AG sont une méthode d´optimisation caractérisée par:
1) Ils travaillent sur un codage arbitraire des paramètres (et non par sur les paramètres
eux-mêmes), ce qui évite d´introduire une signification qui biaiserait la recherche des
solutions.
2) Ils travaillent sur des populations, c´est à dire en parallèlle, ce qui
évite de tomber dans un optimum local.
3) Ils utilisent les valeurs de la fonction (et non pas ses dérivées ou d´autres
propriétés particulières).
4) Ils utilisent des règles de transition probabilistes (et non pas déterministes).
Principle
L´application mouv_gen.htm montrait une méthode
de cinématique inverse utilisant des algorithmes génétiques avec des fonctions
fitness de "ressemblance" permettant d´aller vers un mouvement donné mais ne
permettant pas d´inventer de nouveaux mouvements.
La présenta application propose une méthode pour faire émerger de nouveaux
mouvements réalistes à partir de populations aléatoires obéissant à
des fonctions de fitness opérant un contrôle biomécanique ou des lois de la
physiologie des mouvements naturels.
Comment construire une génétique
1) Cliquer sur PARAM
1-1) puis cliquer sur PICK
1-1-1) puis cliquer sur ITEM, puis sur certains items
(L_FOOT, L_TIB, ...)
1-1-2) ou sur L_LEG, R_LEG, ...
1-2) puis cliquer sur FITNESS
1-2-1) puis cliquer sur BIO (contrôle biomécanique)
1-2-2) ou sur LAW
(La loi de la puissance un tiers)
1-3) puis cliquer sur TRAJ
1-3-1) puis cliquer sur ROTA (rotation)
1-3-2) ou sur ROTA_AXIS (rotation et axe)
1-3-3) ou sur FORCE_ROTA (couple de forces)
1-3-4) ou sur QUAT (quaternion)
2) Cliquer sur GEN
2-1) puis cliquer sur BUILD
2-1-2) puis cliquer sur population (changer la taille de la
génétique)
2-1-2) puis cliquer sur see (nombre de corps visualisés)
2-1)puis cliquer sur EVOLVE lance lévolution (croisement
et mutation), les notes apparaissent sur des échelles.
2-2) puis cliquer sur ADJUST si l´évolution est stoppée.
2-3) puis cliquer sur FITNESS montrant le code de la fitness courante.
2-4) click on OFF stoppe le processus d´évolution.
2)Comment écrire une fonction FITNESS function
voir les exemples de fonctions :
FITNESS_ROTA(g,num,p)
FITNESS_FORCE_ROTA(g,num,p,sem)
FITNESS_ROTA_AXIS(g,num,p)
FITNESS_QUAT(g,num,p)
Remarque:
Pour programmer en C cette application hors anyflo il sera nécessaire de:
1) programmer les algorithmes génétiques.
2) programmer les quaternions et leur interpollation sphérique.
3) programmer une interface temps réel pour l´interaction.
Automatic working
Le menu PARAM->WRITE permet de garer un fichier name.auto contenant les
paramètres actuels: rentrer un nom après le > ou cliquer sur un
name.auto (attention celui-ci sera écrasé).
Le menu PARAM->READ permet de charger un fichier: cliquer sur un name.auto:
les paramètres sont initialisés: le processus (croisements et mutations)
est lancé selon les paramètres du fichier lu. Tous les menus restent accessibles.
Contenu
Dossier env
Contenant:
*.h: fichier de configuration.
initb.h
fichier de configuration dans le dossier distribution_eng/env et racine distribution_fra.
PARAM READ rentrer un nom de fichier (après le >) ou cliquer
sur un name.auto: lance l´exécution automatique selob les paramès
stocké:s dans ce fichier.
WRITE rentrer un nom de fichier (après le >) ou cliquer
sur un name.auto (mais attention il sera écrasé): les paramètres
courrants seront stockés dans ce fichier.
PICK ITEM: cliquer sur des noms: les parties correspondantes du corps
apparaissent en violet, il leur sera associée une seule g&eacuté;nétique.
L_LEG: jambe gauche à laquelle sera associée une
g&eacuté;nétique particulière.
R_LEG: jambe droite à laquelle sera associée une
g&eacuté;nétique particulière.
L_ARM: bras gauche au laquel sera associée une
g&eacuté;nétique particulière.
R_ARM: bras droit au laquel sera associée une
g&eacuté;nétique particulière.
SPINE: torse et tête aux quels sera associée une
g&eacuté;nétique particulière.
FITNESS BIO: contraintes biomécaniques.
LAW: loi de la puissance 1/3.
TRAJ ROTA: rotation en z
ROTA_AXIS: rotation autour d´un axe
FORCE_ROTA: coupled dynamiques autour d´un axe
QUAT: quaternions
GEN HEL: help
POPUL modifier les échelles:
ni: taille des trajectoires
nb_key: nombre de clés définissant une trajectoire
nb_bits: nombre de bits de codage des mots du génome
population: nombre d´individus des génétiques
see: nombre de corps affichés
muta: probabilit&eac ute; de mutation
EVOLVE: lance l´évolution, les notes apparaissent
ADJUST: ajustement automatique des mutations dans le cas où une
génétique serait bloquée
FITNESS: affiche le code de la fonction de fitness courante
OFF: stoppe lévolution
SCALES: modifier les échelles
NOTES: fait apparaître les notes
PART: fait apparaître les particules
NONE: fait disparaître les échelles, notes et les particules
Les génétiques sont constituées de
Dim_POP[2] individus appelés
particules. Un processus d´évolution
darwinienne régénère une population par croisements et mutations
aléatoires des individus qui sont notés par des fonctions de fitness qui
sont, en fait, l´évaluation de chaque individu par la mesure de son comportement
(animation selon les trajectoires codées dans son génome) sur un certain nombre
d´images en référence à cette fonction de fitness.
On a défini, à titre d´exemple, 2 types:
Type_FITNESS=Type_FITNESS_BIO: respect des contraintes biomécaniques
Type_FITNESS=Type_FITNESS_LAW: respect de la
(loi de la puissance un tiers)
One, or several,genetics can be defined (depending on the designation of the body parts which are animated).
À chaque particule est associé un corps qui est son génotype
dont les mouvements sont codés sur des mots de Nb_Bit=6 selon le type Type_TRAJ
du mouvement. Celui-ci est défini par une trajectoire de
Nb_KEY[2] clés étendue en une cubique de Ni[2] points.
On a défini, à titre d´exemple, 4 types:
Type_TRAJ=Type_TRAJ_ROTA: rotations (1D: angle)
Type_TRAJ=Type_TRAJ_ROTA_AXIS: rotation autour d´un axe (4D: angle,axe)
Type_TRAJ=Type_TRAJ_FORCE_ROTA: couples dynamiques (4D: force,axe)
Type_TRAJ=Type_TRAJ_QUAT: quaternions (4D: w,x,y,z)
Chaque mouvement est évalué par une fonction de fitness(g,num,p)
(g=identificateur de la génétique associé, num=numéro de la particule
considérée, p=cette particule), on a défini 4 fonctions correspondant
aux 4 types de mouvements définis plus haut:
FITNESS_ROTA(g,num,p)
FITNESS_FORCE_ROTA(g,num,p,sem)
FITNESS_ROTA_AXIS(g,num,p)
FITNESS_QUAT(g,num,p)
La note est en fait la moyenne des 2 notes obtenues selon Type_FITNESS:
biomécanique (voir le code de ces fonctions dans le fichier
genetic_emerge.func)
loi de la puissance 1/3 (voir un extrait du code en C)
Interaction
Deux call backs:
F0() d´initialisations
F5() appelé à chaque image et affichant les menus, différents
messages et appelant des call backs spécifiques selon les cases des menus qui ont
été cliqués. Par exemple:
PARAM->READ et PARAM->WRITE permettent de lire et décrire les
paramètres courrants dans des fichiers *.auto voir:
ALL_BIO_ROT.auto: contraintes biomécaniques sur
tout le corps avec des rotations.
ARM_BIO_LAW_QUA.auto: contraintes biomécaniques
et loi de la puissance 1/3 sur les bras avec des quaternions.
ARM_LEG_BIO_ROTA.auto: contraintes biomécaniques
sur les bras et les jambes avec des rotations.
SPI_BIO_FOR.auto: contraintes biomécaniques sur
le torse par des couples dynamiques.
Exemples
Fonctionnement automatique
Cliquer sur PARAM
Cliquer sur READ
Cliquer sur ARM_LEG_BIO_ROT.auto: un corps apparait en mouvement exagéré,
les notes des 4 génétiques associées aux 4 membres apparaissent en violet,
les notes moyennes (en vert) progressent tandis que les mouvements deviennent plus naturels
Définition manuelle
Cliquer sur PARAM
Cliquer sur PICK
Cliquer sur L_ARM
Cliquer sur FITNESS
Cliquer sur LAW
Cliquer sur TRAJ
Cliquer sur QUAT Cliquer sur GEN
Cliquer sur POPUL
choisir population=25
choisir see=1
Cliquer sur EVOLVE: le processus d´évolution est lancé, un corps
apparait avec le bras gauche en mouvement, la trajectoire de la main est en blanc et les positions
successives sont en vert, les notes apparaissent en violet. La note moyenne (en violet) progresse.
Il se peut qu´elle se bloque, cliquer alors sur ADJUST, ce qui a pour effet de
rendre les mutations dépendantes de l´évolution, les notes se diversifient,
recliquer sur ADJUST, l´évolution reprend alors normalement.
On constate que les points verts sont espacés lorsque le rayon de courbure est grand et
concentrés lorsque ce rayon est faible, ce qui traduit exactement la loi de la puissance 1/3.