Pourquoi des algorithmes génétiques(GA) ?
|
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 plusieures
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.
Les 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).
L´application
mouv_gen de cinématique inverse utilisant des
algorithmes génétiques avec des fonctions
fitness de "ressemblance" permettant d´aller vers un mouvement donné ne
permettaient 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.
1) 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
(loi de la
puissnace 1/3)
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) cliquer sur
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.
Fonctionnement automatique
|
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.
Dossier env
Contenant:
*.h: fichier de configuration.
*.auto: exemples.
Aide sur le web.
initb.h
fichier de configuration dans le dossier
distribution_fra/env et racine
distribution_fra.
Fonction en language anyflo.
genetic_emerge.htm
Ce fichier.
Java scrypte lançant l´application.
Main menu
HEL: help.
PARAM:
HEL: help
PARAM
READ rentrer un nom de fichier (après le
>) ou cliquer
sur un
name.auto: lance l´exécution automatique selon 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: invalide toutes les parties, cliquer sur des noms: les parties correspondantes du corps
apparaissent en violet, il leur sera associée une seule génétique.
L_LEG: jambe gauche à laquelle sera associée une
génétique particulière.
R_LEG: jambe droite à laquelle sera associée une
génétique particulière.
L_ARM: bras gauche au laquel sera associée une
génétique particulière.
R_ARM: bras droit au laquel sera associée une
génétique particulière.
SPINE: torse et tête aux quels sera associée une
gé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
BIO: force les contraintes biomécaniques
ILLUM: affichage en plein
VIEW: cliquer sous le trait blanc modifie la vue
SHAD: ombres portées
SKIN: peau
EXT:
extension
COLLISION: les corps sont soumis à la pesanteur et entrent en
contact avec un sol rigide
SPEED: loi de l´
opposition de phase
law: force de la loi
coe: coefficient de propagation
INI: initialisation
EXIT: quitte le programme.
DEUX_POINTS(): cache les échelles, les menus, les messages et les textes.
Principe
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.
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.