Ant Colony Algorithm Lecture and Videos

                                                Ant Colony Lecture and Examples Video

Ant Colony Algorithms are inspired by the behaviour of natural ant colonies, in the sense that they solve their problems by multi agent cooperation using indirect communication through modifications in the environment.

Natural, or real, ants release a certain amount of pheromone while walking, and each ant prefers(probabilistically) to follow a direction which is rich of pheromone. This simple behaviour explains why ants are able to adjust to changes in the environment, such as new obstacles interrupting the currently shortest path. Let me illustrate:

What happens when an ant colony following a shortest path between a food source and the nest (see below) gets interrupted by an obstacle appearing somewhere in the path? When the ants reach the obstacle they will randomly choose some way around it(right, left, over or under).

If we assume that the only way around the obstacle is either right or left, we can safely assume that approximately half of the ants will go right and the other half left, as illustrated below.

The ants that happen to pick the shorter path will obviously create a strong trail of pheromone a lot faster than the ones choosing a longer path(see below). This will cause more and more ants to choose the shorter path until eventually all ants have found the shortest path.

Ant Colony Algorithms attempt somehow to apply similar techniques in order to solve real life problems. The main idea is to use repeated and often recurrent simulations of artificial ants (mobile agents inspired by real ant behaviour) to generate new solutions to the problem at hand. 

The ants use information collected during past simulations to direct their search and this information is available and modified through the environment. Many different artificial ant algorithms have been implemented and no universal definition of an artificial ant fits them all.

 In the next section we will take a look at an example where an artificial ant colony solves the travelling salesman problem. 

Click for the next lectures and source

PREMATURE CONVERGENCE IN GENETIC ALGORITHM

GA is a kind of hill-climbing search; more specifically it is very similar to a randomized beam search. As with all hill-climbing algorithms, there is a problem of local maxima. There is no absolute assurance that a genetic algorithm will find a global optimum. It happens very often when the populations have a lot of subjects. Local maxima in a genetic problem are those individuals that get stuck with a pretty good, but not optimal, fitness measure. [7]

When applying genetic algorithm for solving large-scale and complex real-world problems, premature convergence is the one of the most frequently encountered difficulties. In that situation  , the  solving  procedure  is  trapped  in  the suboptimal state and  most  of the operators can’t  produce offspring surpassing their parents any more . It has been proven that the genetic algorithm can't converge to the global optimal solution [8]

Any small mutation gives worse fitness. Fortunately, crossover can help them get out of a local maximum. Also, mutation is a random process, so it is possible that we may have a sudden large mutation to get these individuals out of this situation. (In fact, these individuals never get out. It's their offspring that get out of local maxima.) Overall, GAs have less problems with local maxima than back-propagation neural networks. [9]

Sources:

[7] [9]  C. R. Dyer, CS 540 Lecture Notes, University of Wisconsin – Madison

[8] Rudolph G., 1994, “Convergence Analysis of Canonical Genetic Algorithms”, IEEE Trans.  On Neural Networks, Vo1.5(1), p96-101.