//Evolutionary Computation and Artificial Life (202-1-5171), Semester A, 2006/7
//Eyal Liss, 040170789
//David Suissa, 040580003

public class Question5 {

    final int NUMBER_OF_BITS = 50;
    final int POPULATION_SIZE = 200;
    final int GENERATIONS = 500;
    final double Pc = 0.7;
    final double Pm = 0.001;

    private static final int C = 625;
    final int[][] Items ={  {47,23}, {21,3}, {20,2}, {34,6}, {23,22}, {22,43}, {24,4}, {2,24}, {32,13}, {9,10},
                            {10,43}, {6,6}, {21,22}, {22,35}, {11,42}, {12,1}, {18,7}, {12,31}, {5,7}, {41,23},
                            {22,18}, {32,5}, {21,32}, {28,13}, {0,32}, {25,11}, {23,29}, {5,3}, {12,32}, {41,16},
                            {28,11}, {41,47}, {21,9}, {32,29}, {18,26}, {14,42}, {46,42}, {2,15}, {31,30}, {31,34},
                            {15,5}, {48,44}, {39,3}, {4,0}, {30,45}, {23,20}, {16,23}, {17,40}, {31,5}, {19,39},
                          };


    public void run() {

        String []population = new String[POPULATION_SIZE];

        //initiate population
        //our representation is bitstring with length 50
        for (int i = 0; i < POPULATION_SIZE; ++i)
            population[i] = getRandomIndavidual();

        String bestOfAllTimes ="";
        int bestYVal=0;
        System.out.println("Generation,Best,Average,Representation,Weight");
        for (int g = 0; g < GENERATIONS; ++g) {

            population = selection(population);
            population = crossover(population);
            population = mutation(population);

            String max_individual = "";
            int max_fitness = 0;
            int SumVal = 0;
            //calculate the Best & Average values
            for (int i = 0; i < POPULATION_SIZE; ++i) {
                int val = fitness(population[i]);
                if (max_fitness < val) {
                    max_fitness = val;
                    max_individual = population[i];
                }
                SumVal += val;
            }
            if (max_fitness >=bestYVal) {
                bestYVal = max_fitness;
                bestOfAllTimes = g + ", " + max_fitness + ", " + ((double)SumVal / POPULATION_SIZE)+", "+max_individual +", "+culcAllWeight(max_individual);
            }
            System.out.println(g + ", " + max_fitness + ", " + ((double)SumVal / POPULATION_SIZE)+", "+max_individual +", "+culcAllWeight(max_individual));

        }
        System.out.println("\nThe Best of All Times = "+bestOfAllTimes);
    }


    private int culcAllWeight(String individual) {
        int weight=0;
        for(int i=0;i<NUMBER_OF_BITS;++i)
            weight+=(individual.charAt(i)=='1'?Items[i][1]:0);
        return weight;
    }


    private String[] selection(String[] population) {
        double []p = new double[POPULATION_SIZE];
        double []c = new double[POPULATION_SIZE];
        double s = 0;

        //calculate the s (total fitness)
        for (int i = 0; i < POPULATION_SIZE; ++i)
            s += fitness(population[i]);

        //calculate the probability Pi
        for (int i = 0; i < POPULATION_SIZE; ++i)
            p[i] = fitness(population[i]) / s;

        //calculate the comulative probability (Ci)
        c[0] = p[0];
        for (int i = 1; i < POPULATION_SIZE; ++i)
            c[i] = c[i - 1] + p[i];

        String []tempPop = new String[POPULATION_SIZE];
        //select according to Ci and random number r
        for (int i = 0; i < POPULATION_SIZE; ++i) {
            double r = getRandom(0, 1);
            int si = 0;
            while (c[si] < r)
                si++;
            tempPop[i] = population[si];
        }
        return tempPop;
    }


    private String[] crossover(String[] population) {
        String []tempPop = new String[POPULATION_SIZE];
        for (int i = 0; i < POPULATION_SIZE; i += 2) {
            double r = getRandom(0, 1);
            if (r > Pc) {   //this pair does not participate in the crossover
                tempPop[i] = population[i];
                tempPop[i + 1] = population[i + 1];
            }
            else { //make crossover
                int xo_point = (int) getRandom(1, NUMBER_OF_BITS - 0.0000001); //choose where to cut
                tempPop[i] = population[i].substring(0, xo_point) + population[i + 1].substring(xo_point);
                tempPop[i + 1] = population[i + 1].substring(0, xo_point) + population[i].substring(xo_point);
            }
        }
        return tempPop;
    }


    private String[] mutation(String[] population) {
        String []tempPop = new String[POPULATION_SIZE];

        for (int i = 0; i < POPULATION_SIZE; ++i) {
            String tempSt = "";
            for (int j = 0; j < NUMBER_OF_BITS; ++j) {
                double r = getRandom(0, 1);
                if (r > Pm)
                    tempSt = tempSt + population[i].charAt(j); //this bit does not participate in the mutation
                else  //make mutation
                    tempSt = tempSt + ((population[i].charAt(j) == '0') ? '1' : '0');
            }
            tempPop[i] = tempSt;
        }
        return tempPop;
    }


    private int fitness(String x) {
        int value=0;
        int weight = 0;

        for(int i=0;i<NUMBER_OF_BITS;++i)
            if (x.charAt(i) == '1') {
                value += Items[i][0];
                weight += Items[i][1];
            }
        if (weight <= C)
            return value;
        else return 0; //if the weight is higher the capacity C
    }

    //return random double number between [min,max]
    private double getRandom(double min, double max) {
        return min + Math.random() * (max - min);
    }

    
    private String getRandomIndavidual() {
        String tmp="";
        for(int i=0;i<NUMBER_OF_BITS;++i)
            tmp+=Math.round(Math.random())==0?'0':'1';
        return tmp;
    }


    public static void main(String []args) {
        Question5 q5 = new Question5();
        q5.run();
    }
}

//The Best of All Times = 547, 946, 890.626, 11111010110110011011111101110111110010111111111010, 623