Some links may not be active (if the application is not in the folder env / applications / mouv_gen the distributed version).
Why genetic algorithms (GA) ?
|
The traditional analytical methods can solve only perfectlywell posed problems and which we know a resolution algorithm.
But most of the real problems are not clearly established, and their solution, when it exists, is not necessarily computable in a finite time.
A problem may have several solutions, or even not having one at all, what to do in this case if seeking the best possible compromise:
it is not so much the search for the optimum that counts, but rather to improve what is possible.
The GA are an optimization method characterized by:
1) They work on arbitrary
encoding parameters (and not the parameters themselves), which avoids introducing a meaning that would bias the search for solutions.
2) They work on populations, ie in
parallel, which avoids falling into a local optimum
3) They use the values of the function (and not its derivatives or other special properties).
4) They use
probabilistic transition rules (not deterministic).
The application
mouv_gen.htm provides a methode of inverse kinematic
with genetic algorithms with some "likes" fitness functions allowing to reach a given movement
but not allowing to create some new movements.
The actual application provides a method allowing new movements to emerge from random populations
following some fitness functions as biomecacanical constraints or some natural laws of movement.
How build a genetic
1) Click on
PARAM
1-1) then click on
PICK
1-1-1) then click on
ITEM, then on some items (
L_FOOT, L_TIB, ...)
1-1-2) or on
L_LEG, R_LEG, ...
1-2) then click on
FITNESS
1-2-1) then click on
BIO (biomecanic law)
1-2-2) or on
LAW
(
power 1/3 law)
1-3) then click on
TRAJ
1-3-1) then click on
ROTA (rotation)
1-3-2) or on
ROTA_AXIS (rotation and axis)
1-3-3) or on
FORCE_ROTA (torque)
1-3-4) or on
QUAT (quaternion)
2) Click on
GEN
2-1) then click on
POPUL
2-1-2) then click on
population (choose genetic size)
2-1-2) then click on
see (choose number of visualized bodies)
2-1) then click on
EVOLVE launching the evolution process (cross over
and mutation), notes appear on scales.
2-2) then click on
ADJUST if the evolution is stopped, the mutations will
be automatically modified.
2-3) click on
FITNESS showing the fitness function code.
2-4) click on
OFF stops the evolutionary process.
2)How to write a FITNESS function optimization
see example functions
:
FITNESS_ROTA(g,num,p)
FITNESS_FORCE_ROTA(g,num,p,sem)
FITNESS_ROTA_AXIS(g,num,p)
FITNESS_QUAT(g,num,p)
Note:
For programming in C (out anyflo) this application it will be necessary:
1) programmed genetic algorithms.
2) program quaternions and spherical interpollation.
3) schedule a real-time interaction interface.
The menu PARAM->WRITE allows saving a file name.auto containing the actual
paramaters: enter a name after the > or click on one name.auto
The menu PARAM->READ allows loading a file: click on one name.auto: the
parameters are initialized. Then click on EVOLVE: the evolutionary process
(cross over and mutations) is launched.
Folder env
Containing:
*.h: configuration files.
initb.h
Configuration file in folder distribution_eng/env and root distribution_eng.
Function in anyflo language.
genetic_emerge.htm
This file.
Java scrypte launching the application.
Main menu
HEL: help.
DOC: an example.
PARAMN">GEN:
HEL: help
GEN:
ITEM: choose L_FOOT, L_TIB, ...
L_LEG: validates left leg.
R_LEG: validates left leg.
L_ARM: validates left arm.
R_ARM: validates right arm.
SPINE: validates spine (chest and head).
FITNESS:
BIO: biomecanic law.
LAW: power 1/3 law.
TRAJ:
ROTA: traj rota
ROTA_AXIS: traj rota axis
FORCE_ROTA: traj force rota
QUAT: traj quat,
quaternions.
GEN:
BUILD: buildung genetics
change the
SCALES: showing the scales
nb key: number ok keys on trajectories
nb bits: number of codage bits for the genomes
population: nombre of individuals in a population, to any individu is associated
a genome and a body which will be animated and noted according to it fits the fitness function
see: number of bodies diaplayed
line: coefficient of
meta validate
muta: mutation probability
NOTES: showing the notes
PART: showing the particles (genetic individuals)
NONE: hides scales and notes
BIO: forcing the biomecnical control
ILLUM: yes/no illumination
VIEW: click below the horizontal line changes the view
SHAD: yes/no shadow (when COLLISION is acyive)
SKIN: skin/body
EXT: yes/no ext
COLLISION: yes/no collision
BEHAVE: automatic behavior (when COLLISION is active)
ACC: opposion phase law on acceleration, change the scales law_acc
and coe
SPEED: opposion phase law on speed, change the scales law_speed
and coe
DEUX_POINTS(): inhibits display of scales, menus, messages, texts.
INI: initialization
EXIT: exites the program.
Principe
The genetics are made of Dim_POP[2] individuals
called particles.
A process of Darwinian evolution by random crossovers and mutations regenerates a population of individuals
that are rated by fitness functions which are, in fact, the assessment of each individual by measuring its behavior
(animation paths according to its encoded genome) on a number of images in reference to the fitness function.
Was defined, for example, two kinds:
Type_FITNESS=Type_FITNESS_BIO: respect the biomechanical constraints
Type_FITNESS=Type_FITNESS_LAW: respect of the
(power law third)
Une, ou plusieures, génétiques peuvent être définies (selon le mode
de désignation des parties du corps qui sont animées).
Each particle is associated with a body which is its genotype whose movements are coded on
words size Nb_Bit=6 according the type Type_TRAJ of movement. It is defined by a path of Nb_KEY [2] keys
in an extended cubic of Ni [2] points. Was defined, for example, four types:
Type_TRAJ=Type_TRAJ_ROTA: rotations (1D: angle)
Type_TRAJ=Type_TRAJ_ROTA_AXIS: rotation about an axis (4D: angle,axe)
Type_TRAJ=Type_TRAJ_FORCE_ROTA: dynamic torque (4D: force,axe)
Type_TRAJ=Type_TRAJ_QUAT: quaternions (4D: w,x,y,z)
Each movement is evaluated by a fitness function (g, num, p) (g = identifier of the associated genetic,
num = number of particle considered, p = the particle) was defined four functions corresponding to the
4 types of movements defined above:
FITNESS_ROTA(g,num,p)
FITNESS_FORCE_ROTA(g,num,p,sem)
FITNESS_ROTA_AXIS(g,num,p)
FITNESS_QUAT(g,num,p)
The rating is actually the average of the 2 scores according Type_FITNESS:
biomechanics (see the code for these functions in the file
genetic_emerge.func)
power law 1/3 (see the code in C language in file
genetic_emerge.func)
Interaction
Deux call backs:
F0() initializations
F5() called every image displaying the menus, various messages and
calling another specific call backs according the clicked case of the menu.
For example:
PARAM->READ and PARAM->WRITE allowing read and write the current
parameters in files *.auto voir:
ALL_BIO_ROT.auto: biomechanical constraints on
the entire body with rotations.
ARM_BIO_LAW_QUA.auto: biomechanical constraints
and power law 1/3 on the arm with quaternions.
ARM_LEG_BIO_ROTA.auto:biomechanical
constraints on the arms and the legs with rotations.
SPI_BIO_FOR.auto: biomechanical constraints on the
torso by dynamic torqules.
Automatic working
Click on PARAM
Click on READ
Click on ARM_LEG_BIO_ROT.auto: an exagerated moving body appears,
notes of the 4 genetics associated with the 4 limbs appear in purple,
the average notes(green) advence while mouvments become more natural.
Manual definition
Click on PARAM
Click on PICK
Click on L_ARM
Click on FITNESS
Click on LAW
Click on TRAJ
Click on QUAT
Click on GEN
Click on POPUL
choose population=25
choose see=1
Click on EVOLVE: the evolutionary process is started, a body appears with the left
arm movement, the trajectory of the hand is white and the successive positions are green, the notes appear
in purple. Average rating (purple) increased. It may be blocked, then click on ADJUST, which has
the effect of making dependent changes of evolution, notes diversify, click again ADJUST, evolution then resumes
normally. It is found that the green dots are spaced when the radius of curvature is large and concentrated when
the radius is small, reflecting exactly the power law 1/3.