/*
Copyright 2006 by Sean Luke
Licensed under the Academic Free License version 3.0
See the file "LICENSE" for more information
*/
package ec.simple;
import ec.Initializer;
import ec.Individual;
import ec.BreedingPipeline;
import ec.Breeder;
import ec.EvolutionState;
import ec.Population;
import ec.util.Parameter;
import ec.util.*;
/*
* SimpleBreeder.java
*
* Created: Tue Aug 10 21:00:11 1999
* By: Sean Luke
*/
/**
* Breeds each subpopulation separately, with no inter-population exchange,
* and using a generational approach. A SimpleBreeder may have multiple
* threads; it divvys up a subpopulation into chunks and hands one chunk
* to each thread to populate. One array of BreedingPipelines is obtained
* from a population's Species for each operating breeding thread.
*
* Prior to breeding a subpopulation, a SimpleBreeder may first fill part of the new
* subpopulation up with the best n individuals from the old subpopulation.
* By default, n is 0 for each subpopulation (that is, this "elitism"
* is not done). The elitist step is performed by a single thread.
*
*
If the sequential parameter below is true, then breeding is done specially:
* instead of breeding all Subpopulations each generation, we only breed one each generation.
* The subpopulation index to breed is determined by taking the generation number, modulo the
* total number of subpopulations. Use of this parameter outside of a coevolutionary context
* (see ec.coevolve.MultiPopCoevolutionaryEvaluator) is very rare indeed.
*
*
SimpleBreeder adheres to the default-subpop parameter in Population: if either an 'elite'
* or 'reevaluate-elites' parameter is missing, it will use the default subpopulation's value
* and signal a warning.
*
Parameters
base.elite.i
int >= 0 (default=0)
(the number of elitist individuals for subpopulation i) base.reevaluate-elites.i
boolean (default = false)
(should we reevaluate the elites of subpopulation i each generation?) base.sequential
boolean (default = false)
(should we breed just one subpopulation each generation (as opposed to all of them)?)
*
*
* @author Sean Luke
* @version 1.0
*/
public class SimpleBreeder extends Breeder
{
public static final String P_ELITE = "elite";
public static final String P_ELITE_FRAC = "elite-fraction";
public static final String P_REEVALUATE_ELITES = "reevaluate-elites";
public static final String P_SEQUENTIAL_BREEDING = "sequential";
public static final String P_CLONE_PIPELINE_AND_POPULATION = "clone-pipeline-and-population";
/** An array[subpop] of the number of elites to keep for that subpopulation */
public int[] elite;
public double[] eliteFrac;
public boolean[] reevaluateElites;
public boolean sequentialBreeding;
public boolean clonePipelineAndPopulation;
public Population backupPopulation = null;
public static final int NOT_SET = -1;
public ThreadPool pool = new ThreadPool();
public boolean usingElitism(int subpopulation)
{
return (elite[subpopulation] > 0 ) || (eliteFrac[subpopulation] > 0);
}
public int numElites(EvolutionState state, int subpopulation)
{
if (elite[subpopulation] != NOT_SET)
{
return elite[subpopulation];
}
else if (eliteFrac[subpopulation] == 0)
{
return 0; // no elites
}
else if (eliteFrac[subpopulation] != NOT_SET)
{
return (int) Math.max(Math.floor(state.population.subpops[subpopulation].individuals.length * eliteFrac[subpopulation]), 1.0); // AT LEAST 1 ELITE
}
else
{
state.output.warnOnce("Elitism error (SimpleBreeder). This shouldn't be able to happen. Please report.");
return 0; // this shouldn't happen
}
}
public void setup(final EvolutionState state, final Parameter base)
{
Parameter p = new Parameter(Initializer.P_POP).push(Population.P_SIZE);
int size = state.parameters.getInt(p,null,1); // if size is wrong, we'll let Population complain about it -- for us, we'll just make 0-sized arrays and drop out.
eliteFrac = new double[size];
elite = new int[size];
for(int i = 0; i < size; i++)
eliteFrac[i] = elite[i] = NOT_SET;
reevaluateElites = new boolean[size];
sequentialBreeding = state.parameters.getBoolean(base.push(P_SEQUENTIAL_BREEDING), null, false);
if (sequentialBreeding && (size == 1)) // uh oh, this can't be right
state.output.fatal("The Breeder is breeding sequentially, but you have only one population.", base.push(P_SEQUENTIAL_BREEDING));
clonePipelineAndPopulation =state.parameters.getBoolean(base.push(P_CLONE_PIPELINE_AND_POPULATION), null, true);
if (!clonePipelineAndPopulation && (state.breedthreads > 1)) // uh oh, this can't be right
state.output.fatal("The Breeder is not cloning its pipeline and population, but you have more than one thread.", base.push(P_CLONE_PIPELINE_AND_POPULATION));
int defaultSubpop = state.parameters.getInt(new Parameter(Initializer.P_POP).push(Population.P_DEFAULT_SUBPOP), null, 0);
for(int x=0;x= 0", base.push(P_ELITE).push(""+x));
}
}
else if (state.parameters.exists(base.push(P_ELITE_FRAC).push(""+x),null))
{
eliteFrac[x] = state.parameters.getDoubleWithMax(base.push(P_ELITE_FRAC).push(""+x),null,0.0, 1.0);
if (eliteFrac[x] < 0.0)
state.output.error("Elite Fraction of subpopulation " + x + " must be a real value between 0.0 and 1.0 inclusive", base.push(P_ELITE_FRAC).push(""+x));
}
else if (defaultSubpop >= 0)
{
if (state.parameters.exists(base.push(P_ELITE).push(""+defaultSubpop),null))
{
elite[x] = state.parameters.getIntWithDefault(base.push(P_ELITE).push(""+defaultSubpop),null,0);
if (elite[x] < 0)
state.output.warning("Invalid default subpopulation elite value."); // we'll fail later
}
else if (state.parameters.exists(base.push(P_ELITE_FRAC).push(""+defaultSubpop),null))
{
eliteFrac[x] = state.parameters.getDoubleWithMax(base.push(P_ELITE_FRAC).push(""+defaultSubpop),null,0.0, 1.0);
if (eliteFrac[x] < 0.0)
state.output.warning("Invalid default subpopulation elite-frac value."); // we'll fail later
}
else // elitism is 0
{
elite[x] = 0;
}
}
else // elitism is 0
{
elite[x] = 0;
}
// get reevaluation
if (defaultSubpop >= 0 && !state.parameters.exists(base.push(P_REEVALUATE_ELITES).push(""+x),null))
{
reevaluateElites[x] = state.parameters.getBoolean(base.push(P_REEVALUATE_ELITES).push(""+defaultSubpop), null, false);
if (reevaluateElites[x])
state.output.warning("Elite reevaluation not specified for subpopulation " + x + ". Using values for default subpopulation " + defaultSubpop + ": " + reevaluateElites[x]);
}
else
{
reevaluateElites[x] = state.parameters.getBoolean(base.push(P_REEVALUATE_ELITES).push(""+x), null, false);
}
}
state.output.exitIfErrors();
}
/** Elites are often stored in the top part of the subpopulation; this function returns what
part of the subpopulation contains individuals to replace with newly-bred ones
(up to but not including the elites). */
public int computeSubpopulationLength(EvolutionState state, Population newpop, int subpopulation, int threadnum)
{
if (!shouldBreedSubpop(state, subpopulation, threadnum))
return newpop.subpops[subpopulation].individuals.length; // we're not breeding the population, just copy over the whole thing
return newpop.subpops[subpopulation].individuals.length - numElites(state, subpopulation); // we're breeding population, so elitism may have happened
}
/** A simple breeder that doesn't attempt to do any cross-
population breeding. Basically it applies pipelines,
one per thread, to various subchunks of a new population. */
public Population breedPopulation(EvolutionState state)
{
Population newpop = null;
if (clonePipelineAndPopulation)
newpop = (Population) state.population.emptyClone();
else
{
if (backupPopulation == null)
backupPopulation = (Population) state.population.emptyClone();
newpop = backupPopulation;
newpop.clear();
backupPopulation = state.population; // swap in
}
// load elites into top of newpop
loadElites(state, newpop);
// how many threads do we really need? No more than the maximum number of individuals in any subpopulation
int numThreads = 0;
for(int x = 0; x < state.population.subpops.length; x++)
numThreads = Math.max(numThreads, state.population.subpops[x].individuals.length);
numThreads = Math.min(numThreads, state.breedthreads);
if (numThreads < state.breedthreads)
state.output.warnOnce("Largest subpopulation size (" + numThreads +") is smaller than number of breedthreads (" + state.breedthreads +
"), so fewer breedthreads will be created.");
int numinds[][] =
new int[numThreads][state.population.subpops.length];
int from[][] =
new int[numThreads][state.population.subpops.length];
for(int x=0;x 0)
{
numinds[y][x] = individualsPerThread + 1;
slop--;
}
else
numinds[y][x] = individualsPerThread;
if (numinds[y][x] == 0)
{
state.output.warnOnce("More threads exist than can be used to breed some subpopulations (first example: subpopulation " + x + ")");
}
from[y][x] = currentFrom;
currentFrom += numinds[y][x];
}
}
/*
for(int y=0;yupperbound) // uh oh! Someone blew it!
state.output.fatal("Whoa! A breeding pipeline overwrote the space of another pipeline in subpopulation " + subpop + ". You need to check your breeding pipeline code (in produce() ).");
bp.finishProducing(state,subpop,threadnum);
}
}
}
static class EliteComparator implements SortComparatorL
{
Individual[] inds;
public EliteComparator(Individual[] inds) {super(); this.inds = inds;}
public boolean lt(long a, long b)
{ return inds[(int)b].fitness.betterThan(inds[(int)a].fitness); }
public boolean gt(long a, long b)
{ return inds[(int)a].fitness.betterThan(inds[(int)b].fitness); }
}
protected void unmarkElitesEvaluated(EvolutionState state, Population newpop)
{
for(int sub=0;substate.population.subpops[x].individuals.length)
state.output.error("The number of elites for subpopulation " + x + " exceeds the actual size of the subpopulation",
new Parameter(EvolutionState.P_BREEDER).push(P_ELITE).push(""+x));
if (numElites(state, x)==state.population.subpops[x].individuals.length)
state.output.warning("The number of elites for subpopulation " + x + " is the actual size of the subpopulation",
new Parameter(EvolutionState.P_BREEDER).push(P_ELITE).push(""+x));
}
state.output.exitIfErrors();
// we assume that we're only grabbing a small number (say <10%), so
// it's not being done multithreaded
for(int sub=0;sub0) // we'll need to sort
{
int[] orderedPop = new int[state.population.subpops[sub].individuals.length];
for(int x=0;x
Ads help maintain this website.