chromosome.java

clustering data for the different techniques of data mining

	  System.out.print(c.v[j] + " ");
	System.out.println();
      }
  }

  /** crosses over this chromosome with the one received as argument;
   * implementation with array of maps */
  private void crossoverAM(Chromosome c, Random rand)
  {
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print(" Crossover AM ");
	System.out.println("first chromosome before crossover");
	printAM();
	System.out.println("second chromosome before crossover");
	c.printAM();
      }
    
    // create array of maps for first chromosome
    int noClasses1 = getMaxNoClasses();
    Hashtable[] am1 = new Hashtable[noClasses1];
    for (int i = 0; i < noClasses1; i++)
      am1[i] = new Hashtable();
    getAM(am1);

    // create array of maps for second chromosome
    int noClasses2 = c.getMaxNoClasses();
    Hashtable[] am2 = new Hashtable[noClasses2];
    for (int i = 0; i < noClasses2; i++)
      am2[i] = new Hashtable();
    c.getAM(am2);

    if (Global.DEBUG == 1)
      if (noClasses1 != getMaxNoClasses() 
	  || noClasses2 != c.getMaxNoClasses())
	{
	  System.out.println("ERROR! Chromosome.crossoverAM():"
			     + " invalid number of classes");
	  System.exit(1);
	}
    
    Vector v = selectCrossoverClasses(c, rand);
    // class with best fitness
    int from1AMIndex = ((Integer)v.elementAt(0)).intValue();
    // class with worst fitness
    int to2AMIndex = ((Integer)v.elementAt(1)).intValue();
    // class with best fitness
    int from2AMIndex = ((Integer)v.elementAt(2)).intValue();
    // class with worst fitness
    int to1AMIndex  = ((Integer)v.elementAt(3)).intValue();

    // save class to2AMIndex from am2 into a toReplace map
    Hashtable toReplace = new Hashtable(am2[to2AMIndex]);
    // save the original from2AMIndex from am2
    Hashtable from2bak = new Hashtable(am2[from2AMIndex]); 
    
    // put class from1AMIndex in am2 instead of class to2AMIndex
    am2[to2AMIndex] = new Hashtable(am1[from1AMIndex]);
    
    // remove the elements of class from1AMIndex that appear in other
    // classes of am2
    // remove the elements in toReplace that are also in from1AMIndex
    // since they should not be distributed to other classes
    cleanUpAndDistributeAM(am2, toReplace, to2AMIndex, rand, c);
    //    c.setAM(am2, noClasses2);
    c.setAM(am2);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print("AM2 map sizes = ");
	for (int i = 0; i < am2.length; i++)
	  System.out.print(am2[i].size() + " ");
	System.out.println();
      }
    /////////////// Second part //////////////
    
    // save class to1AMIndex from am1 in a toReplace map
    toReplace = new Hashtable(am1[to1AMIndex]);
    
    // put class from2bak (the original from2AMIndex) in am1 instead of
    // class to1AMIndex
    am1[to1AMIndex] = new Hashtable(from2bak);
    
    // remove the elements of class from2AMIndex that appear in other
    // classes of am2
    // remove the elements in toReplace that are also in to1AMIndex
    // since they should not be distributed to other classes
    cleanUpAndDistributeAM(am1, toReplace, to1AMIndex, rand, this);
    //    setAM(am1, noClasses1);
    setAM(am1);
    
    if (Global.ULTRA_VERBOSE == 1)
      {    
	System.out.print("AM1 map sizes = ");
	for (int i = 0; i < am1.length; i++)
	  System.out.print(am1[i].size() + " ");
	System.out.println();
      }

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome after crossover");
	printAM();
	
	System.out.println(" second chromosome after crossover");
	c.printAM();
      }
  }
  
  //////////////////// MISCELLANEOUS METHODS //////////////////////

  private void cleanUpAndDistributeAM(Hashtable[] am, Hashtable temp, int k,
				      Random rand, Partition p)
  {
    // indices of classes that become empty
    Hashtable emptyClasses = new Hashtable();

    cleanUpAM(am, temp, k, emptyClasses, p);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("there are " + temp.size() 
			   + " elements to distribute");
	System.out.println("there are " + emptyClasses.size() 
			   + " empty classes");
      }
    
    int nElemDistribute = temp.size();
    int nEmptyClasses = emptyClasses.size();
  
    if (nEmptyClasses == 0)
      {
	// we have no empty classes
	  
	// if temp is empty nothing is done 
	// otherwise we distribute elem of temp 
	// according to distribution_type
	distribute(temp, am, rand); 
      }
    else // we have empty classes
      {
	if (nElemDistribute <= nEmptyClasses)
	  {
	    // we have less elements to distribute
	    // than empty classes
	    // insert one element in each empty class
	    distributeToEmptyClasses(temp, am, emptyClasses, 1, rand);
	  }
	else
	  {
	    // we have more elements to distribute than empty classes
	    int quota = nElemDistribute/nEmptyClasses;
	    
	    // distribute nElemDistribute/nEmptyClasses 
	    // to each empty class
	    distributeToEmptyClasses(temp, am, emptyClasses, quota, rand);
	  }
      }
  }
  
  /** cleans up the classes of <code>am</code> such that the elements
   * of class <code>am[k]</code> do not appear in other classes of
   * <code>am</code> (different than <code>k</code>) also removes the
   * elements of <code>temp</code> that are in <code>am[k]</code>
   * since they should not be distributed to other classes;
   * <code>emptyClasses</code> gets filled with the ids of the classes
   * that got empty */
  private void cleanUpAM(Hashtable[] am, Hashtable temp, int k, 
			 Hashtable emptyClasses, Partition p)
  {
    int noClasses = p.getNoClasses();
    for (Enumeration classes = am[k].keys(); classes.hasMoreElements();)
      {
	Integer currClass = (Integer)classes.nextElement();
	// if currClass is in map temp
	// delete this value from the map
	if (temp.containsKey(currClass) == true)
	  temp.remove(currClass);

	for (int i = 0; i < noClasses; i++)	
	  if (i != k)
	    {
	      // if currClass is in map am[i]
	      if (am[i].containsKey(currClass) == true)
		{
		  // delete this value from the map
		  am[i].remove(currClass);
		  
		  // if this class becomes empty remember its index
		  if (am[i].size() == 0)
		    emptyClasses.put(new Integer(i), new Integer(i));

		  break;
		}
	    }
      }
    
    // from noClasses to getMaxNoClasses() - 1 we have empty classes
    for (int i = noClasses; i < p.getMaxNoClasses(); i++)
      {
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("Found " + i + " as empty class");
	emptyClasses.put(new Integer(i), new Integer(i));
      }
  }

  /** selects the best class according to the class fitness and
   * returns its index in <code>am</code> representation */
  private int selectBestClass()
  {
    int amIndex = -1;
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("select best class ");

    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    getAM(am);

    Enumeration classes = classFitness.keys();
    Integer currClass = (Integer)classes.nextElement();
    int classNo = currClass.intValue();
    double bestFit = ((Double)classFitness.get(currClass)).doubleValue();
    for (Enumeration classes1 = classFitness.keys();
	 classes1.hasMoreElements();)
      {
	Integer currClass1 = (Integer)classes1.nextElement();
	double value = ((Double)classFitness.get(currClass1)).doubleValue();
	if (value < bestFit)
	  {
	    classNo = currClass1.intValue();
	    bestFit = value;
	  }
      }


    // classNo is the class integer that has the smallest fitness
    // see to what class it corresponds in am
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("AM contents start " + noClasses);
	for (int k = 0; k < noClasses; k++)
	  {
	    System.out.print("am[" + k + "]:");
	    printMap(am[k]);
	  }
	System.out.println("AM contents end");
      }

    int k;
    for (k = 0; k < noClasses; k++)
      {
	Enumeration keys = am[k].keys();
	Integer key = (Integer)keys.nextElement();
	if (v[key.intValue()] == classNo)
	  {
	    amIndex = k;
	    break;
	  }
      }


    if (Global.DEBUG == 1)
      if (k == noClasses)
	{
	  // this should never happen
	  System.err.println("ERROR! Chromosome.selectBestClass():"
			     + "classNo corresponds to no class: " + classNo);
	  System.exit(1);
	}

    return amIndex;
  }

  /** selects the best and worst classes according to the class
   * fitness and returns a vector containing two Integer objects, the
   * first one is the best class index in am representation and the
   * second one is the worst class index in am representation */
  private Vector selectBestWorstClasses()
  {
    int bAMIndex = -1;
    int wAMIndex = -1;
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("select best worst class ");

    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    getAM(am);

    if (Global.DEBUG == 1)
      if (classFitness.size() == 0)
	{
	  System.err.println("ERROR! Chromosome.selectBestWorstClasses():"
			     + " classFitness is empty");
	  System.exit(1);
	}
    
    Enumeration classes = classFitness.keys();
    Integer currClass = (Integer)classes.nextElement();
    int bClassNo = currClass.intValue();
    double minFit = ((Double)classFitness.get(currClass)).doubleValue();
    int wClassNo = bClassNo;
    double maxFit = minFit;

    for (Enumeration classes1 = classFitness.keys();
	 classes1.hasMoreElements();)
      {
	Integer currClass1 = (Integer)classes1.nextElement();
	double value = ((Double)classFitness.get(currClass1)).doubleValue();
	if (value < minFit)
	  {
	    bClassNo = currClass1.intValue();
	    minFit = value;
	  }
	else if (value > maxFit)
	  {
	    wClassNo = currClass1.intValue();
	    maxFit = value;
	  }
      }
  
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("bClassNo " + bClassNo + " wClassNo " + wClassNo);

    // bClassNo is the class integer that has the smallest fitness
    // wClassNo is the class integer that has the largest fitness
    // see to what classes correspond in am
    int k;
    boolean foundBest = false;
    boolean foundWorst = false;
    for (k = 0; k < noClasses; k++)
      {
	Enumeration keys = am[k].keys();
	Integer key = (Integer)keys.nextElement();

	if (!foundBest && v[key.intValue()] == bClassNo)
	  {
	    bAMIndex = k;
	    foundBest = true;
	  }
	
	if (!foundWorst && v[key.intValue()] == wClassNo)
	  {
	    wAMIndex = k;
	    foundWorst = true;
	  }
	
	if (foundBest && foundWorst)
	  break;
      }
    
    if (Global.DEBUG == 1)  
      if (k == noClasses)
	{
	  // this should never happen
	  System.err.println("ERROR! selectBestWorstClasses(): invalid class"
			     + " number -> bClassNo =? " + bClassNo 
			     + " wClassNo =? " + wClassNo);
	  System.exit(1);
	}

    Vector v = new Vector(2);
    v.insertElementAt(new Integer(bAMIndex), 0);
    v.insertElementAt(new Integer(wAMIndex), 1);

    return v;
  }

  /** selects the classes to crossover between this chromosome and c
   * and returns a vector containing from1AMIndex, to2AMIndex,
   * from2AMIndex, and to1AMIndex*/
  private Vector selectCrossoverClasses(Chromosome c, Random rand)
  {
    int from1AMIndex = -1;
    int to2AMIndex = -1;
    int from2AMIndex = -1;
    int to1AMIndex = -1;

    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("select crossover classes ...");

    switch(crossoverType)
      {
      case CROSS_AM_X_2RAND_CLASS:
	from1AMIndex = to1AMIndex = rand.nextInt(getNoClasses());
	from2AMIndex = to2AMIndex = rand.nextInt(c.getNoClasses());
	break;

      case CROSS_AM_X_BEST_CLASS:
	from1AMIndex = selectBestClass();
	to1AMIndex = from1AMIndex;
	from2AMIndex = c.selectBestClass();
	to2AMIndex = from2AMIndex;
	break;

      case CROSS_AM_X_BEST_WORST:
	Vector v = selectBestWorstClasses();
	from1AMIndex = ((Integer)v.elementAt(0)).intValue();
	to1AMIndex = ((Integer)v.elementAt(1)).intValue();
	v = c.selectBestWorstClasses();
	from2AMIndex = ((Integer)v.elementAt(0)).intValue();
	to2AMIndex = ((Integer)v.elementAt(1)).intValue();
	break;

      default:
	System.err.println("ERROR! Chromosome.selectCrossoverClasses():"
			   + " invalid crossoverType");
	System.exit(1);
      }
    
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("from1 " + from1AMIndex + " to1 " + to1AMIndex
			 + " from2 " + from2AMIndex + " to2 " + to2AMIndex);
  
    Vector ret = new Vector(4);
    ret.insertElementAt(new Integer(from1AMIndex), 0);
    ret.insertElementAt(new Integer(to2AMIndex), 1);
    ret.insertElementAt(new Integer(from2AMIndex), 2);
    ret.insertElementAt(new Integer(to1AMIndex), 3);
    return ret;
  }

  private void distribute(Hashtable temp, Hashtable[] am, Random rand)
  {
    switch (distributionType)
      {
      case DISTRIB_RAND:
	distributeRandomly(temp, am, rand);
	break;
	
      case DISTRIB_TO_EVEN:
	distributeToEven(temp, am, rand);
	break;
	
      case DISTRIB_NONE:
      default:
	System.err.println("ERROR! Chromosome.distribute(): invalid"
			   + " distributionType");
	System.exit(1);
      }
  }

  /** distributes the elements of the map <code>temp</code> to other
   * classes in <code>am</code>; classes are selected randomly*/
  private void distributeRandomly(Hashtable temp, Hashtable[] am, Random rand) 
  {
    if (Global.VERBOSE == 1)
      System.out.print("distributeRandomly ");

    int nElemDistribute = temp.size();
    if (nElemDistribute == 0)
      return; //no elements to distribute

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print("temp ");
	printMap(temp);
      }
  
    // distribute the elements in temp to randomly selected classes 
    for (Enumeration classes = temp.keys(); classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	// select at random a class to distribute
	// the element from temp
	// pos should be a number between 0 and getMaxNoClasses()-1
	// here in am we have maximum number of classes
	int pos = rand.nextInt(getMaxNoClasses());
	
	// insert the element from temp
	am[pos].put(currClass, currClass); 
	
	if (Global.ULTRA_VERBOSE == 1)
	  {	
	    System.out.println("distribute " + currClass + " to am[" 
			       + pos + "] ");
	    printMap(am[pos]);
	  }
      }
  }

  /** selects <code>n</code> classes from <code>am</code>, based on