Engine.java

/*
 * MIT License
 *
 * Copyright (c) 2009-2016 Ignacio Calderon <https://github.com/kronenthaler>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
package libai.genetics;

import libai.genetics.chromosomes.Chromosome;

import javax.swing.*;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * Engine class provides complete algorithm to evolve populations of
 * chromosomes, regardless of these kind. This implementation of the genetic
 * algorithm contemplates the elitism variant for the selection. The mutation
 * and cross are more chromosome-dependent that the algorithm-dependent,
 * therefore, chromosomes are instantiated for its class and evaluated through
 * the Fitness instance.
 *
 * @author kronenthaler
 */
public class Engine {

    /**
     * The current population
     */
    private Chromosome population[];
    /**
     * The offsprings of the current population
     */
    private Chromosome newpopulation[];
    /**
     * The chromosomes selected to crossing
     */
    private Chromosome toCross[];
    /**
     * The best solution so far.
     */
    private Chromosome best;//population
    /**
     * Utility random instance.
     */
    private Random random;
    /**
     * The fitness evaluator
     */
    private Fitness evaluator;
    /**
     * The size of each chromosome
     */
    private int chromosomeSize;
    /**
     * The cross probability
     */
    private double pc = .6;
    /**
     * The mutation probability
     */
    private double pm = .01;
    private JProgressBar progress;

    /**
     * Constructor. Initialize a population of <code>individuals</code> of type
     * <code>chromotype</code>. Each chromosome has a length of
     * <code>_chromosomeSize</code>, with a crossing probability of
     * <code>_pc</code> and a mutation probability of <code>_pm</code>. To
     * evaluate the fitness of each chromosome will use <code>_evaluator</code>.
     *
     * @param chromotype The class for the chromosomes
     * @param individuals The number of individuals for this population
     * @param _chromosomeSize The size of each chromosome
     * @param _pc The crossing probability.
     * @param _pm The mutation probability.
     * @param _evaluator The fitness evaluator.
     */
    public Engine(Class chromotype, int individuals, int _chromosomeSize, double _pc, double _pm, Fitness _evaluator) {
        evaluator = _evaluator;
        chromosomeSize = _chromosomeSize;
        pc = _pc;
        pm = _pm;

        population = new Chromosome[individuals];
        newpopulation = new Chromosome[individuals];
        toCross = new Chromosome[individuals];
        random = getDefaultRandomGenerator();

        try {
            best = (Chromosome) chromotype.newInstance();
            best.setFitness(evaluator.theWorst());
            best.setFitnessReal(evaluator.theWorst());
        } catch (Exception ex) {
            ex.printStackTrace();
        }

        initialize(chromosomeSize);
    }

    public static Random getDefaultRandomGenerator() {
        return ThreadLocalRandom.current();
    }

    /**
     * Initialize population with size <code>chromosomeSize</code>
     *
     * @param chromosomeSize The size of the chromosome.
     */
    protected void initialize(int chromosomeSize) {
        for (int i = 0; i < population.length; i++) {
            population[i] = best.getInstance(chromosomeSize, random);
        }
    }

    /**
     * Roulette determinate individuals to cross
     *
     * @param maximum The maximum value for the fitness in this population.
     */
    private void roulette(double maximum) {
        Chromosome current = null;
        double q = 0;
        for (int i = 0; i < population.length; i++) {
            current = population[i];

            double temp = (current.getFitness() / maximum);
            current.setFitness(q + (1 - temp));
            current.setChance(random.nextDouble());

            q += temp;
        }

        for (int j = 0; j < population.length; j++) {
            if (best == population[j]) {
                toCross[j] = best;
            } else {
                for (int i = 1; i < population.length; i++) {
                    if (population[j].getChance() > 0 && population[j].getChance() <= population[i].getFitness()) {
                        toCross[j] = population[0];
                        break;
                    } else if (population[j].getChance() > population[i - 1].getFitness() && population[j].getChance() <= population[i].getFitness()) {
                        toCross[j] = population[i];
                        break;
                    }
                }
            }
        }
    }

    /**
     * Cross population. Elitist style.
     */
    private void cross() {
        int a = 0;
        int j = 0;
        boolean wait = false;
        for (int i = 0; i < population.length; i++) {
            if (toCross[i].getChance() < pc && !wait) {
                a = i;
                wait = true;
            } else if (toCross[i].getChance() < pc && wait) {
                wait = false;
                Chromosome children[] = toCross[a].cross(toCross[i], Math.abs(random.nextInt(chromosomeSize)));
                newpopulation[j++] = children[0];//toCross[a].cross(toCross[b],pos);
                newpopulation[j++] = children[1];//toCross[b].cross(toCross[a],pos);
            } else {
                newpopulation[j++] = toCross[i].getCopy();
            }
        }
        if (wait) //one individual missing
        {
            newpopulation[j] = toCross[a].getCopy();
        }
    }

    /**
     * Mutate random genes in each chromosome
     */
    private void mutate() {
        for (int i = 0; i < population.length; i++) {
            if (newpopulation[i] != best) {
                newpopulation[i] = newpopulation[i].mutate(pm);
            }
        }
        population = newpopulation;
    }

    /**
     * Evolve the population for <code>ages</code>
     *
     * @param ages {@code ages}
     * @return The best chromosome for all these epochs.
     */
    public Chromosome evolve(int ages) {
        if (progress != null) {
            progress.setMaximum(ages - 1);
            progress.setMinimum(0);
            progress.setValue(0);
        }

        double maximum = 0;
        for (int iter = 0; iter < ages; iter++) {
            Chromosome current = null;
            maximum = 0;

            //eval fitness
            for (int i = 0; i < population.length; i++) {
                current = population[i];
                current.setFitness(evaluator.fitness(current));
                current.setFitnessReal(current.getFitness());
                maximum += current.getFitness(); //store to calculate roulette
                if (evaluator.isBetter(current.getFitnessReal(), best.getFitnessReal())) {
                    best = current;
                }
            }

            roulette(maximum);
            cross();
            mutate(); //mutate and swap

            if (progress != null) {
                progress.setValue(iter);
            }
        }

        return best; //the best individual
    }

    public void setProgressBar(JProgressBar _progress) {
        progress = _progress;
    }
}