geneticsearch.java

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

    if (m_maxFitness - m_minFitness > 0) {
      // find the best in this population
      for (i=0;i<m_popSize;i++) {
        if (m_population[i].getObjective() > b) {
          b = m_population[i].getObjective();
          localbest = m_population[i];
          oldcount = countFeatures(localbest.getChromosome());
        } else if (Utils.eq(m_population[i].getObjective(), b)) {
          // see if it contains fewer features
          count = countFeatures(m_population[i].getChromosome());
          if (count < oldcount) {
            b = m_population[i].getObjective();
            localbest = m_population[i];
            oldcount = count;
          }
        }
      }
    } else {
      // look for the smallest subset
      for (i=0;i<m_popSize;i++) {
        temp = m_population[i].getChromosome();
        count = countFeatures(temp);;

        if (count < lowestCount) {
          lowestCount = count;
          localbest = m_population[i];
          b = localbest.getObjective();
        }
      }
      converged = true;
    }

    // count the number of features in localbest
    count = 0;
    temp = localbest.getChromosome();
    count = countFeatures(temp);

    // compare to the best found so far
    if (m_best == null) {
      m_best = (GABitSet)localbest.clone();
      m_bestFeatureCount = count;
    } else if (b > m_best.getObjective()) {
      m_best = (GABitSet)localbest.clone();
      m_bestFeatureCount = count;
    } else if (Utils.eq(m_best.getObjective(), b)) {
      // see if the localbest has fewer features than the best so far
      if (count < m_bestFeatureCount) {
        m_best = (GABitSet)localbest.clone();
        m_bestFeatureCount = count;
      }
    }
    return converged;
  }

  /**
   * counts the number of features in a subset
   * @param featureSet the feature set for which to count the features
   * @return the number of features in the subset
   */
  private int countFeatures(BitSet featureSet) {
    int count = 0;
    for (int i=0;i<m_numAttribs;i++) {
      if (featureSet.get(i)) {
        count++;
      }
    }
    return count;
  }

  /**
   * performs a single generation---selection, crossover, and mutation
   * @throws Exception if an error occurs
   */
  private void generation () throws Exception {
    int i,j=0;
    double best_fit = -Double.MAX_VALUE;
    int old_count = 0;
    int count;
    GABitSet [] newPop = new GABitSet [m_popSize];
    int parent1,parent2;

    /** first ensure that the population best is propogated into the new
        generation */
    for (i=0;i<m_popSize;i++) {
      if (m_population[i].getFitness() > best_fit) {
        j = i;
        best_fit = m_population[i].getFitness();
        old_count = countFeatures(m_population[i].getChromosome());
      } else if (Utils.eq(m_population[i].getFitness(), best_fit)) {
        count = countFeatures(m_population[i].getChromosome());
        if (count < old_count) {
          j = i;
          best_fit = m_population[i].getFitness();
          old_count = count;
        }
      }
    }
    newPop[0] = (GABitSet)(m_population[j].clone());
    newPop[1] = newPop[0];

    for (j=2;j<m_popSize;j+=2) {
      parent1 = select();
      parent2 = select();
      newPop[j] = (GABitSet)(m_population[parent1].clone());
      newPop[j+1] = (GABitSet)(m_population[parent2].clone());
      // if parents are equal mutate one bit
      if (parent1 == parent2) {
        int r;
        if (m_hasClass) {
          while ((r = (Math.abs(m_random.nextInt()) % m_numAttribs)) == m_classIndex);
        }
        else {
          r = m_random.nextInt() % m_numAttribs;
        }
        
        if (newPop[j].get(r)) {
          newPop[j].clear(r);
        }
        else {
          newPop[j].set(r);
        }
      } else {
        // crossover
        double r = m_random.nextDouble();
        if (m_numAttribs >= 3) {
          if (r < m_pCrossover) {
            // cross point
            int cp = Math.abs(m_random.nextInt());
            
            cp %= (m_numAttribs-2);
            cp ++;
            
            for (i=0;i<cp;i++) {
              if (m_population[parent1].get(i)) {
                newPop[j+1].set(i);
              }
              else {
                newPop[j+1].clear(i);
              }
              if (m_population[parent2].get(i)) {
                newPop[j].set(i);
              }
              else {
                newPop[j].clear(i);
              }
            }
          }
        }

        // mutate
        for (int k=0;k<2;k++) {
          for (i=0;i<m_numAttribs;i++) {
            r = m_random.nextDouble();
            if (r < m_pMutation) {
              if (m_hasClass && (i == m_classIndex)) {
                // ignore class attribute
              }
              else {
                if (newPop[j+k].get(i)) {
                  newPop[j+k].clear(i);
                }
                else {
                  newPop[j+k].set(i);
                }
              }
            }
          }
        }
                  
      }
    }

    m_population = newPop;
  }

  /**
   * selects a population member to be considered for crossover
   * @return the index of the selected population member
   */
  private int select() {
    int i;
    double r,partsum;

    partsum = 0;
    r = m_random.nextDouble() * m_sumFitness;
    for (i=0;i<m_popSize;i++) {
      partsum += m_population[i].getFitness();
      if (partsum >= r) {
        break;
      }
    }
    
    // if none was found, take first
    if (i == m_popSize)
      i = 0;
    
    return i;
  }

  /**
   * evaluates an entire population. Population members are looked up in
   * a hash table and if they are not found then they are evaluated using
   * ASEvaluator.
   * @param ASEvaluator the subset evaluator to use for evaluating population
   * members
   * @throws Exception if something goes wrong during evaluation
   */
  private void evaluatePopulation (SubsetEvaluator ASEvaluator)
    throws Exception {
    int i;
    double merit;

    for (i=0;i<m_popSize;i++) {
      // if its not in the lookup table then evaluate and insert
      if (m_lookupTable.containsKey(m_population[i]
                                    .getChromosome()) == false) {
        merit = ASEvaluator.evaluateSubset(m_population[i].getChromosome());
        m_population[i].setObjective(merit);
        m_lookupTable.put(m_population[i].getChromosome(),m_population[i]);
      } else {
        GABitSet temp = (GABitSet)m_lookupTable.
          get(m_population[i].getChromosome());
        m_population[i].setObjective(temp.getObjective());
      }
    }
  }

  /**
   * creates random population members for the initial population. Also
   * sets the first population member to be a start set (if any) 
   * provided by the user
   * @throws Exception if the population can't be created
   */
  private void initPopulation () throws Exception {
    int i,j,bit;
    int num_bits;
    boolean ok;
    int start = 0;

    // add the start set as the first population member (if specified)
    if (m_starting != null) {
      m_population[0] = new GABitSet();
      for (i=0;i<m_starting.length;i++) {
        if ((m_starting[i]) != m_classIndex) {
          m_population[0].set(m_starting[i]);
        }
      }
      start = 1;
    }

    for (i=start;i<m_popSize;i++) {
      m_population[i] = new GABitSet();
      
      num_bits = m_random.nextInt();
      num_bits = num_bits % m_numAttribs-1;
      if (num_bits < 0) {
        num_bits *= -1;
      }
      if (num_bits == 0) {
        num_bits = 1;
      }

      for (j=0;j<num_bits;j++) {
        ok = false;
        do {
          bit = m_random.nextInt();
          if (bit < 0) {
            bit *= -1;
          }
          bit = bit % m_numAttribs;
          if (m_hasClass) {
            if (bit != m_classIndex) {
              ok = true;
            }
          }
          else {
            ok = true;
          }
        } while (!ok);
        
        if (bit > m_numAttribs) {
          throw new Exception("Problem in population init");
        }
        m_population[i].set(bit);
      }
    }
  }

  /**
   * calculates summary statistics for the current population
   */
  private void populationStatistics() {
    int i;
    
    m_sumFitness = m_minFitness = m_maxFitness = 
      m_population[0].getObjective();

    for (i=1;i<m_popSize;i++) {
      m_sumFitness += m_population[i].getObjective();
      if (m_population[i].getObjective() > m_maxFitness) {
        m_maxFitness = m_population[i].getObjective();
      }
      else if (m_population[i].getObjective() < m_minFitness) {
        m_minFitness = m_population[i].getObjective();
      }
    }
    m_avgFitness = (m_sumFitness / m_popSize);
  }

  /**
   * scales the raw (objective) merit of the population members
   */
  private void scalePopulation() {
    int j;
    double a = 0;
    double b = 0;
    double fmultiple = 2.0;
    double delta;
    
    // prescale
    if (m_minFitness > ((fmultiple * m_avgFitness - m_maxFitness) / 
                        (fmultiple - 1.0))) {
      delta = m_maxFitness - m_avgFitness;
      a = ((fmultiple - 1.0) * m_avgFitness / delta);
      b = m_avgFitness * (m_maxFitness - fmultiple * m_avgFitness) / delta;
    }
    else {
      delta = m_avgFitness - m_minFitness;
      a = m_avgFitness / delta;
      b = -m_minFitness * m_avgFitness / delta;
    }
      
    // scalepop
    m_sumFitness = 0;
    for (j=0;j<m_popSize;j++) {
      if (a == Double.POSITIVE_INFINITY || a == Double.NEGATIVE_INFINITY ||
          b == Double.POSITIVE_INFINITY || b == Double.NEGATIVE_INFINITY) {
        m_population[j].setFitness(m_population[j].getObjective());
      } else {
        m_population[j].
          setFitness(Math.abs((a * m_population[j].getObjective() + b)));
      }
      m_sumFitness += m_population[j].getFitness();
    }
  }
  
  /**
   * generates a report on the current population
   * @return a report as a String
   */
  private String populationReport (int genNum) {
    int i;
    StringBuffer temp = new StringBuffer();

    if (genNum == 0) {
      temp.append("\nInitial population\n");
    }
    else {
      temp.append("\nGeneration: "+genNum+"\n");
    }
    temp.append("merit   \tscaled  \tsubset\n");
    
    for (i=0;i<m_popSize;i++) {
      temp.append(Utils.doubleToString(Math.
                                       abs(m_population[i].getObjective()),
                                       8,5)
                  +"\t"
                  +Utils.doubleToString(m_population[i].getFitness(),
                                        8,5)
                  +"\t");

      temp.append(printPopMember(m_population[i].getChromosome())+"\n");
    }
    return temp.toString();
  }

  /**
   * prints a population member as a series of attribute numbers
   * @param temp the chromosome of a population member
   * @return a population member as a String of attribute numbers
   */
  private String printPopMember(BitSet temp) {
    StringBuffer text = new StringBuffer();

    for (int j=0;j<m_numAttribs;j++) {
      if (temp.get(j)) {
        text.append((j+1)+" ");
      }
    }
    return text.toString();
  }

  /**
   * prints a population member's chromosome
   * @param temp the chromosome of a population member
   * @return a population member's chromosome as a String
   */
  private String printPopChrom(BitSet temp) {
    StringBuffer text = new StringBuffer();

    for (int j=0;j<m_numAttribs;j++) {
      if (temp.get(j)) {
        text.append("1");
      } else {
        text.append("0");
      }
    }
    return text.toString();
  }

  /**
   * reset to default values for options
   */
  private void resetOptions () {
    m_population = null;
    m_popSize = 20;
    m_lookupTableSize = 1001;
    m_pCrossover = 0.6;
    m_pMutation = 0.033;
    m_maxGenerations = 20;
    m_reportFrequency = m_maxGenerations;
    m_starting = null;
    m_startRange = new Range();
    m_seed = 1;
  }
}