Traveling Salesman Problem (TSP) By Ant Colony Optimization (ACO) – JAVA 8 Tutorial

Traveling Salesman Problem (TSP) By Ant Colony Optimization (ACO) – JAVA 8 Tutorial


individual ants have limited capabilities
but as a group they can achieve impressive results for example when searching for food
now finding food is an optimization problem meaning it’s a problem of gathering food while
minimizing the energy needed to do that now stigmergy is where individual organisms interact
with each other through modifications of their environment it is a form of self organization
that can produce complex structures and behavior without the need for planning or direct communication
now ants find the shortest path from colony to food source using stigmergy they use phermones
which is a chemical they produce in order to mark a path for other ants to follow now
when other ants come across a phermone trail they follow it with a certain probability
and this probability increases relative to the strength of the phermone trail and the
phermone strength increases relative to the number of ants that have followed that trail
and how recent this happened now ants do not always follow the same phermone trail because
some of them should always be searching for new food sources and phermone trails degrade
overtime so that ones that no longer lead anywhere stop being attractive and are replaced
by other trails so the above is the inspiration for ant colony optimization where we are not
looking for a model of real ant behavior but we are attempting to exploit elements of ant
stigmergy in order to solve similar problems this tutorial covers solving the traveling
salesman problem with ant colony optimization and java 8 i will start with a demo of the
prebuilt aco application where each city is identified by its latitude and longitude
coordinates and where the haversine formula is used in order to calculate distances between
cities and where the application will find and display the shortest route 2nd i will
step by step write explain and run this application using an eclipse ide this is the prebuilt
application so let’s go ahead and run it so we have 500 artificial ants and we started
with this route as the shortest route with ant number 2 so we start from Boston and than
go to New York then Chicago etc until San Francisco and then go back to Boston and we
ended up with this route as the optimal route with this distance in miles and this was discovered
by ant number 63 next i’ll start by creating a new project and this will be running on
Java 8 and we will initially start with 3 classes before adding the remaining classes
so this class will be driving the application and it will have a main method and we will
have an Ant class and a Route class now for the purpose of this tutorial let’s define
500 ants with each of them trying to find the shortest route and we will define this
executor service and this is an executor that provide methods
to manage termination and methods that can produce a future for tracking progress of
one or more asynchronous tasks and we will have this executor completion service it uses
a supplied executor to execute tasks and this class arranges that submitted tasks are upon
completion placed on a queue accessible using the take method and i also need to define
this counter for the number of active ants and we need to instantiate and activate each
one of those 500 ants so we will do it in this loop we will use the executor completion
service submit method and this method takes in a callable let’s go to the ant class and
make it implement the callable interface and by doing that we will add this method call
and from the ant class i will need access to the route that this ant has traversed so
we’ll define this route and a get method and also let’s have a print line statement here
and going back to the driver class now we can do a submit and here we will instantiate
a new ant and let me instantiate a driver instance here and we will increase the counter
here and we will have a while loop so while we have active ants we will call the take
method on the executor completion service and this will end up triggering a call to
this method to the call method which would return an ant instance and from that instance
we can get access to the route associated with that ant and in the while loop we will
decrease the counter and we will do a shutdown now on the executor service and let’s add
some print line statements and we’ll have one to indicate that we submitted a new ant
and one to indicate that we did a take method on the executor completion service so let’s
go ahead and test run the application before adding the remaining classes here we go we
entered the activate ants loop and this is for each one of the ants so after take is
called the call method ends up being invoked then we exit that loop so let’s go ahead and
add this ant colony optimization class and a city class representing a city on the
route and we also need a utility class atomic double and it will be in this package now
the city class will have the exact same code as in previous traveling salesman problem
tutorials that i have done so we have 3 constants the earth equatorial radius and converting
degrees to radians and converting kms to miles and a city is defined by its longitude latitude
and name and those 3 are initialized in the constructor and we have get methods for all
3 of them and the toString method returns the name of this city and the measure distance
method measures the distance between the passed in city and this city and it uses the haversine
formula to do that and the route class will have an ArrayList
of cities on this route and the total distance for the route
and get methods for both and the constructor will initialize those 2 values and the toString
method will print out all the cities on this route and the total distance and for AtomicDouble
an operation is atomic when you can safely perform the operation in parallel on multiple
threads without using the synchronized keyword or locks so we will have this class extend
Number and implement the Comparable interface and since this is a utility class i’ll just
put the code that we need over here next let’s go to the Driver class and add
this initial route now going to the AntColonyOptimization class
we need 2 matrices here one to keep track of the phermone levels between the different
cities and another to keep track of the distances and we will have get methods for both and
the cities ArrayList will be what’s in the initial route and the size will be the size
of that initial route ArrayList and we will have 2 methods for initializing the distances
and for initializing the phermone levels in both matrices so we measure the distances between the cities
using the measure distance method on the city class
and we have an outer loop and an inner loop which allows us to pick up all combination
of cities and in this method we will randomly initialize the phermone levels in this 2 dimensional
array and to do that we have an outer loop and an inner loop next let’s go to the Ant
class and here i wanna keep track of the AntColonyOptimization instance we are
using and the Ant identification number and we will have a constructor that would initialize
both of them and a get method for the ant number and let’s define -1 as an invalid city
index and the number of cities will be whats in the initial route and before continuing
with the Ant class let’s go here and fix this error message so i’ll have this AntColonyOptimization
instance and pass that instance and the ant number to the new ant we are instantiating
so let’s go back to Ant now in the call method we will start by randomly picking up the index
of the originating city and let’s define an ArrayList containing all the cities on this
route for this ant and we will be returning this and we will have a HashMap for visited
cities and initially we will indicate that all the
cities are not visited in this HashMap and let’s define this number of visited cities
and initialize it to 0 and let’s indicate that the originating city is visited so we
have the originating city index here inside the visited cities HashMap and were setting
true here and i will initialize the route distance to 0 and x will be the index of the
originating city and initially y will have -1 as index and if we haven’t yet visited
all the cities than i will have this method get y that will return the index of the next
city to visit and let’s define this get y method and let’s return the invalid city index
for now we will pass it the index of the originating
city and a hashmap of all the visited cities and it would return the index of the next
city to visit and going back to the call method so if we haven’t yet visited all the cities
than we will add the originating city so driver dot initial route dot get x to the array list
route cities that this ant is traversing and we will add the distance from city with index
x to city with index y to the route distance and next we’ll call a method that adjust the
phermone level so this method takes in the indexes of the originating and destination
cities and the distance and next we will indicate that the city with index y so the name of
that city so it is visited and next i will set the index of the originating city to be
what used to be the index of the destination city and next we will try to find another
city to visit if we have not yet visited all the cities otherwise i will set y to be the
invalid city index so that we can exit this while loop and after exiting this loop we
will add the distance from the final city back to the originating city to the route
distance and since x is the last city i will add it to the route cities and the route associated
with this ant will be a new route instance given the route cities and the route distance
and we will return this ant instance next in adjust phermone level i will have a boolean
flag and only exit this while loop if the flag is set to true and we will initially
pickup the current phermone level between cities with index x and y
and next i will update the phermone level according to this formula so Q is a parameter used for adjusting the
amount of phermone deposited and the value is between 0 and 1 and ROU is a parameter
used for varying the level of phermone evaporation and the value is between 0 and 1 and for the
purpose of this tutorial i’ll have that set to those two values
and next if all phermone have evaporated between cities with index x and y than i will set
the phermone level to 0 otherwise i will set the phermone level in the matrix to the updated
phermone level now in the get y method i will start by picking up a random double number
between 0 and 1 and next i will pickup an array list of transition probabilities and
those would be the probabilities of moving from city with index x to the other cities
so i need to define this method so we will have this array list transition
probabilities that we will end up returning after populating it now going back to the
get y method let’s go ahead and add this logic so we would go through all the cities and
if the transition probability of city with index y is bigger than a random number than
this will be the index of the destination city otherwise we would modify random and
go back into the loop trying to find a different destination city and now coming back to this
method i will initialize all the transition probabilities in this array list to 0 and
before finishing this let me define two methods get transition probability denominator
and we’ll define this denominator and end up returning it and get transition probability
numerator and we’ll define this numerator and end up returning it
so here the denominator will be what’s returned from this method so i will pass it the array
list of transition probabilities and the index of the originating city and a hashmap of visited
cities and i will set all the transition probabilities in this array list according to this formula
now here i will have this logic so we will go through all the cities and if the city
have not been visited here we make sure that we are not moving from and to the same city
otherwise we will set the transition probabilities to what’s returned from this method and here
we are adding that transition probability to the denominator
and in this method this is the logic that we need to add and let’s come back here and
define alpha and beta so alpha is the parameter used for controlling the importance of the
phermone train and the value is bigger or equal to 0 and beta is a parameter used for
controlling the importance of the distance between source and destination and the value
is bigger or equal to 1 so here i am picking up the phermone level from the phermone level
matrix between cities with index x and y and if that phermone level is different than 0
than the numerator will be set according to this formula this should do it for this class
next let’s go to the driver class and here let’s start by defining this processing
cycle probability that i will be using shortly and this route and we will start the main
method with a println statement indicating the number of ants that have been activated
and let me remove this println and we will have this print heading method that will print
the heading row so the route the distance in miles and the ant identification number
and after instantiating the driver we will do print heading and let’s add this process
ants method and we will move he while loop down there and we will do if pickup a random
number and if its bigger than the processing cycle probability than we go ahead and call
the process ants method and here let’s take out the driver we don’t need it and let’s
rewrite this executor completion service dot take so we pickup an ant so what take returns
is a future so that future we do get on it and so when take gets called what ends up
being called is this call method which returns an ant and up here before doing the shut down
now will call the process ant again to finish up all ants that haven’t been processed yet
and we will pickup the route that was traversed by this ant so ant dot get route and if the
distance for the current route is smaller than the distance for the shortest route the
shortest route becomes the current route and than we do a system dot out dot println for
the cities in the shortest route and the distance that we prepare over here and the ant identification
number that found this route and after the shutdown let’s go ahead and add these two
println statement so the optimal route and the distance of that optimal route finally
let’s go ahead and test run this application so ant with identification number 1 found
this route starting from Austin going to Houston etc until getting to Boston and then going
back to Austin and it had this distance in miles and ant with identification number 267
found the optimal route and it has this distance in miles

Comments

  1. Post
    Author
  2. Post
    Author
  3. Post
    Author
  4. Post
    Author
  5. Post
    Author
  6. Post
    Author
    zaneacademy

    TSP + Ant Colony Optimization (ACO) + SQLite DB + JAVA @ https://youtu.be/nBIXdpb0bRY

    Traveling Salesman Problem (TSP) By Ant Colony Optimization (ACO) – JAVA 8 Tutorial @ https://youtu.be/i_DX8K1i3vU

    Traveling Salesman Problem (TSP) By Ant Colony Optimization (ACO) – w/ File Input @ https://youtu.be/uAQxHW61Ek8
    TSP By Genetic Algorithms w/ JAVA @ https://youtu.be/Z3668A0zLCM

    TSP By Simulated Annealing w/ JAVA @ https://youtu.be/1kgbwosVUPs

    TSP By Nearest Neighbor w/ JAVA @ https://youtu.be/m7O0n8Fv-94

    TSP By Hill Climbing w/ JAVA @ https://youtu.be/eGT9RuhclUE

    TSP By Recursive Brute Force w/ JAVA @ https://youtu.be/rZeBBXbBSMY

    TSP By Random Restart Hill Climbing w/ JAVA @ https://youtu.be/itijbdn0Xz0

  7. Post
    Author
    Yogesh Kumar

    can we implement ACO on printing Neatly problems? I am struck would you please help me in implementation of ACO for printing neatly problems

Leave a Reply

Your email address will not be published. Required fields are marked *