class GeneticAlgorithm{ int chromosomeLength = 6; int poolSize = 40; int generation = 0; int target; float crossOverRate = 0.7; float mutationRate = 0.001; boolean found = false; char [] trait = { '0','1','2','3','4','5','6','7','8','9','+','-','*','/' }; Vector newGenePool; Vector genePool; GeneticAlgorithm(int target){ this.target = target; newGenePool = new Vector(0); genePool = new Vector(0); for(int i = 0; i < poolSize; i++){ genePool.add(new Chromosome(target)); } } void propagate(){ generation++; newGenePool.clear(); for(int i = genePool.size() - 1; i > -1; i -= 2){ Chromosome p1 = phenotype(genePool); Chromosome p2 = phenotype(genePool); p1.crossOver(p2); p1.mutate(); p2.mutate(); p1.scoreFitness(target); p2.scoreFitness(target); if(p1.total == target && p1.isValid()){ found = true; printout = ("generations: " + generation + ", solution: " + p1.decode()); } if(p2.total == target && p2.isValid()){ found = true; printout = ("generations: " + generation + ", solution: " + p2.decode()); } newGenePool.add(p1); newGenePool.add(p2); } genePool.addAll(newGenePool); } class Chromosome{ StringBuffer dna = new StringBuffer(chromosomeLength * 4); StringBuffer decode = new StringBuffer(chromosomeLength * 4); float score; int total; Chromosome(int target){ for(int i = 0; i < chromosomeLength; i++){ dna.append(binary((int)random(trait.length), 4)); } scoreFitness(target); } Chromosome(StringBuffer dna){ this.dna = dna; } String decode(){ decode.setLength(0); for(int i = 0; i < dna.length()-4; i += 4){ int id = unbinary(dna.substring(i, i+4)); if(id < trait.length){ decode.append(trait[id]); } } return decode.toString(); } void scoreFitness(int target){ total = addUp(); if(total == target){ score = 0; } else{ score = 1.0 / (target - total); } } void crossOver(Chromosome mate){ if(random(1.0) > crossOverRate){ return; } int position = int(random(dna.length())); for(int i = position; i < dna.length()-1; i++){ char temp = dna.charAt(i); dna.setCharAt(i, mate.dna.charAt(i)); mate.dna.setCharAt(i, temp); } } void mutate(){ for(int i = 0; i < dna.length(); i++){ if(random(1.0) <= mutationRate){ dna.setCharAt(i, (dna.charAt(i)=='0' ? '1' : '0')); } } } int addUp(){ String decodedDna = decode(); int calculation = 0; int i = 0; while(i < decodedDna.length()){ char nucleotide = decodedDna.charAt(i); if(Character.isDigit(nucleotide)){ calculation = nucleotide - '0'; i++; break; } else{ i++; } } if(i == decodedDna.length()){ return 0; } boolean isNumber = false; char operand = ' '; while(i < decodedDna.length()){ char nucleotide = decodedDna.charAt(i); if(isNumber && !Character.isDigit(nucleotide)){ i++; continue; } if(!isNumber && Character.isDigit(nucleotide)){ i++; continue; } if(isNumber){ switch(operand){ case '+': calculation += nucleotide - '0'; break; case '-': calculation -= nucleotide - '0'; break; case '*': calculation *= nucleotide - '0'; break; case '/': if(nucleotide != '0'){ calculation /= (nucleotide - '0'); } break; } } else{ operand = nucleotide; } i++; isNumber = !isNumber; } return calculation; } boolean isValid(){ String decodedDna = decode(); boolean isNumber = true; for(int i = 0; i < decodedDna.length(); i++){ char nucleotide = decodedDna.charAt(i); if(isNumber == !Character.isDigit(nucleotide)){ return false; } if(i > 0 && nucleotide == '0' && decodedDna.charAt(i-1) == '/'){ return false; } isNumber = !isNumber; } if(!Character.isDigit(decodedDna.charAt(decodedDna.length()-1))){ return false; } return true; } } Chromosome phenotype(Vector genePool){ float totalFitness = 0.0; for(int i = genePool.size() - 1; i > -1; i--){ Chromosome gene = (Chromosome)genePool.get(i); totalFitness += gene.score; } float qualify = random(totalFitness); totalFitness = 0.0; for(int i = genePool.size() - 1; i > -1; i--){ Chromosome gene = (Chromosome)genePool.get(i); totalFitness += gene.score; if(totalFitness >= qualify){ genePool.remove(i); return gene; } } return (Chromosome)genePool.remove(genePool.size()-1); } }