preface

Need to use genetic algorithm to optimize some things recently, was originally intended to some algorithm based on the realization of a simple function to optimize, but write a late run function general feel pure improved operator or someone else will be difficult to use, and genetic algorithm of basic concept and operation process is relatively fixed, improvement is generally through the coding mechanism, selection strategy, Crossover mutation operator and parameter design have no great influence on the overall structure of the algorithm. So for genetic algorithms, it’s a good idea to write a relatively fixed framework and then give space for operators and parameters and so forth to test and improve on new algorithms. So I began to write a small framework of genetic algorithm gAFT, this paper introduces this framework and respectively to a one-dimensional search and two-dimensional search as an example to introduce the use of methods.

GitHub: github.com/PytLab/gaft

PyPI: pypi.python.org/pypi/gaft

At present, the framework only completed the initial version, relatively simple, built in a few basic common operators, users can according to the interface rules to achieve a custom operator and put into the framework to run. I myself will add more refinement operators and improve the framework to make it more generic as needed.

The body of the

Introduction to genetic Algorithms

Here I give a brief introduction to the basic concepts of genetic algorithm and explain the design principles of GAFT.

In simple terms, genetic algorithm uses population search technology to represent the feasible solution of a group of problems, and generates a new generation of population by applying selection, crossover, mutation and other series of genetic operations to the current population, and gradually makes the population evolve to contain the approximate global optimal solution. Here I summarize the correspondence between genetics and genetic algorithm terms:

The term

Genetic terminology Terminology for genetic algorithms
group Feasible solution set
individual Feasible solution
chromosome The code of the feasible solution
gene The components that can be decoded
Genetic form The genetic code
fitness Evaluation function value
choose Select operation
cross Crossover operation
variation mutation

Algorithm characteristics

  1. Taking the coding of decision variables as the operation object makes it possible for the optimization process to learn from the concepts in biology
  2. The objective function is directly used as the search information to determine the search direction, which belongs to the derivative – free optimization
  3. Using search information from multiple search points at the same time is an implicit parallelism
  4. Is a probabilistic search technique
  5. It has the characteristics of self-organization, self-adaptation and self-learning

Algorithm process

Gaft design principles

Due to the process of genetic algorithm is relatively fixed, we optimized algorithm basically also is in the process of coding mechanisms within the framework of the whole, operator, parameters such as modified, so at the time of writing framework, then I want to put those fixed genetic operators, fitness function as the interface, and use metaclasses, decorators and way to realize the interface of the limitation of optimization, This facilitates subsequent custom operators and fitness function customization. Finally, each part is combined together to form an engine and then the target is optimized by running genetic algorithm according to the algorithm flow.

In this way, we can get rid of the tedious process of writing genetic algorithm every time. We only need to realize our own operator and fitness function like writing plug-ins each time, and then we can put them into GAFT to test the algorithm or optimize the objective function.

GAFT file structure

In this section, I will introduce the overall structure of the framework I have implemented.

. ├ ─ ─ LICENSE ├ ─ ─ the MANIFEST. In ├ ─ ─ the README. RST ├ ─ ─ examples │ ├ ─ ─ ex01 │ └ ─ ─ ex02 ├ ─ ─ gaft │ ├ ─ ─ just set py │ ├ ─ ─ ├── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── Setup.py exercises ── Bass Exercises ─ individual_test.py Exercises ─ individual_test.py Exercises ─ Roulette_wheel_selection_test. Py └ ─ ─ uniform_crossover_test. PyCopy the code

The current file results are shown above,

  • /gaft/componentsIt defines built-in individual and population types and provides two different genetic coding methods: binary coding and real coding.
  • /gaft/plugin_interfacesAll operator definitions and the interface rules for on-the-fly analysis are in the plugin interface definition, which allows users to write their own plug-ins and put them into engine.
  • /gaft/operatorsThere are built-in genetic operators that they follow/gaft/plugin_interfacesRules, can be used as an example of writing operators. Among the operators, I have built roulette wheel selection operator, Uniform crossover operator and Flipbit mutation operator. Users can directly use the built-in operator to optimize their own problems by using Gaft.
  • /gaft/analysisInside is the built-in on-the-fly analysis plug-in, which can analyze the variables in the iterative process of genetic algorithm iteration. For example, I built the console log information output and the preservation of iteration fitness value and other plug-ins to facilitate the drawing of evolution curves.
  • /gaft/engineThis is the flow control module of the genetic algorithm, which combines all the previously defined parts together to optimize the iteration using the genetic algorithm flow.

Using GAFT

Here are two functions that I use as examples to optimize the target function using GAFT.

One dimensional search

First of all, let’s optimize a simple function with multiple local minima. Let’s use the built-in operator to find the function. Ok? f(x) = x + 10sin(5x) + 7cos(4x) ? The value range of x is $[0, 10]$

  1. Import required modules first

     from math import sin, cos

 # Import population and built-in operator correlation classes
 from gaft import GAEngine
 from gaft.components import GAIndividual
 from gaft.components import GAPopulation
 from gaft.operators import RouletteWheelSelection
 from gaft.operators import UniformCrossover
 from gaft.operators import FlipBitMutation

 Interface class for writing analysis plug-ins
 from gaft.plugin_interfaces.analysis import OnTheFlyAnalysis

 # Built-in analysis class for archive fitness functions
 from gaft.analysis.fitness_store import FitnessStoreAnalysis

 We will register the analysis plug-in with the genetic algorithm engine in two waysCopy the code

  2. Create the engine

     # Define population
 indv_template = GAIndividual(ranges=[(0.10)], encoding='binary', eps=0.001)
 population = GAPopulation(indv_template=indv_template, size=50)

 Create a genetic operator
 selection = RouletteWheelSelection()
 crossover = UniformCrossover(pc=0.8, pe=0.5)
 mutation = FlipBitMutation(pm=0.1)

 Create a genetic algorithm engine where analysis plugins and fitness functions can be passed in as parameters
 engine = GAEngine(population=population, selection=selection,
                   crossover=crossover, mutation=mutation,
                   analysis=[FitnessStoreAnalysis])Copy the code

  3. Custom fitness function

    You can register fitness functions with the engine in the form of modifiers.

     @engine.fitness_register
 def fitness(indv):
     x, = indv.variants
     return x + 10*sin(5*x) + 7*cos(4*x)Copy the code

  4. Custom on-the-fly analysis plug-in

    You can also use modifiers to register plug-ins directly with the engine at definition time

     @engine.analysis_register
 class ConsoleOutputAnalysis(OnTheFlyAnalysis):
     interval = 1

     def register_step(self, ng, population, engine):
         best_indv = population.best_indv(engine.fitness)
         msg = 'Generation: {}, best fitness: {:.3f}'.format(ng, engine.fitness(best_indv))
         engine.logger.info(msg)

     def finalize(self, population, engine):
         best_indv = population.best_indv(engine.fitness)
         x = best_indv.variants
         y = engine.fitness(best_indv)
         msg = 'Optimal solution: ({}, {})'.format(x, y)
         engine.logger.info(msg)Copy the code

  5. Ok, start running!

    We have a 100-generation population here.

     if '__main__' == __name__:
     # Run the GA engine.
     engine.run(ng=100)Copy the code

The built-in analysis plug-in records the best individuals of each generation in each iteration and generates data for preservation.

Draw the curve of the function itself and the evolution curve we obtained using the genetic algorithm:

Optimization process animation:

A two-dimensional search

Now we use the GAFT built-in operator to search for binary functions that also have multiple extreme points. Ok? f(x) = ysin(2\pi x) + xcos(2\pi y) ?

$[-2, 2]$

Instead of customizing the analysis plug-in, we’ll use the built-in analysis classes and pass them in when we build the engine.

'''
Find the global maximum for binary function: f(x) = y*sim(2*pi*x) + x*cos(2*pi*y)
'''

from math import sin, cos, pi

from gaft import GAEngine
from gaft.components import GAIndividual
from gaft.components import GAPopulation
from gaft.operators import RouletteWheelSelection
from gaft.operators import UniformCrossover
from gaft.operators import FlipBitMutation

# Built-in best fitness analysis.
from gaft.analysis.fitness_store import FitnessStoreAnalysis
from gaft.analysis.console_output import ConsoleOutputAnalysis

# Define population.
indv_template = GAIndividual(ranges=[(2 -.2), (2 -.2)], encoding='binary', eps=0.001)
population = GAPopulation(indv_template=indv_template, size=50)

# Create genetic operators.
selection = RouletteWheelSelection()
crossover = UniformCrossover(pc=0.8, pe=0.5)
mutation = FlipBitMutation(pm=0.1)

# Create genetic algorithm engine.
# Here we pass all built-in analysis to engine constructor.
engine = GAEngine(population=population, selection=selection,
                  crossover=crossover, mutation=mutation,
                  analysis=[ConsoleOutputAnalysis, FitnessStoreAnalysis])

# Define fitness function.
@engine.fitness_register
def fitness(indv):
    x, y = indv.variants
    return y*sin(2*pi*x) + x*cos(2*pi*y)

if '__main__' == __name__:
    engine.run(ng=100)Copy the code

Evolution curve:

Two-dimensional functional surface:

Search process animation:

It can be seen that the built-in basic operator can find the best advantage of the function in the example.

conclusion

This paper mainly introduces a Python framework developed by me for genetic algorithm optimization calculation. The framework has built-in components commonly used in genetic algorithm, including individuals, populations, and genetic operators with different coding methods. At the same time, the framework also provides the interface of user-defined genetic operator and analysis plug-in, which can facilitate the rapid construction of genetic algorithm flow and used for algorithm testing.

At present, the framework is only in the preliminary stage, and more built-in operators will be gradually improved in the process of their own use to make the framework more universal. Both optimization examples in this article can be found on GitHub (github.com/PytLab/gaft…).

Current plans: 1. Add more built-in operators; 2. Add C++ backend to built-in operators and components. 3. The parallelization

reference

  • Intelligent Optimization Algorithms and MATLAB Examples
  • MATLAB Optimization Calculation