*
* -F num
* The fitness threshold specifying the termination criterion.
* (default 0.85)
*
* -P num
* The number of hypotheses to be included in the population. (default 100)
*
* -R num
* The fraction of the population to be replaced by Crossover at each step.
* (default 0.6)
*
* -M num
* The mutation rate. (default 0.3)
*
* -S num
* The seed for the random number generator. (default current date)
*
* -I num
* The maximum number of populations to generate. (default 100)
*
* -L num
*
* -F num
*
* -P num
*
* -R num
*
* -M num
*
* -S num
*
* -I num
*
* -L num
* Specifies which logical operations to use to classify an instance.
* It can also specify a combination of logical operations to use.
* The population is divided into approximately equal parts. Each part
* uses a different logical operator (AND = 1, OR = 2 or XOR = 4).
* Use the sum to specify multiple logical operators. (default 4, XOR)
*
* @author Keith A. Pray
*
*/
public class GA extends DistributionClassifier
implements OptionHandler
{
/***** The options *****/
/** The fitness threshold */
private double m_FitnessThreshold = 0.85;
/** The number of the hypotheses in the population **/
private int m_NumPopulation = 100;
/** the fraction of the population to be replaced by
Crossover at each step **/
private double m_Replace = 0.6;
/** The mutation rate **/
private double m_MutationRate = 0.3;
/** Seed used for shuffling the dataset */
private int m_Seed = 1;
/** The maximum number of iterations */
private int m_NumIterations = 100;
/** The Logical operation(s) to use. */
private int m_Logical = 4;
/***** END The options *****/
/** Logical operator types */
final static public int AND = 1;
final static public int OR = 2;
final static public int ANDOR = 3;
final static public int XOR = 4;
final static public int ANDXOR = 5;
final static public int ORXOR = 6;
final static public int ANDORXOR = 7;
/** The training instances */
private Instances m_Train = null;
/** We need to keep the number of intances with each
classification */
private double numTrain0, numTrain1;
/** The filter used to make attributes numeric. */
/** using my own specialized version */
private NominalToBinaryFilter m_NominalToBinary =null;
/** The filter used to get rid of missing values. */
private ReplaceMissingValuesFilter m_ReplaceMissingValues =null;
/** The random number generator **/
private Random random = null;
/***** data structures to hold population *****/
/** the population */
private BitSet[] populationBitSet;
/** the fitness of a hypothesis in population */
private double[] populationFitness;
/** the index of the most fit hypothesis */
private int maxFitness;
/** the sum of all fitness */
private double fitnessSum;
/** population index - for choosing next */
private int populationIndex;
/** GA's for multiple logical operations */
private GA andGA;
private GA orGA;
private GA xorGA;
/***** Switches for reporting details *****/
/** set to 1 to print */
/** Pr() details. Generated probability of selection */
private final int printPr = 0;
/** Choose() details. Decides if specified hyp. should
be choosen. */
private final int printChoose = 0;
/** Show the initial population */
private final int printInitPopulation = 0;
/** Show each population generated */
private final int printEachPopulation = 0;
/** Show the fitness (and overall average) of each
population generated */
private final int printPopulationFitness = 1;
/** Show the fitness of each hyp. in each population */
private final int printPopulationFitnesses = 0;
/** show best hypothesis in final population */
private final int printBestHypothesis = 0;
/** Fitness() details. Assigns fitness. */
private final int printFitness = 0;
//********************************************************//
/**
* Returns an enumeration describing the available options
*
* @return an enumeration of all the available options
*/
public Enumeration listOptions()
{
Vector newVector = new Vector ( 7 );
newVector.addElement ( new Option ( "\tThe maximum number of iterations to be performed.\n"
+ "\t(default 100)",
"I", 1, "-I
* The fitness threshold specifying the termination criterion.
* (default 0.85)
* The number of hypotheses to be included in the population.
* (default 100)
* The fraction of the population to be replaced by Crossover at each step.
* (default 0.6)
* The mutation rate. (default 0.3)
* The seed for the random number generator. (default current date)
* The maximum number of populations to generate. (default 100)
* Specifies which logical operations to use to classify an instance.
* It can also specify a combination of logical operations to use.
* The population is divided into approximately equal parts. Each part
* uses a different logical operator (AND = 1, OR = 2 or XOR = 4).
* Use the sum to specify multiple logical operators.
*
* @param options the list of options as an array of strings
* @exception Exception if an option is not supported
*/
public void setOptions ( String[] options ) throws Exception
{
String iterationsString = Utils.getOption ( 'I', options );
if (iterationsString.length() != 0)
{
m_NumIterations = Integer.parseInt ( iterationsString );
}
else
{
m_NumIterations = 100;
}
String fitnessThresholdString = Utils.getOption ( 'F', options );
if (fitnessThresholdString.length() != 0)
{
m_FitnessThreshold = ( new Double ( fitnessThresholdString ) ).doubleValue();
}
else
{
m_FitnessThreshold = 0.85;
}
String seedString = Utils.getOption ( 'S', options );
if ( seedString.length() != 0 )
{
m_Seed = Integer.parseInt ( seedString );
}
else
{
Date date = new Date();
m_Seed = (int)(date.getTime());
}
String numPopulationString = Utils.getOption ( 'P', options );
if ( numPopulationString.length() != 0 )
{
m_NumPopulation = Integer.parseInt ( numPopulationString );
}
String mutationRateString = Utils.getOption ( 'M', options );
if ( mutationRateString.length() != 0 )
{
m_MutationRate = ( new Double ( mutationRateString ) ).doubleValue();
}
else
{
m_MutationRate = 0.3;
}
String replaceString = Utils.getOption ( 'R', options );
if ( replaceString.length() != 0 )
{
m_Replace = ( new Double ( replaceString ) ).doubleValue();
}
else
{
m_Replace = 0.6;
}
String logicalString = Utils.getOption ( 'L', options );
if ( logicalString.length() != 0 )
{
m_Logical = ( new Integer ( logicalString ) ).intValue();
}
else
{
m_Logical = XOR;
}
} // END public void setOptions ( String[] options )
// throws Exception
//********************************************************//
/**
* Gets the current settings of the classifier.
*
* @return an array of strings suitable for passing to setOptions
*/
public String[] getOptions()
{
// should be twice the number of options.
String[] options = new String [14];
int current = 0;
options[current++] = "-F"; options[current++] = "" + m_FitnessThreshold;
options[current++] = "-P"; options[current++] = "" + m_NumPopulation;
options[current++] = "-R"; options[current++] = "" + m_Replace;
options[current++] = "-M"; options[current++] = "" + m_MutationRate;
options[current++] = "-S"; options[current++] = "" + m_Seed;
options[current++] = "-I"; options[current++] = "" + m_NumIterations;
options[current++] = "-L"; options[current++] = "" + m_Logical;
while ( current < options.length )
{
options[current++] = "";
}
return ( options );
} // END public String[] getOptions()
//********************************************************//
/**
* Builds the classifier with a Genetic Algorithm
*
* @exception Exception if something goes wrong during building
*/
public void buildClassifier ( Instances insts )
throws Exception
{
if ( insts.checkForStringAttributes() )
{
throw new Exception ( "Can't handle string attributes!" );
}
if ( insts.numClasses() > 2 )
{
throw new Exception ( "Can only handle two-class datasets!" );
}
if ( insts.classAttribute().isNumeric() )
{
throw new Exception ( "Can't handle a numeric class!" );
}
// Filter data
// make the training set
m_Train = new Instances ( insts );
// take care of missing values
m_Train.deleteWithMissingClass();
m_ReplaceMissingValues = new ReplaceMissingValuesFilter();
m_ReplaceMissingValues.inputFormat ( m_Train );
m_Train = Filter.useFilter ( m_Train, m_ReplaceMissingValues );
// Note: using binary representation of nominal values
// so we can use a bit representation of the hypotheses
// in our population
m_NominalToBinary = new NominalToBinaryFilter();
m_NominalToBinary.inputFormat ( m_Train );
m_Train = Filter.useFilter ( m_Train, m_NominalToBinary );
// count the number of instances with each classification
Enumeration enum = m_Train.enumerateInstances();
numTrain0 = 0;
numTrain1 = 0;
while ( enum.hasMoreElements() )
{
if ( ((Instance)(enum.nextElement())).classValue() == 1 )
{
numTrain1 += 1;
}
else
{
numTrain0 += 1;
}
} // end while
switch ( printInitPopulation )
{
case 1:
// let's output a summary of what the data now looks like
System.out.println ( "Summary of data transformation: \n" );
System.out.println ( m_Train.toSummaryString() + "\n" );
System.out.println ( "Example: " +
m_Train.firstInstance().toString() + "\n" );
break;
}
// set seed for random number generator
random = new Random ( m_Seed );
// if we are using multiple logical operations, just
// start a new GA for each logical operation
switch ( m_Logical )
{
case ANDOR:
{
// make new orGA - use 1/2 the population
InitorGA ( m_NumPopulation / 2 );
// make new andGA - use 1/2 the population
InitandGA ( m_NumPopulation / 2 );
// we should be all set now :)
break;
}
case ANDXOR:
{
// make new xorGA - use 1/2 the population
InitxorGA ( m_NumPopulation / 2 );
// make new andGA - use 1/2 the population
InitandGA ( m_NumPopulation / 2 );
// we should be all set now :)
break;
}
case ORXOR:
{
// make new xorGA - use 1/2 the population
InitxorGA ( m_NumPopulation / 2 );
// make new orGA - use 1/2 the population
InitorGA ( m_NumPopulation / 2 );
// we should be all set now :)
break;
}
case ANDORXOR:
{
// make new xorGA - use 1/3 the population
InitxorGA ( m_NumPopulation / 3 );
// make new orGA - use 1/3 the population
InitorGA ( m_NumPopulation / 3 );
// make new andGA - use 1/3 the population
InitandGA ( m_NumPopulation / 3 );
// we should be all set now :)
break;
}
default:
SingleBuild();
break;
} // end switch
} // END public void buildClassifier ( Instances insts )
// throws Exception
//********************************************************//
/**
* Build classifier so single logical operator
*
*/
private void SingleBuild()
throws Exception
{
// Initialize our population
InitPopulation();
// Now we train
// need a counter
int counter = 0;
int i = 0;
// need temp vector
Vector tempVector = null;
// need a new population
BitSet [] newPopulation = new BitSet [ m_NumPopulation ];
// let's decay the mutation rate over time
// try using the mutation rate divided by number of
// populations, so we'll come near zero by the time
// we are near the end
double mutationDecayRate = m_MutationRate / (double)m_NumPopulation;
while ( ( counter < m_NumIterations ) &&
( CurrentFitness() < m_FitnessThreshold ) )
{
// select the hypotheses to continue in the new
// population
tempVector = Continue();
// do cross over
tempVector.addAll ( CrossOver() );
switch ( printEachPopulation )
{
case 1:
System.out.println ( "The new population: " + tempVector );
break;
}
// mutate away (the new population of course)
// remember to subtract the decay
tempVector = Mutate ( tempVector,
m_MutationRate - (mutationDecayRate *
((double)counter)) );
// put the new population in place
// let's try adding it in a random order
// need temp bitset
BitSet tempBitSet = null;
while ( tempVector.size() > 0 )
{
// trim the vector to size so we always use a valid
// index
tempVector.trimToSize();
// get the next bitset
tempBitSet = (BitSet)tempVector.
elementAt ( random.nextInt ( tempVector.size() ) );
// add this bitset to our population
populationBitSet[i] = tempBitSet;
// remove the bitset from temp
tempVector.remove ( tempBitSet );
} // end while temp vector has more
// Enumeration e = tempVector.elements();
// while ( e.hasMoreElements() && ( i < m_NumPopulation ) )
// {
// populationBitSet[i] = (BitSet)(e.nextElement());
// i++;
// }
// evaluate fitness
Fitness();
// next
counter++;
switch ( printPopulationFitness )
{
case 1:
System.out.print ( "Population " );
switch ( m_Logical )
{
case AND:
System.out.print ( "andGA : " );
break;
case OR:
System.out.print ( "orGA : " );
break;
case XOR:
System.out.print ( "xorGA : " );
break;
} // end switch
System.out.println ( "# " + counter +
"\t : Fitness " + CurrentFitness() +
"\t ( Avg. " + CurrentAverageFitness() + " )" );
break;
}
} // end while more iterations and have not reached
// fitness threshold
switch ( printBestHypothesis )
{
case 1:
// print best hypothesis found
System.out.println ( populationBitSet [ maxFitness ].toString() );
break;
}
} // END void SingleBuild()
//********************************************************//
/**
* Initializes andGA
*
* @param n
* number of instances to use
*/
private void InitandGA ( int n )
throws Exception
{
// make a new one
andGA = new GA();
// set fitness threshold
andGA.setFitnessThreshold ( m_FitnessThreshold );
// set the number of instances
andGA.setNumPopulation ( n );
// set replace rate
andGA.setReplace ( m_Replace );
// set mutation rate
andGA.setMutationRate ( m_MutationRate );
// set random seed
andGA.setSeed ( m_Seed );
// set the number of iterations
andGA.setNumIterations ( m_NumIterations );
// set the logical operation to OR of course
andGA.setLogical ( AND );
// build with our training data
andGA.buildClassifier ( m_Train );
} // END void InitandGA()
//********************************************************//
/**
* Initializes orGA
*
* @param n
* number of instances to use
*/
private void InitorGA ( int n )
throws Exception
{
// make a new one
orGA = new GA();
// set fitness threshold
orGA.setFitnessThreshold ( m_FitnessThreshold );
// set the number of instances to half
orGA.setNumPopulation ( n );
// set replace rate
orGA.setReplace ( m_Replace );
// set mutation rate
orGA.setMutationRate ( m_MutationRate );
// set random seed
orGA.setSeed ( m_Seed );
// set the number of iterations
orGA.setNumIterations ( m_NumIterations );
// set the logical operation to OR of course
orGA.setLogical ( OR );
// build with our training data
orGA.buildClassifier ( m_Train );
} // END void InitorGA()
//********************************************************//
/**
* Initializes xorGA
*
* @param n
* number of instances to use
*/
private void InitxorGA ( int n )
throws Exception
{
// make a new one
xorGA = new GA();
// set fitness threshold
xorGA.setFitnessThreshold ( m_FitnessThreshold );
// set the number of instances to half
xorGA.setNumPopulation ( n );
// set replace rate
xorGA.setReplace ( m_Replace );
// set mutation rate
xorGA.setMutationRate ( m_MutationRate );
// set random seed
xorGA.setSeed ( m_Seed );
// set the number of iterations
xorGA.setNumIterations ( m_NumIterations );
// set the logical operation to OR of course
xorGA.setLogical ( XOR );
// build with our training data
xorGA.buildClassifier ( m_Train );
} // END void InitxorGA()
//********************************************************//
/**
* Initializes the population of hypotheses.
*/
private void InitPopulation() throws Exception
{
// we need bitset's for the hypotheses in our population
int counter = 0;
int counter2 = 0;
// we need a bitset for each hypothesis
populationBitSet = new BitSet [ m_NumPopulation ];
while ( counter < m_NumPopulation )
{
// each bit set will need a bit for each attribute
populationBitSet [ counter ] = new BitSet ( m_Train.numAttributes() );
// randomly assign bit values to each bit in the
// bit set
counter2 = 0;
while ( counter2 < m_Train.numAttributes() )
{
if ( random.nextBoolean() )
{
populationBitSet [ counter ].set ( counter2 );
} // end set to true
else
{
populationBitSet [ counter ].clear ( counter2 );
} // end else set to false
counter2++;
} // end while more bits
counter++;
} // end while more bitsets
// set the fitness for these initial hypothesis
// gotta make the array of course
populationFitness = new double [ m_NumPopulation ];
Fitness();
populationIndex = 0;
} // END void InitPopulation()
//********************************************************//
/**
* Assigns a fitness to each hypothesis in the current
* population
*/
private void Fitness() throws Exception
{
int counter = 0;
Enumeration e;
// reset max fitness
maxFitness = 0;
fitnessSum = 0;
// need a temp instance
Instance tempInstance;
// need a temp answer
double answer;
// for each hypothesis, count how many of the training
// instances it does not classifies incorrectly
while ( counter < m_NumPopulation )
{
// reset the fitness for this hypothesis
// use a small number, but NOT zero, or it will run
// forever if there are no hypotheses that classify
// anything correctly
populationFitness [ counter ] = 0.00000001;
// get an enumeration of the training instances
e = m_Train.enumerateInstances();
// count how many we don't classify incorrectly
while ( e.hasMoreElements() )
{
tempInstance = (Instance)( e.nextElement() );
// classify using current hypothesis
answer = SimpleClassifyInstance ( tempInstance, counter );
switch ( printFitness )
{
case 1:
System.out.println ( "H : " + answer + ", I : " +
tempInstance.classValue() );
break;
}
// if it is correct, increase fitness
if ( ( ( tempInstance.classValue() == 1 ) &&
( answer == 1 ) )
||
( ( tempInstance.classValue() == 0 ) &&
( answer == 0 ) ))
{
// increase fitness then
populationFitness [ counter ] = populationFitness [ counter ] + 1;
} // end if classified correctly
// if it classified incorrectly, subtract from fitness
if ( ( ( tempInstance.classValue() == 1 ) &&
( answer == 0 ) )
||
( ( tempInstance.classValue() == 0 ) &&
( answer == 1 ) ))
{
// decrease fitness
populationFitness [ counter ] = populationFitness [ counter ] - 1;
}
} // end while more instances
// if the fitness is zero or negative,
// reset it to the default min
if ( populationFitness [ counter ] <= 0 )
{
populationFitness [ counter ] = 0.00000001;
}
// set the fitness to this count over the number of
// training instances with this hypothesis' classification
if ( populationBitSet [ counter ].get ( m_Train.classIndex() ) )
{
switch ( printFitness )
{
case 1:
System.out.println ( "Setting Fit = " +
populationFitness [ counter ] +
" / " +
numTrain1 + "\n" );
break;
}
populationFitness [ counter ] =
populationFitness [ counter ] / numTrain1;
}
else
{
switch ( printFitness )
{
case 1:
System.out.println ( "Setting Fit = " +
populationFitness [ counter ] +
" / " +
numTrain0 + "\n" );
break;
}
populationFitness [ counter ] =
populationFitness [ counter ] / numTrain0;
}
// if this fitness is greater than the current max,
// set max to this index
if ( populationFitness [ counter ] >
populationFitness [ maxFitness ] )
{
maxFitness = counter;
} // end if this is new max
// update fitness sum
fitnessSum += populationFitness [ counter ];
// next hypothesis
counter++;
} // end while there are more hypotheses
// reset the population index
populationIndex = 0;
switch ( printPopulationFitnesses )
{
case 1:
// print out fitnesses
System.out.print ( "Fitnesses : " );
for ( counter = 0; counter < populationFitness.length; counter++ )
{
System.out.print ( populationFitness [ counter ] + ", " );
}
System.out.print ( "\n" );
break;
}
} // END void Fitness()
//********************************************************//
/**
* Classifies an instance with a specific hypothesis
*
* @param instance
* the instance to classify
*
* @param hypothesis
* the index of the hypothesis to use
*
* @return
* the classification
*/
private double SimpleClassifyInstance ( Instance instance,
int hypothesis )
{
// put the instance into a Bit Set
BitSet instanceBitSet = new BitSet ( instance.numAttributes() );
// get a double array of the attribute values
double [] values = instance.toDoubleArray();
// now, all but the class attribute should be binary
int counter = 0;
// skip the last one of course
while ( counter < instance.numAttributes() - 1 )
{
if ( values [ counter ] > 0 )
{
instanceBitSet.set ( counter );
} // end if value more than 0 set bit
else
{
instanceBitSet.clear ( counter );
} // end else clear bit
// go to next
counter++;
} // end while there's more
// now we do something that decides the class...
// This can be of three logical operators
switch ( m_Logical )
{
case AND:
instanceBitSet.and ( populationBitSet [ hypothesis ] );
break;
case OR:
instanceBitSet.or ( populationBitSet [ hypothesis ] );
break;
case XOR:
instanceBitSet.xor ( populationBitSet [ hypothesis ] );
break;
default:
instanceBitSet.xor ( populationBitSet [ hypothesis ] );
break;
} // end switch logical
// and add up the individual bits set in the result
// and the original hypothesis.
counter = 0;
// the total
int resultTotal = 0;
int hypothesisTotal = 0;
while ( counter < instance.numAttributes() )
{
if ( instanceBitSet.get ( counter ) )
{
resultTotal++;
}
if ( populationBitSet [ hypothesis ].get ( counter ) )
{
hypothesisTotal++;
}
counter++;
} // end while more bits to add
// System.out.println ( total );
// let's keep track of the answer
// default is right in the middle
double answer = 0.50;
switch ( m_Logical )
{
case AND:
// AND has the effect of demanding that an attribute
// bit is set. the ratio of these bits set determines
// the likely hood that this hypothesis' classification
// is correct.
// if the ratio of the result bits set to hypothesis
// bits set if above a certain threshold, return
// the classification specified by the hypothesis
if ( hypothesisTotal > ((double)(resultTotal)) * 0.85 )
{
// return the last bit of the hypothesis as the answer
if (populationBitSet [ hypothesis ].get ( m_Train.classIndex() ))
{
answer = 1;
} // end if
else
{
answer = 0;
} // end else
} // end if
break;
case OR:
// OR can only identify attributes that have no
// significance. This means the more bits set in
// the instance over the hypothesis, the more
// likely the hypothesis' classification is correct.
// so, we really want to compare the difference of bits
// NOT set in the hypothesis to bits set in the result
// over the number that were set in the hypothesis.
// if the ratio of hypothesis bits set to result
// bits set is above a threshold, give this hypothesis'
// classification
// number of bits not set in hypothesis
int bitsNotSetH = m_Train.numAttributes() - hypothesisTotal;
// difference in number of bits set in result and hypothesis
int bitsNotSetR = m_Train.numAttributes() - resultTotal;
if ( ( ((double)(bitsNotSetR)) / ((double)(bitsNotSetH)) ) > 0.85 )
{
// return the last bit of the hypothesis as the answer
if (populationBitSet [ hypothesis ].get ( m_Train.classIndex() ))
{
answer = 1;
} // end if
else
{
answer = 0;
} // end else
} // end if
break;
case XOR:
// now, since xor is the most specific, we will count
// the number of set bits. If this is over some
// threshold, we'll return the last bit of the
// hypothesis as the answer.
// if the sum is below the threshold, we'll return
// a neutral answer
if (resultTotal > ((double)(instance.numAttributes())) * 0.50 )
{
// return the last bit of the hypothesis as the answer
if (populationBitSet [ hypothesis ].get ( m_Train.classIndex() ))
{
answer = 1;
} // end if
else
{
answer = 0;
} // end else
} // end if
break;
default:
answer = 0.50;
break;
} // end switch
// all done
return ( answer );
// just return the ratio of yes votes
// return ( 1 - ((double)total / (double)(instance.numAttributes())) );
// if ( ((double)total) / ((double)(instance.numAttributes())) > 0.5 )
// {
// return ( 1.0 );
// }
// otherwise, we really didn't know, so return 0.5
// which is half way between our two classifications
// return ( 0.5 );
} // END double SimpleClassifyInstance ( Instance instance,
// int hypothesis )
//********************************************************//
/**
* Classifies an instance
*
* @param instance
* the instance to classify
*
* @return
* the classification
*/
private double ClassifyInstance ( Instance instance )
{
// if we have more than one logical operator
// we should get the classification given by each
// one and use those to decide.
// otherwise, just call the simple classify
// let's average our answer's
double answer = 0.0;
switch ( m_Logical )
{
case ANDOR:
answer += andGA.ClassifyInstance ( instance );
answer += orGA.ClassifyInstance ( instance );
answer = answer / 2;
break;
case ANDXOR:
answer += andGA.ClassifyInstance ( instance );
answer += xorGA.ClassifyInstance ( instance );
answer = answer / 2;
break;
case ORXOR:
answer += orGA.ClassifyInstance ( instance );
answer += xorGA.ClassifyInstance ( instance );
answer = answer / 2;
break;
case ANDORXOR:
answer += andGA.ClassifyInstance ( instance );
answer += orGA.ClassifyInstance ( instance );
answer += xorGA.ClassifyInstance ( instance );
answer = answer / 3;
break;
default:
// simply use our best hypothesis
answer = SimpleClassifyInstance ( instance,
maxFitness );
}
// well, return our answer
return ( answer );
} // END double ClassifyInstance ( Instance instance )
//********************************************************//
/**
* Returns the current fitness level
*
* @return
* the current fitness as percentage of correctly
* classified training instances
*/
public double CurrentFitness()
{
return ( populationFitness [ maxFitness ] );
} // END double CurrentFitness()
//********************************************************//
/**
* Returns the current average fitness level
*
* @return
* the current average fitness as percentage of correctly
* classified training instances per hypothesis in the
* population
*/
public double CurrentAverageFitness()
{
return ( fitnessSum / ((double)(m_NumPopulation)) );
} // END double CurrentAverageFitness()
//********************************************************//
/**
* Returns the hypotheses to continue in a new generation
*
* @return
* the continuing hypothesis
*/
public Vector Continue()
{
// the vector to return
Vector v = new Vector();
// need a counter
int counter = 0;
// go through population selecting a single hypothesis
// to continue with probability fitness / fitness sum
counter = 0;
while ( counter < ( 1 - m_Replace ) * m_NumPopulation )
{
// add the next hypothesis to the list
v.addElement ( populationBitSet [ ChooseNext() ] );
counter++;
}
// hopefully we have enough now
return ( v );
} // END double Continue()
//********************************************************//
/**
* Outputs the distribution for the given output.
*
* @param inst
* the instance for which distribution is to be computed
*
* @return
* the distribution
*
* @exception Exception if something goes wrong
*/
public double[] distributionForInstance ( Instance inst )
throws Exception
{
double [] dis = new double[2];
// classify an instance
double answer = ClassifyInstance ( inst );
dis[0] = 1 - answer;
dis[1] = answer;
return ( dis );
} // END public double[] distributionForInstance ( Instance inst )
// throws Exception
//********************************************************//
/**
* Probabilistically select (r*p)/2 pairs of the
* hypotheses of tempPopulation according to
* fitness. Each pair, produce 2 offspring by
* applying the crossover operator. Return an array of
* these offspring.
*
* @returns
* the offspring
*/
private Vector CrossOver()
{
// the vector to return
Vector v = new Vector();
// start selecting ( r * p ) / 2 pairs
int counter = 0;
int i = 0;
// need 2 temp BitSets
BitSet b1, b2;
// need two new bit sets
BitSet n1, n2;
// let's try to limit the number of times any one
// individual of the population can reproduce
Vector didItVector = new Vector();
// let a certain number of repeats through before
// you don't let something through
int didItCounter = 0;
// let it go up to 10% of the population
int didItMax = m_NumPopulation / 10;
while ( counter < ( m_Replace * m_NumPopulation ) / 2 )
{
b1 = populationBitSet [ ChooseNext() ];
b2 = populationBitSet [ ChooseNext() ];
// make sure b1 and b2 are not equivalent, cause that
// would result in nothing more than duplicating b1 and b2
while ( b1.equals ( b2 ) )
{
b2 = populationBitSet [ ChooseNext() ];
}
// if b1 is already in did it vector,
// increase the did it counter
// if ( didItVector.contains ( b1 ) )
// {
// didItCounter++;
// }
// if b1 or b2 did it already, try to get some new ones
// while ( (didItVector.contains ( b1 )) &&
// (didItCounter >= didItMax) &&
// (didItVector.size() < m_NumPopulation) )
// {
// b1 = populationBitSet [ ChooseNext() ];
// }
// check if did it vector full
// if ( didItVector.size() >= m_NumPopulation )
// {
// didItVector.removeAllElements();
// didItCounter = 0;
// }
// didItVector.addElement ( b1 );
// if b2 is already in did it vector,
// increase the did it counter
// if ( didItVector.contains ( b2 ) )
// {
// didItCounter++;
// }
// while ( (didItVector.contains ( b2 )) &&
// (didItCounter >= didItMax) &&
// (didItVector.size() < m_NumPopulation) )
// {
// b2 = populationBitSet [ ChooseNext() ];
// }
// check if did it vector full
// if ( didItVector.size() >= m_NumPopulation )
// {
// didItVector.removeAllElements();
// didItCounter = 0;
// }
// didItVector.addElement ( b2 );
// clone these to make new ones
n1 = (BitSet)(b1.clone());
n2 = (BitSet)(b2.clone());
// switch the bits at some random point
int randomPoint = random.nextInt ( m_Train.numAttributes() );
// Note that the random.nextInt ( int x ) method returns an
// uniformly distributed integer
// between o (inclusive) and x (exclusive)
for ( i = 0; i < randomPoint; i++ )
{
if ( b1.get ( i ) )
{
n2.set ( i );
}
else
{
n2.clear ( i );
}
if ( b2.get ( i ) )
{
n1.set ( i );
}
else
{
n1.clear ( i );
}
} // end for
// add the new ones to the vector
v.addElement ( n1 );
v.addElement ( n2 );
counter++;
} // end while
return ( v );
} // END Vector CrossOver()
//********************************************************//
/**
* Mutates the population specified according to the
* mutation rate.
*
* @param p
* the population to mutate
*
* @param r
* the rate at which to mutate
*
* @return
* the mutated population
*/
private Vector Mutate ( Vector p, double r )
{
// the vector to return
Vector v = new Vector ( p.size() );
// need a temp bitset
BitSet tempBitSet = null;
// ok, let's loop through the whole vector
Enumeration e = p.elements();
// need a temp index
int index = 0;
int biti = 1;
// number of bits to change, with a min of 1
double numBitChange = Math.max ( 1, (m_Train.numAttributes() * r) );
while ( e.hasMoreElements() )
{
// get the next bitset
tempBitSet = (BitSet)e.nextElement();
// should we mutate this one?
if ( random.nextDouble() <= r )
{
// change bits
for ( biti = 0; biti < numBitChange; biti++ )
{
// change a random bit, but not the last one,
// how do we expect them to get better?
index = random.nextInt ( m_Train.numAttributes() - 1 );
if ( tempBitSet.get ( index ) )
{
tempBitSet.clear ( index );
}
else
{
tempBitSet.set ( index );
}
}
} // end if we mutate this one
// add the bitset to our new population
v.addElement ( tempBitSet );
} // end while e has more
// all done
return ( v );
} // END Vector Mutate ( Vector p, double r )
//********************************************************//
/**
* Computes the probabilty of a hypothesis being
* selected based on fitness.
*
* @return
* the probability
*/
private double Pr ( int hypothesis )
{
switch ( printPr )
{
case 1:
System.out.println ( "Pr = " +
populationFitness [ hypothesis ] +
" / " +
fitnessSum + " = " +
populationFitness [ hypothesis ] / fitnessSum );
break;
}
// make sure we have no zeros
// if ( fitnessSum == 0 )
// {
// return ( 1 );
// }
// if we have a negative sum, we better adjust it
// if ( fitnessSum < 0 )
// {
// return ( ( populationFitness [ hypothesis ] +
// Math.abs ( fitnessSum ) ) /
// Math.abs ( fitnessSum ) );
// }
// nothing special to do
return ( populationFitness [ hypothesis ] /
fitnessSum );
} // END double Pr ( int hypothesis )
//********************************************************//
/**
* Decides if the hypothesis should be choosen
* probabilistically based on fitness
*
* @return
* true or false
*/
private boolean Choose ( int hypothesis )
{
if ( random.nextDouble() <= Pr ( hypothesis ) )
{
switch ( printChoose )
{
case 1:
System.out.println ( "Choose Pr = " + Pr ( hypothesis ) +
", H : " + hypothesis );
break;
}
return ( true );
}
return ( false );
} // END boolean Choose ( int hypothesis )
//********************************************************//
/**
* Picks the next hypothesis to be choosen
*
* @return
* the index of the hypothesis
*/
private int ChooseNext()
{
while ( true )
{
// go to the next hypothesis
populationIndex++;
// are we about to pass the max population index?
if ( populationIndex >= m_NumPopulation )
{
populationIndex = 0;
}
// is this the one?
if ( Choose ( populationIndex ) )
{
return ( populationIndex );
}
}
} // END int ChooseNext()
//********************************************************//
/**
* Returns textual description of classifier.
*/
public String toString()
{
// the string to return
String s = new String();
// need counters
int i, j = 0;
s += "Genetic Algorithm Learner Classifier:\n";
// add the options
for ( i = 0; i < getOptions().length; i++ )
{
s += "\t" + getOptions()[i] + "\t" +
getOptions()[i+1] + "\n";
i++;
}
// also provide the text for the logical
// operation(s) used
switch ( m_Logical )
{
case AND:
s += "\t\t" + AND + " = AND";
break;
case OR:
s += "\t\t" + OR + " = OR";
break;
case XOR:
s += "\t\t" + XOR + " = XOR";
break;
case ANDOR:
s += "\t\t" + ANDOR + " = AND, OR";
break;
case ANDXOR:
s += "\t\t" + ANDXOR + " = AND, XOR";
break;
case ORXOR:
s += "\t\t" + ORXOR + " = OR, XOR";
break;
case ANDORXOR:
s += "\t\t" + ANDORXOR + " = AND, OR, XOR";
break;
} // end switch
s+= "\n";
// add the population
// for ( i = 0; i < m_NumPopulation; i++ )
// {
// s += populationBitSet[i].toString() + "\n";
// }
// all done
return ( s );
} // END public String toString()
//********************************************************//
/**
* Get the value of NumIterations.
*
* @return Value of NumIterations.
*/
public int getNumIterations()
{
return m_NumIterations;
} // END public int getNumIterations()
//********************************************************//
/**
* Set the value of NumIterations.
*
* @param v Value to assign to NumIterations.
*/
public void setNumIterations ( int v )
{
m_NumIterations = v;
} // END public void setNumIterations ( int v )
//********************************************************//
/**
* Get the value of fitness threshold
*
* @return Value of fitness threshold
*/
public double getFitnessThreshold()
{
return m_FitnessThreshold;
} // END public double getFitnessThreshold()
//********************************************************//
/**
* Set the value of FitnessThreshold
*
* @param v Value to assign to FitnessThreshold
*/
public void setFitnessThreshold ( double v )
{
m_FitnessThreshold = v;
} // END public void setFitnessThreshold ( double v )
//********************************************************//
/**
* Get the value of Mutation Rate
*
* @return Value of Mutation Rate
*/
public double getMutationRate()
{
return m_MutationRate;
} // END public double getMutationRate()
//********************************************************//
/**
* Set the value of MutationRate
*
* @param v Value to assign to MutationRate
*/
public void setMutationRate ( double v )
{
m_MutationRate = v;
} // END public void setMutationRate ( double v )
//********************************************************//
/**
* Get the value of Seed.
*
* @return Value of Seed.
*/
public int getSeed()
{
return m_Seed;
} // END public int getSeed()
//********************************************************//
/**
* Set the value of Seed.
*
* @param v Value to assign to Seed.
*/
public void setSeed ( int v )
{
m_Seed = v;
// is there a random object yet?
if ( random == null )
{
// then make a new one silly
random = new Random ( m_Seed );
}
else
{
// just update seed in random
random.setSeed ( m_Seed );
}
} // END public void setSeed ( int v )
//********************************************************//
/**
* Get the value of population number.
*
* @return Value of number of population.
*/
public int getNumPopulation()
{
return m_NumPopulation;
} // END public int getNumPopulation()
//********************************************************//
/**
* Set the number of population.
*
* @param v Value to assign to population number.
*/
public void setNumPopulation ( int v )
{
m_NumPopulation = v;
} // END public void setNumPopulation ( int v )
//********************************************************//
/**
* Get the value of logical operation(s).
*
* @return Value of logical operation(s)
*/
public int getLogical()
{
return ( m_Logical );
} // END public int getLogical()
//********************************************************//
/**
* Set the logical operation(s) to use.
*
* @param v Value to assign to logical operation(s)
*/
public void setLogical ( int v )
{
m_Logical = v;
} // END public void setLogical ( int v )
//********************************************************//
/**
* Get the value of the replace rate
*
* @return Value of the replace rate
*/
public double getReplace()
{
return ( m_Replace );
} // END public double getReplace()
//********************************************************//
/**
* Set the replace rate to use.
*
* @param v Value to assign to the replace rate
*/
public void setReplace ( double v )
{
m_Replace = v;
} // END public void setReplace ( double v )
/******************************************************************/
/**
* Main method.
*/
public static void main ( String[] argv )
{
try
{
System.out.println ( Evaluation.evaluateModel ( new GA(),
argv ) );
}
catch ( Exception e )
{
System.out.println ( e.getMessage() );
}
} // END public static void main ( String[] argv )
//********************************************************//
//********************************************************//
} // END public class GA extends DistributionClassifier
// implements OptionHandler