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 :
- Ant runs more or less at random environment around the colony.
- 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.
- These pheromones are attractive, nearby ants passing will tend to follow the track.
- Returning to the ‘home’, these ants will strengthen the path.
- If two paths are possible to reach the same source of food, they will take the shortest track.
- The short track will be increasingly enhanced.
- The longer track will eventually will disappear as pheromones are volatile.
- 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 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | <span style="color: #ff00ff;">// returns the next Node of the path</span> public int ProbablePath(ArrayList VisitedNodes) { <span style="color: #ff00ff;">// create a random generator</span> Random r = new Random(Global.Seed); double val=0; double count = 0; double Lastcount = -1; ArrayList tempTEVector=new ArrayList(); <span style="color: #ff00ff;">// loop through all the connected nodes</span> for(int i=0;i<tableEntry.Length;i++) { <span style="color: #ff00ff;">// has the node been visitied?</span> bool v=false; <span style="color: #ff00ff;">//loop through all the visited nodes</span> 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; } <span style="color: #ff00ff;">// If v is false then the node hasnt been visited.. so Add</span> if(!v) { // get the node Node n = Global.Nodes[tableEntry[i].NodeID]; <span style="color: #ff00ff;">// if the node is accepting connections</span> if(!n.FullCapacity) { <span style="color: #ff00ff;">// add the node as a possible candidate</span> tempTEVector.Add(tableEntry[i]); } } } <span style="color: #ff00ff;">// if all connections have been visited</span> if(tempTEVector.Count==0) { <span style="color: #ff00ff;">// loop through all the connected nodes</span> for(int i=0;i<tableEntry.Length;i++) tempTEVector.Add(tableEntry[i]); } <span style="color: #ff00ff;">// get the ceiling amount for probabilities</span> for(int i=0;i<tempTEVector.Count;i++) val+= ((TableEntry)tempTEVector[i]).Probablilty; <span style="color: #ff00ff;">//create randon value</span> val = r.NextDouble()*val; <span style="color: #ff00ff;">// loop through the temp Table Entryies</span> for(int i=0;i<tempTEVector.Count;i++) { <span style="color: #ff00ff;">// increment the count on each loop</span> count += ((TableEntry)tempTEVector[i]).Probablilty; <span style="color: #ff00ff;">// if the random value falls into delegated range</span> <span style="color: #ff00ff;">// then select that path as the next node</span> if(val>Lastcount && val < count) return ((TableEntry)tempTEVector[i]).NodeID; <span style="color: #ff00ff;">// get the value of the last count</span> Lastcount=count; } <span style="color: #ff00ff;">// method should never return here</span> return -1; }// returns the next Node of the path public int ProbablePath(ArrayList VisitedNodes) { <span style="color: #ff00ff;">// create a random generator</span> Random r = new Random(Global.Seed); double val=0; double count = 0; double Lastcount = -1; ArrayList tempTEVector=new ArrayList(); <span style="color: #ff00ff;">// loop through all the connected nodes</span> for(int i=0;i<tableEntry.Length;i++) { <span style="color: #ff00ff;">// has the node been visitied?</span> bool v=false; <span style="color: #ff00ff;">//loop through all the visited nodes</span> for(int j=0;j<VisitedNodes.Count;j++) { <span style="color: #ff00ff;">// if the ID's match then this node has already been visited</span> if(tableEntry[i].NodeID==(int)VisitedNodes[j]) v=true; } <span style="color: #ff00ff;">// If v is false then the node hasnt been visited.. so Add</span> if(!v) { <span style="color: #ff00ff;">// get the node</span> Node n = Global.Nodes[tableEntry[i].NodeID]; // if the node is accepting connections if(!n.FullCapacity) { <span style="color: #ff00ff;">// add the node as a possible candidate</span> tempTEVector.Add(tableEntry[i]); } } } <span style="color: #ff00ff;">// if all connections have been visited</span> if(tempTEVector.Count==0) { <span style="color: #ff00ff;">// loop through all the connected nodes</span> for(int i=0;i<tableEntry.Length;i++) tempTEVector.Add(tableEntry[i]); } <span style="color: #ff00ff;">// get the ceiling amount for probabilities</span> for(int i=0;i<tempTEVector.Count;i++) val+= ((TableEntry)tempTEVector[i]).Probablilty; <span style="color: #ff00ff;">//create random value</span> val = r.NextDouble()*val; <span style="color: #ff00ff;">// loop through the temp Table Entries</span> for(int i=0;i<tempTEVector.Count;i++) { <span style="color: #ff00ff;">// increment the count on each loop</span> count += ((TableEntry)tempTEVector[i]).Probablilty; <span style="color: #ff00ff;">// if the random value falls into delegated range // then select that path as the next node</span> if(val>Lastcount && val < count) return ((TableEntry)tempTEVector[i]).NodeID; <span style="color: #ff00ff;">// get the value of the last count</span> Lastcount=count; } <span style="color: #ff00ff;">// method should never return here</span> 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.
