abstractgeneticalgorithm.java

一个很好的LIBSVM的JAVA源码。对于要研究和改进SVM算法的学者。可以参考。来自数据挖掘工具YALE工具包。

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2001-2004
 *      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.IOObject;
import edu.udo.cs.yale.operator.parameter.*;
import edu.udo.cs.yale.example.ExampleSet;
import edu.udo.cs.yale.example.AttributeWeightedExampleSet;
import edu.udo.cs.yale.operator.features.*;
import edu.udo.cs.yale.tools.RandomGenerator;

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 optimization / 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 individuals 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 population 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>
 *
 *  If the example set contains value series attributes with blocknumbers, the whole block will be switched on and off.
 *
 *  @version $Id: AbstractGeneticAlgorithm.java,v 2.4 2004/09/14 08:39:05 ingomierswa Exp $
 */
public abstract class AbstractGeneticAlgorithm extends FeatureOperator {

    private LinkedList preOp = new LinkedList();
    private LinkedList postOp = new LinkedList();

    /** 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;


    /** Returns an operator that performs the mutation. Can be overridden by subclasses. */
    protected abstract PopulationOperator getMutationPopulationOperator() throws OperatorException;

    /** Returns an operator that performs crossover. Can be overridden by subclasses. */
    protected abstract PopulationOperator getCrossoverPopulationOperator() throws OperatorException;


    public IOObject[] apply() throws OperatorException {
	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");

	// pre eval ops	
	preOp = new LinkedList();
	preOp.add(new RouletteWheel(numberOfIndividuals, keepBest));
	
	PopulationOperator crossover = getCrossoverPopulationOperator();
	if (crossover != null)
	    preOp.add(crossover);

	PopulationOperator mutation = getMutationPopulationOperator();
	if (mutation != null)
	    preOp.add(mutation);

	preOp.addAll(getPreProcessingPopulationOperators());

	// post eval ops
	postOp = new LinkedList();
	postOp.addAll(getPostProcessingPopulationOperators());

	return super.apply();
    }


    /** 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();
	int i = 0;
	while (initP.getNumberOfIndividuals() < numberOfIndividuals) {
	    AttributeWeightedExampleSet nes = new AttributeWeightedExampleSet((ExampleSet)es.clone());
	    for (int j = 0; j < nes.getNumberOfAttributes(); j++) {
		if (RandomGenerator.getGlobalRandomGenerator().nextDouble() < pInitialize)
		    j = nes.flipAttributeUsed(j);
	    }
	    if (nes.getNumberOfUsedAttributes() > 0) initP.add(nes);
	}
	return initP;
    }
    
    /** Returns an empty list. */
    protected List getPreProcessingPopulationOperators() { return new LinkedList(); }
    /** Returns an empty list. */
    protected List getPostProcessingPopulationOperators() { return new LinkedList(); }
    /** Returns the list with pre eval pop ops. */
    public final List getPreEvaluationPopulationOperators() { return preOp; }
    /** Returns the list with post eval pop ops. */
    public final 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();
	ParameterType type = 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);
	type.setExpert(false);
	types.add(type);
	type = new ParameterTypeInt("population_size", "Number of individuals per generation.", 1, Integer.MAX_VALUE, 5);
	type.setExpert(false);
	types.add(type);
	type = new ParameterTypeInt("maximum_number_of_generations", "Number of generations after which to terminate the algorithm.", 1, Integer.MAX_VALUE, 30);
	type.setExpert(false);
	types.add(type);
	type = new ParameterTypeInt("generations_without_improval", "Stop criterion: Stop after n generations without improval of the performance.", 1, Integer.MAX_VALUE, 20);
	type.setExpert(false);
	types.add(type);
	types.add(new ParameterTypeDouble("p_initialize", "Initial probability for an attribute to be switched on.", 0, 1, 0.5));
	return types;
    }
}