README
¶
Differential Evolution in Go
Introduction
The differential evolution algorithm is an optimization algorithm developed by
Storn & Price
(1997). Given
a function with a set of N parameters, the algorithm creates a set of NP
random solutions within a defined parameter space, and then uses the variation
among the parameters to mutate the existing population and find better
solutions. Although this optimization method can be slow, it can be useful to
avoid the falling into a local minimum, and it is a simple algorithm to
implement and understand.
Differential Evolution can also be adapted to Markov Chain Monte Carlo methods easily (see ter Braak 2006). This package implements differential evolution and Markov chain Monte Carlo differential evolution in the Go programming language.
Using the library
Import the library with a standard import statement.
import "github.com/devries/godevo"
Next, you need a function which takes a set of parameters as a go slice of
float64 numbers, and returns a value to be optimized as a float64. For
example, the function below is a parabola in two dimensions which takes a
slice of length 2 as input and returns the parabola value.
func parabola(vec []float64) float64 {
res := 3.0 + (vec[0]-1.0)*(vec[0]-1.0) + (vec[1]-2.0)*(vec[1]-2.0)
return res
}
The minimization process involves specifying the range of parameters available
by creating a set of minimum and maximum parameter values. In the code below I
allow the first parameter to vary between 0.0 and 2.0, and the second
parameter to vary between 0.0 and 5.0. I choose NP which is the size of the
population of samples to be 15 in the case below. I indicate if I want the
optimization function to be calculated in parallel (if the function takes a
long time to calculate this can be a good idea, but if it is relatively quick
to calculate, then the overhead of goroutines can slow the process down).
Finally, I provide the function to be optimized into the Initialize
function. I get a pointer to a Model as well as an error which will be
nil if the initialization worked.
minparams := []float64{0.0, 0.0}
maxparams := []float64{2.0, 5.0}
model, err := godevo.Initialize(minparams, maxparams, 15, false, parabola)
if err != nil {
panic(err)
}
It is possible to fine tune parameters after initialization, for example the
crossover constant CR and the weighting factor F can be modified on the
model structure. By default CR=0.1 and F=0.7.
model.CrossoverConstant = 0.4
model.WeightingFactor = 0.8
The method Step of the receiver *Model performs one iteration (one
generation) of the algorithm. Therefore to run through 50 generations of
evolution, you could do the following:
for i := 0; i < 50; i++ {
model.Step()
}
At any point you can use the Best method of *Model to get the best
solution and the fitness of that solution.
bestParameters, bestFitness := model.Best()
Markov Chain Monte Carlo
The Markov chain Monte Carlo method is very similar, but is initialized with
the InitializeMCMC function, which takes the same parameter, but sets the
optimization function to accept solutions based on the Metropolis algorithm,
and only evolves child generations directly from the corresponding parent
solution, which is required to get good statistical measurements. Generations
are evolved using the Step method, but generally you want to find the mean
value of the parameters and their standard deviations in this case. For that
you can use the MeanStd method of the *Model receiver as shown below.
meanParameters, stdevParameters := model.MeanStd()
The Markov chain Monte Carlo variant should provide a population whose distribution is a good statistical representation of the accuracy of the model.
Documentation
Detailed documentation is available through
godoc. Some examples are
included in the internal subdirectory.
Documentation
¶
Overview ¶
Package godevo is a differential evolution and Markov Chain Monte Carlo differential evolution library.
Example ¶
package main
import (
"fmt"
"math/rand"
"github.com/devries/godevo"
)
func main() {
rand.Seed(42)
minparams := []float64{0.0, 0.0}
maxparams := []float64{2.0, 5.0}
model, err := godevo.Initialize(minparams, maxparams, 15, false, parabola)
if err != nil {
panic(err)
}
model.TrialFunction = godevo.TrialPopulationSP95
model.CrossoverConstant = 0.4
model.WeightingFactor = 0.8
model.ParallelMode = false
bp, bf := model.Best()
fmt.Printf("Best Parameters: %v\n", bp)
fmt.Printf("Best Fitness: %f\n", bf)
ngen := 50
fmt.Printf("Running model of %d generations\n", ngen)
for i := 0; i < ngen; i++ {
model.Step()
}
bp, bf = model.Best()
fmt.Printf("Best Parameters: %v\n", bp)
fmt.Printf("Best Fitness: %f\n", bf)
}
func parabola(vec []float64) float64 {
res := 3.0 + (vec[0]-1.0)*(vec[0]-1.0) + (vec[1]-2.0)*(vec[1]-2.0)
return res
}
Output: Best Parameters: [1.3280218953690182 2.331018106387252] Best Fitness: 3.217171 Running model of 50 generations Best Parameters: [0.999987025007789 1.999966608737686] Best Fitness: 3.000000
Example (Mcmc) ¶
package main
import (
"fmt"
"math/rand"
"github.com/devries/godevo"
)
func main() {
rand.Seed(42)
x := make([]float64, 21)
p0 := []float64{2.0, 3.0}
for i := range x {
x[i] = 0.5 * float64(i)
}
y := make([]float64, 21)
for i := range y {
y[i] = linear(p0, x[i]) + rand.NormFloat64()*0.5
}
optimizationFunc := func(params []float64) float64 {
sumsq := 0.0
for i := range x {
sumsq += residual(params, x[i], y[i], 0.25)
}
return sumsq
}
pmin := []float64{0.0, 0.0}
pmax := []float64{10.0, 10.0}
// This is not actually efficient in parallel, but I just want to exercise that code.
model, err := godevo.InitializeMCMC(pmin, pmax, 500, true, optimizationFunc)
if err != nil {
panic(err)
}
model.WeightingFactor = 0.9
for i := 0; i < 2000; i++ {
model.Step()
}
mean, stdev := model.MeanStd()
fmt.Printf("Mean Result: %v\n", mean)
fmt.Printf("Standard Deviation: %v\n", stdev)
}
func linear(params []float64, x float64) float64 {
return params[0]*x + params[1]
}
func residual(params []float64, x, y, sigmasq float64) float64 {
yp := linear(params, x)
diff := yp - y
return diff * diff / sigmasq
}
Output: Mean Result: [1.9624802929430822 3.3155542023129514] Standard Deviation: [0.03711446105839528 0.21234935229456098]
Index ¶
- func GreedyDenial(oldFitness float64, newFitness float64) bool
- func MetropolisDenial(oldFitness float64, newFitness float64) bool
- func TrialPopulationParent(population [][]float64, f float64, cr float64) [][]float64
- func TrialPopulationSP95(population [][]float64, f float64, cr float64) [][]float64
- func TrialPopulationSP97(population [][]float64, f float64, cr float64) [][]float64
- type Model
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GreedyDenial ¶
GreedyDenial is the standard differential evolution denial function which returns True if the new fitness value is greater than the old fitness value.
func MetropolisDenial ¶
MetropolisDenial is a function which has a greater probability of returning True if the new fitness value is large compared to the old fitness value.
func TrialPopulationParent ¶
TrialPopulationParent will enerate a trial population according to Storn & Price 1997 paper, but always evolve from parent vector at same position. The population is the previous generation population of parameters. The f parameter is the weighting factor in the differential evolution algorithm. The cr parameter is the crossover constance in the differential evolution algorithm. The function returns a new trial population of parameters.
func TrialPopulationSP95 ¶
TrialPopulationSP95 will generate a trial population according to Storn & Price 1995 notes. The population is the previous generation population of parameters. The f parameter is the weighting factor in the differential evolution algorithm. The cr parameter is the crossover constance in the differential evolution algorithm. The function returns a new trial population of parameters.
func TrialPopulationSP97 ¶
TrialPopulationSP97 will generate a trial population according to Storn & Price 1997 paper. The population is the previous generation population of parameters. The f parameter is the weighting factor in the differential evolution algorithm. The cr parameter is the crossover constance in the differential evolution algorithm. The function returns a new trial population of parameters.
Types ¶
type Model ¶
type Model struct {
Population [][]float64 // The population of parameters
Fitness []float64 // The fitness of each parameter set
CrossoverConstant float64 // The crossover constant: CR
WeightingFactor float64 // The weighting factor: F
DenialFunction func(float64, float64) bool // The denial function, either GreedyDenial or MetropolisDenial
TrialFunction func([][]float64, float64, float64) [][]float64 // The trial population function, TrialPopulationSP97 for Storn & Price (1997)
ModelFunction func([]float64) float64 // The function to optimize
ParallelMode bool // Do fitness calculation in parallel
}
Model is a differential evolution model structure
func Initialize ¶
func Initialize(pmin []float64, pmax []float64, np int, parallel bool, modelFunction func([]float64) float64) (*Model, error)
Initialize returns a standard initialized differential evolution model with a population of np parameters. pmin are the minimum parameter values, and pmax are the maximum parameter values. The parallel parameter controls if the fitness function is computed in parallel or not. The function to be optimized is modelFunction.
func InitializeMCMC ¶
func InitializeMCMC(pmin []float64, pmax []float64, np int, parallel bool, modelFunction func([]float64) float64) (*Model, error)
InitializeMCMC returns an initialized Markov chain Mote Carlo differential evolution model with a population of np parameters. pmin are the minimum parameter values, and pmax are the maximum parameter values. The parallel parameter controls if the optimization function is to be run in parallel. The function to be optimized is modelFunction.
func (*Model) Best ¶
Best returns the optimal parameters, and the fitness of the optimal parameters from the model.
Source Files
Directories