Created
February 13, 2012 21:53
-
-
Save akawry/1820794 to your computer and use it in GitHub Desktop.
Genetic algorithm for solving the 17x17 4-coloring with no monochromatic rectangle problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.BitSet; | |
import java.util.List; | |
import java.util.Random; | |
public class Challenge17 { | |
/** | |
* The probability that any given bit is mutated, once is a candidate is being mutated | |
*/ | |
public static double MUTATION_RATE = 0.001; | |
/** | |
* The probability that a candidate undergoes mutation | |
*/ | |
public static double MUTATION_PROB = 0.4; | |
/** | |
* The probability that a candidate results from mixing the parents (otherwise just a direct clone) | |
*/ | |
public static double CROSSOVER_PROB = 0.9; | |
/** | |
* The population size | |
*/ | |
public static int POPULATION = 500; | |
public static void main(String[] args) { | |
// create generation 0 | |
List<BitSet[][]> population = new ArrayList<BitSet[][]>(POPULATION); | |
BitSet[][] cand; | |
for (int i = 0; i < POPULATION; i++){ | |
cand = newCandidate(); | |
setRandom(cand); | |
population.add(cand); | |
} | |
// here's where the magic happens | |
int generations = 0; | |
BitSet[][] candidate = null; | |
do { | |
System.out.println("generation: "+generations+", average fitness: "+fitness(population)); | |
candidate = valid(population); | |
population = newGeneration(population); | |
mutate(population); | |
generations++; | |
} while (candidate == null); | |
// if we do find a candidate, print him out | |
prettyPrint(candidate); | |
} | |
private static void setRandom(BitSet[][] sets){ | |
double rand, p = 1.0/sets.length; | |
for (int i = 0; i < 17; i++){ | |
for (int j = 0; j < 17; j++){ | |
rand = Math.random(); | |
for (int k = 0; k < sets.length; k++){ | |
sets[k][i].set(j, rand >= k * p && rand < (k + 1) * p); | |
} | |
} | |
} | |
} | |
/** | |
* Return a valid candidate from the population, if one exists. | |
* Returns null if there are no valid candidates. | |
* @param population | |
* @return | |
*/ | |
private static BitSet[][] valid(List<BitSet[][]> population){ | |
for (BitSet[][] candidate : population){ | |
if (isValid(candidate)) | |
return candidate; | |
} | |
return null; | |
} | |
private static boolean isValid(BitSet[][] sets){ | |
BitSet temp = new BitSet(17); | |
int cardinality; | |
for (int color = 0; color < sets.length; color++){ | |
for (int i = 0; i < 17; i++){ | |
for (int j = i + 1; j < 17; j++){ | |
temp.set(0, 17, true); | |
temp.and(sets[color][i]); | |
sets[color][i].and(sets[color][j]); | |
cardinality = sets[color][i].cardinality(); | |
sets[color][i].set(0, 17); | |
sets[color][i].and(temp); | |
if (cardinality > 1){ | |
return false; | |
} | |
} | |
} | |
} | |
return true; | |
} | |
private static void prettyPrint(BitSet[][] sets){ | |
for (int i = 0; i < 17; i++){ | |
for (int j = 0; j < 17; j++){ | |
for (int k = 0; k < sets.length; k++){ | |
if (sets[k][i].get(j)){ | |
System.out.print(k + " "); | |
break; | |
} | |
} | |
} | |
System.out.println(); | |
} | |
System.out.println(); | |
} | |
/** | |
* Counts the number of pairs of rows which are square free, | |
* across all colors | |
* @param sets | |
* @return | |
*/ | |
private static int fitness(BitSet[][] sets){ | |
int squarefree = 0; | |
int card = 0; | |
BitSet temp = new BitSet(17); | |
for (int c = 0; c < sets.length; c++){ | |
for (int i = 0; i < 17; i++){ | |
for (int j = i + 1; j < 17; j++){ | |
temp.set(0, 17, true); | |
temp.and(sets[c][i]); | |
sets[c][i].and(sets[c][j]); | |
card = sets[c][i].cardinality(); | |
if (card < 2) | |
squarefree++; | |
sets[c][i].set(0, 17); | |
sets[c][i].and(temp); | |
} | |
} | |
} | |
return squarefree; | |
} | |
/** | |
* Simple cross over: take the rows from [0, crossover) from parent A, and the rows [crossover, b.length) | |
* from parent B | |
* @param a | |
* @param b | |
* @param child | |
* @param crossover | |
*/ | |
private static void mate(BitSet[][] a, BitSet[][] b, BitSet[][] child, int crossover){ | |
for (int i = 0; i < 17; i++){ | |
for (int c = 0; c < child.length; c++){ | |
child[c][i].set(0, 17); | |
child[c][i].and(i < crossover ? a[c][i] : b[c][i]); | |
} | |
} | |
} | |
/** | |
* For each colour, we have 17 vectors of 17 bits. | |
* One grid is then a 4-tuple of 17 such vectors | |
* @return | |
*/ | |
private static BitSet[][] newCandidate(){ | |
BitSet[][] cand = new BitSet[4][17]; | |
for (int i = 0; i < 4; i++){ | |
cand[i] = new BitSet[17]; | |
for (int j = 0; j < 17; j++){ | |
cand[i][j] = new BitSet(17); | |
} | |
} | |
return cand; | |
} | |
private static List<BitSet[][]> newGeneration(List<BitSet[][]> population){ | |
List<BitSet[][]> gen = new ArrayList<BitSet[][]>(); | |
Random rand = new Random(); | |
int aFirst, aSecond, aFirstScore, aSecondScore, bFirst, bSecond, bFirstScore, bSecondScore; | |
BitSet[][] a1, a2, b1, b2, child; | |
int n = population.size(); | |
while (gen.size() < n){ | |
/* | |
* Tournament selection: | |
* Pick two individuals at random, keeping the more fit one and removing the less fit one from the gene pool. | |
* Pick another two individuals at random, again keeping the more fit and removing the less fit from the gene pool. | |
* | |
* Finally, let these two 'winners' mate and produce 2 offspring, which is added to the new generation. | |
*/ | |
aFirst = rand.nextInt(population.size()); | |
aSecond = rand.nextInt(population.size()); | |
bFirst = rand.nextInt(population.size()); | |
bSecond = rand.nextInt(population.size()); | |
a1 = population.get(aFirst); | |
aFirstScore = fitness(a1); | |
a2 = population.get(aSecond); | |
aSecondScore = fitness(a2); | |
b1 = population.get(bFirst); | |
bFirstScore = fitness(b1); | |
b2 = population.get(bSecond); | |
bSecondScore = fitness(b1); | |
if (Math.random() < CROSSOVER_PROB){ | |
int crossover = rand.nextInt(17); | |
child = newCandidate(); | |
mate(aFirstScore > aSecondScore ? a1 : a2, bFirstScore > bSecondScore ? b1 : b2, child, crossover); | |
gen.add(child); | |
child = newCandidate(); | |
mate(aFirstScore > aSecondScore ? a1 : a2, bFirstScore > bSecondScore ? b1 : b2, child, 16 - crossover); | |
gen.add(child); | |
} else { | |
gen.add(aFirstScore > aSecondScore ? a1 : a2); | |
gen.add(bFirstScore > bSecondScore ? b1 : b2); | |
} | |
if (aFirstScore < aSecondScore) | |
population.remove(a1); | |
else | |
population.remove(a2); | |
if (bFirstScore < bSecondScore) | |
population.remove(b1); | |
else | |
population.remove(b2); | |
} | |
return gen; | |
} | |
private static double fitness(List<BitSet[][]> population){ | |
double fitness = 0; | |
for (BitSet[][] candidate : population){ | |
fitness += fitness(candidate); | |
} | |
return fitness / population.size(); | |
} | |
private static void mutate(BitSet[][] candidate){ | |
int rand; | |
for (int i = 0; i < 17; i++){ | |
for (int j = 0; j < 17; j++){ | |
if (Math.random() < MUTATION_RATE){ | |
rand = (int) Math.floor(Math.random() * candidate.length); | |
for (int k = 0; k < candidate.length; k++){ | |
candidate[k][i].set(j, k == rand); | |
} | |
} | |
} | |
} | |
} | |
private static void mutate(List<BitSet[][]> population){ | |
for (BitSet[][] cand : population){ | |
if (Math.random() < MUTATION_PROB) | |
mutate(cand); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment