edu.udo.cs.yale.operator.features.selection
Class AbstractGeneticAlgorithm

java.lang.Object
  edu.udo.cs.yale.operator.Operator
      edu.udo.cs.yale.operator.OperatorChain
          edu.udo.cs.yale.operator.features.FeatureOperator
              edu.udo.cs.yale.operator.features.selection.AbstractGeneticAlgorithm

All Implemented Interfaces:

ConfigurationListener

Direct Known Subclasses:

AbstractGeneratingGeneticAlgorithm, EvolutionaryWeighting, GeneticAlgorithm

public abstract class AbstractGeneticAlgorithm
extends FeatureOperator

Genetic algorithms are general purpose optimization / search algorithms that are suitable in case of no or little problem knowledge.
A genetic algorithm works as follows

1. Generate an initial population consisting of population_size individuals. Each attribute is switched on with probability p_initialize
2. For all individuals in the population
   • Choose two individuals from the population and perform crossover with probability p_crossover. The type of crossover can be selected by crossover_type.
   • Perform mutation, i.e. set used attributes to unused with probability p_mutation and vice versa. Other mutations may for example create new attributes etc.
3. Perform selection with a defined selection scheme.
4. As long as the fitness improves, go to 2

If the example set contains value series attributes with blocknumbers, the whole block should be switched on and off.

Version:

$Id: AbstractGeneticAlgorithm.java,v 1.1 2006/04/14 07:47:17 ingomierswa Exp $

Author:

Ingo Mierswa

Field Summary

static int	BOLTZMANN_SELECTION
static int	CUT_SELECTION
private int	generationsWithoutImproval Stop criterion: Stop after generationsWithoutImproval generations without an improval of the fitness.
private int	maxGen Maximum number of generations.
static int	NON_DOMINATED_SORTING_SELECTION
private int	numberOfIndividuals The size of the population.
static int	RANK_SELECTION
static int	ROULETTE_WHEEL
static java.lang.String[]	SELECTION_SCHEMES
static int	STOCHASTIC_UNIVERSAL
static int	TOURNAMENT_SELECTION
static int	UNIFORM_SELECTION

Constructor Summary

AbstractGeneticAlgorithm(OperatorDescription description)

Method Summary

protected abstract PopulationOperator	getCrossoverPopulationOperator(ExampleSet example) Returns an operator that performs crossover.
protected abstract PopulationOperator	getMutationPopulationOperator(ExampleSet example) Returns an operator that performs the mutation.
java.util.List<ParameterType>	getParameterTypes() Returns a list of ParameterTypes describing the parameters of this operator.
java.util.List<PopulationOperator>	getPostEvaluationPopulationOperators(ExampleSet input) Returns the list with post eval pop ops.
protected java.util.List<PopulationOperator>	getPostProcessingPopulationOperators(ExampleSet input) Returns an empty list.
java.util.List<PopulationOperator>	getPreEvaluationPopulationOperators(ExampleSet input) Returns the list with pre eval pop ops.
protected java.util.List<PopulationOperator>	getPreProcessingPopulationOperators(ExampleSet input) Returns an empty list.
boolean	solutionGoodEnough(Population pop) Returns true if generation is >= maximum_number_of_generations or after generations_without_improval generations without improval.

Methods inherited from class edu.udo.cs.yale.operator.features.FeatureOperator

apply, createInitialPopulation, evaluate, evaluate, getCheckForMaximum, getInnerOperatorCondition, getInputClasses, getMaxNumberOfInnerOperators, getMinNumberOfInnerOperators, getNumberOfSteps, getOutputClasses, getRandom, setCheckForMaximum

Methods inherited from class edu.udo.cs.yale.operator.OperatorChain

addAddListener, addOperator, addOperator, checkDeprecations, checkIO, checkNumberOfInnerOperators, checkProperties, clearErrorList, clearStepCounter, cloneOperator, countStep, createExperimentTree, delete, experimentFinished, experimentStarts, getAllInnerOperators, getCurrentStep, getIndexOfOperator, getInnerOperatorForName, getInnerOperatorsXML, getNumberOfAllOperators, getNumberOfChildrensSteps, getNumberOfOperators, getOperator, getOperatorFromAll, getOperators, isEnabled, performAdditionalChecks, removeAddListener, removeOperator, setEnabled, setExperiment, shouldReturnInnerOutput

Methods inherited from class edu.udo.cs.yale.operator.Operator

addError, addValue, addWarning, apply, createExperimentTree, createFromXML, createMarkedExperimentTree, getAddOnlyAdditionalOutput, getApplyCount, getDeliveredOutputClasses, getDeprecationInfo, getDesiredInputClasses, getErrorList, getExperiment, getInput, getInput, getInput, getInputDescription, getIOContainerForInApplyLoopBreakpoint, getName, getOperatorClassName, getOperatorDescription, getParameter, getParameterAsBoolean, getParameterAsColor, getParameterAsDouble, getParameterAsFile, getParameterAsInt, getParameterAsString, getParameterList, getParameters, getParameterType, getParent, getStartTime, getStatus, getUserDescription, getValue, getValues, getXML, hasBreakpoint, hasBreakpoint, hasInput, inApplyLoop, isParameterSet, logMessage, register, remove, rename, resume, setBreakpoint, setInput, setListParameter, setOperatorParameters, setParameter, setParameters, setParent, setUserDescription, toString, writeXML

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

SELECTION_SCHEMES

public static final java.lang.String[] SELECTION_SCHEMES

UNIFORM_SELECTION

public static final int UNIFORM_SELECTION

See Also:

Constant Field Values

CUT_SELECTION

public static final int CUT_SELECTION

See Also:

Constant Field Values

ROULETTE_WHEEL

public static final int ROULETTE_WHEEL

See Also:

Constant Field Values

STOCHASTIC_UNIVERSAL

public static final int STOCHASTIC_UNIVERSAL

See Also:

Constant Field Values

BOLTZMANN_SELECTION

public static final int BOLTZMANN_SELECTION

See Also:

Constant Field Values

RANK_SELECTION

public static final int RANK_SELECTION

See Also:

Constant Field Values

TOURNAMENT_SELECTION

public static final int TOURNAMENT_SELECTION

See Also:

Constant Field Values

NON_DOMINATED_SORTING_SELECTION

public static final int NON_DOMINATED_SORTING_SELECTION

See Also:

Constant Field Values

numberOfIndividuals

private int numberOfIndividuals

The size of the population.

maxGen

private int maxGen

Maximum number of generations.

generationsWithoutImproval

private int generationsWithoutImproval

Stop criterion: Stop after generationsWithoutImproval generations without an improval of the fitness.

Constructor Detail

AbstractGeneticAlgorithm

public AbstractGeneticAlgorithm(OperatorDescription description)

Method Detail

getMutationPopulationOperator

protected abstract PopulationOperator getMutationPopulationOperator(ExampleSet example)
                                                             throws OperatorException

Returns an operator that performs the mutation. Can be overridden by subclasses.

Throws:

OperatorException

getCrossoverPopulationOperator

protected abstract PopulationOperator getCrossoverPopulationOperator(ExampleSet example)
                                                              throws OperatorException

Returns an operator that performs crossover. Can be overridden by subclasses.

Throws:

OperatorException

getPreProcessingPopulationOperators

protected java.util.List<PopulationOperator> getPreProcessingPopulationOperators(ExampleSet input)
                                                                          throws OperatorException

Returns an empty list.

Throws:

OperatorException

getPostProcessingPopulationOperators

protected java.util.List<PopulationOperator> getPostProcessingPopulationOperators(ExampleSet input)
                                                                           throws OperatorException

Returns an empty list.

Throws:

OperatorException

getPreEvaluationPopulationOperators

public final java.util.List<PopulationOperator> getPreEvaluationPopulationOperators(ExampleSet input)
                                                                             throws OperatorException

Returns the list with pre eval pop ops.

Specified by:

getPreEvaluationPopulationOperators in class FeatureOperator

Throws:

OperatorException

getPostEvaluationPopulationOperators

public final java.util.List<PopulationOperator> getPostEvaluationPopulationOperators(ExampleSet input)
                                                                              throws OperatorException

Returns the list with post eval pop ops.

Specified by:

getPostEvaluationPopulationOperators in class FeatureOperator

Throws:

OperatorException

solutionGoodEnough

public boolean solutionGoodEnough(Population pop)

Returns true if generation is >= maximum_number_of_generations or after generations_without_improval generations without improval.

Specified by:

solutionGoodEnough in class FeatureOperator

getParameterTypes

public java.util.List<ParameterType> getParameterTypes()

Description copied from class: Operator

Returns a list of ParameterTypes describing the parameters of this operator. The default implementation returns an empty list if no input objects can be retained and special parameters for those input objects which can be prevented from being consumed.

Overrides:

getParameterTypes in class FeatureOperator