EASystem.java

package net.bmahe.genetics4j.core;

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

import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang3.Validate;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import net.bmahe.genetics4j.core.chromosomes.Chromosome;
import net.bmahe.genetics4j.core.chromosomes.factory.ChromosomeFactoryProvider;
import net.bmahe.genetics4j.core.combination.ChromosomeCombinator;
import net.bmahe.genetics4j.core.combination.GenotypeCombinator;
import net.bmahe.genetics4j.core.evaluation.FitnessEvaluator;
import net.bmahe.genetics4j.core.evolutionlisteners.EvolutionListener;
import net.bmahe.genetics4j.core.mutation.Mutator;
import net.bmahe.genetics4j.core.replacement.ReplacementStrategyImplementor;
import net.bmahe.genetics4j.core.selection.Selector;
import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
import net.bmahe.genetics4j.core.spec.AbstractEAExecutionContext;
import net.bmahe.genetics4j.core.spec.EvolutionResult;
import net.bmahe.genetics4j.core.spec.ImmutableEvolutionResult;
import net.bmahe.genetics4j.core.termination.Termination;
import net.bmahe.genetics4j.core.util.GenotypeGenerator;

/**
 * Main class used to manage and execute the evolution process
 *
 * @param <T>
 */
public class EASystem<T extends Comparable<T>> {
	final static public Logger logger = LogManager.getLogger(EASystem.class);

	private final GenotypeGenerator<T> genotypeGenerator;
	private final FitnessEvaluator<T> fitnessEvaluator;
	private final AbstractEAConfiguration<T> eaConfiguration;
	private final AbstractEAExecutionContext<T> eaExecutionContext;
	private final int populationSize;

	private final List<ChromosomeCombinator<T>> chromosomeCombinators;
	private final ChromosomeFactoryProvider chromosomeFactoryProvider;

	private final ReplacementStrategyImplementor<T> replacementStrategyImplementor;

	private final List<Mutator> mutators;

	private final double offspringRatio;

	private Selector<T> parentSelector;

	public EASystem(final AbstractEAConfiguration<T> _eaConfiguration, final long _populationSize,
			final List<ChromosomeCombinator<T>> _chromosomeCombinators, final double _offspringRatio,
			final Selector<T> _parentSelectionPolicyHandler, final List<Mutator> _mutators,
			final ReplacementStrategyImplementor<T> _replacementStrategyImplementor,
			final AbstractEAExecutionContext<T> _eaExecutionContext, final FitnessEvaluator<T> _fitnessEvaluator) {
		Objects.requireNonNull(_eaConfiguration);
		Validate.isTrue(_populationSize > 0);
		Objects.requireNonNull(_chromosomeCombinators);
		Validate.isTrue(_chromosomeCombinators.size() == _eaConfiguration.numChromosomes());
		Validate.inclusiveBetween(0.0, 1.0, _offspringRatio);
		Objects.requireNonNull(_parentSelectionPolicyHandler);
		Objects.requireNonNull(_replacementStrategyImplementor);
		Objects.requireNonNull(_eaExecutionContext);
		Objects.requireNonNull(_fitnessEvaluator);

		this.eaConfiguration = _eaConfiguration;
		this.eaExecutionContext = _eaExecutionContext;
		this.populationSize = (int) _populationSize;
		this.chromosomeCombinators = _chromosomeCombinators;
		this.offspringRatio = _offspringRatio;
		this.mutators = _mutators;
		this.chromosomeFactoryProvider = _eaExecutionContext.chromosomeFactoryProvider();
		this.fitnessEvaluator = _fitnessEvaluator;

		parentSelector = _parentSelectionPolicyHandler;

		this.replacementStrategyImplementor = _replacementStrategyImplementor;
		this.genotypeGenerator = new GenotypeGenerator<>(chromosomeFactoryProvider, eaConfiguration);
	}

	private List<T> evaluate(final long generation, final List<Genotype> population) {
		Validate.isTrue(generation >= 0);
		Objects.requireNonNull(population);
		Validate.isTrue(population.size() > 0);

		logger.debug("Evaluating population of size {}", population.size());
		final List<T> fitnesses = fitnessEvaluator.evaluate(generation, population);

		logger.debug("Done evaluating population of size {}", population.size());
		return fitnesses;
	}

	private List<Genotype> initializePopulation() {
		final int initialPopulationSize = eaExecutionContext.populationSize();
		logger.info("Generating initial population of {} individuals", initialPopulationSize);

		final List<Genotype> genotypes = new ArrayList<>(initialPopulationSize);

		final var seedPopulation = eaConfiguration.seedPopulation();
		if (CollectionUtils.isNotEmpty(seedPopulation)) {
			genotypes.addAll(seedPopulation);
		}
		if (genotypes.size() < initialPopulationSize) {
			final var missingInitialIndividualCount = initialPopulationSize - genotypes.size();
			logger.info(
					"{} seed individual(s) added and generating {} individuals to reach the target of {} initial population size",
					genotypes.size(),
					missingInitialIndividualCount,
					initialPopulationSize);

			final var extraIndividuals = genotypeGenerator.generateGenotypes(missingInitialIndividualCount);
			genotypes.addAll(extraIndividuals);
		}

		return genotypes;
	}

	private List<Genotype> mutateGenotypes(final List<Genotype> genotypes) {
		Objects.requireNonNull(genotypes);

		return genotypes.stream()
				.map(child -> {
					Genotype mutatedChild = child;

					for (final Mutator mutator : mutators) {
						mutatedChild = mutator.mutate(mutatedChild);
					}

					return mutatedChild;
				})
				.toList();
	}

	private List<Genotype> combineParents(final Population<T> parents, final GenotypeCombinator genotypeCombinator) {
		Objects.requireNonNull(parents);
		Objects.requireNonNull(genotypeCombinator);

		final List<Genotype> children = new ArrayList<>();
		int parentIndex = 0;
		while (parentIndex + 1 < parents.size()) {
			final Genotype firstParent = parents.getGenotype(parentIndex);
			final T firstParentFitness = parents.getFitness(parentIndex);

			final Genotype secondParent = parents.getGenotype(parentIndex + 1);
			final T secondParentFitness = parents.getFitness(parentIndex + 1);

			final List<List<Chromosome>> chromosomes = new ArrayList<>();
			for (int chromosomeIndex = 0; chromosomeIndex < eaConfiguration.numChromosomes(); chromosomeIndex++) {

				final Chromosome firstChromosome = firstParent.getChromosome(chromosomeIndex);
				final Chromosome secondChromosome = secondParent.getChromosome(chromosomeIndex);

				final List<Chromosome> combinedChromosomes = chromosomeCombinators.get(chromosomeIndex)
						.combine(eaConfiguration, firstChromosome, firstParentFitness, secondChromosome, secondParentFitness);

				chromosomes.add(combinedChromosomes);
				logger.trace("Combining {} with {} ---> {}", firstChromosome, secondChromosome, combinedChromosomes);
			}

			final List<Genotype> offsprings = genotypeCombinator.combine(eaConfiguration, chromosomes);

			children.addAll(offsprings);
			parentIndex += 2;
		}

		return children;
	}

	/**
	 * Create offsprings without mutation
	 *
	 * @param population
	 * @param offspringsNeeded
	 * @return
	 */
	private List<Genotype> createBasicOffsprings(final Population<T> population, final int offspringsNeeded) {
		Objects.requireNonNull(population);
		Validate.isTrue(offspringsNeeded > 0);

		final GenotypeCombinator genotypeCombinator = eaConfiguration.genotypeCombinator();

		final int parentsNeeded = (int) (offspringsNeeded * 2);
		logger.info("Selecting {} parents as we expect to generate {} offsprings", parentsNeeded, offspringsNeeded);
		final Population<T> selectedParents = parentSelector
				.select(eaConfiguration, parentsNeeded, population.getAllGenotypes(), population.getAllFitnesses());
		logger.trace("Selected parents: {}", selectedParents);
		Validate.isTrue(selectedParents.size() % 2 == 0);

		logger.info("Combining parents into offsprings");
		final List<Genotype> offsprings = combineParents(selectedParents, genotypeCombinator);

		return offsprings;
	}

	public AbstractEAConfiguration<T> getEAConfiguration() {
		return eaConfiguration;
	}

	public long getPopulationSize() {
		return populationSize;
	}

	public List<Genotype> createOffsprings(final Population<T> population, final int offspringsNeeded) {
		Objects.requireNonNull(population);
		Validate.isTrue(offspringsNeeded > 0);

		final List<Genotype> offpsrings = createBasicOffsprings(population, offspringsNeeded);
		logger.info("Generated {} offsprings", offpsrings.size());

		logger.info("Mutating offsprigns");
		final List<Genotype> mutatedOffsprings = mutateGenotypes(offpsrings);

		return mutatedOffsprings;
	}

	/**
	 * Triggers the evolutionary process
	 * 
	 * @return
	 */
	public EvolutionResult<T> evolve() {
		final Termination<T> termination = eaConfiguration.termination();

		logger.info("Starting evolution");

		fitnessEvaluator.preEvaluation();

		long generation = 0;
		final List<Genotype> genotypes = initializePopulation();

		logger.info("Evaluating initial population");
		final List<T> fitnessScore = evaluate(generation, genotypes);

		Population<T> population = eaConfiguration.postEvaluationProcessor()
				.map(pep -> pep.apply(Population.of(genotypes, fitnessScore)))
				.orElseGet(() -> Population.of(genotypes, fitnessScore));

		while (termination
				.isDone(eaConfiguration, generation, population.getAllGenotypes(), population.getAllFitnesses()) == false) {
			logger.info("Going through evolution of generation {}", generation);

			for (final EvolutionListener<T> evolutionListener : eaExecutionContext.evolutionListeners()) {
				evolutionListener
						.onEvolution(generation, population.getAllGenotypes(), population.getAllFitnesses(), false);
			}

			final int offspringsNeeded = (int) (populationSize * offspringRatio);
			final List<Genotype> offsprings = createOffsprings(population, offspringsNeeded);

			logger.info("Evaluating offsprings");
			final List<T> offspringScores = evaluate(generation, offsprings);

			final Population<T> childrenPopulation = eaConfiguration.postEvaluationProcessor()
					.map(pep -> pep.apply(Population.of(offsprings, offspringScores)))
					.orElseGet(() -> Population.of(offsprings, offspringScores));

			logger.info("Executing replacement strategy");
			final int nextGenerationPopulationSize = eaExecutionContext.populationSize();
			final Population<T> newPopulation = replacementStrategyImplementor.select(eaConfiguration,
					nextGenerationPopulationSize,
					population.getAllGenotypes(),
					population.getAllFitnesses(),
					childrenPopulation.getAllGenotypes(),
					childrenPopulation.getAllFitnesses());

			if (newPopulation.size() < nextGenerationPopulationSize) {
				logger.info("New population only has {} members. Generating more individuals", newPopulation.size());
				final List<Genotype> additionalIndividuals = genotypeGenerator
						.generateGenotypes(nextGenerationPopulationSize - newPopulation.size());
				logger.debug("Number of generated individuals: {}", additionalIndividuals.size());

				if (additionalIndividuals.size() > 0) {

					final List<T> additionalFitness = evaluate(generation, additionalIndividuals);
					newPopulation.addAll(Population.of(additionalIndividuals, additionalFitness));
				}
			}

			if (logger.isTraceEnabled()) {
				logger.trace("[Generation {}] New population: {}", generation, Arrays.asList(newPopulation));
			}
			population = newPopulation;
			generation++;
		}

		logger.info("Evolution has terminated");

		// isDone has returned true and we want to let the evolutionListeners run a last
		// time
		for (final EvolutionListener<T> evolutionListener : eaExecutionContext.evolutionListeners()) {
			evolutionListener.onEvolution(generation, population.getAllGenotypes(), population.getAllFitnesses(), true);
		}

		fitnessEvaluator.postEvaluation();

		return ImmutableEvolutionResult
				.of(eaConfiguration, generation, population.getAllGenotypes(), population.getAllFitnesses());
	}

	public List<T> evaluateOnce(final long generation, final List<Genotype> genotypes) {
		Validate.isTrue(generation >= 0);
		Objects.requireNonNull(genotypes);
		Validate.isTrue(genotypes.size() > 0);

		fitnessEvaluator.preEvaluation();
		final var fitness = evaluate(generation, genotypes);

		final var population = Population.of(genotypes, fitness);
		for (final EvolutionListener<T> evolutionListener : eaExecutionContext.evolutionListeners()) {
			evolutionListener.onEvolution(generation, population.getAllGenotypes(), population.getAllFitnesses(), true);
		}

		fitnessEvaluator.postEvaluation();

		return fitness;
	}
}