python algo génétique faire la plus petite phrase

a marqué ce sujet comme résolu.

Bonjour, j’ai un cours en ia et j’ai comme exercice de faire un programme faisant la plus courte phrase possible (en terme de nb de caractere)

Je dispose d’une liste2D de départ

1
data=[["Un","Des","Une","On","Elle"],["a","eu","avait","est","était","fut"],["soif","rouge"]]

je dois faire une phrase de 3 mots la plus petite possible (en nb de caractère), la solution serait ici "Un a soif"

voila ce que j’ai fais en algorithme génétique, je cherche la valeur la plus patite en modifiant a chaque gen 0.05% de la pop.

Un individu est une phrase une population est un ensemble de phrase je cherche à générer la plus petite phrase possible.

  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
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
from random import randint, random
from operator import add
from functools import reduce

data=[["Un","Des","Une","On","Elle"],["a","eu","avait","est","était","fut"],["soif","rouge"]]

def phrases():
    myphrase=[]
    for element in data:
        mystring=element[randint(0, len(element)-1)]
        myphrase.append(mystring)
        myphrase.append(len(mystring))
    return myphrase

def individual():
    'Create a member of the population.'
    matrice=[]
    strings_length=[]
    strings_name=[]

    myphrase=phrases()
    strings_name.append(myphrase)
    strings_length.append(len(myphrase))

    matrice.append(strings_length)
    matrice.append(strings_name)
    return matrice

def population(count):
    population=[ individual() for x in range(count) ]
    return population

def fitness(individual, target):
    sum = reduce(add, individual, 0)
    return abs(target-sum)

def grade(pop, target):
    'Find average fitness for a population.'
    pop_number=[]
    pop_string=[]
    for element in pop:
        pop_number.append(element[0])
        pop_string.append(element[1])   

    summed = reduce(add, (fitness(x, target) for x in pop_number))
    data=[[summed / (len(pop_number) * 1.0)], [pop_string[-1]]]
    return data

def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.01):
    pop_number=[]
    pop_string=[]

    for element in pop:
        pop_number.append(element[0])
        pop_string.append(element[1])
    graded = [ (fitness(x, target), x) for x in pop_number]
    graded = [ x[1] for x in sorted(graded)]

    pop_new_string=[]

    retain_length = int(len(graded)*retain)
    parents = graded[:retain_length]
    for individual in graded[retain_length:]:
        parents.append(individual)
        myphrase=phrases()
        if random_select > random():
            pop_new_string.append(myphrase)
    for individual in parents:
        myphrase=phrases()
        pop_new_string.append(myphrase)
        if mutate > random():
            pos_to_mutate = randint(0, len(individual)-1)
            individual[pos_to_mutate] = randint(
                min(individual), max(individual))
    parents_length = len(parents)
    desired_length = len(pop_number) - parents_length
    children = []
    while len(children) < desired_length:
        male = randint(0, parents_length-1)
        female = randint(0, parents_length-1)
        if male != female:
            male = parents[male]
            female = parents[female]
            half = int(len(male) / 2)
            child = male[:half] + female[half:]
            children.append(child)        
    parents.extend(children)

    i=0
    pop=[]
    print(len(parents))
    print(len(pop_new_string))
    for element in parents:
        data=[]
        data.append(element)
        data.append(pop_new_string[i])
        i=i+1
        pop.append(data)

    return pop

target = 0
p_count = 100
p = population(p_count)
fitness_history = [grade(p, target),]

for i in range(100):
    p = evolve(p, target)
    fitness_history.append(grade(p, target))

for datum in fitness_history:
   print(datum)

le probleme c’est que ma valeur n’évolue pas. Par avance merci pour votre aide

+0 -0

Salut,

La phrase la plus courte doit-elle aussi être correcte? Au vu de la solution que tu donnes en exemple il semble que non. Du coup, qu’est-ce qui t’empêches de faire ceci:

1
2
data=[["Un","Des","Une","On","Elle"],["a","eu","avait","est","était","fut"],["soif","rouge"]]
' '.join(map(lambda x: min(x, key=len), data))
+0 -0

J’imagine que le but de l’exercice est de travailler les algorithmes génétiques, pas de trouver des phrases courtes. Cela dit, je suis aussi un peu dubitatif de l’intérêt de faire pratiquer ce genre de méthode sur un problème dont il est trivial d’obtenir une solution exacte.

+0 -0

oui je dois utiliser un algorithme génétique (c’est l’objectif de l’exercice) Et non les phrases n’ont pas à être correcte.

Sinon oui vous avez raison il des solutions plus simple. et se serais même débile dans la vrai vie d’utiliser un algo génétique juste pour sa.

+0 -0

Est ce vraiment nécessaire de faire la distinction mâle/femelle dans la fonction evolve ?

Je trouve ton implémentation compliquée, il y a notamment des variables dont l’intérêt m’échappe. Je te propose ma solution, où le jeu de données contient la taille des mots et les (3) gènes d’un individu correspondent à un indice de mon jeu de données. Du coup, l’individu (0, 3, 1) correspond à la phrase "Un est rouge".

Le code que je te propose est juste en dessous, il contient cependant une "erreur" à la ligne 30, la fonction round n’est probablement pas la plus adaptée, puisqu’elle retourne toujours l’entier supérieur quand le nombre est x.5, ce qui n’est pas toujours le résultat voulu dans notre cas.

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import random
import statistics


def individual(data):
    return tuple(random.choice(range(len(feature))) for feature in data)


def population(data, initial=100):
    return [individual(data) for i in range(initial)]


def fitness(individual, data):
    return sum(data[i][individual[i]] for i in range(len(individual)))


def grade(population, data):
    fit = [fitness(ind, data) for ind in population]
    return statistics.mean(fit)


def mutate(ind, data):
    gene = random.randrange(0, len(ind))
    clone = list(ind)
    clone[gene] = random.randrange(0, len(data[gene]))
    return tuple(clone)


def cross(mother, father):
    return tuple(round(statistics.mean(genes)) for genes in zip(mother, father))


def evolve(population, data, retain=0.2, random_select=0.05, mutation_rate=0.01):
    def cmp_ind(ind):
        return fitness(ind, data)
    sorted_population = sorted(population, key=cmp_ind)

    len_retained = round(len(population) * retain)
    retained = sorted_population[:len_retained]

    random_selected = [
        ind
        for ind in sorted_population[len_retained:]
        if random.random() <= random_select
    ]

    mutated = [
        mutate(ind, data)
        for ind in sorted_population[len_retained:]
        if random.random() <= mutation_rate
    ]

    children = [
        cross(random.choice(sorted_population),
              random.choice(sorted_population))
        for i in range(len(population) - len(random_selected) - len(mutated))
    ]

    return random_selected + mutated + children


if __name__ == '__main__':
    words = [
        ["Un", "Des", "Une", "On", "Elle"],
        ["a", "eu", "avait", "est", "était", "fut"],
        ["soif", "rouge"]
    ]

    data = [[len(w) for w in ws] for ws in words]

    initial_population = population(data, 100)
    next_population = initial_population
    max_iter = 20

    for i in range(max_iter):
        next_population = evolve(next_population, data)

    sorted_population = sorted(next_population, key=lambda x: fitness(x, data))
    best_individual = sorted_population[0]
    sentence = [
        words[i][best_individual[i]]
        for i in range(len(best_individual))
    ]
    print(' '.join(sentence))
+2 -0

merci GaaH pour ton aide.

J’étudie actuellement ta solution, si j’ai bien compris c’est bien dans la fonction evolve que tu teste (tu regarde la longueur de la chaine) et sélectionne les combinaisons pertinente

Je n’arrive pas a comprendre comment tu arrive à retrouver les mots. dans la ligne return random_selected + mutated + children random select c’est une matrice par exemple [(2, 2, 0), (2, 2, 0), (2, 2, 0), (2, 2, 0)] je vois pas à quoi cela correspond dans la liste de mots (en faite je cherche à faire un print des solutions que le proigramme test avant d’arriver à la solution final)

+0 -0

Un individu est un tuple de taille 3. La i-ème composante de ce tuple correspond a un indice de la i-ème ligne du jeu de données.

Si j’ai l’individu (0, 1, 2), pour récupérer le premier mot, je récupère la valeur à l’indice i=0 de mon individu : c’est 0. Le mot correspondant sera alors words[i, individu[i]] soit words[0, 0]. Idem pour les gènes 1 et 2.

Dans l’algorithme génétique, je me fiche pas mal de la phrase en elle même, par contre la taille de celle ce m’intéresse. Du coup je construit mon jeu de données data en fonction de la taille des mots présents dans words.

Tu peux surement afficher la phrase correspondant a un individu avec 

1
2
def sentence(individual, words):
    return ' '.join([words[i][individual[i]] for i in range(len(words))])
+1 -0

merci. Je pense avoir compris le truc. J’ai repris ton code mais cette fois ci je cherche à avoir la somme des caractères ascii de ma phrase le plus petite possible. Si j’ai bien tous compris, je n’ai juste à modifier la fonction fitness.

  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
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
import random
import statistics

words = [
    ["aaa", "bbb", "ccc", "yyy", "zzz"],
    ["000", "111", "222", "555", "888", "999"],
    ["~~~", "!!!"]
]

def individual(data):
    #return tuple(random.choice(range(len(feature))) for feature in data)
    return tuple(random.choice(range(len(feature))) for feature in data)


def population(data, initial=100):
    return [individual(data) for i in range(initial)]


def fitness(individual, data):
    chaine=sentence(individual,words)
    somme = 0
    for caractere in chaine:
        somme = somme + ord(caractere)

    print(chaine)
    print(somme)
    return somme
    #return sum(data[i][individual[i]] for i in range(len(individual)))


def grade(population, data):
    fit = [fitness(ind, data) for ind in population]
    return statistics.mean(fit)


def mutate(ind, data):
    gene = random.randrange(0, len(ind))
    clone = list(ind)
    clone[gene] = random.randrange(0, len(data[gene]))
    #print(sentence(tuple(clone),words))
    return tuple(clone)


def cross(mother, father):
    return tuple(round(statistics.mean(genes)) for genes in zip(mother, father))

def sentence(individual, words):
    return ' '.join([words[i][individual[i]] for i in range(len(words))])

def evolve(population, data, retain=0.2, random_select=0.05, mutation_rate=0.01):
    def cmp_ind(ind):
        return fitness(ind, data)
    sorted_population = sorted(population, key=cmp_ind)

    len_retained = round(len(population) * retain)
    retained = sorted_population[:len_retained]

    random_selected = [
        ind
        for ind in sorted_population[len_retained:]
        if random.random() <= random_select
    ]

    mutated = [
        mutate(ind, data)
        for ind in sorted_population[len_retained:]
        if random.random() <= mutation_rate
    ]

    children = [
        cross(random.choice(sorted_population),
              random.choice(sorted_population))
        for i in range(len(population) - len(random_selected) - len(mutated))
    ]

    return random_selected + mutated + children




if __name__ == '__main__':

    data = [[len(w) for w in ws] for ws in words]



    initial_population = population(data, 100)
    next_population = initial_population
    max_iter = 5

    for i in range(max_iter):
        next_population = evolve(next_population, data)

    sorted_population = sorted(next_population, key=lambda x: fitness(x, data))
    best_individual = sorted_population[0]

    print("best solution :")

    chaine=sentence(best_individual,words)
    somme = 0
    for caractere in chaine:
        somme = somme + ord(caractere)
    print(chaine)
    print(somme)

j’ai testé plusieurs fois cela semble fonctionner. Je veut juste ton avis (pour voir si j’ai bien compris ou si j’ai zappé un truc) On remarque par contre que la meilleur solution qu’il arrive à trouver change à chaque lancement du programme (c’est comme je l’ai compris l’intérêt de l’algo génétique, qui ne trouve pas la meilleur solution mais l’une des plus optimal et évite de tous tester) J’imagine après qu’il faut jouer avec les 3 variables retain=0.2, random_select=0.5, mutation_rate=0.1 pour essayer de l’optimiser

et autre question, pourquoi n’utilise tu pas la fonction grade ?

+0 -0

L’intérêt de ma façon de procéder, c’est justement que tu n’est pas censé modifier les fonctions. Le résultat est censé s’adapter en fonction des données en entré. ma variable data contient une liste de valeur représentant des tailles, l’algorithme va alors essayer de trouver un individu dont la somme des taille sera minimal. Maintenant tu veux trouver l’individu dont la somme des valeur ascii est minimal, il suffit de remplacer les valeurs de data par celles-ci :

1
2
3
4
data = [
    [sum(ord(c) for c in w) for w in ws] 
    for ws in words
]

A savoir que si tu veux récupérer l’individu avec la plus grosse valeur, il faudra multiplier les valeurs de data par -1. Pour des cas simples comme ça ou une simple somme suffit à attribuer un score a un individu, ma fonction fitness devrait être suffisante. Si tu t’attaques a des problèmes plus complexes, une bonne solution serait de passer une fonction de fitness a la fonction evolve

Oui, c’est normal que tu obtienne des résultats différents, plus la population initiale est grande, moins le résultat sera aléatoire. Ce comportement est aussi modulé par les paramètre de croisement/mutation mais dans une moindre mesure (enfin, il me semble).

J’ai recodé la fonction grade "bêtement" pour rester cohérent avec ton code, je ne m’en suis pas servi car je ne comprends pas son utilité pour l’apprentissage. J’ai du, moi aussi, louper un truc ^^.

+0 -0

Bonjour, le sujet m’interesse et j’ai une question, je cherhce a faire l’inverse, trouver la valeur maximum au lieu de trouver la valeur minimal. Mais je comprend pas quoi modifier dans le code pour y parvenir.

J’avais penser aud épart faire un reverse de sorted_population mais cela est sans effet. et pour moi : random.random() <= random_select ou random.random() <= mutation_rate n’influence pas ce parametre si ?

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import random
import statistics

words = [
    ["aaa", "bbb", "ccc", "yyy", "zzz"],
    ["000", "111", "222", "555", "888", "999"],
    ["~~~", "!!!"]
]

def individual(data):
    return tuple(random.choice(range(len(feature))) for feature in data)


def population(data, initial=100):
    return [individual(data) for i in range(initial)]


def fitness(individual, data):
    chaine=sentence(individual,words)
    somme = 0
    for caractere in chaine:
        somme = somme + ord(caractere)

    print(chaine)
    print(somme)
    return somme


def mutate(ind, data):
    gene = random.randrange(0, len(ind))
    clone = list(ind)
    clone[gene] = random.randrange(0, len(data[gene]))
    return tuple(clone)


def cross(mother, father):
    return tuple(round(statistics.mean(genes)) for genes in zip(mother, father))

def sentence(individual, words):
    return ' '.join([words[i][individual[i]] for i in range(len(words))])

def evolve(population, data, retain=0.2, random_select=0.05, mutation_rate=0.01):
    def cmp_ind(ind):
        return fitness(ind, data)
    sorted_population = sorted(population, key=cmp_ind)


    len_retained = round(len(population) * retain)
    retained = sorted_population[:len_retained]

    random_selected = [
        ind
        for ind in sorted_population[len_retained:]
        if random.random() <= random_select
    ]

    mutated = [
        mutate(ind, data)
        for ind in sorted_population[len_retained:]
        if random.random() <= mutation_rate
    ]

    children = [
        cross(random.choice(sorted_population),
              random.choice(sorted_population))
        for i in range(len(population) - len(random_selected) - len(mutated))
    ]

    return random_selected + mutated + children




if __name__ == '__main__':

    data = [[len(w) for w in ws] for ws in words]



    initial_population = population(data, 100)
    next_population = initial_population
    max_iter = 5

    for i in range(max_iter):
        next_population = evolve(next_population, data)

    sorted_population = sorted(next_population, key=lambda x: fitness(x, data))
    best_individual = sorted_population[0]

    print("best solution :")

    chaine=sentence(best_individual,words)
    somme = 0
    for caractere in chaine:
        somme = somme + ord(caractere)
    print(chaine)
    print(somme)
+0 -0

ce code ne viens pas de moi mais du po jipete, moi je voudrais juste m’en inspirer pour faire l’inverse, cherche les valeurs les plus forte au lieu des plus faible.

je pense que la clé du probleme viens du crossover la fonction cross, mais elle ne fait que calculer la moyenne, pas de comparaison

+0 -0

Bonjour Uther, Non vous ne pourrez pas faire cela avec un algorithme génétique.

Un algo génétique cherche la solution la plus proche de 0, meme si vous inverser les résultats en multipliant par -1 vous aurez le mème résultat, il cherchera la valeur la plus proche de 0.

donc non c’est impossible.

+1 -0

en faite je me demande si l’algorithme marche bien, je reprend l’exemple avec word

  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
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import random
import statistics

EVOLUTION=[]

words = [
        ["Un", "Des", "Une", "On", "Elle"],
        ["a", "eu", "avait", "est", "était", "fut"],
        ["soif", "rouge"]
        ]

def individual(data):
    #return tuple(random.choice(range(len(feature))) for feature in data)
    return tuple(random.choice(range(len(feature))) for feature in data)


def population(data, initial=100):
    return [individual(data) for i in range(initial)]


def fitness(individual, data):
    chaine=sentence(individual,words)
    somme = 0
    for caractere in chaine:
        somme = somme + ord(caractere)

    print(chaine)
    print(somme)
    EVOLUTION.append(somme)
    return somme
    #return sum(data[i][individual[i]] for i in range(len(individual)))


def grade(population, data):
    fit = [fitness(ind, data) for ind in population]
    return statistics.mean(fit)


def mutate(ind, data):
    gene = random.randrange(0, len(ind))
    clone = list(ind)
    clone[gene] = random.randrange(0, len(data[gene]))
    #print(sentence(tuple(clone),words))
    return tuple(clone)


def cross(mother, father):
    return tuple(round(statistics.mean(genes)) for genes in zip(mother, father))

def sentence(individual, words):
    return ' '.join([words[i][individual[i]] for i in range(len(words))])

def evolve(population, data, retain=0.2, random_select=0.05, mutation_rate=0.01):
    def cmp_ind(ind):
        return fitness(ind, data)
    sorted_population = sorted(population, key=cmp_ind, reverse=True)

    len_retained = round(len(population) * retain)
    retained = sorted_population[:len_retained]

    random_selected = [
        ind
        for ind in sorted_population[len_retained:]
        if random.random() <= random_select
    ]

    mutated = [
        mutate(ind, data)
        for ind in sorted_population[len_retained:]
        if random.random() <= mutation_rate
    ]

    children = [
        cross(random.choice(sorted_population),
              random.choice(sorted_population))
        for i in range(len(population) - len(random_selected) - len(mutated))
    ]

    return random_selected + mutated + children




if __name__ == '__main__':

    data = [[len(w) for w in ws] for ws in words]



    initial_population = population(data, 30)
    next_population = initial_population
    max_iter = 3

    for i in range(max_iter):
        next_population = evolve(next_population, data)

    sorted_population = sorted(next_population, key=lambda x: fitness(x, data))
    best_individual = sorted_population[0]

    print("best solution :")

    chaine=sentence(best_individual,words)
    somme = 0
    for caractere in chaine:
        somme = somme + ord(caractere)
    print(chaine)
    print(somme)

    import matplotlib
    matplotlib.use('Agg')
    import matplotlib.pyplot as plt
    plt.plot(EVOLUTION)
    plt.savefig('myfig')

`

et voila ce que m’affiche myfig.png :Image utilisateur

https://pasteboard.co/Hf40F3a.png

j’essaye juste de comprendre, pourquoi j’ai ce "yoyo" ? pourquoi es ce que je ne converge pas vers un minium ou un maximum ?

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte