geneticsearch.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

	  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
   * @exception 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;
      }
    }
    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
   * @exception 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
   * @exception 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;
  }
}