Modelling of Swarm Intelligence in Artificial Intelligence - Coursework Example

Modelling of Swarm Intelligence in Artificial Intelligence By: First Last 26 November. Table of Contents Introduction 3 SI in a Natural System 4 Modelling Natural SI into an Artificial System 5 Algorithm Metaheuristic 7 Real World Problem and Ant System 8 Algorithm Evaluation 9 AI Algorithm Applications 9 Conclusion 10 Reference List 10 Introduction Swarm intelligence is a branch of Artificial Intelligence (AI) which is based on the study of the collective intelligent behaviour of individuals or agents from the different decentralized and self-organizing intelligent systems (natural or artificial). These agents interact locally with each other and the environment without being the influence of a central controlling body (Lim, Jain and Dehuri, 2009). Usually, the inspiration for the artificial swarm intelligent systems comes from the natural biological systems. The natural agents’ behaviours are not governed by any central control structure rather they exhibit a local and somewhat random behaviour following simple rules. Yet as a result of this local simple interaction between the agents, an intelligent behaviour emerges at the global level. The agents are unaware of the ultimate global intelligent behaviour that their individual behaviours lead to. One of the nature’s many species that exhibit swarm behaviour are the social insects of which one is the ant. The Ant Colony Optimization (ACO) is an AI approach that models the natural behaviour of ants and embeds the modelled behaviour into artificial ants (artificial agents) (Dorigo, Maniezzo and Colorni, 1991). The artificial ants then collaborate with one another and with the environment. The collaboration leads to an emergent intelligence that helps solve complex practical optimization problems such as train scheduling, finding optimal routes, etc. This essay presents an overview of how ants from the nature deliver swarm intelligence, and how they are used to deliver the swarm intelligence in artificial systems. It also briefs how the derived AI model provides social benefits to humans and systems made for humans. SI in a Natural System The general observation of the ant colonies is that the unsophisticated ants although blind can still jointly find out the shortest path between the food and their nest. Similar to many social insects, ant communicates with each other through volatile chemical substance called pheromone (Ahmed and Glasgow, 2012). The ants can sense the intensity and direction of the pheromones through their antennas. One of the different types of pheromones that the ant leaves behind is the food trail pheromone. Ants searching for food leave behind the food pheromones which the other ants searching for food can use to follow to the food source. The self-organizing behaviour of ants is achieved through the positive and negative feedbacks. The ant that finds the shortest path to the food would be the first to return to the nest. And as it left food pheromones on its way to the nest, the shortest path would be reinforced as the other ants follow the pheromones and leave their pheromones on their way back to the nest. As more food pheromones are dropped along a path, it becomes more attractive for the other food searching ants. The food trail pheromones depict a positive feedback process which demonstrates the self- organizing behaviour of the ants. As the number of ants passing from a route increases, the probability of the route being chosen by ants increases (Chen and Liu, 2011). Figure 1 Ants Making Decisions based on Pheromone amount When the food resource is consumed, the returning ants stop leaving food pheromones on their way to the nest. So the volatile pheromones soon evaporate causing the route to be abandoned by the ants. This behaviour of negative feedback helps the ants adapt to the changes in the environment. For instance, in case a route to the food resource was somehow blocked, the ants will cease to follow the blocked route and start looking for an alternative route. Modelling Natural SI into an Artificial System While modelling the natural swarm intelligence into artificially intelligent systems, the constraints need to be set according to the environment. Consider the case where a long path is traced by ants for a long time and the obstacle blocking the shorter path is somehow removed, the ants would continue following the long route due to the high amount of pheromone present along the long route. Secondly the slow evaporation rate of the pheromone does not allow the ant to forget the paths. Since sub-optimal solutions is a huge concern for AI optimization problems, to avoid such situations the artificial systems set small evaporation timescales. This way the ants can easily forget the bad path choices and converge to an optimal solution. Thus, although the basic principles of ACO metaheuristic are inspired by the natural ant colony, not all the parameters of artificial ants need to be similar to the natural ants. The domain of the natural ant is interpreted for the artificial ant is as follows: Natural Environment Artificial Ant Natural Habitat Graph (nodes and edges) Nest and Food Start and destination nodes Visibility The reciprocal of distance Pheromones Artificial Pheromones Foraging behaviour Pheromone guided walk through graph nodes Table below summarizes the behavioural differences between the natural and artificial ants (Ahmed and Glasgow, 2012). Real Ants Artificial Ants Pheromone is deposited in both directions of the route (to and back) Pheromone is deposited only on the way back once candidate path is evaluated. No memory. Store path they walked to retrace and return. They use length to determine amount of pheromone to deposit when returning. Some ants update the amount of pheromone according to the food resource’s quantity and quality Pheromone amount inversely proportional to path length is deposited on return. Use deposited pheromone in forward to trace back the path when returning. Use path in memory to return. Pheromone evaporates too slowly. Exponential evaporation of pheromone. Have competition with other colonies. No ecological constraints. The most important difference between the natural and artificial ant is the presence of memory which enables the artificial ants to solve complex problems. Through memory the artificial ants are able to evaluate and therefore select the better quality solution from all. Based on the quality of a solution an ant decides the quantity of pheromone to drop on its return journey after it has evaluated the lengths (costs) of all the constructed paths (solutions). Algorithm Metaheuristic Similar to the natural behaviour, the basic idea is to model a problem in terms of a search for an optimal quality path within a weighted graph (construction graph) through the artificial ants that drop pheromones corresponding to the quality of a path. The artificial ant’s behaviour are comparable to the natural ants: 1. The artificial ants reinforce good quality paths by dropping pheromones at nodes of the construction graph. 2. The walk of the artificial ants is based on probabilities that depend on amount of pheromone deposited on a node by other ants. 3. The artificial pheromones decrease at every iteration which simulates the behaviour of the volatile natural pheromone trails. While developing the AI algorithm, the fitness function that determines a candidate optimal solution needs devising. In an ACO algorithm, the fitness function determines the amount of pheromone to deposit on a path and how ants would exploit the better quality components while generating new solutions. In ACO, the fitness function is based on cost minimization of solution i.e. the eventual goal of an artificial ant is to walk through the graph and find those nodes that generate a solution path of shortest length. The basic flow of the algorithm is (Ahmed and Glasgow, 2012): Step 1: Representation of solution space with a graph Step 2: Setting ACO parameters and initializing the pheromone trails. Step 3: Generating solution for each ant’s walk. Step 4: Update intensities of pheromones. Step 5: Start from step 3 and repeat till converge or stopping conditions are met. Real World Problem and Ant System Sometimes there are only certain types of problems that an artificial algorithm based on SI can be applied to. For instance, the ACO algorithm can be applied to problems that can be represented by weight construction graphs. The operation of the ACO algorithm can be demonstrated by how it applies to the optimization problem of the Travelling Salesman Problem (TSP). The goal is to find the shortest tour path for a salesman to travel from his home city to finite customer cities. The constraint is that each city can be visited only once before returning to home city in the end. For this a list of untraversed cities is maintain that each ant reviews at each construction step. In the AS, the initial value of pheromone on each edge is 0 and each ant initially sets out on a randomly selected node (city). Each ant traverses through the construction graph and decides on probability based on pheromone value to move from a node to the next. While constructing a solution, each ant saves the traversed cities in its memory in each of its iteration. Each construction step in the ant’s memory starts from a city and ends one all cities are traversed (Ahmed and Glasgow, 2012). The ant deposits pheromone on all the edges it covered while walking from the starting node to the ending nodes. The amount is inversely proportional to the total distance it took between the two nodes. Amount of pheromone on an edge determines the probability of it being selected by another ant. This helps converge the system. When the solution converges, the shortest path solution has the highest pheromone amount. Algorithm Evaluation The AI algorithms require tuning of its parameters to converge to an optimal solution and deliver the expected swarm intelligence. For instance, in the TSP, two parameters are important in reaching to a solution; the amount of pheromone and the intensity of the pheromone. A low value if pheromone amount is set to 0, the ants pick the closest city and act like a greedy search algorithm. If the pheromone intensity is set to 0, the search becomes biased based on the pheromone deposit from the first tours of ants. Both the situations may not lead to an optimal convergence. On the contrary, a high value of pheromone intensity would also cause biased search for many iterations until enough pheromone values are reduced through evaporation and the deposits can actually contribute towards an optimal solution. The artificial systems have their limitations. For instance, in ACO the optimal solution cannot be reached in cases when there are a large number of edges in the construction graph that can form good paths. Since the good paths are enforced in the algorithm, many paths will become part of the candidate solutions and the convergence will take a lot of time. So in the TSP, if the situation is such that many similar distance paths between two cities exist, the differentiation and selection of an optimal path would take a lot of time. AI Algorithm Applications The AI algorithms based on swarm intelligence have been successfully applied in various systems intended for human welfare. Due to the fact that the ACO algorithm adapts to the changing environment, it finds its application in the combinatorial optimization problems belonging to different fields. The ACO algorithm has found its applications in the fields of: Ecommerce e.g. for devising solution for the scheduling problems (Ponnambalam, Kawahar and Girish, 2010) Data mining e.g. in designing e-learning systems (Sengupta, Sahu and Dasgupta, 2012), Pattern matching (Guo et al. 2009), Operation research for solving assignment problem (Nicolescu 2013) and travelling salesman problem (Rongwei et al. 2010), Genomics (Rekaya et al. 2013), Transportation (Huang, 2011; Claes and Holvoet 2011), Healthcare (Sousa et al. 2012), Image processing (Konstantinidis, Sirakoulis and Andreadis, 2009), Routing in telecommunication networks (Ilham, 2012) Bioinformatics and biomedicine (Das, Abraham and Konar, 2008). Conclusion The various systems of nature are a tremendous source of inspiration and learning. Through observation of the collective behaviour of natural species in their swarms in pursuit of their survival can help humans formulate solutions for their real life problems. In swarm intelligence, an intelligent behaviour emerges through the local interaction of several simple individuals (agents). The trend of adopting AI computational systems based on SI for solving real life problems is constantly increasing as the underlying algorithms are simple, resource efficient and robust. The optimization methodologies (such as ACO) based on SI have an application domain that spreads over different fields. To summarize, SI is an effective field of AI that has been the focus of research for quite some time now and still has room for further research. Reference List Ahmed, H. and Glasgow, J., 2012. Swarm Intelligence: Concepts, Models and Applications. Technical Report 2012-585. School of Computing. Queens University. Available from: http://research.cs.queensu.ca/TechReports/Reports/2012-585.pdf Chen, E. and Liu, X., 2011. Multi-Colony Ant Algorithm. In: Ostfeld, A. ed. 2011. Ant Colony Optimization - Methods and Applications, InTech, DOI: 10.5772/13991. P. 4. Available from: http://www.intechopen.com/books/ant-colony-optimization-methods-and-applications/multi-colony-ant-algorithm Claes, R. and Holvoet, T., 2011. Ant Colony Optimization Applied to Route Planning Using Link Travel Time Predictions. International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, IEEE, 2011, pp. 358 – 365 Das, S., Abraham, A. and Konar, A., 2008. Swarm Intelligence Algorithms in Bioinformatics, Studies in Computational Intelligence. 94, pp. 113–147 Dorigo, M., Maniezzo, V. and Colorni, A., 1991. Positive feedback as a search strategy, Tech. Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy, Available from: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.6342 Guo, Y., Lu, M., Tan, Z., Ren, G. and Liu, S., 2009. Point pattern matching using modified ant colony optimization. SPIE Proceedings, 7496(1), MIPPR 2009: Pattern Recognition and Computer Vision, 74960Y (October 30, 2009); doi:10.1117/12.833054. Huang, M., 2011 A Study on Bus Routing Problem: An Ant Colony Optimization Algorithm Approach. Emerging Research in Artificial Intelligence and Computational Intelligence, Communications in Computer and Information Science, 237, pp 570-575 Ilham, B., 2012. A Survey of Ant Colony Optimization Algorithms for Telecommunication Networks. International Journal of Applied Metaheuristic Computing, 3(2), pp. 18-32. Web. 18 Nov. 2013. doi:10.4018/jamc.2012040102 Konstantinidis, K., Sirakoulis, G. C., and Andreadis, I., 2009. Ant Colony Optimization for Use in Content Based Image Retrieval. In: H. Mo (ed.), Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies, pp. 384-404. Hershey, PA: Medical Information Science Reference. doi:10.4018/978-1-60566-310-4.ch018 Lim, C.P., Jain, L.C. and Dehuri, S., 2009. Innovations in Swarm Intelligence. Springer. P. 1 Nicolescu, L., Galalae, C. and Voicu, A., 2013. Solving a Supply Chain Management Problem to Near Optimality Using Ant Colony Optimization, in an International Context. The AMFITEATRU ECONOMIC journal, Academy of Economic Studies - Bucharest, Romania, 15(33), pp 8-26, February. Ponnambalam, S.G., Jawahar, N. and Girish, B.S., 2010. An Ant Colony Optimization Algorithm for Flexible Job Shop Scheduling Problem, New Advanced Technologies, Lazinica, A. (ed.), ISBN: 978-953-307-067-4, InTech, DOI: 10.5772/9425. Available from: http://www.intechopen.com/books/new-advanced-technologies/an-ant-colony-optimization-algorithm-for-flexible-job-shop-scheduling-problem Rekaya, R., Robbins, K., Spangler, M., Smith, S., Hay, E.H. and Bertrand, K., 2013. Ant Colony Algorithm with Applications in the Field of Genomics, Ant Colony Optimization - Techniques and Applications, Barbosa, H. (ed.), ISBN: 978-953-51-1001-9, InTech, DOI: 10.5772/52051. Available from: http://www.intechopen.com/books/ant-colony-optimization-techniques-and-applications/ant-colony-algorithm-with-applications-in-the-field-of-genomics Rongwei, G., Qingshun, G., Huiyou, C. and Yang, Y., 2010. Improved ant colony optimization algorithm for the traveling salesman problems. Journal of Systems Engineering and Electronics, 21(2), pp.329-333, April 2010 Sengupta, S.; Sahu, S. & Dasgupta, R. (2012), Construction of Learning Path Using Ant Colony Optimization from a Frequent Pattern Graph, CoRR abs/1201.3976 . Sousa M, Lopes W, Madeiro F, Alencar M., 2012. Cognitive LF-Ant: A Novel Protocol for Healthcare Wireless Sensor Networks. Sensors. 12(8), pp.10463-10486. Read More