models.go

package eaopt

import (
	"errors"
	"math/rand"
)

var (
	errNilSelector      = errors.New("selector cannot be nil")
	errInvalidMutRate   = errors.New("mutRate should be between 0 and 1")
	errInvalidCrossRate = errors.New("crossRate should be between 0 and 1")
)

// Two parents are selected from a pool of individuals, crossover is then
// applied to generate two offsprings. The selection and crossover process is
// repeated until n offsprings have been generated. If n is uneven then the
// second offspring of the last crossover is discarded.
func generateOffsprings(n uint, indis Individuals, sel Selector, crossRate float64,
	rng *rand.Rand) (Individuals, error) {
	var (
		offsprings = make(Individuals, n)
		i          = 0
	)
	for i < len(offsprings) {
		// Select 2 parents
		var selected, _, err = sel.Apply(2, indis, rng)
		if err != nil {
			return nil, err
		}
		// Generate 2 offsprings from the parents
		if rng.Float64() < crossRate {
			selected[0].Crossover(selected[1], rng)
		}
		if i < len(offsprings) {
			offsprings[i] = selected[0]
			i++
		}
		if i < len(offsprings) {
			offsprings[i] = selected[1]
			i++
		}
	}
	return offsprings, nil
}

// A Model specifies a protocol for applying genetic operators to a
// population at generation i in order for it obtain better individuals at
// generation i+1.
type Model interface {
	Apply(pop *Population) error
	Validate() error
}

// ModGenerational implements the generational model.
type ModGenerational struct {
	Selector  Selector
	MutRate   float64
	CrossRate float64
}

// Apply ModGenerational.
func (mod ModGenerational) Apply(pop *Population) error {
	// Generate as many offsprings as there are of individuals in the current population
	var offsprings, err = generateOffsprings(
		uint(len(pop.Individuals)),
		pop.Individuals,
		mod.Selector,
		mod.CrossRate,
		pop.RNG,
	)
	if err != nil {
		return err
	}
	// Apply mutation to the offsprings
	if mod.MutRate > 0 {
		offsprings.Mutate(mod.MutRate, pop.RNG)
	}
	// Replace the old population with the new one
	copy(pop.Individuals, offsprings)
	return nil
}

// Validate ModGenerational fields.
func (mod ModGenerational) Validate() error {
	// Check the selection method presence
	if mod.Selector == nil {
		return errNilSelector
	}
	// Check the selection method parameters
	var errSelector = mod.Selector.Validate()
	if errSelector != nil {
		return errSelector
	}
	// Check the mutation rate
	if mod.MutRate < 0 || mod.MutRate > 1 {
		return errInvalidMutRate
	}
	// Check the crossover rate
	if mod.CrossRate < 0 || mod.CrossRate > 1 {
		return errInvalidCrossRate
	}
	return nil
}

// ModSteadyState implements the steady state model.
type ModSteadyState struct {
	Selector  Selector
	KeepBest  bool
	MutRate   float64
	CrossRate float64
}

// Apply ModSteadyState.
func (mod ModSteadyState) Apply(pop *Population) error {
	var selected, indexes, err = mod.Selector.Apply(2, pop.Individuals, pop.RNG)
	if err != nil {
		return err
	}
	var offsprings = selected.Clone(pop.RNG)
	if pop.RNG.Float64() < mod.CrossRate {
		offsprings[0].Crossover(offsprings[1], pop.RNG)
	}
	// Apply mutation to the offsprings
	if mod.MutRate > 0 {
		if pop.RNG.Float64() < mod.MutRate {
			offsprings[0].Mutate(pop.RNG)
		}
		if pop.RNG.Float64() < mod.MutRate {
			offsprings[1].Mutate(pop.RNG)
		}
	}
	if mod.KeepBest {
		// Replace the chosen individuals with the best individuals
		err = offsprings[0].Evaluate()
		if err != nil {
			return err
		}
		err = offsprings[1].Evaluate()
		if err != nil {
			return err
		}
		var indis = Individuals{selected[0], selected[1], offsprings[0], offsprings[1]}
		indis.SortByFitness()
		pop.Individuals[indexes[0]] = indis[0]
		pop.Individuals[indexes[1]] = indis[1]
	} else {
		// Replace the chosen parents with the offsprings
		pop.Individuals[indexes[0]] = offsprings[0]
		pop.Individuals[indexes[1]] = offsprings[1]
	}
	return nil
}

// Validate ModSteadyState fields.
func (mod ModSteadyState) Validate() error {
	// Check the selection method presence
	if mod.Selector == nil {
		return errNilSelector
	}
	// Check the selection method parameters
	var errSelector = mod.Selector.Validate()
	if errSelector != nil {
		return errSelector
	}
	// Check the mutation rate in the presence of a mutator
	if mod.MutRate < 0 || mod.MutRate > 1 {
		return errInvalidMutRate
	}
	// Check the crossover rate
	if mod.CrossRate < 0 || mod.CrossRate > 1 {
		return errInvalidCrossRate
	}
	return nil
}

// ModDownToSize implements the select down to size model.
type ModDownToSize struct {
	NOffsprings uint
	SelectorA   Selector
	SelectorB   Selector
	MutRate     float64
	CrossRate   float64
}

// Apply ModDownToSize.
func (mod ModDownToSize) Apply(pop *Population) error {
	var offsprings, err = generateOffsprings(
		mod.NOffsprings,
		pop.Individuals,
		mod.SelectorA,
		mod.CrossRate,
		pop.RNG,
	)
	if err != nil {
		return err
	}
	// Apply mutation to the offsprings
	if mod.MutRate > 0 {
		offsprings.Mutate(mod.MutRate, pop.RNG)
	}
	err = offsprings.Evaluate(false)
	if err != nil {
		return err
	}
	// Merge the current population with the offsprings
	offsprings = append(offsprings, pop.Individuals...)
	// Select down to size
	var selected, _, _ = mod.SelectorB.Apply(uint(len(pop.Individuals)), offsprings, pop.RNG)
	// Replace the current population of individuals
	copy(pop.Individuals, selected)
	return nil
}

// Validate ModDownToSize fields.
func (mod ModDownToSize) Validate() error {
	// Check the number of offsprings value
	if mod.NOffsprings <= 0 {
		return errors.New("NOffsprings has to higher than 0")
	}
	// Check the first selection method presence
	if mod.SelectorA == nil {
		return errNilSelector
	}
	// Check the first selection method parameters
	var errSelectorA = mod.SelectorA.Validate()
	if errSelectorA != nil {
		return errSelectorA
	}
	// Check the second selection method presence
	if mod.SelectorB == nil {
		return errNilSelector
	}
	// Check the second selection method parameters
	var errSelectorB = mod.SelectorB.Validate()
	if errSelectorB != nil {
		return errSelectorB
	}
	// Check the mutation rate in the presence of a mutator
	if mod.MutRate < 0 || mod.MutRate > 1 {
		return errInvalidMutRate
	}
	return nil
}

// ModRing implements the island ring model.
type ModRing struct {
	Selector Selector
	MutRate  float64
}

// Apply ModRing.
func (mod ModRing) Apply(pop *Population) error {
	for i := range pop.Individuals {
		var (
			indi      = pop.Individuals[i].Clone(pop.RNG)
			neighbour = pop.Individuals[(i+1)%len(pop.Individuals)]
		)
		indi.Crossover(neighbour, pop.RNG)
		// Apply mutation to the offsprings
		if mod.MutRate > 0 {
			if pop.RNG.Float64() < mod.MutRate {
				indi.Mutate(pop.RNG)
			}
			if pop.RNG.Float64() < mod.MutRate {
				neighbour.Mutate(pop.RNG)
			}
		}
		err := indi.Evaluate()
		if err != nil {
			return err
		}
		err = neighbour.Evaluate()
		if err != nil {
			return err
		}
		// Select an individual out of the original individual and the
		// offsprings
		indis := Individuals{pop.Individuals[i], indi, neighbour}
		selected, _, err := mod.Selector.Apply(1, indis, pop.RNG)
		if err != nil {
			return err
		}
		pop.Individuals[i] = selected[0]
	}
	return nil
}

// Validate ModRing fields.
func (mod ModRing) Validate() error {
	// Check the selection method presence
	if mod.Selector == nil {
		return errNilSelector
	}
	// Check the selection method parameters
	var errSelector = mod.Selector.Validate()
	if errSelector != nil {
		return errSelector
	}
	// Check the mutation rate in the presence of a mutator
	if mod.MutRate < 0 || mod.MutRate > 1 {
		return errInvalidMutRate
	}
	return nil
}

// ModMutationOnly implements the mutation only model. Each generation, all the
// Individuals are mutated. If Strict is true then the individuals are only
// replaced if the mutation is favorable.
type ModMutationOnly struct {
	Strict bool
}

// Apply ModMutationOnly.
func (mod ModMutationOnly) Apply(pop *Population) error {
	for i, indi := range pop.Individuals {
		var mutant = indi.Clone(pop.RNG)
		mutant.Mutate(pop.RNG)
		err := mutant.Evaluate()
		if err != nil {
			return err
		}
		if !mod.Strict || (mod.Strict && mutant.Fitness < indi.Fitness) {
			pop.Individuals[i] = mutant
		}
	}
	return nil
}

// Validate ModMutationOnly fields.
func (mod ModMutationOnly) Validate() error {
	return nil
}

// An SAAcceptance function, used by ModSimulatedAnnealing, returns the
// probability of accepting an energy (badness) increase from e0 to e1 on
// generation gen of nGen.
type SAAcceptance func(gen, nGen uint, e0, e1 float64) float64

// ModSimulatedAnnealing is a mutation-only model used to implement simulated
// annealing.  All individuals are mutated but only conditionally replace their
// parent.  If the mutation is favorable it always replaces its parent.  If the
// mutation is unfavorable, it is more likely to replace its parent earlier
// than later in the evolution.
type ModSimulatedAnnealing struct {
	GA     *GA          // Pointer to the encompassing GA, set by NewGA and needed to gauge progress toward completion
	Accept SAAcceptance // Badness acceptance function
}

// Apply ModSimulatedAnnealing.
func (mod ModSimulatedAnnealing) Apply(pop *Population) error {
	for i, indi := range pop.Individuals {
		// Mutate the individual.
		var mutant = indi.Clone(pop.RNG)
		mutant.Mutate(pop.RNG)
		err := mutant.Evaluate()
		if err != nil {
			return err
		}

		// Decide whether to keep the original or its mutation
		prob := 1.0
		if mutant.Fitness > indi.Fitness && mod.GA != nil {
			prob = mod.Accept(mod.GA.Generations,
				mod.GA.GAConfig.NGenerations,
				indi.Fitness,
				mutant.Fitness)
		}
		if prob > pop.RNG.Float64() {
			pop.Individuals[i] = mutant
		}
	}
	return nil
}

// Validate ModSimulatedAnnealing fields.
func (mod ModSimulatedAnnealing) Validate() error {
	// Ideally, we would check that GA is not nil.  Unfortunately, Validate
	// may be called before NewGA has a chance to initialize that field so
	// all we can check is the Accept field.
	if mod.Accept == nil {
		return errors.New("an Accept function must be provided to ModSimulatedAnnealing")
	}
	return nil
}