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
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.
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.
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.
Here's what this auto-generated algorithm spits out to be executable in Python:
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