Ant Colony Optimization (ACO) are algorithms inspired by the behavior of ants and defined mathematically, simulated and applied for combinatorial optimization. We mentioned about Ant Colony Optimization in DNA Computing and Modeling of Neurons, Artificial Immune System (AIS) and in the article on Mind, Theory of Mind and Computing.

Basics of Ant Colony Optimization

Ant Colony Optimization was initially proposed by Marco Dorigo et al. during 1990s, for the search for optimal paths in a graphical format, first the algorithm was inspired by the behavior of ants seeking a path between their colony and a source of food. The original idea has been diversified to solve a wider class of problems and several algorithms has been emerged, drawing on various aspects of the behavior of ants.

The model of Ant Colony Optimization is :

1. Ant runs more or less at random environment around the colony.
2. If it discovers a source of food, it returns more or less directly to the ‘home’, leaving a trail of pheromones, a kind of hormones that can be traced by them.
3. These pheromones are attractive, nearby ants passing will tend to follow the track.
4. Returning to the ‘home’, these ants will strengthen the path.
5. If two paths are possible to reach the same source of food, they will take the shortest track.
6. The short track will be increasingly enhanced.
7. The longer track will eventually will disappear as pheromones are volatile.
8. Eventually all the ants will take the shortest track.

Ant Colony Optimization and Artificial Intelligence

Ant Colony Optimization can be used in Artificial intelligence for network load balancing, for example an article submitted by Lawrence Botley :

// returns the next Node of the path
 public int ProbablePath(ArrayList VisitedNodes)
{
// create a random generator
 Random r = new Random(Global.Seed);

 double val=0;
 double count = 0;
 double Lastcount = -1;

 ArrayList tempTEVector=new ArrayList();

// loop through all the connected nodes
 for(int i=0;i<tableEntry.Length;i++)
 {
// has the node been visitied?
 bool v=false;

//loop through all the visited nodes
 for(int j=0;j<VisitedNodes.Count;j++)
 {
 // if the ID's match then this node has alrady been visited
 if(tableEntry[i].NodeID==(int)VisitedNodes[j])
 v=true;
 }

// If v is false then the node hasnt been visited.. so Add
 if(!v) 
 {
 // get the node
 Node n = Global.Nodes[tableEntry[i].NodeID];

// if the node is accepting connections
 if(!n.FullCapacity)
 {
// add the node as a possible candidate
 tempTEVector.Add(tableEntry[i]);
 }
 }
 }

// if all connections have been visited
 if(tempTEVector.Count==0)
 {
// loop through all the connected nodes
 for(int i=0;i<tableEntry.Length;i++)
 tempTEVector.Add(tableEntry[i]);
 }

// get the ceiling amount for probabilities
 for(int i=0;i<tempTEVector.Count;i++)
 val+= ((TableEntry)tempTEVector[i]).Probablilty;

//create randon value
 val = r.NextDouble()*val;

// loop through the temp Table Entryies
 for(int i=0;i<tempTEVector.Count;i++)
 {
// increment the count on each loop
 count += ((TableEntry)tempTEVector[i]).Probablilty;

// if the random value falls into delegated range
// then select that path as the next node
 if(val>Lastcount && val < count)
 return ((TableEntry)tempTEVector[i]).NodeID;

// get the value of the last count
 Lastcount=count;
 }

// method should never return here
 return -1;
}// returns the next Node of the path
 public int ProbablePath(ArrayList VisitedNodes)
{
// create a random generator
 Random r = new Random(Global.Seed);

 double val=0;
 double count = 0;
 double Lastcount = -1;

 ArrayList tempTEVector=new ArrayList();

// loop through all the connected nodes
 for(int i=0;i<tableEntry.Length;i++)
 {
// has the node been visitied?
 bool v=false;

//loop through all the visited nodes
 for(int j=0;j<VisitedNodes.Count;j++)
 {
// if the ID's match then this node has already been visited
 if(tableEntry[i].NodeID==(int)VisitedNodes[j])
 v=true;
 }

// If v is false then the node hasnt been visited.. so Add
 if(!v) 
 {
// get the node
 Node n = Global.Nodes[tableEntry[i].NodeID];

 // if the node is accepting connections
 if(!n.FullCapacity)
 {
// add the node as a possible candidate
 tempTEVector.Add(tableEntry[i]);
 }
 }
 }

// if all connections have been visited
 if(tempTEVector.Count==0)
 {
// loop through all the connected nodes
 for(int i=0;i<tableEntry.Length;i++)
 tempTEVector.Add(tableEntry[i]);
 }

// get the ceiling amount for probabilities
 for(int i=0;i<tempTEVector.Count;i++)
 val+= ((TableEntry)tempTEVector[i]).Probablilty;

//create random value
 val = r.NextDouble()*val;

// loop through the temp Table Entries 
for(int i=0;i<tempTEVector.Count;i++)
 {
// increment the count on each loop
 count += ((TableEntry)tempTEVector[i]).Probablilty;

// if the random value falls into delegated range // then select that path as the next node
 if(val>Lastcount && val < count)
 return ((TableEntry)tempTEVector[i]).NodeID;

// get the value of the last count
 Lastcount=count;
 }

// method should never return here
 return -1;
}

You can read the original article here on Artificial intelligence network load balancing using Ant Colony Optimization. Ant Colony Optimization has been applied to solve complex structure analysis like quadratic assignment to the folds of protein molecules. The basic algorithm of Ant Colony Optimization has been adapted to solve dynamic problems.

0saves

Save

If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.