geneticalgorithm.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.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.
 *
 *  @yale.xmlclass GeneticAlgorithm
 *  @version $Id: GeneticAlgorithm.java,v 2.22 2004/08/27 11:57:36 ingomierswa Exp $
 */
public class GeneticAlgorithm extends AbstractGeneticAlgorithm {

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

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

    public List getParameterTypes() {
	List types = super.getParameterTypes();
	ParameterType type = new ParameterTypeDouble("p_mutation", 
						     "Probability for an attribute to be changed (-1: 1 / numberOfAtt).", 
						     -1.0d, 1.0d, 0.1d);
	type.setExpert(false);
	types.add(type);
	type = new ParameterTypeDouble("p_crossover", 
				       "Probability for an individual to be selected for crossover.", 
				       0.0d, 1.0d, 0.5d);
	type.setExpert(false);
	types.add(type);
	types.add(new ParameterTypeCategory("crossover_type", 
					    "Type of the crossover.", 
					    SelectionCrossover.CROSSOVER_TYPES, 
					    SelectionCrossover.UNIFORM));
	return types;
    }
}