A Java Primer of Ant Colony Algorithms

The Ants in the Garden

Ants always find a way: I used to found them on the garden of my house marching on ordered lines while carrying food to their nest. And they were indeed ordered: all the ants seemed to be following some paths that my eyes weren’t able to see. Later, I found these paths weren’t only invisible: They were also optimal. Which is kind of surprising since ants have very limited sight and a very small brain.

The colony mechanism is as simple as it is surprising. When the ants traverse a terrain looking for food, they drop a chemical called pheromone. This means that the ants that by chance have found shorter paths have also deposited more pheromone on them. Because the path are shorter -i.e optimal- they can traverse it more times in the same amount of time.

Pheromone is special for Ants for two reasons: They have senses to detect it and they feel attracted to it. This translate that Ants will have a tendency to traverse paths that have stronger pheromone trails on them. The technical term for this is stigmergy, and is the mechanism that allows this amazing behavior:

  1. All Ants of the colony go after a food. They traverse randomly the garden looking for a way to reach it.
  2. A very lucky ant gets there first, before any other fellow ant. He grabs the food, and returns it to the nest.
  3. New ants are assigned the mission to get food to the nest. These new ants found the pheromone deposited in 2, so they follow that lead.
  4. While the Ant in 2 keeps going from the Food to the Nest, the other unlucky ants are still trying to find their way.
  5. Now the path discovered in 2 is very pheromone intensive, because is being traversed several times by several ants. Even the Ants that take inefficient paths in 1 are now taken the path discovered in 2 since is so attractive now (i.e pheromone intensive).
  6. Now all the colony follows the optimal path.

That means that the Colony won’t starve, and that the system has converged to optimality.

The Ants in Code

But this is a Programming article, not a Biology one. On 1992, Marco Dorigo applied the strategy of the Ants to the solution of optimization problems. There are problems in Computer Science where the search space is so vast that it is impossible to traverse it completely to find the optimal solution. So, what Dorigo proposed was to build Software-Ants that will traverse this search space and look for an optimal solution, like the real ants do. This artificial ants don’t guarantee us that they will find the best solution, but they will find as a solution that is good-enough for our needs. The algorithms of this kind are called heuristics.

The optimization problems that can be solved in this fashion are vast: I can mention now the Travelling Salesman Problem, the Knapsack Problem and even Image Processing tasks like Image Segmentation and Clustering. And since Dorigo’s proposal on 1992 several algorithms have appeared that follow the principle of using Artificial Ants, like Ant System, Ant Colony System, Max-Min Ant System and many others. These algorithms have being grouped in a meta-heuristic which is now known as Ant Colony Optimization (ACO).

The Ants in Java

So, with Ant Colony Optimization you can solve several problems, using several algorithms. In order to save myself some lines of code, I have developed a little framework that allows an easy implementation of ACO algorithms in Java, called Isula (available for free here). I will use some snippets from Isula to demonstrate how to implement Ant Algorithms in Java.

This is a portion of the solveProblem() method of the AcoProblemSolver class:

        while (iteration < numberOfIterations) {

          antColony.clearAntSolutions();
          antColony.buildSolutions(environment, configurationProvider);

          applyDaemonActions(DaemonActionType.AFTER_ITERATION_CONSTRUCTION);

          updateBestSolution(environment);
          iteration++;
        }

That’s a snippet from an Isula-based Java Program available here.

This is the main loop of any Ant Colony Algorithm. We need to establish a stop condition for our program, so we define a parameter to set the maximum number of iterations our Ants will be traversing the problem space, which in the ACO domain is usually a graph. On each iteration, these things happen:

  1. Our Ants prepare themselves to build a solution: This can be a route, a cluster or any other entity which our problem requires us to find.
  2. The colony will traverse the problem graph and every ant of them will built a solution. Some of them will be good, some of them will be bad.
  3. There are some global actions that can be required in our algorithm. For example, we can rank our ants and only allow some of them to deposit pheromone. Those procedures are called Daemon Actions in ACO terminology.
  4. We store the best solution built so far. When we reach the maximum number of iterations, that will be the output of our program.

Now let’s take a deeper look into how the colony builds solutions. This is a snippet from the buildSolution() method of the AntColony class:

        for (Ant<C, E> ant : hive) {

          while (!ant.isSolutionReady(environment)) {
            ant.selectNextNode(environment, configurationProvider);
          }

          ant.doAfterSolutionIsReady(environment, configurationProvider);
        }

Some things to note there:

  1. The AntColony class administer a number of ants which are stored in the hive attribute. It depends on your algorithm characteristics or a parameter how many ants you want to use.
  2. Each ant of the colony will add components to their solution until it is considered finished. For example, if we’re tyring to cluster an image we will continue adding pixels to the cluster until we have covered every pixel in our image.
  3. The selection of the next component is stochastic: the ant will choose according some probabilities. One key factor in their decision is the amount of pheromone related to a solution component, but several others will be considered depending on the algorithm you are using.
  4. Once an Ant has finished its solution, some things might happen. You can improve the generated solution with a local search procedure, for example, or you can start depositing pheromone. Once again, that depends on the nature of your algorithm.

And, the more important class if you are working on an Ant algorithm is the Ant itself. Here’s a snippet of the Ant class taken from Isula:


public abstract class Ant<C, E extends Environment> {

  private int currentIndex = 0;
  private List<AntPolicy<C, E>> policies = new ArrayList<AntPolicy<C, E>>();
  private C[] solution;
  private List<C> visitedComponents = new ArrayList<C>();

Notice this:

  1. This is parametrized class. The class Parameter C represents a component in our solution: In the image clustering example, this class would represent a pixel and the assigned cluster.
  2. The solution is an array of these components. This Java Ant controls how the solution is built by keeping the current component index in the array.
  3. The Ant behavior is also determined by the algorithm you are using or proposing. For example, the specific rule for selecting a component vary greatly from algorithm to algorithm. This specific ant behavior is modeled as an AntPolicy in the Isula Framework.

The Ants in Action

Let’s put our colony to work in order to solve a specific optimization problem. The Flow Shop Scheduling optimization problem tries to find an optimal ordering of a number of jobs, given each job needs to be processed on some machines, requiring a specific amount of time on each machine depending on the job nature.

We will try to find an ordering of jobs -permutation in combinatorial terms- so we finish processing all the jobs in the minimum amount of time. Depending on the number of jobs and machines, solving this problem precisely can take considerable time, so we rely on our Isula-based ants to find a good-enough solution:

      FlowShopProblemSolver problemSolver;

      ProblemConfiguration configurationProvider = new ProblemConfiguration();
      problemSolver = new FlowShopProblemSolver(graph, configurationProvider);
      configurationProvider.setEnvironment(problemSolver.getEnvironment());

      problemSolver.addDaemonActions(
          new StartPheromoneMatrixForMaxMin<Integer, FlowShopEnvironment>(),
          new FlowShopUpdatePheromoneMatrix());
      problemSolver.getAntColony().addAntPolicies(
          new PseudoRandomNodeSelection<Integer, FlowShopEnvironment>(),
          new ApplyLocalSearch());

      problemSolver.solveProblem();
      showSolution(graph, problemSolver);

That’s a snippet from an Isula-based Java Program available here , which is an adaptation of the algorithm proposed by Thomas Stutzle in the paper “An ant approach to the flow shop problem”. Take a look at the following:

  1. The FlowShopProblemSolver is an extension of the AcoProblemSolver class we reviewed before, with some minor modifications to suit the Flow-Shop problem. We call the solveProblem() method in order to trigger the generation of the solution.
  2. The paper proposes an adaptation of the well-known algorithm Max-Min Ant System, so we are reusing some code already available for that algorithm, like the Daemon Action for initializing the pheromone matrix. The Update Pheromone Matrix policy was also reused but some adaptations were required.
  3. A very popular node-selection rule was proposed by Dorigo in its Ant Colony System algorithm. Stutzle used the same in its paper, so we can reuse it directly from the implementation available in Isula code.
  4. The author proposes a Local Search procedure after an Ant finishes building its solution. We developed a custom Ant Policy for that task.

We will try our algorithm with a problem instance of 20 jobs and 5 machines (dataset available here). Here’s a visual representation of the solution found:

aco-flowshop

I hope this article helps you get a feeling on what you can accomplish through Ant Colony algorithms, and how to do it in the Java Programming language. I also invite you to take a look at the Isula Framework and try to use the code already available. I’d like to finish with some Java Projects that use ACO algorithms to solve optimization problems:

  1. The Flow Shop Scheduling Problem, using Max-Min Ant System
  2. Image Binary Thresholding, with Ant System
  3. Image Clustering using Max-Min Ant System
Advertisements

Removing duplicates in an unsorted Linked List

I started reviewing Cracking the Coding Interview by Gayle Laakmann, since my last coding interview doesn’t come as good as I expected. The book is very well written and the problems contained there come from the very basic to some advanced stuff, and it represent a good choice if you want to refresh your rusty algorithms knowledge from college.

Another rusty skill I’m in urgent need to update is my blogging, so I thought reading and reviewing that book would be an excellent opportunity to also retake my long forgotten English blog. What I will  try to do is post here my very first attempts of  resolution for some problems contained in the book, share my code with the community and -hopefully- get some feedback from the readers. These are not the responses contained in the book (I believe in some cases they might coincide) but my personal (and maybe naive) approach for solutions in the Java Programming Language.

I also hope to don’t get in some copyright trouble posting the problems contained in the book. If that’s the case Gayle and you’re reading this, please let me know xD.

Well, saying that, what I’m trying to do in this post is to remove duplicates from an unsorted Linked List. The first step is to define the classes that will represent that data structure, so I used two simple classes to represent the Head of the List and another one for every Node in it, using generics to make them flexible. This might seem overkill -specially the Head class- but I’m more comfortable with that approach,  having a clear separation between the List and the elements contained within it.

So, here’s the Node:

package coding.problems.linkedlists;

/**
 * A node in a Linked List.
 *
 * @author Carlos G. Gavidia (cgavidia@acm.org)
 *
 * @param <E>
 *            Data type of the node's data.
 */
public class LinkedListNode<E> {

	private LinkedListNode<E> nextNode;
	private E data;

	public LinkedListNode(E data) {
		this.data = data;
	}

	public LinkedListNode<E> getNextNode() {
		return nextNode;
	}

	public void setNextNode(LinkedListNode<E> nextNode) {
		this.nextNode = nextNode;
	}

	public E getData() {
		return data;
	}
}

And here’s the List. The getElementCount method will prove useful in testing:

package coding.problems.linkedlists;

/**
 * A Linked-List representation.
 *
 * @author Carlos G. Gavidia (cgavidia@acm.org)
 *
 * @param <E>
 *            Data type of the node's data.
 */
public class LinkedList<E> {

	private LinkedListNode<E> head;

	public LinkedListNode<E> getHead() {
		return head;
	}

	public void setHead(LinkedListNode<E> head) {
		this.head = head;
	}

	/**
	 * Gets the number of nodes that have a particular data value.
	 *
	 * @param elementToCount
	 *            Data value to count.
	 * @return
	 */
	public int getElementCount(E elementToCount) {
		int elementCount = 0;
		LinkedListNode<E> currentNode = this.getHead();
		while (currentNode != null) {
			if (currentNode.getData().equals(elementToCount)) {
				elementCount++;
			}
			currentNode = currentNode.getNextNode();
		}
		return elementCount;
	}

Then there comes the fun part: How do I remove duplicates? My plan was quite simple:

  • Per every node in the list, I will traverse the rest of the list -excluding the current node- to search if there are other nodes that have the same value. To traverse the Linked List, I use a simple loop in the removeDuplicates method.
  • Then I need a method that will do the dirty work, that is, search and remove every node in the list that has the same data value as the current node and remove it from the list. All that is done in the removeFrom method.
  • In removeFrom everything is pretty straightforward: What I do is break the “next” references of the nodes I need to remove so they will be garbage-collected later. There’s a special edge case when I’m in the need to remove the last item of the list, so I will keep a reference of the previous reference of the current node that will allow me to remove the last node if I’m in the need of it.

The advantages of that approach is that I don’t require additional memory to perform the operation, and that the search and removal will require less computing power through iterations since the list will become shorter after the removals were made. Saying that, the solutions is 50 lines long, including comments:

package coding.problems.linkedlists;

/**
 * Class for remove duplicate elements from an unsorted linked list. Problem
 * taken from Cracking the Coding Interview from Gayle Laakmann.
 *
 * @author Carlos G. Gavidia (cgavidia@acm.org)
 *
 * @param <E>
 *            Data type of the Linked List Node's data.
 */
public class DuplicatesRemover<E> {

	public void removeDuplicates(LinkedList<E> linkedList) {
		LinkedListNode<E> currentNode = linkedList.getHead();
		while (currentNode != null) {
			removeFrom(currentNode.getData(), currentNode);
			currentNode = currentNode.getNextNode();
		}
	}

	/**
	 * Removes elements that have a particular data value, excluding the node
	 * that starts the traversal.
	 *
	 * @param elementToRemove
	 *            Element to remove.
	 * @param nodeToStart
	 *            Node that starts the list traversal.
	 */
	private void removeFrom(E elementToRemove, LinkedListNode<E> nodeToStart) {
		LinkedListNode<E> currentNode = nodeToStart;
		LinkedListNode<E> nextNode = null;
		LinkedListNode<E> previousNode = null;

		while (currentNode != null) {
			nextNode = currentNode.getNextNode();
			if (nextNode != null && elementToRemove.equals(nextNode.getData())) {
				currentNode.setNextNode(nextNode.getNextNode());
			} else if (nextNode == null
					&& elementToRemove.equals(currentNode.getData())) {
				previousNode.setNextNode(null);
			}
			previousNode = currentNode;
			currentNode = currentNode.getNextNode();
		}
	}
}

And here’s a Unit Test to verify that everything is working as expected.

package coding.problems.linkedlists;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class DuplicatesRemoverTest {

	private LinkedList<Integer> listWithDuplicates;
	private DuplicatesRemover<Integer> duplicatesRemover;

	@Before
	public void setUp() throws Exception {
		listWithDuplicates = new LinkedList<Integer>();
		duplicatesRemover = new DuplicatesRemover<Integer>();

		LinkedListNode<Integer> firstNode = new LinkedListNode<Integer>(1);
		LinkedListNode<Integer> secondNode = new LinkedListNode<Integer>(2);
		LinkedListNode<Integer> thirdNode = new LinkedListNode<Integer>(3);
		LinkedListNode<Integer> fourthNode = new LinkedListNode<Integer>(2);
		LinkedListNode<Integer> fifthNode = new LinkedListNode<Integer>(4);
		LinkedListNode<Integer> sixthNode = new LinkedListNode<Integer>(4);
		LinkedListNode<Integer> seventhNode = new LinkedListNode<Integer>(4);

		firstNode.setNextNode(secondNode);
		secondNode.setNextNode(thirdNode);
		thirdNode.setNextNode(fourthNode);
		fourthNode.setNextNode(fifthNode);
		fifthNode.setNextNode(sixthNode);
		sixthNode.setNextNode(seventhNode);

		listWithDuplicates.setHead(firstNode);

	}

	@Test
	public void testRemoveDuplicates() {
		duplicatesRemover.removeDuplicates(listWithDuplicates);
		assertEquals(1, listWithDuplicates.getElementCount(1));
		assertEquals(1, listWithDuplicates.getElementCount(2));
		assertEquals(1, listWithDuplicates.getElementCount(3));
		assertEquals(1, listWithDuplicates.getElementCount(4));
	}
}

The books solution makes a smart use of a Hash Table to keep track of the existing items, with that the solution is way simpler (12 lines length) but additional memory is required. In the book there’s also a solution without a buffer that makes use of two “pointers” to detect duplicates while traversing the list. Quite smart also.

I will be keeping my solutions and the corresponding tests in a Github repository. All criticism is welcome.


The Java Sorting Algorithm Playground

Algorithms and I have a love-hate history. I met them in college in a course in fifth semester, and I was pretty excited about it because it was the first course of the Software Development track of my major. Systems Engineering (that’s what Computing Professionals study in Pery) in my university has a very peculiar curricula, and to start coding you have to first pass several hard and heavy math and science courses. So after two years of suffering with engineering fundamentals I finally get to what I really expect from College education: to learn how to code.

But bad luck is always after me, and I got the worst teacher from the entire faculty. It was and old school guy that teaches algorithms with pseudo-code and diagrams and never –I mean NEVER- showed us a running program or a software demonstration. And also the syllabus of the course was very light and superficial (I don’t remember even a mention of Binary Search Trees). The semester ended, I got a nice grade and I forgot about algorithms for a very long time.

A few years ago my interest for algorithms was renewed when I discovered that all Computer Science dream Jobs –like Google or Facebook- have an algorithm-based interview in their hiring process, so I decided to get ready when the moment comes and start to learn by myself all the topics that I was supposed to learn at college. I did a light forum-research for recommendations of good algorithm books and started my training with Skienna and his Algorithm Design Manual. It’s a very theoretical book and while reading I needed a lot of Wikipedia searching to get some notions. Reading was hard and slow –but very instructive- and the coding part was written all in C, a Programming Language that I’m not very familiar with (I know, shame on me!). So learning algorithm concepts was hard and getting C syntax made it harder, so I decided to get a Java-Based Algorithm Book and speed up my learning process.

The selected book was Data Structures and Algorithms in Java by Robert Lafore and was more beginner-friendly than the academically-oriented Skienna book. Reading was lots of fun, until I found code like this:

// insertSort.java
// demonstrates insertion sort
// to run this program: C>java InsertSortApp
//--------------------------------------------------------------
class ArrayIns
	{
	private long[] a; // ref to array a
	private int nElems; // number of data items
	//--------------------------------------------------------------
	public ArrayIns(int max) // constructor
		{
		a = new long[max]; // create the array
		nElems = 0; // no items yet
		}
	//--------------------------------------------------------------
	public void insert(long value) // put element into array
		{
		a[nElems] = value; // insert it
		nElems++; // increment size
		}
	//--------------------------------------------------------------
	public void display() // displays array contents
		{
		for(int j=0; j<nElems; j++) // for each element,
		System.out.print(a[j] + “ “); // display it
		System.out.println(“”);
		}
	//--------------------------------------------------------------
	public void insertionSort()
		{
		int in, out;
		for(out=1; out<nElems; out++) // out is dividing line
			{
			long temp = a[out]; // remove marked item
			in = out; // start shifts at out
			while(in>0 && a[in-1] >= temp) // until one is smaller,
				{
				a[in] = a[in-1]; // shift item to right
				--in; // go left one position
				}
			a[in] = temp; // insert marked item
			} // end for
		} // end insertionSort()
	//--------------------------------------------------------------
} // end class ArrayIns

That code violated almost all the coding conventions that Sun established and that almost every Java Programmer in the world know. Just to mention some of them:

  • The method-separator comment lines are a really weird convention .
  • There are several patterns for bracket usage (or not using them when they should) and indentation.
  • All the variables/attributes had non descriptive names like “a”, “temp”, “in” and “out”.

Maybe I’m just been too picky, but I think those issues -at least for me – really make the code less readable and more hard to understand. And it’s not a problem only in Lafore book, many other books that I consulted have the same problem: Coding style that doesn’t follow industry-accepted practices. So when I got the assignment in my Algorithm Course to write a Sorting Algorithm Demonstration program I decided the improve the way Java algorithms are presented and rewrite them in a more Convention-Based way, that’s also a more less intimidating way of presenting algorithms to the students (like myself). And that project is now finished and available to everyone interested in my Github account.

For example, let’s see now Insertion Sort:

package pe.edu.pucp.algorithms.sorting.algs.impl;

import pe.edu.pucp.algorithms.sorting.algs.BaseSorter;

/**
 * Implementation of Insertion Sort algorithm. Based on the implementation
 * described in Robert Sedgewick's Algorithm book.
 * 
 * @author Carlos Gavidia (cgavidia@acm.org)
 * 
 * @param <T>
 *            Type of the array to be sorted
 */
public class InsertionSorter<T extends Comparable<T>> extends BaseSorter<T> {

    public InsertionSorter(Class<T> clazz, T[] data) {
        super(clazz, data);
    }

    /*
     * (non-Javadoc)
     * 
     * @see pe.edu.pucp.algorithms.sorting.algs.BaseSorter#sortData()
     */
    @Override
    public void sortData() {
        for (int currentIndex = 0; currentIndex < getLength(); currentIndex++) {
            T currentItem = getDataAtIndex(currentIndex);
            int auxIndex = currentIndex;
            while (auxIndex > 0
                    && getDataAtIndex(auxIndex - 1).compareTo(currentItem) >= 0) {
                setDataAtIndex(auxIndex, getDataAtIndex(auxIndex - 1));
                --auxIndex;
            }
            setDataAtIndex(auxIndex, currentItem);
        }
    }

}

I got some ideas from the Sedgewick book to build an Algorithm Framework that allow the sorting of any Type –that implement Comparable- and to extract the common logic to a Base Class to get the Algorithm Class the cleaner possible, with the only responsibility of implementing the algorithm logic. Also, the access to the array to sort is encapsulated by some methods to makes easier the Observer Pattern implementation required to implement the Sorting process animation. And that animation looks like this (captions in Spanish):

Algorithm Demo

Top-Down merge while executing

As professor requests, I included in the program implementations of Bubble Sort, Merge Sort, Insertion Sort, Quick Sort and some bonus algorithms like Several Unique Sort and Odd-Even Transposition (as you can see in the SortingAlgorithm enumeration). Building the software required a lot of time but I entertained myself doing it, and I really hope that the code can help some other Algorithm Expert wannabe to learn sorting algorithms a little faster (and easier).