# goanneal

package module
Version: v0.0.0-...-f40f182 Latest Latest

Go to latest
Published: Oct 10, 2017 License: MIT

### goanneal

Work in progress.

#### Introduction

goanneal is a Go package for Simulated Annealing Optimization.

This package is totally inspired by a python module, simanneal.

#### Usage

1. Create a problem which you want to solve by implementing `State` interface.

``````type State interface {
Copy() interface{} // Returns an address of an exact copy of the current state
Move()             // Move to a different state
Energy() float64   // Return the energy of the current state
}
``````

In general, Egergy() represents an objective function to minimize.

2. Get a new `Annealer` object by calling `NewAnnealer(State)`.

3. `Annealer`'s fields, which are annealing parameters, can be changed.

4. Execute annealing by calling `Annealer.Anneal()`.

Then you'll get an approximate solution.

#### Example: Travelling Salesman Problem (TSP)

The quintessential discrete optimization problem is the travelling salesman problem.

Please refer to examples/salesman to see full code.

##### 0. Install
``````go get github.com/matsulib/goanneal
``````
##### 1. Implement `State` interface as `TravelState`
``````import (
"math/rand"

"github.com/matsulib/goanneal"
)

var distanceMatrix map[string]DMap

type TravelState struct {
state []string
}

// Returns an address of an exact copy of the receiver's state
func (self *TravelState) Copy() interface{} {
copiedState := make([]string, len(self.state))
copy(copiedState, self.state)
return &TravelState{state: copiedState}
}

// Swaps two cities in the route.
func (self *TravelState) Move() {
a := rand.Intn(len(self.state))
b := rand.Intn(len(self.state))
self.state[a], self.state[b] = self.state[b], self.state[a]
}

// Calculates the length of the route.
func (self *TravelState) Energy() float64 {
e := 0.0
for i := 0; i < len(self.state); i++ {
if i == 0 {
e += distanceMatrix[self.state[len(self.state)-1]][self.state[0]]
} else {
e += distanceMatrix[self.state[i-1]][self.state[i]]
}
}
return e
}
``````
##### 2. Get a new `Annealer` object
``````    initialState := &TravelState{state: problem.CitiesKeys()}

tsp := goanneal.NewAnnealer(initialState)
``````
##### 3. Change a parameter of the number of iterations.
``````    tsp.Steps = 100000
``````
##### 4. Execute annealing
``````    state, energy := tsp.Anneal()
``````
##### 5. Output
``````    ts := state.(*TravelState)

fmt.Println(int(energy), "mile route:")
for i := 0; i < len(ts.state); i++ {
fmt.Println("\t", ts.state[i])
}
``````

The output is as follows:

`````` Temperature        Energy    Accept   Improve     Elapsed   Remaining
2.50000       6845.62     6.40%     0.00%     0:00:00     0:00:00
``````
``````6845 mile route:
New York City
Baltimore
Charlotte
Jacksonville
Houston
Austin
San Antonio
Phoenix
San Diego
Los Angeles
San Jose
San Francisco
Fort Worth
Dallas
Memphis
Indianapolis
Chicago
Detroit
Columbus
``````

#### Annealing parameters

Getting the annealing algorithm to work effectively and quickly is a matter of tuning parameters. The defaults are:

``````Tmax = 25000.0  # Max (starting) temperature
Tmin = 2.5      # Min (ending) temperature
Steps = 50000   # Number of iterations
Updates = 100   # Number of updates (by default an update prints to stdout)
``````

These can vary greatly depending on your objective function and solution space.

See: simanneal

## Documentation ¶

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### type Annealer ¶

```type Annealer struct {
// parameters
Tmax    float64 // max temperature
Tmin    float64 // minimum temperature
Steps   int

// user settings
CopyStrategy string
UserExit     bool

// placeholders
State State
// contains filtered or unexported fields
}```

Annealer performs simulated annealing by calling functions to calculate energy and make moves on a state. The temperature schedule for annealing may be provided manually or estimated automatically.

#### func NewAnnealer ¶

`func NewAnnealer(initialState State) *Annealer`

NewAnnealer initializes an Annealer struct

#### func (*Annealer) Anneal ¶

`func (a *Annealer) Anneal() (interface{}, float64)`

Anneal minimizes the energy of a system by simulated annealing. Parameters state : an initial arrangement of the system Returns (state, energy): the best state and energy found.

#### func (*Annealer) Auto ¶

`func (a *Annealer) Auto(minutes float64, steps int) map[string]float64`

Auto explores the annealing landscape and estimates optimal temperature settings. Returns a dictionary suitable for the `set_schedule` method.

#### func (*Annealer) SetSchedule ¶

`func (a *Annealer) SetSchedule(schedule map[string]float64)`

SetSchedule takes the output from `auto` and sets the attributes

#### type State ¶

```type State interface {
Copy() interface{} // Returns an address of an exact copy of the current state
Move()             // Move to a different state
Energy() float64   // Return the energy of the current state
}```

State is an interface of a state of a problem. These three methods will handle the state.

## Keyboard shortcuts

 ? : This menu / : Search site f or F : Jump to t or T : Toggle theme light dark auto y or Y : Canonical URL