geneticsearch.java

这是关于数据挖掘的一些算法

/*
 *    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., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    GeneticSearch.java
 *    Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
 *
 */

package  weka.attributeSelection;

import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.Range;
import weka.core.TechnicalInformation;
import weka.core.TechnicalInformation.Type;
import weka.core.TechnicalInformation.Field;
import weka.core.TechnicalInformationHandler;
import weka.core.Utils;

import java.io.Serializable;
import java.util.BitSet;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Random;
import java.util.Vector;

/** 
 <!-- globalinfo-start -->
 * GeneticSearch:<br/>
 * <br/>
 * Performs a search using the simple genetic algorithm described in Goldberg (1989).<br/>
 * <br/>
 * For more information see:<br/>
 * <br/>
 * David E. Goldberg (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley.
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- technical-bibtex-start -->
 * BibTeX:
 * <pre>
 * &#64;book{Goldberg1989,
 *    author = {David E. Goldberg},
 *    publisher = {Addison-Wesley},
 *    title = {Genetic algorithms in search, optimization and machine learning},
 *    year = {1989},
 *    ISBN = {0201157675}
 * }
 * </pre>
 * <p/>
 <!-- technical-bibtex-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -P &lt;start set&gt;
 *  Specify a starting set of attributes.
 *  Eg. 1,3,5-7.If supplied, the starting set becomes
 *  one member of the initial random
 *  population.</pre>
 * 
 * <pre> -Z &lt;population size&gt;
 *  Set the size of the population.
 *  (default = 10).</pre>
 * 
 * <pre> -G &lt;number of generations&gt;
 *  Set the number of generations.
 *  (default = 20)</pre>
 * 
 * <pre> -C &lt;probability of crossover&gt;
 *  Set the probability of crossover.
 *  (default = 0.6)</pre>
 * 
 * <pre> -M &lt;probability of mutation&gt;
 *  Set the probability of mutation.
 *  (default = 0.033)</pre>
 * 
 * <pre> -R &lt;report frequency&gt;
 *  Set frequency of generation reports.
 *  e.g, setting the value to 5 will 
 *  report every 5th generation
 *  (default = number of generations)</pre>
 * 
 * <pre> -S &lt;seed&gt;
 *  Set the random number seed.
 *  (default = 1)</pre>
 * 
 <!-- options-end -->
 *
 * @author Mark Hall ([e-mail])
 * @version $Revision: 1.18 $
 */
public class GeneticSearch 
  extends ASSearch 
  implements StartSetHandler, OptionHandler, TechnicalInformationHandler {

  /** for serialization */
  static final long serialVersionUID = -1618264232838472679L;
  
  /** 
   * holds a starting set as an array of attributes. Becomes one member of the
   * initial random population
   */
  private int[] m_starting;

  /** holds the start set for the search as a Range */
  private Range m_startRange;
  
 /** does the data have a class */
  private boolean m_hasClass;
 
  /** holds the class index */
  private int m_classIndex;
 
  /** number of attributes in the data */
  private int m_numAttribs;

  /** the current population */
  private GABitSet [] m_population;

  /** the number of individual solutions */
  private int m_popSize;

  /** the best population member found during the search */
  private GABitSet m_best;

  /** the number of features in the best population member */
  private int m_bestFeatureCount;

  /** the number of entries to cache for lookup */
  private int m_lookupTableSize;

  /** the lookup table */
  private Hashtable m_lookupTable;

  /** random number generation */
  private Random m_random;

  /** seed for random number generation */
  private int m_seed;

  /** the probability of crossover occuring */
  private double m_pCrossover;

  /** the probability of mutation occuring */
  private double m_pMutation;

  /** sum of the current population fitness */
  private double m_sumFitness;

  private double m_maxFitness;
  private double m_minFitness;
  private double m_avgFitness;

  /** the maximum number of generations to evaluate */
  private int m_maxGenerations;

  /** how often reports are generated */
  private int m_reportFrequency;

  /** holds the generation reports */
  private StringBuffer m_generationReports;

  // Inner class
  /**
   * A bitset for the genetic algorithm
   */
  protected class GABitSet 
    implements Cloneable, Serializable {
    
    /** for serialization */
    static final long serialVersionUID = -2930607837482622224L;
    
    /** the bitset */
    private BitSet m_chromosome;

    /** holds raw merit */
    private double m_objective = -Double.MAX_VALUE;
    
    /** the fitness */
    private double m_fitness;
    
    /**
     * Constructor
     */
    public GABitSet () {
      m_chromosome = new BitSet();
    }

    /**
     * makes a copy of this GABitSet
     * @return a copy of the object
     * @throws CloneNotSupportedException if something goes wrong
     */
    public Object clone() throws CloneNotSupportedException {
      GABitSet temp = new GABitSet();
      
      temp.setObjective(this.getObjective());
      temp.setFitness(this.getFitness());
      temp.setChromosome((BitSet)(this.m_chromosome.clone()));
      return temp;
      //return super.clone();
    }

    /**
     * sets the objective merit value
     * @param objective the objective value of this population member
     */
    public void setObjective(double objective) {
      m_objective = objective;
    }
      
    /**
     * gets the objective merit
     * @return the objective merit of this population member
     */
    public double getObjective() {
      return m_objective;
    }

    /**
     * sets the scaled fitness
     * @param fitness the scaled fitness of this population member
     */
    public void setFitness(double fitness) {
      m_fitness = fitness;
    }

    /**
     * gets the scaled fitness
     * @return the scaled fitness of this population member
     */
    public double getFitness() {
      return m_fitness;
    }

    /**
     * get the chromosome
     * @return the chromosome of this population member
     */
    public BitSet getChromosome() {
      return m_chromosome;
    }

    /**
     * set the chromosome
     * @param c the chromosome to be set for this population member
     */
    public void setChromosome(BitSet c) {
      m_chromosome = c;
    }

    /**
     * unset a bit in the chromosome
     * @param bit the bit to be cleared
     */
    public void clear(int bit) {
      m_chromosome.clear(bit);
    }

    /**
     * set a bit in the chromosome
     * @param bit the bit to be set
     */
    public void set(int bit) {
      m_chromosome.set(bit);
    }

    /**
     * get the value of a bit in the chromosome
     * @param bit the bit to query
     * @return the value of the bit
     */
    public boolean get(int bit) {
      return m_chromosome.get(bit);
    }
  }

  /**
   * Returns an enumeration describing the available options.
   * @return an enumeration of all the available options.
   **/
  public Enumeration listOptions () {
    Vector newVector = new Vector(6);

    newVector.addElement(new Option("\tSpecify a starting set of attributes." 
                                    + "\n\tEg. 1,3,5-7."
                                    +"If supplied, the starting set becomes"
                                    +"\n\tone member of the initial random"
                                    +"\n\tpopulation."
                                    ,"P",1
                                    , "-P <start set>"));
    newVector.addElement(new Option("\tSet the size of the population."
                                    +"\n\t(default = 10)."
                                    , "Z", 1
                                    , "-Z <population size>"));
    newVector.addElement(new Option("\tSet the number of generations."
                                    +"\n\t(default = 20)" 
                                    , "G", 1, "-G <number of generations>"));
    newVector.addElement(new Option("\tSet the probability of crossover."
                                    +"\n\t(default = 0.6)" 
                                    , "C", 1, "-C <probability of"
                                    +" crossover>"));    
    newVector.addElement(new Option("\tSet the probability of mutation."
                                    +"\n\t(default = 0.033)" 
                                    , "M", 1, "-M <probability of mutation>"));

    newVector.addElement(new Option("\tSet frequency of generation reports."
                                    +"\n\te.g, setting the value to 5 will "
                                    +"\n\treport every 5th generation"
                                    +"\n\t(default = number of generations)" 
                                    , "R", 1, "-R <report frequency>"));
    newVector.addElement(new Option("\tSet the random number seed."
                                    +"\n\t(default = 1)" 
                                    , "S", 1, "-S <seed>"));
    return  newVector.elements();
  }

  /**
   * Parses a given list of options. <p/>
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -P &lt;start set&gt;
   *  Specify a starting set of attributes.
   *  Eg. 1,3,5-7.If supplied, the starting set becomes
   *  one member of the initial random
   *  population.</pre>
   * 
   * <pre> -Z &lt;population size&gt;
   *  Set the size of the population.
   *  (default = 10).</pre>
   * 
   * <pre> -G &lt;number of generations&gt;
   *  Set the number of generations.
   *  (default = 20)</pre>
   * 
   * <pre> -C &lt;probability of crossover&gt;
   *  Set the probability of crossover.
   *  (default = 0.6)</pre>
   * 
   * <pre> -M &lt;probability of mutation&gt;
   *  Set the probability of mutation.
   *  (default = 0.033)</pre>
   * 
   * <pre> -R &lt;report frequency&gt;
   *  Set frequency of generation reports.
   *  e.g, setting the value to 5 will 
   *  report every 5th generation
   *  (default = number of generations)</pre>
   * 
   * <pre> -S &lt;seed&gt;
   *  Set the random number seed.
   *  (default = 1)</pre>
   * 
   <!-- options-end -->
   *
   * @param options the list of options as an array of strings
   * @throws Exception if an option is not supported
   *
   **/
  public void setOptions (String[] options)
    throws Exception {
    String optionString;
    resetOptions();

    optionString = Utils.getOption('P', options);
    if (optionString.length() != 0) {
      setStartSet(optionString);
    }

    optionString = Utils.getOption('Z', options);
    if (optionString.length() != 0) {
      setPopulationSize(Integer.parseInt(optionString));
    }

    optionString = Utils.getOption('G', options);
    if (optionString.length() != 0) {
      setMaxGenerations(Integer.parseInt(optionString));
      setReportFrequency(Integer.parseInt(optionString));
    }

    optionString = Utils.getOption('C', options);
    if (optionString.length() != 0) {
      setCrossoverProb((new Double(optionString)).doubleValue());
    }

    optionString = Utils.getOption('M', options);
    if (optionString.length() != 0) {
      setMutationProb((new Double(optionString)).doubleValue());
    }

    optionString = Utils.getOption('R', options);
    if (optionString.length() != 0) {
      setReportFrequency(Integer.parseInt(optionString));
    }

    optionString = Utils.getOption('S', options);
    if (optionString.length() != 0) {
      setSeed(Integer.parseInt(optionString));
    }
  }

  /**
   * Gets the current settings of ReliefFAttributeEval.
   *
   * @return an array of strings suitable for passing to setOptions()
   */
  public String[] getOptions () {
    String[] options = new String[14];
    int current = 0;