alns

README

ALNS in Go

This is a partial port/adaptation of the Python library N-Wouda/ALNS to the Go programming language.

The original implementation can be found here: N-Wouda/ALNS.

Overview

• Implements core components of the ALNS metaheuristic: destroy operators, repair operators, acceptance criteria, and the operator selection mechanism.
• Can be used to solve complex combinatorial optimization problems such as TSP, VRP, and others, similar to the Python version.

Import the module in your Go project:

import "github.com/bibenga/alns"

Exmaple

initSol := NewMyProblemState(...)

destroyOperators := []alns.Operator{randomRemoval, pathRemoval, worstRemoval}
repairOperators := []alns.Operator{greedyRepair}

selector, err := alns.NewRouletteWheel(
    [4]float64{3, 2, 1, 0.5},
    0.8,
    len(destroyOperators),
    len(repairOperators),
    nil,
)
if err != nil {
    ...
}
acceptor := alns.HillClimbing{}
stop := alns.MaxRuntime{MaxRuntime: 1 * time.Second}

a := alns.ALNS{
    Rnd:               rnd,
    DestroyOperators:  destroyOperators,
    RepairOperators:   repairOperators,
    Selector:          &selector,
    Acceptor:          &acceptor,
    Stop:              &stop,
    InitialSolution:   initSol,
}

if result, err := a.Iterate(); err != nil {
    ...
} else {
    // do something with result
}

Documentation

Index

• Variables
• func Compare(a, b float64) int
• func IsClose(a, b float64) bool
• type ALNS
  • func (a *ALNS) AddDestroyOperator(ops ...Operator)
  • func (a *ALNS) AddRepairOperator(ops ...Operator)
  • func (a *ALNS) Iterate() (*Result, error)
• type AcceptanceCriterion
• type Context
  • func (c *Context) IsDone(rnd *rand.Rand, best, current State) (bool, error)
• type HillClimbing
  • func (h *HillClimbing) Accept(rnd *rand.Rand, best, current, candidate State) (bool, error)
• type Listener
• type MaxIterations
  • func (mi *MaxIterations) IsDone(rnd *rand.Rand, best, current State) (bool, error)
• type MaxRuntime
  • func (mr *MaxRuntime) IsDone(rnd *rand.Rand, best, current State) (bool, error)
• type NoImprovement
  • func (ni *NoImprovement) IsDone(rnd *rand.Rand, best, current State) (bool, error)
• type Operator
• type OperatorSelectionScheme
• type OperatorStatistics
  • func (o OperatorStatistics) String() string
• type Outcome
  • func (o Outcome) String() string
• type Result
  • func Iterate(initial State, destroyOperators []Operator, repairOperators []Operator, ...) (*Result, error)
• type RouletteWheel
  • func NewRouletteWheel(scores [4]float64, decay float64, numDestroy int, numRepair int, ...) (RouletteWheel, error)
  • func (r *RouletteWheel) Select(rnd *rand.Rand, best State, current State) (int, int, error)
  • func (r *RouletteWheel) Update(candidate State, deleteOpIndx int, repairOpIndx int, outcome Outcome) error
• type State
• type Statistics
• type StoppingCriterion
• type StoppingCriterions
  • func (sc StoppingCriterions) IsDone(rnd *rand.Rand, best, current State) (bool, error)

Variables

var AbsoulteTolerance float64 = 1e-12 // for numbers near zero

var RelativeTolerance float64 = 1e-12 // for numbers that can be of large order

var RuntimeRand *rand.Rand = rand.New(&randomSource{})

var UseIsCloseComparison = true

Functions

func Compare

func Compare(a, b float64) int

func IsClose

func IsClose(a, b float64) bool

Types

type ALNS

type ALNS struct {
	Rnd               *rand.Rand
	CollectObjectives bool
	Listener          Listener
	DestroyOperators  []Operator
	RepairOperators   []Operator
	Selector          OperatorSelectionScheme
	Acceptor          AcceptanceCriterion
	Stop              StoppingCriterion
	InitialSolution   State
	Result            Result
}

func (*ALNS) AddDestroyOperator

func (a *ALNS) AddDestroyOperator(ops ...Operator)

func (*ALNS) AddRepairOperator

func (a *ALNS) AddRepairOperator(ops ...Operator)

func (*ALNS) Iterate

func (a *ALNS) Iterate() (*Result, error)

type AcceptanceCriterion

type AcceptanceCriterion interface {
	Accept(rnd *rand.Rand, best, current, candidate State) (bool, error)
}

type Context

type Context struct {
	Context context.Context
}

func (*Context) IsDone

func (c *Context) IsDone(rnd *rand.Rand, best, current State) (bool, error)

type HillClimbing

type HillClimbing struct {
}

func (*HillClimbing) Accept

func (h *HillClimbing) Accept(rnd *rand.Rand, best, current, candidate State) (bool, error)

type Listener

type Listener func(outcome Outcome, cand State) error

type MaxIterations

type MaxIterations struct {
	MaxIterations int
	// contains filtered or unexported fields
}

func (*MaxIterations) IsDone

func (mi *MaxIterations) IsDone(rnd *rand.Rand, best, current State) (bool, error)

type MaxRuntime

type MaxRuntime struct {
	MaxRuntime time.Duration
	// contains filtered or unexported fields
}

func (*MaxRuntime) IsDone

func (mr *MaxRuntime) IsDone(rnd *rand.Rand, best, current State) (bool, error)

type NoImprovement

type NoImprovement struct {
	MaxIterations int
	// contains filtered or unexported fields
}

func (*NoImprovement) IsDone

func (ni *NoImprovement) IsDone(rnd *rand.Rand, best, current State) (bool, error)

type Operator

type Operator func(state State, rnd *rand.Rand) (State, error)

type OperatorSelectionScheme

type OperatorSelectionScheme interface {
	Select(rnd *rand.Rand, best, current State) (deleteOpIndx, repairOpIndx int, err error)
	Update(candidate State, deleteOpIndx, repairOpIndx int, outcome Outcome) error
}

type OperatorStatistics

type OperatorStatistics [4]int // see Outcome

func (OperatorStatistics) String

func (o OperatorStatistics) String() string

type Outcome

type Outcome int

const (
	Best   Outcome = iota // Candidate solution is a new global best
	Better                // Candidate solution is better than the current incumbent
	Accept                // Candidate solution is accepted
	Reject                // Candidate solution is rejected
)

func (Outcome) String

func (o Outcome) String() string

type Result

type Result struct {
	BestState  State
	Statistics Statistics
}

func Iterate

func Iterate(
	initial State,
	destroyOperators []Operator,
	repairOperators []Operator,
	scores [4]float64,
	decay float64,
	maxIterations int,
) (*Result, error)

type RouletteWheel

type RouletteWheel struct {
	// contains filtered or unexported fields
}

The `RouletteWheel` scheme updates operator weights as a convex combination of the current weight, and the new score.

func NewRouletteWheel

func NewRouletteWheel(
	scores [4]float64,
	decay float64,
	numDestroy int,
	numRepair int,
	opCoupling [][]bool,
) (RouletteWheel, error)

func (*RouletteWheel) Select

func (r *RouletteWheel) Select(rnd *rand.Rand, best State, current State) (int, int, error)

func (*RouletteWheel) Update

func (r *RouletteWheel) Update(candidate State, deleteOpIndx int, repairOpIndx int, outcome Outcome) error

type State

type State interface {
	Objective() float64
}

type Statistics

type Statistics struct {
	IterationCount        int                  // the number of iterations
	TotalRuntime          time.Duration        // the total runtime
	Runtimes              []time.Duration      // run times
	Objectives            []float64            // previous objective values, tracking progress
	DestroyOperatorCounts []OperatorStatistics // the destroy operator counts
	RepairOperatorCounts  []OperatorStatistics // the repair operator counts
}

type StoppingCriterion

type StoppingCriterion interface {
	IsDone(rnd *rand.Rand, best, current State) (bool, error)
}

type StoppingCriterions

type StoppingCriterions []StoppingCriterion

func (StoppingCriterions) IsDone

func (sc StoppingCriterions) IsDone(rnd *rand.Rand, best, current State) (bool, error)