The target audience for this article is
・ I know about artificial intelligence, but I don't understand it. ・ Isn't artificial intelligence so valuable in the first place? ・ I thought I'd do it, but after seeing the formula, I withered and quit. ・ I want to do artificial intelligence, but I don't know what to do ・ Artificial intelligence sources are too wasteful to read
It is aimed at people like.
Although the genetic algorithm is defined as part of artificial intelligence, From my point of view, it feels like I'm writing a binary search algorithm. Since the genetic algorithm is also an algorithm, it is easy to implement if you understand the concept.
This article is practical and is not intended for anyone who does not know the genetic algorithm in the first place. But don't worry. It's OK if you read all the God slides below and understand them about. (This slide is a super-efficient way to learn genetic algorithms at the divine level. Sell it as a book) Getting started with the Genetic Algorithm!
How much you should understand is OK if you can roughly understand the following Also, the words you don't understand are basically written on the slides.
1 Determine the sign that expresses the solution 2 Create N random current gene individuals 3 Variable generation to store the next-generation gene population 4 Evaluation calculation of the current gene using the evaluation function 5 Select two genes from the current generation 6 Cross the selected genes to generate offspring 7 Mutate the generated offspring 8 Repeat 5-6 up to N next-generation individuals 9 Transfer the next-generation group to the current generation and repeat until it converges 10 Output the most highly rated gene
Then I will enter immediately
In this article, we will solve the OneMax problem using a genetic algorithm (GA). Also, this time we will not use an external library for GA. You don't use a library when you do a binary search, right? The import to use is shown below
・ Decimal to eliminate calculation error as much as possible Random to get a random value -Class that stores gene information and the evaluation value of the gene for easy calculation. Genetic Algorithm (Make it yourself first)
The Genetic Algorithm is created because the author of this article likes Java-like coding. (Alternative method is OK)
list = [0,1,0,0,0,1,0,0,0,1,0,1,1,0,1] Randomly arranged arrays like Evolutionary Computation (GA) list = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] It is a problem to bring all array values close to 1.
The goal is to get the same results as below. 1 is the optimal solution. The minimum value and maximum value average value of the evaluation values of various generations are output.
-----1st generation results-----
Min:0.36
Max:0.63
Avg:0.4999
-----2nd generation results-----
Min:0.46
Max:0.65
Avg:0.5653
-----3rd generation results-----
Min:0.54
Max:0.67
Avg:0.6098
-----4th generation results-----
...
...
-----39th generation results-----
Min:0.84
Max:0.93
Avg:0.9247
-----40th generation results-----
Min:0.85
Max:0.94
Avg:0.9256
The best individual is[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]
Details of each algorithm
Code: Binary encoding Representing a gene with 0 and 1
Choice: Elitism Select the most applicable individual
Crossing: Two-point crossing Select two random points as part of the gene, Replace the genes in between
Mutation: replacement Replace genes with opposing numbers 0.1% ~ 1% at most a few% Local convergence if too low. If it is too high, it will not converge.
Generation: Steady state model Replace the generated offspring with less applicable individuals.
Gene length: 100 Population of individuals with genes: 100 Elite number for optimal solution at that time: 20 Number of offspring produced by crossing the elite: 40 Breakdown at the time of generation change: Elite gene 20. Offspring gene 40. Current genes other than elite 40. 100 in total Individual mutation rate: 1% Gene mutation: 1% (mutation rate for one gene) Alternation of generations: 40
In the middle, the abstraction method may be ridiculous or the code may be inconsistent. Please note.
GeneticAlgorithm.py First of all, create GeneticAlgorithm.py and create 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
Gene information and evaluation value are stored using this Class as an instance variable. Assign a value with set and get the value with get.
main.py
Various constants
main.py
#Length of genetic information
GENOM_LENGTH = 100
#The size of the gene population
MAX_GENOM_LIST = 100
#Number of gene selections
SELECT_GENOM = 20
#Individual mutation probability@0 in the code posted on GitHub.1 of 10%It has become
INDIVIDUAL_MUTATION = 0.01
#Gene mutation probability@0 in the code posted on GitHub.1 of 10%It has become
GENOM_MUTATION = 0.01
#Number of generations to repeat
MAX_GENERATION = 40
The detailed explanation inside the function is described in the comment out.
create_genom Randomly generate the number of genes specified by the argument and return it with genomClass evaluation Extract genetic information from an individual and evaluate it select Returns a certain number of elite populations specified by the argument from the population crossover Get two individuals from the argument and return the two offspring generated from it in an array next_generation_gene_create Change generations. Create from the current population, elite population, and offspring population mutation Mutation processing is performed based on the probability obtained from the argument.
def create_genom(length):
main.py
def create_genom(length):
"""
Random gene information of the digit specified by the argument is generated and returned in the stored genomClass.
:param length:Length of genetic information
:return:Generated population genomClass
"""
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):
"""Evaluation function. This time, if all the genes are 1, it will be the optimum solution, so
0 when the total number is the same as the gene.00~1.Evaluate at 00
:param ga:Genom Class to evaluate
:return:Returns the evaluated genomClass
"""
genom_total = sum(ga.getGenom())
return Decimal(genom_total) / Decimal(len(ga.getGenom()))
def select(ga, elite):
main.py
def select(ga, elite_length):
"""Choice function. Make an elite selection
After sorting in descending order of evaluation, above a certain level
:param ga:An array of genomClass to make selections
:param elite_length:Number of elites to choose
:return:Returns a certain elite, genomClass, with selection processing
"""
#Sort the ratings of the current generation population in descending order
sort_result = sorted(ga, reverse=True, key=lambda u: u.evaluation)
#Extract certain tops
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):
"""It is a cross function. Perform two-point crossing.
:param ga:Array of genomClass to cross
:param ga_one:First individual
:param ga_second:Second individual
:return:Returns a list containing two offspring genomClass
"""
#Generate a list to store offspring
genom_list = []
#Set the two points to be replaced →[10:25]→ From 10 to 25
cross_one = random.randint(0, GENOM_LENGTH)
cross_second = random.randint(cross_one, GENOM_LENGTH)
#Extract the gene
one = ga_one.getGenom()
second = ga_second.getGenom()
#Cross
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:]
#Create a genomClass instance and store offspring in a list
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):
"""
Performs generation change processing
:param ga:Current generation population
:param ga_elite:Current generation elite group
:param ga_progeny:Current generation offspring group
:return:Next-generation population
"""
#Sort the ratings of the current generation population in ascending order
next_generation_geno = sorted(ga, reverse=False, key=lambda u: u.evaluation)
#Remove the sum of the elite and offspring populations you add
for i in range(0, len(ga_elite) + len(ga_progeny)):
next_generation_geno.pop(0)
#Add elite and offspring groups to the next generation
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):
"""Mutation function.
:param ga:Genom Class to mutate
:param individual_mutation:Mutation probability for fixation
:param genom_mutation:Mutation probability for each gene
:return:Returns a mutated genomClass"""
ga_list = []
for i in ga:
#Mutation occurs with a certain probability for an individual
if individual_mutation > (random.randint(0, 100) / Decimal(100)):
genom_list = []
for i_ in i.getGenom():
#Mutations occur in each individual genetic information
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__':
#Generates the very first current generation population.
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):
#Evaluate genes in the current generation population and assign them to genomClass
for i in range(MAX_GENOM_LIST):
evaluation_result = evaluation(current_generation_individual_group[i])
current_generation_individual_group[i].setEvaluation(evaluation_result)
#Select an elite individual
elite_genes = select(current_generation_individual_group,SELECT_GENOM)
#Cross the elite genes and store them in the list
progeny_gene = []
for i in range(0, SELECT_GENOM):
progeny_gene.extend(crossover(elite_genes[i - 1], elite_genes[i]))
#Create next-generation populations from current generations, elite populations, and offspring populations
next_generation_individual_group = next_generation_gene_create(current_generation_individual_group,
elite_genes, progeny_gene)
#Mutate all individuals in the next-generation population.
next_generation_individual_group = mutation(next_generation_individual_group,INDIVIDUAL_MUTATION,GENOM_MUTATION)
#Evolutionary computation of one generation is completed. Move on to evaluation
#Arrange the applicability of each individual.
fits = [i.getEvaluation() for i in current_generation_individual_group]
#Evaluate evolutionary results
min_ = min(fits)
max_ = max(fits)
avg_ = sum(fits) / Decimal(len(fits))
#Outputs the evolution results of the current generation
print "-----No.{}Generational results-----".format(count_)
print " Min:{}".format(min_)
print " Max:{}".format(max_)
print " Avg:{}".format(avg_)
#Swap the current generation with the next generation
current_generation_individual_group = next_generation_individual_group
#Final result output
print "The best individual is{}".format(elite_genes[0].getGenom())
-----1st generation results-----
Min:0.36
Max:0.63
Avg:0.4999
-----Second generation results-----
Min:0.46
Max:0.65
Avg:0.5653
-----3rd generation results-----
Min:0.54
Max:0.67
Avg:0.6098
-----4th generation results-----
...
...
-----39th generation results-----
Min:0.84
Max:0.93
Avg:0.9247
-----40th generation results-----
Min:0.85
Max:0.94
Avg:0.9256
The best individual is[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]
The maximum applicability of the first individual is 0.63, but the solution can be approached to 0.94 at the end. In short, I was able to bring the number of 1s from 63/100 at first to 94/100. If you run it several times, you may go to 100
You can do it by copying the above, but it's a hassle so let's bring it from Git Let's clone from GitHub and execute it.
$ 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
Processing starts by executing main.py
Introduction to Python Web Scraping Practice Python Web scraping technique collection "There is no value that cannot be obtained" JavaScript support [10,000 requests per second !?] Explosive web scraping starting with Go language [Golang]
Recommended Posts