You are currently browsing the tag archive for the ‘Co-Evolution’ tag.
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.
“… words are not numbers, nor even signs. They are animals, alive and with a will of their own. Put together, they are invariably less or more than their sum. Words die in antisepsis. Asked to be neutral, they display allegiances and stubborn propensities. They assume the color of their new surroundings, like chameleons; they perversely develop echoes.” Guy Davenport, “Another Odyssey”, 1967. [above: painting by Mark Rothko – untitled]
“Now, here, you see, it takes all the running you can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that!” ~ The Red Queen, at “Through the looking-glass, and what Alice found there“, Charles Lutwidge Dogson, 1871.
Your move. Alice was suddenly found in a new strange world. And quickly needed to adapt. As C.L. Dogson (most known as Lewis Carroll) brilliantly puts it, all the running you can do, does not suffices at all. This is a world (Wonderland) with different “physical” laws or “societal norms”. Surprisingly, those patterns appear also to us quite familiar, here, on planet Earth. As an example, the quote above is mainly the paradigm for Biological Co-Evolution, in the form of the Red-Queen effect.
In Wonderland (1st book), Alice follows the white rabbit, which end-ups driving her on this strange habitat, where apparently “normal” “physical” laws do not apply. On this second book however, Alice now needs to overcome a series of great obstacles – structured as phases in a game of chess – in order to become a queen. Though, as she moves on, several other enigmatic personages appear. Punctuated as well as surrounded by circular arguments and logical paradoxes, Alice must keep on, in order to found the “other side of the mirror“.
There are other funny parallel moves, also. The story goes on that Lewis Carroll gave a copy of “Alice in Wonderland” to Queen Victoria who then asked him in return to send her his next book as she fancied the first one. The joke is that the book was (!) … “An Elementary Treatise on Determinants, With Their Application to Simultaneous Linear Equations and Algebraic Equations (link)”. Lewis Carroll then went on to write a follow-on to Alice in Wonderland entitled “Through the Looking-Glass, and what Alice found there” that features a chess board on his first pages, and where chess was used to gave her, Queen Victoria, a glimpse on what Alice explored on this new world.
In fact, the diagram on the first pages contains not only the entire book chapters of this novel as well how Alice moved on. Where basically, each move, moves the reader to a new chapter (see below) representing it. The entire book could be found here in PDF format. Besides the beauty and philosophical value of Dogson‘s novel on itself, and his repercussions on nowadays co-Evolution research as a metaphor, this is much probably the first “chess-literature” diagram ever composed. Now, of course, pieces are not white and black, but instead white and red (note that pieces in c1 – queen – and c6 – king – are white). Lewis Carroll novel, then goes on like this: White pawn (Alice) to play, and win in eleven moves.
However, in order to enter this world you must follow the “rules” of this new world. “Chess” in here is not normal, as Wonderland was not normal to Alice’s eyes. Remember: If you do all do run you could do, you will find yourself at the same place. Better if you could run twice as fast! First Lewis Carroll words on his second book (at the preface / PDF link above) advise us:
(…) As the chess-problem, given on a previous page, has puzzled some of my readers, it may be well to explain that it is correctly worked out, so far as the moves are concerned. The alternation of Red and White is perhaps not so strictly observed as it might be, and the ‘castling’ of the three Queens is merely a way of saying that they entered the palace; but the ‘check’ of the White King at move 6, the capture of the Red Knight at move 7, and the final ‘check-mate’ of the Red King, will be found, by any one who will take the trouble to set the pieces and play the moves as directed, to be strictly in accordance with the laws of the game. (…) Lewis Carroll, Christmas,1896.
Now, the solution, could be delivered in various format languages. But here is one I prefer. It was encoded on classic BASIC, running on a ZX Spectrum emulator. Here is an excerpt:
1750 LET t$=”11. Alice takes Red Queen & wins(checkmate)”: GO SUB 7000 (…)
9000 REM
9001 REM ** ZX SPECTRUM MANUAL Page 96 Chapter 14. **
9002 REM
9004 RESTORE 9000 (…)
9006 LET b=BIN 01111100: LET c=BIN 00111000: LET d=BIN 00010000
9010 FOR n=1 TO 6: READ p$: REM 6 pieces
9020 FOR f=0 TO 7: REM read piece into 8 bytes
9030 READ a: POKE USR p$+f,a
9040 NEXT f
9100 REM bishop
9110 DATA “b”,0,d,BIN 00101000,BIN 01000100
9120 DATA BIN 01101100,c,b,0
9130 REM king
9140 DATA “k”,0,d,c,d
9150 DATA c,BIN 01000100,c,0
9160 REM rook
9170 DATA “r”,0,BIN 01010100,b,c
9180 DATA c,b,b,0
9190 REM queen
9200 DATA “q”,0,BIN 01010100,BIN 00101000,d
9210 DATA BIN 01101100,b,b,0
9220 REM pawn
9230 DATA “p”,0,0,d,c
9240 DATA c,d,b,0
9250 REM knight
9260 DATA “n”,0,d,c,BIN 01111000
9270 DATA BIN 00011000,c,b,0
(…) full code on [link]
This is BASIC-ally Alice’s story …
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).
“If you want to be incrementally better: Be competitive. If you want to be exponentially better: Be cooperative“. ~ Anonymous
Two hunters decide to spent their week-end together. But soon, a dilemma emerges between them. They could choose for hunting a deer stag together or either -individually- hunt a rabbit on their own. Chasing a deer, as we know, is something quite demanding, requiring absolute cooperation between them. In fact, both friends need to be focused for a long time and in position, while not being distracted and tempted by some arbitrary passing rabbits. On the other hand, stag hunt is increasingly more beneficiary for both, but that benefice comes with a cost: it requires a high level of trust between them. Somehow at some point, each hunter concerns that his partner may diverts while facing a tempting jumping rabbit, thus jeopardizing the possibility of hunting together the biggest prey.
The original story comes from Jean Jacques Rousseau, French philosopher (above). While, the dilemma is known in game theory has the “Stag Hunt Game” (Stag = adult deer). The dilemma could then take different quantifiable variations, assuming different values for R (Reward for cooperation), T (Temptation to defect), S (Sucker’s payoff) and P (Punishment for defection). However, in order to be at the right strategic Stag Hunt Game scenario we should assume R>T>P>S. A possible pay-off table matrix taking in account two choices C or D (C = Cooperation; D = Defection), would be:
Choice — C ——- D ——
C (R=3, R=3) (S=0, T=2)
D (T=2, S=0) (P=1, P=1)
Depending on how fitness is calculated, stag hunt games could also be part of a real Prisoner’s dilemma, or even Ultimatum games. As clear from above, highest pay-off comes from when both hunters decide to cooperate (CC). Over this case (first column – first row), both receive a reward of 3 points, that is, they both really focused on hunting a big deer while forgetting everything else, namely rabbits. However – and here is where exactly the dilemma appears -, both CC or DD are Nash equilibrium! That is, at this strategic landscape point no player has anything to gain by changing only his own strategy unilaterally. The dilemma appears recurrently in biology, animal-animal interaction, human behaviour, social cooperation, over Co-Evolution, in society in general, and so on. Philosopher David Hume provided also a series of examples that are stag hunts, from two individuals who must row a boat together up to two neighbours who wish to drain a meadow. Other stories exist with very interesting variations and outcomes. Who does not knows them?!
The day before last school classes, two kids decided to do something “cool”, while conjuring on appearing before their friends on the last school day period, both with mad and strange haircuts. Although, despite their team purpose, a long, anguish and stressful night full of indecisiveness followed for both of them…
“It is not the strongest of the species that survives, nor the most intelligent that survives. It is the one that is the most adaptable to change“. Charles Darwin (On the Origin of Species, Nov. 1859)
During the Victorian era where high prudery and morality were constant, it would be hard to imagine seeing Charles Darwin wearing a Scottish-kilt. In fact, men’s formal clothing was less colourful than it was in the previous century, while women’s tight-fitting jersey dresses of the 1880s covered the body, leaving little to the imagination (source). There is however, one beautiful – as in strict sense of delighting the senses for exciting intellectual or emotional admiration – reason, I think he should have done it (!), regardless the obvious bearing consequences of a severe Victorian society. Surprisingly, some how, that reason is linked to cheetahs chasing gazelles, among many other things…
As the image of Charles Darwin wearing a kilt, you will probably find these awkward too, but when a cheetah chases a gazelle, banded tartan Scottish-kilt woven textile like patterns soon start to pop-up everywhere. Not at the ground terrain level, of course. Instead, they appear as a phenotype-like map between your present and the past. You may think that this banded tartans will have no significance for your life, but do mind this: crying babies do it all the time with their mommy’s and fathers, companies do it with other companies in their regular business, people commuting in large cities do it over large highways, human language, literature and culture does it, friends do it, PC virus and anti-virus software do it, birds singing do it also, … and even full countries at war do it.
One extreme example is the Cold War, where for the first time on our Human history, co-evolutionary arms-race raised to unprecedented levels. Co-Evolution is indeed the right common key-word for all these phenomena, while large white banded strips punctuated by tiny black ones (bottom-left woven kilt above), would be the perfect correspondent tartan pattern for the case of the Cold War example mentioned. But among these, there is of course, much more Scottish-kilt like patterns we could find. Ideas, like over this TV ad above, co-evolve too. Here, the marketeer decided to co-evolve with a previous popular famous meme image: Sharon Stone crossing his legs at the 1992 ‘Basic Instinct‘ movie. In fact, there is an authentic plethora of different possible behavioural patterns. Like a fingerprint (associated with different Gaelic clans), each of these patterns correspond to a lineage of current versus ancestral strategies, trying to solve a specific problem, or achieving one precise goal. But as the strategic landscape is dynamically changing all the time, a good question is, how can we visualize it. And, above all, what vital information and knowledge could we retrieve from this evolutionary Scottish-kilts maps.
Fig. – The frontispiece drawing to the English edition of Ernst Haeckel‘s Evolution of Man (trans. 1903) presents a skull labelled “Australian Negro” as an intervening evolutionary stage between the “Mediterranean” skull and those of the lower primates (from the 1891 ed. of the Anthropogenie).
In nature, organisms and species coexist in an ecosystem, where each species has its own place or niche in the system. The environment contains a limited number and amount of resources, and the various species must compete for access to those resources, where successive adaptations in one group put pressure on another group to catch up (e.g., the coupled phenomena of speed in the cheetah and evasive agility in the gazelle). Through these interactions, species grow and change, each influencing the others evolutionary development [7]. This process of bi-adaptive relationship (in some cases can also assume a form of cooperation and mutualism) or reciprocal adaptation is know as Co-evolution, i.e. the evolution of two or more competing populations with coupled fitness.
The phenomena has several interesting features that may potentially enhance the adaptive power of artificial evolution [7], or other types of bio-inspired learning systems. In particular, competing populations may reciprocally drive one another to increasing levels of complexity by producing an evolutionary “arms race”, where each group may become bigger, faster, more lethal, more intelligent, etc. Co-Evolution can then happen either between a learner (e.g., single population) and its environment (i.e. based on competitions among individuals in the population) or between learning species (two populations evolving), where the fitness of individuals is based on their behaviour in the context of the individuals of the other population [7]. This latter type of co-evolutionary search is often described as “host-parasite”, or “predator-prey” co-evolution. A good example and application of co-evolutionary learning include the pioneering work by Hillis in 1990 [1] on sorting networks.
It can occur at multiple levels of biology: it can be as microscopic as correlated mutations between amino acids in a protein, or as macroscopic as co-varying traits between different species in an environment. Being biological Co-Evolution, in a broad sense, “the change of a biological object triggered by the change of a related object” [2], his visualization however, could be profoundly hard. In fact, attempting to define and monitor “progress” in the context of Co-Evolutionary systems can be a somewhat nightmarish experience , as stated in [4]. It’s exactly here where Scottish-kilts come into play.
In 1995 [3], two researchers had a simple, yet powerful idea. In order to monitor the dynamics of artificial competitive co-evolutionary systems between two populations, Dave Cliff and Geoffrey Miller [3,4,5] proposed evaluating the performance of an individual from the current population in a series of trials against opponents from all previous generations. while visualizing the results as 2D grids of shaded cells or pixels: qualitative patterns in the shading can thus indicate different classes of co-evolutionary dynamic. Since their technique involves pitting a Current Individual (CI) against Ancestral Opponents (AO), they referred to the visualizations as CIAO plots (fig. above [3]).
Important Co-Evolutionary dynamics such as limited evolutionary memory, “Red Queen” effects or intransitive dominance cycling, will then be revealed like a fingerprint as certain qualitative patterns. Dominance cycling, for instance, it’s a major factor on Co-Evolution, wish could appear or not, during the entire co-evolutionary process. Imagine, for instance, 3 individuals (A,B,C) or strategies. Like over the well known “Rock, Paper, Scissors” game, strategy B could beat strategy A, strategy C could beat B, and strategy A could beat C, over and over in an eternal cycling, where only “arms race” specialized learning will emerge, at the cost of a limited learning generalization against a possible fourth individual-strategy D. If you play poker, you certainly know what I am talking about, since 2 poker players are constantly trying to broke this behavioural cycle, or entering it, depending on their so-far success.
Above (left and right figures – [3]), two idealised typical CIAO plot patterns can be observed, where darker shading denotes higher scores. On the left figure, however, co-evolutionary intransitive dominance cycling is a constant, where current elites (population A elites) score highly against population B opponents from 3, 8 and 13 generations ago, but not so well against generations in between. On the other hand (right figure), the behavioural pattern is completely different: over here we do observe limited evolutionary memory, where the current elites do well against opponents from 3,4 and 5 generations ago, but much less well against more distant ancestral opponents.
“For to win one hundred victories in one hundred battles is not the acme of skill. To subdue the enemy without fighting is the acme of skill.” ~ Sun Tzu
Of course, in increasingly complex real-world situations Scottish-kilt like CIAO plots are much noisy than this (fig. above -[7]) where banded tartans could be less prominent, while the same could happen in irregular dominance cycling as elegantly showed by Cartlidge and Bullock in 2004 [6]. Above, some of my own experiences can be observed (submitted work). Over here I decided to co-evolve a AI agent strategy to play against a pool of 15 different strategies (6 of those confronts are presented above), and as a result, 6 different behavioural patterns emerged between them. All in all, the full spectrum of co-evolving dynamics could be observed, from the “Red Queen” effect, till alternate dominant cycles, and limited or long evolutionary memory. Even if some dynamics seem counter-productive in one-by-one confronts, in fact, all of these dynamics are useful in some way, as when you play Poker or the “Rock, Paper, Scissors” game. A typical confront between game memory (exploitation) and the ability to generalize (exploration). Where against precise opponents limited evolutionary memory was found, the same effect produced dominant cycles or long evolutionary memory against other strategies. The idea of course, is not to co-evolve a super-strategy to win all one-by-one battles (something that would be rather impossible; e.g. No free Lunch Theorem) but instead to win the whole round-robin tournament, by being highly adaptive and/or exaptive.
So next time you see someone wearing a banded tartan Scottish-kilt do remind yourself that, while getting trapped in traffic, that precise pattern could be the result of your long year co-evolved strategies to find the quickest way home, while confronting other commuters doing the same. And that, somewhere, somehow, Charles Darwin is envying your observations…
.
[1] W. Daniel Hillis (1990), “Co-Evolving Parasites improve Simulated Evolution as an Optimization Procedure”, Physica D, Vol. 42, pp. 228-234 (later in, C. Langton et al. (Eds.) (1992), Procs. Artificial Life II, Addison-Welsey, pp. 313-324).
[2] Yip et al.; Patel, P; Kim, PM; Engelman, DM; McDermott, D; Gerstein, M (2008). “An integrated system for studying residue Coevolution in Proteins“. Bioinformatics 24 (2): 290-292. doi:10.1093/bioinformatics/btm584. PMID 18056067.
[3] Dave Cliff, Geoffrey F. Miller, (1995), “Tracking the Red Queen: Methods for measuring co-evolutionary progress in open-ended simulations“. In F. Moran, A. Moreno, J. J. Merelo, & P. Cachon (Eds.), Advances in artificial life: Proceedings of the Third European Conference on Artificial Life (pp. 200-218). Berlin: Springer-Verlag.
[4] Dave Cliff, Geoffrey F. Miller, (2006), “Visualizing Co-Evolution with CIAO plots“, Artificial Life, 12(2), 199-202
[5] Dave Cliff, Geoffrey F. Miller (1996). “Co-evolution of pursuit and evasion II: Simulation methods and results“. In P. Maes, M. J. Mataric, J.-A. Meyer, J. Pollack, & S. W. Wilson (Eds.), From Animals to Animats 4: Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior (pp. 506-515). Cambridge, MA: MIT Press.
[6] Cartlidge, J. and Bullock S., (2004), “Unpicking Tartan CIAO plots: Understanding irregular Co-Evolutionary Cycling“, Adaptive Behavior Journal, 12: 69-92, 2004.
[7] Ramos, Vitorino, (2007), “Co-Cognition, Neural Ensembles and Self-Organization“, extended abstract for a seminar talk at ISR – Institute for Systems and Robotics, Technical Univ. of Lisbon (IST), Lisbon, PORTUGAL. May 31, 2007.
Video – Awesome choice by Tim Burton. It fits him like a glove. Here is the official Tim Burton’s Alice in Wonderland teaser trailer (just uploaded yesterday). Alice in Wonderland is directed by visionary director Tim Burton, of everything from Pee-Wee’s Big Adventure to Beetlejuice to Batman to Edward Scissor hands to Mars Attacks to Sleepy Hollow to Charlie and the Chocolate Factory to Sweeney Todd most recently. This is based on Lewis Carroll’s beloved series of books that were first published in 1865. Disney is bringing Tim Burton’s Alice in Wonderland to both digital 3D and 2D theaters everywhere on March 5th, 2010 early next year (more). Finally, just one personal thought. Soon, Tim Burton’s will stand for cinema, as what Jules Verne represented in literature.
In 1973, under several ongoing works on Co-Evolution and Evolutionary theory, L. van Alen proposed a new hypothesis: the Red Queen effect [1]. According to him, several different species will migth propably undergo and submit themselves to a continuous re-adapation [2,3], being it genetic or synaptic, only to end themselves at the point they started. A kind of arms races between species [4], potentially leading to specialization, as well as evolutionary Punctuated equilibria [5,6].
Van Alen chose the name “Red Queen” in allusion to the romance “Alice in Wonderland”, from Charles Lutwidge Dodgson (better known as Lewis Carroll) published in 1865. Over this country (Wonderland) it was usual to run as quick as you could, just to end yourself at the same place. The dialogs between Alice and the Red Queen are sintomatic:
[…] ‘Now! Now!’ cried the Queen. ‘Faster! Faster!’ And they went so fast that at last they seemed to skim through the air, hardly touching the ground with their feet, till suddenly, just as Alice was getting quite exhausted, they stopped, and she found herself sitting on the ground, breathless and giddy. The Queen propped her up against a tree, and said kindly, ‘You may rest a little, now. Alice looked round her in great surprise. ‘Why, I do believe we’ve been under this tree the whole time! Everything’s just as it was!’ ‘Of course it is,’ said the Queen. ‘What would you have it?’. ‘Well, in our country, said Alice, still panting a little, ‘you’d generally get to somewhere else – if you ran very fast for a long time as we’ve been doing.’ ‘A slow sort of country!’ said the Queen. ‘Now, here, I see, it takes all the running you can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that!‘ […]
Meanwhile, since 2007 (even much earlier!) I have taken Alice into my own arms. In fact, she is not heavy at all. If you feel you should keep running, some should, have a read on “Co-Cognition, Neural Ensembles and Self-Organization“, extended abstract for a seminar talk at ISR – Institute for Systems and Robotics, Technical Univ. of Lisbon (IST), May 31, 2007. Written at Granada University, Spain, 29 May 2007.
[1] van Alen, L. (1973), “A New Evolutionary Law“, Evolutionary Theory, 1, pp. 1-30.
[2] Cliff D., Miller G.F. (1995), “Tracking the Red Queen: Measurements of Adaptive Progress in Co-Evolutionary Simulations“, in F. Moran, A. Moreno, J.J. Merelo and P. Cachon (editors) Advances in Artificial Life: Proceedings of the Third European Conference on Artificial Life (ECAL95). Lecture Notes in Artificial Intelligence 929, Springer- Verlag, pp.200-218.
[3] Cliff D., Miller G.F. (1996), “Co-Evolution of Pursuit and Evasion II: Simulation Methods and Results“. In P. Maes et al. (Eds.), From Animals to Animats IV, Procs. of the Fourth Int. Conf. on Simulation of Adaptive Behaviour, MIT Press, pp. 506-515.
[4] Dawkins R., Krebs J.R. (1979), “Arms Races between and within Species“. In Procs. of the Royal Society of London: Biological Sciences, nº. 205, pp. 489-511.
[5] Eldredge, N., Gould, S. J., “Punctuated equilibria: an alternative to phyletic gradualism“. In: Models In Paleobiology (Ed. by T. J. M. Schopf), 1972.
[6] Gould, S. J., & Eldredge, N., “Punctuated equilibria: the tempo and mode of evolution reconsidered“. Paleobiology, 3, 115-151, 1977.
Chemoton § Vitorino Ramos' research notebook 
Recent Comments