CADCOM/MANUEL D'UTILISATION
 
ALGORITHMES GENETIQUES
 1) Rappels biologiques
Les algorithmes génétiques sont basés sur la théorie de la sélection naturelle de 
Darwin et de la génétique moderne.
  Sélection naturelle
   Dans la lutte pour leur survie,les individus les plus adaptés à leur environnement
   ("fit") survivent plus longtemps et se reproduisent plus facilement. 
  
  Génétique 
   Les lois de l'hérédité font appel aux notions de croisements et mutations,
   L'évolution et l’adaptation des espèces s'explique en évoquant le facteur
   "chance(ou hasard)",cad que les espéces évoluent sans but prédéterminé.
     


2) Algorithme

 
La population initiale est définie comme un ensemble de N individus.
Chaque individu est représenté par un ou plusieurs chromosomes.
Chaque chromosome comprend un nombre de gènes égal aux variables à
optimiser et dont la valeur(alléle) est fournie par notre tableau d'entrée.  

 Codage des variables  
 
Le codage le plus utilisé est binaire car on peut facilement coder et décoder 
toutes sortes d’objets : des réels, des entiers, des valeurs booléennes,
des chaînes de caractères.Le codage de Gray…
 
Chaque géne est donc représenté par une chaine de bits. 

 
Les schémas de codification habituels sont de 3 types.
         . le codage génétique
         . le codage des chemins
         . le codage des différences

      Le codage génétique
        Chaque valeur dans la chaîne représente une variable
        indépendante.Cela veut dire que chaque valeur peût
        prendre tout élément autorisé de l'algorithme
        génétique,indépendamment des éléments utilisés pour les
        autres valeurs.
      Le codage des chemins
        La chaîne représente un chemin ou une route.
        Les valeurs de la chaine génétique ne sont pas
        indépendantes.
      Le codage des différences
        La premiére itération utilise le schéma du codage
        génétique.Aprés la premiére itération,la meilleure
        solution est utilisée comme template.Une nouvelle
        population initiale est crée,mais cette fois chaque
        valeur dans la chaine génétique représente un
        changement(ou delta) par rapport au template.
création d'une population initiale 
      La génération est en général aléatoire.mais peut être également dirigée.
      
définition de la fonction fitness  
     La fitness mesure,la qualité de l'individu exprimée sous forme
    d'un nombre ou d'un vecteur.
    On dit qu'un individu i est meilleur que l'individu j 
    quand i est plus proche de la solution que j.
Evaluation de tous les individus de la population initiale 
    Les individus sont classés suivant la valeur de leur fitness.
b)Sélection des parents 
      La méthode élitiste
        La probabilité de reproduction d'un individu est proportionnelle 
        à sa fitness relative 
      La méthode aléatoire
Generation de nouveaux individus. 
     
     Pour assurer sa reproduction ,on fait appel à des opérateurs genetiques.
       Mutation. 
        cet opérateur substitue 1 ou plusieurs bits d'un individu aléatoirement
        par une nouvelle  valeur (0 or 1). 
         
       Croisement(Crossover) 
        cet opérateur échange des parties de bits d'un individu 
        avec les parties correspondantes d'un autre  individu.
       


Organigramme général

  
  
 


 






Webmaster:
Last revised:05/2000