MaxHalford/eaopt

package eaopt

import (
    "math"
    "math/rand"
    "sort"
    "time"
)

// A GA contains populations which themselves contain individuals.
type GA struct {
    GAConfig `json:"-"`

    // Fields generated at runtime
    Populations Populations   `json:"populations"`
    HallOfFame  Individuals   `json:"hall_of_fame"` // Sorted best Individuals ever encountered
    Age         time.Duration `json:"duration"`     // Duration during which the GA has been evolved
    Generations uint          `json:"generations"`  // Number of generations the GA has been evolved
}

// Find the best current Individual in each population and then compare the best
// overall Individual to the current best Individual. The Individuals in each
// population are expected to be sorted.
func updateHallOfFame(hof Individuals, indis Individuals, rng *rand.Rand) {
    var k = len(hof)
    // Start by finding the current best Individual
    for _, indi := range indis[:minInt(k, len(indis))] {
        // Find if and where the Individual should fit in the hall of fame
        var (
            f = func(i int) bool { return indi.Fitness < hof[i].Fitness }
            i = sort.Search(k, f)
        )
        if i < k {
            // Shift the hall of fame to the right
            copy(hof[i+1:], hof[i:])
            // Insert the new Individual
            hof[i] = indi.Clone(rng)
        }
    }
}

func (ga *GA) init(newGenome func(rng *rand.Rand) Genome) error {
    // Reset counters
    ga.Generations = 0
    ga.Age = 0

    // Create the initial Populations
    ga.Populations = make(Populations, ga.NPops)
    for i := range ga.Populations {
        ga.Populations[i] = newPopulation(ga.PopSize, ga.ParallelInit, newGenome, ga.RNG)
        // Evaluate and sort
        err := ga.Populations[i].Individuals.Evaluate(ga.ParallelEval)
        if err != nil {
            return err
        }
        ga.Populations[i].Individuals.SortByFitness()
        // Log current statistics if a logger has been provided
        if ga.Logger != nil {
            ga.Populations[i].Log(ga.Logger)
        }
    }

    // Initialize the hall of fame
    ga.HallOfFame = make(Individuals, ga.HofSize)
    for i := range ga.HallOfFame {
        ga.HallOfFame[i] = Individual{Fitness: math.Inf(1)}
    }
    for _, pop := range ga.Populations {
        updateHallOfFame(ga.HallOfFame, pop.Individuals, pop.RNG)
    }

    // Execute the callback if it has been set
    if ga.Callback != nil {
        ga.Callback(ga)
    }

    return nil
}

// Evolve a GA's Populations in parallel.
func (ga *GA) evolve() error {
    var start = time.Now()
    ga.Generations++

    // Migrate the individuals between the populations if there are at least 2
    // Populations and that there is a migrator and that the migration frequency
    // divides the generation count
    if len(ga.Populations) > 1 && ga.Migrator != nil && ga.Generations%ga.MigFrequency == 0 {
        ga.Migrator.Apply(ga.Populations, ga.RNG)
    }

    var f = func(pop *Population) error {
        var err error
        // Apply speciation if a positive number of species has been specified
        if ga.Speciator != nil {
            err = pop.speciateEvolveMerge(ga.Speciator, ga.Model)
            if err != nil {
                return err
            }
        } else {
            // Else apply the evolution model to the entire population
            err = ga.Model.Apply(pop)
            if err != nil {
                return err
            }
        }
        // Evaluate and sort
        err = pop.Individuals.Evaluate(ga.ParallelEval)
        if err != nil {
            return err
        }
        pop.Individuals.SortByFitness()
        // Record time spent evolving
        pop.Age += time.Since(start)
        pop.Generations++
        // Log current statistics if a logger has been provided
        if ga.Logger != nil {
            pop.Log(ga.Logger)
        }
        return err
    }

    var err = ga.Populations.Apply(f)
    if err != nil {
        return err
    }
    // Update HallOfFame
    for _, pop := range ga.Populations {
        updateHallOfFame(ga.HallOfFame, pop.Individuals, pop.RNG)
    }

    ga.Age += time.Since(start)

    // Execute the callback if it has been set
    if ga.Callback != nil {
        ga.Callback(ga)
    }

    return nil
}

// Minimize evolves the GA's Populations following the given evolutionary
// method. The GA's hall of fame is updated after each generation.
func (ga *GA) Minimize(newGenome func(rng *rand.Rand) Genome) error {
    // Initialize the GA
    var err = ga.init(newGenome)
    if err != nil {
        return err
    }

    // Go through the generations
    for i := uint(0); i < ga.NGenerations; i++ {
        // Check for early stopping
        if ga.EarlyStop != nil && ga.EarlyStop(ga) {
            return nil
        }
        if err := ga.evolve(); err != nil {
            return err
        }
    }
    return nil
}

func (pop *Population) speciateEvolveMerge(spec Speciator, model Model) error {
    var (
        species, err = spec.Apply(pop.Individuals, pop.RNG)
        pops         = make([]Population, len(species))
    )
    if err != nil {
        return err
    }
    // Create a subpopulation from each specie so that the evolution Model can
    // be applied to it.
    for i, specie := range species {
        pops[i] = Population{
            Individuals: specie,
            Age:         pop.Age,
            Generations: pop.Generations,
            ID:          randString(len(pop.ID), pop.RNG),
            RNG:         pop.RNG,
        }
        err = model.Apply(&pops[i])
        if err != nil {
            return err
        }
    }
    // Merge each species back into the original population
    var i int
    for _, subpop := range pops {
        copy(pop.Individuals[i:i+len(subpop.Individuals)], subpop.Individuals)
        i += len(subpop.Individuals)
    }
    return nil
}