Genetic algorithm for solving the 17x17 4-coloring with no monochromatic rectangle problem

gistfile1.java

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);
        }
    }
}