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