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

Author

thx

Author

Thank you.

It's really interesting.

Waiting for VNS and PSO tutorials ðŸ™‚

Author

I cant find the download source in your website :/

Author

what is the accuracy percentage of this implementation?

Author

Do you have a implementation for Artificial Bee Colony? ðŸ™‚

Author

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

Author

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