import numpy as np
import random
import matplotlib.pyplot as plt

Entrons dans le sujet principal.

Qu'est-ce que l'algorithme génétique (GA)?

Descendants prospères de ceux qui ont d'excellents gènes. Dans l'algorithme génétique, une bonne solution prospère de la même manière.

La prospérité des descendants

Un individu supérieur dans chaque élément donne naissance à de nombreux descendants, Les individus inférieurs ne peuvent donner naissance qu'à quelques petits. La même chose se produit avec le passage de la génération des enfants à la génération des petits-enfants. En répétant ce processus, naissent des enfants sophistiqués et adaptés à l'environnement.

mutation

Au fur et à mesure de la traversée, seuls des individus similaires seront trouvés. Nos gènes assurent la diversité en provoquant des mutations occasionnelles.

Quel est le problème du voyageur de commerce (TSP)?

Le problème du voyageur de commerce est C'est une sorte de problème qu'un vendeur doit parcourir n destinations d'affaires dans quel ordre. Théoriquement, il y a des routes n! Street, donc le round-robin est difficile.

Cette fois, je voudrais résoudre GA en utilisant ce TSP.

couler

[Source]((http://samuiui.com/2019/10/27/Implémentation d'un algorithme génétique (ga) en python et patrouilles /))

Génération individuelle initiale

En tant qu'individu précoce, vous devez créer une ville et des gènes.

ville

Génère n villes dont les coordonnées x et y sont toutes deux comprises entre 0 et 1. L'entrée est le nombre de villes, la sortie est la matrice de (nombre de villes) x 2 Exemple d'implémentation: generate_rand_cities

#Générer une ville
def generate_rand_cities(num_cities):
    positions = np.zeros((num_cities, 2))
    for i in range(num_cities):
        positions[i, 0] = random.random()
        positions[i, 1] = random.random()
    return positions
#Comme test
generate_rand_cities(10)

À propos de aléatoire (random.random)

random.random()

Génère de manière aléatoire des nombres à virgule flottante supérieurs ou égaux à 0,0 et inférieurs à 1,0

gène

Donnez au gène des informations sur l'ordre de circuler dans la ville. Faites correspondre la longueur du gène avec le nombre de villes. Par exemple, lorsque le nombre de villes est de 6, [3, 5, 1, 0, 4, 2] [0, 4, 2, 1, 5, 3] De tels individus sont possibles.

Parce que les gènes font plusieurs individus en une génération Les gènes sont représentés par la matrice (nombre d'individus de gènes) x (nombre de villes).

L'entrée est le nombre de villes et le nombre d'individus dans une génération, et la sortie est la matrice de (nombre de gènes) x (nombre de villes).

Exemple d'implémentation: generate_init_genes

#produire
def generate_init_genes(num_individual, num_cities):
    genes = np.zeros((num_individual, num_cities), dtype=np.int16)
    for i in range(num_individual):
        genes[i,] = random.sample(range(num_cities), k=num_cities)
    return genes
#Comme test
generate_init_genes(15,10)

À propos de random (random.sample)

Random.sample est extrait au hasard sans duplication. Par exemple

l = [0, 1, 2, 3, 4]
random.sample(l, 3)

Affiche quelque chose comme [4, 2, 1] ou [1, 0, 3].

Évaluation

Dans cette tâche, les gènes présentant des voies plus courtes doivent être fortement évalués. Par conséquent, tout d'abord, la longueur de la voie correspondant au gène est obtenue. Après cela, il est comparé et évalué au sein de la génération.

Voies correspondant aux gènes

La source de référence a calculé la distance entre les villes pour chaque gène. Faites un tableau sur la distance entre les villes et référez-vous-y selon l'ordre des gènes.

Tableau des distances entre les villes

Exemple d'implémentation

#Tableau sur les distances entre les villes
def generate_dist_table(positions):
    path_table = np.zeros((len(positions), len(positions)))
    for i in range(len(positions)):
        for j in range(len(positions)):
            path_table[i,j] = np.linalg.norm(positions[i]-positions[j])
    return path_table

#Comme test
num_cities = 4
positions = generate_rand_cities(4)
generate_dist_table(positions)

La distance entre deux villes est calculée deux fois. Je peux encore gratter ici ...

La longueur de la voie correspondant au gène

Sur la base de ce tableau, la longueur de la voie correspondant au gène est obtenue.

#Se reporter au tableau pour trouver la somme des voies correspondant aux gènes
def sum_path2(path_table, gene):
    sum = 0.
    for i in range(len(gene)-1):
        sum += path_table[int(gene[i]),int(gene[i+1])]
    return sum

#Comme test
cities = generate_rand_cities(10)
genes = generate_init_genes(15,10)
dist_table = generate_dist_table(cities)
for i in range(len(genes)):
    print(sum_path2(dist_table, genes[i]))

Afin d'évaluer les gènes collectivement pour chaque génération, définissez une fonction pour produire collectivement les gènes d'une génération.

#Calcul d'une génération pour la somme des itinéraires
def genes_path2(path_table, genes):
    pathlength_vec = np.zeros(len(genes))
    for i in range(len(genes)):
        pathlength_vec[i] = sum_path2(path_table, genes[i])
    return pathlength_vec

#Comme test
cities = generate_rand_cities(10)
genes = generate_init_genes(15,10)
dist_table = generate_dist_table(cities)
genes_path2(dist_table, genes)

roulette

La longueur de la voie correspondant au gène a été trouvée. Cette fois, plus l'itinéraire est court, plus l'évaluation est élevée. Plus l'itinéraire est court, plus la probabilité d'être sélectionné comme celui qui laisse la progéniture est élevée. Effectuez la normalisation.

#roulette
def generate_roulette(fitness_vec):
    total = np.sum(fitness_vec)
    roulette = np.zeros(len(fitness_vec))
    for i in range(len(fitness_vec)):
        roulette[i] = fitness_vec[i]/total
    return roulette

#Comme test
fitness = np.array([20,50,30])
generate_roulette(fitness)

Au contraire

array([0.2, 0.5, 0.3])

Sera.

Évaluer les gènes

La longueur de la voie correspondant au gène est déjà connue. Cette fois, plus l'itinéraire est court, plus l'évaluation est élevée. Plus l'itinéraire est court, plus la probabilité d'être sélectionné comme celui qui laisse la progéniture est élevée. Par conséquent, cette fois, le nombre inverse de la longueur de l'itinéraire est utilisé.

#Exemple d'exécution de la roulette
cities = generate_rand_cities(20)
genes = generate_init_genes(21, 20)
dist_table = generate_dist_table(cities)
paths = genes_path2(dist_table, genes)
inverse_path = 1/paths
print("path length: "+str(paths))
print("roulette table: "+str(generate_roulette(inverse_path)))

Puisque la table de roulette a un total de 1, cela peut être interprété comme la probabilité que le gène correspondant soit sélectionné. Ceci est utilisé pour sélectionner les gènes.

Sélection (sélection)

#Sélectionnez les individus à croiser en fonction de la roulette
def roulette_choice(fitness_vec):
    roulette = generate_roulette(fitness_vec)
    choiced = np.random.choice(len(roulette), 2, replace=True, p=roulette)
    return choiced

#Comme test
cities = generate_rand_cities(20)
genes = generate_init_genes(21, 20)
dist_table = generate_dist_table(cities)
fitness_vec = 1 / genes_path2(dist_table, genes)
roulette_choice(fitness_vec)

Créez une table de roulette avec generate_roulette. Sélectionnez deux gènes de la roulette en fonction de la table de roulette.

À propos de random (random.choice)

random.choice a des doublons et sélectionne une valeur au hasard. Plage de nombres sélectionnés par le premier argument, Le deuxième argument est le nombre à choisir, Spécifiez s'il existe un doublon avec remplacement (Vrai avec duplicata) La probabilité que chacun soit sélectionné est spécifiée par p.

Traversée

Il est maintenant possible de sélectionner deux individus relativement excellents en utilisant roulette_choice. Multipliez les deux individus. Il existe plusieurs méthodes de croisement selon la forme du gène et également pour la même forme de gène. Par exemple, il semble y avoir un croisement d'ordre et un croisement circulaire → Application de GA aux problèmes d'ordre Cette fois, nous avons effectué un croisement partiel. Veuillez vous référer à l'image ci-dessous pour la méthode de croisement partiel. [Source]((http://samuiui.com/2019/10/27/Implémentation d'un algorithme génétique (ga) en python et patrouilles /))

Implémentation du crossover partiel

#Implémentation du crossover partiel
def partial_crossover(parent1, parent2):
    num = len(parent1)
    cross_point = random.randrange(1,num-1)   #Pause
    child1 = parent1
    child2 = parent2
    for i in range(num - cross_point):
        #Valeur juste à droite de la pause
        target_index = cross_point + i
        target_value1 = parent1[target_index]
        target_value2 = parent2[target_index]
        exchange_index1 = np.where(parent1 == target_value2)
        exchange_index2 = np.where(parent2 == target_value1)
        #Échange
        child1[target_index] = target_value2
        child2[target_index] = target_value1
        child1[exchange_index1] = target_value1
        child2[exchange_index2] = target_value2
    return child1, child2

#Comme test
genes = generate_init_genes(2, 10)
print("parent1: "+str(genes[0]))
print("parent2: "+str(genes[1]))
child = partial_crossover(genes[0], genes[1])
print("child1:  "+str(child[0]))
print("child2:  "+str(child[1]))

mutation

Il existe différentes méthodes de mutation. Cette fois, nous ferons ce qu'on appelle la translocation. Échangez deux lieux choisis au hasard.

def translocation_mutation2(genes, p_value):
    mutated_genes = genes
    for i in range(len(genes)):
        mutation_flg = np.random.choice(2, 1, p = [1-p_value, p_value])
        if mutation_flg == 1:
            mutation_value = np.random.choice(genes[i], 2, replace = False)
            mutation_position1 = np.where(genes[i] == mutation_value[0])
            mutation_position2 = np.where(genes[i] == mutation_value[1])
            mutated_genes[i][mutation_position1] = mutation_value[1]
            mutated_genes[i][mutation_position2] = mutation_value[0]
    return mutated_genes

#Comme test
genes = generate_init_genes(5, 10)
print("before")
print(genes)
print("after")
print(translocation_mutation2(genes, 0.7))

mutation_flag a une probabilité de p_value de 1. Par conséquent, le gène mute avec une probabilité de p_value.

Visualisation

Bien qu'il ne soit pas écrit dans l'organigramme, il est visualisé à l'aide de matplotlib pour vérifier la transition de GA.

Emplacement de la ville

#Visualisation de l'emplacement de la ville
def show_cities(cities):
    for i in range(len(cities)):
        plt.scatter(cities[i][0], cities[i][1])

#Comme test
cities = generate_rand_cities(10)
show_cities(cities)

Visualisation de l'itinéraire

def show_route(cities, gene):
    for i in range(len(gene)-1):
        if i == 0:
            plt.text(cities[int(gene[i])][0], cities[int(gene[i])][1], "start")
        else:
            plt.text(cities[int(gene[i])][0], cities[int(gene[i])][1], str(i))
        plt.plot([cities[int(gene[i])][0], cities[int(gene[i+1])][0]], 
                 [cities[int(gene[i])][1], cities[int(gene[i+1])][1]])
    plt.text(cities[int(gene[i+1])][0], cities[int(gene[i+1])][1], "goal")

#Comme test
cities = generate_rand_cities(10)
show_cities(cities)
genes = generate_init_genes(10,10)
show_route(cities,genes[0])

L'intégration

Implémentez un programme qui résout TSP avec GA en utilisant les fonctions créées jusqu'à présent.

Paramètres

#Paramètres
num_cities = 10
individuals = 21
generation = 10000
elite = 9
p_mutation = 0.01

Initialiser

#Initialiser
cities = generate_rand_cities(num_cities)
genes = generate_init_genes(individuals, num_cities)
dist_table = generate_dist_table(cities)
show_cities(cities)
show_route(cities, genes[0])
plt.show()

Vous devriez pouvoir voir ça

Département d'exécution

Avec une excellente élite de la génération parentale Les enfants d'élite individuels nés par croisement entre les générations parentales sont responsables de la génération des enfants. Des mutations se produisent dans la progéniture pour former la progéniture finale.

#Département d'exécution
top_individual=[]  #Liste des meilleures adaptabilité pour chaque génération
max_fit = 0  #La plus haute adaptabilité jamais vue
fitness_vec = np.reciprocal(genes_path2(dist_table, genes))
for i in range(generation):
    children = np.zeros(np.shape(genes))
    for j in range(int((individuals-elite)/2+1)):
        parents_indices = roulette_choice(fitness_vec)
        children[2*j], children[2*j+1] = partial_crossover(genes[parents_indices[0]], genes[parents_indices[1]])

    for j in range(individuals-elite, individuals):
        children[j] = genes[np.argsort(genes_path2(dist_table, genes))[j-individuals+elite]]

    children = translocation_mutation2(children, p_mutation)
    top_individual.append(max(fitness_vec))
    genes = children
    fitness_vec = np.reciprocal(genes_path2(dist_table, genes))
    if max(fitness_vec) > max_fit:  #Après avoir enregistré la plus grande adaptabilité jamais vue, affichez l'itinéraire
        max_fit = max(fitness_vec)
        show_cities(cities)
        show_route(cities, genes[np.argmax(fitness_vec)])
        plt.text(0.05, 0.0, "generation: " + str(i) + "  distance: " +str(sum_path2(dist_table,genes[np.argmax(fitness_vec)])))
        plt.show()

top_individual est une liste de la meilleure adaptabilité de chaque génération.

Le dernier affiché Ce sera celui qui circule dans l'ordre où l'itinéraire devient plus court. Aussi,

plt.plot(top_individual)

Vous pouvez vérifier la transition de l'adaptabilité à mesure que la génération change.

À propos de numpy (Remarque)

np.reciprocal () → Donne celui avec chaque élément inversé np.argmax () → Donne l'indice du plus grand de chaque élément np.argsort () → Ordre des index lorsque chaque élément est trié

Sommaire

Par défaut Nombre de villes, Population de gènes, Nombre de générations évolutives, Nombre d'élite, Probabilité de mutation, A été donné.

Évidemment, il y a un meilleur itinéraire lorsque vous augmentez le nombre de villes, mais il n'évolue pas vers cet itinéraire. De plus, il faut du temps pour calculer Il y a encore place à l'amélioration. Comme point possible

Comment traverser

Je ne sais rien car je ne connais pas d'autres moyens de traverser. Il existe peut-être une meilleure méthode de croisement. Aussi, je veux le connecter avec la mutation.

Probabilité de mutation

On pense que l'efficacité sera améliorée si la probabilité de mutation change en fonction de la similitude des parents.

Nombre d'élites ramassées

Cette fois, j'ai décidé des paramètres initiaux. Cependant, comme pour la probabilité de mutation, il peut être préférable de changer cela en fonction de la similitude des parents. A titre de test, si le nombre d'élites est réduit, l'adaptabilité n'augmente pas et ça vibre. On pense qu'il n'y aura pas d'augmentation de l'adaptabilité dans les premiers stades car les mauvais éléments seront ramassés lors du croisement.

Nombre de générations

Le nombre de générations a également été donné par défaut, mais il y a place à amélioration. Le nombre de générations est directement lié à la charge de calcul. Si la condition finale est définie à partir du taux de changement de l'adaptabilité, il ne sera pas nécessaire de spécifier le nombre de générations.

Nombre de gènes

De même, le nombre d'individus d'un gène est impliqué dans le calcul. Si le nombre d'individus est petit, il sera nécessaire d'augmenter la génération d'évolution. Si vous le définissez dans un rapport adapté au nombre de villes indiqué, vous n'aurez pas besoin de le saisir.

Perspective

En fin de compte, entrez simplement dans la ville et cela vous guidera vers le bon itinéraire. Par conséquent, il semble nécessaire d'étudier la méthode de croisement, comment donner la probabilité de mutation et des valeurs appropriées pour le nombre d'individus et le nombre de générations de gènes. Je ferai de mon mieux.

résumé aléatoire

-Sélectionnez un élément au hasard: random.choice () -Sélectionnez plusieurs éléments au hasard (pas de duplication): random.sample () -Sélectionnez plusieurs éléments au hasard (avec des doublons): random.choices () -Générer au hasard des nombres à virgule flottante de 0 à 1: random.random () De Utilisation aléatoire avec python