Introduction à l’informatique et applications à la biologie

Les fonctions

#include<iostream>
using namespace std;

int absolue(int nombre){
   if(nombre < 0)
     nombre = -nombre;
   return nombre; 
}

int main(){
   int a;
   cin >> a;
   cout << absolue(a) << " " << a;
   return 0;
}

• portée d’une variable (passage par valeur)
• fonction principale (main)

Passage par réference

#include<iostream>
using namespace std;

int absolue(int &nombre){
   if(nombre < 0)
     nombre = -nombre;
   return nombre; 
}

int main(){
   int a;
   cin >> a;
   cout << absolue(a) << " " << a;
   return 0;
}

• qu’est-ce qui a changé?
• attention aux tableaux

Exemple: les algorithmes génétiques

Genetic cars

Application d’un algorithme génétique

• La bibliothèque de département de Biologie de Madrid fait une liquidation totale

• Ils se séparent de 1000 livres

• Après recherche rapide, vous décidez d’en ramener

• Mais… vous rentrez par avion: 23kg max

Problème du “sac à dos” (knapsack)

• Comment sélectionner un choix de livres de valeur maximale n’excédant pas 23kg?

• p. ex. 30 livres parmi 1000 (2.43E+57 combinaisons)  \(\rightarrow\)milliards d’année pour toutes les tester

  L1	L2	L3	L4	L5	L6	…
  500€	2000€	10€	800€	180€	3000€	…
  500g	1500g	800g	200g	50g	2000g	…

  • Les plus chers d’abord?
  • Les meilleurs rapports prix/poids?

Solution par la sélection naturelle (artificielle)

• Le problème du “sac à dos” est prouvé comme insoluble en temps raisonnable \(\rightarrow\) il faut se focaliser sur les combinaisons les plus prometteuses

  • Au départ on crée des valises aléatoires

  • Les meilleures valises se reproduisent le plus

  • On laisse tourner pendant plusieurs générations (de valises càd quelques minutes de simulation)

  • p.ex. 500 valises X 200 générations = 10k combinaisons

Génome des individus

• 1 si le livre est dans la valise 0 s’il n’y est pas

• vecteur de booléens, par exemple:

  0	1	0	1	0	1	…
  500€	2000€	10€	800€	180€	3000€	…
  500g	1500g	800g	200g	50g	2000g	…

• Valeur: 2000+800+3000 = 5800€

• Poids: 1500+200+2000 = 3700g

• Taille d’un génome?

Evaluation des individus

float score(bool adn[nbgenes], int euros[nbgenes], int grams[nbgenes]) {
     float valeur = 0, poids = 0, res;
     for(int i = 0; i < nbgenes; i++) 
        if(adn[i]) {
          valeur += euros[i];
          poids += grams[i];
        }
     if (poids <= 23000)
        res = valeur;
     else
        res = -poids;
     return res;
}

La sélection des meilleurs individus

• probabilité d’être choisi dépend de la performance (fitness) d’un individu

La création des enfants

Crossover (nombre et lieux des points?)

• p.ex. si les livres sont indexés par ordre alphabétique
  • de A à F les choix de la valise maman
  • de G à Z les choix de la valise papa
• Autant d’enfants que de parents (population constante)

La mutation des enfants

Taux de mutation de chaque gène pour chaque individu, p.ex.

\[ 0\ 1\ 0\ 0\ 0\ 1\ 1\ 0\ 1\ 1\ 1\ 1 \]

devient:

\[ 0\ 1\ 0\ \textbf{1}\ 0\ 1\ 1\ 0\ 1\ \textbf{0}\ 1\ 1 \]

• Si on augmente le taux de mutation, que gagne-t-on?

• …et que perd-t-on?

• typiquement entre 1 et 5%

Paramètres de la simulation

const int nbgenes = 1000;       //nb de livres dispos
const int nbindividus = 500;    //nb de valises testées par génération
const float tauxmutation= 0.03;    
const int nbgenerations = 200;

int main () {
   int choix1, choix2, grams[nbgenes], euros[nbgenes];
   bool parents[nbindividus][nbgenes];
   bool enfants[nbindividus][nbgenes];
   float fitness[nbindividus];
   read(grams,euros);
   randomstart(enfants);
   //...simulation...
   afficheMax(parents,fitness);
}

• Seulement 4 paramètres à la simulation!
• une population entière est codée par une matrice de booléens individus X genomes

Code de la simulation

 for(int gen = 0; gen < nbgenerations; gen++) {
     replace(parents,enfants);
     evaluations(parents,euros,grams,fitness);
     
     for(int couple = 0; couple < nbindividus/2; couple++) {
         choix1 = selection(fitness); 
         choix2 = selection(fitness);
         crossover(parents, choix1, choix2, enfants, couple);
         mutation(enfants, couple, tauxmutation);         
     }
 }

• Seule la fonction score est spécifique au problème
• score étant appelée ici par la fonction evaluations

Leçons des algorithmes génétiques

• Choix implicite dans la fonction d’évaluation
• Démarrage et arrêt de la simulation
• Conservation des meilleurs (élitisme), efficace?
• Elimination des faibles (idéologie aryenne), efficace?
• Sélection sexuelle, efficace?
• Plusieurs (>2) parents, efficace?
• Processus épigénétiques (Lamarck vs Darwin), efficace?