## 3 Ant Colony Optimization  
Ant-like mobile agents demonstrate their usefulness for solving some combinatorial optimization problems such as the travelling salesman problem [15]. The idea that network control software can use ant-like mobile agents to control communication network was introduced in late 1990s [13, 16]. Today, various control methods based on ant-like mobile agents have been proposed for telecommunication networks [17, 18]. The use of ant-like mobile agents for routing protocol was inspired by the fact that social insects like ants have a remarkable ability to solve complex problems in a distributed way. There is no central command. Individual insects act based on their local information, yet overall coordination is accomplished. Ants communicate with each other through an indirect method called stigmergy. Each ant lays down a special chemical substance in its environment that is read by other ants to identify it as having been at a given location. This feature has often been reproduced in ant-like mobile agent algorithms. However, social insect society also has the ability to recover from individual members' erroneous behaviors or deaths. This ability needs to be included into our artificial ant-like mechanisms. [PERSON] and [PERSON] demonstrated that ant-like agents can successfully solve complex problems and self-organize [19, 20]. For example if there are several routes from the nest of ants to a food source, the ants may find some of them as shown in Figure 2. Every time the ants convey food from the source to the nest, they deposit pheromone so that the newly recruited ants can follow. When the ants deposit pheromone faster than it evaporates, the pheromone starts to accumulate. The more the ants follow a given path, the more the pheromone trail is strengthened. The ants may take the longer path as well as the shorter path. However, over time, the shortest route will accumulate greater pheromone density and it will attract more fellow ants. Such positive feedback works. Therefore, even though the ants find the shortest path later than longer ones, the shortest path eventually dominates. [PERSON], [PERSON], and other biologists, as well as computer scientists naturally derive the engineering application from this observation. Figure 2: Ants take shorter path after initial search phase. For example, consider solving the traveling salesman problem (TSP) using the artificial ant colony approach. Each ant builds a solution by using two types of information locally accessible: (1) problem-specific information, _i.e._, distance among cities, and (2) information added by ants, as pheromone values, during previous iterations of the algorithm. While building a solution, each ant collects information on the problem characteristics and on its own performance, and uses this information to modify the representation of the problem. The modified representation is the new environment shared by all the ants and seen locally by other ants. The representation of the problem is modified in such a way that information contained in past good solutions can be exploited to build new better solutions. This form of indirect communication mediated by the environment is called _stigmergy_, and is typical of social insects [21; 22; 23; 24]. Suppose an ant \(k\) (in \(m\) ants) is at city \(i\), and \(N^{k}\) is the set of \(k\)'s unvisited cities. Then, the ant chooses city \(j\) to visit next in a probabilistic way as follows:  
\[p^{k}\left(i,j\right)=\frac{\left[\tau\left(i,j\right)\right]^{n}\left[\eta \left(i,j\right)\right]^{\beta}}{\sum_{i\in N^{k}}\left[\tau\left(i,l\right) \right]^{n}\left[\eta\left(i,l\right)\right]^{\beta}} \tag{1}\]  
here, \(\eta\left(i,j\right)\) represents the problem-specific information, and in TSP, it is the reciprocal of the distance between two cities \(i\) and \(j\). \(\alpha\) and \(\beta\) are non-negative constants, and their values are determined by whether one attaches importance to global information or local information.