Ant colony algorithm simulation

Every software developer will have a point where he / she looks back and says "what kind of code i wrote" :) Back in 2013, i have seen optimization tecniques like hill climbing, ant colony, genetic algorithm and artificial neural networks as a graduate student. As the final project of the intelligent optimization techniques course, i have developed a simulator where you can observe how ant colony optimization algorithm works in realtime and can be used as a training tool. I have had uploaded a video that shows how this simulator works to youtube, which is the first video i have ever uploaded. After 4 years, i have decided to push the source code into my github repo and the commit message was "First and probably the last commit". And 3 years passed. I have decided to write about it here and optimized the old code a little and doubled the performence of the simulator. Maybe i would decide to re-write it from scratch to make it work with multithreads :D

First i will explain ant colony algorithm. Then i will explain the video that shows how to use it and the logic of my application. Then i will tell you how to run this JavaFX application. Lastly i will trash my own application that i have developed 7 years ago and write about the deficits and where can it be improved. Maybe someone can take the code and improve it..

What is ant colony optimization

Optimization means converging on the optimzel value or solution. If the complexity required to solve a problem get more and more complicated, it brings the need to divide the problem into small pieces. Because there may not be efficient methods that guarantees a certain solution. In this case, we can converge to the ideal solution by optimizing the small solutions with iterations. If you are saying "in English please?", let me give you this example. You know the ants come and go after they leave their nest. This way they find the closest source of food and draw a straight line. This is what i mean.

Ant colony behaviour is modeling the ants (or any other animal) leaving their nest and finding the shortest path to some point. This is called a swarm behaviour. All the ants are acting on a certain logic and creating a collective movement or action. It leaves the nest and starts leaving a substance called pheromone. When it finds the food and gets back, the pheromone will be evaporated. If the food is far away, the pheromone will be mostly evaporated. If the food is somewhere near, the pheromone will lure the other ants towards that path too. This way, the shortest path will survive. So yes, this is kind of a survival of the fittest logic. Even though the ants look like flies, you can understand the result if you take a look at the image that represents this mechanism.

The ants have found the shortest path between the brown big dot at the top left and the turquoise dot on the bottom right of the map. There is a mathematical expression of the actions of these ants. But we need a map that we can impose this expression. This is called a Graph. It is sort of like a star map and it connects small dots called nodes. The path between these nodes are called edges. Each ant knows the edges connected to the nodes in the computer envorinment and most likely directs to the path that has the most amount of pheromone scent. Moreover, if the pheromone amounts are the same among those edges, it heads to the shorter ones in order to minimize the path. Of course there is a risk of chosing the longer path overall with a shortsided desicion.

We should also take the evaporation of the pheromone into account. All the edges that have pheromone must also fade it away. This will be our first formula. The second one is the parametric scoring formula that takes the pheromone amount, the tendency to chose the edge with the most amount of pheromone and the tendency to choose the short edge. Let 's take a look at the pheromone amount formula first.

Here, F_ij(t + 1) gives us the pheromone amount of the edge between the i and j nodes at the t + 1 instant according to the amount at t instance. This is the amount of pheromone on the edge, not the node. We can calculate the result by multiplying the t instance (F_ij(t)) and the evaporation ratio (b). For example, if evaporation is 30%, we will multiple with 0,7. Then we will add the amount that the ant releases, Delta F_ij.

The released amount it Q / Kn where q is the amount that the ant drops and the Kn is the length of the edge. Thus, there will be less amount overall on the longer edges and more on the shorter edges. The purpose is to converge to the shorter path be sticking to shorter edges. But this is not the only criteria. Because we would end up choosing 5 short edges over 1 long edge and increasing the overall length. Therefore we have the core function and weighted probability choices.

P_ij means the probability of chosing the edge between the i and j nodes. For example, if there are 2 edges connected 1 nodes, they can have probabilities like 70% and 30%. Of course it will probably head towards the most likely one. This probability function has the amount of existing pheromone on the edge between the nodes i and j. We use the alpha parameter as the power to make this value weihgted. Alpha is the tendency to head towards the edge with most pheromone. N_ij is the length of the edge between the nodes i and j. We have a beta parameter as the power so that we can change the tendency to chose the shorter edge. Attention here, the beta is between 0 and -1 therefore the longer edge will have less weight..

The numerator is calculated for 1 edge. We add all the values of pheromone to the power of alpha and edge length to the power of beta for all of the edges for the denominator. This way, we can have probabilities like 1/10, 3/10 and 6/10 for 3 edges for example. The edges will be chosen by 10%, 30% and 60%. This mechanisim doesn't have a mathematical representation but the calculation is epic.

Let's consider these 3 probabilities. 1, 3 and 6 makes 10 total. These could be 6, 3 and 1 too. Since the total is 10, we take a random number between 0 and 10. Let's suppose it is 4. We subtract the numbers one by one from 4. So 4 - 1 makes 3. And 3 - 3 makes 0. When we reach 0 or below, we chose that number. In this case we chose the edge with the probability of 3, which is the second. The bigger numbers will more likely to drop the result below zero, therefore they will be selected more frequently. This is weighted probability.

Each and every ant makes this calculation and decides where to go. By appling this operation to a lot of ants, we are basically optimizing the solutions by iterating over them. This ant colony optimization is used in shortest path problems. It can also be useful for edge tracking in image processing. My master thesis was facial expression recognition, which i will write a post later. I have come across with publications that uses ant algorithm to define and detect facial expressions. I have thought about giving the nodes some properties and dynamically adjusting the pheromone amount to create a algorthm for logistics companies' distributions.

As you can see, this is a small but effective optimization algorithm. I haven't seen another comperehensive example of my simulator that lets you observe and experiment on how the ant algorithm works. There are 3 - 4 small examples because people are mostly interested in artificial neural networks and genetic algorithm. My application is providing this opportunity to everyone by simulating the algorithm realtime. You have to know what is the ant algorithm in order to use the application. If you don't have much knowledge, the video that shows how to use it is down below. Even though it is the old version of the application, the basic idea is still the same.

Let me explain the video

Upon start-up, the application lays out the grid according to your screen resolution. If you open it fullscreen or maximized mode, there should be no empty or overflowed areas. You can adjust the animation speed, the amount of pheromone that the ants drop, alpha and beta parameters with the settings onthe right. In the updated version of the app, you can also set the visibility of the edge info texts, which shows the pheromone amount and the length. I first chose to load a graph that i have saved before to load. Then i add 1 nest and 1 food point by right clicking. Then i start the simulation.

Ants start navigating and leaving pheromone all over the place, as intended, and the edges with more pheromone gets more red. The animation speed can be changed at any time. All of th settings except the ants count can be changed and will be immediately reflected to the simulation. I stop the animation and delete an edge on the fly and the ants stick to the older path because of the power of the alpha parameter. Then the ants find the shorter path when i restart the simulation.

You can set any point as food or nest point. You can set only 1 nest but you can set multiple food points. They will find the nearest food. This is not in the video because i didn't think about it back then. Then i show how to draw a graph yourself. As long as the draw graph button is active, you can add new nodes or connect any of them with any of them. You can also save your custom graph to a file and load it just like the beginning in the video. I will be saved and loaded with the parameters. I conclude the video by experimenting on my own drawing. Since there is only one food point, let me put an image of what it looks like.

Running the application

You can find the source code of this application on github. I have developed this project with JDK 8 using JavaFX. I can say JavaFX is basically a library developed on top of Java Swing interface components. It has its own coding style and the property binding becomes very handful. It also helps drawing 3D objects and animations. You can use the xml based FXML files to define interfaces and apply CSS on it. JavaFX comes with JDK 8 but after JDK 11, you need to download OpenJFX which is maintained by community because Oracle ended its support for it.

I ahve developed this project with Netbeans. You can use eclipse or intellij. The important part is to get the JavaFX plugin for the IDE. If you use netbeans, you can easily run the app with ant scripts, which are not ants since ant are not responsible for compiling java code :) I have seen JavaFX developed with spring boot or a simple maven project but i didn't change the infrastructure since i have used JDK 8, which is old already. When you open the project you will see the main class that extends Application class and the start method is overriden. This start method is the main entry point for JavaFX but actually it has a real main method behind the scene that initiates Application class. The plugin of the IDE handles this packaging and running.

If you don't want to open the project with and IDE, you can also run it if you install JDK 8. You can download the latest Jar file here and run a command like java -jar "Ant Algorithm.jar" in the java installation folder on command line.

Difficulties and deficits

Let me explain the "what kind of code i wrote" question that i have asked at the beginning :) The main class of the application is more than 1K lines of code and it is generating the interface with code rather than using FXML. This also helps the interface fit into any kind of screen without overflow but increases the code complexity. Furthermore, for some unknown reason, i have had used Arrays instead of Arraylists for most of the data structures. I could have even increased the performance by using HashMaps and therefore avoding for loops for some functionalities. On the other hand, 3000 ants are able to decide and move without any troubles. The most important method in the entire application is the create_animation method that decides where to go for the ant creates the animation. There are inconsistencies in the naming convention and some names are snake case some are camel case. That is what would you expect from a 2 years old junior developer :)

The biggest trouble of this kind of simulator app is the performance. You would either consume too much memory or processing power. My application seems like it is leaning towards too much (or inefficient) cpu usage. It keeps the graph info at the top level and moves the ants according to this data. Even though it looks like the ants are deciding on their own, the desicion mechanism is probably on the main class. Also, there may not be thread safety if more than 1 ant drops pheromone at the same time. I think i should also investigate how the animation classes work in JavaFX.

3000 ants are able to move freely and simultaneously since JavaFX animations are using GPU. But the desicion for each ant is being made on the main thread, which is probably the interface thread. If you can distribute the desicion method across multiple threads, it would make the app faster and let you increase the number of the ants. At this stage, i can't migrate to a multithreaded soluiton without re-writing almost the entire application (at least the ants, animations and the calculation logic) from scratch.

Download, have fun, learn

This sounded like a mobile game ad. In this post, i have introduced my ant colony algorithm simulation. This simulation does not guarantee you to be able to find the shortest path always. It enables you to observe how the algorithm works in realtime and experiment on it by changing the parameters on the fly. You can fork the code and improve or use it however you want or show it to your students in your lectures, with a small acknowledgement. See you at the next post :)