Pharaon ants inspire an Artificial Intelligence algorithm with applications such as drug search or logistic optimization

CSIC scientists improve an algorithm inspired by the behaviour of these ants. Pharaon ants use pheromones for setting ‘no-entry’ signals, which is an example of learning based on negative feedback. It enables to improve optimization techniques for many sectors, both in industry and in scientific research.

Pharaon ants. WikimediaAnts are known to leave a pheromone trail as they move, allowing the rest of the ant colony to follow the same route. Shorter routes to the nest allow a more frequent passage of ants: consequently, these routes accumulate a greater trace of pheromone and, in this way, receive more positive reinforcement than others. This enables the ant colony to come up with the solution of finding a very short path.

This is an example of ‘swarm intelligence’, resulting from the collective behaviour of animals such as ants, bees or termites, which inspires developments in Artificial Intelligence. As a matter of fact, the ACO technique ("ant colony optimization") is based on the behaviour that enables ants to find short paths, and has applications in logistics, medical research or bioinformatics.

Now, scientists from the Artificial Intelligence Research Institute (IIIA) of the CSIC have improved the ACO technique, inspired by pharaoh ants. Christian Blum, the IIIA scientist who led the work, explains: “The type of learning used in ACO is limited to learning from 'positive examples'. However, learning from negative examples seems to play an important role in self-organizing biological systems”.

Christian Blum continues: “Pharaoh ants (Monomorium pharaonis) use pheromones to display no-entry signals to mark unrewarding feeding paths, leaving therefore a negative trail. Another example is the use of hydrocarbon anti-pheromones produced by male tsetse flies”.

In the research, Christian Blum and the doctoral student Teddy Nurcahyadi have designed the first general mechanism to incorporate negative learning in a way that clearly benefits and improves the ACO technique. The research has been published at the ANTS 2020 congress, one of the main congresses in the area, where it was awarded with Best Paper Award for its great potential for innovation.

Positive and negative learning together

The scientists have modified the ACO algorithm to incorporate learning based on negative examples. “Negative learning can complement positive learning. Yet, positive learning is still more important than the negative one. But in our article we show that,  when the two types of learning are combined, we get as a result a better algorithm.”

Our algorithms are iterative, explains Blum. That means that the same instructions are executed repeatedly over and over again. "Every iteration is as if there were a group of "ants", every one of them generating a possible valid solution to solve the problem”.

In the same way that ants are guided in a probabilistic way by the pheromones that they find on each piece of the path, in the algorithms, the pheromones would be equivalent to numerical values ​​that are assigned to components of possible solutions. Likewise to pheromones, these values ​​are reinforced positively or negatively depending on whether or not they appear in good solutions.

This type of algorithm can be applied to numerous optimization problems in which there are many possible solutions and the aim is to find the best or, at least, one that is “good enough”, says the researcher, as in the case of combining molecules to find new drugs or in logistics. "I would say," says Blum, "that research in many fields would not be possible without proper optimization tools."

The research is carried out within a project of the Spanish research programme “Plan Nacional de I+ D + I”, CI-SUSTAIN: Advanced Computational Intelligence to Achieve Sustainable Development Goals

Reference article:

Teddy Nurcahyadi, Christian Blum. A New Approach for Making Use of Negative Learning in Ant Colony Optimization. Conference paper. ANTS 2020: Swarm Intelligence pp 16-28. https://link.springer.com/chapter/10.1007%2F978-3-030-60376-2_2

 

Mercè Fernandez Via / CSIC Comunicación