/*
    ExampleGA.java
    CIS 123
    David G. Klick
    2012-11-18
    2017-08-26 Updated with minor mods by D. Klick

    Simple demonstration of genetic algorithm techniques.
    This code starts with a random selection of strings
    and tries to evolve to "Management Information Systems"
    through selection, cross-breeding, and mutation. To
    simplify the code and speed up the process, all of the
    population is set to have messages the same length as
    the trget string. The code limits the number of
    generations and only displays those generations where
    a "more fit" member has been found.
*/

import java.util.*;

public class ExampleGA {
    private static final double MUTATION_RATE = 0.03;
    private static final int POPSIZE = 1000;
    private static final int MAX_GENERATIONS = 1000;
    private static final int ELITISM = 50;
    
    public static void main(String[] args) {
        Random rnd = new Random();
        Chromo[] pop = new Chromo[POPSIZE];
        int i, eliteNum = ELITISM;
        if (eliteNum < 0) eliteNum = 0;
        if (eliteNum >= POPSIZE) eliteNum = POPSIZE / 10;
        for (i=0; i<pop.length; i++) pop[i] = new Chromo();
        System.out.printf("%3s %8s  %5s  %s\n", "Gen", " Average", " Best", "Most fit phrase");
        System.out.printf("%3s %8s  %5s  %s\n", "---", "--------", "-----", "------------------------------");
        int generation = 0;
        String bestPhrase = "";
        do {
            Arrays.sort(pop);  // sort by fitness score
            if (!bestPhrase.equals(pop[0].getChromo())) {
                System.out.printf("%3d %8.2f  %5d  %s\n", generation, getAverageFitness(pop), pop[0].getFitness(), pop[0].getChromo());
                bestPhrase = pop[0].getChromo();
            }
            // cross breed - best are at end, so use them more
            for (i=pop.length-eliteNum-1; i>=eliteNum; i--) {
                int p1 = rnd.nextInt(i);
                int p2 = p1;
                while (p1 == p2) p2 = rnd.nextInt(i);
                pop[i].cross(pop[p1], pop[p2]);
            }
            
            // mutate
            for (i=pop.length-eliteNum-1; i>=eliteNum; i--) pop[i].mutate(MUTATION_RATE);
            generation++;
        } while (generation<=MAX_GENERATIONS && pop[0].getFitness() != 0);
    }
    
    private static double getAverageFitness(Chromo[] p) {
        double tot = 0.0;
        for (int i=0; i<p.length; i++) tot += p[i].getFitness();
        return tot / p.length;
    }
}


class Chromo implements Comparable<Chromo> {
    public static boolean useAlternateCross = true;
    public static final String target = "Management Information Systems";
    public static final int targetLength = target.length();
    private char[] chromo = new char[targetLength];
    private int fit;
    private static Random rnd = new Random();
    private static String printable = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!~@#$%^&*()_+=-{}[]|\\:;<>,.?/'\"` ";

    public int compareTo(Chromo obj) {
        return fit - obj.fit;
    }
    
    private static char getRandomPrintableChar() {
        return printable.charAt(rnd.nextInt(printable.length()));
    }
    
    public Chromo() {
        for (int i=0; i<chromo.length; i++) chromo[i] = getRandomPrintableChar();
        fit = fitness();
    }

    public Chromo(Chromo p1, Chromo p2) {
        cross(p1, p2);
    }

    public void cross(Chromo p1, Chromo p2) {
        // Two cross-breeding algorithms are available in this method
        if (useAlternateCross) {
            for (int i=0; i<targetLength; i++) chromo[i] = rnd.nextInt(2) == 0 ? p1.chromo[i] : p2.chromo[i];
        } else {
            int r1 = rnd.nextInt(targetLength);
            int r2 = rnd.nextInt(targetLength - r1) + r1;
            int i;
            for (i=0; i<r1; i++) chromo[i] = p1.chromo[i];
            for (i=r1; i<r2; i++) chromo[i] = p2.chromo[i];
            for (i=r2; i<targetLength; i++) chromo[i] = p1.chromo[i];
        }
        fit = fitness();
    }

    public void mutate(double mutationRate) {
        if (mutationRate <= 0) return;
        if (mutationRate > 1.0) mutationRate = 1.0;
        for (int i=0; i<targetLength; i++) if (rnd.nextDouble() < mutationRate) chromo[i] = getRandomPrintableChar();
        fit = fitness();
    }
    
    public int fitness() {
        int f = 0;
        for (int i=0; i<chromo.length; i++) f += (int) Math.pow(chromo[i]-target.charAt(i), 2);
        return f;
    }
    
    public String getChromo() { return new String(chromo); }
    public int getFitness() { return fit; }
    public String toString() { return getChromo() + " (" + fit + ")"; }
    
}