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.
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
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)
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.
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]
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.
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
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
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
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é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
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
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