文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Ant algorithms Review and future applications
侵权投诉

Ant algorithms Review and future applications

A search for a robust optimization methodology for addressing dynamic problems in business and engineering has been in research for the past decade. One such tool in the array of algorithms is the Ant algorithms, inspired by the behavior of the real ants.

scratch [5]. But the condition is that the ant algorithms should have learnt the problem structure to solve so that it can adopt itself to find new solutions similar to the real ant’s obstacle overcoming nature. It claims that due to this,“ Ant algorithms are ideal for solving problems in the rapidly changing world businesses face today ”[5].

This paper describes significant developments and application of the ant algorithms to solve complex optimization problems. The paper is organized as follows. Section 2 describes ant algorithms and the nature of problems that can be solved by using them. Section 3 gives a detailed description of the various practical applications that can be solved by the implementation of ant algorithms followed by a concluding section.

2. Ant Algorithms

The ant algorithms are basically a colony of artificial ants or cooperative agents, designed to solve a particular problem. They are a class of heuristics based search algorithms used to solve many combinatorial optimization problems. These algorithms are probabilistic in nature because they avoid the local minima entrapment and provide very good solutions close to the natural solution. They are inspired by the co-operative behavior exhibited by the real ants in performing various day-to-day activities such as brooding and foraging. Individual real ants are incapable of performing a structured task but an ant colony has great potential to carry out a coordinative activity. The ants’ main medium of communication is through the building up of the path through an artificial chemical substance called ‘pheromone’. This method of indirect communication is referred to as ‘stigmergy’ [6]. Whenever an ant leaves their nest to search for food, they lay a trail of pheromone on their path. The number of ants that has traveled on the path determines the strength of the pheromone trail. The ant, which travels the shortest path, reinforces the path with more amount of pheromone, which aids others to follow. After an initial randomization the ants finally arrive at a shortest path. This behavior is known as ‘auto catalytic’ behavior or the positive feedback mechanism in which reinforcement of the previously most followed route, is more desirable for future search [7]. The famous double bridge experiment by Goss et al. [6] gives a probabilistic model for this type of foraging behavior of ants. The probability with which that the n+1th ant chooses the upper path (PU (n)) or the lower path (PL (n)) in the bridge is given by the function as given below, where n is the number of ants. The parameters h and k are used to match the model represented with the experimental data. This model is used as the basis for the simulation of ants over a given problem domain.

hUn+k (1)P(n)=U

(2)PL (n) + PU (n) = 1

Inspired by this probabilistic behavior of the real ants, ant algorithms are the software agents that coordinate by updating the information of a common memory similar to the pheromone trail of the real ants. When a large number of these simple artificial agents coordinate based on the memory updation they are able to build good solutions to hard combinatorial optimization problems. Similar to the pheromones, which had a rate of evaporation, the unwanted or the poor quality solution is removed from the solution space. Thus a collective memory is formed which allows the artificial ants to find good solutions in short period of time. In case of dynamic problems, the artificial ants adapt rapidly to the new problem and provide good solutions. The constructive solution building procedure is also driven by problem data and the heuristic function, which is formulated to identify and evaluate further solution space and steps.

Figure 1 represents a generalized flow chart of the ant algorithms. The problem is defined in the form of a network or a graph. All possible links between the components of the network and limiting criteria’s are identified. The distance between the nodes and an initial amount of pheromone deposition on the nodes are given as the input to the system. Based on the given constraints the possible feasible solutions are identified and a potential search list is created. This creates the initial solution phase of the system. Once this is created, number of artificial ant agents walk through the neighborhood of the solution to find the optimal solution. When the artificial ant agents travel from one node to another the memory is updated based on the goodness of the solution. The iteration continues until the best solution is obtained based on the terminating conditions specified. In most cases the minimization of the objective function is the goal and the terminating condition is either the number of iterations or the computation time of the problem.

The artificial ant agents have many properties that differentiate them from the real ants and thus evolve different ant algorithms based systems [8]. Along with these unique features that enhances the capabilities of the artificial agents there are other governing parameters such as the optimum number of ants, the pheromone decay rate, and the Un+k+Ln+k

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email