Discussion :

[zeinab ali]

Bonjour
s'il vous plait ,j'ai développé une fonction de croisement de deux individus et maintenant je veux entrer dans mon code une probabilité de croisement Pc=0.7
mais je sais pas comment je vais modifier mon code pour prendre en considération la probabilité de croisement.
Merci d'avance.
voici le code de fonction de croisement:

Code :

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

1
2
3
4
5
6
7
8
9
10
def croisement_deux (self , i1 , i2):
            child=individu(self.nombre_genes)
            l = len(i1.genes)
            a = l / 2
            for i in range(0, int(a)):
                child.genes[i]=i1.genes[i]
            for i in range( int(a), l):
                child.genes[i]=i2.genes[i]
 
            return child

[Julien N]

Salut,

A quoi fait référence cette probabilité de croisement? A la probabilité que deux individus "se croisent", ou a la probabilité qu'un gène provienne de l'un ou de l'autre? Ou bien tout autre chose... C'est pas super clair.

[zeinab ali]

Salut,

A quoi fait référence cette probabilité de croisement? A la probabilité que deux individus "se croisent", ou a la probabilité qu'un gène provienne de l'un ou de l'autre? Ou bien tout autre chose... C'est pas super clair.

Merci pour la réponse.
En fait ,la probabilité de croisement correspond à la probabilité que deux individus "se croisent".

[Julien N]

Et bien dans ce cas deux possibilités:

1. On choisit s'il y a croisement avant l'appel de la méthode croisement_deux
2. Ou on choisit s'il y a croisement après l'appel à la méthode

Au choix en fonction de comment vous voulez architecturer votre programme.

Pour faire un choix le plus simple est de faire appel au module random. On tire aléatoirement un nombre en 0 et 1 (tirage équiprobable). On fixe une limite, par exemple 0.7. Si le nombre généré est en dessous, alors croisement, sinon rien (d'ailleurs il faut définir ce rien).

Code :

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

1
2
3
4
5
6
7
from random import random
 
probabilite_croisement = 0.7
if random() < 0.7:
    print('Croisement')
else:
    print('Rien')

Si vous souhaitez faire ce test à l'intérieur de la méthode croisement_deux il va vous falloir définir ce qui se passe s'il n'y a pas de croisement. Qu'est-ce que cette méthode devrait renvoyer?

J

[zeinab ali]

Et bien dans ce cas deux possibilités:

1. On choisit s'il y a croisement avant l'appel de la méthode croisement_deux
2. Ou on choisit s'il y a croisement après l'appel à la méthode

Au choix en fonction de comment vous voulez architecturer votre programme.

Pour faire un choix le plus simple est de faire appel au module random. On tire aléatoirement un nombre en 0 et 1 (tirage équiprobable). On fixe une limite, par exemple 0.7. Si le nombre généré est en dessous, alors croisement, sinon rien (d'ailleurs il faut définir ce rien).

Code :

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

1
2
3
4
5
6
7
from random import random
 
probabilite_croisement = 0.7
if random() < 0.7:
    print('Croisement')
else:
    print('Rien')

Si vous souhaitez faire ce test à l'intérieur de la méthode croisement_deux il va vous falloir définir ce qui se passe s'il n'y a pas de croisement. Qu'est-ce que cette méthode devrait renvoyer?

J

Merci bien pour votre explication
en fait ,j'ai modifié le code de la fonction croisement comme ça:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
def croisement_deux (self , i1 , i2):
            child=individu(self.nombre_genes)
            l = len(i1.genes)
            Pc=0.7
            a = l / 2
            if random.random()<Pc:
                for i in range(0, int(a)):
                    child.genes[i]=i1.genes[i]
                for i in range( int(a), l):
                    child.genes[i]=i2.genes[i]
 
            return child

Et j'ai fait appel à cette méthode dans la fonction ci-dessous:

Code :

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

1
2
3
4
5
6
7
8
9
10
def croisement_nombre (self ):
                for v in self.individus:
			print v.genes
                new = []
		for r in range(len(self.individus)):
			v1 = random.randint (0 , len(self.individus)-1)
			v2 = random.randint (0 , len(self.individus)-1)
			new.append (self.croisement_deux (self.individus[v1] , self.individus[v2]) )
 
		self.individus  = new

est ce que c'est juste comme ca
et en cas de non croisement(random.random()>Pc)est ce que je peux développer que la nouvelle population contient seulement les parents .
Merci d'avance

[Julien N]

est ce que c'est juste comme ca

Presque. La méthode croisement_deux est sensée renvoyer quelque chose. Si un croisement à effectivement lieu elle renvoi un individu, sinon quoi? Telle qu'écrite en ce moment, la méthode ne renvoi rien. Ce n'est pas correct.

et en cas de non croisement(random.random()>Pc)est ce que je peux développer que la nouvelle population contient seulement les parents .

La condition de croisement est vérifiée à chaque croisement. Si la population totale fait 1000 individus, grosso modo 70 croisements auront lieux (en fait il faudrait plutôt dire, 70 enfants verront le jour). La "nouvelle population" ne pourra pas (et ne devrait pas) contenir seulement les parents. Je pense que vous voulez que la taille de la nouvelle population reste inchangée, et donc compléter avec des parents. Correct?

Dans ce cas, on peut envisager de demander à la méthode croisement_deux de fournir aléatoirement un des deux parents s'il n'y a pas de croisement. Mais je ne trouve pas ça terrible. Dans un algo génétique, il doit y avoir les phases suivantes:

1. Evaluation de la population (on attribut une note à chaque individu en fonction de sa performance)
2. Sélection d'une fraction des meilleurs individus. On les place d'office dans la prochaine population.
3. Croisement aléatoire des individus avec ou sans mutations.
4. Génération éventuel de nouveaux individus aléatoires, histoire de donner du sang neuf à la population (et éviter de rester bloquer dans la convergence vers le "meilleur" individu)

On s'assure que la taille de la population ne varie pas, sinon on risque quelques problèmes.

Moi, je ferais une boucle while comme ceci (pseudo-code) à modifier et à placer dans la méthode appropriée:

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
# Liste des individus de la nouvelle population/génération
# Initialement vide, elle contient désormais les individus issus de la sélection
new_population = ...
# La population précédente
old_population = ...
 
# On va générer autant d'enfants que nécessaire pour compléter la population
while len(new_population) != len(old_population):
    # Tirage aléatoire des individus à croiser parmi la population précédente
    parent_1 = old_population[random.randint(0, len(old_population))]
    parent_2 = old_population[random.randint(0, len(old_population))]
    # Croisement
    child = self.croisement_deux(parent_1 , parent_2)
    # On gère le cas où rien ne se passe
    if child:
        new_population.append(child)

La modification a apporter à croisement_deux serait minime (attention à utiliser des variables comme a, l, i1, i2... ici le code est court mais sinon un lecteur, vous éventuellement plus tard, sera bien en mal de comprendre ce veulent dire ces variables. Préférez des noms explicites comme child, parent, gene, etc...) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def croisement_deux (self , i1 , i2, Pc=0.7):
    if random.random() < Pc:
        child = individu(self.nombre_genes)
        l = len(i1.genes)
        a = l / 2
        for i in range(0, int(a)):
            child.genes[i]=i1.genes[i]
        for i in range( int(a), l):
            child.genes[i]=i2.genes[i]
 
        return child
 
    return None

J'ai pris la liberté de placer la variable Pc en argument. Cela pourrait aussi être un attribut de la classe. Il est préférable de définir les constantes ailleurs que dans la fonction/méthode elle-même. J'ai choisi de renvoyer None si aucun croisement n'a lieu. Dans votre code vous renvoyiez un nouvel individu généré aléatoirement... rien a voir avec un "croisement" .

J

[zeinab ali]

Presque. La méthode croisement_deux est sensée renvoyer quelque chose. Si un croisement à effectivement lieu elle renvoi un individu, sinon quoi? Telle qu'écrite en ce moment, la méthode ne renvoi rien. Ce n'est pas correct.



La condition de croisement est vérifiée à chaque croisement. Si la population totale fait 1000 individus, grosso modo 70 croisements auront lieux (en fait il faudrait plutôt dire, 70 enfants verront le jour). La "nouvelle population" ne pourra pas (et ne devrait pas) contenir seulement les parents. Je pense que vous voulez que la taille de la nouvelle population reste inchangée, et donc compléter avec des parents. Correct?

Dans ce cas, on peut envisager de demander à la méthode croisement_deux de fournir aléatoirement un des deux parents s'il n'y a pas de croisement. Mais je ne trouve pas ça terrible. Dans un algo génétique, il doit y avoir les phases suivantes:

1. Evaluation de la population (on attribut une note à chaque individu en fonction de sa performance)
2. Sélection d'une fraction des meilleurs individus. On les place d'office dans la prochaine population.
3. Croisement aléatoire des individus avec ou sans mutations.
4. Génération éventuel de nouveaux individus aléatoires, histoire de donner du sang neuf à la population (et éviter de rester bloquer dans la convergence vers le "meilleur" individu)

On s'assure que la taille de la population ne varie pas, sinon on risque quelques problèmes.

Moi, je ferais une boucle while comme ceci (pseudo-code) à modifier et à placer dans la méthode appropriée:

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
# Liste des individus de la nouvelle population/génération
# Initialement vide, elle contient désormais les individus issus de la sélection
new_population = ...
# La population précédente
old_population = ...
 
# On va générer autant d'enfants que nécessaire pour compléter la population
while len(new_population) != len(old_population):
    # Tirage aléatoire des individus à croiser parmi la population précédente
    parent_1 = old_population[random.randint(0, len(old_population))]
    parent_2 = old_population[random.randint(0, len(old_population))]
    # Croisement
    child = self.croisement_deux(parent_1 , parent_2)
    # On gère le cas où rien ne se passe
    if child:
        new_population.append(child)

La modification a apporter à croisement_deux serait minime (attention à utiliser des variables comme a, l, i1, i2... ici le code est court mais sinon un lecteur, vous éventuellement plus tard, sera bien en mal de comprendre ce veulent dire ces variables. Préférez des noms explicites comme child, parent, gene, etc...) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def croisement_deux (self , i1 , i2, Pc=0.7):
    if random.random() < Pc:
        child = individu(self.nombre_genes)
        l = len(i1.genes)
        a = l / 2
        for i in range(0, int(a)):
            child.genes[i]=i1.genes[i]
        for i in range( int(a), l):
            child.genes[i]=i2.genes[i]
 
        return child
 
    return None

J'ai pris la liberté de placer la variable Pc en argument. Cela pourrait aussi être un attribut de la classe. Il est préférable de définir les constantes ailleurs que dans la fonction/méthode elle-même. J'ai choisi de renvoyer None si aucun croisement n'a lieu. Dans votre code vous renvoyiez un nouvel individu généré aléatoirement... rien a voir avec un "croisement" .

J

je vous remercie infiniment pour cette réponse détaillée
Z

[zeinab ali]

Presque. La méthode croisement_deux est sensée renvoyer quelque chose. Si un croisement à effectivement lieu elle renvoi un individu, sinon quoi? Telle qu'écrite en ce moment, la méthode ne renvoi rien. Ce n'est pas correct.



La condition de croisement est vérifiée à chaque croisement. Si la population totale fait 1000 individus, grosso modo 70 croisements auront lieux (en fait il faudrait plutôt dire, 70 enfants verront le jour). La "nouvelle population" ne pourra pas (et ne devrait pas) contenir seulement les parents. Je pense que vous voulez que la taille de la nouvelle population reste inchangée, et donc compléter avec des parents. Correct?

Dans ce cas, on peut envisager de demander à la méthode croisement_deux de fournir aléatoirement un des deux parents s'il n'y a pas de croisement. Mais je ne trouve pas ça terrible. Dans un algo génétique, il doit y avoir les phases suivantes:

1. Evaluation de la population (on attribut une note à chaque individu en fonction de sa performance)
2. Sélection d'une fraction des meilleurs individus. On les place d'office dans la prochaine population.
3. Croisement aléatoire des individus avec ou sans mutations.
4. Génération éventuel de nouveaux individus aléatoires, histoire de donner du sang neuf à la population (et éviter de rester bloquer dans la convergence vers le "meilleur" individu)

On s'assure que la taille de la population ne varie pas, sinon on risque quelques problèmes.

Moi, je ferais une boucle while comme ceci (pseudo-code) à modifier et à placer dans la méthode appropriée:

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
# Liste des individus de la nouvelle population/génération
# Initialement vide, elle contient désormais les individus issus de la sélection
new_population = ...
# La population précédente
old_population = ...
 
# On va générer autant d'enfants que nécessaire pour compléter la population
while len(new_population) != len(old_population):
    # Tirage aléatoire des individus à croiser parmi la population précédente
    parent_1 = old_population[random.randint(0, len(old_population))]
    parent_2 = old_population[random.randint(0, len(old_population))]
    # Croisement
    child = self.croisement_deux(parent_1 , parent_2)
    # On gère le cas où rien ne se passe
    if child:
        new_population.append(child)

La modification a apporter à croisement_deux serait minime (attention à utiliser des variables comme a, l, i1, i2... ici le code est court mais sinon un lecteur, vous éventuellement plus tard, sera bien en mal de comprendre ce veulent dire ces variables. Préférez des noms explicites comme child, parent, gene, etc...) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def croisement_deux (self , i1 , i2, Pc=0.7):
    if random.random() < Pc:
        child = individu(self.nombre_genes)
        l = len(i1.genes)
        a = l / 2
        for i in range(0, int(a)):
            child.genes[i]=i1.genes[i]
        for i in range( int(a), l):
            child.genes[i]=i2.genes[i]
 
        return child
 
    return None

J'ai pris la liberté de placer la variable Pc en argument. Cela pourrait aussi être un attribut de la classe. Il est préférable de définir les constantes ailleurs que dans la fonction/méthode elle-même. J'ai choisi de renvoyer None si aucun croisement n'a lieu. Dans votre code vous renvoyiez un nouvel individu généré aléatoirement... rien a voir avec un "croisement" .

J

Merci beaucoup pour cette réponse.
Je suis reconnaissante
si j'ai bien compris votre explication ,j'ai modifié mon code comme ci-dessous et il marche bien.

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
19
20
21
22
23
24
25
26
27
28
def croisement_deux (self , father , mother,Pc=0.7):
            child=individu(self.nombre_genes)
            long = len(father.genes)
            a = long / 2
            if random.random()<Pc:
                for i in range(0, int(a)):
                    child.genes[i]=father.genes[i]
                for i in range( int(a), long):
                    child.genes[i]=mother.genes[i]
 
            return child
 
	def croisement_nombre (self ):
 
            old_population = self.individus
            new_population = []
            while (len(new_population) != len(old_population)):
            # Tirage aléatoire des individus à croiser parmi la population précédente
                parent_1 = old_population[random.randint(0, len(old_population))]
                print parent_1
                parent_2 = old_population[random.randint(0, len(old_population))]
                print parent_2
                child = self.croisement_deux(parent_1, parent_2)
                print child
            # On gère le cas où rien ne se passe
                if child:
                    new_population.append(child)
            self.individus = new_population

Et en vous répondant pour cette phrase "Dans votre code vous renvoyiez un nouvel individu généré aléatoirement... rien a voir avec un "croisement" ."
je pense qu'il n'y a pas de problème en cas de non croisement car moi,avant le code de croisement j'écris cette ligne

Code :

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

child=individu(self.nombre_genes)

donc si le croisement ne se fait pas ,dans tous les cas la fonction croisement_deux va retourner un child ,la ligne de code précedente permet de génerer un individu aléatoirement.
voici le code de classe individu:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class individu:
	def __init__ (self,nombre_genes,random=-1,genes=[]):
		self.genes = []
		self.nombre_genes = nombre_genes
                if random == -1 : self.get_random (genes)
	"""
        random : initialise aleatoirement les genes
        """def get_random (self,s):
            self.genes=s
            self.genes=np.zeros(self.nombre_genes)
 
            for i in range(self.nombre_genes):
                self.genes[i]=random.randint(0,1)
            return self.genes

Je vois comme ça et vous Qu'est ce vous voyez s'il vous plait.
Merci encore fois pour votre temps

[Julien N]

Salut,

Si ça fonctionne comme vous le voulez alors c'est tout bon. Mais je dois quand avouer que cette ligne me perturbe:

Code :

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

child=individu(self.nombre_genes)

Cela revient à dire que deux parents essayent d'avoir un enfant, qu'ils ont une probabilité Pc d'y parvenir, mais que si ça ne marche pas ils adoptent. Pourquoi pas, ça donne du sang neuf à la population, mais alors il faut l'expliquer par un commentaire dans le code je pense.

J

[zeinab ali]

Salut,

Si ça fonctionne comme vous le voulez alors c'est tout bon. Mais je dois quand avouer que cette ligne me perturbe:

Code :

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

child=individu(self.nombre_genes)

Cela revient à dire que deux parents essayent d'avoir un enfant, qu'ils ont une probabilité Pc d'y parvenir, mais que si ça ne marche pas ils adoptent. Pourquoi pas, ça donne du sang neuf à la population, mais alors il faut l'expliquer par un commentaire dans le code je pense.

J

Merci pour vos réponses.
s'il vous plait,je veux demander votre conseil.
Après la terminaison de mon algorithme génétique ,je veux obtenir quelques résultats concernant cet algorithme (sous forme des graphiques),mais je sais pas quels sont les résultats que je dois les afficher .
En fait ,j'ai suivi un article qui traite une problème proche de ma problème (optimisation de placement des passerelles dans un réseau maillé en utilisant une approche génétique)
Dans l'un des courbes affichées, les chercheurs présentent l'évolution de taux de convergence en fonction de taille de population.
Comment je peux calculer le taux convergence dans mon algorithme ???
Cordialement
Z

[Julien N]

Comment je peux calculer le taux convergence dans mon algorithme ???

Cela mérite peut-être un autre sujet, celui-ci étant intitulé "probabilité de croisement dans un algorithme génétique".

[zeinab ali]

Cela mérite peut-être un autre sujet, celui-ci étant intitulé "probabilité de croisement dans un algorithme génétique".

salut
merci ,mais je reste quand même dans le thème des algorithmes génetiques
vous ne pouvez pas me répondre ici.
Cordialement

[Julien N]

merci ,mais je reste quand même dans le thème des algorithmes génetiques
vous ne pouvez pas me répondre ici.

Si bien sûr, mais si plus tard quelqu'un à un problème lié à "croisement & algorithme génétique", il fera une recherche par mots clés sur ce forum pour voir si le sujet n'a pas déjà été abordé et résolu (bon la plupart du temps les gens ne cherchent pas et ouvrent un nouveau sujet). C'est pour cette raison qu'il faut éviter le hors sujet.

Si le problème "probabilité de croisement dans un algorithme genetique" est résolu alors il faut l'indiqué "bouton résolu". Toute autre question méritant un nouveau sujet doit donner lieu à un nouveau sujet.

Comment je peux calculer le taux convergence dans mon algorithme ???

Ici la question n'est pas directement liée à python. C'est une question sur un algorithme, il y a une section sur développez dédiée aux algorithmes. Vous devriez aller y jeter un oeil. Peut-être même qu'elle a déjà été résolue par quelqu'un d'autre.

J

[zeinab ali]

Si bien sûr, mais si plus tard quelqu'un à un problème lié à "croisement & algorithme génétique", il fera une recherche par mots clés sur ce forum pour voir si le sujet n'a pas déjà été abordé et résolu (bon la plupart du temps les gens ne cherchent pas et ouvrent un nouveau sujet). C'est pour cette raison qu'il faut éviter le hors sujet.

Si le problème "probabilité de croisement dans un algorithme genetique" est résolu alors il faut l'indiqué "bouton résolu". Toute autre question méritant un nouveau sujet doit donner lieu à un nouveau sujet.


Ici la question n'est pas directement liée à python. C'est une question sur un algorithme, il y a une section sur développez dédiée aux algorithmes. Vous devriez aller y jeter un oeil. Peut-être même qu'elle a déjà été résolue par quelqu'un d'autre.

J

OK c'est clair ,je suis convaincue.
http://www.developpez.net/forums/d16...e/#post8749366