East West University Department of Computer Science and Engineering Course Title: Advanced Artificial Intelligence Course Code: CSE 532 Assignment 1 Section 1 Course Teacher: Dr. M. Ameer Ali Q1. Write a research article for ANT COLONY OPTIMIZATION. Name:A. K. M Abdul Halim ID:2009-2-96-010 Contents: 1. Abstract 2. Introduction 3. Existing Literature Survey 4. Analysis of the Existing Algorithms 5. Conclusions 6. References Abstract Ants: Small animals (insects) that live in colonies in/on the ground. With this real life definition, ant colony optimization is an optimization method in which imaginary agents are used.
Daemon Actions: These are the actions that can be taken to centralize the solution. The aim of Daemon Actions is to prevent quick convergence of the algorithm. Decentralized Control: A term which is related to robustness and flexibility. Robust systems are desired because of their ability to continue to function in the event of breakdown of one of their components (Dreo et al. , 2006). Dense Heterarchy: A term which is taken from biology and represents the organization of ant colonies. It is different from the managerial term hierarchy.
In dense heterarchy, the structure is horizontal, contrary to hierarchy Pheromone: In real life, pheromone refers to the chemical material that an ant spreads over the path it goes and the level of it changes over time by evaporating. On the other hand, in ant colony optimization, pheromone is a parameter. The amount of this parameter determines the intensity of the trail. The intensity of the trail can be viewed as a global memory of the system (Dreo et al. , 2006). Introduction In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails.
If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food. Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate.
Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. The original idea comes from observing the exploitation of food resources among ants, in which ants’ individually limited cognitive abilities have collectively been able to find the shortest path between a food source and the nest. The first ant finds the food source (F), via any way (a), then returns to the nest (N), leaving behind a trail pheromone (b)Ants indiscriminately follow four possible ways, but the strengthening of the runway makes it more attractive as the shortest route.
Ants take the shortest route, long portions of other ways lose their trail pheromones. In a series of experiments on a colony of ants with a choice between two unequal length paths leading to a source of food, biologists have observed that ants tended to use the shortest route. A model explaining this behaviour is as follows: An ant (called “blitz”) runs more or less at random around the colony; If it discovers a food source, it returns more r less directly to the nest, leaving in its path a trail of pheromone; These pheromones are attractive, nearby ants will be inclined to follow, more or less directly, the track; Returning to the colony, these ants will strengthen the route; If two routes are possible to reach the same food source, the shorter one will be, in the same time, traveled by more ants than the long route will; The short route will be increasingly enhanced, and therefore become more attractive; The long route will eventually disappear, pheromones are volatile; Eventually, all the ants have determined and therefore “chosen” the shortest route.
Existing Literature Survey The easiest way to understand how ant colony optimization works is by means of an example. We consider its application to the traveling salesman problem (TSP). In the TSP a set of locations (cities) and the distances between them are given. The problem consists of finding a closed tour of minimal length that visits each city once and only once. To apply ACO to the TSP, we consider the graph defined by associating the set of cities with the set of vertices of the graph. This graph is called construction graph.
Since in the TSP it is possible to move from any given city to any other city, the construction graph is fully connected and the number of vertices is equal to the number of cities. We set the lengths of the edges between the vertices to be proportional to the distances between the cities represented by these vertices and we associate pheromone values and heuristic values with the edges of the graph. Pheromone values are modified at runtime and represent the cumulated experience of the ant colony, while heuristic values are problem dependent values that, in the case of the TSP, are set to be the inverse of the lengths of the edges.
The ants construct the solutions as follows. Each ant starts from a randomly selected city (vertex of the construction graph). Then, at each construction step it moves along the edges of the graph. Each ant keeps a memory of its path, and in subsequent steps it chooses among the edges that do not lead to vertices that it has already visited. An ant has constructed a solution once it has visited all the vertices of the graph. At each construction step, an ant probabilistically chooses the edge to follow among those that lead to yet unvisited vertices.
The probabilistic rule is biased by pheromone values and heuristic information: the higher the pheromone and the heuristic value associated to an edge, the higher the probability an ant will choose that particular edge. Once all the ants have completed their tour, the pheromone on the edges is updated. Each of the pheromone values is initially decreased by a certain percentage. Each edge then receives an amount of additional pheromone proportional to the quality of the solutions to which it belongs (there is one solution per ant).
This procedure is repeatedly applied until a termination criterion is satisfied. The first step for the application of ACO to a combinatorial optimization problem (COP) consists in defining a model of the COP as a triplet [pic], where: [pic] is a search space defined over a finite set of discrete decision variables; [pic] is a set of constraints among the variables; and [pic] is an objective function to be minimized (as maximizing over [pic] is the same as minimizing over [pic], every COP can be described as a minimization problem).
The search space [pic] is defined as follows. A set of discrete variables [pic], [pic], with values [pic], is given. Elements of [pic] are full assignments, that is, assignments in which each variable [pic] has a value [pic] assigned from its domain [pic]. The set of feasible solutions [pic] is given by the elements of [pic] that satisfy all the constraints in the set [pic]. A solution [pic] is called a global optimum if and only if: [pic]. The set of all globally optimal solutions is denoted by [pic]. Solving a COP requires finding at least one [pic].
Analysis of the Existing Algorithms In ACO, artificial ants build a solution to a combinatorial optimization problem by traversing a fully connected construction graph, defined as follows. First, each instantiated decision variable [pic] is called a solution component and denoted by [pic]. The set of all possible solution components is denoted by [pic]. Then the construction graph GC(V,E) is defined by associating the components C either with the set of vertices V or with the set of edges E. A pheromone trail value [pic] is associated with each component [pic]. Note that pheromone values are in general a function of the algorithm’s iteration [pic]. ) Pheromone values allow the probability distribution of different components of the solution to be modelled. Pheromone values are used and updated by the ACO algorithm during the search. The ants move from vertex to vertex along the edges of the construction graph exploiting information provided by the pheromone values and in this way incrementally building a solution. Additionally, the ants deposit a certain amount of pheromone on the components, that is, either on the vertices or on the edges that they traverse.
The amount [pic] of pheromone deposited may depend on the quality of the solution found. Subsequent ants utilize the pheromone information as a guide towards more promising regions of the search space. The ACO metaheuristic is: Set parameters, initialize pheromone trails SCHEDULE_ACTIVITIES ConstructAntSolutions DaemonActions {optional} UpdatePheromones END_SCHEDULE_ACTIVITIES The metaheuristic consists of an initialization step and of three algorithmic components whose activation is regulated by the Schedule_Activities construct. This construct is repeated until a termination criterion is met.
Typical criteria are a maximum number of iterations or a maximum CPU time. The Schedule_Activities construct does not specify how the three algorithmic components are scheduled and synchronized. In most applications of ACO to NP-hard problems however, the three algorithmic components undergo a loop that consists in (i) the construction of solutions by all ants, (ii) the (optional) improvement of these solution via the use of a local search algorithm, and (iii) the update of the pheromones. These three components are now explained in more details. ConstructAntSolutions
A set of [pic] artificial ants construct solutions from elements of a finite set of available solution components [pic], [pic], [pic]. A solution construction starts with an empty partial solution [pic]. Then, at each construction step, the current partial solution [pic] is extended by adding a feasible solution component from the set of feasible neighbors [pic]. The process of constructing solutions can be regarded as a path on the construction graph GC(V,E). The allowed paths in GC are implicitly defined by the solution construction mechanism that defines the set [pic] with respect to a partial solution [pic].
The choice of a solution component from [pic] is done probabilistically at each construction step. The exact rules for the probabilistic choice of solution components vary across different ACO variants. The best known rule is the one of ant system (AS) (Dorigo et al. 1991, 1996): [pic] where [pic] and [pic] are respectively the pheromone value and the heuristic value associated with the component [pic]. Furthermore, [pic] and [pic] are positive real parameters whose values determine the relative importance of pheromone versus heuristic information. edit] DaemonActions Once solutions have been constructed, and before updating the pheromone values, often some problem specific actions may be required. These are often called daemon actions, and can be used to implement problem specific and/or centralized actions, which cannot be performed by single ants. The most used daemon action consists in the application of local search to the constructed solutions: the locally optimized solutions are then used to decide which pheromone values to update. [edit] UpdatePheromones
The aim of the pheromone update is to increase the pheromone values associated with good solutions, and to decrease those that are associated with bad ones. Usually, this is achieved (i) by decreasing all the pheromone values through pheromone evaporation, and (ii) by increasing the pheromone levels associated with a chosen set of good solutions [pic]: [pic] where [pic] is the set of solutions that are used for the update, [pic] is a parameter called evaporation rate, and [pic] is a function such that [pic]. [pic] is commonly called the fitness function.
Pheromone evaporation implements a useful form of forgetting, favoring the exploration of new areas in the search space. Different ACO algorithms, for example ant colony system (ACS) (Dorigo & Gambardella 1997) or MAX-MIN ant system (MMAS) (Stutzle & Hoos 2000), differ in the way they update the pheromone. Instantiations of the update rule given above are obtained by different specifications of [pic], which in many cases is a subset of [pic], where [pic] is the set of solutions that were constructed in the current iteration, and [pic] is the best-so-far solution, that is, the best solution found since the first algorithm iteration.
A well-known example is the AS-update rule, that is, the update rule of ant system (Dorigo et al. 1991, 1996): [pic] An example of a pheromone update rule that is more often used in practice is the IB-update rule (where IB stands for iteration-best): [pic] The IB-update rule introduces a much stronger bias towards the good solutions found than the AS-update rule. Although this increases the speed with which good solutions are found, it also increases the probability of premature convergence. An even stronger bias is introduced by the BS-update rule, where BS refers to the use of the best-so-far solution [pic].
In this case, [pic] is set to [pic]. In practice, ACO algorithms that use variations of the IB-update or the BS-update rules and that additionally include mechanisms to avoid premature convergence, achieve better results than those that use the AS-update rule. Main ACO Algorithms Several special cases of the ACO metaheuristic have been proposed in the literature. Here we briefly overview, in the historical order in which they were introduced, the three most successful ones: ant system (Dorigo 1992, Dorigo et al. 991, 1996), ant colony system (ACS) (Dorigo & Gambardella 1997), and MAX-MIN ant system (MMAS) (Stutzle & Hoos 2000). In order to illustrate the differences between them clearly, we use the example of the traveling salesman problem. [edit] Ant System Ant system (AS) was the first ACO algorithm to be proposed in the literature (Dorigo et al. 1991, Dorigo 1992, Dorigo et al. 1996). Its main characteristic is that the pheromone values are updated by allthe ants that have completed the tour.
Solution components [pic] are the edges of the graph, and the pheromone update for [pic], that is, for the pheromone associated to the edge joining cities [pic] and [pic], is performed as follows: [pic] where [pic] is the evaporation rate, [pic] is the number of ants, and [pic] is the quantity of pheromone laid on edge [pic] by the [pic]-th ant: [pic] where [pic] is the tour length of the [pic]-th ant. When constructing the solutions, the ants in AS traverse the construction graph and make a probabilistic decision at each vertex.
The transition probability [pic] of the [pic]-th ant moving from city [pic]to city [pic] is given by: [pic] where [pic] is the set of components that do not belong yet to the partial solution [pic] of ant [pic], and [pic] and [pic] are parameters that control the relative importance of the pheromone versus the heuristic information [pic], where [pic] is the length of component [pic] (i. e. , of edge [pic]). [edit] Ant Colony System The first major improvement over the original ant system to be proposed was ant colony system (ACS), introduced by Dorigo and Gambardella (1997).
The first important difference between ACS and AS is the form of the decision rule used by the ants during the construction process. Ants in ACS use the so-called pseudorandom proportional rule: the probability for an ant to move from city [pic] to city [pic]depends on a random variable [pic] uniformly distributed over [pic], and a parameter [pic]; if [pic], then, among the feasible components, the component that maximizes the product [pic] is chosen, otherwise the same equation as in AS is used.
This rather greedy rule, which favors exploitation of the pheromone information, is counterbalanced by the introduction of a diversifying component: the local pheromone update. The local pheromone update is performed by all ants after each construction step. Each ant applies it only to the last edge traversed: [pic] where [pic] is the pheromone decay coefficient, and [pic] is the initial value of the pheromone. The main goal of the local update is to diversify the search performed by subsequent ants during one iteration.
In fact, decreasing the pheromone concentration on the edges as they are traversed during one iteration encourages subsequent ants to choose other edges and hence to produce different solutions. This makes less likely that several ants produce identical solutions during one iteration. Additionally, because of the local pheromone update in ACS, the minimum values of the pheromone are limited. As in AS, also in ACS at the end of the construction process a pheromone update, called offline pheromone update, is performed.
ACS offline pheromone update is performed only by the best ant, that is, only edges that were visited by the best ant are updated, according to the equation: [pic] where [pic] if the best ant used edge [pic] in its tour, [pic] otherwise ([pic] can be set to either the length of the best tour found in the current iteration—iteration-best, [pic]—or the best solution found since the start of the algorithm—best-so-far, [pic]). It should be noted that most of the innovations introduced by ACS were introduced first in Ant-Q, a preliminary version of ACS by the same authors.
MAX-MIN Ant System MAX-MIN ant system (MMAS) is another improvement, proposed by Stutzle and Hoos (2000), over the original ant system idea. MMAS differs from AS in that (i) only the best ant adds pheromone trails, and (ii) the minimum and maximum values of the pheromone are explicitly limited (in AS and ACS these values are limited implicitly, that is, the value of the limits is a result of the algorithm working rather than a value set explicitly by the algorithm designer). The pheromone update equation takes the following form: pic] where [pic] if the best ant used edge [pic] in its tour, [pic] otherwise, where [pic] is the length of the tour of the best ant. As in ACS, [pic] may be set (subject to the algorithm designer decision) either to [pic] or to [pic], or to a combination of both. The pheromone values are constrained between [pic] and [pic] by verifying, after they have been updated by the ants, that all pheromone values are within the imposed limits: [pic] is set to [pic] if [pic] and to [pic] if [pic].
It is important to note that the pheromone update equation of MMAS is applied, as it is the case for AS, to all the edges while in ACS it is applied only to the edges visited by the best ants. The minimum value [pic] is most often experimentally chosen (however, some theory about how to define its value analytically has been developed in (Stutzle & Hoos 2000)). The maximum value [pic] may be calculated analytically provided that the optimum ant tour length is known. In the case of the TSP, [pic], where [pic] is the length of the optimal tour.
If [pic] is not known, it can be approximated by [pic]. It is also important to note that the initial value of the trails is set to [pic], and that the algorithm is restarted when no improvement can be observed for a given number of iterations. Conclusions The initial applications of ACO were in the domain of NP-hard combinatorial optimization problems. The largest body of ACO research is still, not surprisingly, to be found in this area. The interested reader will find a rather complete overview of these applications in (Dorigo & Stutzle 2004).
Another application that was considered early in the history of ACO is routing in telecommunication networks. A particularly successful example of ACO algorithm in this domain is AntNet (Di Caro & Dorigo 1998). Current research in ACO algorithms is devoted both to the development of theoretical foundations and to the application of the metaheuristic to new challenging problems. The development of theoretical foundation was started by Gutjahr, who was the first to prove convergence in probability of an ACO algorithm (Gutjahr 2000).
An overview of theoretical results available for ACO can be found in (Dorigo & Blum 2005). Concerning applications, the use of ACO for the solution of dynamic, multiobjective, stochastic, continuous and mixed-variable optimization problems is a current hot topic, as well as the creation of parallel implementations capable of taking advantage of the new available parallel hardware. Many papers reporting on current research can be found in the proceedings of the ANTS conference or in the Swarm Intelligence journal References J. -L.
Deneubourg, S. Aron, S. Goss, and J. M. Pasteels. The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behavior, 3:159–168, 1990. G. Di Caro and M. Dorigo. AntNet: Distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research, 9:317–365, 1998. M. Dorigo. Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, 1992. M. Dorigo and C. Blum. Ant colony optimization theory: A survey.
Theoretical Computer Science, 344(2–3):243–278, 2005. M. Dorigo and L. M. Gambardella. Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997. M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, 1991. M. Dorigo, V. Maniezzo, and A. Colorni. Ant System: Optimization by a colony of cooperating agents.
IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26(1):29–41, 1996. M. Dorigo and T. Stutzle. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004. S. Goss, S. Aron, J. -L. Deneubourg, and J. M. Pasteels. Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 76:579–581, 1989. W. J. Gutjahr. A Graph-based Ant System and its convergence. Future Generation Computer Systems, 16(8):873–888, 2000. T. Stutzle and H. H. Hoos. MAX–MIN Ant System. Future Generation Computer Systems, 16(8):889–914, 2000.
