|
jpayne@68
|
1 package fun;
|
|
jpayne@68
|
2
|
|
jpayne@68
|
3 import java.util.Arrays;
|
|
jpayne@68
|
4 import java.util.Random;
|
|
jpayne@68
|
5
|
|
jpayne@68
|
6 public class Genetic {
|
|
jpayne@68
|
7
|
|
jpayne@68
|
8 public static void main(String[] args){
|
|
jpayne@68
|
9 Genetic g=new Genetic(args);
|
|
jpayne@68
|
10 long answer=g.solve();
|
|
jpayne@68
|
11 System.out.println(Long.toBinaryString(answer)+" \t-> "+f(answer));
|
|
jpayne@68
|
12 }
|
|
jpayne@68
|
13
|
|
jpayne@68
|
14 public Genetic(String[] args){
|
|
jpayne@68
|
15 pop=(args.length>0 ? Integer.parseInt(args[0]) : 20);
|
|
jpayne@68
|
16 bits=(args.length>1 ? Integer.parseInt(args[1]) : 8);
|
|
jpayne@68
|
17 iters=(args.length>2 ? Integer.parseInt(args[2]) : 20);
|
|
jpayne@68
|
18 mutProb=(args.length>3 ? Double.parseDouble(args[3]) : 0.01);
|
|
jpayne@68
|
19 mask=(bits>63 ? -1L : ~((-1L)<<bits));
|
|
jpayne@68
|
20 }
|
|
jpayne@68
|
21
|
|
jpayne@68
|
22 public long solve(){
|
|
jpayne@68
|
23 final long mask=(bits>63 ? -1L : ~((-1L)<<bits));
|
|
jpayne@68
|
24 double[] prob=new double[pop];
|
|
jpayne@68
|
25 Bug[] current=new Bug[pop];
|
|
jpayne@68
|
26 for(int i=0; i<pop; i++){
|
|
jpayne@68
|
27 current[i]=new Bug(randy.nextLong()&mask);
|
|
jpayne@68
|
28 }
|
|
jpayne@68
|
29 Arrays.sort(current);
|
|
jpayne@68
|
30 Bug best=current[current.length-1];
|
|
jpayne@68
|
31
|
|
jpayne@68
|
32 for(int i=0; i<iters; i++){
|
|
jpayne@68
|
33
|
|
jpayne@68
|
34 if(true){
|
|
jpayne@68
|
35 System.out.println("Iteration "+i+": "+current[current.length-1]);
|
|
jpayne@68
|
36 }
|
|
jpayne@68
|
37
|
|
jpayne@68
|
38 current=iterate(current, prob);
|
|
jpayne@68
|
39 Arrays.sort(current);
|
|
jpayne@68
|
40 if(best.compareTo(current[current.length-1])<0){best=current[current.length-1];}
|
|
jpayne@68
|
41 }
|
|
jpayne@68
|
42
|
|
jpayne@68
|
43 return best.dna;
|
|
jpayne@68
|
44 }
|
|
jpayne@68
|
45
|
|
jpayne@68
|
46 public Bug[] iterate(Bug[] current, double[] prob){
|
|
jpayne@68
|
47 Arrays.fill(prob, 0);
|
|
jpayne@68
|
48 double sum=0;
|
|
jpayne@68
|
49 for(int i=0; i<current.length; i++){
|
|
jpayne@68
|
50 Bug b=current[i];
|
|
jpayne@68
|
51 sum+=b.fitness;
|
|
jpayne@68
|
52 prob[i]=b.fitness;
|
|
jpayne@68
|
53 }
|
|
jpayne@68
|
54 double mult=1/sum;
|
|
jpayne@68
|
55 prob[0]*=mult;
|
|
jpayne@68
|
56
|
|
jpayne@68
|
57 for(int i=1; i<prob.length; i++){
|
|
jpayne@68
|
58 prob[i]=prob[i-1]+prob[i]*mult;
|
|
jpayne@68
|
59 }
|
|
jpayne@68
|
60
|
|
jpayne@68
|
61 Bug[] next=new Bug[current.length];
|
|
jpayne@68
|
62 for(int i=0; i<next.length; i++){
|
|
jpayne@68
|
63 long babyDna=breed(current, prob, mutProb);
|
|
jpayne@68
|
64 next[i]=new Bug(babyDna);
|
|
jpayne@68
|
65 }
|
|
jpayne@68
|
66 return next;
|
|
jpayne@68
|
67 }
|
|
jpayne@68
|
68
|
|
jpayne@68
|
69 public long breed(Bug[] current, double[] prob, double mutProb){
|
|
jpayne@68
|
70 double fa=randy.nextDouble();
|
|
jpayne@68
|
71 double fb=randy.nextDouble();
|
|
jpayne@68
|
72 Bug a=current[findIndex(fa, prob)];
|
|
jpayne@68
|
73 Bug b=current[findIndex(fb, prob)];
|
|
jpayne@68
|
74 long crossover=randy.nextLong();
|
|
jpayne@68
|
75 long baby=(a.dna&crossover)|(b.dna&~crossover);
|
|
jpayne@68
|
76 if(mutProb>0 && randy.nextDouble()<mutProb){
|
|
jpayne@68
|
77 long bit=(1L<<randy.nextInt(bits));
|
|
jpayne@68
|
78 baby^=bit;
|
|
jpayne@68
|
79 }
|
|
jpayne@68
|
80 return baby;
|
|
jpayne@68
|
81 }
|
|
jpayne@68
|
82
|
|
jpayne@68
|
83 public int findIndex(double f, double[] prob){
|
|
jpayne@68
|
84 for(int i=pop-1; i>0; i--){
|
|
jpayne@68
|
85 if(prob[i-1]<f){return i;}
|
|
jpayne@68
|
86 }
|
|
jpayne@68
|
87 return 0;
|
|
jpayne@68
|
88 }
|
|
jpayne@68
|
89
|
|
jpayne@68
|
90 public static double f(long x){
|
|
jpayne@68
|
91 return x*x;
|
|
jpayne@68
|
92 }
|
|
jpayne@68
|
93
|
|
jpayne@68
|
94 private static class Bug implements Comparable<Bug> {
|
|
jpayne@68
|
95
|
|
jpayne@68
|
96 public Bug(long dna_){
|
|
jpayne@68
|
97 dna=dna_;
|
|
jpayne@68
|
98 fitness=f(dna);
|
|
jpayne@68
|
99 }
|
|
jpayne@68
|
100
|
|
jpayne@68
|
101 @Override
|
|
jpayne@68
|
102 public int compareTo(Bug b){
|
|
jpayne@68
|
103 return (fitness<b.fitness ? -1 : fitness>b.fitness ? 1 : 0);
|
|
jpayne@68
|
104 }
|
|
jpayne@68
|
105
|
|
jpayne@68
|
106 @Override
|
|
jpayne@68
|
107 public String toString(){
|
|
jpayne@68
|
108 return Long.toBinaryString(dna)+" \t-> "+fitness;
|
|
jpayne@68
|
109 }
|
|
jpayne@68
|
110
|
|
jpayne@68
|
111 final long dna;
|
|
jpayne@68
|
112 final double fitness;
|
|
jpayne@68
|
113 }
|
|
jpayne@68
|
114
|
|
jpayne@68
|
115 public static final Random randy=new Random();
|
|
jpayne@68
|
116
|
|
jpayne@68
|
117 final int pop;
|
|
jpayne@68
|
118 final int bits;
|
|
jpayne@68
|
119 final int iters;
|
|
jpayne@68
|
120 final double mutProb;
|
|
jpayne@68
|
121
|
|
jpayne@68
|
122 final long mask;
|
|
jpayne@68
|
123
|
|
jpayne@68
|
124 }
|
