Tuesday, September 18, 2007

Collective Intelligence and Evolution

Collective Intelligence and Evolution

by Akira Namatame


The mission of collective evolution is to harness the systems of selfish agents to secure a sustainable relationship, so that desirable properties can emerge as 'collective intelligence'.

Why do colonies of ants work collectively, and how do they do it so effectively? One key to answering this question is to look at interactions among ants. For the last decade, attempts have been made to develop some general understanding, which has produced the theory of collective systems, that is, systems consisting of a large collection of agents. It is common to refer to the desirable emergent properties of collective systems as 'collective intelligence'. Interactions are able to produce collective intelligence at the macroscopic level that is simply not present when the components are considered individually.

The concept of collective intelligence observed in social insects can be extended to humans. In his book, The Wisdom Of Crowds, Surowiecki explores a simple idea that has profound implications: a large collection of people are smarter than an elite few at solving problems, fostering innovation, coming to wise decisions, and predicting the future. His counterintuitive notion, rather than crowd psychology as traditionally understood, provides us with new insights for understanding how our social and economic activities should be organized.

On the other hand, the fact that selfish behaviour may not achieve full efficiency is also well known in the literature. It is important to investigate the loss of collective welfare due to selfish and uncoordinated behavior. Recent research efforts have focused on quantifying this loss for specific environments, and the resulting degree of efficiency loss is known as 'the price of anarchy'. Investigations into the price anarchy have provided some measures for designing collective systems with robustness against selfish behaviour. Collective systems are based on an analogous assumption that individuals are selfish optimizers, and we need methodologies so that the selfish behaviour of individuals need not degrade the system performance. Of particular interest is the issue of how social interactions should be restructured so that agents are free to choose their own actions, while avoiding outcomes that none would choose.

Darwinian dynamics based on mutation and selection form the core of models for evolution in nature. Evolution through natural selection is often understood to imply improvement and progress. If multiple populations of species are adapting each other, the result is a co-evolutionary process. However, the problem to contend with in Darwinian co-evolution is the possibility of an escalating arms race with no end. Competing species may continually adapt to each other in more and more specialized ways, never stabilizing at a desirable outcome.
The Rock-Scissors-Paper (RSP) game is a typical form of representing the triangular relationship. This simple game has been used to explain the importance of biodiversity. We generalize a basic rock-scissors-paper relationship to a non-zero-sum game with the payoff matrix shown in Table 1. In this triangular situation, diversity resulting from proper dispersal by achieving Nash equilibrium is not efficient, and the agents may benefit from achieving a better relationship.

Table 1: The generalized rock-scissors-paper game (ramda greater than or equal to 2). Figure 1: The state diagram of the strategy choices between two agents.
Table 1: The generalized rock-scissors-paper game (ramda greater than or equal to 2). Figure 1: The state diagram of the strategy choices between two agents.

In particular, we have examined the system of interactive evolving agents in the context of repeated RSP games, by considering a population of agents located on a lattice network of 20x20. They repeatedly play the generalized RSP game with their nearest eight neighbours based on the coupling rules, which are updated by the crossover operator. 400 different rules, one for each agent, are aggregated at the beginning into a few rules with many commonalities. The game between two agents with the learned coupling rule becomes a kind of stochastic process. The transitions of the outcome are represented as the phase diagram in Figure 1, and they converge into the limit cycle, visiting the Pareto-optimal outcomes: (0,1) (1,2) (2,0) (1,0) (2,1) (0,2). Therefore each agent learns to behave as follows: win three times and then lose three times. In this way, the agents succeed in collectively evolving a robust learning procedure that leads to near-optimal behaviour based on the principle of give and take.

The framework of collective evolution is distinguished from co-evolution in three aspects. First, there is the coupling rule: a deterministic process that links past outcomes with future behaviour. The second aspect, which is distinguished from individual learning, is that agents may wish to optimize the outcome of the joint actions. The third aspect is to describe how a coupling rule should be improved, using the criterion of performance to evaluate the rule.

In biology, the gene is the unit of selection. However, the collective evolutionary process is expected to compel agents towards ever more refined adaptation, resulting in sophisticated behavioural rules. Cultural interpretations of collective evolution assume that successful behavioural rules are spread by imitation or learning by the agents. This approach to collective evolution is very much at the forefront of the design of desired collectives in terms of efficiency, equity, and sustainability. Further work will need to examine how collective evolution across the complex socio-economical networks leads to emergent effects at higher levels.

Please contact:
Akira Namatame, National Defense Academy, Japan
Tel: +81 468 3810
E-mail: nama@nda.ac.jp
http://www.nda.ac.jp/~nama

Sunday, September 16, 2007

new Journal: Evolutionary Intelligence

12065

Evolutionary Intelligence

Editor-in-Chief: Larry Bull
ISSN: 1864-5909 (print version)
ISSN: 1864-5917 (electronic version)
Journal no. 12065
Springer
Description
|
Description

Evolutionary Intelligence is an international journal devoted to the publication and dissemination of theoretical and practical aspects of the use of population-based search for artificial intelligence. Techniques of interest include evolving rule-based systems, evolving artificial neural networks, evolving fuzzy systems, evolving Bayesian and statistical approaches, artificial immune systems, and hybrid systems which combine evolutionary computation with other A.I. techniques in general.

Saturday, September 15, 2007

Swarm Intelligence journal

11721

Swarm Intelligence

Editor-in-Chief: Marco Dorigo
ISSN: 1935-3812 (print version)
ISSN: 1935-3820 (electronic version)
Journal no. 11721
Springer US

Description
|
Description

Swarm Intelligence: the principle resource dedicated to reporting on developments in the new discipline of swarm intelligence.

Swarm intelligence research deals with the study of self-organizing processes in natural and artificial swarm systems. It is a fast-growing field that involves the efforts of researchers in multiple disciplines, ranging from ethologists and social scientists to operations research and computer engineers.

Swarm Intelligence is dedicated to reporting on advances in the understanding and utilization of swarm intelligent systems. Submissions that shed light on either theoretical or practical aspects of swarm intelligence are welcome. The following subjects are of particular interest to the journal:

  • modeling and analysis of collective biological systems such as social insects colonies, school and flocking vertebrates, human crowds;
  • discussion of models of swarm behavior in insect, animal, or human societies that can stimulate new algorithmic approaches;
  • modeling and analysis of ant colony optimization, particle swarm optimization, swarm robotics, and other swarm intelligent systems;
  • empirical and theoretical research in swarm intelligence;
  • application of swarm intelligence methods to real-world problems such as distributed computing, data clustering, graph partitioning, optimization and decision making;
  • theoretical and experimental research in swarm robotic systems.

For better or worse, sex chromosomes are linked to human intelligence

For better or worse, sex chromosomes are linked to human intelligence

by Ellen Ruppel Shell

Last January Harvard University president Lawrence Summers hypothesized that women may be innately less scientifically inclined than men. Not long after the ensuing uproar, researchers announced the sequencing of the human X chromosome. The project was hailed as a great leap forward in decoding the differences between men and women, at least from a biological perspective. While it did nothing to calm the maelstrom swirling around Summers, the new understanding of the chromosome revealed tantalizing clues to the role genes might play in shaping cognitive differences between the sexes. And while these differences seem to be largely to the female's advantage, permutations during the genetic recombination of the X chromosome may confer to a few men a substantial intellectual edge.

Considerations of this sort are mired in politics and sensationalism, but one fact is beyond dispute: Three hundred million years after parting ways in our earliest mammalian ancestors, the X and the Y chromosomes are very different genetic entities. The Y has been whittled down to genes governing a handful of functions, most entailing sperm production and other male-defining features. Meanwhile, the gene-rich X is the most intensely studied of the 23 chromosomes, largely because of its role in rendering men vulnerable to an estimated 300 genetic diseases and disorders associated with those mutations—from color blindness to muscular dystrophy to more than 200 brain disorders.

The sex chromosomes lay the foundation for human sexual difference, with women having two Xs, one from each parent, while men get an X from their mom and a Y from their dad. Only 54 of the 1,098 protein-coding genes on the X seem to have functional counterparts on the Y, a dichotomy that has led scientists to describe the Y chromosome as "eroded." This diminutive chromosome offers little protection against the slings and arrows of genetic happenstance. When an X-linked gene mutates in a woman, a backup gene on the second X chromosome can fill the gap. But when an X-linked gene mutation occurs in a man, his Y stands idly by, like an onlooker at a train wreck.

The brain seems particularly vulnerable to X-linked malfunction. Physician and human geneticist Horst Hameister and his group at the University of Ulm in Germany recently found that more than 21 percent of all brain disabilities map to X-linked mutations. "These genes must determine some component of intelligence if changes in them damage intelligence," Hameister says.

Gillian Turner, professor of medical genetics at the University of Newcastle in Australia, agrees that the X chromosome is a natural home for genes that mold the mind. "If you are thinking of getting a gene quickly distributed through a population, it makes sense to have it on the X," she says. "And no human trait has evolved faster through history than intelligence."

The X chromosome provides an unusual system for transmitting genes between sexes across generations. Fathers pass down nearly their entire complement of X-linked genes to their daughters, and sons get their X-linked genes from their mothers.

Although this pattern of inheritance leaves men vulnerable to a host of X-linked disorders, Hameister contends that it also positions them to reap the rewards of rare, beneficial X-linked mutations, which may explain why men cluster at the ends of the intelligence spectrum. "Females tend to do better overall on IQ tests; they average out at about 100, while men average about 99," Hameister says. "Also, more men are mentally retarded. But when you look at IQs at 135 and above, you see more men."

To understand his hypothesis, consider that during the formation of a woman's eggs, paternal and maternal X chromosomes recombine during meiosis. Now suppose a mother passes to her son an X chromosome carrying a gene or genes for superintelligence. While this genetic parcel would boost the son's brilliance, he could pass that X chromosome only to a daughter, where it could be diluted by the maternally derived X. The daughter, in turn, could pass on only a broken-up and remixed version to the fourth generation, due, again, to the recombination that occurs during meiosis. Odds are that the suite of genes for superintelligence wouldn't survive intact in the remix. "It's like winning the lottery," Hameister adds. "You wouldn't expect to win twice in one day, would you?"

The theory is controversial. Among its detractors is David Page, interim director of the Whitehead Institute for Biomedical Research in Cambridge, Massachusetts. "Many claims have been made about gene enrichment on the X, and most look quite soft to me," he says. Nonetheless, he says that the attempt to link the enrichment of cognitive genes on the X to IQ differences "is a reasonable speculation."

Intelligence is a multifaceted quality that is unlikely to be traced to a single gene. Yet the link between gender and cognition is far too persistent for the public—or science—to ignore. Until recently sex differences in intelligence were thought to result chiefly from hormones and environment. New findings suggest genes can play a far more direct role. Working constructively with that insight will be a delicate challenge for the new millennium, one perhaps best avoided by college presidents.

DIALOGUE

SOCIAL SMARTS

DAVID SKUSE, professor of behavioral and brain sciences at the Institute of Child Health in London, has shown how the X chromosome can influence social skills. In studies of women with only one X chromosome, he found that test subjects who inherited their X chromosome from their fathers had better social skills than those who inherited their X chromosome from their mothers. This disparity offers clues to why boys, who inherit their single X chromosome from their mothers, are more vulnerable to disorders that affect social functioning.

What does your research reveal?

S: Imprinted genes are expressed differently depending on whether they are inherited from the father or the mother. By comparing the cognitive social skills of women with a single X chromosome [Turner's syndrome]—which could be either maternal or paternal in origin—with the skills of normal women, who have an X chromosome from both parents, we were able to show that X-linked imprinted genes could influence sexually dimorphic traits. It is important to note a couple of things; first, the gene that is imprinted was not expressed in the parent from whom it was inherited, so girls do not get their social skills from their fathers in any simple sense. Second, we are talking about a mechanism that potentially affects every one of us, but its effects will be subtly different depending on our genetic makeup and our environment of rearing.

Have you looked at whether normal men and women differ in social cognition?

S: We did a study of normal males and females on skills such as the ability to tell whether someone is looking directly at you and interpreting facial expressions. We looked at 700 children and over 1,000 adults and discovered little difference between adult men and women. On the other hand, girls entering elementary school tend to do a much better job than boys in interpreting facial expressions. This difference almost completely disappears after puberty.

What are the implications of your work?

S: What I can say is that disorders of social cognitive skills seem to affect a surprisingly large number of people. The disability can lead, especially among boys, to disruptive behavior in childhood if it is not recognized and treated sufficiently early. Others have found that boys are more vulnerable than girls to the long-term impact of maltreatment in childhood, and the risk of such boys becoming antisocial in later life seems to be related to a gene on the X chromosome, although not one that is imprinted.

Oldest University Unearthed in Egypt

Oldest University Unearthed in Egypt

by Susan Karlin

In May a team of Polish and Egyptian archaeologists announced they had unearthed the long-lost site of Archimedes’ alma mater: the University of Alexandria in Egypt. Even Cambridge University in England, which boasts Sir Isaac Newton as an alum, cannot claim such a venerable pedigree.

The legendary university flourished 2,300 years ago when Alexandria was the intellectual and cultural hub of the world. While in the city, Archimedes crafted a water pump of a type still used today; Euclid organized and developed the rules of geometry; Hypsicles divided the zodiac into 360 equal arcs; and Eratosthenes calculated the diameter of Earth. Other scholars in the city are believed to have edited the works of Homer and produced the Septuagint, the ancient Greek translation of the Old Testament. “This is the oldest university ever found in the world,” Grzegorz Majcherek, who directed the dig under the auspices of Egypt’s Supreme Council of Antiquities, told the Associated Press. “This is the first material evidence of the existence of academic life in Alexandria.”

Emily Teeter, an Egyptologist with the Oriental Institute at the University of Chicago, adds: “This discovery is of tremendous importance because of its role as a nexus of learning among the great cultures of that time. It’s one of the most famous institutions of the ancient world, and it’s astounding that the exact location has been unknown until now. Archaeologists knew it was in Alexandria, but not where in Alexandria.”

The research team found 13 identical lecture halls lining a large public square in the ancient city’s eastern section. A nearby Roman theater, discovered a half century ago, now assumes new meaning as a possible part of the ancient university. The halls are lined on three sides with rows of elevated benches overlooking a raised seat thought to have been used by a lecturer to address students.

“The magnificence of Alexandria as a center of learning was not just a myth,” says Willeke Wendrich, an archaeologist at UCLA. “It gives us hope that some day we might even find the location of the famous Library of Alexandria.” The library thrived from 295 B.C. into the fourth century A.D., when it burned to the ground; its ruins have never been found.

In a nod to its glory, Alexandria two years ago opened a new $230 million library complex containing a quarter-million books, a planetarium, a conference hall, five research institutes, six galleries, and three museums.

Hod Lipson How to Draw a Straight Line Using a GP:

How to Draw a Straight Line Using a GP: Benchmarking Evolutionary Design Against 19th Century Kinematic Synthesis
Hod Lipson
Computational Synthesis Laboratory,
Mechanical & Aerospace Engineering, and Computing & Information Science,
Cornell University, Ithaca NY 14850, USA
hod.lipson@cornell.edu

Abstract. This paper discusses the application of genetic programming to the synthesis of compound 2D kinematic mechanisms, and benchmarks the results against one of the classical kinematic challenges of 19th century mechanical de-sign. Considerations for selecting a representation for mechanism design are presented, and a number of human-competitive inventions are shown.

http://ccsl.mae.cornell.edu/papers/GECCO04_Lipson.pdf

Hod Lipson: Reinventing the Wheel: An Experiment in Evolutionary Geometry

http://ccsl.mae.cornell.edu/papers/GECCO05_Bongard2.pdf

In the domain of design, there are two ways of viewing the competitiveness
of evolved structures: they either improve in some manner
on previous solutions; they produce alternative designs that were
not previously considered; or they achieve both. In this paper we
show that the way in which designs are genetically encoded influences
which alternative structures are discovered, for problems in
which a set of more than one optimal solution exists. The problem
considered is one of the most ancient known to humanity: design
a two-dimensional shape that, when rolled across flat ground,
maintains a constant height. It was not until the late 19th century—
roughly 7000 years after the discovery of the wheel—that Franz
Reuleaux showed that a circle is not the only optimal solution. Here
we demonstrate that artificial evolution repeats this discovery in under
one hour.