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

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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
Auteur du sujet

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.

Édité par jipete

+0 -0

Cette réponse a aidé l'auteur du sujet

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
Auteur du sujet

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
Auteur du sujet

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 ?

Édité par jipete

+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
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

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