DistrictTSP.java

import static java.lang.String.format;
import static java.lang.System.getProperty;
import static java.util.Objects.requireNonNull;
import static io.jenetics.engine.EvolutionResult.toBestPhenotype;
import static io.jenetics.jpx.Length.Unit.METER;

import java.io.IOException;
import java.io.InputStream;
import java.util.AbstractMap.SimpleImmutableEntry;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.function.Function;
import java.util.stream.IntStream;

import io.jenetics.jpx.GPX;
import io.jenetics.jpx.WayPoint;

import io.jenetics.EnumGene;
import io.jenetics.Gene;
import io.jenetics.Optimize;
import io.jenetics.PartiallyMatchedCrossover;
import io.jenetics.Phenotype;
import io.jenetics.SwapMutator;
import io.jenetics.engine.Codec;
import io.jenetics.engine.Codecs;
import io.jenetics.engine.Engine;
import io.jenetics.engine.EvolutionStatistics;
import io.jenetics.engine.Problem;
import io.jenetics.util.ISeq;

/**
 * Implementation of the Traveling Salesman Problem. This example tries to find
 * the shortest path, which visits all Austrian district capitals.
 */
public final class TravelingSalesman
	implements Problem<ISeq<WayPoint>, EnumGene<WayPoint>, Double>
{

	// Caching the distances.
	private final Map<Entry<WayPoint, WayPoint>, Double>
	_distances = new HashMap<>();

	private final ISeq<WayPoint> _points;

	/**
	 * Create a new TSP instance with the way-points we want to visit.
	 *
	 * @param points the way-points we want to visit
	 * @throws NullPointerException if the given {@code points} seq is {@code null}
	 */
	public TravelingSalesman(final ISeq<WayPoint> points) {
		_points = requireNonNull(points);

		for (int i = 0; i < points.size(); ++i) {
			final WayPoint a = points.get(i);

			for (int j = i + 1; j < points.size(); ++j) {
				final WayPoint b = points.get(j);

				if (i != j) {
					final double distance = a.distance(b).to(METER);
					_distances.put(new SimpleImmutableEntry<>(a, b), distance);
					_distances.put(new SimpleImmutableEntry<>(b, a), distance);
				}
			}
		}
	}

	@Override
	public Codec<ISeq<WayPoint>, EnumGene<WayPoint>> codec() {
		return Codecs.ofPermutation(_points);
	}

	@Override
	public Function<ISeq<WayPoint>, Double> fitness() {
		return way -> IntStream.range(0, way.length())
			.mapToObj(i -> new SimpleImmutableEntry<>(
				way.get(i), way.get((i + 1)%way.size())))
			.mapToDouble(_distances::get)
			.sum();
	}

	public static void main(String[] args) throws IOException {
		final TravelingSalesman tsm = new TravelingSalesman(districtCapitals());

		final Engine<EnumGene<WayPoint>, Double> engine = Engine.builder(tsm)
			.optimize(Optimize.MINIMUM)
			.alterers(
				new SwapMutator<>(0.15),
				new PartiallyMatchedCrossover<>(0.15))
			.build();

		// Create evolution statistics consumer.
		final EvolutionStatistics<Double, ?>
			statistics = EvolutionStatistics.ofNumber();

		final Phenotype<EnumGene<WayPoint>, Double> best = engine.stream()
			.limit(3_000_000)
			.peek(statistics)
			.collect(toBestPhenotype());

		final ISeq<WayPoint> path = best.getGenotype()
			.getChromosome().toSeq()
			.map(Gene::getAllele);

		final GPX gpx = GPX.builder()
			.addTrack(track -> track
				.name("Best Track")
				.addSegment(s -> s.points(path.asList())))
			.build();

		final double km = tsm.fitness(best.getGenotype())/1_000.0;
		GPX.write(
			gpx,
			format("%s/out_%d.gpx", getProperty("user.home"), (int)km),
			"    "
		);
		System.out.println("Length: " + km);
		System.out.println(statistics);
	}

	// Return the district capitals, we want to visit.
	private static ISeq<WayPoint> districtCapitals() throws IOException {
		final String capitals = "/io/jenetics/example/DistrictCapitals.gpx";
		try (InputStream in = TravelingSalesman
				.class.getResourceAsStream(capitals))
		{
			return ISeq.of(GPX.read(in).getWayPoints());
		}
	}

}