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 ?