[Pour les débutants] Re: Algorithme génétique partant de zéro [Intelligence artificielle]

Le public cible de cet article est

・ Je connais l'intelligence artificielle, mais je ne la comprends pas. ・ L'intelligence artificielle n'est-elle pas si précieuse en premier lieu? ・ Je pensais le faire, mais après avoir vu la formule, j'ai flétri et j'ai arrêté ・ Je veux faire de l'intelligence artificielle, mais je ne sais pas quoi faire ・ Les sources d'intelligence artificielle sont trop inutiles à lire

Il s'adresse à des gens comme.

L'algorithme génétique est défini comme faisant partie de l'intelligence artificielle, De mon point de vue, j'ai l'impression d'écrire un algorithme de dichotomie. Puisque l'algorithme génétique est également un algorithme, il est facile à mettre en œuvre si vous comprenez le concept.

Cet article est pratique et n'est pas destiné à quiconque n'est pas familiarisé avec les algorithmes génétiques en premier lieu. Mais ne t'inquiète pas. Ce n'est pas grave si vous lisez toutes les diapositives de Dieu ci-dessous et que vous les comprenez. (Cette diapositive est un moyen très efficace d'apprendre les algorithmes génétiques au niveau divin. Vendez-la sous forme de livre) Lancez-vous avec l'algorithme génétique!

Tout ce que vous devez comprendre est acceptable si vous pouvez approximativement comprendre ce qui suit De plus, les mots que vous ne comprenez pas sont essentiellement écrits sur la diapositive.

Flux approximatif de ce programme (avec quelques différences)

1 Déterminez le code qui exprime la solution 2 Créer N individus de gène courant aléatoire 3 Génération variable pour stocker la population de gènes de nouvelle génération 4 Calcul d'évaluation du gène actuel à l'aide de la fonction d'évaluation 5 Sélectionnez deux gènes de la génération actuelle 6 Croisez les gènes sélectionnés pour générer une progéniture 7 Faites des mutations dans la progéniture générée 8 Répétez 5-6 jusqu'à N individus de la prochaine génération 9 Transférer le groupe de nouvelle génération à la génération actuelle et répéter jusqu'à ce qu'il converge 10 Sortez le gène le mieux noté

Alors j'entrerai immédiatement

Aperçu

Dans cet article, nous allons résoudre le problème OneMax en utilisant un algorithme génétique (GA). De plus, cette fois, nous n'utiliserons pas de bibliothèque externe pour GA. Vous n'utilisez pas une bibliothèque lorsque vous faites une dichotomie, non? L'importation à utiliser est indiquée ci-dessous

・ Décimal pour éliminer au maximum les erreurs de calcul Aléatoire pour obtenir une valeur aléatoire -Classe qui stocke les informations sur le gène et la valeur d'évaluation du gène pour un calcul facile. Algorithme génétique (faites-le vous-même d'abord)

L'algorithme génétique est créé parce que le premier auteur de cet article aime le codage de type Java. (La méthode alternative est OK)

Quel est le problème OneMax?

list = [0,1,0,0,0,1,0,0,0,1,0,1,1,0,1] Séquences arrangées de manière aléatoire comme par calcul évolutif (GA) list = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] C'est un problème d'amener toutes les valeurs de tableau près de 1.

Objectif de réalisation de cet article

Le but est d'obtenir les mêmes résultats que ci-dessous. 1 est la solution optimale. La valeur minimale et la valeur moyenne de la valeur maximale des valeurs d'évaluation dans différentes générations sont sorties.

-----Résultats de 1ère génération-----
  Min:0.36
  Max:0.63
  Avg:0.4999
-----Résultats de 2e génération-----
  Min:0.46
  Max:0.65
  Avg:0.5653
-----Résultats de 3e génération-----
  Min:0.54
  Max:0.67
  Avg:0.6098
-----Résultats de 4e génération-----
...

...
-----Résultats de la 39e génération-----
  Min:0.84
  Max:0.93
  Avg:0.9247
-----Résultats de la 40e génération-----
  Min:0.85
  Max:0.94
  Avg:0.9256
Le meilleur individu est[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Sélection du code Crossover Mutation Changement de génération Différentes définitions

Détails de chaque algorithme

Code: encodage binaire Représentant un gène avec 0 et 1

Choix: Eliteism Sélectionnez l'individu le plus pertinent

Traversée: Traversée à deux points Sélectionnez deux points aléatoires dans le cadre du gène, Remplacez les gènes entre

Mutation: remplacement Remplacez les gènes par des nombres opposés 0,1% ~ 1% au plus quelques% Convergence locale si trop faible. S'il est trop élevé, il ne convergera pas.

Génération: modèle à l'état stable Remplacez la progéniture générée par des individus moins applicables.

Réglage numérique

Longueur du gène: 100 Population d'individus avec des gènes: 100 Numéro Elite pour une solution optimale à ce moment-là: 20 Nombre de descendants issus du croisement d'élites: 40 Répartition au moment du changement de génération: gène Elite 20. Gène descendant 40. Gènes actuels autres qu'élite 40. 100 au total Taux de mutation individuel: 1% Mutation génique: 1% (taux de mutation pour un gène) Nombre de changements de génération: 40

codage

Au milieu, la méthode d'abstraction peut être ridicule ou le code peut être incohérent. Notez s'il vous plaît.

GeneticAlgorithm.py Tout d'abord, créez GeneticAlgorithm.py et créez genomClass.

GeneticAlgorithm.py


class genom:

    genom_list = None
    evaluation = None

    def __init__(self, genom_list, evaluation):
        self.genom_list = genom_list
        self.evaluation = evaluation


    def getGenom(self):
        return self.genom_list


    def getEvaluation(self):
        return self.evaluation


    def setGenom(self, genom_list):
        self.genom_list = genom_list


    def setEvaluation(self, evaluation):
        self.evaluation = evaluation

Cette classe est utilisée comme variable d'instance pour stocker des informations génétiques et des valeurs d'évaluation. Attribuez une valeur avec set et obtenez une valeur avec get.

main.py

constant

Diverses constantes

main.py


#Longueur des informations génétiques
GENOM_LENGTH = 100
#La taille de la population de gènes
MAX_GENOM_LIST = 100
#Nombre de sélections de gènes
SELECT_GENOM = 20
#Probabilité de mutation individuelle@0 dans le code publié sur GitHub.1 sur 10%Il est devenu
INDIVIDUAL_MUTATION = 0.01
#Probabilité de mutation génique@0 dans le code publié sur GitHub.1 sur 10%Il est devenu
GENOM_MUTATION = 0.01
#Nombre de générations à répéter
MAX_GENERATION = 40

Diverses fonctions

L'explication détaillée à l'intérieur de la fonction est décrite dans le commentaire.

create_genom  Générez au hasard le nombre de gènes spécifié par l'argument et renvoyez-le avec genomClass evaluation Extraire l'information génétique d'un individu et l'évaluer select Renvoie un certain nombre de populations élites spécifiées par l'argument de la population crossover Récupère deux individus de l'argument et renvoie les deux descendants générés à partir de celui-ci dans un tableau next_generation_gene_create Je changerai de génération. Créer à partir de la population actuelle, de la population élite, de la population descendante mutation Le traitement de mutation est effectué en fonction de la probabilité obtenue à partir de l'argument.

def create_genom(length):

main.py


def create_genom(length):
    """
Les informations aléatoires sur le gène du chiffre spécifié par l'argument sont générées et renvoyées dans le genomClass stocké.
    :param length:Longueur des informations génétiques
    :return:GenomClass de la population générée
    """
    genome_list = []
    for i in range(length):
        genome_list.append(random.randint(0, 1))
    return ga.genom(genome_list, 0)

def evaluation(ga):

main.py


def evaluation(ga):
    """Fonction d'évaluation. Cette fois, si tous les gènes sont 1, ce sera la solution optimale, donc
0 lorsque le nombre total est le même que le gène.00~1.Évaluer à 00
    :param ga:Classe de génom à évaluer
    :return:Renvoie la genomClass évaluée
    """
    genom_total = sum(ga.getGenom())
    return Decimal(genom_total) / Decimal(len(ga.getGenom()))

def select(ga, elite):

main.py


def select(ga, elite_length):
    """C'est une fonction de sélection. Faites une sélection élite
Après tri par ordre décroissant d'évaluation, au-dessus d'un certain niveau
    :param ga:Un tableau de genomClass pour faire des sélections
    :param elite_length:Nombre d'élites à choisir
    :return:Renvoie une certaine élite, genomClass qui a été sélectionnée
    """
    #Trier les évaluations de la population de la génération actuelle par ordre décroissant
    sort_result = sorted(ga, reverse=True, key=lambda u: u.evaluation)
    #Extraire certains sommets
    result = [sort_result.pop(0) for i in range(elite_length)]
    return result

def crossover(ga_one, ga_second):

main.py


def crossover(ga_one, ga_second):
    """C'est une fonction croisée. Effectuer un croisement en deux points.
    :param ga:Tableau de génomClasse à traverser
    :param ga_one:Premier individu
    :param ga_second:Deuxième individu
    :return:Renvoie une liste contenant deux descendants genomClass
    """
    #Générer une liste pour stocker les descendants
    genom_list = []
    #Définir les deux points à remplacer →[10:25]→ De 10 à 25
    cross_one = random.randint(0, GENOM_LENGTH)
    cross_second = random.randint(cross_one, GENOM_LENGTH)
    #Sortez le gène
    one = ga_one.getGenom()
    second = ga_second.getGenom()
    #Traverser
    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:]
    #Créer une instance genomClass et stocker ses descendants dans une liste
    genom_list.append(ga.genom(progeny_one, 0))
    genom_list.append(ga.genom(progeny_second, 0))
    return genom_list

def next_generation_gene_create(ga, ga_elite, ga_progeny):

main.py


def next_generation_gene_create(ga, ga_elite, ga_progeny):
    """
Effectuer le traitement des changements de génération
    :param ga:Population de la génération actuelle
    :param ga_elite:Groupe élite de la génération actuelle
    :param ga_progeny:Groupe descendant de la génération actuelle
    :return:Population de la prochaine génération
    """
    #Trier les évaluations de la population de la génération actuelle par ordre croissant
    next_generation_geno = sorted(ga, reverse=False, key=lambda u: u.evaluation)
    #Supprimer le total du groupe élite et du groupe descendant à ajouter
    for i in range(0, len(ga_elite) + len(ga_progeny)):
        next_generation_geno.pop(0)
    #Ajouter des groupes d'élite et de descendants à la prochaine génération
    next_generation_geno.extend(ga_elite)
    next_generation_geno.extend(ga_progeny)
    return next_generation_geno

def mutation(ga, individual_mutation, genom_mutation):

main.py


def mutation(ga, individual_mutation, genom_mutation):
    """C'est une fonction de mutation.
    :param ga:Classe génomique à muter
    :param individual_mutation:Probabilité de mutation pour la fixation
    :param genom_mutation:Probabilité de mutation pour chaque gène
    :return:Renvoie une genomClass mutée"""
    ga_list = []
    for i in ga:
        #La mutation se produit avec une certaine probabilité pour un individu
        if individual_mutation > (random.randint(0, 100) / Decimal(100)):
            genom_list = []
            for i_ in i.getGenom():
                #Des mutations se produisent pour chaque information génétique individuelle
                if genom_mutation > (random.randint(0, 100) / Decimal(100)):
                    genom_list.append(random.randint(0, 1))
                else:
                    genom_list.append(i_)
            i.setGenom(genom_list)
            ga_list.append(i)
        else:
            ga_list.append(i)
    return ga_list

if name == 'main':

main.py



if __name__ == '__main__':

    #Génère la toute première population de la génération actuelle.
    current_generation_individual_group = []
    for i in range(MAX_GENOM_LIST):
        current_generation_individual_group.append(create_genom(GENOM_LENGTH))

    for count_ in range(1, MAX_GENERATION + 1):
        #Évaluer les gènes de la population de la génération actuelle et les attribuer à genomClass
        for i in range(MAX_GENOM_LIST):
            evaluation_result = evaluation(current_generation_individual_group[i])
            current_generation_individual_group[i].setEvaluation(evaluation_result)
        #Sélectionnez un individu élite
        elite_genes = select(current_generation_individual_group,SELECT_GENOM)
        #Croisez les gènes d'élite et stockez dans la liste
        progeny_gene = []
        for i in range(0, SELECT_GENOM):
            progeny_gene.extend(crossover(elite_genes[i - 1], elite_genes[i]))
        #Créer la population de la prochaine génération à partir de la génération actuelle, de la population d'élite et de la population descendante
        next_generation_individual_group = next_generation_gene_create(current_generation_individual_group,
                                                                       elite_genes, progeny_gene)
        #Mettre en sourdine tous les individus de la population de prochaine génération
        next_generation_individual_group = mutation(next_generation_individual_group,INDIVIDUAL_MUTATION,GENOM_MUTATION)

        #Le calcul évolutif d'une génération est terminé. Passer à l'évaluation

        #Organisez l'applicabilité de chaque individu.
        fits = [i.getEvaluation() for i in current_generation_individual_group]

        #Évaluer les résultats évolutifs
        min_ = min(fits)
        max_ = max(fits)
        avg_ = sum(fits) / Decimal(len(fits))

        #Sort les résultats d'évolution de la génération actuelle
        print "-----Non.{}Résultats générationnels-----".format(count_)
        print "  Min:{}".format(min_)
        print "  Max:{}".format(max_)
        print "  Avg:{}".format(avg_)

        #Échangez la génération actuelle avec la prochaine génération
        current_generation_individual_group = next_generation_individual_group

    #Sortie du résultat final
    print "Le meilleur individu est{}".format(elite_genes[0].getGenom())

Résultat d'exécution

-----Résultats de 1ère génération-----
  Min:0.36
  Max:0.63
  Avg:0.4999
-----Résultats de 2e génération-----
  Min:0.46
  Max:0.65
  Avg:0.5653
-----Résultats de 3e génération-----
  Min:0.54
  Max:0.67
  Avg:0.6098
-----Résultats de 4e génération-----
...

...
-----Résultats de la 39e génération-----
  Min:0.84
  Max:0.93
  Avg:0.9247
-----Résultats de la 40e génération-----
  Min:0.85
  Max:0.94
  Avg:0.9256
Le meilleur individu est[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

L'applicabilité maximale du premier individu est de 0,63, mais la solution peut être approchée à 0,94 à la fin. Bref, j'ai pu faire passer le nombre de 1 de 63/100 dans un premier temps à 94/100. Si vous l'exécutez plusieurs fois, vous pouvez passer à 100

Essayons réellement

Vous pouvez copier et coller ce qui précède, mais c'est un problème, alors apportez-le de Git. Clonons-le depuis GitHub et exécutons-le.

$ git clone https://github.com/Azunyan1111/OneMax.git
>>Cloning into 'OneMax'...
>>remote: Counting objects: 5, done.
>>remote: Compressing objects: 100% (4/4), done.
>>remote: Total 5 (delta 0), reused 5 (delta 0), pack-reused 0
>>Unpacking objects: 100% (5/5), done.

$ pwd
>>/Users/admin/Desktop

$ cd OneMax/

$ pwd
>>/Users/admin/Desktop/OneMax

$ ls
>>GeneticAlgorithm.py	README.md		main.py

$ python main.py 

Le traitement commence par l'exécution de main.py

Ici aussi

Introduction à la pratique du grattage Web Python Collection de techniques de scraping Web Python "Aucune valeur ne peut être obtenue" Prise en charge de JavaScript [10 000 requêtes par seconde!?] Scrapage Web explosif à partir du langage Go [Golang]

Recommended Posts

[Pour les débutants] Re: Algorithme génétique partant de zéro [Intelligence artificielle]
Algorithme Dikstra pour les débutants
[Tweepy] Re: Développement de Twitter Bot à partir de zéro # 1 [python]
Analyse ChIP-seq à partir de zéro
Re: Durée de vie de la programmation compétitive à partir de zéro Chapitre 1.3 "Side tea"
Re: Vie de programmation compétitive à partir de zéro Pour que les débutants puissent obtenir des performances encore un peu plus élevées ~ ABC154 ~ 156 avec impressions ~
Créer une intelligence artificielle par apprentissage automatique à l'aide de TensorFlow à partir de zéro connaissance - Introduction 1
Re: Vie de programmation compétitive à partir de zéro Chapitre 1.2 "Python of tears"
Objet: Vie de programmation compétitive à partir de zéro Chapitre 1 1 "Seul C ++ peut être utilisé"