Ant Colony Optimization and Artificial Intelligence

Abhishek Ghosh

By Abhishek Ghosh September 14, 2012 1:13 am Updated on September 14, 2012

Ant Colony Optimization and Artificial Intelligence

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 Colony Optimization and Artificial Intelligence

---

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 :

// 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&lt;tableEntry.Length;i++)
 {
// has the node been visitied?
 bool v=false;

//loop through all the visited nodes
 for(int j=0;j&lt;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&lt;tableEntry.Length;i++)
 tempTEVector.Add(tableEntry[i]);
 }

// get the ceiling amount for probabilities
 for(int i=0;i&lt;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&lt;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&gt;Lastcount &amp;&amp; val &lt; 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&lt;tableEntry.Length;i++)
 {
// has the node been visitied?
 bool v=false;

//loop through all the visited nodes
 for(int j=0;j&lt;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&lt;tableEntry.Length;i++)
 tempTEVector.Add(tableEntry[i]);
 }

// get the ceiling amount for probabilities
 for(int i=0;i&lt;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&lt;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&gt;Lastcount &amp;&amp; val &lt; count)
 return ((TableEntry)tempTEVector[i]).NodeID;

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

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

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

// 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.

Tagged With artificial ant colony

Ant Colony Optimization and Artificial Intelligence

Basics of Ant Colony Optimization

Ant Colony Optimization and Artificial Intelligence

About Abhishek Ghosh

Here’s what we’ve got for you which might like :

Take The Conversation Further ...

Basics of Ant Colony Optimization

Ant Colony Optimization and Artificial Intelligence

About Abhishek Ghosh

Here’s what we’ve got for you which might like :

Articles Related to Ant Colony Optimization and Artificial Intelligence

Take The Conversation Further ...