jpayne@68: package fun;
jpayne@68: 
jpayne@68: import java.util.Arrays;
jpayne@68: import java.util.Random;
jpayne@68: 
jpayne@68: public class Genetic {
jpayne@68: 	
jpayne@68: 	public static void main(String[] args){
jpayne@68: 		Genetic g=new Genetic(args);
jpayne@68: 		long answer=g.solve();
jpayne@68: 		System.out.println(Long.toBinaryString(answer)+" \t-> "+f(answer));
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public Genetic(String[] args){
jpayne@68: 		pop=(args.length>0 ? Integer.parseInt(args[0]) : 20);
jpayne@68: 		bits=(args.length>1 ? Integer.parseInt(args[1]) : 8);
jpayne@68: 		iters=(args.length>2 ? Integer.parseInt(args[2]) : 20);
jpayne@68: 		mutProb=(args.length>3 ? Double.parseDouble(args[3]) : 0.01);
jpayne@68: 		mask=(bits>63 ? -1L : ~((-1L)<<bits));
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public long solve(){
jpayne@68: 		final long mask=(bits>63 ? -1L : ~((-1L)<<bits));
jpayne@68: 		double[] prob=new double[pop];
jpayne@68: 		Bug[] current=new Bug[pop];
jpayne@68: 		for(int i=0; i<pop; i++){
jpayne@68: 			current[i]=new Bug(randy.nextLong()&mask);
jpayne@68: 		}
jpayne@68: 		Arrays.sort(current);
jpayne@68: 		Bug best=current[current.length-1];
jpayne@68: 		
jpayne@68: 		for(int i=0; i<iters; i++){
jpayne@68: 			
jpayne@68: 			if(true){
jpayne@68: 				System.out.println("Iteration "+i+": "+current[current.length-1]);
jpayne@68: 			}
jpayne@68: 			
jpayne@68: 			current=iterate(current, prob);
jpayne@68: 			Arrays.sort(current);
jpayne@68: 			if(best.compareTo(current[current.length-1])<0){best=current[current.length-1];}
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		return best.dna;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public Bug[] iterate(Bug[] current, double[] prob){
jpayne@68: 		Arrays.fill(prob,  0);
jpayne@68: 		double sum=0;
jpayne@68: 		for(int i=0; i<current.length; i++){
jpayne@68: 			Bug b=current[i];
jpayne@68: 			sum+=b.fitness;
jpayne@68: 			prob[i]=b.fitness;
jpayne@68: 		}
jpayne@68: 		double mult=1/sum;
jpayne@68: 		prob[0]*=mult;
jpayne@68: 		
jpayne@68: 		for(int i=1; i<prob.length; i++){
jpayne@68: 			prob[i]=prob[i-1]+prob[i]*mult;
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		Bug[] next=new Bug[current.length];
jpayne@68: 		for(int i=0; i<next.length; i++){
jpayne@68: 			long babyDna=breed(current, prob, mutProb);
jpayne@68: 			next[i]=new Bug(babyDna);
jpayne@68: 		}
jpayne@68: 		return next;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public long breed(Bug[] current, double[] prob, double mutProb){
jpayne@68: 		double fa=randy.nextDouble();
jpayne@68: 		double fb=randy.nextDouble();
jpayne@68: 		Bug a=current[findIndex(fa, prob)];
jpayne@68: 		Bug b=current[findIndex(fb, prob)];
jpayne@68: 		long crossover=randy.nextLong();
jpayne@68: 		long baby=(a.dna&crossover)|(b.dna&~crossover);
jpayne@68: 		if(mutProb>0 && randy.nextDouble()<mutProb){
jpayne@68: 			long bit=(1L<<randy.nextInt(bits));
jpayne@68: 			baby^=bit;
jpayne@68: 		}
jpayne@68: 		return baby;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public int findIndex(double f, double[] prob){
jpayne@68: 		for(int i=pop-1; i>0; i--){
jpayne@68: 			if(prob[i-1]<f){return i;}
jpayne@68: 		}
jpayne@68: 		return 0;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public static double f(long x){
jpayne@68: 		return x*x;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private static class Bug implements Comparable<Bug> {
jpayne@68: 		
jpayne@68: 		public Bug(long dna_){
jpayne@68: 			dna=dna_;
jpayne@68: 			fitness=f(dna);
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		@Override
jpayne@68: 		public int compareTo(Bug b){
jpayne@68: 			return (fitness<b.fitness ? -1 : fitness>b.fitness ? 1 : 0);
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		@Override
jpayne@68: 		public String toString(){
jpayne@68: 			return Long.toBinaryString(dna)+" \t-> "+fitness;
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		final long dna;
jpayne@68: 		final double fitness;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public static final Random randy=new Random();
jpayne@68: 
jpayne@68: 	final int pop;
jpayne@68: 	final int bits;
jpayne@68: 	final int iters;
jpayne@68: 	final double mutProb;
jpayne@68: 	
jpayne@68: 	final long mask;
jpayne@68: 	
jpayne@68: }