package src.strategies;

/**
 * This class implements a deterministic variant of the Genetic Algorithm described in the script, section 5.1.1.
 */
import java.util.Arrays;

import src.individuals.GAIndividual;
import src.tools.RandomNumberGenerator;

public class GeneticAlgorithm {
	/** The length of the genotype of the individuals **/
	private int m_GenotypeLength;
	/** The number of individuals in the population **/
	private int m_Mu;
	/** The number of children generated **/
	private int m_Lambda;
	/** The number of single optimization steps to be evaluated **/
	private int m_OptimizationSteps;
	/** The number of times the experiment is repeated **/
	private int m_MultiRuns;
	/** Number of steps needed to reach best result **/
	private int m_OptimizationStepsNeeded = 0;
	/** Current best individual **/
	private GAIndividual m_Best;

	private GAIndividual[] m_Population;

	/**
	 * This constructor sets up GeneticAlgorithm
	 * 
	 * @param genotypeLength
	 *            The length of the genotype of the individuals
	 * @param mu
	 *            The number of individuals in the population
	 * @param lambda
	 *            The number of children generated in each iteration
	 * @param optimizationSteps
	 *            The number of single optimization steps to be evaluated
	 *            (adjust as necessary)
	 * @param multiRuns
	 *            The number of times the experiment is repeated (at least 10)
	 */
	public GeneticAlgorithm(int genotypeLength, int mu, int lambda,
			int optimizationSteps, int multiRuns) {
		m_Mu = mu;
		m_Lambda = lambda;
		m_OptimizationSteps = optimizationSteps;
		m_MultiRuns = multiRuns;
		m_GenotypeLength = genotypeLength;
		m_Population = new GAIndividual[m_Mu];
	}

	/**
	 * This method will initialize the GeneticAlgorithm
	 */
	public void initialize() {
		m_OptimizationStepsNeeded = 0;
		for (int i = 0; i < m_Mu; i++) {
			m_Population[i] = new GAIndividual(m_GenotypeLength);
		}
	}

	/**
	 * This method will optimize the evaulateAsMaxiBits Problem. Use
	 * m_FitnessCallsNeeded to return the number of FitnessCalls (e.g., calling
	 * evaluateAsMaxiBits()) needed to find the optimum. The optimization should
	 * terminate after m_FitnessCalls.
	 */
	public void optimize() {
		// The deterministic Genetic Algorithm works as follows:
		// while maxSteps not reached do
		for (int j = 0; j < m_OptimizationSteps; j++) {
			GAIndividual[] nextGen = new GAIndividual[m_Lambda];
			// do select 2 (distinct) parents from population randomly
			// perform crossover to generate two children
			// until lambda children generated
			for (int i = 0; i < m_Lambda; i = i + 2) {
				GAIndividual ind1;
				GAIndividual ind2;
				do {
					ind1 = m_Population[RandomNumberGenerator.randomInt(0,
							m_Population.length - 1)];
					ind2 = m_Population[RandomNumberGenerator.randomInt(0,
							m_Population.length - 1)];
				} while (ind1 == ind2);// distinct parents

				GAIndividual[] children = GAIndividual.crossover(ind1, ind2);
				nextGen[i] = children[0];
				nextGen[i + 1] = children[1];
			}
			// mutate the children (p_m = 0.5, use randomBoolean from
			// RandomNumberGenerator)
			for (int i = 0; i < m_Lambda; i++) {
				if (RandomNumberGenerator.randomBoolean()) {
					nextGen[i].mutate();
				}
			}
			// calculate the fitness of the children (use
			// GAIndividual.evaluateAsMaxiBits())
			Arrays.sort(nextGen);
			// System.out.println(nextGen[0].getStringRepresentation());
			// select the mu best individuals for the new population
			for (int i = 0; i < m_Mu; i++) {
				m_Population[i] = nextGen[i];
			}

			if (m_Population[0].evaluateAsMaxiBits() != 0) {
				m_OptimizationStepsNeeded++;
			}
		}
		m_Best = m_Population[0];
	}

	/**
	 * This main method will start a simple GeneticAlgorithm search. No
	 * arguments necessary.
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO: parameters for the GeneticAlgorithm, adjust these values as
		// necessary
		int genotypeLength = 25;
		int mu = 10;
		int lambda = 50;
		int optimizationSteps = 100;
		int multiRuns = 100;
		GeneticAlgorithm program = new GeneticAlgorithm(genotypeLength, mu,
				lambda, optimizationSteps, multiRuns);
		int TmpMeanCalls = 0, TmpMeanFitness = 0;
		// perform repeated optimization
		for (int i = 0; i < program.m_MultiRuns; i++) {
			// System.out.println(i);
			program.initialize();
			program.optimize();
			TmpMeanCalls += program.m_OptimizationStepsNeeded;
			TmpMeanFitness += program.m_Best.evaluateAsMaxiBits();
		}
		TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns;
		TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns;
		System.out.println("(" + program.m_MultiRuns + "/"
				+ program.m_OptimizationSteps + ") Mean Fitness : "
				+ TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls);
	}
}
