Genetic Programming and self-replicating structures in cellular automata

The study of self-replicating structures is a very important field in Artificial Life. Cellular automata have studied two kinds of replicating structures: self-replicating ones and universal constructors. Von Neumann designed complex universal constructors consisting of multiple components. A second type of replicators, self-replicated loops, were studied by Langton, showing that looplike structures used in universal constructors could independently reproduce themselves. The replication process underlying both universal constructors and self-replicating loops, uses a sequential construction in which an arm extends from the parent structure and deposits the child structure. It depends on manually programmed sequential instructions depending on the presence of totalistic transition functions. But today Genetic programming facilitates the evolution of cellular automata given initial structures where cells may have several possible states. Pan and Reggia (2010) obtain replicating structures that are qualitatively different from past manually designed universal constructors and self-replicating loops. As a consequence, it is possible to produce many replicators that vary in just a single property.

To build a Genetic programming system that can program a cellular automata to support self-replication, the authors use trees as data structures ("chromosomes") that represent both structural information and the rules forming the state transition functions. They use a fitness function that generates the ocurrence of multiple copies of an initial structure in the cellular space over time. These self-replicating structures produced by Genetic programming are different from those found in self-replicating loops and universal constructors: there is no an identifiable instruction sequence and no construction arm. An initial structure grows and then divide, making replication very fast. The structures move and it is not possible distinguish between parents and childrens. In some ways, their fissionlike replication process is similar to the splicing during mitosis in biological cells. Replicators can also support the construction of secondary structures as they replicate, either with or without a given initial seed structure. When the replication rules are executed in parallel in each cell, they often employ a strategy that has not been manually created in old constructions. For instance, the moving-wall strategy consisting in a line of replicating structures depositing secondary structures behind it. Thus, Genetic programming is a very powerful tool in the discovery of novel self-replicating structures in cellular automata.

A computational simulation of laws of imitation in Social Psychology

(Spatial prisoner´s dilemma for b=1.6)

I am going to explain the design of a gamed based on the spatial prisoner introducing the three laws of imitation defined by the French Sociologist Jean Gabriel Tarde. It was presented by Carlos Pelta in the "2011 Meeting of the European Mathematical Psychology Group", celebrated in Paris.

The first law or law of Close contact (LCC) describes how individuals in close intimate contact with one another imitate each other´s behavior. The second law of imitation or imitation of superiors by inferiors (LSI) establishes people follow the model of high status in hopes their imitative behavior will get the rewards associated with being of a "superior" class. Tarde´s third law is the law of insertion (LOI): new acts and behaviors are superimposed on old ones and subsequently either reinforce or discourage previous customs. The following imitation rules are introduced: (1) Conf rule (Conformist rule) simulating the law of Close contact (LCC): if your behavior is different from that of the neighboring agent, copy its behavior; (2) Maxi rule (Maximization rule) simulates the law LSI and is so defined: if the neighbor agent gets higher payoffs, copy its behavior; (3) Fashion rule: copy the behavior with the highest frequency of appearance in your neighborhood (in case of equal frequency, copy at random); (4) Snob rule: copy the behavior with a lower frequency of appearance in your neighborhood (if the frequency of behavior appearance is the same, copy at random). Rules (3) and (4) simulate the law of insertion (LOI), alternating the copy of the latest choice made with the Fashion rule and the copy using the Snob rule in every round of the game. The agents have memory for these two rules for the 3 previous rounds of the game.

Once taken into account all these rules in a spatial prisoner´s dilemma, and combining all the possible values of b between 1 and 1.9, with an initial distribution of cooperators between 0.1 and 0.9, a memory M between 1 and 9 rounds for the rules (3) and (4) and changing the number N of agents and the number of rounds of the game, it is concluded that in our game the imitation rules by Tarde yield a preferential attractor and a low proportion of cooperating individuals. Although we have introduced two rules of stochastic nature (3) and (4), its effect is nullified by the proper mimetic dynamics, which means that they can not even be present in the attractor. Thus, agents attracted by non stochastic rules, and b values that increasingly are encouraging defection, are mass defined as defectors which find ways to maintain their payoffs as high as possible. But this circumstance supports Tarde´s law LSI because the imitation of the agents with higher payoffs (defectors) is majority also including the case with an initial rate of 0.9 cooperators receiving a payoff of 1 (defectors receive payoffs from 1.1 to 1.9). Besides our simulation verifies the law LOI, combining rules (1) and (2), because the most imitated behavior or Maximization behavior, makes via rule (1), the new behavior reinforced, discouraging the cooperative behavior of the agents with lesser payoffs.

The dynamics of group affiliation

Today we present in this blog the work by Nicholas Geard and Seth Bullock about the dynamics of group affiliation-see http://eprints.ecs.soton.ac.uk/21195/5/S0219525910002712.pdf-. Models about group formation are common in many social simulations. But models on group affiliation in which individuals can belong to multiple groups simultaneously are very infrequent. According to Geard and Bullock (art. cit., 2010, p. 501), some types of groups may be exclusive, that is, membership in one group precludes membership in other groups of that type and others are non-exclusive. Affiliation with a group involves the consum of time and energy being very important to determine the degree of commitment of the subjects and their degree of participation in other groups for studying the social evolution.

In pre-modern societies the affiliations were made in a series of concentric social circles from family to the country but in contemporary society all is more complex. In the "liquid society" (so called by Zygmunt), the bonds in choices of affiliation are very complex and fuzzy. Individual may belong to multiple groups simultaneously and Geard and Bullock design a model of affiliation to non-exclusive groups. Their simulation considers a network of n nodes and m undirected edges (art. cit., p. 507), representing individuals and the social ties between them. Each node i has a trait vector of dimension d, representing that individual´s location in social space, a list of affiliated groups and a time and energy capacity. Trait values are bounded between zero and one and are uniformly distributed. The social distance between two individuals is defined as the Euclidean distance between their trait vectors. Each group has a cost of time and energy associated with being a member, reducing the number of groups with which a node can be affiliated.

In the network, edges may be rewired either to nodes sharing a common state, or at random. Nodes may either initiate a new group, or be recruited to an existing group by one of their network neighbors. A node initiating a new group will always leave existing groups to maketime for the new group while a node being recruited to a new group will either leave existing groups or refuse the recruitment attempt, depending of the sociodemographic space.

For the simulations, the authors explored the circumstance where all memberships are exclusive, the population evolving to a "connected community structure" (art. cit., p. 509), that is, a type of continuing connectivity combined with the occasional initiation of novel groups. All groups had a cost of one but increasing cost above one had relevant effects on network structure, decreasing the level of community comparable to that of a random network. this trend suggests that as individuals belong to more groups, they are lees likely to become disconnected from the population, but have more opportunities to leave groups containing different to themselves. Obviously, less costly groups were maintained in the population in greater quantities than more costly groups but the mean size of the more costly groups remained constant as capacity of time and energy increased, while that of the less costly groups grown rapidly.

One interesting prediction is that less costly groups may find it easier to thrive, but that more costly groups may retain more diversity. We believe that the ideas surrounding the simulation by Geard and Bulloch is an interesting step forward for the modelization of the complex problem of the affiliation in social dynamics.

EMPG 2011: Forty years of the "European Mathematical Psychology Group"

(Telecom-Paris) (Photo by Carlos Pelta)

The "Meeting of the European Mathematical Psychology Group", which was held at the Telecom ParisTech, August 29-31, 2011, was a great success. Major credits go to Professor Olivier Hudry, the Meeting chair, who opened the Meeting with a few welcoming remarks. Next, Professor Marchant, the first plenary speaker, shared the latest developments about "Measurement theory with unary relations". H. Colonius and S. Rach have developed an approach based on the theory of Fechnerian Scaling for the measure of visual-auditory integration efficiency. Fechnerian Scaling deals with the computation of subjective distances from their pairwise discrimination probabilities. In the afternoon, L. Stefanutti spoke about knowledge structures extending the probabilistic framework to represent local independence among items in a probabilistic knowledge structure. Professors Alcalá-Quintana and García-Pérez introduced a model of indecision in perceptual detection tasks revealing strong order effects that vary in sign and magnitude in a systematic manner across observers. Besides, they used a probabilistic model of temporal-order perception to provide a common framework for synchrony judgments. Professor Shanteau described his experiments on memory-retrieval versus decision-making in repetition priming. Finally, Professors Albert and Hockemeyer analysed the very relevant contributions by Jean-Claude Falmage, the founder of the "European Mathematical Psychology Group", to Mathematical Psychology.

On Tuesday, Professor Raijmakers started the morning sessions with the oral presentation entitled "The application of latent Markov models in category learning". Latent Markov models allows for analysing multiple latent categorization strategies separately in a robust way. Next, Professor Pelta introduced a computational simulation in Social Psychology, adding to the spatial prisoner´s dilemma the three laws of imitation formulated by Jean-Gabriel Tarde in his book "The laws of imitation" (1890). Professor Thiel exposed how automata network models can simulate the halo effect in human attitudes, using a connectionist model on the Beckwith and Lehman multiattributes theory. In the afternoon, Jean-Claude Falmagne presented the idea of "Learning Spaces" and his colaborator Eric Cosyn introduced a very interesting practical application. Cosyn has extracted 350 items forming a learning space whose domain is the field of middle-school algebra. Professor Induráin tried to establish a common theory that relates the different mathematical properties that the concept of "mean" can have.

On Wednesday 31 August, Professor Choirat reviewed her work on separable representations in Mathematical Psychology and decision making. Finally, I would like to stress the oral presentation by Professor Doignon about representations of interval orders.

A post-conference edition of Meeting presentations should be available on the journal "Electronic Notes in Discrete Mathematics" perhaps during the first quarter of 2012.

We are very grateful, in first place, to the city of Paris, and, in a second place, to Professors Hudry, Lobstein, Charon and Choirat and Telecom ParisTech, for the organization of the Meeting.

2011 Meeting of the European Mathematical Psychology Group (Paris)

The "2011 Meeting of the European Mathematical Psychology Group" will be held at the TELECOM ParisTech, August 29-31, 2011 (http://www.telecom-paristech.fr/eng/home.html).

The conference is organized by Irène Charon (Tèlècom ParisTech), Olivier Hudry (Tèlècom ParisTech and CNRS), Antoine Lobstein (CNRS and Tèlècom ParisTech) and Hayette Soussou (Tèlècom ParisTech). The Program has been elaborated by Professor Hudry and the plenary speakers will be T. Marchant ("Measurement theory with unary relations"), L. Stefanutti ("When the correspondence between probabilistic and set representations of local independence becomes a requirement: constant odds models for probabilistic knowledge structures"), D. Albert and C. Hockemeyer ("JCF´s impact is not limited to the foundation of the EMPG"), M. Raijmakers ("The application of latent Markov models in category learning"), J.-C. Falmagne ("Learning spaces in real life. How the large size of actual learning spaces guides the development of the theory"), C. Choirat ("Separable representations in mathematical psychology and decision making") and A. Diederich ("Optimal time windows: Modeling multisensory integration in saccadic reaction times").

In the parallel sessions, the author of this blog (C. Pelta) will started the morning sessions on Tuesday 30 August (10:30 h.) with his oral presentation entitled "Spatial prisoner´s dilemma and laws of imitation in Social Psychology". I design a game based on the spatial prisoner introducing the three laws of social imitation defined by Gabriel Tarde in his book Les lois de l´imitation (1890). The French author described (a) the law of close contact (individuals in close intimate contact with one another imitate each other´s behavior), (b) the law of imitation of superiors by inferiors (people follow the model of high status in hopes their behavior will procure the rewards associated with the "superior" class) and (c) the law of insertion (new behaviors reinforce or discourage previous customs). I run a computational simulation in which the formation of little "clusters" of cooperators supports not only the laws of Tarde but also the ideas of Sutherland which explain the imitation of deviance behavior as a process of communication within intimate personal groups or "differential association".

I predict that the Meeting will be a great success and that the organization will be very succesful. The readers of this blog are cordially invited to participate. On September it will be published in this blog a summary exposing the main ideas of this event to celebrate in Paris. For more information, please, see the webpage content designed by Professor Olivier Hudry (http://www.infres.enst.fr/~hudry/EMPG/).

Computational Models of Human-Mate Choice and KAMA

Since classical article by Gale and Shapely (1962), several computational models about Human-Mate Choice have emerged. In this article, the authors developed a "match-making" algorithm for a population with an equal number of males and females. Kalick and Hamilton (1986) found a correlation in physical attractiveness among married couples. Kenrick et al. (2000) used dynamic social influence networks and concluded that males are inclined to take advantage of unrestricted relations whereas females prefer restricted relationships. Other models have been presented but in this article for the blog, we expose perhaps the most recent model. And for the author of this blog, perhaps the most interesting. It is adequately complex (it uses a vector of values to simulate the population-level effects of the modification over time of particular characteristics of individuals) and employs the mechanism of computational temperature for the simulation, that is, the amount of energy that people put into encountering and dating potential mates). Bob French and Elif Kus (2008) (see their article that was published in the journal Adaptive Behavior, http://leadserv.u-bourgogne.fr/files/publications/000261-kama-a-temperature-driven-model-of-mate-choice-using-dynamic-partner-representations.pdf) distinguish between "parallel" versus "serial" decision-making procedures. The male selects someone to ask out among a number of available alternatives ("parallel" decision process) and the female then accepts or declines his invitation immediately upon receiving it ("serial" decision process). KAMA, the computational model designed by French and Kus, implements the search of resources for a mate by a feedback-driven internal parameter called "temperature". In KAMA each agent has its own temperature that regulates its behavior. Temperature is a function of both an individual´s recent dating history and his/her age (French and Kus, 2008, p. 75), that is, a measure of the energy that one is willing to expend to find a partner. The higher the temperature, the more willing an individual is to explore for a mate; the lower the temperature, the less willing he/she is to do so. Also KAMA is a "stochastic model: essentially all choices are made probabilistically, on the basis of the individual´s temperature. The authors run a simulation (20 runs of the program) starting with 600 indviduals (half of them, females) whose ages vary randomly between 18 and 48. Both males and females maintain a list of all previously encountered individuals and the values of their characteristics, updated with each new encounter. After acceptance or refusal of a date, the temperature of the individuals involved is updated. The mechanisms of KAMA include "attractiveness" implying mate value. Characteristic preferences for the profiles are "kindness and understanding", "exciting personality", intelligence", "physical attractiveness", "good health", "adaptability", "creativity", "desire for childen", "College graduate", "good earning capacity", "good heredity", "good housekeeper" and "religious orientation". In addition to their preference profiles and characteristic profiles, all indviduals maintain a memory of all individuals they have previously encountered, along with the values of the characteristics of these individuals that they have discovered through encounters and dates with them.

To test KAMA, French and Kus drew on empirical data from the Eurostat. In KAMA, physical attractiveness decreased with age and wealth. On average, males´preference weighting for physical attractiveness was higher than the preference weight for females. The most surprising results were that when males and females had identical preference profiles and identical temperature curves, there was a marked male-female hazard-rate shift. Why does the fact that males ask women out and women accept or refuse lead to this difference in hazard rates? The asymmetry in the males-ask/females-decide custom produce this difference in hazard rates. When women can ask men out, this asymmetry disappears and, all other things being equal, the male-female hazard-rate shift disappears.

More sophisticated versions of this model are necessary but we think that KAMA incorporates novel features like the notion of agents with indidualized preferences or the idea of computational temperature which controls the focus of decision making. Undoubtely, KAMA is a very functional and complete model for the Human-Mate Choice.

(Photo: Bob French).

Models of minority opinion spreading

Maxi San Miguel (Physics of Complex Systems, University of Balearic Islands) has won the Medal of the Royal Society of Physics in Spain. Congratulations for this excellent researcher. His studies linking Physics to Social Dynamics are very interesting. And so, Wio, Toral, Tessone, Amengual, San Miguel (2004), have exposed several neighborhood models of minority opinion spreading the idea which we analyze in this article. According to the authors, the neighborhood models are locally defined neighborhood cells systems with complete connectedness. Neighborhood cells change shape and size during evolution. The question is How an initially minority opinion can become majority? Obviously, there are several theoretic models like Galam Model. Galam (2002) says that social inertia is a conservative response to the risk of a change maintaining social status quo. Let be a binary opinion and initially there is a minority against social reform. Cells are defined only by their size. A tie in the voting is a "No" for social reform. When all the agents in the cell adopt an opinion, agents join a meeting cell randomly selected. Decision rule is applied in all the cells. Agents randomly redistributed in the meeting cells carry their adopted opinion. Applying a mean-field analysis, there is a threshold value of initial minority supporters such that the minority opinion finally becomes majority. There is an asymmetric unstable fixed point or "faith point". Time to reach consensus is fast and system-size independent. In this model, individuals are fixed at the sites of a regular lattice and meeting cells are locally defined by a tessellation of the lattice. Consensus is always reached in finite systems in a finite number of steps. In an infinite system the initial minority opinion wins regardless the amount of initial supporters. Why? Because a critical size for an initial local domain of minority supporters exists: a domain of overcritical size always exists in a large enough population. Neighborhood models describe a more efficient spreading of minority opinion, but spreading takes a much longer time.

Social groups and chaotic state transitions: homage to Walter J. Freeman III

In this article, we pay homage to one of the most prominent neuroscientists ever: Walter Jackson Freeman III. He has designed a perspective called Nonlinear Neurodynamics of the brain that, perhaps is the most advanced and veridical approximation to the study of the brain dynamics. More interesting for this blog is the connection between his neurophysiological discoveries and its applications to the social dynamics o formation of social groups (see his book, "Societies of Brains", 1995). According to Freeman (1995), the cerebral cortex switches abruptly from one basin of attraction to another, each transition involving learning. Therefore, each brain creates its own trajectory which is not directly accessible by any other brain. The question is: how can several brains be shaped by learning so as to form cooperative groups for survival and reproduction? Large numbers of neurons follow chaotics dynamics expressing global state transitions (sleep to waking, etc.) and one class of state transitions in brains provides for the formation of social groups. Brains process meaning. But this intentional mechanism implies, in a certain sense, the isolation of each brain. With respect to energy and information each brain is an open system but with respect to meaning it is a closed system. However Nature has evolved powerful methods for the social learning and social cooperation. The discovery of the means for inducing these forms of learning can be understood as a chaotic state transition in brain dynamics like, for instance, the rapid adaptation of young adults for their new roles in state transitions from child to adulthood.

Maja J. Mataric and social robots

In this article we expose some interesting ideas by Maja J. Mataric (University of Southern California) about the design of social robots (see Mataric, 2002 in Encyclopedia of cognitive science).

Building sociable robots includes many facets, like imitation, social learning and emotion. We can design social robots applying ideas from developmental psychology, for example and so looking for inspiration in Neuroscience. Mataric (1992) described the work with TOTO, a mobile robot being able to represent landmarks in the environment. TOTO was representative of an Artificial Intelligence interpretation of the organization of the rat hippocampus. As an alternative, Nicolescu and Mataric (2002) designed a hierarchical behavior-based architecture enabling behaviors to represent more abstract concepts. Here representations are stored in a distribuited fashion. The same perspective on generating behavior has been successful with groups of robots. This area is known as "swarm robotics". Truly coordinating a set of robots is complicated problem. Multi-robot coordination involves communication and selection action, between several tasks. In 1995 Mataric worked with the NERD HERD, a group of 20 autonomous mobile robots with limited sensing and computational abilities. Each robot was programmed with a small set of behaviors: homing, wandering, following, aggregation and dispersion. The basis behaviors were designed to conserve energy by minimizing interference between robots. Mataric (1997) described the problem of learning social rules in order to maximize energy. Robots acting within a social setting have additional sources of information: observation of a peer performing a successful action, etc. Models of people´s natural social interactions are relevant for robots in human environments. For humanoid robots this can take the form of learning natural human skills. Mataric is an excellent searcher looking for solutions which imply the design of social robots.