Introduction à l'intelligence artificielle avec Python 2 «Pratique de l'algorithme génétique»

Préface

Puisque nous allons commencer par la pratique ici, veuillez vous référer d'abord à "Genetic Algorithm-Theory-".

essayons

Maintenant, exécutons GA en utilisant Python. Ici, nous allons procéder en supposant que vous avez déjà des connaissances de base de Python. Utilisez des fonctions, mais n'utilisez pas de classes car les explications sont chaotiques.

Problème ONEMAX

Que faites-vous exactement?

Un exemple courant est le problème ONEMAX. c'est, 　　　　　　　　　　　　｛1，0，0，1，0，1，1，1，0，0｝ À partir d'un tableau composé de «1» ou «0», tel que 　　　　　　　　　　　　｛1，1，1，1，1，1，1，1，1，1｝ J'ai réfléchi à la façon de créer un tableau de tous les 1.

Ceci est résolu avec GA. Le flux consiste à générer au hasard une séquence avec "1" ou "0" comme élément, à l'utiliser comme information génétique et à construire un algorithme en utilisant la valeur totale de la séquence comme standard d'évaluation.

Tout d'abord, le code entier est affiché.

code

GA.py

import random
from decimal import Decimal


GENOM_LENGTH = 20          #Longueur des informations génétiques
MAX_GENOM_LIST = 200        #La taille de la population de gènes
SELECT_GENOM = 10           #Nombre de sélections de gènes élites
INDIVIDUAL_MUTATION = 0.01  #Probabilité de mutation individuelle
GENOM_MUTATION = 0.01       #Probabilité de mutation génique
MAX_GENERATION = 20        #Nombre de générations à répéter


def genom(length):

    """
Générez des gènes au hasard.
La valeur de retour est la séquence génique d'un individu
    """
    genom_list = []
    for i in range(length):
        a = random.randint(0,1)
        genom_list.append(a)
    return genom_list
    

def evaluation(ga):
    """
Fonction d'évaluation d'un individu.
À partir de la séquence de gène obtenue par l'argument, la valeur totale est renvoyée comme valeur d'évaluation.
    """
    genom_total = sum(ga)
    genom_num = len(ga)
    return Decimal(genom_total) / Decimal(genom_num)


def select_elite(ga,elite_length):
    """
Une fonction pour extraire d'excellents individus.
    """
    sort_result = sorted(ga, reverse=True, key=evaluation)
    result = [sort_result.pop(0) for i in range(elite_length)]
    return result


def crossover(ga_one,ga_second):
    """
Fonction croisée.
Deux descendants sont renvoyés des deux parents donnés par l'argument.
Ici, il est hérité par croisement en deux points.
    """
    genom_list = []
    cross_one = random.randint(0,GENOM_LENGTH)
    cross_second = random.randint(cross_one,GENOM_LENGTH)

    one = ga_one
    second = ga_second

    progeny_one = one[:cross_one] + second[cross_one:cross_second] + one[cross_second:]
    progeny_second = second[:cross_one] + one[cross_one:cross_second] + second[cross_second:]

    genom_list.append(progeny_one)
    genom_list.append(progeny_second)

    return genom_list


def create_next_generation(ga,ga_elite,ga_progeny):
    """
Générez la population de la prochaine génération.
Obtenez le groupe de génération précédente avec le premier argument,
Les deuxième et troisième arguments élite et enfants sont ajoutés, et les individus les moins excellents sont supprimés.
    """
    next_generation_geno = sorted(ga, reverse = False, key = evaluation)

    for i in range(0, len(ga_elite) + len(ga_progeny)):
        next_generation_geno.pop(0)

    next_generation_geno.extend(ga_elite)
    next_generation_geno.extend(ga_progeny)
    return next_generation_geno

def mutation(ga, individual_mutation, genom_mutation):
    """
Faites une mutation.
Sélectionnez si l'individu mute avec une certaine probabilité,
L'élément de séquence génique de l'individu capturé est également sélectionné avec probabilité,
Modifiez l'élément piégé sur 1 ou 0.
    """
    ga_list = []
    for i in ga:
        if individual_mutation > (random.randint(0,100) / Decimal(100)):
            genom_list = []
            for i_ in i:
                if genom_mutation > (random.randint(0,100)/Decimal(100)):
                    genom_list.append(random.randint(0,1))
                else:
                    genom_list.append(i_)
            ga_list.append(genom_list)
        else:
            ga_list.append(i)

    return ga_list

    
if __name__ == '__main__':

    current_generation = []    
    for i in range(MAX_GENOM_LIST):
        current_generation.append(genom(GENOM_LENGTH))

    
    for count_ in range(1,MAX_GENERATION + 1):
        current_evaluation = []

        for i in range(MAX_GENOM_LIST):
            evaluation_result = evaluation(current_generation[i])
            current_evaluation.append(evaluation_result)

        elite_genes = select_elite(current_generation,SELECT_GENOM)

        progeny_gene = []

        for i in range(0,SELECT_GENOM):
            progeny_gene.extend(crossover(elite_genes[i-1],elite_genes[i]))

        next_generation = create_next_generation(current_generation,elite_genes,progeny_gene)
        next_generation = mutation(next_generation,INDIVIDUAL_MUTATION,GENOM_MUTATION)

        fits = []
        j = 0
        for i in current_generation:
            fits.append(current_evaluation[j])
            j = j + 1
        min_ = min(fits)
        max_ = max(fits)
        avg_ = sum(fits) / Decimal(len(fits))
        
        print ("-----------Non.{}génération----------".format(count_))
        print ("        Min:{}".format(min_))
        print ("        Max:{}".format(max_))
        print ("        avg:{}".format(avg_))
        print("\n")

        current_generation = next_generation
        

    print ("Le meilleur individu est{}".format(elite_genes[0]))

Contour

La procédure est comme indiqué dans l'article précédent, Théorie. Dans ce programme

** Le nombre d'individus par génération est de 200, La longueur de la séquence génique par individu est de 20, Le nombre de générations répétitives est de 20, La probabilité de mutation est de 1% pour les deux espèces, 20 choix élites, **

Il évolue avec la valeur. Bien entendu, cette valeur peut être décidée librement. Fondamentalement, plus le nombre de générations est élevé, meilleur sera l'individu et plus la longueur de la séquence du gène sera longue, plus la vitesse de convergence vers la solution optimale sera lente, de sorte que le nombre de générations et la taille de l'ensemble seront augmentés. Il y a un besoin de. ** **

Et quand tu fais ça,

-----------20e génération----------
        Min:0.9
        Max:1
        avg:0.96875


Le meilleur individu est[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Il a été produit comme ça et a résolu le problème ONEMAX avec brio! !! (Seules les dernières lignes sont répertoriées.)

C'est la puissance de GA! !!

Tâche

Vous pouvez maintenant comprendre ce qu'est l'AG et sa puissance. Par conséquent, je voudrais confier une tâche à ceux qui apprennent en utilisant cet article.

** ⑴ Créez et exécutez le code ci-dessus en excluant le traitement de la mutation. Considérez également les résultats. ⑵ Solution optimale, 　　　　　　　　　　　　　　　｛1,0,1,0,1,0,1,0,..........0,1｝ En tant que tel, GA est assemblé en tant qu'individu dans lequel "1" et "0" sont disposés en alternance. ** **

C'est tout.

Sommaire

Il semble qu'il existe une image selon laquelle l'IA est extrêmement difficile à démarrer. Mais étonnamment, la fondation est intéressante et facile à imaginer. Dans cet article, vous pouvez voir un aperçu de l'IA. Tout ce que vous avez à faire est de présenter vos idées. À la prochaine. Merci pour la lecture.