Discussion :

[italiasky]

Bonsoir,

Dans le cadre d'algorithme génétique, je dois créer une fonction qui croise deux listes selon une probabilité donnée mais en fait je ne vois pas trop comment faire... si quelqu'un pouvait me guider...

En entrée de la fonction, je pense qu'il faut déja les 2 listes "parents" + la probabilité donnée et en sortie on a donc une liste "enfant".

Mais je sais pas trop comment partir...

Merci
Bonne soirée...


Ps : en espérant être dans le bon forum, sinon désolez...

[méphistopheles]

je suppose que pour une liste à n éléments, tu choisit au hasart x éléments dans la liste mère et n-x éléments dans la liste "père" , et tu les compile en une seule liste enfant. sauf, si un morceau de chaque élément de chaque liste doit se mélanger à l'élément de l'autre liste avant de donner la liste enfant (un peu comme dans le génétisme animal) auquel cas il faudrais nous donner quelles sont tes contraintes de césure et de réassemblage .


salut

[jobherzt]

qu'est ce que tu entends par "selon une probabilité deonnée" ?? comme je le comprend, je ferais un simple truc comme ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
liste resultat <- []
de i=1 a tailleDeLaListe
   tire un nombre n au hasard entre 0 et 1
   si n < probabilité
      resultat[i] <- liste1[i]
   sinon
      resultat[i] <- liste2[i]
   fin si
fin de
 
return resultat

[italiasky]

et bien en fait ce que j'ai compris moi, c'est qu'il faut intervertir les éléments des 2 listes parents selon une probabilité, donc par exemple si la probabilité est 0,5
on prend 1 sur 2...

Enfin c'est ce que j'ai compris, voici l'énoncé de la question exactement, comment le comprenez-vous ?

"Croiser deux listes, c'est à dire intervertir les éléments des deux listes selon une probabilité donnée (proba) pour chaque position dans la liste (tirage aléatoire et comparaison avec la probabilité"

Et donc ensuite on peut choisir proba tel qu'on veut. Dans la pluspart des exemples a faire ensuite : proba = 0,5.


Merci Bonne journée

[jobherzt]

ben tel que je le comprends, c'est exactement ce que je t'ai donné, mais avec 2 listes en sortie.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
de i=1 a tailleDeLaListe
   tire un nombre n au hasard entre 0 et 1
   si n < probabilité
      Swap(liste1[i], liste2[i])
   fin si
in de

[italiasky]

Euh donc selon vous, on a deux listes au départ, et on en récupère 2 en sortie ?

swap ca veut dire quoi ?

Par exemple, on a 2 listes de bits en entrée :
L1 : 0 1 1 0 1
L2 : 1 1 1 0 0

On va donc faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
Pour i=1 à 5
    n = nombre décimal aléatoire entre 0 et 1
 
    Si n<proba
 
       ... je ne comprends pas trop ce qui se passe ici...
       Alors... Sinon ?
 
    Fin Si
 
Fin Pour

Merci de votre aide

[jobherzt]

je te cite :

"Croiser deux listes, c'est à dire intervertir les éléments des deux listes

c'est ce mot "intervertir" qui me fait dire que ca va retourner 2 listes. on parcourt les listes simultanement, a chaque etape, on tire un nombre au hasard. si ce nombre est plus petit que la proba demandée, on echange le ieme element de la liste 1 et celui de la liste 2, c'est ca que veut dire swap, c'est un reccourci, j'aurais pu ecrire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
temp <- liste1[i]
liste1[i] <- liste2[i]
liste2[i] <- temp

[italiasky]

Ah ok merci

oui parce que moi ca me genais un peut ce mot "intervertir" parce que je voyais plus le croisement comme le modele en génétique : 2 parents qui donne un enfant qui contient les genes des 2 parents...

Mais comme vous m'expliquez, ca colle tout a fait avec la question quand je la relis après avoir lu votre explication...

Donc du coup, mon algo devient bien :

Entrée : liste1, liste 2
Sortie : liste3, liste 4

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
 
liste3 <- liste1
liste4 <- liste2
 
Pour i de 1 à taille_liste de 1 en 1
    n_al = nombre décimal aléatoire entre 0 et 1
 
    Si n_al<proba
          Alors  // on échange l'élément i des 2 listes
                  temp <- liste3[i]
                  liste3[i] <- liste4[i]             
                  liste4[i] <- temp
    Fin Si
 
    retourner ???
 
Fin Pour

Mais j'ai un petit problème, comment je vais faire pour retourner les 2 nouvelles listes ?
Dans mon cas ce sera des listes chainées en C, mais il me semble que dans une fonction on peut retourner qu'une seule chose nan ?

Merci

[Sivrît]

c'est ce mot "intervertir" qui me fait dire que ca va retourner 2 listes. on parcourt les listes simultanement, a chaque etape, on tire un nombre au hasard. si ce nombre est plus petit que la proba demandée, on echange le ieme element de la liste 1 et celui de la liste 2

Dans ce cas on ne va pas tant retourner deux listes qu'effectuer une opération sur deux listes données en paramètre. La question, suivant le contexte, est doit-on copier ou modifier les listes ?

Edit:

Mais j'ai un petit problème, comment je vais faire pour retourner les 2 nouvelles listes ?
Dans mon cas ce sera des listes chainées en C, mais il me semble que dans une fonction on peut retourner qu'une seule chose nan ?

Soit en définissant une structure qui contient deux listes et sera le type de retour (et peut-être aussi d'entrée), soit en passant en entrée les listes de destination que la fonction ne fera que remplir.

[italiasky]

doit-on copier ou modifier les listes ?

Euh moi je pense que nos 2 listes de départs doivent rester intact et donc il faut en créer deux nouvelles qui sont le fruit du croisement des 2...
C'est pour ca que dans ma fonction au départ, je copierais les 2 listes dans 2 nouvelles mais ensuite comment retourner les 2 ? c'est pas possible si ?

Merci
++

[jobherzt]

je pense qu'on doit les retourner, car en general un meme parents peut etre "impliqué" dans plusieurs accouplements. :-) mais a la limite il suffit de les copier au prealable et passer les copies par references.

en fait, il y a bien l'idee {papa,maman} -> enfant, mais pour que l'algo fonctionne, il faut que le nombre d'individu soit stable (et meme constant en general). Donc decider que 2 parents vont donenr 2 enfants est une maniere de faire.

Apres, il y en a d'autre, pas forcement moins bonne au contraire. on peut decide que chaque "mariage" ne donne qu'un enfant, mais faire 2 fois plus de mariage. a priori, cela introuit plus de diversité genetique.

[italiasky]

Oui donc il faudrait au préalable d'appeler la fonction, dupliquer les parents et ensuite appelé la fonction qui renvoie rien mais qui modifiera les listes parents en enfants...
Sauf que le problème, si j'ai un nombre indéfini d'individus au départ, de parents, tous les dupliqués c'est pas forcément génial si ? il faut que je fasse une fonction qui duplique tout ca ?

Oui mais comme jobherzt disait, avec le mot intervertir, ca fait bien penser qu'il y a deux enfants... donc je pense que je vais partir la dessus...

Je vais essayer, je vous tiens au courant si j'ai un problème

Merci a vous

[jobherzt]

Sauf que le problème, si j'ai un nombre indéfini d'individus au départ, de parents, tous les dupliqués c'est pas forcément génial si ? il faut que je fasse une fonction qui duplique tout ca ?

ben non, tu duliques juste avant d'appeler la fonction croisement.. ou alors je n'ai pas compris la question. et normalement le nombre d'individu est quand meme plus ou moins defini !