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