README
¶
hego
hego aims to provide a consistent API for several metaheuristics (black box optimization algorithms) while being performant.
Even though most of the metaheuristics might fit to any kind of optimization problem most of them have some caveats / advantages in different fields. hego allows you to rapidly try different algorithms and experiment with the parameters in order to solve your problems in the best possible time-to-quality ratio.
Algorithms
Currently the following algorithms are implemented:
- Simulated Annealing (SA)
- Genetic Algorithm (GA)
- Ant Colony Optimization (ACO)
- Tabu Search (TS)
- Evolution Strategies (ES) (continuous only)
- Particle Swarm Optimization (PSO) (continuous only)
All algorithms are implemented for finding minimum values.
Usage
hego is able to solve your optimization problems when the algorithm specific interface is implemented. This approach allows you to use hego for various problem encodings. For example integer- or boolean vectors, graphs, structs etc.
For basic vector types (int, bool and float64) helper methods implemented in the subpackages hego/crossover and hego/mutate allow you to experiment with different parameter variants of the algorithms.
Some algorithms however are only designed for specific sets of optimization problems. In these cases the algorithms provide an easier call signature that only requires the objective and the initial guess or initializer functions. (Evolution Strategies, Particle Swarm Optimization)
hego has a rich examples directory. It is ordered by problem type and shows how to apply hego's algorithms to these types of problems:
- Traveling Salesman Problem, an integer encoded permutation problem for finding the shortest path to visit all cities (wikipedia)
- Knapsack Problem, a binary encoded combinatorical optimization problem to select items to get be best value while respecting the maximum weight (wikipedia)
- Rastrigin Function, a non convex function with a large number of local minima (wikipedia)
- Nurse Scheduling Problem, a scheduling problem for assigning shifts to nurses with constraints (wikipedia)
- Vehicle Routing Problem, a combination of Knapsack and Traveling Salesman problem (wikipedia)
NOTE: The examples goal is to show how hego can be applied to these problem types. The goal ist not to show the current state of the art solution approaches. If you have improvement ideas for the examples performance, feel free to open a PR.
Example
This example uses Simulated Annealing (SA) for optimizing the Rastrigin Function:
package main
import (
"fmt"
"math"
"github.com/ccssmnn/hego"
"github.com/ccssmnn/hego/mutate"
)
func rastringin(x, y float64) float64 {
return 10*2 + (x*x - 10*math.Cos(2*math.Pi*x)) + (y*y - 10*math.Cos(2*math.Pi*y))
}
// state is a two element vector, it will implement the State interface for Simulated Annealing
type state []float64
// Neighbor produces another state by adding gaussian noise to the current state
func (s state) Neighbor() hego.AnnealingState {
return state(mutate.Gauss(s, 0.3))
}
// Energy returns the energy of the current state. Lower is better
func (s state) Energy() float64 {
return rastringin(s[0], s[1])
}
func main() {
initialState := state{5.0, 5.0}
settings := hego.SASettings{}
settings.MaxIterations = 100000
settings.Verbose = 10000
settings.Temperature = 10.0 // choose temperature in the range of the systems energy
settings.AnnealingFactor = 0.9999 // decrementing the temperature leads to convergence, we want to reach convergence when approaching the end of iterations
// start simulated annealing algorithm
result, err := hego.SA(initialState, settings)
if err != nil {
fmt.Printf("Got error while running Anneal: %v", err)
}
finalState := result.State
finalEnergy := result.Energy
fmt.Printf("Finished Simulated Annealing in %v! Result: %v, Value: %v \n", result.Runtime, finalState, finalEnergy)
}
It logs:
Iteration Temperature Energy
0 9.999 50
10000 3.6782426032832705 3.0986994133146712
20000 1.3530821730781113 4.227542078387473
30000 0.497746224098313 2.336322174938326
40000 0.1831014468548652 0.30639618340376096
50000 0.06735588984342127 0.03177535766328887
60000 0.024777608121224735 0.02194743246350228
70000 0.009114716851579779 0.0030078958948340784
80000 0.003352949278962375 0.012710941747947402
90000 0.0012334194303957732 0.004538678651899275
99999 0.0004537723395901116 0.0008388313144696014
Done after 108.647155ms!
Finished Simulated Annealing in 108.647155ms! Result: [0.0010647353926910566 -0.001759125670646859], Value: 0.0008388313144696014
Contributing
This repo is accepting PR's and welcoming issues. Feel free to contribute in any kind if
- you find any bugs
- you have ideas to make this library easier to use
- you have ideas on how to improve the performance
- you miss algorithm XY
License
The MIT License (MIT). License
Documentation
¶
Overview ¶
Package hego provides methods to blackbox optimization algorithms like Genetic Algorithm, Simulated Annealing or Ant Colony Optimization
The consistent API between algorithms and (optionally) verbose execution make finding the best algorithm and the right parameters easy and quick
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ACOResult ¶
type ACOResult struct {
// AveragePerformances holds the mean performances for each iteration
AveragePerformances []float64
// BestPerformances holds the best performance for each iteration
BestPerformances []float64
// BestAnts holds the best Ant for each iteration
BestAnts []Ant
// BestPerformance stores the overall best ants performance
BestPerformance float64
// BestAnt stores the overall best ant
BestAnt Ant
Result
}
ACOResult represents the result of the ACO
type ACOSettings ¶
type ACOSettings struct {
// Evaporation must be a value in (0, 1] and is used to reduce the amount of pheromone after each iteration
Evaporation float64
// MinPheromone is the lowest possible amount of pheromone. Convergence to the true optimum is theoretically only guaranteed for a minpheromone > 0
MinPheromone float64
Settings
}
ACOSettings represents the settings available in ACO
func (*ACOSettings) Verify ¶
func (s *ACOSettings) Verify() error
Verify checks validity of the ACOSettings and returns nil if settings are ok
type AnnealingState ¶
type AnnealingState interface {
Energy() float64
Neighbor() AnnealingState
}
AnnealingState represents the current state of the annealing system. Energy is the value of the objective function. Neighbor returns another state candidate
type Ant ¶
type Ant interface {
// Init initializes the ant for creating a new tour
Init()
// Step performs one step to the next position (encoded by int) and returns true when the tour is finished
Step(next int) bool
// PerceivePheromone returns a pheromone slice where each element represents the pheromone for the next step (encoded by position)
PerceivePheromone() []float64
// DropPheromone leaves pheromone (depending on the performance) on the path of this ant
DropPheromone(performance float64)
// Evaporate is called after one iteration and reduces the amount of pheromone on the paths
Evaporate(factor, min float64)
// Performance is the objective, lower is better
Performance() float64
}
Ant is the individuum in the population based Ant Colony Optimization (ACO)
type ESResult ¶
type ESResult struct {
Candidates [][]float64
AverageObjectives []float64
BestObjectives []float64
BestCandidate []float64
BestObjective float64
Result
}
ESResult represents the result of the evolution strategy algorithm
func ES ¶
func ES( objective func(x []float64) float64, x0 []float64, settings ESSettings) (res ESResult, err error)
ES performs Evolutionary Strategy algorithm suited for minimizing a real valued function (objective) from a starting point x0 It takes advantage of population based gradient updates, where each iteration a population is generated from noise added to the current and used to estimate the gradient.
type ESSettings ¶
type ESSettings struct {
// PopulationSize is the number of noise vectors to create for each iteration
// these noise vectors are used to create a gradient estimate, so population size should not
// be too small
PopulationSize int
// LearningRate is the factor to determine the step size after each iteration
// a step is made by calculating x = x + learningRate * gradient_estimate(x)
LearningRate float64
// NoiseSigma is the sigma value for noise generated. A higher sigma results in a wider
// search spread, but might result in inaccuracies for the gradient estimate
NoiseSigma float64
Settings
}
ESSettings represents settings for the evolution strategy algorithm
func (*ESSettings) Verify ¶
func (s *ESSettings) Verify() error
Verify checks the validity of the settings and returns nil if everything is ok
type GAResult ¶
type GAResult struct {
AveragedFitnesses []float64
BestFitnesses []float64
BestGenomes []Genome
BestGenome Genome
BestFitness float64
Result
}
GAResult represents the result of the genetic algorithm
func GA ¶
func GA( initialPopulation []Genome, settings GASettings, ) (res GAResult, err error)
GA Performs optimization. The optimization follows three steps: - for current population calculate fitness - select chromosomes with best fitness values with higher propability as parents - use parents for reproduction (crossover and mutation)
type GASettings ¶
type GASettings struct {
// Selection defines the type of selection to be used
Selection Selection
// TournamentSize defines the size of a tournament (only necessary for TournamentSelection)
TournamentSize int
// MutationRate is the probability of a candidate to mutate after crossover
MutationRate float64
// Elitism is the number of best candidates to pass over to the next generation without selection
Elitism int
Settings
}
GASettings represents the settings available in the genetic algorithm
func (*GASettings) Verify ¶
func (s *GASettings) Verify() error
Verify returns an error, if settings are not valid
type Genome ¶
type Genome interface {
// Fitness returns the objective function value for this genome
Fitness() float64
// Mutate returns a neighbor of this genome
Mutate() Genome
// Crossover merges this and another genome to procude a descendant
Crossover(other Genome) Genome
}
Genome represents a genome (candidate) in the genetic algorithm
type PSOResult ¶
type PSOResult struct {
BestParticles [][]float64
BestObjectives []float64
BestParticle []float64
BestObjective float64
Result
}
PSOResult represents the results of the particle swarm optimization
func PSO ¶
func PSO( objective func(x []float64) float64, init func() ([]float64, []float64), settings PSOSettings) (res PSOResult, err error)
PSO performs particle swarm optimization. Objective is the function to minimize, init initializes a tupe of particle and velocity, settings holds algorithm settings
type PSOSettings ¶
type PSOSettings struct {
// PopulationSize is the number of particles
PopulationSize int
// LearningRate determines the movement size of each particle
LearningRate float64
// Omega is the weight of the current velocity, a momentum
Omega float64
// GlobalWeight determines how much a particle should drift towards the global optimum
GlobalWeight float64
// ParticleWeight determines how much a particle should drift towards the best known position of this particle
ParticleWeight float64
Settings
}
PSOSettings represents settings for the particle swarm optimization
func (*PSOSettings) Verify ¶
func (s *PSOSettings) Verify() error
Verify checks the validity of the settings and returns nil if everything is ok
type Result ¶
Result represents result information of the optimization, including statistics about the run
type SAResult ¶
type SAResult struct {
// State is the result state
State AnnealingState
// Energy is the result Energy
Energy float64
// States when KeepIntermediateResults is set hold every state during the
// process (updated on state change)
States []AnnealingState
// Energies when KeepIntermediateResults is set hold the energy value of
// every state in the process
Energies []float64
Result
}
SAResult represents the result of the Anneal optimization. The last state and last energy are the final results. It extends the basic Result type
func SA ¶
func SA( initialState AnnealingState, settings SASettings, ) (res SAResult, err error)
SA performs simulated annealing algorithm
type SASettings ¶
type SASettings struct {
// Temperature is used to determine if another state will be selected or not
// better states are selected with probability 1, but worse states are selected
// propability p = exp(state_energy - candidate_energy/temperature)
// a good value for Temperature is in the range of randomly guessed state energies
Temperature float64
// AnnealingFactor is used to decrease the temperature after each iteration
// When temperature reaches 0, only better states will be accepted which leads
// to local search / convergence. Thus AnnealingFactor controls after how many
// iterations convergence might be reached. It's good to reach low temperatures
// during the last third of iterations
AnnealingFactor float64
Settings
}
SASettings represents the algorithm settings for the simulated annealing optimization
func (*SASettings) Verify ¶
func (s *SASettings) Verify() error
Verify returns an error if settings verification fails
type Selection ¶
type Selection int
Selection encodes different selection variants
const ( // RankBasedSelection selects parents based on their rank (sorted by fitness) RankBasedSelection Selection = iota // TournamentSelection performs a tournament of randomly selected genomes // and selects the winner TournamentSelection // FitnessProportionalSelection determines the chance of a genome to be // selected by its fitness value compared to the total fitness of the population FitnessProportionalSelection )
type Settings ¶
type Settings struct {
// MaxIterations is the maximum number of iterations run by the algorithm
// the algorithm will stop after this number is reached
MaxIterations int
// Verbose controls wether the algorithm should log information into the
// console. 0 means no logging, n will log every n iterations
Verbose int
// KeepHistory, when true intermediate results are stored
KeepHistory bool
}
Settings represents the settings of the optimization run
type TSResult ¶
type TSResult struct {
// States holds the best states. Last element in this list is overall best solution
States []TabuState
// Objectives holds the best objectives. Each entry corresponds to an element in States
Objectives []float64
BestState TabuState
BestObjective float64
Result
}
TSResult holds result and progress information about the tabu search algorithm
type TSSettings ¶
type TSSettings struct {
// NeighborhoodSize sets the number of neighbors created in each iteration
NeighborhoodSize int
// TabuListSize is the memory of the algorithm. Each iteration the state
// is added to the tabu list. A produced neighbor wont be selected if he appears
// in the tabu list
TabuListSize int
Settings
}
TSSettings describes the necessary settings for the tabu search algorithm
func (*TSSettings) Verify ¶
func (s *TSSettings) Verify() error
Verify returns an error if settings verification fails
type TabuState ¶
type TabuState interface {
// Objective is the function to be minimized
Objective() float64
// Equal returns true, when other state is equal to current one
Equal(other TabuState) bool
// Neighbor produces a related state for local search
Neighbor() TabuState
}
TabuState describes the state during a tabu search
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package crossover provides methods to combine two solution candidates to find another solution.
|
Package crossover provides methods to combine two solution candidates to find another solution. |
|
examples
|
|
|
Package mutate provides methods to mutate one solution candidate in order to generate neighboring solution candidates
|
Package mutate provides methods to mutate one solution candidate in order to generate neighboring solution candidates |