Émergence génétique

download
vidéo: contraintes biomécaniques
vidéo: loi de la puissance un tiers
Pourquoi des algorithmes génétiques (GA) ?
Principe
Fonctionnement automatique
Contenu
Les menus
Le programme
Exemples



















































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).

Principe


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.

Contenu

Dossier env

Contenant:
*.h: fichier de configuration.
*.auto: exemples.

AIDE_ANYFLO_WEB.htm

Aide sur le web.

initb.h

fichier de configuration dans le dossier distribution_fra/env et racine distribution_fra.

genetic_emerge.func

Fonction en language anyflo.

genetic_emerge.htm

Ce fichier.

genetic_emerge.js

Java scrypte lançant l´application.

Les menus


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.

Le programme

principe
interaction

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.

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.