You are currently browsing the tag archive for the 'Artificial Life' tag.
[...] … I do not really believe that we shall succeed in creating life artificially; but after having reached the moon and landed a spaceship or two on Mars, I realize that this disbelief of mine means very little. But computers are totally different from brains, whose function is not primarily to compute but to guide and balance an organism and help it to stay alive. It is for this reason that the first step of nature toward an intelligent mind was the creation of life, and I think that should we artificially create an intelligent mind, we would have to follow the same path. [...], Karl Popper – Popper, K. R. and Eccles, J. C. (1983), The Self and its Brain: An Argument for Interactionism, Routledge & Kegan Paul plc, London.
On Bilateral Monopolies: [...] Mary has the world’s only apple, worth fifty cents to her. John is the world’s only customer for the apple, worth a dollar to him. Mary has a monopoly on selling apples, John has a monopoly (technically, a monopsony, a buying monopoly) on buying apples. Economists describe such a situation as bilateral monopoly. What happens? Mary announces that her price is ninety cents, and if John will not pay it, she will eat the apple herself. If John believes her, he pays. Ninety cents for an apple he values at a dollar is not much of a deal but better than no apple. If, however, John announces that his maximum price is sixty cents and Mary believes him, the same logic holds. Mary accepts his price, and he gets most of the benefit from the trade. This is not a fixed-sum game. If John buys the apple from Mary, the sum of their gains is fifty cents, with the division determined by the price. If they fail to reach an agreement, the summed gain is zero. Each is using the threat of the zero outcome to try to force a fifty cent outcome as favorable to himself as possible. How successful each is depends in part on how convincingly he can commit himself, how well he can persuade the other that if he doesn’t get his way the deal will fall through. Every parent is familiar with a different example of the same game. A small child wants to get her way and will throw a tantrum if she doesn’t. The tantrum itself does her no good, since if she throws it you will refuse to do what she wants and send her to bed without dessert. But since the tantrum imposes substantial costs on you as well as on her, especially if it happens in the middle of your dinner party, it may be a sufficiently effective threat to get her at least part of what she wants. Prospective parents resolve never to give in to such threats and think they will succeed. They are wrong. You may have thought out the logic of bilateral monopoly better than your child, but she has hundreds of millions of years of evolution on her side, during which offspring who succeeded in making parents do what they want, and thus getting a larger share of parental resources devoted to them, were more likely to survive to pass on their genes to the next generation of offspring. Her commitment strategy is hardwired into her; if you call her bluff, you will frequently find that it is not a bluff. If you win more than half the games and only rarely end up with a bargaining breakdown and a tantrum, consider yourself lucky.
Herman Kahn, a writer who specialized in thinking and writing about unfashionable topics such as thermonuclear war, came up with yet another variant of the game: the Doomsday Machine. The idea was for the United States to bury lots of very dirty thermonuclear weapons under the Rocky Mountains, enough so that if they went off, their fallout would kill everyone on earth. The bombs would be attached to a fancy Geiger counter rigged to set them off if it sensed the fallout from a Russian nuclear attack. Once the Russians know we have a Doomsday Machine we are safe from attack and can safely scrap the rest of our nuclear arsenal. The idea provided the central plot device for the movie Doctor Strangelove. The Russians build a Doomsday Machine but imprudently postpone the announcement they are waiting for the premier’s birthday until just after an American Air Force officer has launched a unilateral nuclear attack on his own initiative. The mad scientist villain was presumably intended as a parody of Kahn. Kahn described a Doomsday Machine not because he thought we should build one but because he thought we already had. So had the Russians. Our nuclear arsenal and theirs were Doomsday Machines with human triggers. Once the Russians have attacked, retaliating does us no good just as, once you have finally told your daughter that she is going to bed, throwing a tantrum does her no good. But our military, knowing that the enemy has just killed most of their friends and relations, will retaliate anyway, and the knowledge that they will retaliate is a good reason for the Russians not to attack, just as the knowledge that your daughter will throw a tantrum is a good reason to let her stay up until the party is over. Fortunately, the real-world Doomsday Machines worked, with the result that neither was ever used.
For a final example, consider someone who is big, strong, and likes to get his own way. He adopts a policy of beating up anyone who does things he doesn’t like, such as paying attention to a girl he is dating or expressing insufficient deference to his views on baseball. He commits himself to that policy by persuading himself that only sissies let themselves get pushed around and that not doing what he wants counts as pushing him around. Beating someone up is costly; he might get hurt and he might end up in jail. But as long as everyone knows he is committed to that strategy, other people don’t cross him and he doesn’t have to beat them up. Think of the bully as a Doomsday Machine on an individual level. His strategy works as long as only one person is playing it. One day he sits down at a bar and starts discussing baseball with a stranger also big, strong, and committed to the same strategy. The stranger fails to show adequate deference to his opinions. When it is over, one of the two is lying dead on the floor, and the other is standing there with a broken beer bottle in his hand and a dazed expression on his face, wondering what happens next. The Doomsday Machine just went off. With only one bully the strategy is profitable: Other people do what you want and you never have to carry through on your commitment. With lots of bullies it is unprofitable: You frequently get into fights and soon end up either dead or in jail. As long as the number of bullies is low enough so that the gain of usually getting what you want is larger than the cost of occasionally having to pay for it, the strategy is profitable and the number of people adopting it increases. Equilibrium is reached when gain and loss just balance, making each of the alternative strategies, bully or pushover, equally attractive. The analysis becomes more complicated if we add additional strategies, but the logic of the situation remains the same.
This particular example of bilateral monopoly is relevant to one of the central disputes over criminal law in general and the death penalty in particular: Do penalties deter? One reason to think they might not is that the sort of crime I have just described, a barroom brawl ending in a killing more generally, a crime of passion seems to be an irrational act, one the perpetrator regrets as soon as it happens. How then can it be deterred by punishment? The economist’s answer is that the brawl was not chosen rationally but the strategy that led to it was. The higher the penalty for such acts, the less profitable the bully strategy. The result will be fewer bullies, fewer barroom brawls, and fewer “irrational” killings. How much deterrence that implies is an empirical question, but thinking through the logic of bilateral monopoly shows us why crimes of passion are not necessarily undeterrable. [...]
in Chapter 8, David D. Friedman, “Law’s Order: What Economics Has to Do With Law and Why it Matters“, Princeton University Press, Princeton, New Jersey, 2000.
Note – Further reading should include David D. Friedman’s “Price Theory and Hidden Order“. Also, a more extensive treatment could be found on “Game Theory and the Law“, by Douglas G. Baird, Robert H. Gertner and Randal C. Picker, Cambridge, Mass: Harvard University Press, 1994.
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.
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.
Fig. – Knight, Death and the Devil (1513). This is one of three metal engravings by Albrecht Dürer in a series called Meisterstiche (since I have started this blog, I have also chosen a woodcut engraving done by Dürer, – his Rhinoceros – for several reasons, one being that it appeared in Europe for the fisrt time trough Lisbon in 1515). The others are Melancholia I and Saint Jerome in His Study. The engraving is dated 1513, two hundred years after the dissolution of the Knights Templar in 1313. We see a skull in the bottom left corner; the night in full armour (shining armor?) carries a lance; behing him is a pig-snouted horned devil and he is passing Death on his pale horse, who is carrying an hourglass. Under the knight’s horse runs a long-haired retriever, a hunting dog. Dürer called this picture Reuter, which is, Rider. (source).
“Every evil leaves a sorrow in the memory, until the supreme evil, death,
wipes out all memories together with all life“. Leonardo da Vinci.
Carlos Gershenson (Complexes blog), some days ago just uploaded a short (5 pp.) philosophical essay about life, death and artificial life (*) (aLife), which I vividly recommend. He starts his “What Does Artificial Life Tell Us About Death?” with this precise Leonardo’s quote (above). Among other passages it’s interesting to see how different notions of death are deduced from a limited set of different notions of life (in many situations, opposing terms could be used to define each other). Carlos points us out to six currents, or lines of thought:
• If we consider life as self-production (Varela et al., 1974; Maturana and Varela, 1980, 1987; Luisi, 1998), then death will the the loss of that self-production ability.
• If we consider life as what is common to all living beings (De Duve, 2003, p. 8), then death implies the termination of that commonality, distinguishing it from other living beings.
• If we consider life as computation (Hopfield, 1994), then death will be the end (halting?) of that computing process.
• If we consider life as supple adaptation (Bedau, 1998), death implies the loss of that adaptation.
• If we consider life as a self-reproducing system capable of at least one thermodynamic work cycle (Kauffman, 2000, p. 4), death will occur when the system will be unable to perform thermodynamic work.
• If we consider life as information (a system) that produces more of its own information than that produced by its environment (Gershenson, 2007), then death will occur when the environment will produce more information than that produced by the system.
I was aware of Kauffman’s “blender thought experiment”, however Gershenson adds much more into it. A variation. He goes on like this. Nice reading:
[...] Focussing on our understanding of death, this will depend necessarily on our understanding of life, and vice versa. Throughout history there have been several explanations to both life and death, and it seems unfeasible that a consensus will be reached. Thus, we are faced with multiple notions of life, which imply different notions of death. However, generally speaking, if we describe life as a process, death can be understood as the irreversible termination of that process. The general notion of life as a process or organization (Langton, 1989; Sterelny and Griffiths, 1999; Korzeniewski, 2001) has expelled vitalism from scientific worldviews. Moreover, there are advantages in describing living systems from a functional perspective, e.g. it makes the notion of life independent of its implementation. This is crucial for artificial life. Also, we know that there is a constant flow of matter and energy in living systems, i.e. their physical components can change while the identity of the organism is preserved. In this respect, one can make a variation of Kauffman’s “blender thought experiment” (Kauffman, 2000): if you put a macroscopic living system in a blender and press “on”, after some seconds you will have the same molecules that the living system had. However, the organization of the living system is destroyed in the blending. Thus, life is an organizational aspect of living systems, not so much a physical aspect. Death occurs when this organization is lost. [...]
(*) even if, I do not recommend this Wikipedia entry. Extremely poor.
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.
Abraham, Ajith; Grosan, Crina; Ramos, Vitorino (Eds.), Stigmergic Optimization, Studies in Computational Intelligence (series), Vol. 31, Springer-Verlag, ISBN: 3-540-34689-9, 295 p., Hardcover, 2006.
TABLE OF CONTENTS (short /full) / CHAPTERS:
[1] Stigmergic Optimization: Foundations, Perspectives and Applications.
[2] Stigmergic Autonomous Navigation in Collective Robotics.
[3] A general Approach to Swarm Coordination using Circle Formation.
[4] Cooperative Particle Swarm Optimizers: a powerful and promising approach.
[5] Parallel Particle Swarm Optimization Algorithms with Adaptive
Simulated Annealing.
[6] Termite: a Swarm Intelligent Routing algorithm for Mobile
Wireless ad-hoc Networks.
[7] Linear Multiobjective Particle Swarm Optimization.
[8] Physically realistic Self-Assembly Simulation system.
[9] Gliders and Riders: A Particle Swarm selects for coherent Space-time Structures in Evolving Cellular Automata.
[10] Stigmergic Navigation for Multi-agent Teams in Complex Environments.
[11] Swarm Intelligence: Theoretical proof that Empirical techniques are Optimal.
[12] Stochastic Diffusion search: Partial function evaluation in Swarm Intelligence Dynamic Optimization.
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. (…)
[] Crina Grosan, Ajith Abraham, Sang Yong Han, Vitorino Ramos, Stock Market Prediction using Multi Expression Programming, in ALEA´05, Workshop on Artificial Life and Evolutionary Algorithms at EPIA´05 – Proc. of the 12th Portuguese Conference on Artificial Intelligence, C. Bento, A. Cardoso and G. Dias (Eds.), IEEE Press, pp. 73-78, 2005.
The use of intelligent systems for stock market predictions has been widely established. In this paper we introduce a genetic programming technique (called Multi-Expression programming) for the prediction of two stock indices. The performance is then compared with an artifcial neural network trained using Levenberg-Marquardt algorithm, support vector machine, Takagi-Sugeno neuro-fuzzy model, a difference boosting neural network. We considered Nasdaq-100 index of Nasdaq Stock MarketSM and the S&P CNX NIFTY stock index as test data.
(to obtain the respective PDF file follow link above or visit chemoton.org)
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" ?!
Transition behavior of one Artificial Ant Colony in presence of a sudden change in his artificial digital image Habitat, between two different Digital Grey Images (face of Einstein and a Map). Created with an Artificial Ant Colony, that uses images as Habitats, being sensible to their gray levels [in, V. Ramos, F. Almeida, "Artificial Ant Colonies in Digital Image Habitats - a mass behavior effect study on Pattern Recognition", ANTS'00 Conf., Brussels, Belgium, 2000].
After “Einstein face” is injected as a substrate at t=0, 100 iterations occur. At this point you could recognize the face. Then, a new substrate (a new “environmental condition”) is imposed (Map image). The colony then adapts quickly to this new situation, losing their collective memory of past contours.
In white, the higher levels of pheromone (a chemical evaporative sugar substance used by swarms on their orientation trough out the trails). It’s exactly this artificial evaporation and the computational ant collective group synergy reallocating their upgrades of pheromone at interesting places, that allows for the emergence of adaptation and “perception” of new images. Only some of the 6000 iterations processed are represented. The system does not have any type of hierarchy, and ants communicate only in indirect forms, through out the successive alteration that they found on the Habitat. If you however, inject Einstein image again as a substrate, the whole ant society will converge again to it, but much faster than the first time, due to the residual memory distributed in the environment.
As a whole, the system is constantly trying to establish a proper compromise between memory (past solutions – via pheromone reinforcement) and novel ones in order to adapt (new conditions on the habitat, through pheromone evaporation). The right compromise, ables the system to tackle two contradictory situations: keeping some memory while learning something radically new. Antagonist features such as exploration and exploitation are tackled this way.
Figure – From top left to bottom right, a sequential data-items clustering task performed by an artificial ant colony. The system is able to cope with unforeseen data items in real-time, that is, as data appears in a continuous basis over a large period of time. Also, as time evolves, spatial entropy decreases.
[] Vitorino Ramos, Ajith Abraham, Swarms on Continuous Data, in CEC´03 – Congress on Evolutionary Computation, IEEE Press, ISBN 078-0378-04-0, pp.1370-1375, Canberra, Australia, 8-12 Dec. 2003.
While being it extremely important, many Exploratory Data Analysis (EDA) systems have the inability to perform classification and visualization in a continuous basis or to self-organize new data-items into the older ones (even more into new labels if necessary), which can be crucial in KDD – Knowledge Discovery, Retrieval and Data Mining Systems (interactive and online forms of Web Applications are just one example). This disadvantage is also present in more recent approaches using Self-Organizing Maps. On the present work, and exploiting past successes in recently proposed Stigmergic Ant Systems a robust online classifier is presented, which produces class decisions on a continuous stream data, allowing for continuous mappings. Results show that increasingly better results are achieved, as demonstrated by other authors in different areas.
(to obtain the respective PDF file follow link above or visit chemoton.org)
Springer book “Swarm Intelligence in Data Mining” (Studies in Computational Intelligence Series, Vol. 34) published in late 2006, is receiving a fair amount of attention, so much so, that early this year, Tokyo Denki University press (TDU) decided to negotiate with Springer the translation rights and copyrights in order to released it over their country in Japanese language. The Japanese version will now become shortly available, and I do hope – being one of the scientific editors – it will receive increasing attention as well in Japan, being it one of the most difficult and extraordinary real-world areas we could work nowadays among computer science. Multiple Sequence Alignment (MSA) within Bio-informatics is just one recent example, Financial Markets another. The amount of data – 100000 DVD’s every year -, CERN’s Large Hadron Collider (LHC) will collect is yet another. In order to transform data into information, and information into useful and critical knowledge, reliable and robust Data Mining is more than ever needed, on our daily life.
Meanwhile, I wonder how the Japanese cover design will be?! Starting with it’s own title, which appears to be pretty hard to translate. According to Yahoo BabelFish the Japanese characters (群れの知性) – derived among other language scripts from Kanji – correspond to the English sentence “Swarm Intelligence“. I wonder if this translation is correct or not, since “swarm” in itself, is kind of difficult to translate. Some meanings of it point out to a spaghetti dish, as well, which kind of makes some logic too. Moreover, the technical translation of it is also difficult. I guess the best person to handle the translation (at least from the list of colleagues around the world I know) is Claus Aranha. (IBA Lab., University of Tokyo). Not only he works in Japan for several years now, as well as some of his works focus this precise area.
SIDM book (Swarm Int. in Data Mining) focus on the hybridization of these two areas. As you may probably now, Data Mining (see also; Knowledge Extraction) refers to a collection of techniques – many of them classical – that envisions to tackle large amounts of data, in order to perform classification, clustering, sorting, feature selection, search, forecasting, decision, meaningful extraction, association rule discovery, sequential pattern discovery, etc. In recent years however (1985-2000), state of the art Artificial Intelligence such as Evolutionary Computation was also used, since some of his problems could be seen as – or properly translated to – optimization problems (namely, combinatorial). The same now happens with Swarm Intelligence, since some of it’s unique self-organizing distributed features (allowing direct applications over Grid Computing) seems ideal to tackle some of the most complex data mining problems we may face today.
For those willing for more, I will leave you with it’s contents (chapters), a foreword to this book by James Kennedy (one of the founding fathers of PSO - Particle Swarm Optimization, along with Russell C. Eberhart, and Yuhui Shi) which I vividly recommend (starting with the sentence “Science is a Swarm“!), as well as a more detailed description to it:
Swarm Intelligence (SI) is an innovative distributed intelligent paradigm for solving optimization problems that originally took its inspiration from the biological examples by swarming, flocking and herding phenomena in vertebrates. Particle Swarm Optimization (PSO) incorporates swarming behaviors observed in flocks of birds, schools of fish, or swarms of bees, and even human social behavior, from which the idea is emerged. Ant Colony Optimization (ACO) deals with artificial systems that is inspired from the foraging behavior of real ants, which are used to solve discrete optimization problems. Historically the notion of finding useful patterns in data has been given a variety of names including data mining, knowledge discovery, information extraction, etc. Data Mining is an analytic process designed to explore large amounts of data in search of consistent patterns and/or systematic relationships between variables, and then to validate the findings by applying the detected patterns to new subsets of data. In order to achieve this, data mining uses computational techniques from statistics, machine learning and pattern recognition. Data mining and Swarm intelligence may seem that they do not have many properties in common. However, recent studies suggests that they can be used together for several real world data mining problems especially when other methods would be too expensive or difficult to implement. This book deals with the application of swarm intelligence methodologies in data mining. Addressing the various issues of swarm intelligence and data mining using different intelligent approaches is the novelty of this edited volume. This volume comprises of 11 chapters including an introductory chapters giving the fundamental definitions and some important research challenges. Chapters were selected on the basis of fundamental ideas/concepts rather than the thoroughness of techniques deployed.
The eleven chapters are organized as follows. In Chapter 1, Grosan et al. present the biological motivation and some of the theoretical concepts of swarm intelligence with an emphasis on particle swarm optimization and ant colony optimization algorithms. The basic data mining terminologies are explained and linked with some of the past and ongoing works using swarm intelligence techniques. Martens et al. in Chapter 2 introduce a new algorithm for classification, named AntMiner+, based on an artificial ant system with inherent selforganizing capabilities. AntMiner+ differs from the previously proposed AntMiner classification technique in three aspects. Firstly, AntMiner+ uses a MAX-MIN ant system which is an improved version of the originally proposed ant system, yielding better performing classifiers. Secondly, the complexity of the environment in which the ants operate has substantially decreased. Finally, AntMiner+ leads to fewer and better performing rules. In Chapter 3, Jensen presents a feature selection mechanism based on ant colony optimization algorithm to determine a minimal feature subset from a problem domain while retaining a suitably high accuracy in representing the original features. The proposed method is applied to two very different challenging tasks, namely web classification and complex systems monitoring. Galea and Shen in the fourth chapter present an ant colony optimization approach for the induction of fuzzy rules. Several ant colony optimization algorithms are run simultaneously, with each focusing on finding descriptive rules for a specific class. The final outcome is a fuzzy rulebase that has been evolved so that individual rules complement each other during the classification process. In the fifth chapter Tsang and Kwong present an ant colony based clustering model for intrusion detection. The proposed model improves existing ant-based clustering algorithms by incorporating some meta-heuristic principles. To further improve the clustering solution and alleviate the curse of dimensionality in network connection data, four unsupervised feature extraction algorithms are also studied and evaluated. Omran et al. in the sixth chapter present particle swarm optimization algorithms for pattern recognition and image processing problems. First a clustering method that is based on PSO is discussed. The application of the proposed clustering algorithm to the problem of unsupervised classification and segmentation of images is investigated. Then PSO-based approaches that tackle the color image quantization and spectral unmixing problems are discussed.
In the seventh chapter Azzag et al. present a new model for data clustering, which is inspired from the self-assembly behavior of real ants. Real ants can build complex structures by connecting themselves to each others. It is shown is this paper that this behavior can be used to build a hierarchical tree-structured partitioning of the data according to the similarities between those data. Authors have also introduced an incremental version of the artificial ants algorithm. Kazemian et al. in the eighth chapter presents a new swarm data clustering method based on Flowers Pollination by Artificial Bees (FPAB). FPAB does not require any parameter settings and any initial information such as the number of classes and the number of partitions on input data. Initially, in FPAB, bees move the pollens and pollinate them. Each pollen will grow in proportion to its garden flowers. Better growing will occur in better conditions. After some iterations, natural selection reduces the pollens and flowers and the gardens of the same type of flowers will be formed. The prototypes of each gardens are taken as the initial cluster centers for Fuzzy C Means algorithm which is used to reduce obvious misclassification errors. In the next stage, the prototypes of gardens are assumed as a single flower and FPAB is applied to them again. Palotai et al. in the ninth chapter propose an Alife architecture for news foraging. News foragers in the Internet were evolved by a simple internal selective algorithm: selection concerned the memory components, being finite in size and containing the list of most promising supplies. Foragers received reward for locating not yet found news and crawled by using value estimation. Foragers were allowed to multiply if they passed a given productivity threshold. A particular property of this community is that there is no direct interaction (here, communication) amongst foragers that allowed us to study compartmentalization, assumed to be important for scalability, in a very clear form. Veenhuis and Koppen in the tenth chapter introduce a data clustering algorithm based on species clustering. It combines methods of particle swarm optimization and flock algorithms. A given set of data is interpreted as a multi-species swarm which wants to separate into single-species swarms, i.e., clusters. The data to be clustered are assigned to datoids which form a swarm on a two-dimensional plane. A datoid can be imagined as a bird carrying a piece of data on its back. While swarming, this swarm divides into sub-swarms moving over the plane and consisting of datoids carrying similar data. After swarming, these sub swarms of datoids can be grouped together as clusters. In the last chapter Yang et al. present a clustering ensemble model using ant colony algorithm with validity index and ART neural network. Clusterings are visually formed on the plane by ants walking, picking up or dropping down projected data objects with different probabilities. Adaptive Resonance Theory (ART) is employed to combine the clusterings produced by ant colonies with different moving speeds. We are very much grateful to the authors of this volume and to the reviewers for their tremendous service by critically reviewing the chapters. The editors would like to thank Dr. Thomas Ditzinger (Springer Engineering Inhouse Editor, Studies in Computational Intelligence Series), Professor Janusz Kacprzyk (Editor-in-Chief, Springer Studies in Computational Intelligence Series) and Ms. Heather King (Editorial Assistant, Springer Verlag, Heidelberg) for the editorial assistance and excellent cooperative collaboration to produce this important scientific work. We hope that the reader will share our excitement to present this volume on ‘Swarm Intelligence in Data Mining’ and will find it useful.
April, 2006
Ajith Abraham, Chung-Ang University, Seoul, Korea
Crina Grosan, Cluj-Napoca, Babes-Bolyai University, Romania
Vitorino Ramos, IST Technical University of Lisbon, Portugal
Fig. – (Above) A 3D toroidal fast changing landscape describing a Dynamic Optimization (DO) Control Problem (8 frames in total). (Bellow) A self-organized swarm emerging a characteristic flocking migration behaviour surpassing in intermediate steps some local optima over the 3D toroidal landscape (above), 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). [extra details + PDF]
[] Vitorino Ramos, Fernandes, C., Rosa, A.C., Abraham, A., Computational Chemotaxis in Ants and Bacteria over Dynamic Environments, in CEC´07 – Congress on Evolutionary Computation, IEEE Press, USA, ISBN 1-4244-1340-0, pp. 1009-1017, Sep. 2007.
Chemotaxis can be defined as an innate behavioural response by an organism to a directional stimulus, in which bacteria, and other single-cell or multicellular organisms direct their movements according to certain chemicals in their environment. This is important for bacteria to find food (e.g., glucose) by swimming towards the highest concentration of food molecules, or to flee from poisons. Based on self-organized computational approaches and similar stigmergic concepts we derive a novel swarm intelligent algorithm. What strikes from these observations is that both eusocial insects as ant colonies and bacteria have similar natural mechanisms based on stigmergy in order to emerge coherent and sophisticated patterns of global collective behaviour. Keeping in mind the above characteristics we will present a simple model to tackle the collective adaptation of a social swarm based on real ant colony behaviors (SSA algorithm) for tracking extrema in dynamic environments and highly multimodal complex functions described in the well-know De Jong test suite. Later, for the purpose of comparison, a recent model of artificial bacterial foraging (BFOA algorithm) based on similar stigmergic features is described and analyzed. Final results indicate that the SSA collective intelligence is able to cope and quickly adapt to unforeseen situations even when over the same cooperative foraging period, the community is requested to deal with two different and contradictory purposes, while outperforming BFOA in adaptive speed. Results indicate that the present approach deals well in severe Dynamic Optimization problems.
(to obtain the respective PDF file follow link above or visit chemoton.org)
Swarm robotics is a new approach to the coordination of multirobot systems which consist of large numbers of mostly simple physical robots. It is supposed that a desired collective behavior emerges from the interactions between the robots and interactions of robots with the environment. This approach emerged on the field of artificial swarm intelligence, as well as the biological studies of insects, ants and other fields in nature, where swarm behavior occurs (check for more).
Possible laboratories around the world that follow this line of research include (Europe) Marco Dorigo’s Swarm-Bots Project in Brussels plus Swarm-Intelligent Systems Group, EPFL, in Lausanne, and CORO over Caltech, USA, among many others.
Video – Thousands of starlings birds gathering in flocks, flying in formations while emerging complex patterns on S.W. Scotland (more photos & video by/at Fresh Pics, 2007). Here for an artificial version with different purposes. They are not birds, instead an entirely different new animal.
[...] In contrast to negative feedback, positive feedback (PF) generally promotes changes in the system (the majority of self-organizing SO systems use them). The explosive growth of the human population provides a familiar example of the effect of positive feedback. The snowballing autocatalytic effect of PF 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 autocatalysis are all terms used to describe positive feedback [9]. 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 (1): 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 (check for further references on [7,9]). On social insect societies, PF 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 [49] 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 (2), or even just thinking of yawning, can trigger a yawn [9]. There is however one associated risk, generally if PF 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 PF 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 [9], the minimal behavioral rule could be “I nest where others nest, unless the area is overcrowded” (HEY !! here we go again to the El Farol Bar problem!). In this case both 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. [...]
in, V. Ramos et al., “Social Cognitive Maps, Swarm Collective Perception and Distributed Search on Dynamic Landscapes“.
(1) See also on this subject the seminal sociological work of Gabriel Tarde; Tarde, G., Les Lois de l’Imitation, Eds. du Seuil (2001), 1st Edition, Eds. Alcan, Paris, 1890.
(2) Similarly, Milgram et al (Milgram, Bickerman and Berkowitz, “Note on the Drawing Power of Crowds of Different Size”, Journal of Personality and Social Psychology, 13, 1969) found that if one person stood in a Manhattan street gazing at a sixth floor window, 20% of pedestrians looked up; if five people stood gazing, then 80% of people looked up.
(to obtain the respective PDF file follow this link or visit chemoton.org)
From left to rigth, Nelson Minar, JJ Merelo (one of my co-authors), Manor Askenazi and Chris Langton (founding father of Artificial Life) at the El Farol Bar, Santa Fe, New Mexico, during summer 1995.
From left to rigth, Nelson Minar, JJ Merelo (one of my co-authors), Manor Askenazi and Chris Langton (founding father of Artificial Life) at the El Farol Bar, Santa Fe, New Mexico, during summer 1995. At the same year, Chris was the editor of the well-know Artificial Life book, by MIT Press, and JJ for the 3rd European Conference on Artificial Life, Granada, Spain.
In case you do not have a clue what the El Farol Bar meant to the Santa Fe Institute (SFI), have a read here to Brian Arthur’s paper “Inductive Reasoning and Bounded Rationality: The El Farol bar problem“, American Economic Review, 84, 406-411, 1994 (or check previous posts). I am happy to say that I was also there, visiting Santa Fe back in 2000, speaking with, among other people with Cosma Shalizi, as well as having a cigar and a beer at the El Farol. Much probably at this table, which was near the front door window, one of my favourite ones during my two week stay.
Finally, and in what regards the ongoing present financial world crisis, here’s a quote from 1994’s Arthur’s paper:
[...] Economists have long been uneasy with the assumption of perfect, deductive rationality in decision contexts that are complicated and potentially ill-defined. The level at which humans can apply perfect rationality is surprisingly modest. Yet it has not been clear how to deal with imperfect or bounded rationality. From the reasoning given above, I believe that as humans in these contexts we use inductive reasoning: we induce a variety of working hypotheses, act upon the most credible, and replace hypotheses with new ones if they cease to work. Such reasoning can be modeled in a variety of ways. Usually this leads to a rich psychological world in which agents’ ideas or mental models compete for survival against other agents’ ideas or mental models–a world that is both evolutionary and complex. [...]
Image Classification of Shellfish Larvae Digital Images using Swarm Intelligence. On the left a compendium of 9 raw images (out of 20 samples) used in the present project. Respective segmented images on the rigth.
[] Vitorino Ramos, Jonathan Campbell, John Slater, John Gillespie, Ivan F. Bendezu and Fionn Murtagh, Swarming around Shellfish Larvae Images, in WCLC-05, 2nd World Congress on Lateral Computing, Bangalore, India, 16-18 Dec., 2005.
The collection of wild larvae seed as a source of raw material is a major sub industry of shellfish aquaculture. To predict when, where and in what quantities wild seed will be available, it is necessary to track the appearance and growth of planktonic larvae. One of the most difficult groups to identify, particularly at the species level are the Bivalvia. This difficulty arises from the fact that fundamentally all bivalve larvae have a similar shape and colour. Identification based on gross morphological appearance is limited by the time-consuming nature of the microscopic examination and by the limited availability of expertise in this field. Molecular and immunological methods are also being studied. We describe the application of computational pattern recognition methods to the automated identification and size analysis of scallop larvae. For identification, the shape features used are binary invariant moments; that is, the features are invariant to shift (position within the image), scale (induced either by growth or differential image magnification) and rotation. Images of a sample of scallop and non-scallop larvae covering a range of maturities have been analysed. In order to overcome the automatic identification, as well as to allow the system to receive new unknown samples at any moment, a self-organized and unsupervised ant-like clustering algorithm based on Swarm Intelligence is proposed, followed by simple k-NNR nearest neighbour classification on the final map. Results achieve a full recognition rate of 100% under several situations (k =1 or 3).
(to obtain the respective PDF file follow link above or visit chemoton.org)
Figure – Evolutionary lego cranes and bridges. Check here for a small animation as well as a long mpeg video.
These, I believe, will be the solution for the first floating Europe-Africa bridge preliminary project (linking the Portuguese-Spanish border between Faro and Huelva, ending near Tanger – Morocco, spanning the entire strait of Gibraltar), or for many of them coming in the near future, in case they need to robustly and adaptively join further long distances:
[...] Creating artificial life forms through evolutionary robotics faces a “chicken and egg” problem: Learning to control a complex body is dominated by inductive biases specific to its sensors and effectors, while building a body which is controllable is conditioned on the pre-existence of a brain. The idea of co-evolution of bodies and brains is becoming popular, but little work has been done in evolution of physical structure because of the lack of a general framework for doing it. Evolution of creatures in simulation has been constrained by the “reality gap” which implies that resultant objects are not buildable. The work we present takes a step in the problem of body evolution by applying evolutionary techniques to the design of structures assembled out of parts. Evolution takes place in a simulator we designed, which computes forces and stresses and predicts failure for 2-dimensional Lego structures. The final printout of our program is a schematic assembly, which can then be built physically. We demonstrate its functionality in several different evolved organisms [...]. in, Computer Evolution of Buildable Objects, Pablo Funes and Jordan Pollack, 1997.
Recent Comments