001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.math4.examples.sofm.tsp;
019
020import java.io.FileNotFoundException;
021import java.io.PrintWriter;
022import java.io.UnsupportedEncodingException;
023import java.nio.charset.StandardCharsets;
024import java.util.concurrent.Callable;
025
026import picocli.CommandLine;
027import picocli.CommandLine.Option;
028import picocli.CommandLine.Command;
029
030import org.apache.commons.rng.UniformRandomProvider;
031import org.apache.commons.rng.simple.RandomSource;
032
033/**
034 * Application class.
035 */
036@Command(description = "Run the application",
037         mixinStandardHelpOptions = true)
038public final class StandAlone implements Callable<Void> {
039    /** The neurons per city. */
040    @Option(names = { "-n" }, paramLabel = "neuronsPerCity",
041            description = "Average number of neurons per city (default: ${DEFAULT-VALUE}).")
042    private double neuronsPerCity = 2.2;
043    /** The number of samples. */
044    @Option(names = { "-s" }, paramLabel = "numSamples",
045            description = "Number of samples for the training (default: ${DEFAULT-VALUE}).")
046    private long numSamples = 2000L;
047    /** The number of jobs. */
048    @Option(names = { "-j" }, paramLabel = "numJobs",
049            description = "Number of concurrent tasks (default: ${DEFAULT-VALUE}).")
050    private int numJobs = Runtime.getRuntime().availableProcessors();
051    /** The maximum number of trials. */
052    @Option(names = { "-m" }, paramLabel = "maxTrials",
053            description = "Maximal number of trials (default: ${DEFAULT-VALUE}).")
054    private int maxTrials = 10;
055    /** The output file. */
056    @Option(names = { "-o" }, paramLabel = "outputFile", required = true,
057            description = "Output file name.")
058    private String outputFile;
059
060    /**
061     * Program entry point.
062     *
063     * @param args Command line arguments and options.
064     */
065    public static void main(String[] args) {
066        CommandLine.call(new StandAlone(), args);
067    }
068
069    @Override
070    public Void call() throws FileNotFoundException, UnsupportedEncodingException {
071        // Cities (in optimal travel order).
072        final City[] cities = {
073            new City("o0", 0, 0),
074            new City("o1", 1, 0),
075            new City("o2", 2, 0),
076            new City("o3", 3, 0),
077            new City("o4", 3, 1),
078            new City("o5", 3, 2),
079            new City("o6", 3, 3),
080            new City("o7", 2, 3),
081            new City("o8", 1, 3),
082            new City("o9", 0, 3),
083            new City("i3", 1, 2),
084            new City("i2", 2, 2),
085            new City("i1", 2, 1),
086            new City("i0", 1, 1),
087        };
088
089        final UniformRandomProvider rng = RandomSource.KISS.create();
090        City[] best = null;
091        int maxCities = 0;
092        double minDist = Double.POSITIVE_INFINITY;
093
094        int count = 0;
095        while (count++ < maxTrials) {
096            final City[] travel = TravellingSalesmanSolver.solve(cities,
097                                                                 neuronsPerCity,
098                                                                 numSamples,
099                                                                 numJobs,
100                                                                 rng);
101            final int numCities = City.unique(travel).size();
102            if (numCities > maxCities) {
103                best = travel;
104                maxCities = numCities;
105            }
106
107            if (numCities == cities.length) {
108                final double dist = computeDistance(travel);
109                if (dist < minDist) {
110                    minDist = dist;
111                    best = travel;
112                }
113            }
114        }
115
116        printSummary(outputFile, best, computeDistance(cities));
117
118        return null;
119    }
120    /**
121     * Compute the distance covered by the salesman, including
122     * the trip back (from the last to first city).
123     *
124     * @param cityList List of cities visited during the travel.
125     * @return the total distance.
126     */
127    private static double computeDistance(City[] cityList) {
128        double dist = 0;
129        for (int i = 0; i < cityList.length; i++) {
130            final double[] currentCoord = cityList[i].getCoordinates();
131            final double[] nextCoord = cityList[(i + 1) % cityList.length].getCoordinates();
132
133            final double xDiff = currentCoord[0] - nextCoord[0];
134            final double yDiff = currentCoord[1] - nextCoord[1];
135
136            dist += Math.sqrt(xDiff * xDiff + yDiff * yDiff);
137        }
138
139        return dist;
140    }
141
142    /**
143     * Prints a summary of the current state of the solver to the
144     * given file name.
145     *
146     * @param fileName File.
147     * @param travel Solution.
148     * @param optimalDistance Length of shortest path.
149     * @throws UnsupportedEncodingException If UTF-8 encoding does not exist.
150     * @throws FileNotFoundException If the file cannot be created.
151     */
152    private static void printSummary(String fileName,
153                                     City[] travel,
154                                     double optimalDistance)
155                                     throws FileNotFoundException, UnsupportedEncodingException {
156        try (PrintWriter out = new PrintWriter(fileName, StandardCharsets.UTF_8.name())) {
157            out.println("# Number of unique cities: " + City.unique(travel).size());
158            out.println("# Travel distance: " + computeDistance(travel));
159            out.println("# Optimal travel distance: " + optimalDistance);
160
161            for (final City c : travel) {
162                final double[] coord = c.getCoordinates();
163                out.println(coord[0] + " " + coord[1] + " # " + c.getName());
164            }
165        }
166    }
167}