speciation.go

package eaopt

import (
	"errors"
	"fmt"
	"math/rand"
)

// A Speciator partitions a population into n smaller subpopulations. Each
// subpopulation shares the same random number generator inherited from the
// initial population.
type Speciator interface {
	Apply(indis Individuals, rng *rand.Rand) ([]Individuals, error)
	Validate() error
}

// SpecKMedoids (k-medoid clustering).
type SpecKMedoids struct {
	K             uint // Number of medoids
	MinPerCluster uint
	Metric        Metric // Dissimimilarity measure
	MaxIterations uint
}

// Apply SpecKMedoids.
func (spec SpecKMedoids) Apply(indis Individuals, rng *rand.Rand) ([]Individuals, error) {
	// Check there are at least K Individuals
	if len(indis) < int(spec.K) {
		return nil, fmt.Errorf("SpecKMedoids: have %d individuals and need at least %d",
			len(indis), spec.K)
	}
	var (
		species = make([]Individuals, spec.K)
		medoids = make(Individuals, spec.K)
		dm      = newDistanceMemoizer(spec.Metric)
	)
	// Initialize the clusters with the individuals having the lowest average
	// distances with the other individuals
	indis.SortByDistanceToMedoid(dm)
	copy(medoids, indis[:spec.K])
	// Add each medoid to a cluster
	for i, medoid := range medoids {
		species[i] = append(species[i], medoid)
	}
	// Keep track of the total distance from the medoid to each of the cluster's
	// members, this total will then be used to compare with different cluster
	// dispositions
	var total float64
	// Assign each individual that is not a medoid to the closest initial medoid
	for _, indi := range indis[spec.K:] {
		var i = indi.IdxOfClosest(medoids, dm)
		species[i] = append(species[i], indi)
		total += dm.GetDistance(medoids[i], indi)
	}
	var nIterations uint
	for nIterations < spec.MaxIterations {
		nIterations++
		var (
			newSpecies = make([]Individuals, len(species))
			newTotal   float64
		)
		// Recompute the new medoid inside each specie
		for i, specie := range species {
			specie.SortByDistanceToMedoid(dm)
			medoids[i] = specie[0]
			newSpecies[i] = append(newSpecies[i], specie[0])
		}
		// Reassign each individual to the closest new medoid
		for _, specie := range species {
			for _, indi := range specie[1:] {
				var i = indi.IdxOfClosest(medoids, dm)
				newSpecies[i] = append(newSpecies[i], indi)
				newTotal += dm.GetDistance(medoids[i], indi)
			}
		}
		// No more iterations are needed if the new total is worse
		if newTotal >= total {
			break
		}
		copy(species, newSpecies)
		total = newTotal
	}
	// Rebalance the species so that their are at least
	err := rebalanceClusters(species, dm, spec.MinPerCluster)
	if err != nil {
		return nil, err
	}
	return species, nil
}

// Validate SpecKMedoids fields.
func (spec SpecKMedoids) Validate() error {
	if spec.K < 2 {
		return errors.New("k should be higher than 1")
	}
	if spec.Metric == nil {
		return errors.New("metric field has to be provided")
	}
	if spec.MaxIterations < 1 {
		return errors.New("k should be higher than 0")
	}
	return nil
}

// SpecFitnessInterval speciates a population based on the fitness of each
// individual where each species contains m = n/k (rounded to the closest upper
// integer) individuals with similar fitnesses. For example, with 4 species, 30
// individuals would be split into 3 groups of 8 individuals and 1 group of 6
// individuals (3*8 + 1*6 = 30). More generally each group is of size
// min(n-i, m) where i is a multiple of m.
type SpecFitnessInterval struct {
	K uint // Number of intervals
}

// Apply SpecFitnessInterval.
func (spec SpecFitnessInterval) Apply(indis Individuals, rng *rand.Rand) ([]Individuals, error) {
	// Check there are at least K Individuals
	if len(indis) < int(spec.K) {
		return nil, fmt.Errorf("specFitnessInterval: have %d individuals and need at least %d",
			len(indis), spec.K)
	}
	var (
		species = make([]Individuals, spec.K)
		n       = len(indis)
		m       = minInt(int(float64(n/int(spec.K))), n)
	)
	for i := range species {
		var a, b = i * m, minInt((i+1)*m, n)
		species[i] = indis[a:b]
	}
	return species, nil
}

// Validate SpecFitnessInterval fields.
func (spec SpecFitnessInterval) Validate() error {
	if spec.K < 2 {
		return errors.New("k should be higher than 1")
	}
	return nil
}