IntEdgeRecombinationCrossover.java

package net.bmahe.genetics4j.core.combination.erx;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Optional;
import java.util.Set;
import java.util.random.RandomGenerator;

import org.apache.commons.lang3.Validate;

import net.bmahe.genetics4j.core.chromosomes.Chromosome;
import net.bmahe.genetics4j.core.chromosomes.IntChromosome;
import net.bmahe.genetics4j.core.combination.ChromosomeCombinator;
import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;

public class IntEdgeRecombinationCrossover<T extends Comparable<T>> implements ChromosomeCombinator<T> {

	private final RandomGenerator randomGenerator;

	public IntEdgeRecombinationCrossover(final RandomGenerator _randomGenerator) {
		Validate.notNull(_randomGenerator);

		this.randomGenerator = _randomGenerator;
	}

	protected void addEdges(final Map<Integer, Set<Integer>> edgeMap, final int[] chromosomeValues) {
		Validate.notNull(edgeMap);
		Validate.notNull(chromosomeValues);

		for (int i = 0; i < chromosomeValues.length; i++) {
			final int j = chromosomeValues[i];

			// Add city before
			if (i > 0) {
				final int cityBefore = chromosomeValues[i - 1];
				final Set<Integer> cities = edgeMap.computeIfAbsent(cityBefore, k -> new HashSet<Integer>());
				cities.add(j);
			}

			// Add city after
			if (i < chromosomeValues.length - 1) {
				final int cityAfter = chromosomeValues[i + 1];
				final Set<Integer> cities = edgeMap.computeIfAbsent(cityAfter, k -> new HashSet<Integer>());
				cities.add(j);
			}
		}

		final Set<Integer> lastCities = edgeMap.computeIfAbsent(chromosomeValues[chromosomeValues.length - 1],
				k -> new HashSet<Integer>());
		lastCities.add(chromosomeValues[0]);

		final Set<Integer> firstCities = edgeMap.computeIfAbsent(chromosomeValues[0], k -> new HashSet<Integer>());
		firstCities.add(chromosomeValues[chromosomeValues.length - 1]);
	}

	protected Optional<Integer> cityWithSmallestEdgeList(final Map<Integer, Set<Integer>> edgeMap) {
		Validate.notNull(edgeMap);

		int citySmallestEdgeList = -1;
		int smallestEdgeListSize = Integer.MAX_VALUE;

		for (final Entry<Integer, Set<Integer>> entry : edgeMap.entrySet()) {
			final Integer city = entry.getKey();
			final Set<Integer> edgeList = entry.getValue();

			if (edgeList.size() < smallestEdgeListSize) {
				citySmallestEdgeList = city;
				smallestEdgeListSize = edgeList.size();
			}
		}

		return citySmallestEdgeList > -1 ? Optional.of(citySmallestEdgeList) : Optional.empty();
	}

	protected Optional<Integer> cityWithSmallestEdgeList(final Map<Integer, Set<Integer>> edgeMap,
			final Set<Integer> candidates) {
		Validate.notNull(edgeMap);

		int citySmallestEdgeList = -1;
		int smallestEdgeListSize = Integer.MAX_VALUE;

		for (final Integer candidate : candidates) {
			if (edgeMap.containsKey(candidate)) {
				final Set<Integer> edgeList = edgeMap.get(candidate);

				if (edgeList.size() < smallestEdgeListSize) {
					citySmallestEdgeList = candidate;
					smallestEdgeListSize = edgeList.size();
				}
			}
		}

		return citySmallestEdgeList > -1 ? Optional.of(citySmallestEdgeList) : Optional.empty();
	}

	@Override
	public List<Chromosome> combine(final AbstractEAConfiguration<T> eaConfiguration, final Chromosome chromosome1,
			final T firstParentFitness, final Chromosome chromosome2, final T secondParentFitness) {
		Validate.notNull(chromosome1);
		Validate.notNull(chromosome2);
		Validate.isInstanceOf(IntChromosome.class, chromosome1);
		Validate.isInstanceOf(IntChromosome.class, chromosome2);

		final IntChromosome intChromosome1 = (IntChromosome) chromosome1;
		Validate.isTrue(intChromosome1.getNumAlleles() > 2);
		final int[] chromosome1Values = intChromosome1.getValues();

		final IntChromosome intChromosome2 = (IntChromosome) chromosome2;
		final int[] chromosome2Values = intChromosome2.getValues();

		Validate.isTrue(intChromosome2.getNumAlleles() > 2);
		Validate.isTrue(intChromosome1.getNumAlleles() == intChromosome2.getNumAlleles());

		final Map<Integer, Set<Integer>> edgeMap = new HashMap<>();
		addEdges(edgeMap, chromosome1Values);
		addEdges(edgeMap, chromosome2Values);

		int[] chromosome = new int[chromosome1.getNumAlleles()];
		int currentCity = randomGenerator.nextInt(chromosome1Values.length);
		int currentIndex = 0;
		final Set<Integer> citiesVisited = new HashSet<>();
		while (edgeMap.size() > 0) {

			chromosome[currentIndex] = currentCity;
			final Set<Integer> nextCities = edgeMap.get(currentCity);
			edgeMap.remove(currentCity);
			citiesVisited.add(currentCity);
			currentIndex++;

			final Optional<Integer> cityWithSmallestEdgeList = cityWithSmallestEdgeList(edgeMap, nextCities);

			if (cityWithSmallestEdgeList.isPresent()) {
				currentCity = cityWithSmallestEdgeList.get();
			} else {
				final Set<Integer> citiesSet = edgeMap.keySet();
				if (citiesSet.size() == 1) {
					currentCity = citiesSet.iterator()
							.next();
				} else if (citiesSet.size() > 0) {
					currentCity = citiesSet.stream()
							.skip(randomGenerator.nextInt(citiesSet.size() - 1))
							.findFirst()
							.get();
				}
			}
		}

		if (currentIndex < chromosome1.getNumAlleles()) {
			final Set<Integer> remainingValues = new HashSet<>();
			for (int i : chromosome1Values) {
				remainingValues.add(i);
			}
			for (int i : chromosome2Values) {
				remainingValues.add(i);
			}
			remainingValues.removeAll(citiesVisited);
			for (Integer remainingCity : remainingValues) {
				chromosome[currentIndex++] = remainingCity;

			}
		}

		return List.of(new IntChromosome(chromosome1.getNumAlleles(),
				intChromosome1.getMinValue(),
				intChromosome1.getMaxValue(),
				chromosome));
	}
}