chromosome.java

clustering data for the different techniques of data mining

/*
   Chromosome.java

   Definition of the class Chromosome

   (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 java.util.*;

/**
 * Chromosome
 *
 * @version 	1.0
 * @author	Dana Cristofor
 */
public class Chromosome extends Partition
{
  protected int crossoverType;
  protected int mutationType;
  protected int distributionType;

  // crossover method types
  // random crossover
  static public final int CROSS_RAND              = 11;
  // exchanging two random classes
  static public final int CROSS_X_2RAND_CLASS     = 12;
  // exchanging best classes
  static public final int CROSS_AM_X_BEST_CLASS   = 13;
  // exchanging best worst classes
  static public final int CROSS_AM_X_BEST_WORST   = 14;
  // exchanging two random classes
  static public final int CROSS_AM_X_2RAND_CLASS  = 15;

  // mutation method types
  static public final int MUT_RAND      = 21;  // random mutation
  static public final int MUT_MOVE_ELEM = 22;  // move elements between classes
  static public final int MUT_SWAP_ELEM = 23;  // swap elements between classes

  // types of methods for distributing elements to classes
  static public final int DISTRIB_NONE    = 31;
  static public final int DISTRIB_RAND    = 32;
  static public final int DISTRIB_TO_EVEN = 33;  

  Chromosome(int size, int nc, int classFitnessType, 
	     int crossoverType, int mutationType, int distributionType)
  {
    super(size, nc, classFitnessType);
    this.crossoverType = crossoverType;
    this.mutationType = mutationType;
    this.distributionType = distributionType;
  }

  /** @return the crossover type */
  public int getCrossoverType()
  {
    return crossoverType;
  }

  /** @return the mutation type */
  public int getMutationType()
  {
    return mutationType;
  }

  /** @return the distribution type */
  public int getDistributionType()
  {
    return distributionType;
  }

  /** computes the fitness of the chromosome and the fitness of the
   * classes for chromosomes in the collection <code>c1</code>
   * relative to the partitions in the collection <code>c2</code>;
   * <code>N1</code> is the size of the collection <code>c1</code>;
   * <code>N2</code> represents the number of partitions in
   * <code>c2</code> **/
  static public void computeFitnessValues(Chromosome[] c1, int N1,
					  Partition[] c2, int N2, 
					  int entropyMeasure, 
					  int fitnessMeasure,
					  double[] weightDBTarget,
					  double[] weightTargetDB,
					  double[] weight)
  {
    for (int i = 0; i < N1; i++)
      c1[i].computeFitness(c2, N2, 
			   entropyMeasure, fitnessMeasure, 
			   weightDBTarget, weightTargetDB, weight);
  }

  /** computes fitness value of chromosomes in collection
   * <code>c1</code> based on the fitness value of chromosome
   * <code>chrom1</code> and on the intersection between
   * <code>chrom1</code> and the collection of <code>N</code>
   * partitions in <code>db</code> */
  static public void computeFitnessValues(Chromosome chrom1, 
					  Hashtable[] intersectMap,
					  Partition[] db, int N, 
					  Chromosome[] c1, int N1,
					  int entropyMeasure, 
					  int fitnessMeasure,
					  double[] weightDBTarget,
					  double[] weightTargetDB,
					  double[] weight)
  {
    for (int i = 0; i < N1; i++)
      {
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.println("working on chromosome " + i);
	    System.out.println("best chrom fitness " + chrom1.getFitness());
	  }

	computeFitnessValue(chrom1, intersectMap,
			    db, N, c1[i],
			    entropyMeasure, fitnessMeasure, 
			    weightDBTarget, weightTargetDB, weight);
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("chromosome " + i + " fitness: " 
			     + c1[i].getFitness());
      }
  }


  /** compute fitness value of chromosome <code>chrom2</code> based on
   * the fitness value of chromosome <code>chrom1</code> and on the
   * intersection between <code>chrom1</code> and the collection of
   * <code>N</code> partitions in <code>db</code> */
  static public void computeFitnessValue(Chromosome chrom1, 
					 Hashtable[] intersectMap,
					 Partition[] db, int N, 
					 Chromosome chrom2,
					 int entropyMeasure, 
					 int fitnessMeasure,
					 double[] weightDBTarget,
					 double[] weightTargetDB,
					 double[] weight)
  {
    if (Global.DEBUG == 1)
      if (chrom1.getSize() != chrom2.getSize())
	{
	  System.err.println("ERROR! Chromosome.computeFitnessValue():"
			     + "chromosomes have different size.");
	  System.exit(1);
	}

    int SIZE = chrom1.getSize();
    // <int, <int, int>>
    Hashtable[] localIntersectMap = new Hashtable[N];
    for (int i = 0; i < N; i++)
      {
	localIntersectMap[i] = new Hashtable();
	for (Enumeration classes = intersectMap[i].keys();
	     classes.hasMoreElements();)
	  {
	    Integer currClass = (Integer)classes.nextElement();
	    Hashtable map = (Hashtable)intersectMap[i].get(currClass);
	    localIntersectMap[i].put(currClass, new Hashtable(map));
	  }
      }

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("chrom1 intersections with db");
	for (int i = 0; i < N; i++)
	  {
	    System.out.println("attr " + i);
	    for (Enumeration classes1 = localIntersectMap[i].keys();
		 classes1.hasMoreElements();)
	      {
		Integer currClass1 = (Integer)classes1.nextElement();
		System.out.print(currClass1 + " | ");
		Hashtable value1 = 
		  (Hashtable)localIntersectMap[i].get(currClass1);
		for (Enumeration classes2 = value1.keys(); 
		     classes2.hasMoreElements(); )
		  {
		    Integer currClass2 = (Integer)classes2.nextElement();
		    System.out.print(currClass2 + "(" 
				       + (Integer)value1.get(currClass2) 
				       + ") ");
		  }
		System.out.println();
	      }
	  }
      }
  
    int numModif = 0;

    // loop on all partitions from collection c
    for (int i = 0; i < N; i++)
      // loop on all rowids
      for (int rowid = 0; rowid < SIZE; rowid++)
	// if we have different values on position rowid
	if (chrom1.get(rowid) != chrom2.get(rowid))
	  {
	    numModif++;
	    // for class Cs1 = chrom1[rowid] modify
	    // class Bt = db[i] 
	    // if Cs1 x Bt is 1 delete Bt from the map
	    Integer Cs1 = new Integer(chrom1.get(rowid));
	    Integer Bt = new Integer(db[i].get(rowid));
	    Hashtable map = (Hashtable)localIntersectMap[i].get(Cs1);

	    int count = ((Integer)map.get(Bt)).intValue();
	    if (count == 1)
	      {
		map.remove(Bt);
		// if the map associated with Cs1 becomes empty, remove Cs1
		// from localIntersectMap[i]
		if (map.size() == 0)
		  localIntersectMap[i].remove(Cs1);
	      }
	    else
	      // decrementing Cs1 x Bt
	      map.put(Bt, new Integer(count - 1));
	    
	    // for class Cs2 = chrom2[rowid] modify
	    // class Bt = db[j] by incrementing Cs2 x Bt
	    Integer Cs2 = new Integer(chrom2.get(rowid));
	   
	    if (localIntersectMap[i].containsKey(Cs2))
	      {
		// if localIntersectMap[i] contains the key Cs2 get
		// the count of Bt and increment it
		map = (Hashtable)localIntersectMap[i].get(Cs2); 
		count = 0;
		if (map.containsKey(Bt) == true)
		  count = ((Integer)map.get(Bt)).intValue();
		map.put(Bt, new Integer(count + 1));
	      }
	    else
	      {
		// create a new map with <Bt, 1> and add the map <Cs2,
		// <Bt, 1>> to localIntersectMap[i]
		map = new Hashtable();
		map.put(Bt, new Integer(1));
		localIntersectMap[i].put(Cs2, map);
	      }
	  }
    
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("final intersections");
	for (int i = 0; i < N; i++)
	  {
	    System.out.println("attr " + i);
	    for (Enumeration classes1 = localIntersectMap[i].keys();
		 classes1.hasMoreElements();)
	      {
		Integer currClass1 = (Integer)classes1.nextElement();
		System.out.print(currClass1 + " | ");
		Hashtable value1 = 
		  (Hashtable)localIntersectMap[i].get(currClass1);
		for (Enumeration classes2 = value1.keys(); 
		     classes2.hasMoreElements(); )
		  {
		    Integer currClass2 = (Integer)classes2.nextElement();
		    System.out.println(currClass2 + "(" 
				       + (Integer)value1.get(currClass2) 
				       + ") ");
		  }
		System.out.println();
	      }
	  }
    
	if (numModif > 0)
	  System.out.println("intersectMap has been modified " + numModif);
      }
  
    if (numModif > 0)
      // now in localIntersectMap we have the intersections between
      // chrom2 and the partitions in db
      // based on these intersections compute the fitness of chrom2
      chrom2.computeFitness(localIntersectMap,
			    db, N, 
			    entropyMeasure, fitnessMeasure, 
			    weightDBTarget, weightTargetDB, weight);
    else
      // chrom1 is identical with chrom2
      chrom2.set(chrom1);
  }

  ///////////////// CROSSOVER METHODS //////////////////////

  /** performs the crossover between this chromosome and the one
   * received as argument according to crossoverType */
  public void crossover(Chromosome c, Random rand)
  {
    // if the two partitions are equal return immediately
    if (isEqual(c))
      return;

    if (Global.VERBOSE == 1)
      System.out.print("C ");
    
    switch(crossoverType)
      {
      case CROSS_RAND:
	crossoverR(c, rand);
	break;
  
      case CROSS_X_2RAND_CLASS:
	crossoverXC(c, rand);
	break;
	
      case CROSS_AM_X_2RAND_CLASS:
      case CROSS_AM_X_BEST_CLASS:
      case CROSS_AM_X_BEST_WORST:
	crossoverAM(c, rand);
	break;
	
      default:
	System.err.println("ERROR! Chromosome.crossover():"
			   + "invalid crossover type " + crossoverType);
	System.exit(1);
      }
  }

  /** crosses over this chromosome with the chromosome received as
   * argument by randomly selecting a single cut point and exchanging
   * the last portion starting from the cut point between the two
   * chromosomes */
  private void crossoverR(Chromosome  c, Random rand)
  {
    if (Global.ULTRA_VERBOSE == 1)
      System.out.print("Crossover RANDOM ");
  
    // randomly select a position to cut the chromosomes
    // we will switch positions k to size-1
    // between the two parents
    // k can be a number between 1 and size-1
    int k = 1 + rand.nextInt(size-1);
    // save tail of v in a temp array
    int[] temp = new int[size - k];

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome: ");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();

	System.out.println( " second chromosome: ");
	for (int j = 0; j < c.size; j++)
	  System.out.print(c.v[j] + " ");
	System.out.println();
  
	System.out.println("crossed over at position " + k);      
      }
    
    for (int i = k; i < size; i++)
      temp[i-k] = v[i];

    // copy tail of c.v instead
    for (int i = k; i < size; i++)
      set(i, c.v[i]);

    // copy temp over tail of c
    for (int i = k; i < size; i++)
      c.set(i, temp[i-k]);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome:");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();

	System.out.println(" second chromosome:");
	for (int j = 0; j < c.size; j++)
	  System.out.print(c.v[j] + " ");
	System.out.println();
      }
  }

  /** crosses over this chromosome with the one received as argument;
   * selects a random class and exchanges this class between the two
   * parent chromosomes */
  private void crossoverXC(Chromosome c, Random rand)
  {
    if (Global.ULTRA_VERBOSE == 1)
      System.out.print("Crossover XC ");

    if (getNoClasses() == 1 || c.getNoClasses() == 1)
      return;
  
    // randomly select a class to exchange between the chromosomes
    // k should be a number between 1 and the number of classes
    int noClasses = getNoClasses();
    int k = 1 + rand.nextInt(noClasses);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome:");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();

	System.out.println(" second chromosome:");
	for (int j = 0; j < c.size; j++)
	  System.out.print(c.v[j] + " ");
	System.out.println();
  
	System.out.println("exchanging the class " + k);      
      }

    // save partition c in a temp array
    int[] temp = new int[c.size];
    for (int j = 0; j < c.size; j++)
      temp[j] = c.v[j];

    // copy the class k from this chromosome into c
    // the old elements from c that belong to class k
    // are moved to other classes
    for (int j = 0; j < size; j++)
      {
	if (v[j] == k)
	  c.set(j, k);
	else if (c.v[j] == k)
	  {
	    // move old elements to other distinct classes
	    int new_k = 1 + rand.nextInt(noClasses);
	    while (new_k == k)
	      new_k = 1 + rand.nextInt(noClasses);
	    
	    c.set(j, new_k); 
	  }    
      }
  
    // copy the class k from temp into this chromosome
    // the old elements from v that belonged to class k
    // are moved to other classes
    for (int j = 0; j < size; j++)
      {
	if (temp[j] == k)
	  set(j, k);
	else if (v[j] == k)
	  {
	    // move old elements to other classes
	    int new_k = 1 + rand.nextInt(noClasses);
	    while (new_k == k)
	      new_k = 1 + rand.nextInt(noClasses);
	    
	    set(j, new_k); 
	  }
      }
  
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome:");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();
  
	System.out.println(" second chromosome:");
	for (int j = 0; j < c.size; j++)