232 lines
7.8 KiB
Python
232 lines
7.8 KiB
Python
# Librairie du projet en version impératif
|
|
|
|
import random
|
|
import Levenshtein
|
|
|
|
def min_i(array: list[int]) -> int:
|
|
"""
|
|
Fonction renvoyant l'indexe du minimum d'une liste d'entiers
|
|
"""
|
|
min_val = array[0]
|
|
min_i = 0
|
|
for i in range(len(array)):
|
|
if array[i] < min_val:
|
|
min_val = array[i]
|
|
min_i = i
|
|
return min_i
|
|
|
|
def max_i(array: list[int]) -> int:
|
|
"""
|
|
Fonction renvoyant l'indexe du maximum d'une liste d'entiers
|
|
"""
|
|
max_val = array[0]
|
|
max_i = 0
|
|
for i in range(len(array)):
|
|
if array[i] > max_val:
|
|
max_val = array[i]
|
|
max_i = i
|
|
return max_i
|
|
|
|
def new_population(pm, ng, n, ts, tm, alpha, fm):
|
|
"""
|
|
fonction qui renvoie une nouvelle population
|
|
"""
|
|
population = {
|
|
"individuals": [new_individual() for i in range(n)],
|
|
"pm": pm,
|
|
"ng": ng,
|
|
"l": len(pm),
|
|
"n": n,
|
|
"ts": ts,
|
|
"tm": tm,
|
|
"alpha": alpha,
|
|
"fm": fm
|
|
}
|
|
|
|
# On rend aléatoire les chromozomes des individus
|
|
for individual in population["individuals"]:
|
|
randomize(individual, 4, 30)
|
|
|
|
return population
|
|
|
|
def new_individual():
|
|
"""
|
|
fonction qui renvoie un nouvel individu
|
|
"""
|
|
return {
|
|
"chromozome": ""
|
|
}
|
|
|
|
def randomize(individual, min_l, max_l) -> str:
|
|
"""
|
|
Methode qui change la valeur d'un chromozome pour une valeur aléatoire
|
|
"""
|
|
new = ""
|
|
for i in range(random.randint(min_l, max_l)):
|
|
new += chr(random.randint(0, 255))
|
|
individual["chromozome"] = new
|
|
|
|
def fitness1(individual, pm) -> int:
|
|
"""
|
|
Première methode de fitness, fait la somme des différences entre les codages des caractères des deux chaînes.
|
|
"""
|
|
sum = 0
|
|
for i in range(len(individual["chromozome"])):
|
|
if i < len(pm) and i < len(individual["chromozome"]):
|
|
sum += abs(ord(individual["chromozome"][i]) - ord(pm[i]))
|
|
return -sum
|
|
|
|
def fitness2(individual, pm, alpha) -> int:
|
|
"""
|
|
Deuxième methode de fitness qui compte les caractères bien placés et mal placés et qui renvoie un int pondéré par alpha
|
|
"""
|
|
match = 0
|
|
missed_placed = 0
|
|
for i in range(len(individual["chromozome"])):
|
|
# Si la chaîne est plus grande que la phrase alors on rajoute des caractères mal placés
|
|
if i >= len(pm):
|
|
missed_placed += len(individual["chromozome"]) - len(pm)
|
|
break
|
|
elif individual["chromozome"][i] == pm[i]:
|
|
match += 1
|
|
else:
|
|
missed_placed += 1
|
|
# Si la phrase est trop longue on rajoute autant de caractères mal placés que de caractères en trop
|
|
if len(pm) > len(individual["chromozome"]):
|
|
missed_placed += len(pm) - len(individual["chromozome"])
|
|
return match + alpha * missed_placed
|
|
|
|
def fitness3(individual, pm) -> int:
|
|
"""
|
|
Troisième methode de fitness qui utilise la distance de Levenshtein
|
|
"""
|
|
return -Levenshtein.distance(individual["chromozome"], pm)
|
|
|
|
def get_fitness(population, individual) -> int:
|
|
"""
|
|
Fonction qui renvoie la fitness d'un individu en utilisant la fonction choisie en paramètre de la population
|
|
"""
|
|
match population["fm"]:
|
|
case 1:
|
|
return fitness1(individual, population["pm"])
|
|
case 2:
|
|
return fitness2(individual, population["pm"], population["alpha"])
|
|
case 3:
|
|
return fitness3(individual, population["pm"])
|
|
case _:
|
|
return fitness1(individual, population["pm"])
|
|
|
|
def get_fitness_list(population):
|
|
"""
|
|
Fonction renvoyant une liste des fitness de touts les individus d'une population
|
|
"""
|
|
fitness_list = []
|
|
for individual in population["individuals"]:
|
|
fitness_list.append(get_fitness(population, individual))
|
|
return fitness_list
|
|
|
|
def get_best(population):
|
|
"""
|
|
Methode qui renvoie le meilleur individu de la population
|
|
"""
|
|
fitness_list = get_fitness_list(population)
|
|
return population["individuals"][max_i(fitness_list)]
|
|
|
|
def print_best(population) -> None:
|
|
"""
|
|
Methode qui affiche le meilleur individu de la population
|
|
"""
|
|
print(get_best(population)["chromozome"])
|
|
|
|
def select(population) -> None:
|
|
"""
|
|
Methode qui sélectionne les meilleurs individus
|
|
"""
|
|
fitness_list = get_fitness_list(population)
|
|
for i in range(int((1 - population["ts"]) * population["n"])):
|
|
# On détermine quel est le moins bon individu
|
|
least = min_i(fitness_list)
|
|
# On le supprime des deux listes
|
|
fitness_list.pop(least)
|
|
population["individuals"].pop(least)
|
|
|
|
def get_two_random_individuals(population):
|
|
"""
|
|
Fonction renvoyant deux individus choisis aléatoirement
|
|
"""
|
|
i = random.randint(0, len(population["individuals"]) - 1)
|
|
j = random.randint(0, len(population["individuals"]) - 1)
|
|
while i == j:
|
|
j = random.randint(0, len(population["individuals"]) - 1)
|
|
return (population["individuals"][i], population['individuals'][j])
|
|
|
|
def reproduct(population) -> None:
|
|
"""
|
|
Methode qui reproduit les individus entre eux jusqu'à obtenir une population de taille N
|
|
"""
|
|
new = []
|
|
# On créé de nouveaux individus jusqu'à avoir atteint la taille de population demandée
|
|
while len(population["individuals"]) + len(new) != population["n"]:
|
|
# On prend deux individus aléatoires
|
|
indivi_1, indivi_2 = get_two_random_individuals(population)
|
|
|
|
# On calcule le cut en fonction de la moyenne des tailles des deux individus
|
|
avg = (len(indivi_1) + len(indivi_2)) // 2
|
|
cut = random.randint(avg // 3, 2 * avg // 3)
|
|
# On fait en sorte que le cut reste dans les valeurs possibles
|
|
while cut > len(indivi_1) or cut > len(indivi_2):
|
|
cut = random.randint(avg // 3, 2 * avg // 3)
|
|
|
|
# On créé le nouvel individu et on l'ajoute à la population
|
|
new_chromozome = indivi_1["chromozome"][:cut] + indivi_2["chromozome"][cut:]
|
|
child = new_individual()
|
|
child["chromozome"] = new_chromozome
|
|
new.append(child)
|
|
|
|
population["individuals"] += new
|
|
|
|
def mutate(individual) -> None:
|
|
"""
|
|
Methode qui change un des caractères du chromozome
|
|
"""
|
|
new = list(individual["chromozome"])
|
|
# On jette un dé 6 pour déterminer l'effet qu'aura la mutation
|
|
dice = random.randint(1, 6)
|
|
# Sur un 1 on ajoute un caractère aléatoire
|
|
if dice == 1 and len(new) < 30:
|
|
new.insert(random.randint(0, len(new) - 1), chr(random.randint(0, 255)))
|
|
# Sur un 2 on retire un caractère aléatoire
|
|
elif dice == 2 and len(new) > 4:
|
|
new.pop(random.randint(0, len(new) - 1))
|
|
# Sinon on modifie un caractère déjà existant
|
|
else :
|
|
new[random.randint(0, len(new) - 1)] = chr(random.randint(0, 255))
|
|
individual["chromozome"] = "".join(new)
|
|
|
|
def mutate_pop(population) -> None:
|
|
"""
|
|
Methode qui mute une partie de la population selon le taut de mutation
|
|
"""
|
|
mutated = []
|
|
for i in range(int(population["tm"] * population["n"])):
|
|
# Sélectionne un individu aléatoire qui n'a pas encore été muté à cette génération
|
|
to_mutate = random.randint(0, population["n"] - 1)
|
|
while to_mutate in mutated:
|
|
to_mutate = random.randint(0, population["n"] - 1)
|
|
# Mutation de l'individu choisi
|
|
mutate(population["individuals"][to_mutate])
|
|
mutated.append(to_mutate)
|
|
|
|
def run(population) -> int:
|
|
"""
|
|
Boucle principale
|
|
"""
|
|
# On fait autant de générations que demandé
|
|
for i in range(population["ng"]):
|
|
# On arrête le programme une fois la phrase retrouvée et on renvoie le nombre de générations utilisées
|
|
if get_best(population)["chromozome"] == population["pm"]:
|
|
return i
|
|
select(population)
|
|
reproduct(population)
|
|
mutate_pop(population)
|
|
return population["ng"]
|