fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4.  
  5.  
  6. /*
  7.  * To change this license header, choose License Headers in Project Properties.
  8.  * To change this template file, choose Tools | Templates
  9.  * and open the template in the editor.
  10.  */
  11.  
  12.  
  13. public class city {
  14.     int x;
  15.     int y;
  16.  
  17.     // Constructs a randomly placed city
  18.     public city(){
  19.         this.x = (int)(Math.random()*200);
  20.         this.y = (int)(Math.random()*200);
  21.     }
  22.  
  23.     // Constructs a city at chosen x, y location
  24.     public city(int x, int y){
  25.         this.x = x;
  26.         this.y = y;
  27.     }
  28.  
  29.     // Gets city's x coordinate
  30.     public int getX(){
  31.         return this.x;
  32.     }
  33.  
  34.     // Gets city's y coordinate
  35.     public int getY(){
  36.         return this.y;
  37.     }
  38.  
  39.     // Gets the distance to given city
  40.     public double distanceTo(city city){
  41.         int xDistance = Math.abs(getX() - city.getX());
  42.         int yDistance = Math.abs(getY() - city.getY());
  43.         double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) );
  44.  
  45.         return distance;
  46.     }
  47.  
  48.     @Override
  49.     public String toString(){
  50.         return getX()+", "+getY();
  51.     }
  52. }
  53. /*
  54.  * To change this license header, choose License Headers in Project Properties.
  55.  * To change this template file, choose Tools | Templates
  56.  * and open the template in the editor.
  57.  */
  58.  
  59.  
  60. public class GA {
  61.  
  62.     /* GA parameters */
  63.     private static final double mutationRate = 0.015;
  64.     private static final int tournamentSize = 5;
  65.     private static final boolean elitism = true;
  66.  
  67.     // Evolves a population over one generation
  68.     public static Population evolvePopulation(Population pop) {
  69.         Population newPopulation = new Population(pop.populationSize(), false);
  70.  
  71.         // Keep our best individual if elitism is enabled
  72.         int elitismOffset = 0;
  73.         if (elitism) {
  74.             newPopulation.saveTour(0, pop.getFittest());
  75.             elitismOffset = 1;
  76.         }
  77.  
  78.         // Crossover population
  79.         // Loop over the new population's size and create individuals from
  80.         // Current population
  81.         for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
  82.             // Select parents
  83.             Tour parent1 = tournamentSelection(pop);
  84.             Tour parent2 = tournamentSelection(pop);
  85.             // Crossover parents
  86.             Tour child = crossover(parent1, parent2);
  87.             // Add child to new population
  88.             newPopulation.saveTour(i, child);
  89.         }
  90.  
  91.         // Mutate the new population a bit to add some new genetic material
  92.         for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
  93.             mutate(newPopulation.getTour(i));
  94.         }
  95.  
  96.         return newPopulation;
  97.     }
  98.  
  99.     // Applies crossover to a set of parents and creates offspring
  100.     public static Tour crossover(Tour parent1, Tour parent2) {
  101.         // Create new child tour
  102.         Tour child = new Tour();
  103.  
  104.         // Get start and end sub tour positions for parent1's tour
  105.         int startPos = (int) (Math.random() * parent1.tourSize());
  106.         int endPos = (int) (Math.random() * parent1.tourSize());
  107.  
  108.         // Loop and add the sub tour from parent1 to our child
  109.         for (int i = 0; i < child.tourSize(); i++) {
  110.             // If our start position is less than the end position
  111.             if (startPos < endPos && i > startPos && i < endPos) {
  112.                 child.setCity(i, parent1.getCity(i));
  113.             } // If our start position is larger
  114.             else if (startPos > endPos) {
  115.                 if (!(i < startPos && i > endPos)) {
  116.                     child.setCity(i, parent1.getCity(i));
  117.                 }
  118.             }
  119.         }
  120.  
  121.         // Loop through parent2's city tour
  122.         for (int i = 0; i < parent2.tourSize(); i++) {
  123.             // If child doesn't have the city add it
  124.             if (!child.containsCity(parent2.getCity(i))) {
  125.                 // Loop to find a spare position in the child's tour
  126.                 for (int ii = 0; ii < child.tourSize(); ii++) {
  127.                     // Spare position found, add city
  128.                     if (child.getCity(ii) == null) {
  129.                         child.setCity(ii, parent2.getCity(i));
  130.                         break;
  131.                     }
  132.                 }
  133.             }
  134.         }
  135.         return child;
  136.     }
  137.  
  138.     // Mutate a tour using swap mutation
  139.     private static void mutate(Tour tour) {
  140.         // Loop through tour cities
  141.         for(int tourPos1=0; tourPos1 < tour.tourSize(); tourPos1++){
  142.             // Apply mutation rate
  143.             if(Math.random() < mutationRate){
  144.                 // Get a second random position in the tour
  145.                 int tourPos2 = (int) (tour.tourSize() * Math.random());
  146.  
  147.                 // Get the cities at target position in tour
  148.                 city city1 = tour.getCity(tourPos1);
  149.                 city city2 = tour.getCity(tourPos2);
  150.  
  151.                 // Swap them around
  152.                 tour.setCity(tourPos2, city1);
  153.                 tour.setCity(tourPos1, city2);
  154.             }
  155.         }
  156.     }
  157.  
  158.     // Selects candidate tour for crossover
  159.     private static Tour tournamentSelection(Population pop) {
  160.         // Create a tournament population
  161.         Population tournament = new Population(tournamentSize, false);
  162.         // For each place in the tournament get a random candidate tour and
  163.         // add it
  164.         for (int i = 0; i < tournamentSize; i++) {
  165.             int randomId = (int) (Math.random() * pop.populationSize());
  166.             tournament.saveTour(i, pop.getTour(randomId));
  167.         }
  168.         // Get the fittest tour
  169.         Tour fittest = tournament.getFittest();
  170.         return fittest;
  171.     }
  172. }
  173. /*
  174.  * To change this license header, choose License Headers in Project Properties.
  175.  * To change this template file, choose Tools | Templates
  176.  * and open the template in the editor.
  177.  */
  178.  
  179.  
  180. /*
  181. * Population.java
  182. * Manages a population of candidate tours
  183. */
  184.  
  185.  
  186.  
  187. public class Population {
  188.  
  189.     // Holds population of tours
  190.     Tour[] tours;
  191.  
  192.     // Construct a population
  193.     public Population(int populationSize, boolean initialise) {
  194.         tours = new Tour[populationSize];
  195.         // If we need to initialise a population of tours do so
  196.         if (initialise) {
  197.             // Loop and create individuals
  198.             for (int i = 0; i < populationSize(); i++) {
  199.                 Tour newTour = new Tour();
  200.                 newTour.generateIndividual();
  201.                 saveTour(i, newTour);
  202.             }
  203.         }
  204.     }
  205.  
  206.     // Saves a tour
  207.     public void saveTour(int index, Tour tour) {
  208.         tours[index] = tour;
  209.     }
  210.  
  211.     // Gets a tour from population
  212.     public Tour getTour(int index) {
  213.         return tours[index];
  214.     }
  215.  
  216.     // Gets the best tour in the population
  217.     public Tour getFittest() {
  218.         Tour fittest = tours[0];
  219.         // Loop through individuals to find fittest
  220.         for (int i = 1; i < populationSize(); i++) {
  221.             if (fittest.getFitness() <= getTour(i).getFitness()) {
  222.                 fittest = getTour(i);
  223.             }
  224.         }
  225.         return fittest;
  226.     }
  227.  
  228.     // Gets population size
  229.     public int populationSize() {
  230.         return tours.length;
  231.     }
  232. }
  233. /*
  234.  * To change this license header, choose License Headers in Project Properties.
  235.  * To change this template file, choose Tools | Templates
  236.  * and open the template in the editor.
  237.  */
  238.  
  239.  
  240. import java.util.ArrayList;
  241. import java.util.Collections;
  242.  
  243. public class Tour{
  244.  
  245.     // Holds our tour of cities
  246.     private ArrayList tour = new ArrayList<city>();
  247.     // Cache
  248.     private double fitness = 0;
  249.     private int distance = 0;
  250.  
  251.     // Constructs a blank tour
  252.     public Tour(){
  253.         for (int i = 0; i < TourManager.numberOfCities(); i++) {
  254.             tour.add(null);
  255.         }
  256.     }
  257.  
  258.     public Tour(ArrayList tour){
  259.         this.tour = tour;
  260.     }
  261.  
  262.     // Creates a random individual
  263.     public void generateIndividual() {
  264.         // Loop through all our destination cities and add them to our tour
  265.         for (int cityIndex = 0; cityIndex < TourManager.numberOfCities(); cityIndex++) {
  266.           setCity(cityIndex, TourManager.getCity(cityIndex));
  267.         }
  268.         // Randomly reorder the tour
  269.         Collections.shuffle(tour);
  270.     }
  271.  
  272.     // Gets a city from the tour
  273.     public city getCity(int tourPosition) {
  274.         return (city)tour.get(tourPosition);
  275.     }
  276.  
  277.     // Sets a city in a certain position within a tour
  278.     public void setCity(int tourPosition, city city) {
  279.         tour.set(tourPosition, city);
  280.         // If the tours been altered we need to reset the fitness and distance
  281.         fitness = 0;
  282.         distance = 0;
  283.     }
  284.  
  285.     // Gets the tours fitness
  286.     public double getFitness() {
  287.         if (fitness == 0) {
  288.             fitness = 1/(double)getDistance();
  289.         }
  290.         return fitness;
  291.     }
  292.  
  293.     // Gets the total distance of the tour
  294.     public int getDistance(){
  295.         if (distance == 0) {
  296.             int tourDistance = 0;
  297.             // Loop through our tour's cities
  298.             for (int cityIndex=0; cityIndex < tourSize(); cityIndex++) {
  299.                 // Get city we're travelling from
  300.                 city fromCity = getCity(cityIndex);
  301.                 // City we're travelling to
  302.                 city destinationCity;
  303.                 // Check we're not on our tour's last city, if we are set our 
  304.                 // tour's final destination city to our starting city
  305.                 if(cityIndex+1 < tourSize()){
  306.                     destinationCity = getCity(cityIndex+1);
  307.                 }
  308.                 else{
  309.                     destinationCity = getCity(0);
  310.                 }
  311.                 // Get the distance between the two cities
  312.                 tourDistance += fromCity.distanceTo(destinationCity);
  313.             }
  314.             distance = tourDistance;
  315.         }
  316.         return distance;
  317.     }
  318.  
  319.     // Get number of cities on our tour
  320.     public int tourSize() {
  321.         return tour.size();
  322.     }
  323.  
  324.     // Check if the tour contains a city
  325.     public boolean containsCity(city city){
  326.         return tour.contains(city);
  327.     }
  328.  
  329.     @Override
  330.     public String toString() {
  331.         String geneString = "|";
  332.         for (int i = 0; i < tourSize(); i++) {
  333.             geneString += getCity(i)+"|";
  334.         }
  335.         return geneString;
  336.     }
  337. }
  338.  
  339. /*
  340.  * To change this license header, choose License Headers in Project Properties.
  341.  * To change this template file, choose Tools | Templates
  342.  * and open the template in the editor.
  343.  */
  344.  
  345.  
  346.  
  347.  
  348. public class TourManager {
  349.  
  350.     // Holds our cities
  351.     private static ArrayList destinationCities = new ArrayList<city>();
  352.  
  353.     // Adds a destination city
  354.     public static void addCity(city city) {
  355.         destinationCities.add(city);
  356.     }
  357.  
  358.     // Get a city
  359.     public static city getCity(int index){
  360.         return (city)destinationCities.get(index);
  361.     }
  362.  
  363.     // Get the number of destination cities
  364.     public static int numberOfCities(){
  365.         return destinationCities.size();
  366.     }
  367. }
  368. /*
  369.  * To change this license header, choose License Headers in Project Properties.
  370.  * To change this template file, choose Tools | Templates
  371.  * and open the template in the editor.
  372.  */
  373.  
  374.  
  375. /**
  376.  *
  377.  * @author amani
  378.  */
  379. public class Ttsp {
  380.  
  381.     public static void main(String[] args) {
  382.  
  383.         // Create and add our cities
  384.         city city = new city(60, 200);
  385.         TourManager.addCity(city);
  386.         city city2 = new city(180, 200);
  387.         TourManager.addCity(city2);
  388.         city city3 = new city(80, 180);
  389.         TourManager.addCity(city3);
  390.         city city4 = new city(140, 180);
  391.         TourManager.addCity(city4);
  392.         city city5 = new city(20, 160);
  393.         TourManager.addCity(city5);
  394.         city city6 = new city(100, 160);
  395.         TourManager.addCity(city6);
  396.         city city7 = new city(200, 160);
  397.         TourManager.addCity(city7);
  398.         city city8 = new city(140, 140);
  399.         TourManager.addCity(city8);
  400.         city city9 = new city(40, 120);
  401.         TourManager.addCity(city9);
  402.         city city10 = new city(100, 120);
  403.         TourManager.addCity(city10);
  404.         city city11 = new city(180, 100);
  405.         TourManager.addCity(city11);
  406.         city city12 = new city(60, 80);
  407.         TourManager.addCity(city12);
  408.         city city13 = new city(120, 80);
  409.         TourManager.addCity(city13);
  410.         city city14 = new city(180, 60);
  411.         TourManager.addCity(city14);
  412.         city city15 = new city(20, 40);
  413.         TourManager.addCity(city15);
  414.         city city16 = new city(100, 40);
  415.         TourManager.addCity(city16);
  416.         city city17 = new city(200, 40);
  417.         TourManager.addCity(city17);
  418.         city city18 = new city(20, 20);
  419.         TourManager.addCity(city18);
  420.         city city19 = new city(60, 20);
  421.         TourManager.addCity(city19);
  422.         city city20 = new city(160, 20);
  423.         TourManager.addCity(city20);
  424.  
  425.         // Initialize population
  426.         Population pop = new Population(50, true);
  427.         System.out.println("Initial distance: " + pop.getFittest().getDistance());
  428.  
  429.         // Evolve population for 100 generations
  430.         pop = GA.evolvePopulation(pop);
  431.         for (int i = 0; i < 100; i++) {
  432.             pop = GA.evolvePopulation(pop);
  433.         }
  434.  
  435.         // Print final results
  436.         System.out.println("Finished");
  437.         System.out.println("Final distance: " + pop.getFittest().getDistance());
  438.         System.out.println("Solution:");
  439.         System.out.println(pop.getFittest());
  440.     }
  441. }
  442.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:240: error: class, interface, or enum expected
import java.util.ArrayList;
^
Main.java:241: error: class, interface, or enum expected
import java.util.Collections;
^
2 errors
stdout
copy 
Standard output is empty
https://ideone.com/6v4MCS
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!