genetic.java

基于java实现的遗传算法的源代码

// Genetic Algorithm Java classes
//
// Copyright 1996, Mark Watson.  All rights reserved.

import java.util.*;

abstract public class Genetic {

   protected int numGenesPerChromosome;  // number of genes per chromosome
   protected int numChromosomes;  // number of chromosomes
   private BitSet chromosomes[];
   protected float fitness[];
   private float crossoverFraction;
   private float mutationFraction;
   private int [] rouletteWheel;
    private int rouletteWheelSize;

   public Genetic(int num_genes_per_chromosome, int num_chromosomes) {
       this(num_genes_per_chromosome, num_chromosomes, 0.8f, 0.01f);
   }
   public Genetic(int num_genes_per_chromosome, int num_chromosomes,
		  float crossover_fraction, float mutation_fraction) {
       numGenesPerChromosome = num_genes_per_chromosome;
       numChromosomes = num_chromosomes;
       crossoverFraction = crossover_fraction;
       mutationFraction = mutation_fraction;
       chromosomes = new BitSet[num_chromosomes];
       for (int i=0; i<num_chromosomes; i++) {
          chromosomes[i] = new BitSet(num_genes_per_chromosome);
          for (int j=0; j<num_genes_per_chromosome; j++) {
             if (Math.random() < 0.5) chromosomes[i].set(j);
          }
       }
       fitness = new float[num_chromosomes];
       for (int f=0; f<num_chromosomes; f++)  {
         fitness[f] = -999;
       }
       sort();
       // define the roulette wheel:
       rouletteWheelSize = 0;
       for (int i=0; i<numGenesPerChromosome; i++) {
	   rouletteWheelSize += i + 1;
       }
       System.out.println("count of slots in roulette wheel=" + rouletteWheelSize);
       rouletteWheel = new int[rouletteWheelSize];
       int num_trials = numGenesPerChromosome;
       int index = 0;
       for (int i=0; i<numGenesPerChromosome; i++) {
	   for (int j=0; j<num_trials; j++) {
	       rouletteWheel[index++] = i;
	   }
	   num_trials--;
       }
   }
    public boolean getGene(int chromosome, int gene) {
       return chromosomes[chromosome].get(gene);
    }
    public void setGene(int chromosome, int gene, int value) {
        if (value == 0)  chromosomes[chromosome].clear(gene);
        else             chromosomes[chromosome].set(gene);
    }
    public void setGene(int chromosome, int gene, boolean value) {
        if (value)  chromosomes[chromosome].set(gene);
        else        chromosomes[chromosome].clear(gene);
    }
    public void sort() {
       BitSet btemp;
       for (int c=0; c<numChromosomes; c++) {
           for (int d=(numChromosomes - 2); d>=c; d--) {
                if (fitness[d] < fitness[d+1]) {
                   btemp = chromosomes[d];
                   float x = fitness[d];
                   chromosomes[d] = chromosomes[d+1];
                   fitness[d] = fitness[d+1];
                   chromosomes[d+1] = btemp;
                   fitness[d+1] = x;
                }
            }
        }
    }
    public void evolve() {
	calcFitness();
	sort();
	doCrossovers();
	doMutations();
	doRemoveDuplicates();
    }
    public void doCrossovers()  {
      int num = (int)(numChromosomes * crossoverFraction);
      for (int i=num-1; i>=0; i--) {
	  int c1 = (int)(rouletteWheelSize * Math.random() * 0.9999f);
	  int c2 = (int)(rouletteWheelSize * Math.random() * 0.9999f);
	  c1 = rouletteWheel[c1];
	  c2 = rouletteWheel[c2];
	  if (c1 != c2) {
	      int locus = 1 + (int)((numGenesPerChromosome - 2) * Math.random());
	      for (int g=0; g<numGenesPerChromosome; g++) {
		  if (g < locus) {
		      setGene(i, g, getGene(c1, g));
		  } else {
		      setGene(i, g, getGene(c2, g));
		  }
	      }
	  }
      }
    }
    // 'to' and 'from' are 'sorted' indices:
    private void copyGene(int to, int from) {
       for (int i=0; i<numGenesPerChromosome; i++)
            if (getGene(from, i))  setGene(to, i, 1);
            else                   setGene(to, i, 0);
    }
    public void doMutations() {
      int num = (int)(numChromosomes * mutationFraction);
      for (int i=0; i<num; i++) {
	  int c = (int)(numChromosomes * Math.random() * 0.99);
	  int g = (int)(numGenesPerChromosome * Math.random() * 0.99);
	  setGene(c, g, !getGene(c, g));
      }
    }
    public void doRemoveDuplicates() {
	for (int i=numChromosomes - 1; i>3; i--) {
	    for (int j=0; j<i; j++) {
		if (chromosomes[i].equals(chromosomes[j])) {
		    int g = (int)(numGenesPerChromosome * Math.random() * 0.99);
		    setGene(i, g, !getGene(i, g));
		    break;
		}
	    }
	}
    }
    // Override the following function in sub-classes:
    abstract public void calcFitness() ;
}





































int randbot ()  /* Random (Optimal) */
{
    /* generate action uniformly at random (optimal strategy) */
    return( random() % 3);
}

int rockbot ()  /* Good Ole Rock */
{
    /* "Good ole rock.  Nuthin' beats rock." */
    return(rock);
}

int r226bot ()  /* R-P-S 20-20-60 */
{
    /* play 20% rock, 20% paper, 60% scissors */
    return( biased_roshambo(0.2, 0.2));
}

int rotatebot ()  /* Rotate R-P-S */
{
    /* rotate choice each turn r -> p -> s */
    return( my_history[0] % 3);
}

int copybot ()  /* Beat Last Move */
{
    /* do whatever would have beat the opponent last turn */
    return( (opp_history[opp_history[0]] + 1) % 3);
}

int switchbot ()  /* Always Switchin' */
{
    /* never repeat the previous pick */
    if ( my_history[my_history[0]] == rock ) {
        return( biased_roshambo(0.0, 0.5) ); }
    else if ( my_history[my_history[0]] == paper ) {
        return( biased_roshambo(0.5, 0.0) ); }
    else return( biased_roshambo(0.5, 0.5) );
}

int freqbot ()  /* Beat Frequent Pick */
{
    /* beat the opponent's most frequent choice */

    int i, rcount, pcount, scount;

    rcount = 0;  pcount = 0;  scount = 0;
    for (i = 1; i <= opp_history[0]; i++) {
        if (opp_history[i] == rock)            { rcount++; }
        else if (opp_history[i] == paper)      { pcount++; }
        else /* opp_history[i] == scissors */  { scount++; }
    }
    if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
    else if ( pcount > scount ) { return(scissors); }
    else { return(rock); }
}

int freqbot2 ()  /* Beat Frequent Pick (again) */
{
    /* maintain stats with static variables to avoid re-scanning
       the history array  (based on code by Don Beal) */

    static int rcount, pcount, scount;
    int opp_last;

    if( opp_history[0] == 0 ) {
        rcount = 0;  pcount = 0;  scount = 0;  }
    else {
      opp_last = opp_history[opp_history[0]];
      if ( opp_last == rock)          { rcount++; }
      else if ( opp_last == paper)    { pcount++; }
      else /* opp_last == scissors */ { scount++; }
    }
    if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
    else if ( pcount > scount ) { return(scissors); }
    else { return(rock); }
}