package strategies;

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import 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;
	/** Current list of parents **/
	private List<GAIndividual> m_parents = new ArrayList<GAIndividual>();

	/**
	 * 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) {
		assert multiRuns > 9; // use run configurations: vmargument: -ea
		assert (lambda % 2) == 0;
		this.m_GenotypeLength = genotypeLength;
		this.m_Mu = mu;
		this.m_Lambda = lambda;
		this.m_OptimizationSteps = optimizationSteps;
		this.m_MultiRuns = multiRuns;
	}

	/**
	 * This method will initialize the GeneticAlgorithm
	 */
	public void initialize() {
		m_parents.clear();
		m_OptimizationStepsNeeded = 0;
		for (int i = 0; i < m_Mu; i++) {
			m_parents.add(new GAIndividual(m_GenotypeLength));

		}
		Collections.sort(m_parents, Collections.reverseOrder());
		m_Best = m_parents.get(0);
	}

	/**
	 * 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:
		// initialize the population
		// while maxSteps not reached do
		// do select 2 (distinct) parents from population randomly
		// perform crossover to generate two children
		// until lambda children generated
		// mutate the children (p_m = 0.5, use randomBoolean from
		// RandomNumberGenerator)
		// calculate the fitness of the children (use
		// GAIndividual.evaluateAsMaxiBits())
		// select the mu best individuals for the new population
		// od

		for (int i = 0; i < m_OptimizationSteps; i++) {
			ArrayList<GAIndividual> children = new ArrayList<GAIndividual>();
			for (int a = 0; a < (m_Lambda / 2); a++) {
				GAIndividual parent1;
				GAIndividual parent2;
				do {
					parent1 = m_parents.get(RandomNumberGenerator.randomInt(0,
							m_Mu - 1));
					parent2 = m_parents.get(RandomNumberGenerator.randomInt(0,
							m_Mu - 1));
				} while (parent1 == parent2);// distinct parents
				children.addAll(Arrays.asList(GAIndividual.crossover(parent1,
						parent2)));
			}
			for (GAIndividual child : children) {
				if (RandomNumberGenerator.randomBoolean()) {
					child.mutate();
				}
			}
			m_parents.addAll(children);
			Collections.sort(m_parents, Collections.reverseOrder()); // comparable
																		// implemented
																		// in
																		// GAIndividual
			m_parents = m_parents.subList(0, m_Mu);
			m_Best = m_parents.get(0);
			m_OptimizationStepsNeeded++;
			if (m_Best.evaluateAsMaxiBits() == m_GenotypeLength) {
				break;
			}

		}
	}

	/**
	 * 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 = 50;
		int mu = 10;
		int lambda = 50;
		int optimizationSteps = 100000;
		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++) {
			program.initialize();
			program.optimize();
			TmpMeanCalls += program.m_OptimizationStepsNeeded;
			TmpMeanFitness += program.m_Best.evaluateAsMaxiBits();
		}
		TmpMeanCalls = TmpMeanCalls / program.m_MultiRuns; // ja klar 3.9 =3
		TmpMeanFitness = TmpMeanFitness / program.m_MultiRuns;
		System.out.println("(" + program.m_MultiRuns + "/"
				+ program.m_OptimizationSteps + ") Mean Fitness : "
				+ TmpMeanFitness + " Mean Calls needed: " + TmpMeanCalls);
	}
}