Algorithm generation automation using genetic algorithms

Preface

Genetic algorithms are often introduced with very simple examples such as parameter adjustment and combination optimization, but with a little ingenuity, algorithms and programs can be automatically generated.

Prerequisite knowledge

Genetic algorithm

It is a search algorithm based on the idea of evolution of living things due to mutation, heredity, selection, etc.

Genotype

A type that is the target of genetic manipulations such as mutations and crossovers.

Phenotype

It is an individual expressed from the genotype to be evaluated for fitness.

Various genetic algorithms

Genetic programming

Genotype is tree structure

Wikipedia

Genetic network programming

Genotype is network structure

Graph Structured Program Evolution (GRAPE) Genotype is a one-dimensional sequence Phenotype is graph structure

Yokohama National University Academic Information Repository

Algorithms that require loops can also be expressed, and programs that obtain factorials and Fibonacci numbers can be automatically generated with a certain probability. [Actual demo](https://qiita.com/technote-space/items/7acade8a2b768153f005#%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3% 82% BA% E3% 83% A0% E8% 87% AA% E5% 8B% 95% E7% 94% 9F% E6% 88% 90)

Target problem

I tried to solve a simple problem of OpenAI Gym, which is a simulation environment of reinforcement learning, using GRAPE.

Implementation (GitHub)

Cart Pole The problem is to move the Cart to balance it so that the Pole on top doesn't fall over. Since the initial state is somewhat random, an algorithm that can be used for general purposes is required.

The image below shows the behavior of the algorithm actually acquired. CartPole

Here's what this auto-generated algorithm spits out to be executable in Python: The implementation also automates this process. Source code Algorithm part

Mountain Car The problem is to move the car and climb the mountain on the right. Again, the initial conditions are somewhat random.

The image below shows the behavior of the algorithm actually acquired. MountainCar

Here's what this auto-generated algorithm spits out to be executable in Python:

Source code Algorithm part

Summary

The recently announced AutoML-Zero also automatically builds the algorithm itself using an evolutionary algorithm. It was a thing. In the future, it is expected that more active research will be conducted to automatically create algorithms and programming, including machine learning, completely away from human hands. We have implemented AutoML-Zero by extending GRAPE, which follows a more general genetic algorithm for individual expression and genetic manipulation, and at this point we are getting roughly the expected results. (Implementation in Python was too slow to be useful, so I reimplemented it while doing various optimizations in C ++.)

As mentioned in the introduction, genetic algorithms do more than just solve parameter optimizations and numerical combination optimizations. Evolution and learning are compatible, and I think that AutoML-Zero reproduces the relationship of maximizing the new structure obtained by evolution in learning at a practical level, and the genetic algorithm of this evolution I believe that it can be greatly utilized for the part. We hope that it will be helpful for those who are conducting research and development in this area.

Recommended Posts

Algorithm generation automation using genetic algorithms
[Python] Notes on accelerating genetic algorithms using multiprocessing
Genetic algorithm in python
Jellyfish generation detection algorithm
Search for stable structures of metal nanoclusters using genetic algorithms
Feature selection by genetic algorithm
Search algorithm using word2vec [python]
Strongest Pokemon generation using LSTM
Finding the optimum value of a function using a genetic algorithm (Part 1)