ant_colony.go

package hego

import (
	"errors"
	"fmt"
	"math"
	"time"
)

// Ant is the individuum in the population based Ant Colony Optimization (ACO)
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
}

// ACOResult represents the result of the ACO
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
}

// ACOSettings represents the settings available in ACO
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
}

// Verify checks validity of the ACOSettings and returns nil if settings are ok
func (s *ACOSettings) Verify() error {
	if s.Evaporation <= 0 || s.Evaporation > 1 {
		return errors.New("evaporation must be a value in (0, 1]")
	}
	return nil
}

// ACO performs the ant colony optimization algorithm
func ACO(population []Ant, settings ACOSettings) (res ACOResult, err error) {
	err = settings.Verify()
	if err != nil {
		err = fmt.Errorf("settings verifycation failed: %v", err)
		return
	}

	start := time.Now()

	// increase FuncEvaluations for every performance call
	evaluate := func(a Ant) float64 {
		res.FuncEvaluations++
		return a.Performance()
	}

	logger := newLogger("Ant Colony Optimization", []string{"Iteration", "Average Performance", "Best Performance"}, settings.Verbose, settings.MaxIterations)

	if settings.KeepHistory {
		res.AveragePerformances = make([]float64, settings.MaxIterations)
		res.BestPerformances = make([]float64, settings.MaxIterations)
		res.BestAnts = make([]Ant, settings.MaxIterations)
	}

	res.BestPerformance = math.MaxFloat64

	for i := 0; i < settings.MaxIterations; i++ {
		totalPerformance := 0.0
		bestPerformance := math.MaxFloat64
		bestIndex := -1
		for antIndex, ant := range population {
			// initialize ant
			ant.Init()
			// create path for this ant
			for {
				options := ant.PerceivePheromone()
				next := weightedChoice(options, 1)[0]
				if ant.Step(next) { // step returns true when ant is done
					break
				}
			}
			// evaluate path
			performance := evaluate(ant)
			totalPerformance += performance
			if performance < bestPerformance {
				bestPerformance = performance
				bestIndex = antIndex
			}
		}
		population[bestIndex].DropPheromone(bestPerformance)
		// population[bestIndex].DropPheromone(bestPerformance)
		population[0].Evaporate(settings.Evaporation, settings.MinPheromone)

		if settings.KeepHistory {
			res.AveragePerformances[i] = totalPerformance / float64(len(population))
			res.BestPerformances[i] = bestPerformance
			res.BestAnts[i] = population[bestIndex]
		}

		if res.BestPerformance > bestPerformance {
			res.BestPerformance = bestPerformance
			res.BestAnt = population[bestIndex]
		}

		res.Iterations++
		logger.AddLine(i, []string{
			fmt.Sprint(i),
			fmt.Sprint(totalPerformance / float64(len(population))),
			fmt.Sprint(bestPerformance),
		})
	}
	end := time.Now()
	res.Runtime = end.Sub(start)

	logger.Flush()
	if settings.Verbose > 0 {
		fmt.Printf("DONE after %v\n", res.Runtime)
	}
	return
}