quelque lignes directives pour implémenter l'algorithme génétique

Page 2 sur 2 Précédent  1, 2

Voir le sujet précédent Voir le sujet suivant Aller en bas

Re: quelque lignes directives pour implémenter l'algorithme génétique

Message  -ed- le Mer 17 Juin 2009 - 16:06

potter a écrit:Bonjour,

Je vous remercie pour le temps que vous me consacrez pour m'aider.

Le problème d'optimisation est la minimisation de y=- ( x^ 2 ) +5).
Que signifie 'minimisation' ? L'informaticien n'est pas censé être omniscient. Chaque application métier de l'informatique a ses spécialités qu'il faut expliquer à l'informaticien.

Je suis spécialisé en télécom. Si je te parle de couche, d'OSI, de protocole ou de CRC, tu vas me faire des yeux ronds, et c'est normal.

Le premier pas dans l'implantation des algorithmes génétiques est de créer aléatoirement une population d'individus initiaux(les chromosomes, les x ici). Par analogie avec la biologie, chaque individu de la population est codé par un chromosome ou génotype .
Un individu est caractérisé par un gènotype, c'est à dire un certain nombre de chromosomes (cariotype) composé de chacun de chaines d'ADN dont les séquences de nucléotides CGAT forment des gènes... Il y a environ 27000 gènes dans le génotype humain...

J'ai un peu du mal à voir la relation avec 'algorithme génétique'.

Et puis un algorithme est destiné à effectuer un certain traitement. Je n'ai toujours pas compris lequel...

Je suis en train de lire ceci

http://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n%C3%A9tique

ca devrait m'aider. C'est donc un problème de math et pas de généique... C'était pas évident à comprendre...


Une population est donc un ensemble de chromosomes. Chaque chromosome code un point de l'espace de recherche.
chaque entier xi est codé ici à l'aide de 5 bits (00000). Par exemple, la chaîne:

01111( de valeur 16) 11111(de valeur 10) 00001(de valeur 11) 11110(de valeur 5)
C'est là que je décroche.

01111 en binaire = 15 en décimal. Pourquoi 16 ?
de même
11111 = 31 et non 10
00001 = 1 et non 11
11110 = 30 et non 5

Je ne vois pas d'où tu sors ces valeurs. Ou alors tu appliques une formule étrange que je ne connais pas mais qui n'a rien à voir avec la conversion binaire -> décimal.

La fonction fitness (Y=-x²+5) est une fonction qui permet d'évaluer chaque chromosome. Pour calculer le fitness d'un individu, il faut décoder la chaîne de bits(la fonction chro_x) afin d'y retrouver la solution potentielle.
code les valeurs x0 = 16, x1 = 10, x2 = 11, x3 = 5.
Tant que ce qui précède n'est pas clarifié, inutile d'aller plus loin en ce qui me concerne.

_________________
C is a sharp tool !

-ed-
Admin
Admin

Messages : 289
Date d'inscription : 26/05/2008
Age : 60
Localisation : Paris 6eme arrondissement (75, France)

Voir le profil de l'utilisateur http://bien-programmer.fr

Revenir en haut Aller en bas

Re: quelque lignes directives pour implémenter l'algorithme génétique

Message  potter le Mer 17 Juin 2009 - 18:36

Bonjour,

-ed- a écrit:Que signifie 'minimisation' ?
Voilà un problème de minimisation qui consiste à déterminer la solution permettant de minimiser une fonction mathématique tout en respectant certaine contraintes.
Ceci un problème de minimisation de cout de production:
On écrit comme suit :
Min C=x1 – 2x2, où x1 et x2 sont les quantités à produire de l'article 1, 2
les contraintes
(1)cout de main d'œuvre :-4x1 + 6x2 <= 9
(2)capacité de production : x1 + x2 <=4
(3)intégrité : x1, x2 >= 0

graphiquement est représenté par l'espace coloré(ensemble des solutions réalisables)

->il s'agit de déterminer la quantité optimale(x1 et x2) pour minimiser les couts totaux de production.


-ed- a écrit:J'ai un peu du mal à voir la relation avec 'algorithme génétique'.

Et puis un algorithme est destiné à effectuer un certain traitement. Je n'ai toujours pas compris lequel...

Je suis en train de lire ceci

http://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n%C3%A9tique

ca devrait m'aider. C'est donc un problème de math et pas de génétique... C'était pas évident à comprendre...
Ah, Oui.l'article wiki est intéressant mais ne propose pas des exemples.

-ed- a écrit:Une population est donc un ensemble de chromosomes. Chaque chromosome code un point de l'espace de recherche.
chaque entier xi est codé ici à l'aide de 5 bits (00000). Par exemple, la chaîne:

01111( de valeur 16) 11111(de valeur 10) 00001(de valeur 11) 11110(de valeur 5)
C'est là que je décroche.

01111 en binaire = 15 en décimal. Pourquoi 16 ?
de même
11111 = 31 et non 10
00001 = 1 et non 11
11110 = 30 et non 5

Je ne vois pas d'où tu sors ces valeurs. Ou alors tu appliques une formule étrange que je ne connais pas mais qui n'a rien à voir avec la conversion binaire -> décimal.
J'ai pris un exemple par hasard Laughing

potter
Bavard
Bavard

Messages : 18
Date d'inscription : 24/11/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: quelque lignes directives pour implémenter l'algorithme génétique

Message  potter le Jeu 18 Juin 2009 - 1:08

Voilà -ed- un document intéressant sur l'algorithme génétique(içi adéquation c'est fitness)
En attente de votre retour.Merci.

No Je vous attends -ed-.
Voici mon code :
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NB_BIT 5
typedef struct
{
  unsigned bit[NB_BIT];
  int fitness;
  int value;
}
chromosome;

void affichage (chromosome const tab[], int n)
{
  int i;
  for (i = 0; i < n; i++)
  {
      int j;
      printf("tab[%d]=", i);
      for (j = 0; j < NB_BIT; j++)
      {
        printf ("%d", tab[i].bit[NB_BIT - 1 - j]);
      }
      printf ("\tvalue=%d\tfitness = %d\n", tab[i].value, tab[i].fitness);
  }
}

int chro_x (chromosome * p)
{
  int x;

  x = (1 * p->bit[0])
      + (2 * p->bit[1])
      + (4 * p->bit[2]) + (8 * p->bit[3]) + (16 * p->bit[4]);

  return x;

}

int chro_y (int x)
{
  int y = -(x * x) + 5;
  return y;
}

void pop_initial (chromosome tab[], int n)
{
  int i, value;
  for (i = 0; i < n; i++)
  {
      int j;
      for (j = 0; j < NB_BIT; j++)
      {
        tab[i].bit[j] = rand () % 2;

        value = chro_x (tab + i);
        tab[i].fitness = chro_y (value);

      }
  }
  return 0;
}                              /* -ed- */

int main (void)                /* -ed- */
{
  chromosome tab[4];

  srand ((unsigned) time (NULL));
  pop_initial (tab, 4);
  affichage (tab, 4);

  return 0;
}
J'attends votre avis -ed- Puis-je l'optimiser pour réduire son temps d'exécution ?

potter
Bavard
Bavard

Messages : 18
Date d'inscription : 24/11/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: quelque lignes directives pour implémenter l'algorithme génétique

Message  Contenu sponsorisé Aujourd'hui à 15:28


Contenu sponsorisé


Revenir en haut Aller en bas

Page 2 sur 2 Précédent  1, 2

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum