geneticalgorithm.java

著名的开源仿真软件yale

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2002, 2003
 *      Simon Fischer, Ralf Klinkenberg, Ingo Mierswa, 
 *          Katharina Morik, Oliver Ritthoff
 *      Artificial Intelligence Unit
 *      Computer Science Department
 *      University of Dortmund
 *      44221 Dortmund,  Germany
 *  email: [e-mail]
 *  web:   http://yale.cs.uni-dortmund.de/
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as 
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version. 
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 *  USA.
 */
package edu.udo.cs.yale.operator.features.ga;

import edu.udo.cs.yale.operator.OperatorException;
import edu.udo.cs.yale.operator.parameter.*;
import edu.udo.cs.yale.example.ExampleSet;
import edu.udo.cs.yale.example.AttributeSelectionExampleSet;
import edu.udo.cs.yale.operator.features.*;

import edu.udo.cs.yale.tools.RandomGenerator;
import edu.udo.cs.yale.tools.ParameterService;
import java.util.LinkedList;
import java.util.List;

/** A genetic algorithm for feature selection (mutation=switch features on and off, 
 *  crossover=interchange used features). Selection is done by roulette wheel.
 *  Genetic algorithms are general purpose optimisation/search algorithms that
 *  are suitable in case of no or little problem knowledge.
 *  <br/>
 *  A genetic algorithm works as follows
 *  <ol>
 *    <li>Generate an initial population consisting of <code>population_size</code> individuals.
 *        Each attribute is switched on with probability <code>p_initialize</code></li>
 *    <li>For all inidividuals in the population
 *      <ul>
 *        <li>Perform mutation, i.e. set used attributes to unused with probability <code>p_mutation</code> and vice versa.</li>
 *        <li>Choose two individuals from the poplation and perform crossover with probability <code>p_crossover</code>.
 *            The type of crossover can be selected by <code>crossover_type</code>.</li>
 *      </ul>
 *    </li>
 *    <li>Perform selection, map all individuals to sections on a roulette wheel whose size is proportional
 *        to the individual's fitness and draw <code>population_size</code> individuals at random according
 *        to their probability.</li>
 *    <li>As long as the fitness improves, go to 2</li>
 *  </ol>
 *
 *  @yale.xmlclass GeneticAlgorithm
 *  @version $Id: GeneticAlgorithm.java,v 2.8 2003/08/27 15:28:15 mierswa Exp $
 */
public class GeneticAlgorithm extends FeatureOperator {

    private LinkedList preOp, postOp;
    private RandomGenerator random;

    /** The size of the population. */
    private int numberOfIndividuals;
    /** Maximum number of generations. */
    private int maxGen;
    /** Initial porbability for an attribute to be switched on. */
    private double pInitialize;
    /** Stop criterion: Stop after generationsWithoutImproval generations without an improval of the fitness. */
    private int generationsWithoutImproval;

    public void initApply() throws OperatorException {
	super.initApply();
	this.numberOfIndividuals        = getParameterAsInt("population_size");
	this.maxGen                     = getParameterAsInt("maximum_number_of_generations");
	this.generationsWithoutImproval = getParameterAsInt("generations_without_improval");
	boolean keepBest                = getParameterAsBoolean("keep_best_individual");
	this.pInitialize                = getParameterAsDouble("p_initialize");

	this.random = RandomGenerator.getGlobalRandomGenerator();
	
	preOp = new LinkedList();

	// Die Reihenfolge ist sehr wichtig !!!
	// Zuerst MUSS die Selektion der Individuen kommen und das crossover MUSS vor dem InformationGain ausgefuehrt
	// werden. Sonst werden die Wahrscheinlichkeiten beim Generieren und Mutieren negativ!!!
	preOp.add(new RouletteWheel(numberOfIndividuals, random, keepBest));
 
	PopulationOperator crossover = getCrossoverPopulationOperator();
	if (crossover != null)
	    preOp.add(crossover);

	PopulationOperator[] preProcessing = getPreProcessingPopulationOperators();
	if (preProcessing != null) {
	    for (int i = 0; i < preProcessing.length; i++) 
		preOp.add(preProcessing[i]);
	}
	PopulationOperator mutation = getMutationPopulationOperator();
	if (mutation != null)
	    preOp.add(mutation);

	postOp = new LinkedList();
    }


    /** Sets up a population of given size and creates ExampleSets with
     *  randomly selected attributes (the probability to be switched on is controlled by
     *  pInitialize). */
    public Population createInitialPopulation(ExampleSet es) {
	Population initP = new Population();
	while (initP.getNumberOfIndividuals() < numberOfIndividuals) {
	    AttributeSelectionExampleSet nes = new AttributeSelectionExampleSet((ExampleSet)es.clone());
	    for (int j = 0; j < nes.getNumberOfAttributes(); j++) {
		if (random.nextDouble() < pInitialize)
		    nes.flipAttributeUsed(j);
	    }
	    if (nes.getNumberOfUsedAttributes() > 0) initP.add(nes);
	}
	return initP;
    }
    
    /** Returns an empty array. */
    PopulationOperator[] getPreProcessingPopulationOperators() {
	return new PopulationOperator[0];
    }

    /** Returns an operator that performs the mutation. Can be overridden by subclasses.
     */
    PopulationOperator getMutationPopulationOperator() throws OperatorException {
	double pMutation  = getParameterAsDouble("p_mutation");
	return new SelectionMutation(pMutation, random);
    }

    /** Returns an operator that performs crossover. Can be overridden by subclasses.
     */
    PopulationOperator getCrossoverPopulationOperator() {
	double pCrossover = getParameterAsDouble("p_crossover");
	int crossoverType = getParameterAsInt("crossover_type");
	return new SelectionCrossover(crossoverType, pCrossover, false, random);
    }

    void addPreEvaluationPopulationOperator(PopulationOperator popop) {
	preOp.add(popop);
    }

    void addPostEvaluationPopulationOperator(PopulationOperator popop) {
	postOp.add(popop);
    }

    /** The operators performs two steps
     *  <ol>
     *    <li>mutate the attribute selection
     *    <li>crossover
     *  </ol>  
     */
    public List getPreEvaluationPopulationOperators() {
	return preOp;
    }

    /** The operator performs one step:
     *  <ol>
     *    <li>roulette wheel
     *  </ol>  
     */
    public List getPostEvaluationPopulationOperators() {
	return postOp;
    }

    /** Returns true if generation is >= maximum_number_of_generations or after generations_without_improval generations 
     *  without improval.
     */
    public boolean solutionGoodEnough(Population pop) {
	return ((pop.getGeneration() >= maxGen) || (pop.getGenerationsWithoutImproval() >= generationsWithoutImproval));
    }


    public List getParameterTypes() {
	List types = super.getParameterTypes();

	types.add(new ParameterTypeInt("population_size", "Number of individuals per generation.", 1, Integer.MAX_VALUE, 5));
	types.add(new ParameterTypeInt("maximum_number_of_generations", "Number of generations after which to terminate the algorithm.", 1, Integer.MAX_VALUE, 30));
	types.add(new ParameterTypeInt("generations_without_improval", "Stop criterion: Stop after n generations without improval of the performance.", 1, Integer.MAX_VALUE, 20));	
	types.add(new ParameterTypeBoolean("keep_best_individual", "If set to true, the best individual of each generations is guaranteed to be selected for the next generation.", true));
	types.add(new ParameterTypeDouble("p_initialize", "Initial probability for an attribute to be switched on.", 0, 1, 0.5));
	types.add(new ParameterTypeDouble("p_mutation", "Probability for an individual to be selected for mutation.", 0, 1, 0.1));
	types.add(new ParameterTypeDouble("p_crossover", "Probability for an individual to be selected for crossover.", 0, 1, 0.05));
	types.add(new ParameterTypeCategory("crossover_type", "Type of the crossover.", SelectionCrossover.CROSSOVER_TYPES, SelectionCrossover.UNIFORM));
	return types;
    }
}