Introduction to Artificial Intelligence with Python 2 "Genetic Algorithm-Practice-"

Preface

Since we will start from practice here, please refer to "Genetic Algorithm-Theory-" first.

let's try it

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.

ONEMAX problem

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.

code

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

Outline

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! !!

Task

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.

Summary

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

Introduction to Artificial Intelligence with Python 2 "Genetic Algorithm-Practice-"
Introduction to Python Image Inflating Image inflating with ImageDataGenerator
[Introduction to Python] Let's use foreach with Python
[Python] Introduction to CNN with Pytorch MNIST
The first artificial intelligence. Challenge web output with python. ~ Flask introduction
Markov Chain Chatbot with Python + Janome (1) Introduction to Janome
Markov Chain Chatbot with Python + Janome (2) Introduction to Markov Chain
Introduction to Tornado (1): Python web framework started with Tornado
Introduction to Python language
Introduction to OpenCV (python)-(2)
Introduction to formation flight with Tello edu (Python)
Introduction to Python with Atom (on the way)
Introduction to Generalized Linear Models (GLM) with Python
[Introduction to Udemy Python3 + Application] 9. First, print with print
[Introduction to Python] How to iterate with the range function?
Playing with a user-local artificial intelligence API in Python
[Chapter 5] Introduction to Python with 100 knocks of language processing
An introduction to Python distributed parallel processing with Ray
Introduction to Mathematics Starting with Python Study Memo Vol.1
Reading Note: An Introduction to Data Analysis with Python
I tried to implement an artificial perceptron with python
[Chapter 3] Introduction to Python with 100 knocks of language processing
[Chapter 2] Introduction to Python with 100 knocks of language processing
[Chapter 4] Introduction to Python with 100 knocks of language processing
Connect to BigQuery with Python
Introduction to Python Django (2) Win
Predict candlesticks with artificial intelligence
Connect to Wikipedia with Python
Post to slack with Python 3
Introduction to RDB with sqlalchemy Ⅰ
Introduction to serial communication [Python]
Switch python to 2.7 with alternatives
Write to csv with Python
[Introduction to Python] <list> [edit: 2020/02/22]
Introduction to Python (Python version APG4b)
An introduction to Python Programming
Introduction to Python For, While
Python sample to learn XOR with genetic algorithm with neural network
Introduction to her made with Python ~ Tinder automation project ~ Episode 6
20200329_Introduction to Data Analysis with Python Second Edition Personal Summary
Introduction to her made with Python ~ Tinder automation project ~ Episode 5
Introduction to Python for VBA users-Calling Python from Excel with xlwings-
[Raspi4; Introduction to Sound] Stable recording of sound input with python ♪
[Introduction to Python] How to get data with the listdir function
[Introduction to Udemy Python3 + Application] 51. Be careful with default arguments
[Introduction to Udemy Python 3 + Application] 58. Lambda
[Introduction to Udemy Python 3 + Application] 31. Comments
Python: How to use async with
Link to get started with python
Introduction to Python Numerical Library NumPy
Practice! !! Introduction to Python (Type Hints)
[Introduction to Python3 Day 1] Programming and Python
[Python] Write to csv file with Python
Create folders from '01' to '12' with python
Nice to meet you with python
[Introduction to Python] <numpy ndarray> [edit: 2020/02/22]
[Introduction to Udemy Python 3 + Application] 57. Decorator
Try to operate Facebook with Python
Introduction to Python Hands On Part 1
[Introduction to Python3 Day 13] Chapter 7 Strings (7.1-7.1.1.1)
Output to csv file with Python