Discussion :

[datalandia]

Bonjour, j'ai une liste 2D contenant des mots, je souhaite trouver la combinaison de ces mots qui me donnera la somme ascii la plus grosse

Code :

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

1
2
3
4
5
6
 
words = [
        ["Un", "Des", "Une", "On", "Elle"],
        ["a", "eu", "avait", "est", "était", "fut"],
        ["soif", "rouge"]
        ]

comme phrase je peut avoir par exemple :
Un eu rouge
Elle a soif
Une avait rouge
On avait soit
....etc.
les phrases n'ont pas de sens mais ce n'est pas important

bref j'ai regardé pas mal de tuto et voila ce que j'ai développé pour résoudre mon probleme avec un algorithme génétique, car je veut résoudre mn probleme avec cette méthode.

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
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
 
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')

je pense que globalement mon code, ou plutot ma méthode est bonne, mais il y'a un petit détail quand je ragrde le résultat obtenue, au lieu d'obtenir une courbe qui montrais vers le haut, car je rapelle le but c'est de trouver la somme ascii la plus élevée j'ai un effet yoyo comme sur cette image :



moi je pensait plus obtenir un truc dans ce style :



mais mon plus gros probleme c'est que j'ai l'impression que mon programme tends vers la somme la plus petite pas la plus grande, quelqu'un peut t'il m'aider ?

[tyrtamos]

Bonjour,

Je ne comprends pas bien l'algorithme de recherche. Si on cherche la combinaison des 3 mots donnant la somme ASCII la plus grande, il suffit de calculer les valeurs ASCII dans les 3 séries, de les trier et de prendre les 3 mots ayant la valeur ASCII la plus forte. Comme ça par exemple:

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
# -*- coding: utf-8 -*-
words = [
        ["Un", "Des", "Une", "On", "Elle"],
        ["a", "eu", "avait", "est", "était", "fut"],
        ["soif", "rouge"]
        ]
L = []
for i in range(0, len(words)):
    L.append([])
    for w in words[i]:
        sw = sum(ord(c) for c in w)
        L[-1].append((w, sw))
    L[-1].sort(key=lambda v: v[1], reverse=True)
    print(L[-1])     
print("maxi:", L[0][0], L[1][0], L[2][0])

Ce qui donne:

Code :

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

1
2
3
4
[('Elle', 386), ('Une', 296), ('Des', 284), ('Un', 195), ('On', 189)]
[('était', 667), ('avait', 533), ('fut', 335), ('est', 332), ('eu', 218), ('a', 97)]
[('rouge', 546), ('soif', 433)]
maxi: ('Elle', 386) ('était', 667) ('rouge', 546)

S'il y a un algorithme de recherche, donnes-en le principe, car il n'est pas facile de le deviner en lisant le code.

[datalandia]

tyrtamos, oui j'utilise un algorithme de recherche.
ton code fait une brute force si je puis dire c'est ce que je ne veut surtout pas faire.

mon code est un algorithme génétique, c'est un algorithme de recherche.

Au début je génère une population initiale, une population c'est un ensemble d’individu, un individu c'est un ensemble de mots (dans mon exemple c'est 3 mots)
c'est population je vais calculer sa fitness, donc la somme ascii de chaque individu
Et je répète cela autant de fois que je le souhaite, mais a chaque itération, je sélectionne les meilleurs individus (somme ascii la plus élevée) et je supprime les plus mauvais (somme ascii la plus faible)
Pour ne pas me retrouver sur un maximum local, je rajoute aussi des individues aléatoirement et je conserve aussi une faible part d’individus faible

au final mam population est censé évoluer et aller vers la solution à mon probleme

[lg_53]

@tyrtamos : Les algorithmes génétiques sont des méthodes d'optimisations relativement utilisées dans des cas complexes. Si tu ne les connais pas, tu peux regarder ici :
https://fr.wikipedia.org/wiki/Algori...A9n%C3%A9tique
en particulier la section "schéma récapitulatif" qui donne une bonne vision de ce que l'algo fait. Ici datalandia nous met un cas simple mais je présume que son application est beaucoup plus complexe.

@datalandia : En général quand on code un tel algo, on peut déjà démarrer par ne pas mettre de mutation. Si l'algorithme est bien codé, ca converge quand meme (juste on peut éventuellement tombé sur un minimum local). Je regarde ton code et je t'en dis plus.

[lg_53]

Aie aie aie. J'ai l'impression que tu essaies de faire des choses compliqués et que tu n'as pas les connaissances python suffisantes pour les faire. Je vais tenter de t'aiguiller tout de même.

1) Les variables globales : il faut éviter !!
EVOLUTION par exemple. Ce n'est pas à la fonction fitness de le mettre à jour ! Fitness calcule le score de l'individu. Et je peux très bien vouloir le score d'un individu sans vouloir le garder en mémoire dans une tierce variable. Ta fonction fitness devrait etre :

Code :

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

1
2
3
def fitness(individual, data):
    chaine=sentence(individual,words)
    return sum( ord(carac) for carac in chaine )

et EVOLUTION doit aller dans ton main, et être mis à jour dans ton main également (dans la boucle).

2) Ne duplique pas de code. Dans ton main on voit que tu réécris la fonction fitness. Donc non, il faut écrire la fonction fitness correctement et s'y référer à chaque fois qu'on en a besoin.

3) Qui plus est tu as un biais dans cette variable EVOLUTION que tu regardes :
- Soit tu regardes l'évolution du score moyen sur toute ta population
- Soit tu regardes l'évolution du score maximal sur toute ta population
- Soit tu regardes l'évolution du score de chaque individu de ta population (donc là tu aurais 30 courbes)
Là tu ne fais aucun de ces 3 trucs là, juste tu as mis bout à bout toutes tes infos, ce qui n'as aucune pertinance. Donc dans évolution tu as qqch comme
[ind0_t0, ....,ind30_t0, ind0_t1, ..., ind30_t1, .... ind30_tn ]
(ind pour individu, et t pour le temps, ou le numéro de la génération si tu préfères) ...

4) Tu utilses un IDE ? Moi perso j'utilise spyder. Et tout de suite il me dit (un petit warning) que dans la fonction evolve, la variable retained est certes calculée, mais jamais utilisée. Etrange ça, car vu son nom, c'est plutot le genre de variable que l'on doit retenir et utiliser !

[datalandia]

lg_53 merci pour ton aide.

avec tes conseilles j'ai modifier mon code, alors j'ai lancé plusieurs fois et le programme converge vers un moyenne, il cherche pas les valeurs max ou min mais cherche le juste milieu, bon je pense que sa viens de ma fonction cross qui calcule la moyenne en tous cas grace a toi j'ai déja un programme qui fait quelque chose.

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
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
116
117
118
119
 
import random
import statistics
 
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)
    return sum(ord(carac) for carac in chaine)
 
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.0, random_select=0.00, mutation_rate=0.00):
    def cmp_ind(ind):
        return fitness(ind, data)
    sorted_population = sorted(population, key=cmp_ind, reverse=True)
 
    len_retained = round(len(population) * retain)
 
    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 = 100
    EVOLUTION_moyenne=[]
    EVOLUTION_minimal=[]
    EVOLUTION_maximal=[]
 
    for i in range(max_iter):
        population_score=[]
        moyenne=0
        for element in next_population :
            chaine=sentence(element,words)
            score=sum(ord(carac) for carac in chaine)
            population_score.append(score)
            moyenne=moyenne+score
        moyenne=moyenne/len(next_population)
 
        print("*************")
        print("Moyenne : "+str(moyenne))
        print("Max : "+str(max(population_score)))
        print("Min : "+str(min(population_score)))
 
        EVOLUTION_moyenne.append(moyenne)
        EVOLUTION_minimal.append(min(population_score))
        EVOLUTION_maximal.append(max(population_score))
        next_population = evolve(next_population, data)
 
 
    sorted_population = sorted(next_population, key=lambda x: fitness(x, data))
    best_individual = sorted_population[0]
 
    print("************************************************")
    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_moyenne)
    plt.plot(EVOLUTION_minimal)
    plt.plot(EVOLUTION_maximal)
    plt.savefig('myfig')

si je remplace dans la fonction cross le code par ceci :

Code :

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

return tuple(round(min(genes)) for genes in zip(mother, father))

je converge vers le minimum



mais par contre si je mets :

Code :

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

return tuple(round(max(genes)) for genes in zip(mother, father))

je converge vers la moyenne, pourquoi ?

[bm]

Bonjour,

Je n'ai pas suivi depuis le début.
Avec le ML ( machine learning ), la convergeance est plus sûre en normalisant les variables.

[lg_53]

Ok bonne avancée.

Effectivement tu as un problème dans ta fonction cross.
Si je fais affiché mother et father, au premier coup j'obtient :
mother : (1,5,0)
father : (1,0,1)
cross : (1,5,1)
Ok ... mais pourquoi prendre la position la plus élevée ? Si tu savais que plus la position est élevée et plus le fitness est élevé alors tu n'aurais rien à faire puisque ça voudrais dire que les "words" sont trié par fitness croissant, et donc tu saurais que la phrase avec le fitness max, ca serait celle constituée des derniers mots de words.

Donc non ce n'est pas ça ce que doit faire la fonction cross. Tu prends 2 individus (un père et une mère), et aléatoirement tu choisis pour la fille, si le gène qu'elle possède vient du père ou de la mère. Leur gènes se mélangent à la manière de la reproduction sexuée chez les Hommes. Si tu as un frère ou une soeur, il ne t'es pas identique, même si les parents sont les mêmes. Ici c'est pareil, il y a de l'alétoire. Si t'es pas au point là dessus, il faut te refaire un peu de lecture sur l'algorithme génétique en lui même, car là ce n'est plus le python le souci.

Si je reviens au code donc avec une entrée comme ça :
mother : (1,5,0)
father : (1,0,1)
le cross en sortie devrait être qqch d'aléatoire parmi
(1,5,0) ## on a tout de la mère
(1,0,1) ## on a tout du père
(1,5,1)
(1,0,0)
et chacun ont la meme probabilité d'être formé...

Execute plein de fois ta fonction avec la même entrée pour la tester de manière isolée :

Code :

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

1
2
for i in range(100) :
    print(cross((1,0,1), (1,5,0)))

et constater que dans ton cas elle fournit toujours la même chose et pas quelquechose d'aléatoire.



Tu as encore d'autres problèmes mis à part ça, lié à l'algo aussi. Quand tu écris dans la fonction evolve :

Code :

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

return random_selected + mutated + children

Ca veut dire que tu retourne nécéssairement les enfants. Et bien nom. On n'a mettons 100 individus, on prend les 50 meilleurs, on les fait se reproduire donc on obtient 25 enfants. Donc là on a 125 individus. Ces 125 tu les trie selon leur fitness, et la nouvelle population c'est les 100 avec le meilleur fitness. Mais donc tu peux très bien ne pas avoir conservé un enfant dans ta population (imagine qu'il a simplement pris le pire de ces 2 parents).
D'ailleurs au passage tu remarques que c'est ta fonction evolve qui devrait se charger de retourner une population triée et non le faire dans le main.

PS : Le fitness on en a besoin tout le temps. Donc tu peux éventuellement le garder en mémoire, voire meme le faire retourner aussi par ta fonction evolve

Code :

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

return new_pop, fitness_new_pop

et récupérer son résultat comme ceci :

Code :

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

next_population, fitness_next_population = evolve(next_population, data)

[datalandia]

MERCI !!!
c'est bon je pense que c'est bon maintenant :

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
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
import random
import statistics
 
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)
    return sum(ord(carac) for carac in chaine)
 
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):
    children=[]
    for i in range(0,len(mother)):
        selection=random.choice([True, False])
        if selection:
            children.append(mother[i])
        else:
            children.append(father[i])
 
    children=tuple(children)
    return children
 
def sentence(individual, words):
    return ' '.join([words[i][individual[i]] for i in range(len(words))])
 
def evolve(population, data, retain=0.0, random_select=0.00, mutation_rate=0.00):
    def cmp_ind(ind):
        return fitness(ind, data)
    sorted_population = sorted(population, key=cmp_ind)
    #sorted_population = sorted(population, key=cmp_ind, reverse=True)
 
    len_retained = round(len(population) * retain)
 
    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[len_retained:]),
              random.choice(sorted_population[len_retained:]))
        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 = 5
    EVOLUTION_moyenne=[]
    EVOLUTION_minimal=[]
    EVOLUTION_maximal=[]
 
    for i in range(max_iter):
        population_score=[]
        moyenne=0
        for element in next_population :
            chaine=sentence(element,words)
            score=sum(ord(carac) for carac in chaine)
            population_score.append(score)
            moyenne=moyenne+score
        moyenne=moyenne/len(next_population)
 
        print("*************")
        print("Moyenne : "+str(moyenne))
        print("Max : "+str(max(population_score)))
        print("Min : "+str(min(population_score)))
 
        EVOLUTION_moyenne.append(moyenne)
        EVOLUTION_minimal.append(min(population_score))
        EVOLUTION_maximal.append(max(population_score))
        next_population = evolve(next_population, data, retain=0.9)
 
 
    sorted_population = sorted(next_population, key=lambda x: fitness(x, data))
    best_individual = sorted_population[0]
 
    print("************************************************")
    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_moyenne)
    plt.plot(EVOLUTION_minimal)
    plt.plot(EVOLUTION_maximal)
    plt.savefig('myfig')

pour trouver la solution max je fais
sorted_population = sorted(population, key=cmp_ind)

pour avoir le minium je fais l'inverse :
sorted_population = sorted(population, key=cmp_ind, reverse=True)

dans les 2 cas sa marche, voila ce que j'ai pour le max par exemple, on voit que sa semble marcher


pour le reproduction, je prend que 10% des meilleurs, mais j'en prend plus, par exemple 50% la courbe monte mais forcément moins vite
mais c'est plus safe car le risque de tomber sur un maximum locale est moindre