ga.java

clustering data for the different techniques of data mining

  /** selects <code>nChromMutate</code> chromosomes from population to
   * be subject to mutation */
  private void selectToMutate()
  {
    if (Global.VERBOSE == 1)
      System.out.println(" Selecting to mutate ...");
    
    selectUnif(noChromMutate);
    
    if (Global.VERBOSE == 1)
      {
	// in sample we have the selection
	System.out.print("selected: ");
	for (int i = 0; i < sampleSize; i++)
	  System.out.println(sample[i] + " ");
	System.out.println();
      }
  }


  /** selects <code>N - noChromCrossover - noChromMutate</code> members
   * of the population to propagate directly in the next generation;
   * selection is based on the best values of the fitness */
  private void selectToPropagate()
  {
    if (Global.VERBOSE == 1)
      System.out.println(" Selecting to propagate ...");
      
    //  selectProb(N - no_chrom_crossover - no_chrom_mutate);
    selectBest(N - noChromCrossover - noChromMutate);

    if (Global.VERBOSE == 1)
      {
	// in sample we have the selection
	System.out.print("selected: ");
	for (int i = 0; i < sampleSize; i++)
	  System.out.print(sample[i] + " ");
	System.out.println();
      }
  }

  /** computes most fit chromosome and its best value of fitness in
   * the current population */
  private void findBestFitness()
  {
    bestFitness = population[0].getFitness();
    bestIndex = 0;
  
    double diff;
    for (int j = 0; j < N; j++)
      {
	diff = population[j].getFitness() - bestFitness;
	if ((minimization == 1 ? diff < 0: diff > 0))
	  {
	    bestFitness = population[j].getFitness();
	    bestIndex = j;
	  }
      }
  }

  /** executes the evolve method */
  protected void execute()
  {
    evolve();
  } 

  /** starts the evolution process; computes the final chromosome and
   * the final number of iterations */
  protected void evolve()
  {
    resType = 0;
    // randomly initialize the population of chromosomes
    initPopulation();

    // check for user-requested abort
    checkAbort();

    if (Global.ULTRA_VERBOSE == 1)
      for (int i = 0; i < N; i++)
	population[i].print();

    // define and allocate space for next population
    Chromosome[] nextPopulation = new Chromosome[N];
    for (int i = 0; i < N; i++)
      nextPopulation[i] = 
	new Chromosome(NROWS, K, classFitnessType,
		       crossoverType, mutationType, distributionType);

    // old best value or fitness
    double oldBestFitness = 0;
    // will hold difference between best fitnesses computed in 2
    // successive steps
    double deltaBestFitness;
    
    int startPos = 0; // index in population starting with which
    // the fitness values should be recomputed

    noIterations = 0;
    int count = 0; // counts iterations with no improvement

    while (true)
      {
	noIterations++;

	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.println("Iteration no. " + noIterations);
	    for (int i = 0; i < N; i++)
	      population[i].printClassCardinalities();
	  }

	// remember the old best value of fitness
	oldBestFitness = bestFitness;

	// compute fitness and class fitness 
	// of the chromosomes in the population
	// for the first time use traditional computation
	Chromosome[] tempArray = new Chromosome[N-startPos];
	for (int i = 0; i < N-startPos; i++)
	  tempArray[i] = population[startPos + i];

	if (noIterations == 1)
	  Chromosome.computeFitnessValues(tempArray,
					  N - startPos, 
					  db, NPART, 
					  entropyMeasure, distanceMeasure,
					  weightDBTarget, weightTargetDB, 
					  weight);
	else
	  {
	    // set the intersectMap for best Chromosome
	    for (int i = 0; i < N; i++)
	      intersectMap[i].clear();
	    Partition.computeIntersections(population[0], db, NPART, 
					   intersectMap);

	    // use the efficient computation
	    Chromosome.computeFitnessValues(population[0], intersectMap,
					    db, NPART, 
					    tempArray,
					    N - startPos,	
					    entropyMeasure, distanceMeasure,
					    weightDBTarget, weightTargetDB, 
					    weight);
	  }

	// check for user-requested abort
	checkAbort();

	// compute most fit chromosome and its best value of fitness
	findBestFitness();

	// check for user-requested abort
	checkAbort();
	
	if (noIterations > 1)
	  {
	    deltaBestFitness = bestFitness - oldBestFitness;
	    // oldBestFitness >= bestFitness
	    if (minimization == 1 ? deltaBestFitness < 0.0 
		: deltaBestFitness > 0.0) 
	      count = 0;
	    else
	      // if this iteration was "similar" to 
	      // the previous one increment count
	      count++; 
	  }
	
	// we found a population good enough or
	// the populations did not improve in CONSEC_NITRS iterations
	// exit
	if (count >= CONSEC_NITRS)
	  break;
	
	if (minimization == 1 ? bestFitness < fitnessThreshold 
	    : bestFitness > fitnessThreshold)
	  break;
	
	if (Global.VERBOSE == 1)
	  {
	    System.out.println();
	    System.out.print("******* Another step in evolution ");
	    System.out.println(noIterations + " *******");
	    System.out.println("best fitness " + bestFitness);
	  }

	if (Global.VERBOSE == 1)
	  System.out.println(noIterations + " " + count + " " + bestFitness);

	int index = 0;
	
	// PROPAGATION
	// select chromosomes that will propagate
	// without modifications to the next generation
	selectToPropagate();
	
	// copy these chromosomes to the next generation
	// sample_size represents the number of selections in sample
	for (int i = 0 ; i < sampleSize; i++, index++)
	  nextPopulation[index].set(population[sample[i]]);

	// check for user-requested abort
	checkAbort();

	// position from where the fitness will be computed
	// sample_size chromosomes are from old generation
	startPos = sampleSize;

	// CROSSOVER
	// selects the chromosomes that will be used for crossover
	selectToCrossover();
	
	// performs the crossover according to crossoverType
	// in sample we have the pairs sample[i], sample[i+1]
	// that we will use to crossover
	for (int i = 0; i < sampleSize - 1; i += 2)
	  {
	    //	    System.out.println("Before cross " + population[sample[i]].getNoClasses());
	    // population[sample[i]].print();
	    // population[sample[i]].printClassCardinalities();
	    population[sample[i]].crossover(population[sample[i+1]], rand);
	    // System.out.println("After cross " + population[sample[i]].getNoClasses());
	    // population[sample[i]].print();
	    // population[sample[i]].printClassCardinalities();
	  }

	// copy these chromosomes to the next generation
	// sampleSize represents the number of selections in sample
	for (int i = 0 ; i < sampleSize; i++, index++)
	  nextPopulation[index].set(population[sample[i]]);

	// check for user-requested abort
	checkAbort();
	
	// MUTATION
	// selects <nm> members of the population
	// with uniform probability to be subject to mutation
	selectToMutate();
	
	// performs the mutation according to mutation type
	for (int i = 0; i < sampleSize; i++)
	  {
	    //	    System.out.println("Before mut " + population[sample[i]].getNoClasses());
	    // population[sample[i]].print();
	    population[sample[i]].mutate(rand);
	    // System.out.println("After mut " + population[sample[i]].getNoClasses());
	    // population[sample[i]].print();
	  }
	// copy these chromosomes to the next generation
	// sampleSize represents the number of selections in sample
	for (int i = 0 ; i < sampleSize; i++, index++)
	  nextPopulation[index].set(population[sample[i]]);

	// check for user-requested abort
	checkAbort();
	
	// replace the old generation
	for (int i = 0; i < N; i++)
	  population[i].set(nextPopulation[i]);

	// once we computed the best chromosomes in current population
	// we have partial results
	resType = 1;

	// check for user-requested abort
	checkAbort();
	
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    for (int i = 0; i < N; i++)
	      {
		System.out.print("chrom " + i + " no classes " + population[i].getNoClasses() + " ");
		population[i].printAM();
	      }
	    System.out.println();

	    for (int j = 0; j < N; j++)
	      {
		System.out.print(population[j].getNoClasses() + " ");
		population[j].printClassCardinalities();
		System.out.println(" " + population[j].getFitness());
	      }
	    System.out.println();
	  }
      }

    finalChrom.set(population[bestIndex]);
    resType = 2;
  }

  /** returns partial or final results */
  public Vector getResults()
  {
    if (isRunning)
      throw new IllegalStateException("thread still running");

    if (resType == 0)
      throw new IllegalStateException("thread was never run");

    Vector v = new Vector(2);
    if (resType == 1)
      // we have partial results
      v.insertElementAt(population[0], 0);
    else // if (resType == 2)
      v.insertElementAt(finalChrom, 0);
    
    v.insertElementAt(new Integer(noIterations), 1);
    return v;
  }

  /** returns true if the results are final, false otherwise */
  public boolean areResultsFinal()
  {
    return resType == 2;
  }

    /** returns true if the results are partial, false otherwise */
  public boolean areResultsPartial()
  {
    return resType == 1;
  }
}