Since we will start from practice here, please refer to "Genetic Algorithm-Theory-" first.
Now, let's actually run GA using Python. Here, we will proceed assuming that you already have basic knowledge of Python. Use functions, but don't use classes because the explanations are chaotic.
What exactly do you do?
A common example is the ONEMAX problem. this is, ｛1，0，0，1，0，1，1，1，0，0｝ From an array composed of "1" or "0", like ｛1，1，1，1，1，1，1，1，1，1｝ I thought about how to create an array of all 1s.
This is solved with GA. The flow is to randomly generate a sequence having "1" or "0" as an element, use this as genetic information, and build an algorithm using the total value of the sequence as an evaluation standard.
First, the whole code is shown.
GA.py
import random
from decimal import Decimal
GENOM_LENGTH = 20 #Length of genetic information
MAX_GENOM_LIST = 200 #The size of the gene population
SELECT_GENOM = 10 #Number of elite gene selections
INDIVIDUAL_MUTATION = 0.01 #Individual mutation probability
GENOM_MUTATION = 0.01 #Gene mutation probability
MAX_GENERATION = 20 #Number of generations to repeat
def genom(length):
"""
Genes are randomly generated.
The return value is the gene sequence of one individual
"""
genom_list = []
for i in range(length):
a = random.randint(0,1)
genom_list.append(a)
return genom_list
def evaluation(ga):
"""
Evaluation function of an individual.
From the gene sequence obtained by the argument, the total value is returned as the evaluation value.
"""
genom_total = sum(ga)
genom_num = len(ga)
return Decimal(genom_total) / Decimal(genom_num)
def select_elite(ga,elite_length):
"""
A function that retrieves excellent individuals.
"""
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):
"""
Cross function.
Two offspring are returned from the two parents given as arguments.
Here, it is inherited by two-point crossing.
"""
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):
"""
Generate the next generation population.
Get the previous generation group with the first argument,
The second and third arguments elite and children are added, and the less excellent individuals are removed.
"""
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):
"""
Make a mutation.
Select whether an individual mutates with a certain probability,
The gene sequence element of the caught individual is also selected with probability,
Modify the trapped element to 1 or 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 ("-----------No.{}generation----------".format(count_))
print (" Min:{}".format(min_))
print (" Max:{}".format(max_))
print (" avg:{}".format(avg_))
print("\n")
current_generation = next_generation
print ("The best individual is{}".format(elite_genes[0]))
The procedure is as shown in the previous article, Theory. In this program
** 200 individuals per generation, The length of the gene sequence per individual is 20, The number of repeating generations is 20, Mutation probability is 1% for both species, 20 elite choices, **
It is moving with the value. Of course, this value can be decided freely. Basically, the larger the number of generations, the better the individual will come out, and the longer the gene sequence, the slower the convergence speed to the optimal solution, so the number of generations and the size of the set will be increased. There is a need to. ** **
And when you do this,
-----------20th generation----------
Min:0.9
Max:1
avg:0.96875
The best individual is[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
It was output like this and solved the ONEMAX problem brilliantly! !! (Only the last few lines are listed.)
This is the power of GA! !!
Now you can understand what GA is and its power. Therefore, I would like to give a task to those who are learning using this article.
** ⑴ Create and execute the above code excluding the mutation processing. Also consider the results. ⑵ Optimal solution, ｛1,0,1,0,1,0,1,0,..........0,1｝ As such, GA is assembled as an individual in which "1" and "0" are arranged alternately. ** **
That is all.
It seems that there is an image that AI is extremely difficult to get started with. But surprisingly, the foundation is interesting and easy to imagine. In this article, you could see a glimpse of AI. All you have to do is introduce your ideas. See you next time. thank you for reading.
Recommended Posts