ga.java

clustering data for the different techniques of data mining

/*
  GA.java

  Definition of the class GA
  
  (P)2002  Dana Cristofor
  
*/

/*

GAClust - Clustering categorical databases using genetic algorithms
Copyright (C) 2002  Dana Cristofor


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

GAClust was written by Dana Cristofor ([e-mail]).

*/

import laur.tools.*;
import java.util.*;

/**
 * GA
 *
 * @version 	1.0
 * @author	Dana Cristofor
 */
public class GA extends MonitoredThread
{
  private int N;                       // number of chromosomes
  private int NROWS;                   // size of chromosomes
  // number of maximum classes in the partition
  // determined by chromosomes
  private int K;                       
  private Chromosome[] population;    // population of chromosomes
  private double[] probabilities;     // selection probabilities of chromosomes

  private int classFitnessType; // selects the type of class fitness
  private int crossoverType;    // selects the type of crossover
  private int mutationType;     // selects the type of mutation
  private int distributionType; // selects the type of distribution

  private int entropyMeasure;   // measure for fitness, can be GINI,
				// Shannon, etc
  private int distanceMeasure;

  private int noChromCrossover; // number of chromosomes to cross over
  private int noChromMutate;    // number of chromosomes to mutate

  private int[] sample;           // selected chromosomes
  private int sampleSize;        // size of the sample

  // intersection between the best chromosome and the partitions in db
  private Hashtable[]  intersectMap;

  private double bestFitness;    // fitness of best chromosome
  private int bestIndex;         // index of the most fit chromosome

  private double fitnessThreshold; // this thresholds determines if we
  // achieved the best acceptable fitness

  private int CONSEC_NITRS;       // consecutive iterations with no improvement
  
  private Partition[] db;        // database
  private int NPART;              // number of partitions in the collection db 
  private double[] weightDBTarget; // partitions weights
  private double[] weightTargetDB; // partitions weights
  private double[] weight;        // partitions weights

  private Random rand; // random generator

  private int minimization;       // 1 if minimization, 0 if maximization

  private int resType; // 0 is no results, 1 if partial results, 2 if
		       // final results
  private Chromosome finalChrom; // final chromosome representing the
				 // resulting clustering
  private int noIterations;  // final number of iterations

  GA(int N, int NROWS, int K, double crossoverPct, double mutationPct, 
     int classFitnessType, int crossoverType, int mutationType, 
     int distributionType, int entropyMeasure, int distanceMeasure, 
     int minimization, double fitnessThreshold, int CONSEC_NITRS, Random rand,
     Partition[] db, int NPART, double[] weightDBTarget, 
     double[] weightTargetDB, double[] weight, ThreadMonitor monitor)
  {
    this.N = N;
    this.NROWS = NROWS;
    this.K = K;
    // allocate space for population of chromosomes
    population = new Chromosome[N];
    for (int i = 0; i < N; i++)
      population[i] = new Chromosome(NROWS, K, classFitnessType,
				     crossoverType, mutationType, 
				     distributionType);
    
    this.classFitnessType = classFitnessType;
    this.crossoverType = crossoverType;
    this.mutationType = mutationType;
    this.distributionType = distributionType;

    // set number of chromosomes to cross over
    noChromCrossover = (int)(crossoverPct*N);
    // at least 2 chromosomes are crossed over
    if (noChromCrossover == 0)
      noChromCrossover = 2;
    else
      // make it multiple of 2  
      if (noChromCrossover % 2 != 0)
	noChromCrossover++;
    
    // set number of chromosomes to mutate
    noChromMutate = (int)(mutationPct*N);
    // at least one chromosome is mutated
    if (noChromMutate == 0)
      noChromMutate = 1;
    
    if (noChromMutate + noChromCrossover > N - 1)
      {
	System.err.println("ERROR! GA.GA(): invalid crossover and "
			   + "mutation pctgs");
	System.exit(1);
      }

    this.fitnessThreshold = fitnessThreshold;
    this.CONSEC_NITRS = CONSEC_NITRS;
    
    // initialize the radom number generator
    this.rand = rand;
    
    this.entropyMeasure = entropyMeasure;
    this.distanceMeasure = distanceMeasure;
    this.minimization = minimization;
    
    this.NPART = NPART;
    this.db = db;
    this.weightDBTarget = weightDBTarget;
    this.weightTargetDB = weightTargetDB;
    this.weight = weight;

    // allocate space for probabilities
    probabilities = new double[N];
    sample = null;              // no selection yet

    intersectMap = new Hashtable[N];
    for (int i = 0; i < N; i++)
      intersectMap[i] = new Hashtable();

    resType = 0;
    
    // set the final chromosome
    finalChrom = new Chromosome(NROWS, K, classFitnessType,
				crossoverType, mutationType, 
				distributionType);
    this.monitor = monitor;
  }

  /** randomly initializes the population of chromosomes; the
   * chromosomes will have exactly K classes */
  private void initPopulation()
  {
    for (int i = 0; i < N; i++)
      population[i].init(rand); 
  
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" Initializing population ...");
	for (int i = 0; i < N; i++)
	  population[i].printAM();

	System.out.println("database is");
	for (int i = 0; i < NPART; i++)
	  db[i].printAM();
      }
  }

  
  /** selects <code>n</code> best chromosomes with the greatest values
   * of their probabilities; places the indices corresponding to the
   * selected chromosomes in the <code>sample</code> field; make the
   * field <code>sampleSize = n</code>*/
  private void selectBest(int n)
  {
    sampleSize = n ;
    
    // create new sample
    sample = new int[sampleSize];

    double[] fitnessValues = new double[N];
    for (int i = 0; i < N; i++)
      fitnessValues[i] = population[i].getFitness();
  
    SelectionMethods.selectBest(fitnessValues, N, minimization, 
				sample, sampleSize);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("Best selection");
	for (int i = 0; i < sampleSize; i++)
	  System.out.println(sample[i] + " " 
			     + population[sample[i]].getFitness());
      }
  }

  
  /** selects <code>n</code> chromosomes with uniform probability;
   * places the indices corresponding to the selected chromosomes in
   * the field <code>sample</code>; makes the field <code>sampleSize =
   * n</code> */
  private void selectUnif(int n)
  {
    sampleSize = n ;

    // create new sample
    sample = new int[sampleSize];
    SelectionMethods.selectUnif(N, sample, sampleSize, rand);
  }


  /** selects <code>n</code> chromosomes based on their probabilities;
   * places the indices corresponding to the selected chromosomes in
   * the field <code>sample</code>; makes the field <code>sampleSize =
   * n</code> */
  private void selectProb(int n)
  {
    // compute chromosome selection probabilities based on their fitness
    computeProbabilities();
    
    sampleSize = n;

    // create new sample
    sample = new int[sampleSize];
    SelectionMethods.selectProb(N, probabilities, sample, sampleSize, rand);
  }

  /** computes the cumulated probabilities associated with the
   * chromosomes in the population these probabilities are used in the
   * probabilistic selection of some chromosomes */
  private void computeProbabilities()
  {
    if (Global.VERBOSE == 1)
      System.out.println(" Computing probabilities ...");
  
    // fitness[i] is guaranteed not 
    // to be zero at this point
    double overallProb = 0.0;
    for (int j = 0; j < N; j++)
      {
	if (minimization == 1)
	  // make the smallest fitness value to have the greatest probability
	  probabilities[j] = 1.0 / population[j].getFitness();
	else
	  probabilities[j] = population[j].getFitness();
	
	overallProb += probabilities[j];
      }
  
    // make them real probabilities
    // with sum equal to 1
    for (int j = 0; j < N; j++)
      probabilities[j] /= overallProb;
    
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("prob before cumulation ");
	for (int j = 0; j < N; j++)
	  System.out.print(probabilities[j] + " ");
	System.out.println();
      }
    
    // finally we cumulate the probabilities 
    // in order to make it easier
    // to select one item randomly
    for (int j = 1; j < N - 1; j++)
      probabilities[j] += probabilities[j - 1];
    probabilities[N - 1] = 1.0;

    if (Global.ULTRA_VERBOSE == 1)
      { 
	System.out.println("prob after cumulation ");
	for (int j = 0; j < N; j++)
	  System.out.print(probabilities[j] + " ");
	System.out.println();
      }
  }

  /** selects <code>ncross</code> members of the population to
   * crossover based on the members probabilities; pair
   * <code>(sample[i], sample[i+1])</code> will be used to generate
   * offsprings by crossover */
  private void selectToCrossover()
  {
    if (Global.VERBOSE == 1)
      System.out.println(" Selecting to crossover ...");

    selectProb(noChromCrossover);

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