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}