项目作者: ccssmnn

项目描述 :
Metaheuristics / Blackbox Optimization Algorithms for Go: Simulated Annealing, Genetic Algorithm, Ant Colony Optimization, Tabu Search, Particle Swarm Optimization ...
高级语言: Go
项目地址: git://github.com/ccssmnn/hego.git
创建时间: 2020-12-23T19:03:18Z
项目社区:https://github.com/ccssmnn/hego

开源协议:MIT License

下载


Gitpod ready-to-code stability-unstable codecov License: MIT Go Report Card Go Reference

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:

  1. package main
  2. import (
  3. "fmt"
  4. "math"
  5. "github.com/ccssmnn/hego"
  6. "github.com/ccssmnn/hego/mutate"
  7. )
  8. func rastringin(x, y float64) float64 {
  9. return 10*2 + (x*x - 10*math.Cos(2*math.Pi*x)) + (y*y - 10*math.Cos(2*math.Pi*y))
  10. }
  11. // state is a two element vector, it will implement the State interface for Simulated Annealing
  12. type state []float64
  13. // Neighbor produces another state by adding gaussian noise to the current state
  14. func (s state) Neighbor() hego.AnnealingState {
  15. return state(mutate.Gauss(s, 0.3))
  16. }
  17. // Energy returns the energy of the current state. Lower is better
  18. func (s state) Energy() float64 {
  19. return rastringin(s[0], s[1])
  20. }
  21. func main() {
  22. initialState := state{5.0, 5.0}
  23. settings := hego.SASettings{}
  24. settings.MaxIterations = 100000
  25. settings.Verbose = 10000
  26. settings.Temperature = 10.0 // choose temperature in the range of the systems energy
  27. settings.AnnealingFactor = 0.9999 // decrementing the temperature leads to convergence, we want to reach convergence when approaching the end of iterations
  28. // start simulated annealing algorithm
  29. result, err := hego.SA(initialState, settings)
  30. if err != nil {
  31. fmt.Printf("Got error while running Anneal: %v", err)
  32. }
  33. finalState := result.State
  34. finalEnergy := result.Energy
  35. fmt.Printf("Finished Simulated Annealing in %v! Result: %v, Value: %v \n", result.Runtime, finalState, finalEnergy)
  36. }

It logs:

  1. Iteration Temperature Energy
  2. 0 9.999 50
  3. 10000 3.6782426032832705 3.0986994133146712
  4. 20000 1.3530821730781113 4.227542078387473
  5. 30000 0.497746224098313 2.336322174938326
  6. 40000 0.1831014468548652 0.30639618340376096
  7. 50000 0.06735588984342127 0.03177535766328887
  8. 60000 0.024777608121224735 0.02194743246350228
  9. 70000 0.009114716851579779 0.0030078958948340784
  10. 80000 0.003352949278962375 0.012710941747947402
  11. 90000 0.0012334194303957732 0.004538678651899275
  12. 99999 0.0004537723395901116 0.0008388313144696014
  13. Done after 108.647155ms!
  14. 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