GA.java

import java.util.*; 
/** * @author Kunuk Nykjaer */ 
public class GA {    
 static long BEGIN; 
 static final boolean _DEBUG = true;   
 LinkedList<Candidate> population = new LinkedList<Candidate>();  
 final Random rand;   
 final int populationSize = 10;
 final int parentUsePercent = 10; 
 
 public GA() {        
	rand = new Random();
	for (int i = 0; i < populationSize; i++) { 
		Candidate c = new Candidate(); 
		c.random(); 
		population.add(c); 
	}   
	Collections.sort(population); 
	// sort method    
    System.out.println("Init population sorted"); 
	print();  
} 
    void print() { 
		System.out.println("-- print");    
		for (Candidate c : population) {    
			System.out.println(c);     
		}  
	}
	
	 /**    
	 * Selection strategy: Tournament method 
	 * Replacement strategy: elitism 10% and steady state 
	 * find 4 random in population not same    
	 * let 2 fight, and 2 fight     
	 * the winners makes 2 children   
	 */
	 
	 
	 void produceNextGen() {        
		LinkedList<Candidate> newpopulation = new LinkedList<Candidate>();                     
		while (newpopulation.size() < populationSize * (1.0-(parentUsePercent/100.0)) ) { 
			int size = population.size();      
			int i = rand.nextInt(size);     
			int j, k, l;   
			j = k = l = i;    
			while (j == i)     
				j = rand.nextInt(size);    
			while (k == i || k == j)      
				k = rand.nextInt(size);    
			while (l == i || l == j || k == l)     
				l = rand.nextInt(size);    
			Candidate c1 = population.get(i);  
			Candidate c2 = population.get(j);   
			Candidate c3 = population.get(k);       
			Candidate c4 = population.get(l);      
			int f1 = c1.fitness();      
			int f2 = c2.fitness();       
			int f3 = c3.fitness();     
			int f4 = c4.fitness();           
			Candidate w1, w2;       
			if (f1 > f2)
				w1 = c1;    
            else     
				w1 = c2;       
			if (f3 > f4)    
				w2 = c3;   
			else      
				w2 = c4;      
			Candidate child1, child2;
			// Method one-point crossover random pivot
			// int pivot = rand.nextInt(Candidate.SIZE-2) + 1; // cut interval is 1 .. size-1 
			//child1 = newChild(w1,w2,pivot);
			//child2 = newChild(w2,w1,pivot);
			
			// Method uniform crossover          

			Candidate[] childs = newChilds(w1,w2);   
			child1 = childs[0];  
			child2 = childs[1];        
			double mutatePercent = 0.01;     
			boolean m1 = rand.nextFloat() <= mutatePercent;     
			boolean m2 = rand.nextFloat() <= mutatePercent;
			
			if(m1)     
				mutate(child1);      
			if(m2)      
				mutate(child2); 
			boolean isChild1Good = child1.fitness() >= w1.fitness(); 
			boolean isChild2Good = child2.fitness() >= w2.fitness();    
			newpopulation.add( isChild1Good ? child1 : w1);      
			newpopulation.add( isChild2Good ? child2 : w2);
		}
			
		// add top percent parent      
		int j = (int)(populationSize*parentUsePercent/100.0);     
		for (int i = 0; i < j; i++) {         
			newpopulation.add( population.get(i));   
		}    
		population=newpopulation;       
		Collections.sort(population);
		
	}
	// one-point crossover random pivot  
	Candidate newChild(Candidate c1, Candidate c2, int pivot) {
		Candidate child = new Candidate();     
		for (int i = 0; i < pivot; i++) {       
			child.genotype[i] = c1.genotype[i];     
		}   
		for (int j = pivot; j < Candidate.SIZE; j++) {     
			child.genotype[j] = c2.genotype[j];      
		}        
		return child;    
	}

	// Uniform crossover  
	Candidate[] newChilds(Candidate c1, Candidate c2) {  
		Candidate child1 = new Candidate();   
		Candidate child2 = new Candidate();      
		for (int i = 0; i < Candidate.SIZE; i++) {    
			boolean b = rand.nextFloat() >= 0.5;      
			if(b){ 
				child1.genotype[i] = c1.genotype[i];     
				child2.genotype[i] = c2.genotype[i];    
			}     
			else{
				child1.genotype[i] = c2.genotype[i]; 
				child2.genotype[i] = c1.genotype[i];   
			}    
		}   
		return new Candidate[]{child1,child2} ;    
	}   
	
	void mutate(Candidate c) {   
		int i = rand.nextInt(Candidate.SIZE);   
		c.genotype[i] = !c.genotype[i]; // flip 
	} 

    public static void main(String[] args) {    
		BEGIN = System.currentTimeMillis(); 
        GA ga = new GA();   
		ga.run();     
		long END = System.currentTimeMillis();     
		System.out.println("Time: " + (END - BEGIN) / 1000.0 + " sec.");
	}  

	void run() {    
		final int maxSteps = 50000;    
		int count = 0;  
		while (count < maxSteps) {     
			count++;       
			produceNextGen();     
		}      
		System.out.println("\nResult");     
		print();  
	}
	
	
	public class Candidate implements Comparable<Candidate> {   
		public static final int SIZE = 10;      
		public boolean[] genotype;     
		
		public Candidate() {  
			genotype = new boolean[SIZE];       
        }  

		void random() { 
			for (int i = 0; i < genotype.length; i++) {    
				genotype[i] = 0.5 > rand.nextFloat();    
			}     
		}       

		private String gene()        {    
			StringBuilder sb = new StringBuilder();    
			for (int i = 0; i < genotype.length; i++) {     
				sb.append(genotype[i] == true ? 1 : 0);   
			}  
			return sb.toString();    
		}     

		int fitness() {    
			int sum = 0; 
			for (int i = 0; i < genotype.length; i++) {     
				if (genotype[i])       
					sum++; 
			}        
			return sum;    
		}      

		public int compareTo(Candidate o) {      
			int f1 = this.fitness();        
			int f2 = o.fitness();      
			if (f1 < f2)  
				return 1;  
			else if (f1 > f2)   
				return -1;   
			else 
				return 0;   
		}    

		@Override  
		public String toString() { 
			return "gene="+gene()+" fit="+fitness();  
		} 
	}
}