Skip to content

Instantly share code, notes, and snippets.

@keon

keon/differential-evolution.ipynb

Created January 10, 2018 09:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save keon/42b058b5b320c4090e310b7a8288a955 to your computer and use it in GitHub Desktop.
Save keon/42b058b5b320c4090e310b7a8288a955 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
differential-evolution.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Differential Evolution (DE)\n",
"\n",
"* Subset of Evolutionary Algorithms (which includes Genetic Algo, Evolutionary Strategies and Evolutionary Programming)\n",
"* stochastic, population-based optimization algorithm\n",
"* Introduced by Storn and Price in 1996\n",
"* Developed to optimize real parameter, real valued functions\n",
"\n",
"*the minimization is to find*:\n",
"$$\n",
"x^* \\in X \\text{ such that } f(x^*) \\le f(x) \\, \\forall x \\in X\n",
"$$\n",
"\n",
"## Why DE?\n",
"\n",
"many practical problems have objective functions that are non-differentiable, non-continuous, non-linear, noisy, flat, multi-dimensional or have many local minima, constraints or stochasticity.\n",
"\n",
"DE can be used to find approximate solutions to such problems.\n",
"\n",
"As a part of the evolutionary algorithm family, it follows the cycle below:\n",
"\n",
"Initialization -> Mutation -> Recombination(crossover) -> Selection -> Mutation -> ..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Initialization\n",
"\n",
"Suppose we want to optimize a function with D real parameters.\n",
"\n",
"\n",
"We inittialize by randomly selecting parameter values in the defined lower and upper bounds"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"populrion: [3, 2, 3, 9, 9, 1, 9, 9, 0, 1]\n",
"population-size: 10\n"
]
}
],
"source": [
"import numpy as np\n",
"\n",
"N = 10 # number of population\n",
"pop = [np.random.randint(N) for _ in range(N)] # population\n",
"pop_size = len(pop) \n",
"\n",
"print(\"populrion:\", pop)\n",
"print(\"population-size:\", pop_size)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"def random_unique(length, count, include=[], exclude=[]):\n",
" indices = list(include)\n",
" while len(indices) < count:\n",
" next = np.random.randint(length)\n",
" while next in indices or next in exclude:\n",
" next = np.random.randint(length)\n",
" indices.append(next)\n",
" return indices"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[4, 5, 8, 1, 7, 2, 0, 9, 3]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"random_unique(10, 9)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Mutation\n",
"\n",
"For a given parameter vector $x_i$, randomly select 3 vectors $x_1$, $x_2$, $x_3$.\n",
"\n",
"Add weighted difference of the two vectors to the third\n",
"\n",
"$$\n",
"v_i = x_1 + F(x_2, x_3)\n",
"$$\n",
"\n",
"The mutation factor F is a constant from [0, 2]\n",
"\n",
"$v_i$ is called muntants. (aka donor vectors)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def mutate(pop, costs, F):\n",
" pop = np.array(pop, copy=False)\n",
" costs = np.array(costs, copy=False)\n",
" pop_size = len(pop)\n",
" de_idx = lambda count: np.array([random_unique(pop_size, count, exclude=[i])\n",
" for i in range(pop_size)])\n",
" \n",
" # Could be more methods... but \n",
" parents = pop[de_idx(3)]\n",
" return parents[:,0] + F * (parents[:,1] - parents[:,2])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Crossover (Recombination)\n",
"\n",
"Incorporates successful solutions from the previous generation.\n",
"\n",
"Trial vector is created from the combination of elements of the original population and mutants.\n",
"\n",
"Elements of mutants enter the trial vector with probability C (50% here)."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"def crossover(pop, mutant, C):\n",
" # mutant enters the trial victor with probability C\n",
" pop = np.array(pop, copy=False)\n",
" mask = np.random.random_sample(mutant.shape) < C\n",
" return np.where(mask, mutant, pop)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Select\n",
"\n",
"original population is compared with the trial vector and the one with the lowest value is admitted to the next generation."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"def select(objective, pop, pop_costs, trial, stochastic=False):\n",
" \"\"\"\n",
" objective: function\n",
" pop: original population\n",
" costs: original population costs\n",
" trial_pop: trial population\n",
" \"\"\"\n",
" pop = np.array(pop, copy=False)\n",
" pop_costs = np.array(pop_costs, copy=False)\n",
" \n",
" # objective function is evaluated for each trial vector\n",
" trial_costs = np.array(list(map(objective, trial)))\n",
" \n",
" # storn-price selection method\n",
" mask = pop_costs < trial_costs\n",
" new_pop_costs = np.where(mask, pop_costs, trial_costs)\n",
" new_pop = np.where(mask, pop, trial)\n",
" if stochastic:\n",
" new_costs = np.array(list(map(objective, new_pop)))\n",
" return new_pop, new_pop_costs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Minimization\n",
"\n",
"Mutation, crossover, and selection continue until some stopping criterion is reached."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def minimize(objective, pop, F, C, max_iter):\n",
" costs = list(map(objective, pop))\n",
"\n",
" for i in range(max_iter):\n",
" mutants = mutate(pop, costs, F)\n",
" trial = crossover(pop, mutants, C)\n",
" pop, costs = select(objective, pop, costs, trial)\n",
" print(pop)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Demo\n",
"\n",
"for this demo let's try a simple objective function of $(x-1.5)^2 $.\n",
"\n",
"the result should converge to 1.5"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"def objective(trial_pop):\n",
" return ((trial_pop-1.5) ** 2)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[ 2. 2. 3. 1. 9. 1. 9. 9. 0. 1.]\n",
"[ 2. 2. 3. 1. 9. 1. 1.5 9. 0. 1. ]\n",
"[ 2. 2. 3. 1. 1. 1. 1.5 2.5 0. 1. ]\n",
"[ 1.75 2. 3. 1. 1. 1.75 1.5 2.5 0. 1.25]\n",
"[ 1.75 2. 3. 1. 1. 1.5 1.5 0.75 0. 1.25]\n",
"[ 1.75 2. 1.875 1. 1. 1.5 1.5 0.75 0. 1.25 ]\n",
"[ 1.75 2. 1.875 1. 1.75 1.5 1.5 0.75 0. 1.375]\n",
"[ 1.75 2. 1.875 1. 1.75 1.5 1.5 0.75 1.1875\n",
" 1.375 ]\n",
"[ 1.75 2. 1.71875 1.875 1.75 1.5 1.5 1.875\n",
" 1.1875 1.375 ]\n",
"[ 1.75 1.421875 1.3125 1.78125 1.5 1.5 1.5 1.875\n",
" 1.1875 1.375 ]\n",
"[ 1.75 1.421875 1.3125 1.78125 1.5 1.5 1.5 1.875\n",
" 1.1875 1.375 ]\n",
"[ 1.4453125 1.421875 1.375 1.78125 1.5 1.5 1.5\n",
" 1.21875 1.1875 1.375 ]\n",
"[ 1.4453125 1.421875 1.375 1.78125 1.5 1.5 1.5\n",
" 1.21875 1.1875 1.375 ]\n",
"[ 1.4453125 1.421875 1.375 1.78125 1.5 1.5 1.5\n",
" 1.21875 1.3984375 1.375 ]\n",
"[ 1.4453125 1.421875 1.375 1.42578125 1.5 1.5 1.5\n",
" 1.21875 1.3984375 1.375 ]\n",
"[ 1.4453125 1.421875 1.375 1.51171875 1.5 1.5 1.5\n",
" 1.21875 1.3984375 1.375 ]\n",
"[ 1.45507812 1.421875 1.375 1.51171875 1.5 1.5 1.5\n",
" 1.21875 1.4609375 1.4375 ]\n",
"[ 1.45507812 1.421875 1.375 1.51171875 1.5 1.5 1.5\n",
" 1.47167969 1.5 1.4375 ]\n",
"[ 1.45507812 1.5 1.375 1.51171875 1.5 1.5 1.5\n",
" 1.47167969 1.5 1.4375 ]\n",
"[ 1.45507812 1.5 1.46875 1.51171875 1.5 1.5 1.5\n",
" 1.49121094 1.5 1.4375 ]\n",
"[ 1.45507812 1.5 1.53125 1.51171875 1.5 1.5 1.5\n",
" 1.49121094 1.5 1.51171875]\n",
"[ 1.45507812 1.5 1.51025391 1.51171875 1.5 1.5 1.5\n",
" 1.49121094 1.5 1.51171875]\n",
"[ 1.45507812 1.5 1.5 1.51171875 1.5 1.5 1.5\n",
" 1.49121094 1.5 1.51171875]\n",
"[ 1.49414062 1.5 1.5 1.51171875 1.5 1.5 1.5\n",
" 1.49121094 1.5 1.49560547]\n",
"[ 1.49414062 1.5 1.5 1.51171875 1.5 1.5 1.5\n",
" 1.5 1.5 1.49560547]\n",
"[ 1.5 1.5 1.5 1.51171875 1.5 1.5 1.5\n",
" 1.5 1.5 1.49560547]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5\n",
" 1.5 1.5 1.49560547]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n",
"[ 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]\n"
]
}
],
"source": [
"\n",
"minimize(objective, pop, F=0.5, C=0.5, max_iter=50)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment