You are currently browsing the tag archive for the ‘Ant Systems’ tag.
2016 – Up now, an overall of 1567 citations among 74 works (including 3 books) on GOOGLE SCHOLAR (https://scholar.google.com/citations?user=gSyQ-g8AAAAJ&hl=en) [with an Hirsh h-index=19, and an average of 160.2 citations each for any work on my top five] + 900 citations among 57 works on the new RESEARCH GATE site (https://www.researchgate.net/profile/Vitorino_Ramos).
Refs.: Science, Artificial Intelligence, Swarm Intelligence, Data-Mining, Big-Data, Evolutionary Computation, Complex Systems, Image Analysis, Pattern Recognition, Data Analysis.
Figure – Neural circuit controller of the virtual ant (page 3, fig. 2). [URL: http://arxiv.org/abs/1507.08467 ]
Intelligence and decision in foraging ants. Individual or Collective? Internal or External? What is the right balance between the two. Can one have internal intelligence without external intelligence? Can one take examples from nature to build in silico artificial lives that present us with interesting patterns? We explore a model of foraging ants in this paper that will be presented in early September in Exeter, UK, at UKCI 2015. (available on arXiv [PDF] and ResearchGate)
Cristian Jimenez-Romero, David Sousa-Rodrigues, Jeffrey H. Johnson, Vitorino Ramos; “A Model for Foraging Ants, Controlled by Spiking Neural Networks and Double Pheromones“, UKCI 2015 Computational Intelligence – University of Exeter, UK, September 2015.
Abstract: A model of an Ant System where ants are controlled by a spiking neural circuit and a second order pheromone mechanism in a foraging task is presented. A neural circuit is trained for individual ants and subsequently the ants are exposed to a virtual environment where a swarm of ants performed a resource foraging task. The model comprises an associative and unsupervised learning strategy for the neural circuit of the ant. The neural circuit adapts to the environment by means of classical conditioning. The initially unknown environment includes different types of stimuli representing food (rewarding) and obstacles (harmful) which, when they come in direct contact with the ant, elicit a reflex response in the motor neural system of the ant: moving towards or away from the source of the stimulus. The spiking neural circuits of the ant is trained to identify food and obstacles and move towards the former and avoid the latter. The ants are released on a landscape with multiple food sources where one ant alone would have difficulty harvesting the landscape to maximum efficiency. In this case the introduction of a double pheromone mechanism (positive and negative reinforcement feedback) yields better results than traditional ant colony optimization strategies. Traditional ant systems include mainly a positive reinforcement pheromone. This approach uses a second pheromone that acts as a marker for forbidden paths (negative feedback). This blockade is not permanent and is controlled by the evaporation rate of the pheromones. The combined action of both pheromones acts as a collective stigmergic memory of the swarm, which reduces the search space of the problem. This paper explores how the adaptation and learning abilities observed in biologically inspired cognitive architectures is synergistically enhanced by swarm optimization strategies. The model portraits two forms of artificial intelligent behaviour: at the individual level the spiking neural network is the main controller and at the collective level the pheromone distribution is a map towards the solution emerged by the colony. The presented model is an important pedagogical tool as it is also an easy to use library that allows access to the spiking neural network paradigm from inside a Netlogo—a language used mostly in agent based modelling and experimentation with complex systems.
References:
[1] C. G. Langton, “Studying artificial life with cellular automata,” Physica D: Nonlinear Phenomena, vol. 22, no. 1–3, pp. 120 – 149, 1986, proceedings of the Fifth Annual International Conference. [Online]. Available: http://www.sciencedirect.com/ science/article/pii/016727898690237X
[2] A. Abraham and V. Ramos, “Web usage mining using artificial ant colony clustering and linear genetic programming,” in Proceedings of the Congress on Evolutionary Computation. Australia: IEEE Press, 2003, pp. 1384–1391.
[3] V. Ramos, F. Muge, and P. Pina, “Self-organized data and image retrieval as a consequence of inter-dynamic synergistic relationships in artificial ant colonies,” Hybrid Intelligent Systems, vol. 87, 2002.
[4] V. Ramos and J. J. Merelo, “Self-organized stigmergic document maps: Environment as a mechanism for context learning,” in Proceddings of the AEB, Merida, Spain, February 2002. ´
[5] D. Sousa-Rodrigues and V. Ramos, “Traversing news with ant colony optimisation and negative pheromones,” in European Conference in Complex Systems, Lucca, Italy, Sep 2014.
[6] E. Bonabeau, G. Theraulaz, and M. Dorigo, Swarm Intelligence: From Natural to Artificial Systems, 1st ed., ser. Santa Fe Insitute Studies In The Sciences of Complexity. 198 Madison Avenue, New York: Oxford University Press, USA, Sep. 1999.
[7] M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” Universite Libre de Bruxelles, Tech. Rep. TR/IRIDIA/1996-5, ´ 1996.
[8] M. Dorigo, G. Di Caro, and L. M. Gambardella, “Ant algorithms for discrete optimization,” Artif. Life, vol. 5, no. 2, pp. 137– 172, Apr. 1999. [Online]. Available: http://dx.doi.org/10.1162/ 106454699568728
[9] L. M. Gambardella and M. Dorigo, “Ant-q: A reinforcement learning approach to the travelling salesman problem,” in Proceedings of the ML-95, Twelfth Intern. Conf. on Machine Learning, M. Kaufman, Ed., 1995, pp. 252–260.
[10] A. Gupta, V. Nagarajan, and R. Ravi, “Approximation algorithms for optimal decision trees and adaptive tsp problems,” in Proceedings of the 37th international colloquium conference on Automata, languages and programming, ser. ICALP’10. Berlin, Heidelberg: Springer-Verlag, 2010, pp. 690–701. [Online]. Available: http://dl.acm.org/citation.cfm?id=1880918.1880993
[11] V. Ramos, D. Sousa-Rodrigues, and J. Louçã, “Second order ˜ swarm intelligence,” in HAIS’13. 8th International Conference on Hybrid Artificial Intelligence Systems, ser. Lecture Notes in Computer Science, J.-S. Pan, M. Polycarpou, M. Wozniak, A. Carvalho, ´ H. Quintian, and E. Corchado, Eds. Salamanca, Spain: Springer ´ Berlin Heidelberg, Sep 2013, vol. 8073, pp. 411–420.
[12] W. Maass and C. M. Bishop, Pulsed Neural Networks. Cambridge, Massachusetts: MIT Press, 1998.
[13] E. M. Izhikevich and E. M. Izhikevich, “Simple model of spiking neurons.” IEEE transactions on neural networks / a publication of the IEEE Neural Networks Council, vol. 14, no. 6, pp. 1569–72, 2003. [Online]. Available: http://www.ncbi.nlm.nih. gov/pubmed/18244602
[14] C. Liu and J. Shapiro, “Implementing classical conditioning with spiking neurons,” in Artificial Neural Networks ICANN 2007, ser. Lecture Notes in Computer Science, J. de S, L. Alexandre, W. Duch, and D. Mandic, Eds. Springer Berlin Heidelberg, 2007, vol. 4668, pp. 400–410. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-74690-4 41
[15] J. Haenicke, E. Pamir, and M. P. Nawrot, “A spiking neuronal network model of fast associative learning in the honeybee,” Frontiers in Computational Neuroscience, no. 149, 2012. [Online]. Available: http://www.frontiersin.org/computational neuroscience/10.3389/conf.fncom.2012.55.00149/full
[16] L. I. Helgadottir, J. Haenicke, T. Landgraf, R. Rojas, and M. P. Nawrot, “Conditioned behavior in a robot controlled by a spiking neural network,” in International IEEE/EMBS Conference on Neural Engineering, NER, 2013, pp. 891–894.
[17] A. Cyr and M. Boukadoum, “Classical conditioning in different temporal constraints: an STDP learning rule for robots controlled by spiking neural networks,” pp. 257–272, 2012.
[18] X. Wang, Z. G. Hou, F. Lv, M. Tan, and Y. Wang, “Mobile robots’ modular navigation controller using spiking neural networks,” Neurocomputing, vol. 134, pp. 230–238, 2014.
[19] C. Hausler, M. P. Nawrot, and M. Schmuker, “A spiking neuron classifier network with a deep architecture inspired by the olfactory system of the honeybee,” in 2011 5th International IEEE/EMBS Conference on Neural Engineering, NER 2011, 2011, pp. 198–202.
[20] U. Wilensky, “Netlogo,” Evanston IL, USA, 1999. [Online]. Available: http://ccl.northwestern.edu/netlogo/
[21] C. Jimenez-Romero and J. Johnson, “Accepted abstract: Simulation of agents and robots controlled by spiking neural networks using netlogo,” in International Conference on Brain Engineering and Neuro-computing, Mykonos, Greece, Oct 2015.
[22] W. Gerstner and W. M. Kistler, Spiking Neuron Models: Single Neurons, Populations, Plasticity. Cambridge: Cambridge University Press, 2002.
[23] J. v. H. W Gerstner, R Kempter and H. Wagner, “A neuronal learning rule for sub-millisecond temporal coding,” Nature, vol. 386, pp. 76–78, 1996.
[24] I. P. Pavlov, “Conditioned reflexes: An investigation of the activity of the cerebral cortex,” New York, 1927.
[25] E. J. H. Robinson, D. E. Jackson, M. Holcombe, and F. L. W. Ratnieks, “Insect communication: ‘no entry’ signal in ant foraging,” Nature, vol. 438, no. 7067, pp. 442–442, 11 2005. [Online]. Available: http://dx.doi.org/10.1038/438442a
[26] E. J. Robinson, D. Jackson, M. Holcombe, and F. L. Ratnieks, “No entry signal in ant foraging (hymenoptera: Formicidae): new insights from an agent-based model,” Myrmecological News, vol. 10, no. 120, 2007.
[27] D. Sousa-Rodrigues, J. Louçã, and V. Ramos, “From standard ˜ to second-order swarm intelligence phase-space maps,” in 8th European Conference on Complex Systems, S. Thurner, Ed., Vienna, Austria, Sep 2011.
[28] V. Ramos, D. Sousa-Rodrigues, and J. Louçã, “Spatio-temporal ˜ dynamics on co-evolved stigmergy,” in 8th European Conference on Complex Systems, S. Thurner, Ed., Vienna, Austria, 9 2011.
[29] S. Tisue and U. Wilensky, “Netlogo: A simple environment for modeling complexity,” in International conference on complex systems. Boston, MA, 2004, pp. 16–21.
Figure – Two simplicies a and b connected by the 2-dimensional face, the triangle {1;2;3}. In the analysis of the time-line of The Guardian newspaper (link) the system used feature vectors based on frequency of words and them computed similarity between documents based on those feature vectors. This is a purely statistical approach that requires great computational power and that is difficult for problems that have large feature vectors and many documents. Feature vectors with 100,000 or more items are common and computing similarities between these documents becomes cumbersome. Instead of computing distance (or similarity) matrices between documents from feature vectors, the present approach explores the possibility of inferring the distance between documents from the Q-analysis description. Q-analysis is a very natural notion of connectivity between the simplicies of the structure and in the relation studied, documents are connected to each other through shared sets of tags entered by the journalists. Also in this framework, eccentricity is defined as a measure of the relatedness of one simplex in relation to another [7].
David M.S. Rodrigues and Vitorino Ramos, “Traversing News with Ant Colony Optimisation and Negative Pheromones” [PDF], accepted as preprint for oral presentation at the European Conference on Complex Systems – ECCS‘14 in Lucca, Sept. 22-26, 2014, Italy.
Abstract: The past decade has seen the rapid development of the online newsroom. News published online are the main outlet of news surpassing traditional printed newspapers. This poses challenges to the production and to the consumption of those news. With those many sources of information available it is important to find ways to cluster and organise the documents if one wants to understand this new system. Traditional approaches to the problem of clustering documents usually embed the documents in a suitable similarity space. Previous studies have reported on the impact of the similarity measures used for clustering of textual corpora [1]. These similarity measures usually are calculated for bag of words representations of the documents. This makes the final document-word matrix high dimensional. Feature vectors with more than 10,000 dimensions are common and algorithms have severe problems with the high dimensionality of the data. A novel bio inspired approach to the problem of traversing the news is presented. It finds Hamiltonian cycles over documents published by the newspaper The Guardian. A Second Order Swarm Intelligence algorithm based on Ant Colony Optimisation was developed [2, 3] that uses a negative pheromone to mark unrewarding paths with a “no-entry” signal. This approach follows recent findings of negative pheromone usage in real ants [4].
In this case study the corpus of data is represented as a bipartite relation between documents and keywords entered by the journalists to characterise the news. A new similarity measure between documents is presented based on the Q-analysis description [5, 6, 7] of the simplicial complex formed between documents and keywords. The eccentricity between documents (two simplicies) is then used as a novel measure of similarity between documents. The results prove that the Second Order Swarm Intelligence algorithm performs better in benchmark problems of the travelling salesman problem, with faster convergence and optimal results. The addition of the negative pheromone as a non-entry signal improves the quality of the results. The application of the algorithm to the corpus of news of The Guardian creates a coherent navigation system among the news. This allows the users to navigate the news published during a certain period of time in a semantic sequence instead of a time sequence. This work as broader application as it can be applied to many cases where the data is mapped to bipartite relations (e.g. protein expressions in cells, sentiment analysis, brand awareness in social media, routing problems), as it highlights the connectivity of the underlying complex system.
Keywords: Self-Organization, Stigmergy, Co-Evolution, Swarm Intelligence, Dynamic Optimization, Foraging, Cooperative Learning, Hamiltonian cycles, Text Mining, Textual Corpora, Information Retrieval, Knowledge Discovery, Sentiment Analysis, Q-Analysis, Data Mining, Journalism, The Guardian.
References:
[1] Alexander Strehl, Joydeep Ghosh, and Raymond Mooney. Impact of similarity measures on web-page clustering. In Workshop on Artifcial Intelligence for Web Search (AAAI 2000), pages 58-64, 2000.
[2] David M. S. Rodrigues, Jorge Louçã, and Vitorino Ramos. From standard to second-order Swarm Intelligence phase-space maps. In Stefan Thurner, editor, 8th European Conference on Complex Systems, Vienna, Austria, 9 2011.
[3] Vitorino Ramos, David M. S. Rodrigues, and Jorge Louçã. Second order Swarm Intelligence. In Jeng-Shyang Pan, Marios M. Polycarpou, Micha l Wozniak, André C.P.L.F. Carvalho, Hector Quintian, and Emilio Corchado, editors, HAIS’13. 8th International Conference on Hybrid Artificial Intelligence Systems, volume 8073 of Lecture Notes in Computer Science, pages 411-420. Springer Berlin Heidelberg, Salamanca, Spain, 9 2013.
[4] Elva J.H. Robinson, Duncan Jackson, Mike Holcombe, and Francis L.W. Ratnieks. No entry signal in ant foraging (hymenoptera: Formicidae): new insights from an agent-based model. Myrmecological News, 10(120), 2007.
[5] Ronald Harry Atkin. Mathematical Structure in Human A ffairs. Heinemann Educational Publishers, 48 Charles Street, London, 1 edition, 1974.
[6] J. H. Johnson. A survey of Q-analysis, part 1: The past and present. In Proceedings of the Seminar on Q-analysis and the Social Sciences, Universty of Leeds, 9 1983.
[7] David M. S. Rodrigues. Identifying news clusters using Q-analysis and modularity. In Albert Diaz-Guilera, Alex Arenas, and Alvaro Corral, editors, Proceedings of the European Conference on Complex Systems 2013, Barcelona, 9 2013.
In order to solve hard combinatorial optimization problems (e.g. optimally scheduling students and teachers along a week plan on several different classes and classrooms), one way is to computationally mimic how ants forage the vicinity of their habitats searching for food. On a myriad of endless possibilities to find the optimal route (minimizing the travel distance), ants, collectively emerge the solution by using stigmergic signal traces, or pheromones, which also dynamically change under evaporation.
Current algorithms, however, make only use of a positive feedback type of pheromone along their search, that is, if they collectively visit a good low-distance route (a minimal pseudo-solution to the problem) they tend to reinforce that signal, for their colleagues. Nothing wrong with that, on the contrary, but no one knows however if a lower-distance alternative route is there also, just at the corner. On his global search endeavour, like a snowballing effect, positive feedbacks tend up to give credit to the exploitation of solutions but not on the – also useful – exploration side. The upcoming potential solutions can thus get crystallized, and freeze, while a small change on some parts of the whole route, could on the other-hand successfully increase the global result.
Figure – Influence of negative pheromone on kroA100.tsp problem (fig.1 – page 6) (values on lines represent 1-ALPHA). A typical standard ACS (Ant Colony System) is represented here by the line with value 0.0, while better results could be found by our approach, when using positive feedbacks (0.95) along with negative feedbacks (0.05). Not only we obtain better results, as we found them earlier.
There is, however, an advantage when a second type of pheromone (a negative feedback one) co-evolves with the first type. And we decided to research for his impact. What we found out, is that by using a second type of global feedback, we can indeed increase a faster search while achieving better results. In a way, it’s like using two different types of evaporative traffic lights, in green and red, co-evolving together. And as a conclusion, we should indeed use a negative no-entry signal pheromone. In small amounts (0.05), but use it. Not only this prevents the whole system to freeze on some solutions, to soon, as it enhances a better compromise on the search space of potential routes. The pre-print article is available here at arXiv. Follows the abstract and keywords:
Vitorino Ramos, David M. S. Rodrigues, Jorge Louçã, “Second Order Swarm Intelligence” [PDF], in Hybrid Artificial Intelligent Systems, Lecture Notes in Computer Science, Springer-Verlag, Volume 8073, pp. 411-420, 2013.
Abstract: An artificial Ant Colony System (ACS) algorithm to solve general purpose combinatorial Optimization Problems (COP) that extends previous AC models [21] by the inclusion of a negative pheromone, is here described. Several Travelling Salesman Problem‘s (TSP) were used as benchmark. We show that by using two different sets of pheromones, a second-order co-evolved compromise between positive and negative feedbacks achieves better results than single positive feedback systems. The algorithm was tested against known NP complete combinatorial Optimization Problems, running on symmetrical TSPs. We show that the new algorithm compares favourably against these benchmarks, accordingly to recent biological findings by Robinson [26,27], and Grüter [28] where “No entry” signals and negative feedback allows a colony to quickly reallocate the majority of its foragers to superior food patches. This is the first time an extended ACS algorithm is implemented with these successful characteristics.
Keywords: Self-Organization, Stigmergy, Co-Evolution, Swarm Intelligence, Dynamic Optimization, Foraging, Cooperative Learning, Combinatorial Optimization problems, Symmetrical Travelling Salesman Problems (TSP).
Figure – Hybrid Artificial Intelligent Systems new LNAI (Lecture Notes on Artificial Intelligence) series volume 8073, Springer-Verlag Book [original photo by my colleague David M.S. Rodrigues].
New work, new book. Last week one of our latest works come out published on Springer. Edited by Jeng-Shyang Pan, Marios M. Polycarpou, Emilio Corchado et al. “Hybrid Artificial Intelligent Systems” comprises a full set of new papers on this hybrid area on Intelligent Computing (check the full articles list at Springer). Our new paper “Second Order Swarm Intelligence” (pp. 411-420, Springer books link) was published on the Bio-inspired Models and Evolutionary Computation section.
The Hacker and the Ants is a work of science fiction by Rudy Rucker published in 1994 by Avon Books. It was written while Rucker was working as a programmer at Autodesk, Inc., of Sausalito, California from 1988 to 1992. The main character is a transrealist interpretation of Rucker’s life in the 1970s (Rucker taught mathematics at the State University College at Geneseo, New York from 1972 to 1978. from Wikipedia). The plot follows:
(…) Jerzy Rugby is trying to create truly intelligent robots. While his actual life crumbles, Rugby toils in his virtual office, testing the robots online. Then, something goes wrong and zillions of computer virus ants invade the net. Rugby is the man wanted for the crime. He’s been set up to take a fall for a giant cyberconspiracy and he needs to figure out who — or what — is sabotaging the system in order to clear his name. Plunging deep into the virtual worlds of Antland of Fnoor to find some answers, Rugby confronts both electronic and all-too-real perils, facing death itself in a battle for his freedom. (…)
“I would like to thank flocks, herds, and schools for existing: nature is the ultimate source of inspiration for computer graphics and animation.” in Craig Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model“, (paper link) published in Computer Graphics, 21(4), July 1987, pp. 25-34. (ACM SIGGRAPH ’87 Conference Proceedings, Anaheim, California, July 1987.)
Ever tried to solve a problem where its own problem statement is changing constantly? Have a look on our approach:
Vitorino Ramos, David M.S. Rodrigues, Jorge Louçã, “Spatio-Temporal Dynamics on Co-Evolved Stigmergy“, in European Conference on Complex Systems, ECCS’11, Vienna, Austria, Sept. 12-16 2011.
Abstract: Research over hard NP-complete Combinatorial Optimization Problems (COP’s) has been focused in recent years, on several robust bio-inspired meta-heuristics, like those involving Evolutionary Computation (EC) algorithmic paradigms. One particularly successful well-know meta-heuristic approach is based on Swarm Intelligence (SI), i.e., the self-organized stigmergic-based property of a complex system whereby the collective behaviors of (unsophisticated) entities interacting locally with their environment cause coherent functional global patterns to emerge. This line of research recognized as Ant Colony Optimization (ACO), uses a set of stochastic cooperating ant-like agents to find good solutions, using self-organized stigmergy as an indirect form of communication mediated by artificial pheromone, whereas agents deposit pheromone-signs on the edges of the problem-related graph complex network, encompassing a family of successful algorithmic variations such as: Ant Systems (AS), Ant Colony Systems (ACS), Max-Min Ant Systems (Max–Min AS) and Ant-Q.
Albeit being extremely successful these algorithms mostly rely on positive feedback’s, causing excessive algorithmic exploitation over the entire combinatorial search space. This is particularly evident over well known benchmarks as the symmetrical Traveling Salesman Problem (TSP). Being these systems comprised of a large number of frequently similar components or events, the principal challenge is to understand how the components interact to produce a complex pattern feasible solution (in our case study, an optimal robust solution for hard NP-complete dynamic TSP-like combinatorial problems). A suitable approach is to first understand the role of two basic modes of interaction among the components of Self-Organizing (SO) Swarm-Intelligent-like systems: positive and negative feedback. While positive feedback promotes a snowballing auto-catalytic effect (e.g. trail pheromone upgrading over the network; exploitation of the search space), taking an initial change in a system and reinforcing that change in the same direction as the initial deviation (self-enhancement and amplification) allowing the entire colony to exploit some past and present solutions (environmental dynamic memory), negative feedback such as pheromone evaporation ensure that the overall learning system does not stables or freezes itself on a particular configuration (innovation; search space exploration). Although this kind of (global) delayed negative feedback is important (evaporation), for the many reasons given above, there is however strong assumptions that other negative feedbacks are present in nature, which could also play a role over increased convergence, namely implicit-like negative feedbacks. As in the case for positive feedbacks, there is no reason not to explore increasingly distributed and adaptive algorithmic variations where negative feedback is also imposed implicitly (not only explicitly) over each network edge, while the entire colony seeks for better answers in due time.
In order to overcome this hard search space exploitation-exploration compromise, our present algorithmic approach follows the route of very recent biological findings showing that forager ants lay attractive trail pheromones to guide nest mates to food, but where, the effectiveness of foraging networks were improved if pheromones could also be used to repel foragers from unrewarding routes. Increasing empirical evidences for such a negative trail pheromone exists, deployed by Pharaoh’s ants (Monomorium pharaonis) as a ‘no entry‘ signal to mark unrewarding foraging paths. The new algorithm comprises a second order approach to Swarm Intelligence, as pheromone-based no entry-signals cues, were introduced, co-evolving with the standard pheromone distributions (collective cognitive maps) in the aforementioned known algorithms.
To exhaustively test his adaptive response and robustness, we have recurred to different dynamic optimization problems. Medium-size and large-sized dynamic TSP problems were created. Settings and parameters such as, environmental upgrade frequencies, landscape changing or network topological speed severity, and type of dynamic were tested. Results prove that the present co-evolved two-type pheromone swarm intelligence algorithm is able to quickly track increasing swift changes on the dynamic TSP complex network, compared to standard algorithms.
Keywords: Self-Organization, Stigmergy, Co-Evolution, Swarm Intelligence, Dynamic Optimization, Foraging, Cooperative Learning, Combinatorial Optimization problems, Dynamical Symmetrical Traveling Salesman Problems (TSP).
Fig. – Recovery times over several dynamical stress tests at the fl1577 TSP problem (1577 node graph) – 460 iter max – Swift changes at every 150 iterations (20% = 314 nodes, 40% = 630 nodes, 60% = 946 nodes, 80% = 1260 nodes, 100% = 1576 nodes). [click to enlarge]
David M.S. Rodrigues, Jorge Louçã, Vitorino Ramos, “From Standard to Second Order Swarm Intelligence Phase-space maps“, in European Conference on Complex Systems, ECCS’11, Vienna, Austria, Sept. 12-16 2011.
Abstract: Standard Stigmergic approaches to Swarm Intelligence encompasses the use of a set of stochastic cooperating ant-like agents to find optimal solutions, using self-organized Stigmergy as an indirect form of communication mediated by a singular artificial pheromone. Agents deposit pheromone-signs on the edges of the problem-related graph to give rise to a family of successful algorithmic approaches entitled Ant Systems (AS), Ant Colony Systems (ACS), among others. These mainly rely on positive feedback’s, to search for an optimal solution in a large combinatorial space. The present work shows how, using two different sets of pheromones, a second-order co-evolved compromise between positive and negative feedback’s achieves better results than single positive feedback systems. This follows the route of very recent biological findings showing that forager ants, while laying attractive trail pheromones to guide nest mates to food, also gained foraging effectiveness by the use of pheromones that repelled foragers from unrewarding routes. The algorithm presented here takes inspiration precisely from this biological observation.
The new algorithm was exhaustively tested on a series of well-known benchmarks over hard NP-complete Combinatorial Optimization Problems (COP’s), running on symmetrical Traveling Salesman Problems (TSP). Different network topologies and stress tests were conducted over low-size TSP’s (eil51.tsp; eil78.tsp; kroA100.tsp), medium-size (d198.tsp; lin318.tsp; pcb442.tsp; att532.tsp; rat783.tsp) as well as large sized ones (fl1577.tsp; d2103.tsp) [numbers here referring to the number of nodes in the network]. We show that the new co-evolved stigmergic algorithm compared favorably against the benchmark. The algorithm was able to equal or majorly improve every instance of those standard algorithms, not only in the realm of the Swarm Intelligent AS, ACS approach, as in other computational paradigms like Genetic Algorithms (GA), Evolutionary Programming (EP), as well as SOM (Self-Organizing Maps) and SA (Simulated Annealing). In order to deeply understand how a second co-evolved pheromone was useful to track the collective system into such results, a refined phase-space map was produced mapping the pheromones ratio between a pure Ant Colony System (where no negative feedback besides pheromone evaporation is present) and the present second-order approach. The evaporation rate between different pheromones was also studied and its influence in the outcomes of the algorithm is shown. A final discussion on the phase-map is included. This work has implications in the way large combinatorial problems are addressed as the double feedback mechanism shows improvements over the single-positive feedback mechanisms in terms of convergence speed and on major results.
Keywords: Stigmergy, Co-Evolution, Self-Organization, Swarm Intelligence, Foraging, Cooperative Learning, Combinatorial Optimization problems, Symmetrical Traveling Salesman Problems (TSP), phase-space.
Fig. – Comparing convergence results between Standard algorithms vs. Second Order Swarm Intelligence, over TSP fl1577 (click to enlarge).
“With an eye for detail and an easy style, Peter Miller explains why swarm intelligence has scientists buzzing.” — Steven Strogatz, author of Sync, and Professor of Mathematics, Cornell University.
From the introduction of, Peter Miller, “Smart Swarms – How Understanding Flocks, Schools and Colonies Can Make Us Better at Communicating, Decision Making and Getting Things Done“. (…) The modern world may be obsessed with speed and productivity, but twenty-first century humans actually have much to learn from the ancient instincts of swarms. A fascinating new take on the concept of collective intelligence and its colourful manifestations in some of our most complex problems, Smart Swarm introduces a compelling new understanding of the real experts on solving our own complex problems relating to such topics as business, politics, and technology. Based on extensive globe-trotting research, this lively tour from National Geographic reporter Peter Miller introduces thriving throngs of ant colonies, which have inspired computer programs for streamlining factory processes, telephone networks, and truck routes; termites, used in recent studies for climate-control solutions; schools of fish, on which the U.S. military modelled a team of robots; and many other examples of the wisdom to be gleaned about the behaviour of crowds-among critters and corporations alike. In the tradition of James Surowiecki‘s The Wisdom of Crowds and the innovative works of Malcolm Gladwell, Smart Swarm is an entertaining yet enlightening look at small-scale phenomena with big implications for us all. (…)
(…) What do ants, bees, and birds know that we don’t? How can that give us an advantage? Consider: • Southwest Airlines used virtual ants to determine the best way to board a plane. • The CIA was inspired by swarm behavior to invent a more effective spy network. • Filmmakers studied flocks of birds as models for armies of Orcs in Lord of the Rings battle scenes. • Defense agencies sponsored teams of robots that can sense radioactivity, heat, or a chemical device as easily as a school of fish can locate food. Find out how “smart swarms” can teach us how to make better choices, create stronger networks, and organize our businesses more effectively than we ever thought possible. (…)
The dynamics of ant swarms share an uncanny similarity with the movement of various fluids (video above). Micah Streiff and his team from the Georgia Institute of Technology in Atlanta captured writhing groups of ants behaving just like liquids. You can watch them diffuse outwards from a pool, tackle jagged surface like a viscous fluid or flow from a funnel (from NewScientist | 2010 best videos).
[…] Fire ants use their claws to grip diverse surfaces, including each other. As a result of their mutual adhesion and large numbers, ant colonies flow like inanimate fluids. In this sequence of films, we demonstrate how ants behave similarly to the spreading of drops, the capillary rise of menisci, and gravity-driven flow down a wall. By emulating the flow of fluids, ant colonies can remain united under stressful conditions. […], in Micah Streiff, Nathan Mlot, Sho Shinotsuka, Alex Alexeev, David Hu, “Ants as Fluids: Physics-Inspired Biology,” ArXiv, 15 Oct 2010. http://arxiv.org/abs/1010.3256 .
Remember those weather TV channel hurricane images over central America captured by satellites? E.g. Floyd just off the Florida coast on September 14, 1999 (image at nationalgeographic.com). Well, you are pretty close. Here is an example of an ant colony death spiral, where a group of ants gets separated from their colony and start following each other by scent in a circle, and they do so until they all die of exhaustion. A deadlock. An ant’s circle deadlock.
So in order to teach a computer on how to draw a circle without giving him any clue on how what a circle his, what you have to do is exactly the same thing. You just follow a generative design line of bottom-up distributed pattern formation. And you keep replacing the word “computer” by the word “ant” at the title of this post, as many times you can, back and forth, in a non-explicit manner. Using stigmergy. You just implicitly create simple rules, even ant-like, non-anthropomorphic, which end-up at that exactly behaviour. Yes,… sometimes those “simple” rules are difficult to grab. But you just keep doing it. Not with a simple “trial-and-error” method, of course. We have better tools to do that. In fact, they are present in planet Earth since the Big-Bang: we call it, Evolution. Now, from circles beyond, a full array of problems, even hard ones could be treated. Here are some examples.
From the author of “Rock, Paper, Scissors – Game Theory in everyday life” dedicated to evolution of cooperation in nature (published last year – Basic Books), a new book on related areas is now fresh on the stands (released Dec. 7, 2009): “The Perfect Swarm – The Science of Complexity in everyday life“. This time Len Fischer takes us into the realm of our interlinked modern lives, where complexity rules. But complexity also has rules. Understand these, and we are better placed to make sense of the mountain of data that confronts us every day. Fischer ranges far and wide to discover what tips the science of complexity has for us. Studies of human (one good example is Gum voting) and animal behaviour, management science, statistics and network theory all enter the mix.
One of the greatest discoveries of recent times is that the complex patterns we find in life are often produced when all of the individuals in a group follow similar simple rules. Even if the final pattern is complex, rules are not. This process of “Self-Organization” reveals itself in the inanimate worlds of crystals and seashells, but as Len Fisher shows, it is also evident in living organisms, from fish to ants to human beings, being Stigmergy one among many cases of this type of Self-Organized behaviour, encompassing applications in several Engineering fields like Computer science and Artificial Intelligence, Data-Mining, Pattern Recognition, Image Analysis and Perception, Robotics, Optimization, Learning, Forecasting, etc. Since I do work on these precise areas, you may find several of my previous posts dedicated to these issues, such as Self-Organized Data and Image Retrieval systems, Stigmergic Optimization, Computer-based Adaptive Dynamic Perception, Swarm-based Data Mining, Self-regulated Swarms and Memory, Ant based Data Clustering, Generative computer-based photography and painting, Classification, Extreme Dynamic Optimization, Self-Organized Pattern Recognition, among other applications.
For instance, the coordinated movements of fish in schools, arise from the simple rule: “Follow the fish in front.” Traffic flow arises from simple rules: “Keep your distance” and “Keep to the right.” Now, in his new book, Fisher shows how we can manage our complex social lives in an ever more chaotic world. His investigation encompasses topics ranging from “swarm intelligence” (check links above) to the science of parties (a beautiful example by ICOSYSTEM inc.) and the best ways to start a fad. Finally, Fisher sheds light on the beauty and utility of complexity theory. For those willing to understand a miriad of some basic examples (Fischer gaves us 33 nice food-for-thought examples in total) and to have a well writen introduction into this thrilling new branch of science, referred by Stephen Hawking as the science for the current century (“I think complexity is the science for the 21st century”), Perfect Swarm will be indeed an excelent companion.
Journalism is dying, they say. I do agree. And while the argue continues, many interested on the issue are now debating what really is the reason. The question is…, there is no reason at all, there are many. Intricate ones. Do ponder on this: while newspapers are facing the immense omnipresent and real-time competition from TV channels, TV on itself is dying also (while unexpectedly, … Radio is surging). On many broadcasted programs, TV anchors are now more important than the invited people who, on that subject (supposedly) worked hardly over years to provide that precise innovative content. As in large supermarkets and great malls, package by these means have turned more important than the content in itself. This related business editorial pressure for news quickness have become so intensive and aggressive, that contents are replaced every second without judge and once in the air hardly described, discussed, opposed or dessicated. So at large, TV CEO’s producers think that people are no longer waiting for a new interesting content to appear, they are instead waiting for the anchor which passes them down as they were peanuts. Peanuts are good, but in excess – we all agree – are damn awful. And many do so, as an old passive addiction. Which means that in the long run, nothing remains (fact for both sides); … And if they give me no opportunity at all to check content carefully, if I happen to be on the mood to, … So, I move on. Buy this precise simple way, media cannibalizes itself.
We all know that attention spam is getting narrower these days, and, e.g., yes… greater literature classics are no longer read. So, Media CEO’s say – “they have no time“. But, really … do mind that gap. Think twice. If the whole environment suddenly recognizes (being this one of the major questions – see below) that they are getting enough of peanuts (and they really are), they will urge for beef-steaks. In fact, eating 1000 void peanuts takes more time to consume than one large good beef! And there is a difference, … the beef remains on our body for several hours, not seconds.
It’s promptly becoming a paradox, since Media CEO’s on their blindness competition refuge on saying that they – us readers – have no time (when in mediocrity no solution is found, easiest way is to repeat a mantra), and we (mostly of us) keep zapping news as never before. However, they never realized that we keep zapping it, because no news – by these means – are of interest. They really all have become the same. And once they appear all the same, they all soon disappear from our minds. … We all in some aspects all wonder, what really happened to research journalism, stories about new complex issues, strong content, explained in detail but still provided in simple eloquent ways? Come on, this long-tailed huge market niche, once yours, is now void!
Newspapers do have this wonderful singularity. They still have journalists (at least some, if they had enough vision to nourish them). They could provide insightful detailed backup stories, open questions, or debating new ones as no one can in public space. Moreover, they have time from their consumers. That, at least, is what I am feed-backing to Guardian every Sunday when I put my money over the news bench in change for this newspaper, along others like The Economist. But in face of these overall great news-without-sense turmoil cascade, probably one of these days, people will instead desire silence… or listening to their grandfathers knowledge, good-sense, and long-lived emotion (which keeps increasing believe me). They will relate to him, as never before. Not newspapers. At least, he do provides content.
But once the media is set (and in some way, not all the way, medium is the message, as postulated by Marshall McLuhan), the great gold-run will be on, … guess what, … content. And on relationships among content! Journalism will be no longer under atomization. Or crystallized.
Fig. – Spatial distribution of 931 items (words taken from an article at ABC Spanish newspaper) on a 61 x 61 non-parametric toroidal grid, at t=106. 91 ants used type 2 probability response functions, with k1=0.1 and k2=0.3. Some independent clusters examples are: (A) anunció, bilbao, embargo, titulos, entre, hacer, necesídad, tras, vida, lider, cualquier, derechos, medida.(B) dirigentes, prensa, ciu. (C) discos, amigos, grandes. (D) hechos, piloto, miedo, tipo, cd, informes. (E) dificil, gobierno, justicia, crisis, voluntad, creó, elección, horas, frente, técnica, unas, tarde, familia, sargento, necesídad, red, obra … (among other word semantic clusters; check paper article below).
For long, media decided to do nothing, while new media including social media was coming in to the plateu, stronger as never before. Let me give you one example. In order to understand how relations between item news could enhnace newspaper reading and social awareness, back in 2002 I decided to make an experiment. Together with a colleague, we took one article of the Spanish ABC magazine (photo above). The article was about spanish political parties and corruption. It contained 931words (snapshot above). In order to extract semantic meaning from it as a pre-processing computer analysis, we started by applying Latent Semantic Analysis (LSA). Then, Swarm Intelligent algorithms were developed in order to have a glimpse on the relations among all those words on the newspaper article. Guess what? Some words like “big”, friends” and “music discs” were segmented from the rest of the political related article (segregated it on a remote semantic “island”), that is, not only a whole conceptual semantic atlas of that entire news section was possible, as well as finding unrelated issues (which were uncorrelated semantic “islands”). Now, just imagine if this happens within a newspaper social network, live, 24 hours a day, while people grab for strong co-related content and discuss it as it happens. One strong journal article, could in facto, evolve to social collective knowledge and awareness as never before. That, in reality is something that classic journalism could use as and edge for their (nowadays awful) market approach. Providing not only good content, but along with it, an extra service not available anyware (which is in some way, priceless): The chance to provide co-related real-time meta-content. Not one view, but many aggregated views. Edited real-world real-time good quality journalism which has the potential of an “endless” price, namely these days. On the other hand, what we now see is that news CEO’s along with some editors still keep their minds on 19th century journalism. For worse, due to their legitimic panic. However, meanwhile, the world has indeed evolved.
[] Vitorino Ramos, Juan J. Merelo, Self-Organized Stigmergic Document Maps: Environment as a Mechanism for Context Learning, in AEB´2002 – 1st Spanish Conference on Evolutionary and Bio-Inspired Algorithms, E. Alba, F. Herrera, J.J. Merelo et al. (Eds.), pp. 284-293, Centro Univ. de Mérida, Mérida, Spain, 6-8 Feb. 2002.
Social insect societies and more specifically ant colonies, are distributed systems that, in spite of the simplicity of their individuals, present a highly structured social organization. As a result of this organization, ant colonies can accomplish complex tasks that in some cases exceed the individual capabilities of a single ant. The study of ant colonies behavior and of their self-organizing capabilities is of interest to knowledge retrieval/management and decision support systems sciences, because it provides models of distributed adaptive organization which are useful to solve difficult optimization, classification, and distributed control problems, among others. In the present work we overview some models derived from the observation of real ants, emphasizing the role played by stigmergy as distributed communication paradigm, and we present a novel strategy to tackle unsupervised clustering as well as data retrieval problems. The present ant clustering system (ACLUSTER) avoids not only short-term memory based strategies, as well as the use of several artificial ant types (using different speeds), present in some recent approaches. Moreover and according to our knowledge, this is also the first application of ant systems into textual document clustering.
(to obtain the respective PDF file follow link above or visit chemoton.org)
With the ubiquitous use of web-based and wireless Social Networks, people are increasingly using the term “Collective Intelligence“. However, I do have serious doubts they really understand what they meant. Some call it the wisdom of crowds or collective wisdom, others smart mobs, while others wealth of knowledge, world brain and so on. Moreover, turning things worse, there are those also, which tend to see it, or confound it with crowd-sourcing as well as prediction markets. Even if there are some loosely conceptual bridges between all them, it will be probably useful to know that the term was instead been born over the Artificial Intelligence research area, while exploiting stigmergic phenomena (see also Swarm Intelligence) among ensembles of cooperative agents. So what follows is a recent definition provided by Univ. of Alberta, Canada. This entry was added last month (Nov. 2009) at the Dictionary of Cognitive Science (Michael R.W. Dawson, David A. Medler Eds.):
Collective intelligence – is a term that refers to the computational abilities of a group of agents. With collective intelligence, a group is capable of accomplishing a task, or of solving an information processing problem, that is beyond the capabilities of an individual agent.
Collective intelligence depends on more than mere numbers of agents. For a collective to be considered intelligent, the whole must be greater than the sum of its parts. This idea has been used to identify the presence of collective intelligence by relating the amount of work done by a collective to the number of agents in the collection (Beni & Wang, 1991). If there is a linear increase in amount of work done as a function of the number of agents, then collective intelligence is not evident. However, if there is a nonlinear increase (e.g., an exponential increase) in the amount of work done as a function of the number of agents, then Beni and Wang argue that this is evidence that the collective is intelligent.
Collective intelligence is of interest in cognitive science because many colonies of social insects appear to exhibit this kind of intelligence, and this has inspired researchers to explore “porting” such processing to robot collectives. As far as robots are concerned, collective intelligence is exciting because it offers the possiblity of developing systems that are scalable (they don’t get disrupted when more agents are added) and flexible (they don’t get disrupted when some agents are damaged or fail) (Sharkey, 2006).
References:
1. Beni, G., & Wang, J. (1991, April 9-11). Theoretical problems for the realization of distributed robotic systems. Paper presented at the IEEE International Conference on Robotics and Automation, Sacramento, CA.
2. Sharkey, A. J. C. (2006). Robots, insects and swarm intelligence. Artificial Intelligence Review, 26(4), 255-268.
Figure – My first Swarm Painting SP0016 (Jan. 2002). This was done attaching the following algorithm into a robotic drawing arm. In order to do it however, pheromone distribution by the overall ant colony were carefully coded into different kinds of colors and several robotic pencils (check “The MC2 Project [Machines of Collective Conscience]“, 2001, and “On the Implicit and on the Artificial“, 2002). On the same year when the computational model appeared (2000) the concept was already extended into photography (check original paper) – using the pheromone distribution as photograms (“Einstein to Map” in the original article along with works like “Kafka to Red Ants” as well as subsequent newspaper articles). Meanwhile, in 2003, I was invited to give an invited talk over these at the 1st Art & Science Symposium in Bilbao (below). Even if I was already aware of Jeffrey Ventrella outstanding work as well as Ezequiel Di Paolo, it was there where we first met physically.
[] Vitorino Ramos, Self-Organizing the Abstract: Canvas as a Swarm Habitat for Collective Memory, Perception and Cooperative Distributed Creativity, in 1st Art & Science Symposium – Models to Know Reality, J. Rekalde, R. Ibáñez and Á. Simó (Eds.), pp. 59, Facultad de Bellas Artes EHU/UPV, Universidad del País Vasco, 11-12 Dec., Bilbao, Spain, 2003.
Many animals can produce very complex intricate architectures that fulfil numerous functional and adaptive requirements (protection from predators, thermal regulation, substrate of social life and reproductive activities, etc). Among them, social insects are capable of generating amazingly complex functional patterns in space and time, although they have limited individual abilities and their behaviour exhibits some degree of randomness. Among all activities by social insects, nest building, cemetery organization and collective sorting, is undoubtedly the most spectacular, as it demonstrates the greatest difference between individual and collective levels. Trying to answer how insects in a colony coordinate their behaviour in order to build these highly complex architectures, scientists assumed a first hypothesis, anthropomorphism, i.e., individual insects were assumed to possess a representation of the global structure to be produced and to make decisions on the basis of that representation. Nest complexity would then result from the complexity of the insect’s behaviour. Insect societies, however, are organized in a way that departs radically from the anthropomorphic model in which there is a direct causal relationship between nest complexity and behavioural complexity. Recent works suggests that a social insect colony is a decentralized system composed of cooperative, autonomous units that are distributed in the environment, exhibit simple probabilistic stimulus-response behaviour, and have only access to local information. According to these studies at least two low-level mechanisms play a role in the building activities of social insects: Self-organization and discrete Stigmergy, being the latter a kind of indirect and environmental synergy. Based on past and present stigmergic models, and on the underlying scientific research on Artificial Ant Systems and Swarm Intelligence, while being systems capable of emerging a form of collective intelligence, perception and Artificial Life, done by Vitorino Ramos, and on further experiences in collaboration with the plastic artist Leonel Moura, we will show results facing the possibility of considering as “art”, as well, the resulting visual expression of these systems. Past experiences under the designation of “Swarm Paintings” conducted in 2001, not only confirmed the possibility of realizing an artificial art (thus non-human), as introduced into the process the questioning of creative migration, specifically from the computer monitors to the canvas via a robotic harm. In more recent self-organized based research we seek to develop and profound the initial ideas by using a swarm of autonomous robots (ARTsBOT project 2002-03), that “live” avoiding the purpose of being merely a simple perpetrator of order streams coming from an external computer, but instead, that actually co-evolve within the canvas space, acting (that is, laying ink) according to simple inner threshold stimulus response functions, reacting simultaneously to the chromatic stimulus present in the canvas environment done by the passage of their team-mates, as well as by the distributed feedback, affecting their future collective behaviour. In parallel, and in what respects to certain types of collective systems, we seek to confirm, in a physically embedded way, that the emergence of order (even as a concept) seems to be found at a lower level of complexity, based on simple and basic interchange of information, and on the local dynamic of parts, who, by self-organizing mechanisms tend to form an lived whole, innovative and adapting, allowing for emergent open-ended creative and distributed production.
a) Dynamic Optimization Problems (DOP) tackled by Swarm Intelligence (in here a quick snapshot of the dynamic environment)
b) Swarm adaptive response over time, under severe dynamics, over the dynamic environment on the left (a).
Figs. – Check animated pictures in here. (a) A 3D toroidal fast changing landscape describing a Dynamic Optimization (DO) Control Problem (8 frames in total). (b) A self-organized swarm emerging a characteristic flocking migration behaviour surpassing in intermediate steps some local optima over the 3D toroidal landscape (left), describing a Dynamic Optimization (DO) Control Problem. Over each foraging step, the swarm self-regulates his population and keeps tracking the extrema (44 frames in total).
[] Vitorino Ramos, Carlos Fernandes, Agostinho C. Rosa, On Self-Regulated Swarms, Societal Memory, Speed and Dynamics, in Artificial Life X – Proc. of the Tenth Int. Conf. on the Simulation and Synthesis of Living Systems, L.M. Rocha, L.S. Yaeger, M.A. Bedau, D. Floreano, R.L. Goldstone and A. Vespignani (Eds.), MIT Press, ISBN 0-262-68162-5, pp. 393-399, Bloomington, Indiana, USA, June 3-7, 2006.
PDF paper.
Wasps, bees, ants and termites all make effective use of their environment and resources by displaying collective “swarm” intelligence. Termite colonies – for instance – build nests with a complexity far beyond the comprehension of the individual termite, while ant colonies dynamically allocate labor to various vital tasks such as foraging or defense without any central decision-making ability. Recent research suggests that microbial life can be even richer: highly social, intricately networked, and teeming with interactions, as found in bacteria. What strikes from these observations is that both ant colonies and bacteria have similar natural mechanisms based on Stigmergy and Self-Organization in order to emerge coherent and sophisticated patterns of global foraging behavior. Keeping in mind the above characteristics we propose a Self-Regulated Swarm (SRS) algorithm which hybridizes the advantageous characteristics of Swarm Intelligence as the emergence of a societal environmental memory or cognitive map via collective pheromone laying in the landscape (properly balancing the exploration/exploitation nature of our dynamic search strategy), with a simple Evolutionary mechanism that trough a direct reproduction procedure linked to local environmental features is able to self-regulate the above exploratory swarm population, speeding it up globally. In order to test his adaptive response and robustness, we have recurred to different dynamic multimodal complex functions as well as to Dynamic Optimization Control problems, measuring reaction speeds and performance. Final comparisons were made with standard Genetic Algorithms (GAs), Bacterial Foraging strategies (BFOA), as well as with recent Co-Evolutionary approaches. SRS’s were able to demonstrate quick adaptive responses, while outperforming the results obtained by the other approaches. Additionally, some successful behaviors were found: SRS was able to maintain a number of different solutions, while adapting to unforeseen situations even when over the same cooperative foraging period, the community is requested to deal with two different and contradictory purposes; the possibility to spontaneously create and maintain different sub-populations on different peaks, emerging different exploratory corridors with intelligent path planning capabilities; the ability to request for new agents (division of labor) over dramatic changing periods, and economizing those foraging resources over periods of intermediate stabilization. Finally, results illustrate that the present SRS collective swarm of bio-inspired ant-like agents is able to track about 65% of moving peaks traveling up to ten times faster than the velocity of a single individual composing that precise swarm tracking system. This emerged behavior is probably one of the most interesting ones achieved by the present work.
For some seconds, just imagine having these 50 m² – 8 meters tall artifact constructed (above) by tiny Giant Architects in a plaza over a big city near you. Over this youtube video several scientists have filled the big city unearthed with 10 tens of cement during 3 days. Then calmly (taking several weeks), have digg it to the bone. To have a clue on what I mean just imagine having all these at Times Square plaza in New York! or at the front-door of the Frank Gehry’s Guggenheim Museum in Bilbao (in fact a giant spider is also there – check photo below). Colonies of eu-social insects use stigmergy in order to do this, being a good reference the work done by Karsai back in 1999 at the Artificial Life MIT Press Journal (here is the abstract – unfornately I have it on paper but not scanned):
# István Karsai, “Decentralized Control of Construction Behavior in Paper Wasps: An Overview of the Stigmergy Approach“, Spring 1999, Vol. 5, No. 2, Pages 117-136.
Grassé [26] coined the term stigmergy (previous work directs and triggers new building actions) to describe a mechanism of decentralized pathway of information flow in social insects. In general, all kinds of multi-agent groups require coordination for their effort and it seems that stigmergy is a very powerful means to coordinate activity over great spans of time and space in a wide variety of systems. In a situation in which many individuals contribute to a collective effort, such as building a nest, stimuli provided by the emerging structure itself can provide a rich source of information for the working insects. The current article provides a detailed review of this stigmergic paradigm in the building behavior of paper wasps to show how stigmergy influenced the understanding of mechanisms and evolution of a particular biological system. The most important feature to understand is how local stimuli are organized in space and time to ensure the emergence of a coherent adaptive structure and to explain how workers could act independently yet respond to stimuli provided through the common medium of the environment of the colony.
Another interesting paper (available online) is the more recent work by Mason at the 8th Artificial Life conference, in 2002. Below I have selected part of the introductory text:
# Zachary Mason ,”Programming with Stigmergy: Using Swarms for Construction“, in Artificial Life VIII Conf., Standish, Abbass, Bedau (eds)(MIT Press), New South Wales, Australia, pp. 371-375, 2002.
(…) Termite nests are large and complex. A nest may be as much as 104 or 105 times as large as an individual termite (Boneabeau et al. 1997) a ratio unparalleled in the animal kingdom. The nests of the African termite sub-family Macrotermitinae are composed of many substructures, such as protective bulwarks, pillared brood chambers, spiral cooling vents, galleries of fungus gardens and royal chambers. For all the architectural sophistication of termite nests, termites themselves are blind, weak and apparently not responsive to a coordinating authority. This work attempts to borrow and generalize the termite construction-algorithm, permitting artificial, decentralized swarms to be programmed to build complex, composable structures.
How do small, blind termites manage to build (relatively) huge, intricate nests? Work on this question includes a simple, decentralized building model (Grasse 1959) (Grasse 1984), an empirical study of termite building behavior (Bruinsma 1979), a mathematical model of the synthesis of pillars in termite nests (Deneubourg 1977), and a model explaining how modest environmental variation can cause the same termite behaviors to generate qualitatively different structures (Boneabeau et al. 1997). Most relevant to this work is (Bruinsma 1979), which records three feedback mechanisms governing termite behavior. In the first, a termite picks up a soil pellet, masticates it into a paste and injects a termiteattracting pheremone into it. When the pellet is deposited, the pheremone stimulates nearby termites to pellet-gathering behavior and makes them more likely to deposit their pellets nearby. Second, small obstacles in the terrain stimulate pellet deposits and can seed pillars. Finally, a trail pheremone allows more workers to be drawn to a construction site. Termites and many social insects interact stigmergically – that is, communication is mediated through changes in the environment rather than direct signal transmission. Computer simulations have used stigmergy to reproduce termite’s pillar-making behavior and ant’s foraging and the spontaneous cemetery building. These applications rely of qualitative stigmergy | individual agents react to a continuous variations in the environment. An example of quantitative stigmergy is (G. Theraulaz 1995), a simulation of wasp nest building. Wasps build nests by depositing cells on a lattice. Whether an empty cell is lled depends on the adjacent cells. Because all wasps have the same deposit-triggers, multiple wasps are able to simultaneously work on a single nest without without ruining each others work. A set of deposit-triggers is coherent if each no stage in the building process can be confused with an earlier stage by making only local observations, thus obviating the need for centralized control.
The goal of this work is to generalize the construction methodologies of the social insects and create a language for stigmergically assembling complex structures. Such a language permit swarms of agents to erect interesting architectures without benefit of a central controller or explicit inter-agent communication. The primary advantage of this approach is that stigmergically controlled swarms have minimal communication and no coordination overhead. Also, very little processing is demanded of agents, and the swarm can tolerate a degree of agent error. On a more abstract plane, this work is an example of designing emergent behavior. (…)
Figure – A sequential clustering task of corpses performed by a real ant colony. In here 1500 corpses are randomly located in a circular arena with radius = 25 cm, where Messor Sancta workers are present. The figure shows the initial state (above), 2 hours, 6 hours and 26 hours (below) after the beginning of the experiment (from: Bonabeau E., M. Dorigo, G. Théraulaz. Swarm Intelligence: From Natural to Artificial Systems. Santa Fe Institute in the Sciences of the Complexity, Oxford University Press, New York, Oxford, 1999).
The following research paper exploits precisely this phenomena into digital data.
[] Vitorino Ramos, Fernando Muge, Pedro Pina, Self-Organized Data and Image Retrieval as a Consequence of Inter-Dynamic Synergistic Relationships in Artificial Ant Colonies, in Javier Ruiz-del-Solar, Ajith Abraham and Mario Köppen (Eds.), Frontiers in Artificial Intelligence and Applications, Soft Computing Systems – Design, Management and Applications, 2nd Int. Conf. on Hybrid Intelligent Systems, IOS Press, Vol. 87, ISBN 1 5860 32976, pp. 500-509, Santiago, Chile, Dec. 2002.
Social insects provide us with a powerful metaphor to create decentralized systems of simple interacting, and often mobile, agents. The emergent collective intelligence of social insects “swarm intelligence” resides not in complex individual abilities but rather in networks of interactions that exist among individuals and between individuals and their environment. The study of ant colonies behavior and of their self-organizing capabilities is of interest to knowledge retrieval/ management and decision support systems sciences, because it provides models of distributed adaptive organization which are useful to solve difficult optimization, classification, and distributed control problems, among others. In the present work we overview some models derived from the observation of real ants, emphasizing the role played by stigmergy as distributed communication paradigm, and we present a novel strategy (ACLUSTER) to tackle unsupervised data exploratory analysis as well as data retrieval problems. Moreover and according to our knowledge, this is also the first application of ant systems into digital image retrieval problems. Nevertheless, the present algorithm could be applied to any type of numeric data.
(to obtain the respective PDF file follow link above or visit chemoton.org)
Gum election in the public streets of Berlin – “Who sucks the worst? Vote with your gum“. Several weeks before the election on United States, this rather simple but extraordinary concept spread from NY city to San Francisco, from St. Louis to São Paulo, from Berlin to Sydney within a few days. This kind of remembers me one of my friend’s (Ivo et al’s) project – Stick Me!, due to some similar features. Even nowadays my own refrigerator has one Stick Me! sticker over it and I really enjoyed participating on it in the past via one very quick and humble “Stick Me Mate” proposal, while playing blitz chess with friends at a bar nearby my house.
A bunch of people (promoting Collective Intelligence?) is using the environment as a way to communicate (like over any chessboard). Communication is indirect, but still they communicate through the alterations and patterns they impose on the environment itself. Meanwhile, imposing a mark or sign somewhere, increases the probability of a second response later in time – a response to a stimulus (as ants put their pheromone marks on the ground). Though here however (on both projects) only positive feedback is used.
In fact, Mother Nature has conceived a very outstandingly simple and better strategy: their signs and cues vanish in time, simple as that! For instance, pheromone, a chemical substance segregated by ants and termites evaporates in time. Over here however, there is no evaporation at all working on (societal agents are not entitled to use negative feedbacks or using vanishing marks), which can curse it’s own dynamic – unless someone destroys the posters, of course. Amazon book recommendation system, works as well this way, that is by uniquely making use of positive feedbacks (people that bought this X book also as bought Y, etc). Unfortunately, Amazon system along with his wish lists could not integrate that someone who bought the X book did not bought Z (while others have done it), which basically leads to a snow-balling effect that does not self-organize in time (adapts) to new potential good-reading books. What you end up seeing is just the overall majority consensus, the “minimum common multiple” as I sometimes call it, who tends to over-look and underestimate some high potential new-coming solutions (over this precise context, good books coming in). Amazon should instead look carefully to some scientific works on collaborative filtering. Instead the consequences are this: check here for a real user feedback on what Amazon is suggesting, or in fact not suggesting at all.
Not only their system tends to adapt slowly, since the only thing it’s promoting is nothing else but memory (exploitation, which could be achieved by positive feedbacks), as he is not learning (exploration, which could be achieved by negative feedbacks), when we know that on the contrary, a delicate compromise between both is in fact of huge importance. The difficult but possible systemic trick is to remember the past as simultaneously innovating. If as a whole the system only remembers the past, no innovation is possible causing dramatic consequences when the “environment” changes. This could lead to stagnation. On the other hand, if too much systemic pressure is put on innovation itself, energy is lost, leading the system to explore the universe of possible solutions in a quite “”stupid” trial-and-error like random manner. Some dynamics between one thing (memory) and the other (learning) could be checked here (figs. 4,5,6,7 and 19), along with their speed.
After all a gum or a sticker is nothing else than a tag -as web blogging tags and internet tag clouds are. My question is – Could they vanish over time as I believe and propose they should? Having that question in mind, while looking at these precise public street projects, there are also other conceptual bridges we may found, as far as I recognize.
Let me refer at least 4, with the help of some passages below from other texts: (1) Hobo signs and codes (as well as the bottom-up like emergence of norms and ethical codes between them), (2) the role of Positive and Negative feedbacks briefly discussed above, (3) Swarm Intelligence and of course, (4) Stigmergy. In what specifically regards Hobo signs let me say that they are quite clever. Since they are done with chalk! So, rain and erosion could erase them, little by little, day by day. Thus, solutions that were good in the past, but no longer exist or that are partially vanished over time, tend to be replaced by new fresh ones, appropriated for the present, only loosing part of the whole systemic memory, serving us with new stimulus (we tend to respond to those fresh ones), allowing a continuous adaptation to reality. As I said in the past over a scientific invited lecture (not the right place to say it, though!), signs, quotes, delayed desynchronized dialogues and phrases over the doors of public bathrooms follow similar trends and tend to be stigmergic. In what regards the following four passages, I leave to you the connection between them (sorry for this now long food for thought post):
(1) […] Synergy, from the Greek word synergos, broadly defined, refers to combined or co-operative effects produced by two or more elements (parts or individuals). The definition is often associated with the quote “the whole is greater than the sum of its parts” (Aristotle, in Metaphysics), even if it is more accurate to say that the functional effects produced by wholes are different from what the parts can produce alone. Synergy is a ubiquitous phenomena in nature and human societies alike. One well know example is provided by the emergence of self-organization in social insects, via direct (mandibular, antennation, chemical or visual contact, etc) or indirect interactions. The latter types are more subtle and defined by Grassé as Stigmergy to explain task coordination and regulation in the context of nest reconstruction in Macrotermes termites. An example, could be provided by two individuals, who interact indirectly when one of them modifies the environment and the other responds to the new environment at a later time. In other words, stigmergy could be defined as a typical case of environmental synergy. Grassé showed that the coordination and regulation of building activities do not depend on the workers themselves but are mainly achieved by the nest structure: a stimulating configuration triggers the response of a termite worker, transforming the configuration into another configuration that may trigger in turn another (possibly different) action performed by the same termite or any other worker in the colony. Another illustration of how stimergy and self-organization can be combined into more subtle adaptive behaviors is recruitment in social insects. Self-organized trail laying by individual ants is a way of modifying the environment to communicate with nest mates that follow such trails. It appears that task performance by some workers decreases the need for more task performance: for instance, nest cleaning by some workers reduces the need for nest cleaning. Therefore, nest mates communicate to other nest mates by modifying the environment (cleaning the nest), and nest mates respond to the modified environment (by not engaging in nest cleaning); that is stigmergy. […],
in Vitorino Ramos, Juan J. Merelo, Self-Organized Stigmergic Document Maps: Environment as a Mechanism for Context Learning, in AEB´2002 – 1st Spanish Conference on Evolutionary and Bio-Inspired Algorithms, E. Alba, F. Herrera, J.J. Merelo et al. (Eds.), pp. 284-293, Centro Univ. de Mérida, Mérida, Spain, 6-8 Feb. 2002.
(2) […] To cope with the difficulty of hobo life, hobos developed a system of symbols, or a code. Hobos would write this code with chalk or coal to provide directions, information, and warnings to other hobos. Some signs included “turn right here”, “beware of hostile railroad police”, “dangerous dog”, “food available here”, and so on. For instance: a cross signifies “angel food,” that is, food served to the hobos after a party. A triangle with hands signifies that the homeowner has a gun. Sharp teeth signify a mean dog. A square missing its top line signifies it is safe to camp in that location. A top hat and a triangle signify wealth. A spearhead signifies a warning to defend oneself. A circle with two parallel arrows means to get out fast, as hobos are not welcome in the area. Two interlocked humans signify handcuffs. (i.e. hobos are hauled off to jail). A Caduceus symbol signifies the house has a medical doctor living in it. A cat signifies that a kind lady lives here. A wavy line (signifying water) above an X means fresh water and a campsite. Three diagonal lines means it’s not a safe place. A square with a slanted roof (signifying a house) with an X through it means that the house has already been “burned” or “tricked” by another hobo and is not a trusting house. Two shovels, signifying work was available (Shovels, because most hobos did manual labor). […], in Hobo, Wikipedia.
(3) […] Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of entities interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with which it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model (Stan Franklin, Coordination without Communication, talk at Memphis Univ., USA, 1996). […] (here)
Hobo or tramp markings at Algiers entrance to Canal Street Ferry across Mississippi River, New Orleans. Ferry is free for pedestrians or on bicycle. "X" means "OK", slashed circle "Good way to go". (via Wikipedia above).
(4) […] – Positive feedback, f+: in contrast to negative feedback, positive feedback generally promotes changes in the system (the majority of SO systems use them). The ex-plosive growth of the human population provides a familiar example of the effect of positive feedback. The snowballing auto catalytic effect of f+ takes an initial change in a system (due to amplification of fluctuations; a minimal and natural local cluster of objects could be a starting point) and reinforces that change in the same direction as the initial deviation. Self-enhancement, amplification, facilitation, and auto catalysis are all terms used to describe positive feedback. Another example could be provided by the clustering or aggregation of individuals. Many birds, such as seagulls nest in large colonies. Group nesting evidently provides individuals with certain benefits, such as better detection of predators or greater ease in finding food. The mechanism in this case is imitation : birds preparing to nest are attracted to sites where other birds are already nesting, while the behavioral rule could be synthesized as “I nest close where you nest“. The key point is that aggregation of nesting birds at a particular site is not purely a consequence of each bird being attracted to the site per se. Rather, the aggregation evidently arises primarily because each bird is attracted to others. On social insect societies, f+ could be illustrated by the pheromone reinforcement on trails, allowing the entire colony to exploit some past and present solutions. Generally, as in the above cases, positive feedback is imposed implicitly on the system and locally by each one of the constituent units. Fireflies flashing in synchrony follow the rule, “I signal when you signal”, fish traveling in schools abide by the rule, “I go where you go”, and so forth. In humans, the “infectious” quality of a yawn of laughter is a familiar example of positive feedback of the form, “I do what you do“. Seeing a person yawning , or even just thinking of yawning, can trigger a yawn. There is however one associated risk, generally if f+ acts alone without the presence of negative feedbacks, which per si can play a critical role keeping under control this snowballing effect, providing inhibition to offset the amplification and helping to shape it into a particular pattern. Indeed, the amplifying nature of f+ means that it has the potential to produce destructive explosions or implosions in any process where it plays a role. Thus the behavioral rule may be more complicated than initially suggested, possessing both an autocatalytic as well as an antagonistic aspect. In the case of fish, the minimal behavioral rule could be “I nest where others nest, unless the area is overcrowded“. In this case both the positive and negative feedback may be coded into the behavioral rules of the fish. Finally, in other cases one finds that the inhibition arises automatically, often simply from physical constraints. Since in SO systems their organization arises entirely from multiple interactions, it is of critical importance to question how organisms acquire and act upon information. Basically through two forms: a) information gathered from one’s neighbors, and b) information gathered from work in progress, that is, stigmergy. In the case of animal groups, these internal interactions typically involve information transfers between individuals. Biologists have recently recognized that information can flow within groups via two distinct pathways – signals and cues. Signals are stimuli shaped by natural selection specifically to convey information, whereas cues are stimuli that convey information only incidentally. The distinction between signals and cues is illustrated by the difference ant and deer trails. The chemical trail deposited by ants as they return from a desirable food source is a signal. Over evolutionary time such trails have been molded by natural selection for the purpose of sharing with nestmates information about the location of rich food sources. In contrast, the rutted trails made by deer walking through the woods is a cue, not shaped by natural selection for communication among deer but are a simple by-product of animals walking along the same path. SO systems are based on both, but whereas signals tends to be conspicuous, since natural selection has shaped signals to be strong and effective displays, information transfer via cues is often more subtle and based on incidental stimuli in an organism’s social environment. […], in Social Cognitive Maps, Swarm Collective Perception and Distributed Search on Dynamic Landscapes.
Stick Me! sticker in plain nature over Aljezur, Algarve (South of Portugal). Unknow author. "Copyrigthed nature" or a way of saying "I was here. I am connected. You could also be connected. We are all connected" ?!
Chemoton § Vitorino Ramos' research notebook 
Recent Comments