Evolutionary Algorithms implementations

Evolutionary Algorithms implementations, for various (discrete & continuous) optimization problems.

TL;DR

This repository contains implementations of the following:

Evolutionary Algorithms (EAs):

• Genetic Algorithm (GA) - with multiple choices of Selection, Crossover & Mutation strategies.
• Evolution Strategy (ES) - PEPG, OpenAI-ES, CMA-ES.

Optimization problems (of increasing difficulty):

Optimization problem	Type	Parameters number
String	Discrete-number vector	12
Rastrigin function	Real-number vector	100
Policy Neural-Network for autonomous agent control	Real-number vector	407

Note that the higher the dimensionality (parameters number) of the optimization problem, the harder it is, and the slower the optimization process is.

Table of contents:

• Intro
  • Evolutionary Algorithms
  • Optimization Problems
• Results
  • Evolutionary Algorithms Comparison
  • Genetic Algorithms Comparison
• How to use

Intro

Evolutionary Algorithms

A family of problem-independent, gradient-free, population-based, metaheuristic or stochastic, global optimization algorithms.

Inspired by the biological concept of evolution by natural selection - a population of candidate solution models follows an evolutionary process towards optimality (optimization via evolution).

Genetic Algorithm

Employs a more biologically-accurate form of evolution - utilizes a loop of parents selection, reproduction via crossover (AKA genetic recombination) and mutation.

Evolution Strategy

Employs a more mathematical (and less biologically-accurate) form of evolution - a single parent produces multiple variants of itself via cloning and mutation (a small amount of random noise). After the new population is evaluated, a single parent is created using a weighted-sum of all the individuals (AKA population averaging).

Optimization Problems

String

Optimizing a fixed-length String (discrete-valued vector) towards a chosen target String of 12 characters.

For generality purposes, the String (individual & target) is converted into a discrete-number vector (and vice-versa), which is optimized.

Rastrigin function

Optimizing the Rastrigin function's input parameters (x).

The Rastrigin function is a non-convex function (with multiple local minima), and is used as a performance-test problem for optimization algorithms. It is a typical example of non-linear multimodal function.

Policy Neural-Network for autonomous agent control

Optimizing the Policy Neural-Network's parameters (layers' weights and biases).

A Policy network receives the environment state as an input, and outputs a probability distribution over all possible actions.

Any AI Gym environment can be chosen, as long as the relevant variables parameters (env_name, input_dims, n_actions, optimal_fit) are changed accordingly. Here, AI Gym's CartPole environment is chosen as an example.

Results

optimization process results:

Evolutionary Algorithms Comparison

Legend:

Rastrigin function (100 input parameters)

Policy Neural-Network (407 parameters)

Environment: CartPole.

Neural-Network layers' units number: (Input) 4,25,10,2 (Output).

Genetic Algorithms Comparison

• Selection options:
  • fitness-proportionate selection (FPS)
  • stochastic top-sampling (STS) selection
  • tournament (Tour) selection
• Crossover options:
  • Single-point crossover(1PtCross)
  • Two-point crossover(2PtCross)
  • Uniform crossover(UniCross)
• Mutation options:
  • Deterministic mutation (DetMut)
  • Stochastic uniform mutation (StoUniMut)
  • Gaussian-noise mutation (GaussMut)

Legend:

String (12 characters)

Notice how the optimization is better with a larger population size.

Rastrigin function (100 input parameters)

Notice how the optimization is better with a higher (and constant) mutation sigma.

Sigma = 1

Sigma = 0.5

Sigma: Init = 0.5, Decay = 0.9, Min = 0.01

How to use

Examples of how to use:

• compare_EAs.py
• compare_GAs.py