Entelligence: Evolutionary Intelligence

Collective Intelligence and Evolution

2007-09-18T06:34:00.001-07:00

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.

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: namanda.ac.jp
http://www.nda.ac.jp/~nama

new Journal: Evolutionary Intelligence

2007-09-16T09:11:00.000-07:00

Evolutionary Intelligence

Editor-in-Chief: Larry Bull

ISSN: 1864-5909 (print version)
ISSN: 1864-5917 (electronic version)
Journal no. 12065
Springer

Description

Editorial Board

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.

Swarm Intelligence journal

2007-09-15T23:56:00.001-07:00

	Swarm Intelligence Editor-in-Chief: Marco Dorigo ISSN: 1935-3812 (print version) ISSN: 1935-3820 (electronic version) Journal no. 11721 Springer US Online version available Online First articles available

Description

Editorial Board

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

2007-09-15T18:28:00.001-07:00

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

2007-09-15T18:25:00.001-07:00

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:

2007-09-15T15:58:00.001-07:00

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

2007-09-15T15:52:00.000-07:00

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.

Several interesting papers from Hod Lispon about modeling

2007-09-15T15:48:00.000-07:00

From Publications of Cornell Computational Synthesis Lab by Hod Lipson

Bongard J., Lipson H. (2007), “Automated reverse engineering of nonlinear dynamical systems", Proceedings of the National Academy of Science, vol. 104, no. 24, pp. 9943–9948.

Schmidt M., Lipson H. (2007), "Learning Noise", Genetic and Evolutionary Computation Conference (GECCO'07), pp. 1680-1685.

Bongard J., Zykov V., Lipson H. (2006), “Resilient Machines Through Continuous Self-Modeling", Science Vol. 314. No. 5802, pp. 1118 - 1121 (see commentary by Adami "What Do Robots Dream Of?")

Aquino W., Kouchmeshky B., Bongard J., Lipson H., (2006) "Co-evolutionary algorithm for structural damage identification using minimal physical testing", Int. Journal for Numerical Methods in Engineering

Bongard J., Lipson H. (2005) “Nonlinear system identification using coevolution of models and tests”, IEEE Transactions on Evolutionary Computation, 9(4): 361-384.

Schmidt M., Lipson H., (2005) "Co-evolution of Fitness Maximizers and Fitness Predictors",

Pat Langley at Stanford has a strong interests in automated scientific discovery

2007-09-15T15:43:00.000-07:00

Pat Langley

Institute for the Study of Learning and Expertise
2164 Staunton Court, Palo Alto, CA 94306
(650) 494-3884 (phone); (650) 494-1588 (fax)
langley@isle.org

I currently serve as Director for the Institute for the Study of Learning and Expertise and as Head of CSLI's Computational Learning Laboratory. I am also a Consulting Professor of Symbolic Systems at Stanford University.

My research interests revolve around computational learning and discovery, especially their role in constructing scientific models, architectures for intelligent agents, and adaptive user interfaces.

Research activities:

Recent talks

2007 John Koza's research focus

2007-09-15T15:32:00.001-07:00

Koza Research:

automating the invention process and generating useful, patentable, and human-competitive inventions by means of genetic programming

Genetic Programming Inc. is a small privately funded corporation operating a beowulf cluster computer system consisting of 1,000 Pentium processors to do research in applying genetic programming to produce human-competitive results. Our current focus is on automating the invention process and generating useful, patentable, and human-competitive inventions by means of genetic programming. Our group publishes and presents numerous research papers each year at various scientific conferences and journals (both in the field of genetic and evolutionary computation and in the particular fields of the work). A good overview of the type of work we do can be seen on the home page of Genetic Programming Inc. at www.genetic-programming.com and the home page of John R. Koza at Stanford University is http://www.johnkoza.com Our genetic programming system is written in Java. The simulators with which we frequently work are typically written in C and other languages.

Genetic Programming Inc. is seeking a SCIENTIFIC RESEARCH PROGRAMMER. The position requires the ability to

● read scientific literature, suggest interesting new problems on which to work,

● contribute ideas on how to solve new problems using genetic programming;

● write, debug, and run the necessary programs in the context of our existing software and hardware system;

● analyze the results;

● help in the writing up of the results for publication (including making figures and graphics);

● make changes in our existing software and hardware system; and

● do systems administration to maintain the operation of our existing software and hardware system.

Excellent programming skills and productivity are a must. Although actual programming will consume less than half of the time, the person in this position must be able to rapidly prototype code. The code includes code to analyze results as well as to produce results. This position calls for at least a B.S. degree and at least two years experience in Java and/or C doing academic research programming or corporate research programming. A Master’s degree is preferable and a PhD degree would be even more desirable. It would be desirable for the successful candidate to have expertise in some specific science or engineering domain in order to advance the aim of applying genetic programming to that domain. The possibilities for domain areas are very open-ended and include, but are not limited to, analog circuit design, controller design, finite element analysis, shape optimization, operations research, mechanical design, signal processing, bioinformatics, optical lens systems; antennas; etc. Actual previous experience with, or knowledge of, genetic programming is a big plus.. Experience with, or knowledge of, genetic and evolutionary algorithms in general, machine learning, neural networks, artificial intelligence, artificial life, etc. is a plus, but not required.

The position offers competitive compensation and benefits. Compensation will be appropriate for the level of education and experience.

Please include all relevant information, date available, and several references.

Our offices are located 3 blocks from the Mountain View Cal Train station and Mountain View San Jose Light Rail Station in downtown Mountain View, California. Downtown Mountain View is an attractive and lively area with about 40 restaurants and various other shops and businesses.

Genetic Programming Inc. is an equal opportunity employer.

John R. Koza

Genetic Programming Inc. (Third Millennium On-Line Products Inc.)

Post Office Box K

Los Altos, California 94023 USA

FAX: 650-941-9430

E-mail: koza@genetic-programming.com

www.genetic-programming.com

Toward automated discovery in the biological sciences.

2007-09-15T15:13:00.002-07:00

Publication: AI Magazine
Publication Date: 22-MAR-04
Format: Online - approximately 11151 words
Delivery: Immediate Online Access
Author: Buchanan, Bruce G. ; Livingston, Gary R.

Article Excerpt
The biological sciences are rich with observational and experimental data characterized by symbolic descriptions of organisms and processes and their parts as well as numeric data from high-throughput experiments. The complexity of the data and the underlying mechanisms argue for providing computer assistance to biologists. Initially, computational methods for investigations of relationships in biological data were statistical (Sokal and Rohlf 1969). However, when the DENDRAL project demonstrated that AI methods could be used successfully for hypothesis formation in chemistry (Buchanan and Feigenbaum 1978; Buchanan, Sutherland, and Feigenbaum 1969), it was natural to ask whether AI methods would also be successful in the biological sciences. (1)

Data in the biological sciences have been growing dramatically, and much of the computational effort has been on organizing flexible, open-ended databases that can make the data available to scientists. After the initial demonstrations of the power of applying machine learning to biological databases (Harris, Hunter, and States 1992; Qian and Sejnowski 1988), the application of machine learning to biological databases has increased. It is now possible to carry out large-scale machine learning and data mining from biological databases. Catalysts for this research were the Intelligent Systems in Molecular Biology conferences, the first of which was held in 1993. This conference brought together people from diverse groups, all with the realization that biological problems were large and important and that there was a need for heuristic methods able to reason with symbolic information.

Toward Automated Discovery

The end point of scientific discovery is a concept or hypothesis that is interesting and new (Buchanan 1966). Insofar as there is a distinction at all between discovery and hypothesis formation, discovery is often described as more opportunistic search in a less well-defined space, leading to a psychological element of surprise. The earliest demonstration of self-directed, opportunistic discovery was Doug Lenat's program, AM (Lenat 1982). It was a successful demonstration of AI methods for discovery in a formal domain characterized by axioms (set theory) or rules (games). AM used an agenda-based framework and heuristics to evaluate existing concepts and then create new concepts from the existing concepts. It continued creating and examining concepts until the "interestingness" of operating on new or existing concepts (determined using some of AM'S heuristics) dropped below a threshold. Although some generalization and follow-up research with AM was performed (Lenat 1983), this research was limited to discovery in axiomatic domains (Haase 1990; Shen 1990; Sims 1987).

Our long-range goal is to develop an autonomous discovery system for discovery in empirical domains, namely, a program that peruses large collections of data to find hypotheses that are interesting enough to warrant the expenditure of laboratory resources and subsequent publication. Even longer range, we envision a scientific discovery system to be the generator of plausible hypotheses for a completely automated science laboratory in which the hypotheses can be verified experimentally by a robot that plans and executes new experiments, interprets their results, and maintains careful laboratory records with the new data.

Currently, machine learning and knowledge discovery systems require manual intervention to adjust one or more parameters, inspect hypotheses to identify interesting ones, and plan and execute new experiments. The more autonomous a discovery system becomes, the more it can save time, eliminate human error, follow multiple discovery strategies, and examine orders-of-magnitude more hypotheses in the search for interesting discoveries (Zytkow 1993).

AI research on experimental planning systems has produced numerous successful techniques that can be used in an automated laboratory. For example, Dan Hennessy has developed an experiment planner for the protein crystallization problem discussed later that uses a combination of Bayesian and case-based reasoning (Hennessy et al. 2000). Because the number of possibly interesting discoveries to be made in any large collection of data is open ended, a program needs strong heuristics to guide the selection of lines of investigation.

No published system completely combines all phases of the empirical discovery process, although planning systems for knowledge discovery in databases (KDD), such as the frame work presented in Engels (1996), perform sequences of tasks for a discovery goal provided by a user. Similarly, multistrategy systems such as that developed by Klosgen (1996) perform multiple discovery operations, but again, the discovery goals are provided by a user, as is evaluation of the discovered patterns. The research presented here describes and evaluates an agenda- and justification-based framework for autonomous discovery, coupled with heuristics for deciding which of many tasks are most likely to lead to interesting discoveries.

A Framework for Discovery

It is essential that a discovery program be able to reason about its priorities because there are many lines of investigation that it could pursue at any time and many considerations in its selection of one. Keeping an explicit agenda allows examination of the open tasks, and keeping explicit reasons why each task is interesting allows comparing relative levels of interest. We use an agenda- and justification-based framework, which is similar to the framework of the AM and EURISKO programs (Lenat 1983, 1982): It consists of an agenda of tasks prioritized by their plausibility. As in AM, a task on the agenda can be a call to a hypothesis generator to produce more hypotheses or explore some of the properties of hypotheses (or objects mentioned in them) already formed. Items are the objects or hypothesis (and sets of these) examined by the discovery program, and a task is an operation on zero or more items. For example, one task might be to find patterns (using an induction engine) in a subset of the data that have an interesting common property, such as being counterexamples to a well-supported rule. Although Lenat's programs discovered interesting conjectures in axiomatic domains such as set theory and games, those programs also contained general, domain-independent heuristics of the same sort used in empirical domains.

To evaluate our framework, we developed the prototype discovery program HAMB (Livingston 2001) that finds interesting, new relationships in collections of empirical data. (2) A key feature of HAMB is its domain-independent heuristics that guide the program's choice of relationships in data that are potentially interesting. HAMB'S primary generator of plausible hypotheses is an inductive generalization program that finds patterns in the data; in our case, it is the rule-induction program RL (Provost and Buchanan 1995). RL is an inductive generalization program that looks for general rules in a collection of data, where each rule is a conditional sentence of the form

IF [f.sub.1] and [f.sub.2] and ... and fn THEN class = K (with CF = c)

Each feature (f) relates an attribute (a variable) of a case to a named value, and a degree of certainty (CF) is attached to each rule as a measure of evidential support in the data; for example:

IF SEX = male and AGE

The conditional rule, which is easily understood by anyone who knows the meanings of the variable names, thus says that if a case matches all the antecedent conditions, then it is likely to be a member of the named class (K). Thus, the items in hamb's ontology are attributes, cases, rule conjuncts, and roles, plus sets of these. The cases and the attributes used to describe them are taken directly from the database.

On each cycle, heuristics can create tasks that result in new items or hypotheses, or tasks that examine some of the properties of those items or hypotheses. Each task must have accompanying text justifications for performing it, which are called reasons, qualitative descriptions of why a task might be worth performing (for example, sets of exceptions to general rules are likely to be interesting), and each reason must have an assigned strength, which is a relative measure of the reason's merit.

A task's plausibility is an estimate of the likelihood that performing the task will lead to interesting discoveries, and it is calculated as the product of the sum of the interestingness of the items involved in the task and the sum of the strengths corresponding to the reasons assigned to the tasks, as illustrated in the following equation:

Plausibility(T) = ([summation] [R.sub.T]) * {[summation] Interestingness(IT)}

where T is a task, ([R.sub.T]) is the set of the strengths of T's reasons, and {Interestingness(IT)} represents the sum of the estimated interestingness of T's items.

Tasks are performed using heuristics and, when executed, create new items for further exploration and place new tasks on the agenda. When proposing a new task, a heuristic must also provide reasons and corresponding strengths for performing the task. If new reasons are given for performing a task already on the agenda, then they are attached to the existing task, increasing its plausibility. Therefore, the framework provides three additional properties that Lenat (1982) identified as desirable when selecting the next task to perform:

First, the plausibility of a task monotonically increases with the strength of its reasons. Therefore, with all else being equal, a task with two reasons will have a greater plausibility than a task with only one of those reasons. If a new supporting reason is found, the task's value is increased. (3) The better that new reason, the bigger the increase.

Second, if a task is reproposed for the same reason(s), its plausibility is not increased.

Third, the plausibility of a task involving an item C should increase monotonically with the estimated interestingness of C. Two similar tasks dealing with two different concepts, each supported by the same list of reasons and strengths of reasons, should be ordered by the interestingness of those two concepts.

Thus, the top-level control of the framework is a simple loop: (1) calculate the plausibilities of the tasks; (2) select the task with the greatest plausibility; and (3) perform the task, possibly resulting in the creation or examination of items, the evaluation of relationships between items, and the proposal of new tasks. At the end of each iteration of this loop (called a discovery cycle), a stopping condition is checked to determine if further exploration is warranted. In our prototype program, HAMB, the stopping condition is that either the plausibility of all tasks on the agenda fails below a user-specified threshold (that is, no task is interesting enough), or the number of completed discovery cycles exceeds a user-defined threshold. In cases of repeated consideration of the same task, the system detects the possible deadlock...

NOTE: All illustrations and photos have been removed from this article.

Automated Scientific Discovery, the holy goal of AI? from AAAI

2007-09-15T15:13:00.001-07:00

"[Bruce] Buchanan was trained as a philosopher of science at a time when the profession was dominated by Popper's (1965) view that there is no logic of discovery. Buchanan stated the new research program:

'The traditional problem of finding an effective method for formulating true hypotheses that best explain phenomena has been transformed into finding heuristic methods that generate plausible explanations. The problem of giving rules for producing true scientific statements has been replaced by the problem of finding efficient heuristic rules for culling the reasonable candidates for an explanation from an appropriate set of possible candidates' [and finding methods for constructing the candidates].'"

-from Recent Work in Computational Scientific Discovery

Good Places to Start

2020 Computing: Exceeding human limits. Scientists are turning to automated processes and technologies in a bid to cope with ever higher volumes of data. But automation offers so much more to the future of science than just data handling. By Stephen H. Muggleton. Nature 440, 409-410 (23 March 2006). "During the twenty-first century, it is clear that computers will continue to play an increasingly central role in supporting the testing, and even formulation, of scientific hypotheses. This traditionally human activity has already become unsustainable in many sciences without the aid of computers. This is not only because of the scale of the data involved but also because scientists are unable to conceptualize the breadth and depth of the relationships between relevant databases without computational support. The potential benefits to science of such computerization are high -- knowledge derived from large-scale scientific data could well pave the way to new technologies, ranging from personalized medicines to methods for dealing with and avoiding climate change. [fn: Towards 2020 Science (Microsoft, 2006)]. ... Meanwhile, machine-learning techniques from computer science (including neural nets and genetic algorithms) are being used to automate the generation of scientific hypotheses from data. Some of the more advanced forms of machine learning enable new hypotheses, in the form of logical rules and principles, to be extracted relative to predefined background knowledge. ... One exciting development that we might expect in the next ten years is the construction of the first microfluidic robot scientist, which would combine active learning and autonomous experimentation with microfluidic technology."

'Knowledge discovery'. California Computer News (October 20, 2004). "In the recent science-fiction thriller 'Minority Report,' Tom Cruise plays a detective who solves future crimes by being immersed in a 'data cave,' where he rapidly accesses all the relevant information about the identity, location and associates of the potential victim. A team at Purdue University currently is developing a similar 'data-rich' environment for scientific discovery that uses high-performance computing and artificial intelligence software to display information and interact with researchers in the language of their specific disciplines. 'If you were a chemist, you could walk right up to this display and move molecules and atoms around to see how the changes would affect a formulation or a material's properties,' said James Caruthers, a professor of chemical engineering at Purdue. The method represents a fundamental shift from more conventional techniques in computer-aided scientific discovery. 'Most current approaches to computer-aided discovery center on mining data in a process that assumes there is a nugget of gold that needs to be found in a sea of irrelevant information,' Caruthers said. 'This data-mining approach is appropriate for some scientific discovery problems, but scientific understanding often proceeds through a different method, a 'knowledge discovery' approach. 'Instead of mining for a nugget of gold, knowledge discovery is more like sifting through a warehouse filled with small gears, levers, etc., none of which is particularly valuable by itself. After appropriate assembly, however, a Rolex watch emerges from the disparate parts.' ... Discovery informatics depends on a two-part repeating cycle made up of a 'forward model' and an 'inverse process' and two types of artificial intelligence software: hybrid neural networks and genetic algorithms."

Iridescent Software Illuminates Research Data. By Mike Martin. Sci-Tech Today (January 27, 2004). "Bioinformatics researchers at the University of Texas (UT) Southwestern Medical Center have developed Iridescent, a software program that helps scientists easily identify obscure commonalities in research data and directly relate them to their own work, saving money and speeding the process of discovery. 'This work is about teaching computers to 'read' the literature and make relevant associations so they can be summarized and scored for their potential relevance,' said Dr. Jonathan Wren, a researcher in the department of botany and microbiology at the University of Oklahoma. 'For humans to answer the same questions objectively and comprehensively could entail reading tens of thousands of papers.' ... Iridescent is unveiled in the current issue of the journal Bioinformatics"

Shared relationship analysis: ranking set cohesion and commonalities within a literature-derived relationship network. Wren JD, Garner HR. Bioinformatics. 2004 Jan 22;20(2):191-8. [Abstract]

Toward Automated Discovery in the Biological Sciences. By Bruce G. Buchanan and Gary R. Livingston. AI Magazine 25(1): Spring 2004, 69-84. "The end point of scientific discovery is a concept or hypothesis that is interesting and new (Buchanan 1966). Insofar as there is a distinction at all between discovery and hypothesis formation, discovery is often described as more opportunistic search in a less well-defined space, leading to a psychological element of surprise. The earliest demonstration of self-directed, opportunistic discovery was Doug Lenat's program, AM (Lenat 1982). It was a successful demonstration of AI methods for discovery in a formal domain characterized by axioms (set theory) or rules (games). AM used an agenda-based framework and heuristics to evaluate existing concepts and then create new concepts from the existing concepts. It continued creating and examining concepts until the 'nterestingness' of operating on new or existing concepts (determined using some of AM'S heuristics) dropped below a threshold. Although some generalization and follow-up research with AM was performed (Lenat 1983), this research was limited to discovery in axiomatic domains (Haase 1990; Shen 1990; Sims 1987). Our long-range goal is to develop an autonomous discovery system for discovery in empirical domains, namely, a program that peruses large collections of data to find hypotheses that are interesting enough to warrant the expenditure of laboratory resources and subsequent publication. Even longer range, we envision a scientific discovery system to be the generator of plausible hypotheses for a completely automated science laboratory in which the hypotheses can be verified experimentally by a robot that plans and executes new experiments, interprets their results, and maintains careful laboratory records with the new data."

A Machine With a Mind of Its Own - Ross King wanted a research assistant who would work 24/7 without sleep or food. So he built one. By Oliver Morton. Wired Magazine (August 2004, Issue 12.08). "The 'robot scientist' (King has resisted the temptation of a jazzy acronym) may look like a mere labor-saving gizmo, shuttling back and forth ad nauseam, but it's much more than that. Biology is full of tools with which to make discoveries. Here's a tool that can make discoveries on its own. ... It wasn't until he moved to Aberystwyth in the mid-'90s that King found comrades who fully appreciated the potential of AI and machine learning. One of the first people he encountered there was Douglas Kell, a voluble, handlebar-mustached biologist with a clear view of where his field was headed. ... Stephen Muggleton argues that the life sciences are peculiarly well suited to machine learning. 'There's an inherent structure in biological problems that lends itself to computational approaches,' he says. In other words, biology reveals the machinelike substructure of the living world; it's not surprising that machines are showing an aptitude for it."

Also see this related article: Mark of time. The Engineer Online (September 18, 2006). "A pioneering study at Manchester University is using a 'robot scientist' to examine blood samples for biological markers that may diagnose Alzheimer's disease. ... The robot scientist combines the automatic operation of a blood analysis technique called GCGC-MS with artificial intelligence to determine which experiment to carry out next. ... Douglas Kell, a professor of bioanalytical science at Manchester, was one of the developers of the robot scientist. 'The original idea was to automate the process of scientific discovery,' said Kell. 'There is a model by which we alternate the world of ideas with the world of experience. We carry out an experiment then revise our hypothesis in a cyclic loop. The robot scientist can combine working out what experiment is best to do next with actually carrying it out.' ... The robot uses Inductive Logic Programming, a machine learning process. The scientists give it the background knowledge about the experiment, called the domain. It then decides which hypothesis to follow using the available data."

Herbert A. Simon: Scientific Discovery. One of Professor Simon's departmental web pages (2001) at Carnegie Mellon University's Department of Psychology. "Understanding the processes scientists use to discover new laws and to test hypotheses has been an active domain of cognitive research and AI modeling for several decades, and was one of Herb Simon's chief areas of research activity. Scientific discovery is an interesting and important task domain because it involves highly ill-structured problems that call on the whole range of human cognitive resources, and thereby provides deep insights into complex and creative human thinking. ... Thus, research on scientific discovery requires one to address fundamental problems in cognitive psychology (the processes of discovery), in the philosophy of science (the relation between the discovery and validation, or disconfirmation, of hypotheses), and in computer science (languages for discovery, heuristic search in discovery environments)."

Also watch the video clip: BACON, an excerpt from Herbert Simon's talk: AI: What Can it Do? Where is it Going? (March 21, 1990). Available from the Carnegie Mellon University Archives' exhibit: Mind Models - Artificial Intelligence Discovery At Carnegie Mellon: Into the Future.

Readings Online

A robot that likes to play with test tubes. By David Akin. The Globe & Mail (January 17, 2004). "[The Robot Scientist] probably will become a vital tool for researchers, particularly in biological fields, to advance human knowledge. That is because in many scientific areas, such as nanotechnology, molecular genetics and the exploration of space, information is being generated too fast for humans to analyze it effectively. 'Biology is in a great data-gathering phase at the moment, a bit like it was in the 19th century,' said Stephen Oliver, a professor and genomics researcher at the University of Manchester in England and another of the eight researchers. The Human Genome Project, the monster science project that identified and explained the function of the genes in a human being, made great use of computers and sophisticated software programs to automate the scientific discovery progress. Indeed, there is now a branch of artificial intelligence research devoted to scientific discovery."

Robo-scientist goes it alone. BBC News (January 14, 2004). "The world's first 'robot scientist' that can interpret experiments without any human help has been developed by scientists at the University of Wales, Aberystwyth. It generates a set of hypotheses from what it knows about biochemistry, and then designs experiments to test them. ... Although artificial intelligence has made a number of significant contributions to scientific discovery during the last 30 years, its general impact on experimental science has been limited. But this may be about to change with the increased use of automation in scientific research."

Undergraduate Projects in the Application of Artificial Intelligence to Chemistry. II Self-organizing Maps. By Hugh Cartwright. (2000). The Chemical Educator, Volume 5, Issue 4; 196-206. "The determination of relationships among samples is a task to which Artificial Intelligence is increasingly being applied. In this paper we investigate the Self-Organizing Map (SOM), whose role is to perform just this kind of task; in other words, to cluster data samples so as to reveal the relationships that exist among them."

More resources are available from Dr H.M. Cartwright's home page and research group page at the Physical & Theoretical Chemistry Laboratory, University of Oxford.

Artificial Intelligence and Scientific Creativity. By Simon Colton and Graham Steel, Division of Informatics, University of Edinburgh. "Papers presented at the [the 1999 AISB Symposium on AI and Scientific Creativity, which took place in Edinburgh, Scotland] addressed the theoretical aspects of and computational possibilities for machine creativity. They also reported on systems implemented to achieve automated discovery in science. The intention of the symposium was that that the papers proposing models of scientific creativity would help researchers concerned with implementing discovery programs, and the papers discussing the successes and techniques employed in working systems will help researchers extract general frameworks for scientific machine discovery. This note is a survey of current research on creativity in science, and in particular the automation of discovery tasks in science."

Recent Work in Computational Scientific Discovery. By Lindley Darden. In Proceedings of the Nineteenth Annual Conference of the Cognitive Science Society. Michael Shafto and Pat Langley (Eds.). Mahwah, New Jersey: Lawrence Erlbaum, 1997, pp. 161-166. "The study of computational scientific discovery emerged from the view that science is a problem solving activity, that heuristics for problem solving can be applied to the study of scientific discovery in either historical or contemporary cases, and that methods in artificial intelligence provide techniques for building computational systems. Pioneers in this work are Bruce Buchanan (e.g., 1982) and Herbert Simon (e.g., 1977)."

Also by Lindley Darden (1998): Anomaly-Driven Theory Redesign: Computational Philosophy of Science Experiments. In T.W. Bynum and J.H. Moor, The Digital Phoenix: How Computers are Changing Philosophy. New York: Blackwell Publishers, pp. 62-78. " I have been asked to discuss how computers have affected my work in philosophy. This paper discusses the use of artificial intelligence (AI) models to investigate both the representation of scientific knowledge and reasoning strategies for scientific change. The focus is on the reasoning strategies used to revise a theory, given an anomaly, which is a failed prediction of the theory."

The computer revolution in science: Steps towards the realization of computer-supported discovery environments. By H. de Jong and A. Rip. (1997). Artificial Intelligence, 91(2). "The tools that scientists use in their search processes together form so-called discovery environments. The promise of artificial intelligence and other branches of computer science is to radically transform conventional discovery environments by equipping scientists with a range of powerful computer tools including large-scale, shared knowledge bases and discovery programs." -from the Abstract.

The Computer-Aided Discovery of Scientific Knowledge. By Pat Langley. 1998. Proceedings of the First International Conference on Discovery Science. "In this paper, we review AI research on computational discovery and its recent application to the discovery of new scientific knowledge. ... As evidence for the advantages of such human-computer cooperation, we report seven examples of novel, computer-aided discoveries that have appeared in the scientific literature...."

More of Pat Langley's publications can be found in his Computational Scientific Discovery collection which begins with this historical note: "I became fascinated with the nature of scientific discovery as an undergraduate at TCU, and the interest has remained to this day. My dissertation work at CMU focused on Bacon, an AI system that rediscovered numeric laws from the history of physics. Herbert Simon served as my advisor and contributed many ideas to the effort. Gary Bradshaw and I extended the system to handle additional laws, including ones from the history of chemistry. After Jan Zytkow joined our group, we developed new systems (Stahl and Dalton) that dealt with the discovery of qualitative laws and structural models. This CMU work forms the basis of my early publications on scientific discovery...."

Towards 2020 Science. Produced under the aegis of Microsoft Research Cambridge (2006). "In the summer of 2005, an international expert group was brought together for a workshop to define and produce a new vision and roadmap of the evolution, challenges and potential of computer science and computing in scientific research in the next fifteen years. The resulting document, Towards 2020 Science, sets out the challenges and opportunities arising from the increasing synthesis of computing and the sciences." In addition to the report and the roadmap, be sure to see the related, special issue of Nature.

Introducing robo-scientist - Could robots take over from graduate students in the lab? By Mark Peplow. Nature (January 15, 2004). "A robot scientist has been unveiled that can formulate theories, carry out experiments and interpret results - all more cheaply than its human counterparts. As far as artificial intelligence goes, the Robot Scientist - designed by Ross King of the University of Wales in Aberystwyth, UK, and his colleagues - isn't as smart as other computers, such as those that compete in international chess competitions. But combining the smarts of a computer with the agility of a robot wasn't trivial. ... Geneticist Stephen Oliver of the University of Manchester, UK, who helped to select the robot's research project, says there is potential for the robot to more than just drudgery. 'The next big step is to make our robot discover something completely new,' says Oliver, 'perhaps by applying it to drug discovery.'"

The journal article: Oliver, S. G. et al. Functional genomic hypothesis generation and experimentation by a robot scientist. Nature, 427, 247 - 252, doi:10.1038/nature02236 (2004).
And consider this: A Robot Scientist - As ye sow... A machine can now do science. The Economist (January 15, 2004). "One question is, if their robot does make an important discovery, will it be eligible to win a Nobel prize?"

Editorial: Scientific Discovery and Simplicity of Method. By Herbert A. Simon, Raul E. Valdes-Perez and Derek H. Sleeman. (1997). Artificial Intelligence, 91(2):177-181. ""[C]omplexity of programs or of their outputs is not a measure of their 'intelligence'. Given very complex tasks, complex algorithms may be a necessity, but they are clearly not a virtue. A critical lesson of artificial intelligence, and of computing in general, is that if a task domain has strong structure and if sufficient domain information can be obtained, either a priori or in the course of computation, then rather simple programs may suffice."

Systematic Methods of Scientific Discovery: Papers from the 1995 Spring Symposium, ed. Raul Valdes-Perez. Technical Report SS-95-03. American Association for Artificial Intelligence, Menlo Park, California. Here are just some of the papers you'll find in this collection:

Herbert A. Simon's What is a Systematic Method of Scientific Discovery?
Pat Langley's Stages in the Process of Scientific Discovery.
Joshua S. Lederberg's Notes on Systematic Hypothesis Generation, and Application to Disciplined Brainstorming.

Some Recent Human-Computer Discoveries in Science and What Accounts for Them. By Raul E. Valdes-Perez. AI Magazine 16(3): Fall 1995, 37-44. "My collaborators and I have recently reported in domain science journals several human-computer discoveries in biology, chemistry, and physics. One might ask what accounts for these findings, for example, whether they share a common pattern. My conclusion is that each finding involves a new representation of the scientific task: The problem spaces searched were unlike previous task problem spaces. Such new representations need not be wholly new to the history of science; rather, they can draw on useful representational pieces from elsewhere in natural or computer science. This account contrasts with earlier explanations of machine discovery based on the expert system view. My analysis also suggests a broader potential role for (AI) computer scientists in the practice of natural science."

Also see his collection of Scientific Discovery Resources.

Neural Networks Meet CombiChem. By Emil Venere. Bio.com (January 22, 2002). "The different types of software work together in a repeating two-phase cycle of discovery. First, hybrid neural networks analyze the formulas of the numerous catalysts, or other materials, created by the parallel technique. The neural networks determine the properties of the materials, based on their chemical structures. In the second phase, genetic algorithms cull the best materials and eliminate the poor performers, just like survival of the fittest. The algorithms also generate 'mutations' of the best materials to create even better versions, and the software determines the chemical structures of those mutations. The resulting formulas are returned to the neural network software, and the cycle starts over again, progressively creating better and better materials, said Venkat Venkatasubramanian, a professor of chemical engineering who has been working with Caruthers to develop the software for more than a decade. [James M.] Caruthers said he observes how formulation chemists come up with new ideas. Then he models their trains of thought in software programs."

Text-Based Discovery in Biomedicine: The Architecture of the DAD-system. By M. Weeber, H. Klein, A. R. Aronson, J. G. Mork, L. Jong-van den Berg, and R. Vos. Presented at The American Medical Informatics Association 2000 Symposium. "Current scientific research takes place in highly specialized contexts with poor communication between disciplines as a likely consequence. Knowledge from one discipline may be useful for the other without researchers knowing it. As scientific publications are a condensation of this knowledge, literature-based discovery tools may help the individual scientist to explore new useful domains. We report on the development of the DAD-system, a concept-based Natural Language Processing system for PubMed citations that provides the biomedical researcher such a tool."

Related Web Sites

"ARROWSMITH is interactive software that extends the power of a MEDLINE search. It operates on the output of a conventional search in a way that helps the user see new relationships and form and assess novel scientific hypotheses. It is based on the premise that information developed in one area of research can be of value in another without anyone being aware of the fact." At this site, which is maintained by Don R. Swanson at The University of Chicago, you'll find articles and manuals that show you how it works.

Imperial College Computational Bioinformatics Laboratory (CBL):

Scientific Knowledge Discovery using ILP (Inductive Logic Programming). I"ILP algorithms take examples E of a concept (such as a protein family) together with background knowledge B (such as a definition of molecular dynamics) and construct a hypothesis H which explains E in terms of B.
- Also see: Inductive Logic Programming (ILP) Applications. Part of Professor Stephen Muggleton's Inductive Logic Programming resource.
The HR System - Automated Theory Formation. Originally developed by Simon Colton at the Universities of Edinburgh and York. Currently being developed in The Computational Bioinformatics Group of The Department of Computing at Imperial College, London. "The HR system performs automated theory formation. Given background information about a domain, HR invents concepts, calculates examples, makes hypotheses and seeks explanations of the hypotheses."
- Also see: Simon Colton's Research Pages and this collection of links to other sites from his original PhD project about HR

Related Pages

More Readings

Scientific Discovery - Computational Explorations of the Creative Processes. By Pat Langley, Herbert A. Simon, Gary L. Bradshaw and Jan M. Zytkow. The MIT Press (February 1987). "Using the methods and concepts of contemporary information-processing psychology (or cognitive science) the authors develop a series of artificial-intelligence programs that can simulate the human thought processes used to discover scientific laws. The programs - BACON, DALTON, GLAUBER, and STAHL - are all largely data-driven, that is, when presented with series of chemical or physical measurements they search for uniformities and linking elements, generating and checking hypotheses and creating new concepts as they go along."

Molecular Treasure Hunt - A software tool elicits previously undiscovered gene or protein pathways by combing through hundreds of thousands of journal articles. By Gary Stix. Scientific American (May 2005; subscription req'd.). "When Andrey Rzhetsky arrived at Columbia University as a research scientist in 1996, the first project he collaborated on involved a literature search to try to understand why white blood cells called lymphocytes do not die in chronic lymphocytic leukemia. The mathematician-biologist found a few hundred articles on apoptosis (programmed cell death) and the cancer.... The experience led him to an idea that would have made his job on that first project much easier: an automated search tool that could supplant the mind-numbing task of finding and reading all the literature. But it also might do much more; it could even let a machine conduct research on its own, discovering the patterns among the data much as a human would do...."

FYI: As explained in this announcement, on March 1, 2007 AAAI changed its name from the American Association for Artificial Intelligence to the Association for the Advancement of Artificial Intelligence.

Automated Discovery research by Dr. Zytkow at UNCC

2007-09-15T14:57:00.000-07:00

Publications

Asterisks mark papers published in languages other than English.
Titles of those papers are translated into English.

Ras, Z. & Zytkow, J.M. 2000. Mining for Attribute Definitions
in a Distributed Two-Layered DB System, Journal of
Intelligent Information Systems, 14, p.115-130

Ossowski, A., & Zytkow, J.M. 2000. Geometrical
Approach to a Coherent Set of Operational Definitions, in
M.Klopotek, M.Michalewicz & S.Wierzchon eds. Intelligent
Information Systems, Proceedings of the IIS'2000 Symposium,
Bystra, Poland, June 12-16, 2000, Physica-Verlag, p.109-117.

Zytkow, J.M. 2000. Granularity refined by knowledge: contingency
tables and rough sets as tools of discovery, in B.Dasarathy ed.
Data Mining and Knowledge Discovery: Theory, Tools, and
Technology II, SPIE, p.82-91.

Zytkow, J.M. 2000. Automated Discovery: A Fusion of
Multidisciplinary Principles, in H.Hamilton, ed.
Advances in Artificial Intelligence, Springer,
p. 443-448.

Suzuki, E. & Zytkow, J.M. 2000. Unified Algorithm for
Undirected Discovery of Exception Rules, in D.Zighed,
J.Komorowski & J.Zytkow, eds. Principles and Practice
of Data Mining and Knowledge Discovery, Springer, p.169-180

Zytkow, J.M., Tsumoto, S. & Takabayashi, K. 2000.
Medical (Thrombosis) Data Description, in A.Siebes & P.Berka
eds. Discovery Challenge, PKDD-2000.

Zytkow, J.M. & Ras, Z. 2000. Foundations and Discovery of
Operational Definitions, in Z.Ras & S.Ohsuga, eds.
Foundations of Intelligent Systems, Springer, p.582-590.

Zytkow, J.M. 1999. The Melting Pot of Automated Discovery:
Principles for a New Science, in S.Arikawa & K.Furukawa eds.
Discovery Science; Second International Conference; Tokyo,
Dec 1999, Springer, p.1-12.

Zytkow, J.M. 1999. Robot-Discoverer: a Role Model for Any
Intelligent Agent, in J.Liu & N.Zhong eds. Intelligent
Agent Technology; Proceedings of the 1st Asia-Pacific
Conference, World Scientific, p.9-14.

Zytkow, J.M. 1999. Scientific Modeling: A Multilevel Feedback
Process, in L.Magnani, N.Nersessian, & P.Thagard eds.
Model-Based Reasoning in Scientific Discovery}, Kluwer,
p.311-325.

Zytkow, J.M. 1999. Knowledge-Driven Discovery of Operational
Definitions, in N.Zhong, A.Skowron & S.Ohsuga eds. New
Directions in Rough Sets, Data Mining, and Granular-Soft
Computing, Springer, p.395-404

El-Mouadib, F.A., Koronacki, J. & Zytkow, J.M. 1999.
Taxonomy formation by Approximate equivalence relations,
Revisited, in: J.Zytkow & J.Rauch eds. Principles of Data
Mining and Knowledge Discovery, Springer, p.71-79.

Przybyszewski, A.W. & Zytkow, J.M. 1999. Extracting knowledge
from data recorded in primates visual system, in M.Klopotek &
M.Michalewicz eds. Intelligent Information Systems,
Proceedings of the Workshop held in Ustron, Poland, 14-18 June
1999. Instytut Podstaw Informatyki PAN. p.92-96.

Zytkow, J.M. 1999. Discovery of Concept Expansions, in
M.Klopotek & M.Michalewicz eds. Intelligent Information
Systems, Proceedings of the Workshop held in Ustron, Poland,
14-18 June 1999. Instytut Podstaw Informatyki PAN. p.117-126

Cwik J., Koronacki J. & Zytkow, J.M. 1999. On discovering
functional relationships when observations are noisy: 2D case,
in Ras Z. & Skowron A. Foundations of Intelligent
Systems, Springer-Verlag, p.547-555.

Zytkow, J.M. 1999. Dualism: consciousness evades scientific and
computer reductionism, in: E.Lucius & S.Ural eds. Artificial
Intelligence, Language and Thought, The ISIS Press, Istanbul,
p.95-110.

Zytkow, J. 1999. Model construction: elements of a computational
mechanism, in Proceedings of the AISB'99 Symposium on
Scientific Creativity, Edinburgh, April 1999, p.65-71.

Ras, Z.W. & Zytkow, J.M. 1999. Discovery of Equations and the
Shared Operational Semantics in Distributed Autonomous
Databases, in N.Zhong and L.Zhou eds. Proceedings of Third
Pacific-Asia Conference on Knowledge Discovery in Databases,
Beijing, Springer-Verlag, p. 453-463.

Zytkow, J.M. & Ras Z. 1999. Mining Distributed Databases for
Attribute Definitions, in B.Dasarathy ed. Data Mining
and Knowledge Discovery: Theory, Tools, and Technology,
SPIE, p.171-178.

Consciousness Defies Scientific and Computational Reduction,
Foundations of Science, 4, 1998.

Proving that consciousness defies reduction; a response to
Steve Horst, Foundations of Science, 4, 1998.

Modeling the Business Process by Mining Multiple Databases,
Principles of Data Mining and Knowledge Discovery,
Springer-Verlag, 1998. p.432-440.

Robot-discoverer: a new platform to expand methodology
(abstract), International Congress on Discovery and
Creativity, Univ. of Ghent, 1998. p. 174-175.

Measuring the unknown: knowledge-driven discovery of concept
expansions, Machine Discovery; ECAI-98 Workshop,
1998. p.30-36.

Business Process Understanding: Mining Many Datasets (with
A. Sanjeev), Rough Sets and Current Trends in Computing,
Springer-Verlag, 1998. p. 239-246.

Robot-discoverer: artificial intelligent agent who searches for
knowledge, Proceedings of High Technology Symposium
Yamaguchi '97, 1997, p.11-18.

Discovering Empirical Equations from Robot-Collected Data, (with
K-M. Huang), in Ras Z. & Skowron A., Foundations of
Intelligent Systems, Springer-Verlag, 1997. p. 287-297.

Techniques and Applications of KDD, (abstract, with
W. Kloesgen), in: Komorowski J. & Zytkow J. eds.
Principles of Data Mining and Knowledge Discovery,
Springer-Verlag, 1997, p.394.

Limited view of knowledge in database discovery, in: Proceedings
of the Fifth International Workshop on Rough Sets and Soft
Computing, 1997. 6 pages.

Automated Search for Knowledge on Machinery Diagnostics,
(with W. Moczulski) in: Proceedings of Sixth Symposium on
Intelligent Information Systems, 1997.

Creating a Discoverer: Autonomous Knowledge Seeking Agent, in:
J. Zytkow ed. Machine Discovery, Kluwer, 1997, p.253-283.

Knowledge = Concepts: a harmful equation, in Proceedings of
KDD-97, AAAI Press, 1997. p. 104-109.

Theories That Combine Many Equivalence and Subset Relations
(with Zembowicz R.) in: T.Y. Lin and N. Cercone eds. Rough
Sets and Data Mining : Analysis of Imprecise Data, Kluwer Publ.
1997. p.323-336.

Contingency Tables as the Foundation for Concepts, Concept
Hierarchies and Rules, (with R. Zembowicz),
Fundamenta Informatica, 1997.

Robotic Discovery: the dilemmas of empirical equations (with
K-M. Huang), Proceedings of the Fourth International
Workshop on Rough Sets, Fuzzy Sets, and Machine Discovery, The
Univ. of Tokyo, Nov. 1996, p. 217-224.

Knowledge Discovery in Databases: 49er's Approach,
Proceedings of the Fourth International Workshop on Rough Sets,
Fuzzy Sets, and Machine Discovery, The Univ. of Tokyo,
Nov. 1996, p. 445-446.

Systematic Generation of Constituent Models of Particle Families
(with R.E.Valdes-Perez), Physical Review E, Vol.54,
p.2102-2110, 1996.

From Statistical Regularities to Concepts, Hierarchies, Equation
Clusters and Rules, in: Dowe D., Korb K.B., Oliver J.J. eds.
Information, Statistics and Induction in Science,
World Scientific, 1996. p.269-280.

A Study of Enrollment and Retention in a University Database
(with Arun Sanjeev), Journal of the Mid-America Association
of Educational Opportunity Program Personnel, Vol.8, p. 24-41,
1996.

Empirical discovery: linking data and physical processes,
in: Proceedings of the 5th International
Symposium on Intelligent Information
Systems, Deblin, Poland, June 1996.

Automated pattern mining with a scale dimension (with
R.Zembowicz), Proceedings of 2nd International Conference
on Knowledge Discovery and Data Mining, Aug.1996. p.158-163.

Incremental Discovery of Hidden Structure: Application to
Elementary Particles, (with P. Fischer),
Proceedings of the Fourteenth National Conference
on Artificial Intelligence, The AAAI Press, p.750-756. 1996.

Search for Patterns at Each Scale in Massive Data, (with
R. Zembowicz), in Ras Z. & Michalewicz M. ed. Foundations
of Intelligent Systems, Springer-Verlag, p. 139-148. 1996.

Approximate knowledge of many agents and discovery systems,
in Bulletin of the Section of Logic, Polish
Academy of Sciences, 1996, p.185-9. 1996.

Automated Discovery of Empirical Laws, Fundamenta
Informatica, 27, p. 299-318, 1996.

From contingency tables to various forms of knowledge in
databases (with R.Zembowicz), in: Fayyad U., Piatetsky-Shapiro G.,
Smyth P. & Uthurosamy eds. Advances in Knowledge Discovery
and Data Mining, AAAI Press, 1996. pp.329-349.

Machine Discovery Terminology (with W. Kloesgen), in:
Fayyad, U., Piatetsky-Shapiro G., Smith P. & Uthurusamy R. eds.
Advances in Knowledge Discovery and Data mining. AAAI Press,
1996, pp. 573-592.

* Scientific and Computer Reductionism and the Contents of
Consciousness, Filozofia Nauki (Philosophy of
Science) (in Polish), p. 147-160. 1995.

* Automation of Discovery: a New Methodology and Philosophy of
Science (in Polish), in Pietruska-Madej E. & Strawinski W. eds.
On the Problems of Contemporary Theory of Knowledge, University
of Warsaw, p.43-71, 1995.

Discovering Patterns at Different Scale in Massive Data,
(with R. Zembowicz), in Proceedings of
the 4th International Symposium on Intelligent Information
Systems, Augustow, Poland, June 1995.

Creating a Discoverer: Autonomous Knowledge Seeking Agent,
Foundations of Science, 1, 253-283. 1995.

Discovering Enrollment Knowledge in University Databases
(with A. Sanjeev), Proc. of 1st Intern. Conference on Knowledge
Discovery and Data Mining, Montreal, Aug. 1995, 6 pages.

Tolerance Based Rough Sets (with L. Polkowski A. Skowron), in
Lin T.Y. & A.M.Wilddberger eds. Rough Sets and Soft
Computing, 1995. p.55-59.

Mining Student Databases for Enrollment Patterns (with A.
Sanjeev), ed. Y.Kodratoff, G.Nakhaeizadeh, Ch.Taylor eds.
MLnet Workshop on Statistics, Machine Learning and Knowledge
Discovery in Databases, 1995. pp. 204-209.

Scientific modeling: round trips to many destinations,
AAAI-95 Spring Symposium on Systematic Methods
of Scientific Discovery, 1995, p.175-180.

Geobotanical database exploration (with I.Moraczewski and
R.Zembowicz), AAAI-95 Spring Symposium on Systematic
Methods of Scientific Discovery, 1995, p. 76-80.

Theories that combine many equivalence and subset relations
(with R.Zembowicz), in: T.Y.Lin ed. CSC'95 Workshop on
Rough Sets and Database Mining, 1995, 8 pages

Law-Like Knowledge as the Foundation for Concepts, Concept
Hierarchies and Rules (with R. Zembowicz) in Proceedings of
the 3rd International Symposium on Intelligent Information
Systems, Wigry, Poland, June 1994. Published in 1995.

Abstract Intelligent Agents: Basic Concepts and Problems (with
Gadomski, A.), in Proceedings of the Round Table on Abstract
Intelligent Agents, ENEA, Rome, Italy. 9 pages, Published in
1995.

Searching for the unknown: machine discoverer assesses its
state of knowledge, in Gadomski A. ed. Proceedings of the
Round Table on Abstract Intelligent Agents, Rome, Feb.1994,
Published in 1995.

Rough Foundations for Rough Sets (with L. Polkowski A. Skowron)
in Proceedings of the 3rd International Workshop on Rough Sets,
1994, p.142-149.

Concept Hierarchies: a Restricted Form of Knowledge Derived
from Regularities (with M.Troxell, K.Swarm, and R.Zembowicz),
in: Zemankova M. and Ras Z. eds. Methodologies for Intelligent
Systems, Springer-Verlag, 1994, p.437-447.

Machine discoverers: transforming the spaces they explore,
Behavioral and Brain Science, Vol.17, 1994, p.557-558.

Discovery of Hidden Objects and Structures, in Omyla M. ed.
Nauka i Jezyk (Science and Language), Polish Semiotic Society,
Warsaw, 1994, p. 475-495.

From Law-Like Knowledge to Concept Hierarchies in Data
(with M.Troxell, K.Swarm, and R.Zembowicz), in: Fayyad U.
and Uthurusamy, R. eds. Proceedings of AAAI-94 Workshop on
Knowledge Discovery in Databases, 1994, p.193-204.

Report: Foundations for testing the SWOE models. WSU/FIMTSI-SWOE
Research Group, July 1994. 69 pages.

Control of Automated Empirical Discovery by Diagrammatic
Representation of Theory (with Zhu, J.), in Narayanan H. ed.
Reasoning with Diagrammatic Representations, AAAI Press,
1994. (reprinted from Working Notes of the AAAI
Spring Symposium on Reasoning with Diagrammatic Representations).

Experimentation Guided by a Knowledge Graph (with Zhu, J.)
in: Learning Action Models, Shen W. ed. AAAI Press, 1994.
(reprinted from Proceedings of the AAAI-93 Workshop on Learning
Action Models).

Automated discovery of empirical laws in a science laboratory,
in: Rough Sets, Fuzzy Sets and Knowledge Discovery, Ziarko
W. ed. Workshops in Computing, Springer-Verlag, 1994,
p.119-129.

Putting Together a Machine Discoverer: Basic Building Blocks,
in MLnet NEWS, Vol.2 No.3, 1994, p.19--22.

* Machine Discovery: Current State and Perspectives,
Filozofia Nauki, 1, No.4, 1993, p.37-54.

Scientific Discovery (with Langley, P., Simon, H., and
Bradshaw, G.), in Readings in Philosophy and Cognitive Science,
Goldman A. ed. MIT Press, 1993, p.185--207 (reprinted part of
the book: Scientific Discovery, 1987).

Feedback between knowledge and method in automated discovery,
in Proceedings of 2nd Intelligent Information Systems
Workshop, IPI PAN, Warsaw, 1993, p.282--298.

Discovery of Theorems in Plane Geometry (with V. Shanbhogue,
R. Bagai, S.-C. Chou) Proceedings of the 10th Brazilian
Symposium on Artificial Intelligence, Porto Alegre, Brazil,
October 1993, p.155--167.

Machine Discoverers: Autonomous Intelligent Agents who Explore
Their Environments, in Proceedings of the Abstract Intelligent
Agents Round Table, Rome, ENEA, 1993, p.27--32.

Testing the existence of Functional Relationships in Data (with
Zembowicz, R.) in Piatetsky-Shapiro G. ed. Proceedings of the
AAAI-93 Workshop on Knowledge Discovery in Databases, 1993,
p.102--111.

Experimentation guided by a knowledge graph (with Zhu, J.);
in Shen W. ed. Proceedings of the AAAI-93 Workshop on Learning
Action Models, 1993, p.23--27.

Scientific Model-Building as Search in Matrix Spaces (with
Valdes-Perez, R. and Simon, H.) in Proceedings of the Eleventh
National Conference on Artificial Intelligence, The AAAI Press,
1993, p.472--478.

Automatic theorem generation in plane geometry (with Bagai, R.,
Shanbhogue, V., Chou, S.C.), in Proceedings of 5th Intern. Conf. on
Computing and Information, Sudbury, Ont. Canada, 1993, p.354--358.

Recognition of functional dependencies in data (with Zembowicz,
R.), in Komorowski J. and Ras Z. eds. Methodologies for
Intelligent Systems, Springer-Verlag, 1993, p.632--641.

Automatic theorem generation in plane geometry (with Bagai, R.,
Shanbhogue, V., Chou, S.C.), in Komorowski J. and Ras Z. eds.
Methodologies for Intelligent Systems, Springer-Verlag,
1993, p.415--424.

Cognitive Autonomy in Machine Discovery, Machine
Learning, Vol.12, 1993, p.7--16.

Database exploration in search of regularities (with Zembowicz,
R.) Journal of Intelligent Information Systems,
Vol.2, 1993, p.39--81.

Incremental Generation and Exploration of Hidden Structure (with
Fischer, P.), in Proceedings of the ML-92 Workshop on Machine
Discovery, July 1992, Aberdeen, U.K., p.103--110.

Discovery of Regularities in Databases (with Zembowicz, R.), in
Proceedings of the ML-92 Workshop on Machine Discovery.
July 1992, Aberdeen, U.K. p.18--27.

A Graph Representation of an Empirical Theory: Guiding a Machine
Discovery Process (with Zembowicz, R. and Zhu, J.), in Kishore S.
ed. Proceedings of AAAI-92 Workshop on Communicating Scientific
and Technical Knowledge, July 1992, p.81--88.

Discovery of Equations: Experimental Evaluation of Convergence (with
Zembowicz R.), Proceedings of the Tenth National Conference on
Artificial Intelligence, The AAAI Press, 1992, p.70--75.

Operational Definition Refinement: a Discovery Process (with Zhu,
J., and Zembowicz R.), Proceedings of the Tenth National Conference
on Artificial Intelligence, The AAAI Press, 1992, p.76--81.

A Framework for Discovering Discrete Event Models (with Radiya, A.),
in Machine Learning: Proceedings of the Ninth International
Conference, July 1992, Aberdeen, United Kingdom. Morgan Kaufmann Publ.
p.373--378.

The First Phase of Real-World Discovery: Determining Repeatability
and Error of Experiments (with Zhu, J. and Zembowicz, R.), in
Machine Learning: Proceedings of the Ninth International Conference,
July 1992, Aberdeen, United Kingdom. Morgan Kaufmann Publ. p.480--485.

Control of Automated Empirical Discovery by Diagrammatic
Representation of Theory (with Zhu, J.), in Narayanan H. ed.
Working Notes of the AAAI Spring Symposium on Reasoning with
Diagrammatic Representations, Palo Alto, CA, March 1992. p.176--179.

Automated Discovery of Empirical Equations from Data (with
Zembowicz, R), in Ras Z. and Zemankova M. eds. Methodologies for
Intelligent Systems, Springer-Verlag, 1991, p.429--440.

Constructing Models of Hidden Structure (with Fischer, P), in Ras Z.
and Zemankova M. eds. Methodologies for Intelligent Systems,
Springer-Verlag, 1991, p.441--449.

Human Discovery of Laws and Concepts; An Experiment
(with Zytkow, A), in Proceedings of the 13th Cognitive Science
Conference, Lawrence Earlbaum Associates, 1991, p.617--622.

Automated Empirical Discovery in a Numerical Space (with Zhu, J),
in the Proceedings of the Third Annual Chinese Machine Learning
Workshop, July 15--19, 1991, Harbin Institute of Technology, p.1--11.

Cashing in on the Regularities Discovered in a Database (with
Jafar, M), in Piatetsky-Shapiro, G. ed. Proceedings of the AAAI-91
Workshop on Knowledge Discovery in Databases, Anaheim, July 1991,
p.133--147.

The KDD Land of Plenty, in Piatetsky-Shapiro, G. ed. Proceedings
of the AAAI-91 Workshop on Knowledge Discovery in Databases,
Anaheim, July 1991, p.iii--vi.

Integration of Knowledge and Method in Real-World Discovery,
SIGART, 1991.

Interactive Mining of Regularities in Databases (with J. Baker),
in Piatetsky-Shapiro, G. and Frawley, W. eds. Knowledge Discovery
in Databases, The AAAI Press, Menlo Park, CA. 1991.

An Architecture for Real-World Discovery, in Proceedings of
the AAAI Spring Symposium on Integrated Intelligent Architectures,
Palo Alto, CA, March 1991, p. p.170--174.

Application of Empirical Discovery in Knowledge Acquisition
(with Zhu, J), in Kodratoff, Y. ed. Proceedings of the European
Workshop Session on Learning, Porto, Portugal. Berlin:
Springer-Verlag, 1991, p.101--117.

Data-driven Approaches to Empirical Discovery (with Pat Langley),
in Carbonell, J. ed. Machine Learning: Paradigms and Methods,
Boston: MIT Press, 1990.

Database Analyzer; User Instruction, (with Baker, J., Jafar, M.,
and Tjong M.), Technical Report, Computer Science Department,
Wichita State University, 1990.

Minds beyond brains and algorithms, Behavioral and Brain Sciences,
December, 1990, p.691--692.

Determining Repeatability and Error in Experimental Results by a
Discovery System (with Zhu, J., and Hussam A.) , in: Ras Z.,
Zemankova M., and Emrich M.L., eds. Methodologies for
Intelligent Systems 5, Elsevier Science Publishing Co., Inc.,
New York, NY, 1990, p.362--370.

Discovering Quarks and Hidden Structure (with Fischer, P.), in:
Ras Z., Zemankova M., and Emrich M.L., eds. Methodologies for
Intelligent Systems 5, Elsevier Science Publishing Co., Inc.,
New York, NY, 1990, p.362--370.

Analytical Chemistry: the Science of Many Models(with A. Lewenstam)
Fresenius Journal for Analytical Chemistry, Vol. 338, 1990,
p.225--233.

Automated Discovery in a Chemistry Laboratory (with Zhu, J., and
Hussam A.) , In: Proceedings of the Eight National Conference
on Artificial Intelligence, The AAAI Press, 1990, p.889--894.

Real-World Knowledge Acquisition by Discovery, in A.Rappaport ed.
Proceedings of the AAAI-90 Workshop on Knowledge Acquisition},
Boston, July 1990.

Deriving Laws by Analysis of Processes and Equations, in:
Langley, P., and Shrager J. eds. Computational Models of
Scientific Discovery and Theory Formation, Morgan Kaufmann, San
Mateo:CA, 1990, p.129--156.

* On scientific modeling (with A.Lewenstam), Studia Filozoficzne,
Dec. 1989, p.173--179.

* Artificial Intelligence, Common Sense, and Philosophy (with
M.Bielecki), Studia Filozoficzne, Dec. 1989, p.11--24.

Autonomous control that reasons about its own actions, in: Kanade T.,
Groen F., and Hertzberger L. eds. Intelligent Autonomous Systems 2,
Amsterdam, The Netherlands, Dec. 1989, p.864--874.

AI insider's view on real-time systems, Proc.Fifth Annual
Conference on Artificial Intelligence and Ada, Nov. 1989.

Fusion of vision and touch for spatio-temporal reasoning in learning
manipulation tasks (with Pachowicz P.) in: Proceedings of SPIE's
Advances in Intelligent Robotic Systems, November 1989, p.404--415.

Multisearch Systems with Hierarchical Control: a Tool for Solving
Complex AI Problems (with Jankowski A.), in: Bourbakis N. ed.
Proc. of IEEE Workshop on Tools for Artificial Intelligence,
1989, p.132--137.

A Multisearch Approach to Sequence Prediction, (with
Stefanski, P.), in: Ras Z. ed. Methodologies for Intelligent
Systems 4, Elsevier, New York, NY 1989, p.359--366.

Hierarchical Control and Heuristics in Multisearch Systems,
(with Jankowski A.), in: Ras Z. ed. Methodologies for
Intelligent Systems 4, Elsevier, New York, NY 1989, p.86--93.

Testing ECHO on historical data, Behavioral and Brain Sciences,
September 1989, p.489--490.

Overcoming FAHRENHEIT's experimentation habit: discovery system
tackles a database assignment, in Piatetsky-Shapiro, G. and
Frawley, W. eds. IJCAI Workshop on Knowledge Discovery in
Databases, August 1989, p.398--406.

Reasoning about own plans, goals and actions for an aircraft
(with Swangwanna, S), in Shalin, V. and Boy, G. eds.
Proceedings of IJCAI Workshop on Integrated Human-Machine
Intelligence in Aerospace Systems, August 1989, p.31--40.

Data-driven Approaches to Empirical Discovery (with Pat Langley),
Artificial Intelligence, Vol.40, 1989, p.283--312.

Model Based Science of Ion-Selective Electrodes --- Methodological
Remarks (with Lewenstam, A), in: Pungor, E. ed. Ion-Selective
electrodes, 5; Pergamon Press, Oxford 1989, p.297--304.

Real-time Decision Making for Autonomous Flight Control (with
Sulyuth Swangwanna), Proceedings of SAE General Aviation Meeting,
April, 1989. 7p.

Improving the Tactical Decisions by an Automated Pilot; Search
Mechanism Guided by Experience and Prediction, in: Proceedings
of Techfest XV, Wichita, KS, Nov. 10--12, 1988, 12p.

Data-driven Approaches to Empirical Discovery (with Pat Langley),
Technical Report 88-24, University of California, Irvine,
1988, 28p.

A Methodology for Multisearch Systems (with Andrzej Jankowski),
in: Ras Z. and Saitta L. eds. Methodologies for Intelligent
Systems 3, North-Holland, New York, NY, 1988, p.343--352.

Utilizing Experience for Improving the Tactical Manager (with
Michael Erickson), in: John Laird ed. Proceedings of the Fifth
International Conference on Machine Learning, Ann Arbor, Michigan,
June 1988, Morgan Kaufmann Publ., p.444--450.

Normative Systems of Discovery and Logic of Search (with H.A.Simon),
Synthese, Vol.74, January 1988, p.65--90.

* Computer System of Discovery STAHL (with P.Langley and H.A.Simon),
Zagadnienia Naukoznawstwa, Vol.23, 3--4, 1987, p.518--536.

Tactical Manager in a Simulated Environment (with Michael Erickson),
in: Ras Z. and Zemankova M. eds. Methodologies for Intelligent
Systems, Elsevier Science Publ., 1987, p.139--147.

Combining many searches in the FAHRENHEIT discovery system,
Proceedings of Fourth International Workshop on Machine Learning,
June 22--25, 1987, Morgan Kaufmann Publ., Los Altos, California,
p.281--287.

Is Analytical Chemistry an Autonomous Field of Science? (with
A.Lewenstam), Fresenius Journal for Analytical Chemistry, Vol.326,
1987, p.308--311.

* Operationalism, in: Philosophy and Science, Encyclopedia,
Ossolineum, 1987, p.451--455.

Experimenting and Theorizing in Theory Formation (with Bruce Koehn),
in: Ras Z. and Zemankova M. eds. Proceedings of the International
Symposium on Methodologies for Intelligent Systems, Knoxville, TN,
Oct. 1986, ACM SIGART Press, p.296--307.

Numerical and Symbolic Computing in the Applications of Law-like
Knowledge (with A.Zytkow), in: Coupling Symbolic and Numerical
Computing in Expert Systems, J.S.Kowalik ed. North-Holland,
Amsterdam, The Netherlands, 1986, p.147--159.

A Theory of Historical Discovery: The Construction of Componential
Models (with H.A.Simon), Machine Learning, Vol.1,
March 1986, p.107--137.

What revisions does bootstrap testing need, Philosophy of Science,
Vol. 53, March 1986, p.101--109.

The search for regularity: four aspects of scientific discovery
(with P.Langley, H.A.Simon, G.Bradshaw), in: R.Michalski,
J.Carbonell, and T.Mitchell eds. Machine Learning, Vol.2,
Palo Alto, California: Morgan Kaufmann Publ., 1986, p.425--469.

A Survey of Methods for Object Detection from Images (with X.Li),
Technical Report WSU-CS-85-2, CS Wichita State University,
1985.

Discovering Qualitative Empirical Laws (with P.Langley, H.A.Simon,
D.H.Fisher), Technical Report 85-18, ICS University of California at
Irvine, 1985.

Numbers and Symbols in the Laws of Science, Proceedings of the
Coupling Symbolic and Numerical Computing in Expert Systems, Bellevue,
Washington, August p.27--29, 1985.

INGA --- Intelligent Network Generator (with Z.Czajkiewicz),
Proceedings of the IASTED International Symposium: Robotics
and Automation, Lugano, June 24--26, 1985, Acta Press, p.244--247.

A model of early chemical reasoning (with P.Langley, H.A.Simon)
Proceedings of the Sixth Annual Conference of the Cognitive
Science Society, Boulder, Colorado, June 1984, p.378--381

* Relations between genetically connected theories, in:
Zakonomiernosti razwitija estestvoznanija,
Kupcow W., Majewski Z. eds. Moscow,
1984, IN RUSSIAN.

Partial definitions in science compared to meaning families in natural
language, in: Sign, System, and Function, Sebeok T. et al. eds.
The Hague-Paris, Mouton, 1984, p.479--492.

Three facets of scientific discovery (with P.Langley, H.A.Simon,
G.Bradshaw), Proceedings of the IJCAI-1983.

Mechanisms for qualitative and quantitative discovery (with P.Langley,
H.A.Simon, G.Bradshaw), in: Proceedings of the International
Machine Learning Workshop, Michalski R.S. ed. Univ.of Illinois at
Urbana-Champaign 1983, p.121--132.

* Was the Oxygen Theory of Lavoisier better than the Theory of Phlogiston?
A contribution to the analysis of the scientific revolution (with
A.Lewenstam), Studia Filozoficzne No 9--10, 1982, p.39--65.

Difficulties with the reduction of classical to relativistic mechanics
(with M.Czarnocka), in: Polish Essays in the Philosophy of
the Natural Sciences, Krajewski W. ed. Boston Studies in the
Philosophy of Science, Vol.68, Reidel 1982, p.319--332.

An interpretation of a concept in science by a set of operational
procedures, in: Polish Essays in the Philosophy of the Natural
Sciences, Krajewski W. ed. Boston Studies in the Philosophy of
Science, Vol.68, Reidel 1982, p.169--185.

* Polish political system decay under martial law,
Underground Bulletin, 1982. (pseudonym Jacek Kaleta).

* Deductive theory in science and its relation to reality,
Czlowiek i Swiatopoglad No 9, 1980, p.85--105.

* Orbituary Notice: Tadeusz Nadel-Turonski (with W.Krajewski and
T. Nowaczyk Ruch Filozoficzny, Vol.38, 1980, p.203-6.

* A coherent set of operational procedures as the interpretation of an
empirical term, in two parts: Studia Filozoficzne
No 6, 1979, p.95--112,
and Studia Filozoficzne No 7, 1979, p.25--38.

* Determinism, indeterminism, free will, in: Technologia nauki,
Matuszewski R. ed. Plock 1979, p.43--50.

* On the reduction of the classical mechanics to the relativistic one
(with M.Czarnocka), Studia Filozoficzne No 8--9, 1978, p.185--196.

* On intersubjective communicability and verification of knowledge,
in: Technologia nauki --- specyfika wiedzy naukowej, Matuszewski R.
ed. Plock 1978, p.74--78.

* On the translability of languages of theories divided by a scientific
revolution (with A.Lewenstam), in: Relacje miedzy teoriami a rozwoj
nauki, Krajewski W. et al. eds. Wroclaw--Warszawa 1978, p.81--100.

* Models of atom --- remarks on the growth of knowledge (with
A.Lewenstam), in: Relacje miedzy teoriami a rozwoj nauki, Krajewski W. et al.
eds. Wroclaw--Warszawa 1978, p.27--45.

* On the concept of relative truth in empirical sciences, Studia
Filozoficzne No 6, 1977, p.33--37.

* On cumulative and revolutionary schemes of scientific growth,
Czlowiek i Swiatopoglad No 1, 1977, p.91--106.

* Entanglement of terms in a theory. The question of the vicious circle,
in: Technologia nauki --- redukcjonizm, Matuszewski R. ed. Plock
1976, p.72--76.

Intertheory relations on the formal and semantical level, in:
Formal Methods in the Methodology of Empirical Sciences, Przelecki M. et al.
eds. Wroclaw--Warszawa 1976, p.450--457.

* Remarks on microreduction, Czlowiek i Swiatopoglad No 12,
1974, p.74--88.

* The structure of theory in physics; on reduction and correspondence
relations, in: Zasada korespondencji w fizyce a rozwoj nauki,
Krajewski W. et al. eds. Warszawa 1974, p.233--279.

* The concept of model in formal and in empirical sciences, Studia
Filozoficzne No 7--8, 1972, p.87--96.

* On the visuality of knowledge in science, Czlowiek i Swiatopoglad
No 10, 1971, p.87--100.

BOOK: Scientific Discovery; Computational Explorations of the
Creative Processes (with P.Langley, H.A.Simon, and
G.L.Bradshaw), 1987, MIT Press, 357 pages.

CO-EDITOR (with Krajewski W. and Pietruska-Madej E.) OF A MONOGRAPH:
Intertheory Relations and the Growth of Science (in Polish),
Wroclaw--Warszawa 1978.

CO-EDITOR (with Diaz-Herrera J.) of Conference Proceedings:
Proceedings of the Fourth Artificial Intelligence and Ada Conference,
George Mason University, Fairfax, VA. Nov.1989.

EDITOR of Conference Proceedings: Proceedings of the ML-92 Workshop
on Machine Discovery (MD-92), Aberdeen, U.K., July 1992.

EDITOR of the special issue on machine discovery of Machine Learning
journal, August 1993.

EDITOR of the special issue on automated discovery of Foundations of
Science journal, 1995.

EDITOR of the book (collection of papers) Machine Discovery, Kluwer,
1997.

Co-EDITOR (with J. Komorowski) Principles of Data Mining and
Knowledge Discovery, Springer-Verlag, 1997.

Co-EDITOR (with Willi Kloesgen) Handbook of Data Mining and Knowledge
Discovery; Oxford University Press, 1997-9.

Learnable Evolutionary computation

2007-09-15T14:45:00.000-07:00

The estimation of distribution algorithms (EDA) and the Learnable Evolution Model (LEM) methods are both good examples of combining machine learning and population based evolutionary search.. The basic point is to by extracting the high-level models of the variable relationships, we could make better decision when generating the new exploration individuals.

How could we apply this ideas to Genetic Programming? Sastry Kumar did a try but that kind of fixed full-tree model is of limited value. A better method is needed.

PCA and exploratory analysis for linkage learning in Genetic algorithm

2007-09-15T14:43:00.000-07:00

I just came up with the idea of applying Principle component analysis (PCA) and other feature selection (correlation) analysis tools in data mining to the linkage detection in genetic algorithms based optimization.

During the evolutionary process, we can calculate the correlation( mutual information) of the features with respect to the fitness values, which can be used to guide the new individual generation process.

George Hu

Learnable Evolution Model Non-Darwinian Evolutionary Computation

2007-09-15T14:40:00.001-07:00

Learnable Evolution Model
A Non-Darwinian Evolutionary Computation
Guided by Machine Learning

(Michalski, Wojtusiak, Kaufman)

The Learnable Evolution Model (LEM) is a novel, non-Darwinian methodology for evolutionary computation that employs machine learning to guide the generation of new individuals (candidate problem solutions). Unlike standard, Darwinian-type evolutionary computation methods that use random or semi-random operators for generating new individuals (such as mutations and/or recombinations), LEM employs hypothesis generation and instantiation operators.

The hypothesis generation operator applies a machine learning program to induce descriptions that distinguish between high-fitness and low-fitness individuals in each consecutive population. Such descriptions delineate areas in the search space that most likely contain the desirable solutions. Subsequently the instantiation operator samples these areas to create new individuals.

Figure 1 presents a diagram of LEM3, the newest implementation of Learnable Evolution Model. LEM3 can be viewed as a multistrategy evolutionary program because in addition to creating new individuals through hypothesis generation and instantiation operators (red module in the diagram), it can also create them through probing operators (implementing some forms of mutations and recombinations) and randomization operators (that generate random individuals). In the future, we plan to implement also local search operators.

Figure 1: LEM3 flowchart.

Figure 2: Learn & Instantiate action flowchart.

In our experimental studies concerning complex function optimization (with the number of variables ranging between 10 and 1000), LEM3 significantly outperformed other evolutionary computation methods, sometimes by two or more orders of magnitude in terms of the evolution length (defined as the number of fitness evaluations needed to reach a desired solution).

The LEM methodology was also used to implement specialized systems, ISHED and ISCOD, for optimizing designs of heat exchangers. This work has been done in collaboration with the National Institute for Standards and Technology (see Learnable Evolution Model in Engineering Design).

LEM has the potential for application to a wide range of problems, in particular, to domains in which fitness function evaluation is costly or time-consuming, such as engineering design, economics, drug design, evolvable hardware, software engineering and optimization, and data mining.

Selected References:
Wojtusiak, J. and Michalski R.S., "The LEM3 System for Non-Darwinian Evolutionary Computation: A Method Description and Application to Very Complex Function Optimization Problems," to be submitted to: Evolutionary Computation.

Michalski, R. S., "Optimizing Complex Systems by Intelligent Evolution:The LEMd Method and Case Study," Bulletin of the Polish Academy of Sciences, November 2006.

Michalski, R. S., Wojtusiak, J. and Kaufman, K., "Intelligent Optimization via Learnable Evolution Model," Proceedings of The 18th IEEE International Conference on Tools with Artificial Intelligence, Washington D.C., November 13-15, 2006.

Michalski, R.S. and Kaufman, K., "INTELLIGENT EVOLUTIONARY DESIGN: A New Approach to Optimizing Complex Engineering Systems and its Application to Designing Heat Exchangers," International Journal of Intelligent Systems, Volume 21, Issue 12, 2006.

Michalski, R. S., Wojtusiak, J. and Kaufman, K., "Progress Report on the Learnable Evolution Model," Reports of the Machine Learning and Inference Laboratory, MLI 06-5, George Mason University, Fairfax, VA, 2006.

Wojtusiak, J. and Michalski, R.S., "The LEM3 Implementation of Learnable Evolution Model and Its Testing on Complex Function Optimization Problems," Proceedings of Genetic and Evolutionary Computation Conference, GECCO 2006, Seattle, WA, July 8-12, 2006.

Wojtusiak, J., "Initial Study on Handling Constrained Optimization Problems in Learnable Evolution Model," Proceedings of The Graduate Student Workshop at Genetic and Evolutionary Computation Conference, GECCO 2006, Seattle, WA, July 8-12, 2006.

Wojtusiak, J. and Michalski, R.S., "The LEM3 System for Non-Darwinian Evolutionary Computation and Its Application to Complex Function Optimization," Reports of the Machine Learning and Inference Laboratory, MLI 05-2, George Mason University, Fairfax, VA, October, 2005.

Domanski, P.A., Yashar, D., Kaufman K. and Michalski R.S., "An Optimized Design of Finned-Tube Evaporators Using the Learnable Evolution Model," Reports of the Machine Learning and Inference Laboratory, MLI 04-1, George Mason University, Fairfax, VA, February, 2004.

Kaufman K. and Michalski R.S., "Applying Learnable Evolution Model to Heat Exchanger Design," Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000) and Twelfth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-2000), Austin, TX, pp. 1014-1019, 2000.

Kaufman K., Cervone G. and Michalski R.S., "Experimental Validations of the Learnable Evolution Model," 2000 Congress on Evolutionary Computation, San Diego CA, pp 1064-1071, July 2000.

Michalski R.S., "LEARNABLE EVOLUTION MODEL Evolutionary Processes Guided by Machine Learning," Machine Learning , 38, pp 9-40, 2000.

Michalski R.S. and Zhang, Q., "Initial Experiments with the LEM1 Learnable Evolution Model: An Application to Function Optimization and Evolvable Hardware," Reports of the Machine Learning and Inference Laboratory, MLI 99-4, George Mason University, Fairfax, VA, ay 1999.

Michalski, R.S., " Learnable Evolution: Combining Symbolic and Evolutionary Learning," Proceedings of the Fourth International Workshop on Multistrategy Learning (MSL'98), Desenzano del Garda, Italy, pp. 14-20, June 11-13, 1998.
For more references, see Publication section.

google adsense by Genetic algorithm?

2007-09-15T14:36:00.001-07:00

Google Targeting Ads Based on Previous Queries

Reuters reports from a briefing for journalists at the Googleplex, where Google’s Susan Wojcicki (pictured) talked about how Google is a bit wary to use behavioral targeting... that is, to deliver ads based on a deep user profile aggregated over time (and potentially, through different services). Instead, Google prefers targeting ads to the “task” at hand – the current search query. But Google is now also playing with targeting ads based on immediately previously entered queries (the “search session”):

Google has been testing for several weeks a new advertising feature that delivers ads based not simply on a specific search term, but also on the immediately previous search, [Susan Wojcicki] said.

A user who types “Italy vacation” into a Google search box might see ads about Tuscany or cheap flights to Europe. Were the same user to subsequently search for “weather,” Google will assume there is a link between “Italy vacation” and “weather” and deliver ads tied to local weather conditions in Italy.

Google is “very careful” about traditional behavioral targeting, though. According to Susan, “Nothing is stored, nothing is remembered. It all happens within that session.” (Not sure about the “nothing is stored” bit when you enabled web history...)

Interestingly enough, some of the problems Google points out in relation to behavioral targeting of ads also apply to personalization of search results (something which Google emphasized they believe in):

Wojcicki highlighted the problem of a user searching “video games.” Advertisers might be wrong to assume the searcher was a gamer and not, say, a grandmother, looking for a gift for her grandson, she noted.

This is a good example of why personalization, at least in the form of “user looks at A a lot, A is related to B, let’s show more of B”, can be counter-productive. Then again, some of us recently wondered if Google perhaps partially employs a different personalization strategy: “user looks at A a lot, C is unrelated to A, let’s show more of C as that’s not what the user likely knows anyway.”

I wonder, with that massive amount of ads + searches Google has, if there’s some merit in allowing the software to figure it out for itself... evolutionary algorithms, self-learning style. Search sessions are automatically grouped into general patterns, and then random ads are presented, and when an ad performs well, more ads from that ad segment will be displayed next time, and so on, causing a “survival of the fittest ad” environment. Then when Google meets the press in 2012, they can tell the journalists, “We don’t have a clue anymore how our ads work, but click-throughs are higher than ever.”

[Via Barry Schwartz.]

EDA Intelligent evolutionary design: A new approach to optimizing complex engineering systems and its application to designing heat exchangers

2007-09-15T14:28:00.000-07:00

Learnable Evolution Model is essentially EDA (estimation of distribution algorithm)

Research Article

Intelligent evolutionary design: A new approach to optimizing complex engineering systems and its application to designing heat exchangers

Ryszard S. Michalski^{1 2 *}, Kenneth A. Kaufman^{1 *}

¹Machine Learning and Inference Laboratory, George Mason University, Fairfax, VA 22030, USA
²Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland

email: Ryszard S. Michalski (michalski@mli.gmu.edu) Kenneth A. Kaufman (ken.kaufman@gmail.com)

^*Correspondence to Ryszard S. Michalski, Machine Learning and Inference Laboratory, George Mason University, Fairfax, VA 22030, USA

^*Correspondence to Kenneth A. Kaufman, Machine Learning and Inference Laboratory, George Mason University, Fairfax, VA 22030, USA

Funded by:
National Science Foundation; Grant Number: IIS-0097476, IIS-9906858
UMBC/LUCITE; Grant Number: #32

Abstract

A new method for optimizing complex engineering designs is presented that is based on the Learnable Evolution Model (LEM), a recently developed form of non-Darwinian evolutionary computation. Unlike conventional Darwinian-type methods that execute an unguided evolutionary process, the proposed method, called LEMd, guides the evolutionary design process using a combination of two methods, one involving computational intelligence and the other involving encoded expert knowledge. Specifically, LEMd integrates two modes of operation, Learning Mode and Probing Mode. Learning Mode applies a machine learning program to create new designs through hypothesis generation and instantiation, whereas Probing Mode creates them by applying expert-suggested design modification operators tailored to the specific design problem. The LEMd method has been used to implement two initial systems, ISHED1 and ISCOD1, specialized for the optimization of evaporators and condensers in cooling systems, respectively. The designs produced by these systems matched or exceeded in performance the best designs developed by human experts. These promising results and the generality of the presented method suggest that LEMd offers a powerful new tool for optimizing complex engineering systems. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 1217-1248, 2006.

Digital Object Identifier (DOI)

10.1002/int.20182 About DOI

1997 Recent Work in Computational Scientific Discovery

2007-09-15T14:19:00.002-07:00

In Proceedings of the Nineteenth Annual Conference of the Cognitive Science Society. Michael Shafto and Pat Langley (Eds.). Mahwah, New Jersey: Lawrence Erlbaum, 1997, pp. 161-166.

Recent Work in Computational Scientific Discovery

Lindley Darden (darden at umd.edu)
Committee on the History and Philosophy of Science, Department of Philosophy
University of Maryland, College Park, MD 20742 USA

Abstract

This paper reviews work in computational scientific discovery. After a brief discussion of its history, the focus will be on work since 1990. The second half of the paper discusses the author's use of three methods for studying reasoning strategies in scientific change: historical-philosophical vs. live-in-the-lab vs. computational, pointing out advantages and disadvantages of the computational method.

Introduction

There are a number of approaches to the study of reasoning in scientific discovery. In addition to computational approaches, work continues in cognitive science (e.g., Schunn & Dunbar, 1996), in laboratory studies (e.g., Darden & Cook, 1994; Dunbar, 1995) and in philosophy of science (e.g., Bechtel & Richardson, 1993; Darden, 1991; Kleiner, 1993; Nersessian, 1992; Nickles, 1994; Schaffner, 1993; Spirtes, Glymour & Scheines, 1993). Unfortunately, of the over 200 papers and abstracts submitted for the Philosophy of Science Association meeting in 1996, none were on the topic of reasoning in scientific discovery (Darden, Ed., 1996; 1997). Most philosophers of science do not view discovery as a central topic in the field, despite continuing work by those of us called "friends of discovery" (Nickles, Ed. 1980). It is encouraging that the Cognitive Science Society is sponsoring this Symposium on Scientific Discovery.

This paper will briefly review the history of computational scientific discovery that uses methods from artificial intelligence. (Non-cognitive, non-AI computational work is outside the scope of this paper.) The first part of the paper will concentrate on the work since 1990 (Shrager & Langley, Eds.). The extensive reference list provides a guide for further reading. The second half of the paper will compare three methods used in my own work on reasoning strategies in scientific change. Finally, I will point out advantages and disadvantages of the computational approach from my perspective as a philosopher of science.

Pioneering Work

The study of computational scientific discovery emerged from the view that science is a problem solving activity, that heuristics for problem solving can be applied to the study of scientific discovery in either historical or contemporary cases, and that methods in artificial intelligence provide techniques for building computational systems. Pioneers in this work are Bruce Buchanan (e.g., 1982) and Herbert Simon (e.g., 1977). Buchanan was trained as a philosopher of science at a time when the profession was dominated by Popper's (1965) view that there is no logic of discovery. Buchanan stated the new research program:

"The traditional problem of finding an effective method for formulating true hypotheses that best explain phenomena has been transformed into finding heuristic methods that generate plausible explanations. The problem of giving rules for producing true scientific statements has been replaced by the problem of finding efficient heuristic rules for culling the reasonable candidates for an explanation from an appropriate set of possible candidates" [and finding methods for constructing the candidates] (Buchanan 1985, 110-111).

Discovery as heuristic search in a search space enabled AI methods to be applied to discovery tasks.

The first expert system, DENDRAL, was a scientific discovery system. It formed hypotheses about chemical compounds, given mass-spectrographic data (Lindsay, Buchanan, Feigenbaum, & Lederberg, 1980;1993). This was followed by Meta-DENDRAL, which discovered new rules in mass spectrographic analysis, so as to by-pass the problem of getting rules from experts (Buchanan & Feigenbaum, 1978). Although its original algorithm was a computational realization of Lederberg's systematic scan strategy (Lederberg, 1965), DENDRAL was built to carry out a contemporary, difficult scientific task rather than as a model of human cognition.

A more historical-cognitive approach was the aim of the work on BACON, which rediscovered various scientific laws by finding patterns in numerical data (Langley, Simon, Bradshaw & Zytkow, 1987). Simon's early work on finding patterns in sequences (Simon & Kotovsky, 1963) was extended in BACON to heuristic search for patterns in numerical data. The most creative of BACON's abilities was the decomposition of relational data to conjecture intrinsic properties in one or more of the objects engaging in the relations. This step went beyond curve-fitting and was based on the metaphysical assumption that an entity's relational properties are caused by its intrinsic properties. In addition to the data-driven tasks modeled in BACON, the group also investigated theory-driven discovery in STAHL. One wonders to what extent these programs model actual cognitive processes of historical scientists, as opposed to finding strategies which are sufficient to reproduce the historical results. As with most simulations, they provide "how possibly" accounts. Using studies of notebook evidence, the KEKADA system (Kulkari & Simon, 1988) modeled reasoning patterns in some discoveries of the biochemist Hans Krebs and focused on responses to surprising experimental results, helping to dispel the mystery of serendipity in discovery.

A seminal conference on computational methods for scientific discovery, whose proceedings were published in 1990 (Shrager & Langley, Eds.) is a useful source for the state to the field at that time.

Recent Work

Some of the pioneers in scientific discovery, e.g., Buchanan, Simon, and Zytkow, push ahead with their research programs. Others who contributed to the 1990 volume are still working on discovery. The American Association for Artificial Intelligence sponsored a Spring Symposium on Systematic Methods of Scientific Discovery in March, 1995. A special issue of Artificial Intelligenceon computational discovery is about to appear, although fewer papers were received than the editors wished (Simon, Valdes-Perez & Sleeman, forthcoming). Data-mining in scientific databases is an active area of research, as are other computational approaches applied to individual sciences, e.g., intelligent systems in molecular biology. It is becoming more difficult to locate computational discovery work because much of it is published in scientific journals--a good sign that the methods of producing results of interest to practicing scientists.

Buchanan (e.g., Lee et al., 1996) continues work on rule induction applied to various scientific databases. Simon is studying the difficult problems of constructing diagrammatic representations (Larkin & Simon, 1987; Qin & Simon, 1995) and of modeling relations between diagrammatic and verbal reasoning (Tabachneck-Schijf, Leonardo, & Simon, 1996). Zytkow continues to work on various aspects of discovery, including analyzing the components needed for an autonomous discovery agent (e.g., Zytkow, 1995/96) and knowledge discovery in databases (e.g., Zytkow & Zembowicz, 1996).

Much of the current work in computational discovery is occurring within applications to particular sciences. According to Peter Karp, the whole field of bioinformatics is doing computational scientific discovery but there is a gradient from computational discoveries that are not based on AI methods, to computational discoveries that are based on AI methods, to methods with a "cognitive flavor." Not much of the bioinformatics work falls into the last category. However, Karp (et al., 1996) applied reasoning by analogy to predict metabolic pathways in the bacterium, H. influenzae,based on the extensive knowledge base that he and Monica Riley, a bacterial geneticist, have developed for E. coli.

Larry Hunter, a frequent editor of publications in AI and molecular biology (e.g., Hunter 1993), recently informed me that there is a clear success is the application of AI technology to molecular biology: hidden Markov models (HMMs) for molecular sequence analysis. They are being applied to automatically build models of families of nucleotide and amino acid sequences. These models are useful as extremely sensitive classifiers of novel sequences, and also generate multiple sequence alignments of large numbers of sequences in a computationally efficient way. Tools based on this approach are now in wide use in the biological community. A review article is Eddy (1996). Also, AI-based qualitative reasoning technologies have produced several good applications in reasoning about metabolism. Perhaps somewhat surprising is that the work in intelligent systems in molecular biology, for the most part, does not employ discovery methods discussed at the Shrager and Langley (Eds. 1990) conference.

The extensive protein sequence database has provided a challenge for those seeking to find computational methods to predict how the linear amino acids will fold into the secondary and tertiary structures in proteins. The Human Genome Project, which is rapidly producing millions of bases of sequence information about both human and model organism genomes, presents a challenge for computational approaches. Good programs are needed for discovering genes, both coding regions and regulatory regions, in these linear sequences. Current programs are not good at finding introns, intervening sequences between the coding regions of genes. Since the genetic system has some means of detecting introns, one can expect computational systems to be able to discover the signal(s). Knowledge discovery in scientific databases (e.g., Fayyad, Haussler & Stolorz, 1996) promises to be an important area in coming years.

Raul Valdes-Perez's (1994) work in chemistry shows the power of computational systems in doing a systematic search of a hypothesis space, given certain constraints. MECHEM is able to find reaction pathways that chemists have missed.

Buchanan's work on rule discovery in scientific databases and Valdes-Perez's work on systematically conjecturing chemical reaction pathways illustrate the power of design AI systems that aim, not at realistically modeling human cognitive capacities, but using computational methods to circumvent human limitations. Humans are not good at searching massive databases and manipulating sets of rules with many features to make predictions. Cognitive science research has shown that humans have a tendency to focus too rapidly on one hypothesis before doing a systematic search of a hypothesis space. Discovery programs that are more systematic and more thorough than humans are an aid to scientists.

Computational Discovery: Pros and Cons

My own work on reasoning in scientific change focuses on an cyclic process: discovery, assessment, revision. Given a good revision procedure, one's discovery methods can be weaker. Strategies for these processes include: strategies for producing new ideas, e.g., analogies, abstraction instantiation, interfield relations; strategies for theory assessment, e.g., prediction-testing, relations to theories in other fields; and strategies for anomaly resolution (Darden 1991, Ch. 15). After extensive historical study of the development of Mendelian genetics, I proposed hypothetical strategies of the three types. The historical evidence was inadequate to show that they are descriptive cognitive strategies actually used by geneticists. Instead, they are hypothetical strategies that couldhave been used in the historical development of the theory of the gene to produce the changes that didoccur (Darden, 1991). One needs to show that these strategies are effectiveproblem-solving strategies, instances of useful "compiled hindsight" (Darden, 1987), applicable to additional cases, worthy of being used by contemporary scientists or to build AI discovery systems.

I visited in Joshua Lederberg's Laboratory for Molecular Genetics and Informatics and participated in episodes of anomaly resolution that exemplified some of the revision strategies I had proposed (Darden & Cook 1994). One difficulty with the live-in-the lab approach is that little may happen while you are there; fortunately, I was able to observe some anomaly resolution strategies in use. Although I have attempted to implement some of the strategies in AI programs in order to demonstrate their efficacy (e.g., Darden & Rada, 1988; Kettler & Darden 1993; Darden, 1997), I have returned to historical-philosophical work, testing whether strategies from the Mendelian case apply to molecular biology (Darden, 1995).

Computational discovery work has advantages and disadvantages. Finding an adequate knowledge representation for a scientific case is difficult. Early work attempted to represent the relations between genes and chromosomes in part-whole hierarchies and to implement reasoning via inheritance and upward propagation of properties (Darden & Rada, 1988). A much more fruitful method for knowledge representation in genetics was the functional representation (Josephsons, Eds., 1994) for genetic processes (Darden 1997). Furthermore, when one is designing a computational system to rediscover a historical hypothesis, one must navigate between designing a system that trivially reproduces exactly what one is seeking versus designing a system that is unable to accomplish the task at all. Analogy systems often suffer these problems: either the analog is represented in such a way that the system easily finds it or there are so many analogs that the task becomes impossible (for attempts to navigate between these problems, see Kettler & Darden, 1993; Holyoak & Thagard, 1995).

An advantage of computational methods is the precision and completeness that is required to build a working system. The philosopher-historian may neglect aspects that the programmer must specify in detail if the system is to run. A computational approach forces one to reexamine aspects that may be otherwise neglected. However, this advantage is purchased at the price of much time and effort to implement even small parts of a historical case. Various aspects of human discovery, such as the use of pictorial models (e.g., the beads on a string model for genes on chromosomes), provide substantial difficulties when designing an implementation. On the plus side, once one has invested the effort in building a running system, then there is the fun of running experiments, doing "what-if" analyses, testing alternative strategies.

The approach in our TRANSGENE system (Darden, Moberg, Thadani & Josephson, 1992; Darden, 1997) was also used by Karp (1990) in his GENSIM and HYPGEN systems and points to a fruitful way to design a computational discovery system. A qualitative simulator of biological (or other) processes is built and used to make predictions. Data is supplied to test the predictions and another component of the system compares the prediction with data, detects anomalies, and uses diagnosis/redesign strategies to localize the fault in the simulator and redesign a module to remove the anomaly. Perhaps this architecture may be of use in building future AI systems or perhaps more traditional simulation models might be coupled with a revision system to do diagnosis/redesign for anomaly resolution and model improvement.

It will be exciting to see what computational scientific discovery produces in the coming years.

Acknowledgments

The TRANSGENE work was supported by the General Research Board of the University of Maryland and the National Science Foundation Grant No. RII-9003142. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect those of the National Science Foundation. The TRANSGENE system was designed in collaboration with John and Susan Josephson and Dale Moberg; TR.3 was implemented by Sunil Thadani. This paper was written while I enjoyed the hospitality of the Center for Philosophy of Science at the University of Pittsburgh. Very helpful were discussions with, and reprints received from, Bruce Buchanan and Herb Simon. Rapid email responses from Larry Hunter, Peter Karp, and Pat Langley were appreciated. Sets of reprints from Kevin Dunbar, Nancy Nersessian, Tom Nickles, and Jan Zytkow aided me in learning about their recent work. I enjoyed the demo of MECHEM by Raul Valdes-Perez and I profited from his web page:

www.cs.cmu.edu/~sci-disc

References

Alberdi, E. & Sleeman, D. (1997, forthcoming). "ReTAX: A Step in The Automation of Taxonomic Revision," Artificial Intelligence91(2).

Baker, L. M. & Dunbar, K. (1996). "Constraints on the Experimental Design Process in Real-World Science," in G.W. Cottrell (Ed.), Proceedings of the Eighteenth Annual Conference of the Cognitive Science Society,pp. 154-159. Mahwah, NJ: Lawrence Erlbaum Associates.

Bechtel, W. & Richardson, R.C. (1993). Discovering Complexity: Decomposition and Localization as Strategies in Scientific Research. Princeton, N. J.: Princeton University.

Buchanan, B.G. (1982). "Mechanizing the Search for Explanatory Hypotheses," in P. Asquith & T. Nickles (Eds.), PSA 1982V. 2, pp. 129-146. Philosophy of Science Association, East Lansing, Michigan.

Buchanan, B.G. (1985). "Steps Toward Mechanizing Discovery," in K. Schaffner (Ed.), Logic of Discovery and Diagnosis in Medicine. Berkeley: University of California Press.

Buchanan, B.G. (1994). "The Role of Experimentation in Artificial Intelligence," Phil. Trans. R. Soc. Lond.A 349:153-166.

Buchanan, B.G. & Feigenbaum, E. A. (1978). "DENDRAL and Meta-DENDRAL: Their Applications Dimension," Artificial Intelligence11:5-24.

Cohen, D, M., Kulikowski, C., & Berman, H. (1995). "DEXTER: A System that Experiments with Choices of Training Data Using Expert Knowledge in the Domain of DNA Hydration," Machine Learning21:81-101.

Corruble, V. &. Ganascia, J.-G (1997, forthcoming). "Induction and The Discovery of the Causes of Scurvy: A Computational Reconstruction," Artificial Intelligence91(2).

Dama, M. & Dunbar, K. (1996). "Distributed Reasoning: An Analysis of Where Social and Cognitive Worlds Fuse," in G. W. Cottrell (Ed.), Proceedings of the Eighteenth Annual Conference of the Cognitive Science Society, pp. 166-170. Mahwah, NJ: Lawrence Erlbaum Associates.

Darden, L. (1976). "Reasoning in Scientific Change: Charles Darwin, Hugo de Vries, and the Discovery of Segregation," Studies in History and Philosophy of Science7:127-169.

Darden, L. (1980). "Theory Construction in Genetics," in T. Nickles (Ed.), Scientific Discovery: Case Studies. Dordrecht: Reidel.

Darden, L. (1982). "Artificial Intelligence and Philosophy of Science: Reasoning by Analogy in Theory Construction," in T. Nickles & P. Asquith (Eds.), PSA 1982, V. 2, pp. 147-165. East Lansing, Michigan: Philosophy of Science Association.

Darden, L. (1985). "Hugo de Vries's Lecture Plates and the Discovery of Segregation," Annals of Science42:233-242.

Darden, L. (1987). "Viewing the History of Science as Compiled Hindsight," AI Magazine8(2):33-41.

Darden, L. (1990). "Diagnosing and Fixing Faults in Theories," in J. Shrager & P. Langley (Eds.), Computational Models of Scientific Discovery and Theory Formation. San Mateo, California: Morgan Kaufmann.

Darden, L. (1991). Theory Change in Science: Strategies from Mendelian Genetics. New York: Oxford University Press.

Darden, L. (1992). "Strategies for Anomaly Resolution," in R. Giere (Ed.), Cognitive Models of Science. Minneapolis: University of Minnesota Press.

Darden, L. (1995). "Exemplars, Abstractions, and Anomalies: Representations and Theory Change in Mendelian and Molecular Genetics," in J. G. Lennox & G. Wolters (Eds.), Concepts, Theories, and Rationality in the Biological Sciences. Pittsburgh, PA: University of Pittsburgh Press.

Darden, L. (1997). "Anomaly-Driven Theory Redesign: Computational Philosophy of Science Experiments," in T. W. Bynum & J. Moor (Eds.), Digital Phoenix: How Computers are Changing Philosophy.Oxford: Blackwell.

Darden, L. (Ed.) (1996). PSA 1996, Proceedings of the 1996 Biennial Meeting of the Philosophy of Science Association, Part I: Contributed Papers, Philosophy of Science,Supplement to Volume 63, September 1996.

Darden, L. (Ed.) (1997). PSA 1996, Proceedings of the 1996 Biennial Meeting of the Philosophy of Science Association, Part II: Symposium Papers, Philosophy of Science,Supplement to Volume 64, forthcoming September 1997.

Darden, L. & Rada, R. (1988). "Hypothesis Formation Using Part-Whole Interrelations," in David Helman (Ed.), Analogical Reasoning.Dordrecht: Reidel.

Darden, L. & Rada, R. (1988). "Hypothesis Formation Via Interrelations," in Armand Prieditis (Ed.), Analogica.Los Altos, California: Morgan Kaufmann.

Darden, L., Moberg, D., Nagarajan, S. & Josephson, J. (1991). Anomaly Driven Redesign of a Scientific Theory: The TRANSGENE.2 Experiments (Tech. Rep. 91-LD-TRANSGENE). Columbus, OH: Laboratory for Artificial Intelligence Research, Ohio State University.

Darden, L., Moberg, D., Thadani, S. & Josephson, J. (1992). A Computational Approach to Scientific Theory Revision: The TRANSGENE Experiments (Tech. Rep. 92-LD-TRANSGENE). Columbus, OH: Laboratory for Artificial Intelligence Research, Ohio State University.

Darden, L. & Cook, M. (1994). "Reasoning Strategies in Molecular Biology: Abstractions, Scans and Anomalies," in D. Hull, M. Forbes, & R. M. Burian (Eds.), PSA 1994,v. 2, pp. 179-191. East Lansing, Michigan: Philosophy of Science Association.

Dunbar, K. (1993). "Concept Discovery in a Scientific Domain," Cognitive Science17:397-434.

Dunbar, K. (1995). "How Scientists Really Reason: Scientific Reasoning in Real-World Laboratories," in R. J. Sternberg & J. E. Davidson (Eds.), The Nature of Insight.Cambridge, MA: MIT Press.

Dunbar, K. (1996). "Beyond the Myth of The Lone Scientist: Distributed Reasoning in Science and Scientific Discovery," Cognitive Studies: Bulletin of the Japanese Cognitive Science Society3:24-26.

Dunbar, K. (forthcoming). "How Scientists Think: On-line Creativity and Conceptual Change in Science," in T. B. Ward, S. M. Smith & J. Vaid (Eds.), Conceptual Structures and Processes: Emergence, Discovery and Change. Washington, D. C.: American Psychological Association Press.

Eddy, S. R. (1996). "Hidden Markov Models," ftp://genome.wustl.edu/pub/eddy/hmm-review.ps.Z

Fayyad, U., Djorgovski, S. G., & Weir, N. (1996). "From Digitized Images to Online Catalogs," AI Magazine17 (2): 51-66.

Fayyad, U., Haussler, D. & Stolorz, Z. (1996). "KDD for Science Data Analysis: Issues and Examples," In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96),pp. 50-56. Menlo Park, CA: AAAI Press.

Fayyad, U., Piatetsky-Shapiro, G., Smyth, P. (1996). "From Data Mining to Knowledge Discovery in Databases," AI Magazine17 (3): 37-54.

Griffith, T. W., Nersessian, N. & Goel, A. (1996). The Role of Generic Models in Conceptual Change (Tech. Rep. CIT-GOGSCI-96/02). Atlanta, GA: College of Computing, Georgia Institute of Technology.

Holyoak, K. J. and Thagard, P. (1995). Mental Leaps: Analogy in Creative Thought. Cambridge, Mass.: MIT Press.

Hunter, L. (Ed.) (1993). Artificial Intelligence and Molecular Biology. Cambridge, MA: MIT Press.

de Jong, H. & Rip, A. (1997, forthcoming). "The Computer Revolution in Science: Steps towards the Realization of Computer-Supported Discovery Environments," Artificial Intelligence91(2).

Josephson, J.R. & Josephson, S.G. (Eds.) (1994). Abductive Inference: Computation, Philosophy, Technology. New York: Cambridge University Press.

Karp, P. (1989). Hypothesis Formation and Qualitative Reasoning in Molecular Biology. Ph.D. Dissertation, Stanford University, Stanford, California.

Karp, P. (1990). "Hypothesis Formation as Design," in J. Shrager and P. Langley (Eds.), Computational Models of Scientific Discovery and Theory Formation. San Mateo, California: Morgan Kaufmann.

Karp, P. (1993). "A Qualitative Biochemistry and its Application to the Regulation of the Tryptophan Operon," in L. Hunter (Ed.), Artificial Intelligence and Molecular Biology. Cambridge, MA: AAAI Press and MIT Press.

Karp, P., Ouzouni, C. & Paley, S. M. (1996). "HinCyc: A Knowledge Base of the Complete Genome and Metabolic Pathways of H. influenzae," in D.J. States, P. Agarwal, T. Gaasterland, L. Hunter & R. Smith (Eds.), ISMB-96: Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology, pp. 116-124. Menlo Park, CA: AAAI Press.

Kettler, B. & Darden, L. (1993). "Protein Sequencing Experiment Planning Using Analogy," in L. Hunter, D. Searls, & J. Shavlik (Eds.), ISMB-93, Proceedings of the First International Conference on Intelligent Systems for Molecular Biology, pp. 216-224. Menlo Park, CA: AAAI Press.

Kleiner, S. A. (1993). The Logic of Discovery: A Theory of the Rationality of Scientific Research. Dordrecht: Kluwer.

Kulkarni, D. and Simon, H.A. (1988). "The Processes of Scientific Discovery: The Strategy of Experimentation," Cognitive Science12:139-175.

Langley, P., Simon, H.A., Bradshaw, G.L. & Zytkow, J.M. (1987). Scientific Discovery: Computational Explorations of the Creative Process. Cambridge, Massachusetts: MIT Press.

Larkin, J. H. & Simon, H. A. (1987). "Why a Diagram is (Sometimes) Worth Ten Thousand Words," Cognitive Science11:65-99.

Lederberg, J. (1965). "Signs of Life: Criterion-System of Exobiology," Nature207:9-13.

Lee, Y., Buchanan, B. G., Klopman, G., Dimayuga, M. & Rosenkranz, H. S. (1996). "The Potential of Organ Specific Toxicity for Predicting Rodent Carcinogenicity," Mutation Research358:37-62.

Lindsay, R. K., Buchanan, B. G., Feigenbaum, E. A. & Lederberg, J. (1980). Applications of Artificial Intelligence for Organic Chemistry: The DENDRAL Project. New York: McGraw Hill.

Lindsay, R. K., Buchanan, B. G., Feigenbaum, E. A. & Lederberg, J. (1993). "DENDRAL: A Case Study of the First Expert System for Scientific Hypothesis Formation," Artificial Intelligence61:209-261.

Nersessian, N. J. (1992). "How Do Scientists Think? Capturing the Dynamics of Conceptual Change in Science," in R. N. Giere (Ed.), Cognitive Models of Science. Minneapolis: University of Minnesota Press.

Nersessian, N. J. (1995). "Opening the Black Box: Cognitive Science and History of Science," OSIRIS10:194-211.

Nickles, T. (Ed.) (1980). Scientific Discovery, Logic and Rationality. Dordrecht: Reidel.

Nickles, T. (1994). "Enlightenment Versus Romantic Models of Creativity in Science--and Beyond," Creativity Research Journal7:277-314.

Popper, Karl (1965). The Logic of Scientific Discovery.New York: Harper Torchbooks.

Provost, F. J. & Buchanan, B. G. (1995). "Inductive Policy: The Pragmatics of Bias Selection," Machine Learning20:35-61.

Qin, Y. & Simon, H.A. (1995). "Imagery and Mental Models," in J. Glasgow, H. H. Narayanan, & B. Chandrasekaran (Eds.), Diagrammatic Reasoning: Computational and Cognitive Perspectives. Menlo Park, CA: AAAI/MIT Press.

Richman, H. B., Staszewski, J. J. & Simon, H. A. (1995). "Simulation of Expert Memory using EPAM IV," The Psychological Review102:305-330.

Schaffner, K. (1993). Discovery and Explanation in Biology and Medicine. Chicago: University of Chicago Press.

Schunn, C. D. & Dunbar, K. (1996). "Priming, Analogy, and Awareness in Complex Reasoning," Memory & Cognition24:271-284.

Shrager, J. & Langley, P. (Eds.) (1990). Computational Models of Scientific Discovery and Theory Formation. San Mateo, California: Morgan Kaufmann.

Simon, H.A. (1977). Models of Discovery.Dordrecht: Reidel.

Simon, H.A. and Kotovsky, K. (1963). "Human Acquisition of Concepts for Sequential Patterns," Psychological Review70:534-546.

Simon, H.A., Valdes-Perez, R.E. & Sleeman, D.H. (1997, forthcoming). Editorial: "Scientific Discovery and Simplicity of Method," Artificial Intelligence91(2).

Spirtes, P., Glymour, C. & Scheines, R. (1993). Causation, Prediction, and Search.New York: Springer Verlag.

Swanson, D.R. & Smalheiser, D.H. (1997, forthcoming). "An Interactive System for Finding Complementary Literatures: A Stimulus to Scientific Discovery," Artificial Intelligence91(2).

Tabachneck-Schijf, H. J. M., Leonardo, A. M., Simon, H.A. (1996). CaMeRa: A Computational Model of Multiple Presentations(Tech. Rep. CIP 530). Pittsburgh, PA: Carnegie Mellon University.

Valdes-Perez, R.E. (1992). "Algorithm to Generate Reaction Pathways for Computer-Assisted Elucidation," Journal of Computational Chemistry13:1079-1088.

Valdes-Perez, R.E. (1992). "A Necessary Condition for Catalysis in Reaction Pathways," Journal of Physical Chemistry96:2394-2396.

Valdes-Perez, R.E. (1993). "Algorithm to Test the Structural Plausibility of a Proposed Elementary Reaction," Journal of Computational Chemistry14:1454-1459.

Valdes-Perez, R.E. (1994). "Algorithm to Infer the Structures of Molecular Formulas within a Reaction Pathway," Journal of Computational Chemistry15:1266-1277.

Valdes-Perez, R.E. (1994). "Human/computer Interactive Elucidation of Reaction Mechanisms: Application to Catalyzed Hydrogenolysis of Ethane," Catalysis Letters28:79-87.

Valdes-Perez, R.E. (1994). "Heuristics for Systematic Elucidation of Reaction Pathways," Journal of Chemical Information and Computer Sciences34:976-983.

Valdes-Perez, R.E. (1994). "Conjecturing Hidden Entities via Simplicity and Conservation Laws: Machine Discovery in Chemistry," Artificial Intelligence65:247-280.

Valdes-Perez, R.E. (1995). "Generic Tasks of Scientific Discovery," in R. Valdes-Perez (Ed.) Working Notes: AAAI Spring Symposium Series: Symposium: Systematic Methods of Scientific Discovery.

Valdes-Perez, R.E. (1995). "Some Recent Human/Computer Discoveries in Science and What Accounts for Them," AI Magazine16(3):37-44.

Valdes-Perez, R.E. (1995). "Machine Discovery in Chemistry: New Results," Artificial Intelligence74:191-201.

Valdes-Perez, R.E. (1995). "Machine Discovery Praxis," Foundations of Science1:219-224.

Valdes-Perez, R.E. (1996). "A New Theorem in Particle Physics Enabled by Machine Discovery," Artificial Intelligence,82:331-339.

Valdes-Perez, R.E. (1996). "Computer Science Research on Scientific Discovery," Knowledge Engineering Review11:57-66.

Valdes-Perez, R.E. & Minden, J.S. (1995). "Drosophila Melanogaster Syncytial Nuclear Divisions are Patterned: Time-Lapse Images, Hypothesis, and Computational Evidence," Journal of Theoretical Biology175:525-532.

Valdes-Perez, R.E. & Zytkow, J.M. (1996). "Systematic Generation of Constituent Models of Particle Families," Physical ReviewE 54:2102-2110.

Zembowicz, R. & Zytkow, J.M. (1996). "From Contingency Tables to Various Forms of Knowledge in Databases," in U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, & R. Uthurusany (Eds.), Advances in Knowledge Discovery and Data Mining, Menlo Park, CA: AAAI Press.

Zytkow, J.M. (1993). "Introduction: Cognitive Autonomy in Machine Discovery," Machine Learning: Special Issue on Machine Discovery12:7-16.

Zytkow, J.M. (1995/96). "Creating a Discoverer: Autonomous Knowledge Seeking Agent," Foundations of Science2:253-283.

Zytkow, J.M. (1996). "Automated Discovery of Empirical Laws," Fundamenta Informaticae27:299-318.

Zytkow, J.M. (Ed.) (1996). Machine Discovery. Kluwer Academic Publishers: Dordrecht.

Zytkow, J.M. & Lewenstam, A. (1990). "Analytical Chemistry; The Science of Many Models," Fresenius Journal of Analytical Chemistry338:225-233.

Zytkow J.M., Zhu, J. & Hussam, A. (1990). "Automated Discovery in a Chemistry Laboratory," in Proceedings of the Eighth National Conference on Artificial Intelligence,pp. 889-894. Menlo Park, CA: AAAI Press.

Zytkow, J.M. & Zembowicz, R. (1993). "Database Exploration in Search of Regularities," Journal of Intelligent Information Systems,2:39-81.

Zytkow, J.M. & Zembowicz, R. (1996). "Automated Pattern Mining with a Scale Dimension," in Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pp. 889-894. Menlo Park, CA: AAAI Press.

genometri: company use genetic algorithms for product design

2007-09-15T14:19:00.001-07:00

TECHNOLOGY
> Intelligent Genetic Models
> Mass Customization
> Generative Design
> Color Scheming
> Color Selection

Intelligent
Genetic Models

Genes encode information – efficiently. Nature provides evidence of an effective design process operating on a genetic platform. It is known that plant- and animal-designs are based on genes. Products too have genes. Structuring designs in a genetic format opens a new world of possibilities in design, manufacturing and business.

Mass Customization

One of the critical problems in mass customization is design – which remains a manual and expert dependent process. Genetic structuring of designs enables the creation of intelligent models which understand the limits of reality. These models may be manipulated by non-designers to create what they want.

Generative Design

The power of computation is rarely harnessed by designers. The computer is a great tool for design exploration – it can explore thousands of design possibilities from which the designer can choose the best. Unfortunately this is the designer’s worst nightmare and this deep fear has prevented the translation of computational energy into creative energy. Genetic Design Technology will bridge this gap.

Color Scheming

Color Scheming is still very much an art form. It is very difficult for non-designers to create sophisticated color schemes. This is no longer true. Genometri has developed technology that will extract the graphical color logic of documents and replace its colors while maintaining the graphic logic – another powerful tool that will allow non-designers to design.

Color Selection

What is the right color for this? – this is an eternal dilemma. Many have tried to answer this and there is no shortage of color theories. But color is personal, cultural and very much dependent on context. A different approach to color selection allowing the person to judge colors around the best guess, turns color selection into a process of search and contemplation. A way of mapping colors to words and context is also developed in a social online environment. What is the color of red?

Clarient Obtains Exclusive License for Natural Selection, Inc.

2007-09-15T14:18:00.001-07:00

Clarient Obtains Exclusive License for Natural Selection, Inc. Software to Develop Novel Cancer Markers

Nov 30 2006, 2:30 AM EST

PRNEWSWIRE

ALISO VIEJO, Calif., Nov. 30 /PRNewswire-FirstCall/ -- Clarient, Inc. (Nasdaq: CLRT), a technology and services resource for pathologists, oncologists and the pharmaceutical industry, and Natural Selection, Inc. (NSI), a leader in the development of computational intelligence methods, today announced a 3-year agreement for in vitro diagnostics development in oncology. The two companies are partnering to develop innovative diagnostics to improve cancer detection. The agreement grants Clarient an exclusive, worldwide, non-transferable license to apply the NSI algorithms to specific diagnostic analysis and services.

Ron Andrews, Clarient's President and CEO, commented, "The advent of personalized medicine and the resulting gap between therapeutics and diagnostics has fueled a 'land grab' in the area of cancer biomarkers that will potentially increase the market for cancer diagnostics by as much as $1 billion in the coming 3 to 5 years. Partnering with NSI provides Clarient with proprietary access to an important intellectual asset. This key tool will aid in the development of clinically relevant biomarkers either in-house or through collaborations with biotech firms as well as academic medical centers. We expect the resulting novel markers to produce incremental recurring revenues generated by Clarient directly through its laboratory services group as well as through licensing agreements with third parties."

Andrews continued, "After a thorough evaluation of available technologies, we believe that NSI is the best partner for Clarient. NSI's biological and advanced mathematical knowledge integrated with Clarient's medical experience positions Clarient to bridge the gap between large, cumbersome data and a usable panel of cancer tests. We are very excited about this collaboration and plan to offer these services to biotechnology companies as an important tool for the development and commercialization of novel cancer markers for diagnosis, prognosis and therapy selection."

"We're pleased to be assisting Clarient in developing successful computational intelligence applications that meet Clarient's goals for generating improved cancer diagnostics and better tools for pathologists and oncologists," said Dr. Gary Fogel, Vice President of Natural Selection, Inc. "Our proprietary methods could help physicians make better, more informative decisions for their patients."

About Natural Selection, Inc.

Natural Selection, Inc. was founded in 1993 by Dr. Lawrence J. Fogel, a pioneer of evolutionary computation. The company specializes in applying this technology to solve problems in medicine and biochemistry, such as image analysis, pharmaceutical design, structure prediction, and sequence analysis, as well as other personalized medical applications. NSI also supports a variety of defense and other industry applications.

About Clarient

Clarient combines innovative technologies with world class expertise to assess and characterize cancer. Clarient's mission is to provide technologies, services and the critical information to improve the quality and reduce the cost of patient care as well as accelerating the drug development process. The Company's principal customers include pathologists, oncologists, hospitals and biopharmaceutical companies.

The Company was formed in 1996 to develop and market the ACIS(R) Automated Cellular Imaging System, an important advance in slide-based testing. The rise of individualized medicine as the new direction in oncology led the Company in 2004 to expand its business model to provide the full range of leading diagnostic technologies such as flow cytometry and molecular testing in-house, creating a state-of-the-art commercial cancer laboratory and providing the most advanced oncology testing and drug development services available. Clarient is a Safeguard Scientifics, Inc. partner company. For more information, visit www.clarientinc.com.

About Safeguard

Safeguard Scientifics, Inc. (NYSE: SFE) builds value in high-growth, revenue-stage information technology and life sciences businesses. Safeguard provides growth capital as well as a range of strategic, operating and management resources to our partner companies. The company participates in expansion financings, corporate spin-outs, management buyouts, recapitalizations, industry consolidations and early-stage financings. For more information about Safeguard, please visit www.safeguard.com.

The statements herein regarding Clarient, Inc. contain forward-looking statements that involve risks and uncertainty. Future events and the Company's actual results could differ materially from the results reflected in these forward-looking statements. Factors that might cause such a difference include, but are not limited to the Company's ability to successfully develop biomarkers either in-house or in collaboration with other parties, the Company's ability to market and generate revenues from biomarkers, the acceptance of biomarkers by biotechnology or other companies as tools for diagnosis, prognosis and therapy selection, the Company's ability to compete with other technologies and with emerging competitors in cell imaging and dependence on third parties for collaboration in developing new tests and in distributing the Company's systems and tests performed on the system, and risks detailed from time to time in the Company's SEC reports, including quarterly reports on Form 10-Q, reports on Form 8-K and annual reports on Form 10-K. Recent experience with respect to laboratory services, new contracts for instrument sales, revenues and results of operations may not be indicative of future results for the reasons set forth above.

The company does not assume any obligation to update any forward-looking statements or other information contained in this document.

1999 Computer Scientist To Explore Intricacies Of Biological Evolution

2007-09-14T23:57:00.002-07:00

Date:

June 14, 1999

Keywords:

Computer Science, Computer Programming, Evolutionary Biology, Computer Modeling, Communications, Information Technology

Computer Scientist To Explore Intricacies Of Biological Evolution

Science Daily — A $90,000 fellowship from the National Institutes of Health will send James A. Foster of the University of Idaho Computer Science Department on a journey of exploration into real-life biological evolution.

The journey, Foster said, will help him learn nature's rules that he hopes will apply to his own research into genetic programming.

Although he is interested in using it to write computer code that can adapt to changing conditions, the major interest in genetic programming is as an inexpensive way to develop software. Companies could use genetic programming to evolve software to meet demands rather than hiring software engineers to develop the computer code.

"If I can learn the real rules of how nature works, maybe I can use them to write more robust programs that can cope with changes better," Foster said.

Foster's NIH senior fellowship, awarded through the National Institute of General Medical Sciences, is a rarity, said Laurie Tompkins, program director at Bethesda, Md. His is the only one awarded so far this fiscal year, which ends Sept. 30. The grant also is unusual because it spans two years, she added.

Although the NIH senior fellowship would allow him to pursue his sabbatical studies anywhere, Foster plans to pursue his studies in the lab of Holly Wichman, an associate professor of zoology whose lab is little more than a block away on the UI campus.

Wichman has won two NIH grants, including one through the National Institute of General Medical Sciences. Wichman said modern biology needs computer science just as much as computer science needs modern biology. She works with phiX 174, a bacteriophage that in 1977 became the first organism whose genome was decoded after months of labor. Now the university has a gene sequencer that could do the same job in hours and could analyze six genomes a day if necessary.

"There has been an explosion of data. One of the things molecular biologists need is better computer programs to analyze all this information. The idea is to get a computer scientist in the lab and get his ideas and hopefully get him to build better mousetraps," she said.

She uses the bacteriophage, a virus that infects bacteria, because its life cycle is so short. "We can go through 1,000 population doublings in 10 days," Wichman said, allowing her to trace the effects of higher or lower temperatures or changing hosts on the phage's success.

"We're trying to learn the rules of evolution on a short time scale," she said. There have been surprises. "The dogma is evolution is unpredictable but on a small scale it is not always unpredictable."

Microbes show a predictable pattern in developing resistance to drugs, for example, Wichman said. "You can see the same changes occurring independently in different patients. We're trying to understand the rules that govern when evolution is predictable."

Viruses can also evolve quickly and switch hosts, a well-known worry in the medical world. That's why HIV, hantavirus and flu viruses pose such a threat and a challenge for molecular biologists, she said. "These viruses are evolving on a time scale we can observe and hopefully control."

Foster said evolution is not the sole realm of biology. He's used evolutionary theory to design programs that can respond to changes and reprogram the hardware they're running on to adapt, much as living things can.

"That's the analogy and if I can understand the analogy better, then we will be able to milk it for all its worth," he said.

There's another parallel between molecular biology and computer science, Foster said. Most of an organism's DNA is silent, meaning it does not apparently contribute directly to development or behavior. Most computer programs designed with genetic programming reach a similar point once they grow complex enough, bulking up with code that has no apparent direct influence on their function.

Wichman's interest in transposable elements in DNA, popularly known as jumping genes, caught Foster's attention several years ago. They co-published a scientific paper together about transposable elements.

"I figure if you really understand something, you will be able to find ways to use it," Foster said. "What I'm looking at long term is to get a self-correcting computer chip." But understanding how things evolve is a worthy pursuit that reaches across several disciplines, including biology, math, business and computer science, Foster said, noting that his colleague John Dickinson was one of the original developers of genetic programming. "There is a real strength to this university in evolutionary studies," Foster added.

Note: This story has been adapted from a news release issued by University Of Idaho.

2000 Scientists Discover Evolutionary Origin Of Fins, Limbs

2007-09-14T23:57:00.001-07:00

Scientists Discover Evolutionary Origin Of Fins, Limbs

Science Daily — Performance on the dance floor may not always show it, but people are rarely born with two left feet. We have genes that instruct our arms and legs to grow in the right places and point in the right directions. They also provide for the spaces between our fingers and toes and every other formative detail of our limbs.

Sharks are often portrayed with their dorsal fins knifing through the water. University of Florida researchers writing in the journal Nature have found the genetic programming used to build these fins is still at work in the human body. (Photo by: George Ryschkewitsch/University of Florida)

Evolutionarily speaking, the genetic instructions used to construct and position our limbs were being perfected more than half a billion years ago in fishes, not along the sides of the body where the fins that preceded human arms and legs sprouted, but at the midline that runs along the backbone and belly.

This midline -- think of the dorsal, tail and anal fins of a fish - is where the genetic template to produce fins originated, about 100 million years before paired fins evolved and about 200 million years before paired fins evolved into limbs, according to University of Florida genetics researchers. The findings, published online today in the journal Nature, also provide insight into the evolutionary history of genes involved in human birth defects.

"Given that paired fins made their evolutionary debut at a particular location on the sides of the body, intuitively one would think the genetic tools for fin development would be brought together in that place," said developmental biologist Martin Cohn, Ph.D., an associate professor with the UF departments of zoology and anatomy and cell biology and a member of the UF Genetics Institute. "We've discovered that the genetic circuitry for building limbs first appeared in an entirely different place - the midline of the animal."

The appearance of paired fins on the sides of early vertebrates was a major evolutionary innovation toward fin - and eventually limb - locomotion, Cohn said. The earliest fishes lacked paired fins, similar to the modern-day lamprey - a species of jawless fish with a dorsal fin and tail but no side fins - considered by biologists to share many features with the ancestor of all vertebrates.

"The emergence of paired appendages was a critical event in the evolution of vertebrates," Cohn said. "The fossil record provides clear evidence that the first fins evolved along the midline. The sequence of evolutionary events leading to the origin of limbs has been known for some time, but only now are we deciphering how these events occurred at a molecular genetic level."

Researchers isolated genes from the spotted catshark, a type of slow-moving shark from the eastern Atlantic Ocean. By studying the activity of a dozen genes in shark embryos, they determined shark median fin development is associated with the presence of genes such as HoxD, Fgf8 and Tbx18, which are vital in the development of human limbs.

They also used molecular markers for different cell types to determine which cells give rise to the median fins, finding that they arise from the same cells that form the vertebrae. These same genes dictate the emergence of symmetrical pairs of fins on the animal sides, showing a shared developmental mechanism in completely different locations, according to Renata Freitas and GuangJun Zhang, co-authors of the paper and graduate students in UF's zoology department.

Extending their genetic analysis to the lamprey - a living relic from the time before fish had paired fins - researchers found the same genetic cues in place.

"That we see these same mechanisms operating in lamprey fins tells us they must have been assembled in the median fins first, and later in evolution this entire genetic program was simply reutilized in a new position to build the first paired fins," Cohn said. "It tells us our own arms and legs have their evolutionary roots in the dorsal, caudal and anal fins of our fishy ancestors."

Many of these genetic mechanisms are involved in human birth defects, which provide insight into the evolutionary history of genes and their functions.

"Knowing that many of these genes are responsible for limb defects in humans is intriguing," Cohn said. "What we've done is identify where those developmental pathways originated during our evolutionary past and how they became involved in limb development."

Learning the mechanics of development enriches our understanding of evolution, according to Ann Campbell Burke, Ph.D., an associate professor of biology at Wesleyan University who was not connected with the study.

"Using modern molecular techniques, this confirms in a lovely way an idea that's been around for over 100 years about how paired fins may have evolved in the first place," Burke said. "To translate a 19th century observation about fin development into modern molecular data is a great thing for science. It has become increasingly important to understand developmental processes in our attempts to understand evolution."

Note: This story has been adapted from a news release issued by University of Florida.

2000 Supercomputers Help University Of Idaho Scientists Explore Genetics And Bioinformatics

2007-09-14T23:56:00.001-07:00

Date:

September 7, 2000

Keywords:

Computer Science, Distributed Computing, Computer Modeling, Information Technology, Computer Programming, Artificial Intelligence

Supercomputers Help University Of Idaho Scientists Explore Genetics And Bioinformatics

Science Daily — MOSCOW, Idaho -- The mapping of the human genome is the tip of the iceberg that is the biological information revolution.

University of Idaho computer scientists and mathematicians are joining biologists to explore new ways to interpret the complex genetic information that describes all living things and their relationships.

Along the way, UI students returning to school this fall will find a new course few schools could hope to offer: building a new supercomputer.

A $500,000 National Science Foundation grant will allow James A. Foster, an associate professor of computer science, and a team of fellow scientists to build the university's expertise in bioinformatics.

The network-based supercomputer known as a Beowulf cluster computer will be built with the help of the UI class taught by Robert Heckendorn, an assistant professor of computer science. It will deliver high performance computing to scientists on the Moscow campus.

Foster's NSF grant follows a $90,000 National Institutes of Health senior fellowship that he won last year. Through the NIH grant, Foster worked with Holly Wichman, a UI professor of zoology, to understand evolutionary biology. He hopes to apply its rules to computer science, specifically genetic programming.

Foster and Wichman are founding members of the UI Initiative for Bioinformatics and Evolutionary Studies. The grant will also support a seminar for senior-level and graduate students on bioinformatics, an emerging science.

Fellow members of the initiative group are Paul Joyce and Steve Krone, UI mathematics professors. They recently won a $166,000 National Science Foundation grant to study methods to trace how selection and other factors can affect populations.

Foster's supercomputer actually will be the second owned by the UI. The first is used by zoologist Jack Sullivan, who studies population genetics. That machine, which was funded through a National Science Foundation Grant, is housed at the Smithsonian Institution. Dave Swofford, his partner in the phylogenetics study that is the basis for the grant, is based there.

Swofford is the leading developer of software to study phylogenetics or evolutionary relationships and needed the highest-speed connection to the supercomputer, Sullivan said. That is why the equipment is housed and administered at the Smithsonian in Washington.

The new supercomputer and grant will provide powerful computing resources to support the university's studies in bioinformatics and evolutionary studies, he said.

Ecologists and epidemiologists use mathematical models to trace the relationships among populations of plants and animals, including disease organisms. The goal is to sort through complicated or patchy information to understand links between individuals and groups.

Examples range from the evolution and spread of infectious diseases to invasions of exotic species like weeds, Krone and Joyce noted.

"From the genetic models, we want to look at how certain characteristics are passed down and change through time," Krone said. One way to approach this is by "looking back in time" to see how ancestral relationships and mutations cause the genetic characteristics seen in present-day populations. This backward-looking approach is called coalescent theory.

"Diversity is one general question that's at the bottom of a lot of things. Looking at coalescent theory is one way to calculate the amount of diversity in a population. We want to come up with models to describe and explain certain phenomena we see in nature," Krone said.

Joyce and Krone's interest is in the probability and statistical models that can be used to trace such relationships. Using mathematical methods to track genes while accounting for natural selection and other forces is complicated and fraught with randomness.

The same sorts of complexity and randomness that is part of biological evolution also holds sway for the computer programs Foster is interested in. "It's abstract enough that we could use it for our work building software that can adjust to new conditions or even repair itself," he said.

-30-

SIDEBAR: Students Get Hands-on Experience Building Supercomputer in UI Class

MOSCOW, Idaho -- The age of high-performance computing once symbolized by supercomputers costing millions of dollars apiece, may be closer to home than we think, a University of Idaho computer scientist says.

Robert Heckendorn, an assistant professor of computer science, will oversee students enrolling in a directed study class that will design and build a Beowulf cluster computer this fall. The new supercomputer is one of a class of low cost, high performance computers built with off-the-shelf components.

"We probably won't recognize them when they do go into use," said Heckendorn. Homes may be equipped with versions to customize heating or cooling systems, lights and appliances.

But until then, the new system the class will help design and build has the feel of the earliest days of home computing, when hobbyists worked in their basements or garages to assemble their own computers. "This is like building a hot rod," he said.

The students will work with a budget of $44,000, developing specifications for the equipment and recommending software and hardware for the supercomputer.

The budget comes from a $500,000 National Science Foundation grant won by James A. Foster, a UI associate professor of computer science, and a team of UI researchers to expand the university's expertise in bioinformatics.

"The students will put together a proposal as a class and make a recommendation about how to proceed. I will make the final decision but I don't want to steer the students by talking about it right now. I have an idea of the direction we'll take, but I may be wrong," he said.

The students will work on every step of the project, from determining the requirements the supercomputer must meet, though the purchase, assembly, software selection and installation. "They are involved from start to finish. It should be a great experience for them," Heckendorn added.

Beowulf cluster computers are the rage in high-performance computing these days. The clusters of computer processing and memory chips that form their heart can be assembled relatively cheaply from simple components. Off-the-shelf computers built for the consumer market can do the job.

"It's commodity computing. If you can only buy commodity computers and hook them together with the right stuff in the right way, you can get supercomputing power," he said. Although multi-million dollar specialty supercomputers still dominate the high end of the market, Beowulf-style supercomputers are gaining.

The class already has an experienced hand on the roster: Andrew Shewmaker, a UI senior from Kimberly, Idaho, studying computer science. "As far as I know he's the only one in the class who has worked with one," Heckendorn said.

Shewmaker learned about Beowulf supercomputing while interning at the Idaho National Engineering and Environmental Laboratory during the past three summers. "They've built two Beowulfs in the last two years," he said.

Although he wasn't involved in building the clusters, Shewmaker said, "I did get to help administer and use them."

"I am extremely excited about this project," Shewmaker said. "I am interested in building a Beowulf because I have read tons of information about it on the Internet and in books but I have yet to apply what I have read."

Note: This story has been adapted from a news release issued by University Of Idaho.

2005 Programmable Cells: Engineer Turns Bacteria Into Living Computers

2007-09-14T23:55:00.000-07:00

Date:

April 28, 2005

Keywords:

Biotechnology, Developmental Biology, Microbiology, Molecular Biology, Genetics, Cloning

Programmable Cells: Engineer Turns Bacteria Into Living Computers

Science Daily — In a step toward making living cells function as if they were tiny computers, engineers at Princeton have programmed bacteria to communicate with each other and produce color-coded patterns.

The feat, accomplished in a biology lab within the Department of Electrical Engineering, represents an important proof-of-principle in an emerging field known as "synthetic biology," which aims to harness living cells as workhorses that detect hazards, build structures or repair tissues and organs within the body.

"We are really moving beyond the ability to program individual cells to programming a large collection -- millions or billions -- of cells to do interesting things," said Ron Weiss, an assistant professor of electrical engineering and molecular biology.

Collaborating with researchers at the California Institute of Technology, Weiss and graduate student Subhayu Basu programmed E. coli bacteria to emit red or green fluorescent light in response to a signal emitted from another set of E. coli. In one experiment, the cells glowed green when they sensed a higher concentration of the signal chemical and red when they sensed a lower concentration. In a Petri dish, they formed a bull's-eye pattern -- a green circle inside a red one -- surrounding the sender cells.

In addition to demonstrating that the genetic programming techniques work, this sensing system could be useful for the detection of chemicals or organisms in laboratory tests. "The bull's-eye could tell you: This is where the anthrax is," said Weiss.

The researchers published their results in the April 28 issue of Nature. In addition to Weiss and Basu, authors of the paper are postdoctoral researcher Yoram Gerchman at Princeton and professor of chemical engineering Frances Arnold and graduate student Cynthia Collins at Caltech. It was funded by a grant from the U.S. Defense Advanced Research Projects Agency.

In previous work, including a paper published March 8 in the Proceedings of the National Academy of Sciences along with Sara Hooshangi and Stephan Thiberge, Weiss showed the feasibility of inserting engineered pieces of DNA into cells to make them behave in the same manner as digital circuits. The cells, for example, could be made to perform basic mathematical logic and produce crisp, reliable readouts that are more commonly associated with silicon chips than biological organisms. The new paper applies similar techniques to a large population of cells.

"Here we're showing an integrated package where the cells have an ability to send messages and other cells have the ability to act on these messages," said Weiss.

The creation of patterns, such as the bull's-eye effect, is a key step in one of Weiss' eventual goals, which is to have the cells secrete materials that build physical devices such as antennas or transmitters in places that are hard for humans to reach. Programmed cells also could be used to control the repair or construction of tissues within the body, possibly guiding stem cells to the locations where they are needed for the growth of new nerve or bone cells in a process Weiss called "programmed tissue engineering."

Even the early step of creating patterns in a Petri dish, however, may be useful as a tool for other scientists, particularly developmental biologists who are trying to understand how the cells of an embryo arrange themselves into patterns that become the various body parts of a mature organism. In fruit fly embryos, for example, the first cells are thought to differentiate into the head, abdomen and other parts based on the concentration of chemical signals that are emitted from the ends of the embryo.

In addition to conducting laboratory experiments, Weiss and colleagues are creating computer models of their engineered systems, which allow them to study how small modifications would affect the ultimate behavior of the organisms. So far, said Weiss, the experimental results have matched the computer models fairly closely, but the goal is to have a mathematically exact description of how each component works.

"One of the nice things about synthetic biology is that because we built the network from scratch, we should be able to model all the important details," he said. At some point in the future, he said, scientists will be able to choose a behavior they want from cells, and a computer program will create a genetic circuit to accomplish the task. "Then we can do an experiment to see if the community of cells is behaving as we desire. That is going to have a tremendous number of applications."

Note: This story has been adapted from a news release issued by Princeton University.

2001 Genetic Algorithms "Naturally Select" Better Satellite Orbits

2007-09-14T23:53:00.004-07:00

Source:	Purdue University
Date:	October 16, 2001

Keywords:

Satellites, Aviation, Moon, Vehicles, Asteroids, Comets and Meteors, Computer Programming

Genetic Algorithms "Naturally Select" Better Satellite Orbits

Science Daily — WEST LAFAYETTE, Ind. Some Earth-orbiting satellites will be able to keep in touch longer with controllers on the planet's surface thanks to computer programs that mimic Darwin's evolutionary model of survival-of-the-fittest.

Purdue University engineers used "genetic algorithms" to design innovative constellations, or collections, of satellites orbiting the Earth. The algorithms are helpful in designing low-cost constellations that save money by placing a small number of satellites around the Earth at relatively low altitudes, said William Crossley, an associate professor at Purdue's School of Aeronautics and Astronautics and a faculty member of the university's Center for Satellite Engineering.

Such low-altitude satellite constellations are expected to bring a boon to mobile computing by making it more possible for people to use wireless communication devices. The constellations also may have military applications because they make it possible to quickly reposition satellite constellations for specific surveillance purposes.

However, the constellations have a key disadvantage. To maintain contact with stations on Earth, the satellites must be in a line of sight with antennas on the planet. Because the constellations contain only a few satellites orbiting at low altitudes, there are times when none of the satellites can be seen by ground stations; they are blocked by the Earth's curvature, temporarily cutting off communications. The conventional method for designing constellations containing three or four satellites in low-altitude orbits results in the satellites being out of touch with Earth for about four orbital periods out of each day. Each period represents a single orbit around the Earth, which takes about 90 minutes. During those four orbits, a base on Earth would not have a line of sight to any of the satellites, making communication to or from the Earth base impossible.

The Purdue-designed constellation, however, reduced the blackout time to three orbital periods, keeping the satellites in touch 90 minutes longer. The design is now being considered for defense-related satellites. A research paper about the findings is in the July-September issue of the Journal of Astronautical Sciences, published by the American Astronautical Society.

Genetic algorithms, or computer instructions, adapt Charles Darwin's evolutionary model, interchanging design elements in hundreds of thousands of different combinations. Only the best-performing combinations are permitted to survive, and those combinations "reproduce" further, progressively yielding better and better results. The most profound impact of such algorithms is that they sometimes find solutions that researchers would ordinarily have missed. An added bonus is that they run continuously, overnight and for days at a time, sometimes working faster than would have been humanly possible.

"The genetic algorithm can provide a good starting point," Crossley said. "Once the genetic algorithm has generated a solution, fine tuning or refinement needs to be done to obtain the best final solution."

The genetic algorithm developed by Crossley and former graduate student Edwin Williams has been used to design a constellation of satellites for a possible defense mission, and research collaborators at The Aerospace Corporation in El Segundo, Calif., are currently using the approach to investigate other possible constellation designs.

"For small numbers of satellites, at low altitude, we find constellations that outperform significantly the ones that you would find using the traditional approach," Crossley said.

If money is no object, then satellites can be kept in constant communication with Earth by placing constellations of three satellites in orbit 20,000 miles above Earth. Because they are high above Earth, each satellite can see a large portion of the surface. But the satellites are more expensive to design and build because they must withstand higher radiation than lower-altitude satellites, they require larger on-board power supplies to send and receive signals, and placing them in the proper orbits requires a larger launch vehicle and takes more time.

In comparison, the lower altitude satellites are placed in orbits only a few hundred miles above Earth.

Genetic algorithms are helpful in designing lower-cost constellations by sorting through the multitude of possible configurations and coming up with a design that minimizes the amount of time that the satellites are out of touch with links on the ground. The genetic algorithm designed at Purdue naturally selected the best-performing constellations by interchanging variables such as how far apart the satellites are from each other, the heading of the satellites as they cross the equator, and how high they are above the Earth's surface.

The results were unexpected. Normally, in constellations containing small numbers of satellites, the satellites are spaced at equal distances from each other as they track across the globe's equator. But in the best-performing constellations discovered by the genetic algorithm, the satellites were not spaced at equal distances.

"For example, the constellations might have two satellites spaced very far apart, and the third one will be very close to the second one," Crossley said, noting that engineers with years of aerospace experience were surprised by the higher performance offered by the unconventional design.

Williams, who earned a master of science degree in December 1999, currently works for the Pratt & Whitney Division of United Technologies Corp., in East Hartford, Conn.

Note: This story has been adapted from a news release issued by Purdue University.

1999 Computers Use Darwinian Model To "Evolve" Fuel Additives

2007-09-14T23:53:00.003-07:00

Date:

July 22, 1999

Keywords:

Organic Chemistry, Chemistry, Fossil Fuels, Inorganic Chemistry, Materials Science, Computer Modeling

Computers Use Darwinian Model To "Evolve" Fuel Additives

Science Daily — WEST LAFAYETTE, Ind. -- Chemical engineers at Purdue University have developed and demonstrated how a computerized system that mimics evolution can discover new gasoline additives for better engine performance.

The engineers developed "genetic" algorithms -- or computer instructions -- that adapt Charles Darwin's evolutionary model to combine and recombine chemical components until the "fittest" fuel additives emerge. Each additive is made of three sections: a head, linker and tail. But there are about 20 distinct kinds of heads, linkers and tails that can be combined differently to make a nearly endless variety of compounds.

"Based on the combinations, they can have completely different properties," says Venkat Venkatasubramanian, a professor of chemical engineering. The numerous combinations can be likened to biological diversity: the genetic blueprints for all life forms are made of the same four chemical building blocks of DNA, and only subtle variations in gene sequences spell the difference between monkeys and humans.

Rather than trying to study the properties of every possible compound, the evolutionary method naturally selects the best-performing additives.

"We randomly create hundreds of molecules from these heads and tails at the beginning," Venkatasubramanian says. The system can then predict how well the molecules will work by evaluating their structures.

Only the best candidates are kept, and they continue to breed. Their head, linker and tail sections are recombined, and so on, until a final "generation" of highest-performing additives is reached.

Fuel additives are needed to reduce deposits, left over from the combustion of gasoline, that build up on engine valves. The deposits eventually affect the performance of the valves, hindering engine efficiency. Additives latch onto waste material, preventing it from settling on the surfaces of valves.

The work was detailed in a poster presentation Wednesday, July 21, during the Fifth International Conference on Foundations of Computer-Aided Process Design (http://www.ecs.umass.edu/che/FOCAPD99) in Breckenridge, Colo. The paper was written by Venkatasubramanian, graduate students Anantha Sundaram and Prasenjeet Ghosh, chemical engineering Professor James M. Caruthers, all from Purdue, and chemist Daniel T. Daly from Lubrizol Corp. in Wickliffe, Ohio, which funded the research.

Genetic algorithms are not limited to the design of gasoline additives. They have been used in other applications and might become a major force in the design of future drugs, plastics and other products, Venkatasubramanian says.

Note: This story has been adapted from a news release issued by Purdue University.

2006 Engineers Take Page Out Of Nature's Playbook

2007-09-14T23:53:00.001-07:00

Engineers Take Page Out Of Nature's Playbook

Science Daily — Designing complex systems such as nuclear reactors for space applications is a daunting task, but Oak Ridge National Laboratory researchers have made it less so by borrowing from nature.

Using their genetic algorithm optimization tool, a takeoff of the natural selection process, Louis Qualls and colleagues can quickly perform searches of huge numbers of potential solutions to an engineering problem and identify the best options. An algorithm is a procedure for solving a mathematical problem. Advances in supercomputing and advanced optimization technologies are making it possible to sift through an enormous number of possibilities even for complex problems such as nuclear reactor design.

"Designing space reactor power systems, nuclear reactors or safer automobiles is a long process that involves making perhaps thousands of choices," said Qualls, a nuclear systems integration specialist. "It can take months or years to perform all of the necessary calculations using traditional methods.

"With genetic algorithms, however, we can perform those calculations and end up with a short list of potential solutions in a matter of just minutes or days, depending on the problem."

As in nature and the survival of the fittest, the genetic algorithm approach evolves by removing poor solutions or designs that do not perform well and repopulates the next generation with only combinations - or mutations - of the better designs. Over time and with successive generations only the best options remain.

Unlike traditional design analysis, which is limited to the specific input of engineers, complete with their biases, design optimization through genetic algorithms has virtually no boundaries. Each answer is created without sequential design information, which results in novel approaches that would likely never be generated with conventional methods.

"Because of our individual education and training, we tend to approach problems with certain preconceptions," Qualls said. "Consequently, we often miss unique solutions to any given design challenge."

Specific areas of interest for the Department of Energy's ORNL are in materials research and development and understanding how various metals and alloys respond to extreme radiation. Qualls noted that these are areas for which ORNL has established a long tradition of excellence and continues to play a key role in the nation's efforts to develop nuclear reactors for the space program and commercial nuclear reactors.

Qualls illustrated the advantage of genetic algorithm-based design methods with a recent example proposed by the Nuclear Science and Technology Division irradiation engineering team. The challenge was to optimize the design of an experiment in which 128 material test specimens were to be irradiated in ORNL's High Flux Isotope Reactor.

The specimens were composed of four different materials that were to be distributed over three different temperatures to obtain the broadest range of evenly spaced irradiation damage levels.

"There are literally billions and billions of possible combinations of temperature and specimen arrangements," Qualls said. "While this is something that can be solved manually given some time, it makes a lot of sense to use genetic algorithms to quickly find the most promising solutions. In just a few minutes we found four solutions that were marginally better than the manually derived solutions."

From the perspective of Sherrell Greene, director of Nuclear Technology Programs at ORNL, the genetics algorithm method is providing new design approaches and innovative designs for terrestrial and space-based reactor power and propulsion systems.

"The tools developed by ORNL researchers have already made valuable contributions to our space power programs by enabling us to rapidly explore new concepts and designs," Greene said. "Now we are beginning to harness the power and flexibility of the genetic algorithm approach to improve the design of irradiation experiments and maximize the value of our R&D facilities to our researchers."

In addition to Qualls, others involved in developing the genetic algorithm optimization tool are Ken Childs of the Computational Sciences and Engineering Division and Ed Blakeman, Seokho Kim, Jeff Johnson and John Neal of the Nuclear Science and Technology Division.

This research has been funded by DOE Office of Science, NASA and by the Laboratory Directed Research and Development program. UT-Battelle manages Oak Ridge National Laboratory for the Department of Energy.

Note: This story has been adapted from a news release issued by Oak Ridge National Laboratory.

2003 Falling Prey To Machines?

2007-09-14T23:52:00.000-07:00

Falling Prey To Machines?

Science Daily — ANN ARBOR, Mich (Feb. 10, 2003) -- It's coming, but when? From Garry Kasparov to Michael Crichton, both fact and fiction are converging on a showdown between man and machine. But what does a leading artificial intelligence expert--the world's first computer science PhD--think about the future of machine intelligence? Will computers ever gain consciousness and take over the world?

"Computer sentience is possible," said John Holland, professor of electrical engineering and computer science and professor of psychology at the University of Michigan. "But for a number of reasons, I don't believe that we are anywhere near that stage right now."

In the 1960s, Holland created the field of genetic algorithms, a process in which computers solve problems by mimicking biological evolution. By adapting concepts of natural selection and sexual reproduction to computer programming, Holland showed that computers could "evolve" their programming to solve complex problems in ways that even their creators did not fully understand.

Researchers have since then been able to use genetic algorithms to "breed" optimal solutions for things like managing energy distribution systems or designing ultra-efficient aircraft engines. Genetic algorithms also provide the basis for much of Michael Crichton's best-selling novel Prey, in which nano-sized machines evolve into an intelligent, life-threatening swarm. Holland's research and that of several of his students is cited as source material for the book.

But evolving solutions for well-defined optimization problems is distinctly different than synthesizing something as opened-ended as consciousness or freewill.

According to Holland, the problem with developing artificial intelligence through things like genetic algorithms is that researchers don't yet understand how to define what computer programs should be evolving toward. Human beings did not evolve to be intelligent--they evolved to survive. Intelligence was just one of many traits that human beings exploited to increase their odds of survival, and the test for survival was absolute. Defining an equivalent test of fitness for targeting intelligence as an evolutionary goal for machines, however, has been elusive. Thus, it is difficult to draw comparisons between how human intelligence developed and how artificial intelligence could evolve.

"We don't understand enough about how our own human software works to come even close to replicating it on a computer," says Holland.

According to Holland, advances in software have not kept pace with the exponential improvements in hardware processing power, and there are many artificial intelligence problems that cannot be solved by simply performing more calculations. While hardware performance continues to double almost every year and a half, the doubling time for software performance is at least 20 years.

"In the final analysis, hardware is just a way of executing programs," says Holland. "It's the software that counts."

Comparisons between the brain and electronic hardware are also difficult to draw. For example, the issue of "fanout" demonstrates the complexity of the brain over even today's most sophisticated computers. Fanout refers to the number of connections an element in a network can have to another element of a network. Today's most complicated computers have a fanout factor of about 10. The human brain, however, has a fanout of 10,000.

"We don't have the faintest idea of what machines with that kind of fanout would be like, so inference from the capabilities of present machines to such machines is feeble at best," notes Holland. "As Nobel Laureate physicist Murray Gell-Mann says, three orders of magnitude is a new science."

Advances in hardware, however, have helped computers tackle simpler feats of human-like intelligence with some success. In 1997, IBM's Deep Blue supercomputer was the first machine to beat world chess champion Garry Kasparov. In a recent rematch, Deep Blue's successor, Deep Junior, fought Kasparov to a dramatic 3-3 draw. Kasparov said he played better than the machine and would have pressed a human opponent for a win, but he was afraid that the tireless computer would punish him for on any small mistake he might have made in his fatigue.

"It is a remarkable, but not necessarily surprising accomplishment for computers to play chess at this level. They've been approaching this kind of capability for years," says Holland of the Kasparov-Deep Junior match. "But AI researchers are much more amazed that human beings can still compete with computers on such an even basis given their limited abilities for detailed search. It shows us how much we don't know about the human brain."

Human beings approach playing chess very differently than computers. Kasparov, the top ranking chess player in the world, can probably evaluate about two or three moves a second, relying on his superb intuition and pattern-recognition abilities--things very difficult to teach a computer--to help him win. Deep Junior, on the other hand, crunches up to 3 million moves per second and draws on a huge library of past games and possible moves to succeed. Relying on a weighted algorithm that calculates a numerical advantage representing each possible move, the computer mostly powers through a list of potential ways any given game can play out.

"Until the last decade of the 20th century, AI relied on clever programming and brute computation," says Holland. "Deep Junior is an example of this approach. But the next step for machine intelligence will be in getting them to invent truly creative solutions to complex problems."

For Holland, the crucial leap in machine intelligence will be when computers start thinking like human beings, rather than just reaching the same results as them with different processes. This kind of advanced artificial intelligence would involve learning new skills, adapting to unforeseen circumstances and using analogy and metaphor like humans do. To make these breakthroughs possible, researchers will need an overarching theory that can shape the field of artificial intelligence in the same way that Maxwell's theory of electromagnetism shaped modern physics.

"We are at the earliest stages of theory-making in AI and mature theories of this kind typically take decades of work," says Holland. "Sentient computers are possible, but I don't think we will have them until we have such guidance."

Holland is a pioneer in the fields of artificial intelligence, parallel computation, adaptive systems and cognitive processes, and author of the book Hidden Order: How Adaptation Builds Complexity. He received the world's first PhD in computer science in 1959 from the University of Michigan. He also holds an MA ('54) in mathematics from the University of Michigan and a BS ('50) in physics from the Massachusetts Institute of Technology.

The University of Michigan College of Engineering is consistently ranked among the top engineering schools in the world. The College is composed of 11 academic departments: aerospace engineering; atmospheric, oceanic and space sciences; biomedical engineering; chemical engineering; civil and environmental engineering; electrical engineering and computer science; industrial and operations engineering; materials science and engineering; mechanical engineering; naval architecture and marine engineering; and nuclear engineering and radiological sciences. Each year the College enrolls over 7,000 undergraduate and graduate students and grants about 1,200 undergraduate degrees and 800 masters and doctoral degrees. For more information, please visit our web site at http://www.engin.umich.edu .

Note: This story has been adapted from a news release issued by University Of Michigan College Of Engineering.

2004 Survival Of The Fastest: Scientists 'Selectively Breed' Winning Formula One Cars

2007-09-14T23:51:00.000-07:00

Survival Of The Fastest: Scientists 'Selectively Breed' Winning Formula One Cars

Science Daily — Speed is the name of the game in the world of racing and now University College London scientists have developed a technique that 'breeds' winning Formula One cars.

By applying Darwinian principles to the art of motor racing, the researchers demonstrate in simulations that it's possible to knock crucial tenths of a second off lap time by tailoring a car's setup to whatever conditions are faced on the track.

In a paper to be presented later this month at a conference in Seattle, researchers will report on a new computer model based on genetic algorithms that optimises performance by selectively combining the best settings of Formula One cars to produce the ultimate configuration.

Results show it's possible to shave 0.88 of a second per lap from the best time. In an industry where 1/100th of a second can separate a winner from a loser, that can make all the difference.

Dr. Peter Bentley, leader of the Digital Biology Group at UCL's Department of Computer Science and senior author of the study, says:

"Formula One spends millions each year designing and applying the latest technology to ensure their cars can handle whatever is thrown at them on the track. Each car can be modified in hundreds of way to optimise performance. Even minor changes in wing height, suspension stiffness or type of tyre rubber are 'tweaked' to give them the competitive edge.

"Before every race, attempts are made to optimise settings for given conditions but cars are so finely calibrated than even subtle changes in temperature can affect performance. Decisions are based on experience but there are no guarantees they will always get it right.

"By running simulations we were able to distinguish how different facets of the car perform. Each best performance solution was treated as though it had its own genes that define those parameters. These winning solutions were then bred to produce the next generation, which combined the best settings of both parent cars until eventually we evolved the ultimate Formula One vehicle setup."

Genetic algorithms are an emerging technology that unites the fields of biology and computer science by mimicking the process of evolution in computers in an effort to find the best solutions to complex problems. A number of possible solutions to the problem are treated as 'organisms' known as phenotypes. These are placed into a simulated environment, allowing them to be judged by a set of conditions. Only the better phenotypes survive and they produce 'children' in the next generation. These children are then judged in the environment, the better ones have children, and so on. After a number of generations have passed, fitter phenotypes evolve with new forms better suited to the task required.

The researchers configured 68 parameters in the simulation car, which affected suspension, the engine, tyre and brake pressure, fuel consumption and steering control. Variables included:

* anti-sway has an effect on the under/over-steer for the car and the contact that the tyres have with the ground

* gear ratios effects the acceleration of the car

* wings change the downwards force of the vehicle and its grip on the road

Five experiments were performed using a racing simulation designed by Electronic Arts. The first four experiments tested the car on the UK's Silverstone track. Population size and the number of generations were varied to determine the effect on optimisation. The final run was tested on Germany's Nurburgring track to assess whether the evolved car could still be a winner on a track that presented different challenges.

Mr. Krzysztof Wloch, of UCL's Department of Computer Science and lead author of the study, explains:

"Silverstone is generally a fast circuit with several slow corners and a selection of fast sweeping turns. This allowed us to test cars that are tuned for higher speed, with less down force for cornering. In contrast Nurburgring is a very twisty and tough track. That means cars need to be configured for high-down force to handle tight corners at speed."

At Silverstone, lap time was improved from 1 minute 27.005 seconds to 1 minute 21.050 seconds. Similarly, optimal lap time at Nurburgring improved by seven per cent.

To verify results, a virtual race was set up at Silverstone using cars configured using: genetic algorithms; the default settings of the simulator; human tuning; and an Internet expert. Results placed the evolved setting first with a time of 1 minute 20.349 seconds. The expert setting came second, 0.879 seconds slower. The human tuning came third with a time 1.09 seconds slower. The default settings came last, a massive 2.42 seconds behind. In real life, the fastest lap for Silverstone in 2003 was 1 minute 21.209 seconds.

"The real test would be to use our system in an actual Formula One car," says Dr Bentley. "At present have they have their own software that monitors performance during a race. Using our system you could evolve the car setup while the racing is going on. So if a car was damaged, at the next pit stop you could optimise the settings to offset whatever has gone wrong. You could even beam changes to the car while it is on the track, but somehow I don't think racing authorities would go for that."

Details of the study will also appear in this week's New Scientist magazine (19/06/04).

Note: This story has been adapted from a news release issued by University College London.

2000 Building Better Engines Through Natural Selection

2007-09-14T23:50:00.001-07:00

Building Better Engines Through Natural Selection

Science Daily — MADISON - Could Charles Darwin's rules of evolution help engineers design high-performance engines of the future?

Computer models developed at the University of Wisconsin-Madison are doing just that, by using genetic algorithms to simultaneously increase fuel efficiency and reduce pollution.

Peter Senecal, a post-doctorate engineer at UW-Madison, created the computer models to help sort through literally billions of combinations of factors that determine engine performance - a task too enormous for conventional computer simulations.

Senecal says the most important advance is in improving pollution emissions without sacrificing fuel efficiency, and vice versa. Normally, engine designers who concentrate on solving one problem end up with major tradeoffs in the other.

The results to date have been dramatic. Using a Silicon Graphics supercomputer at UW-Madison's Engine Research Center, Senecal created a diesel engine design that reduces nitric oxide emissions by three-fold and soot emissions by 50 percent over the best available technology. At the same time, the model reduced fuel consumption by 15 percent.

Six engine performance measures were studied, including fuel injection timing, injection pressure, and amount of exhaust recirculation. The simulation was then reproduced experimentally in a real diesel engine housed at the ERC. "We found that the agreement was excellent between what was measured in the lab engine and what the computer predicted," Senecal says.

Senecal's research will be published in an upcoming issue of the International Journal of Engine Research. He will also give an invited presentation Wednesday, June 21, to the Society of Automotive Engineers international meeting in Paris.

His work also is turning heads in the engine manufacturing industry, which faces major new federal pollution control mandates by the year 2002. Caterpillar Inc., a Peoria-based manufacturer of diesel engines for trucks and heavy equipment, is funding Senecal's post-doctorate work that will focus on improving the geometry of engines.

Senecal says genetic algorithms have been developed in recent years for other engineering challenges, such as designing bridges and airplane wings. "I kind of stumbled onto this in the literature, and wasn't sure if it would work for something as complex as engine design," he says.

Here's how it works: Senecal begins with five "individuals," which are defined as one distinct set of the six engine parameters. Four of the individuals are randomly selected and the fifth is the baseline, or best known set of parameters.

Next, a computer model is used to weed out the best parameters of the first group. The two fittest "parents" are then allowed to "reproduce" and a new generation is formed, complete with "mutations" that represent marked improvements over the previous generation. The process is continued through successive generations until the computer identifies the most "fit" member of the group.

Senecal says this process narrows the field of potentially one billion calculations on the computer down to 200 to 250 of the best possibilities. The computer can accomplish in weeks what would otherwise take decades to run.

Mechanical engineering Professor Rolf Reitz, Senecal's Ph.D. thesis advisor, says the computer model is extremely versatile and could be used for all types of engines. While curent work focuses on questions like fuel injection and air intake, studies of engine hardware are just beginning.

Reitz says the typical engine piston, for example, has not been fundamentally improved upon for decades. Yet engineers have no idea whether a different geometry could produce much better engines.

If engine manufacturers want a more powerful engine, or a more durable engine, one can program the genetic model to find those traits, too. "If you want your children to be long jumpers, high jumpers or sprinters, you can specify these attributes with this program," Reitz says.

The diesel engine industry faces a U.S. Environmental Protection Agency mandate to cut nitric oxide emissions in half by 2002. Wisconsin's small engine industry, also facing pollution-control deadlines, also has initiated a research program at UW-Madison using the genetic model.

###

NOTE TO GRAPHICS EDITORS: A chart to accompany this story is available for downloading at: http://www.news.wisc.edu/newsphotos/engines.html

Note: This story has been adapted from a news release issued by University Of Wisconsin-Madison.

1999 Evolving Algorithms Take Aim At Prostate Cancer

2007-09-14T23:49:00.002-07:00

Evolving Algorithms Take Aim At Prostate Cancer

Science Daily — Researchers are sending forth strings of binary digits to go forthand multiply-all in the name of human health.

Using strands of 0s and 1s to stock a digital community, completewith mating, offspring, and the occasional mutation, is nothing new toscientists who create genetic algorithms. These mathematical formulas aregoverned by Darwin's "survival of the fittest" mantra and rely on theprinciples of evolution to create solutions in a variety of applications,including financial analyses, computer-assisted scheduling, and targetdetection for the military.

Now scientists at the University of Rochester Medical Center areexploring use of the formulas to treat prostate cancer by improving howradiation is delivered. The formulas have been developed by medicalphysicist Yan Yu, Ph.D., a well-known expert on radiation treatment planningwho heads a task force on the subject for the American Association ofPhysicists in Medicine. His algorithms are at the heart of a new start-upcompany aimed at improving a common prostate cancer procedure calledbrachytherapy, where tiny radioactive seeds are implanted into the prostateand destroy cancer cells in the organ over several weeks. It's anincreasingly popular procedure for treating the nearly 200,000 men each yearwho are diagnosed with cancer of the prostate, which is an organ about thesize of a small peach between the rectum and bladder that contributes fluidsto semen.

Medical physicists like Yu, an associate professor of radiationoncology, play an often unseen role in cancer treatment, ultimately decidinghow to deliver radiation to best eradicate cancerous tissue or organswithout hurting healthy tissue. In cases of prostate cancer, the stakes arevery high: the bladder, rectum, urethra, and nerves that control sexualfunction are all packed together near the organ, making it an especiallychallenging disease to treat. Brachytherapy is a little bit like baking asingle muffin from the inside out, with physicists and physicians trying toensure that every bit of the "muffin" is cooking at the exact sametemperature while the other muffins nearby stay cool.

Choosing the right pattern for the seeds, which are radioactiveparticles about the size of a grain of rice, is daunting. Physicianscommonly turn to commercial programs to help them decide how to place theparticles. The recommended treatment plan is put in the hands of a surgeon,who actually inserts several dozen seeds into the prostate during a one- ortwo-hour surgical procedure.

Yu's work, dubbed PIPER for Prostate Implant Planning Engine forRadiotherapy, uses artificial-intelligence technology to recommend aradiation treatment plan. Based on an ultrasound scan of a patient'sprostate and other pelvic organs, PIPER sets up a competition between thepossible configurations. Yu and colleagues create a digital community with64 "members" whose binary codes each represent a different radiationpattern. Community members compete to pass on their "genetic material"-bitsof binary code-to the next generation. Each pattern's viability isdetermined by mathematical criteria which favor radiation plans thatirradiate the prostate efficiently and knock out cancerous cells whilesparing vital organs. In a game of virtual natural selection, binary codethat embodies these qualities survives and multiplies, while poor codeperishes.

Over the course of 200 generations the community evolves, with codescoming together randomly, combining their genetic material, and evenmutating occasionally. In this way, the genetic algorithm creates a hugerange of potential solutions that it constantly sifts to find the bestcandidate for a treatment plan. "A genetic algorithm can look at a muchgreater range of options than we otherwise could. There might be certaincombinations that would never occur to a physicist to try," says Yu.

In just two minutes, PIPER presents to physicists and physicians the"winner"-the plan that the program decides is most likely to work best. Thespeed of PIPER, whose underlying technology has been patented by theUniversity, may make it possible to do the radiation planning right in theoperating room immediately before surgery, instead of several weeksbeforehand as is now standard. That's a tremendous advantage, says surgeonEdward Messing, M.D., chair of the Department of Urology, who has performedscores of brachytherapy procedures at the University's Strong MemorialHospital.

"The prostate you see in the operating room is never the same oneyou saw three weeks previously in your office," says Messing. "Hormonetherapy before surgery can shrink the prostate, for instance, and evenanesthesia can change the positioning of the pelvis the day of surgery. Thisoftentimes makes deviations from the now-dated plan necessary duringsurgery." Yu's goal is to make the process more precise. With a radiationtreatment plan compiled just minutes before the operation, the plan is morelikely to match what physicians actually confront in the operating room.

To commercialize the technology, the University has joined with RealTime Enterprises, a Rochester software engineering firm, to create a newcompany, RTek Medical Systems LLC. RTek will focus on the development of newradiation treatment planning systems based on Yu's algorithms. Any suchsystem must be tested rigorously before any application for marketingapproval will be submitted to the U.S. Food and Drug Administration, and theFDA must approve any product before it would become available.

At the University, the FDA has approved a clinical trial of thecurrent system as an investigational device on about 30 patients. Messing,Yu and their colleagues will study the radiation treatment plans recommendedby the system, along with the effects on tumor control, quality of life, andcomplications in patients who get the PIPER treatment compared to patientswho receive a commercially available treatment. The clinical study willbuild on more than five years of basic research that has been funded by avariety of sources, including the National Cancer Institute and the WhitakerFoundation.

New product development and support is part of the expertise thatReal Time Enterprises (RTE) brings to the partnership. The companyspecializes in software for medical equipment and devices like bloodpressure monitors, vision screeners, and other diagnostic equipment usedaround the world.

"This line of research really is compelling," says RTE PresidentRobert Ruppenthal. "People who treat cancer are visibly excited andimpressed by the potential of this technology, because it's so differentfrom what's out there today. Current treatment planning tools are trial anderror: They will tell a physician what dose a given seed distribution willdeliver, but they will not tell the doctor where to put the seeds."

RTek is the result of an accelerated effort by the University tocommercialize technology developed in its laboratories. "There are manyexciting technologies being developed in the Medical Center and across theentire University," says Jay Stein, M.D., senior vice president of theMedical Center and vice provost for health affairs. "This is one of thefirst of what we expect to be an ongoing series of technologies we plan tocommercialize."

CONTACT:
Yan Yu, yan_yu@urmc.rochester.edu, (716) 275-9988
Tom Rickey, trickey@admin.rochester.edu, (716) 275-7954
Edward Messing, edward_messing@urmc.rochester.edu, (716) 275-3345

Note: This story has been adapted from a news release issued by University Of Rochester.

2002 New Method Speeds Up Discovery Of Materials

2007-09-14T23:49:00.001-07:00

New Method Speeds Up Discovery Of Materials

Science Daily — WEST LAFAYETTE, Ind. A new method promises to change how companies create materials using artificial intelligence and a technique that simultaneously tests thousands of formulations dramatically speeding up the discovery process.

Chemical engineers from Purdue University are using their method to discover new types of catalysts, compounds used extensively in numerous manufacturing processes. The same method also could be used for many types of materials research, said Jochen Lauterbach, an associate professor of chemical engineering.

Catalysts in American industry account for billions of dollars in annual business revenues. That means even small improvements in catalyst performance can result in significant increases in profits.

"If you have a reaction that runs a million pounds a year, a catalyst that is only 5 percent better makes a lot more money," Lauterbach said. "This approach will have a significant economic impact."

He will publicly discuss the research for the first time and unveil a commercial version of the new method Friday (1/25) during the 4th Annual International Symposium on Combinatorial Approaches for New Materials Discovery in San Diego, Calif. The conference is sponsored by the Knowledge Foundation Inc., an organization that provides an unbiased forum to showcase promising technologies through conferences and publications.

Lauterbach has developed an automated system that uses combinatorial chemistry, in which equipment systematically creates and tests thousands of chemical samples at the same time, or "in parallel." Thousands of tiny plastic beads about the width of a human hair are coated with different catalysts. All of the beads, each bearing its own individual catalyst, are tested simultaneously in the same experiment. Then the system uses a recently declassified infrared sensor technology to quickly screen each sample to evaluate its performance.

"We have the capability of making a hundred times more catalysts and screening them in the same amount of time that researchers previously needed to study one catalyst," Lauterbach said.

A small percentage of the catalysts created are effective. Information is collected from both the best catalysts and the failed catalysts and fed into software that mimics the logical and intuitive thought processes of chemists. Even though the majority of the catalysts created are not effective, the software uses the wealth of information gained from those failures to come up with entirely new catalysts.

"If a mixture doesn't work, the information about why it does not work is just as valuable as the information about why it does work," Lauterbach said. "We feed that information back into the software, and at some point we tell the program that we want a catalyst that does this and that. The software does its thing and it spits out a material combination, a range of completely new catalysts that nobody has ever thought of before, or had dared to even propose or synthesize because everybody would say, 'You've got to be crazy. This is never going to work.'

"It's something that is totally out of the box thinking for typical catalyst development."

Central to the method are two types of artificial intelligence software: hybrid neural networks and genetic algorithms. The software mimics the thought processes of chemists who create new formulas for everything from rubber compounds to rocket fuels, and plastic materials to snack foods, said James M. Caruthers, a professor of chemical engineering.

"There is this crazy-haired scientist, called a formulation chemist, who actually mixes dabs of this with dabs of that and stirs it up in a pot cooks it, more or less and makes new materials," Caruthers said. "You could say, 'Gee, these guys make this good stuff, and they are lucky.' Except that the people who are very good at it are lucky again and again and again, and they are actually some of the most valuable folks in an organization because they make the new materials.

"It's part science, it's part intuition."

The different types of software work together in a repeating two-phase cycle of discovery.

First, hybrid neural networks analyze the formulas of the numerous catalysts, or other materials, created by the parallel technique. The neural networks determine the properties of the materials, based on their chemical structures. In the second phase, genetic algorithms cull the best materials and eliminate the poor performers, just like survival of the fittest. The algorithms also generate "mutations" of the best materials to create even better versions, and the software determines the chemical structures of those mutations.

The resulting formulas are returned to the neural network software, and the cycle starts over again, progressively creating better and better materials, said Venkat Venkatasubramanian, a professor of chemical engineering who has been working with Caruthers to develop the software for more than a decade.

Caruthers said he observes how formulation chemists come up with new ideas. Then he models their trains of thought in software programs.

"Most experts don't think in terms of equations and mathematics," he said. "They think in terms of pictures. They have a picture of what goes in, and they have a picture of what comes out. What we should really be trying to do is model this sort of picture-to-picture reasoning that goes on.

"I look at eyes. I try to see when the eyes are excited, or a little confused or upset, and try to figure out what is the reasoning behind all of that. We want to learn why experts make the inferences that they do why they jump from here to here."

The software isn't quite as smart as the human formulation chemists. While software programs can't match the creative brain power of people, they can mimic human thinking while simultaneously computing thousands of formulations, compared to about half a dozen for a human chemist.

"No human mind could keep all these balls in the air at the same time," Caruthers said. "Our idea is to reproduce 60, 70, 80 percent of the way these formulation chemists think, but now the computer can balance all of these balls in the air at the same time."

Neural networks are designed to think more like the human brain than a conventional computer program. The Purdue approach differs from previous methods that have used neural networks because it first takes a reaction's physics and chemistry into account, and then it lets the software take over, determining the properties of the materials. Because it combines known physics and chemistry with the software, it is called a hybrid neural network.

"Other methods assume that you know nothing about the physics and the chemistry of a process," Venkatasubramanian said. "However, in most cases you know something about the physics and chemistry governing a reaction, but that knowledge is not complete enough.

"We see how far our fundamental understanding will take us, and then we use neural networks and statistics. That way, your model is built on certain fundamentals of physics and chemistry, so it's more robust and its ability to extrapolate will be more reliable than otherwise."

Eventually, findings that identify the best new materials are handed over to human chemists who conduct experiments to validate that the formulations function well in real-life situations.

Lauterbach, Caruthers and Venkatasubramanian are working with W. Nicholas Delgass, a professor of chemical engineering, and Kendall Thomson, an assistant professor of chemical engineering.

Each component of the method the software and the parallel screening technology are equally important, Venkatasubramanian said.

"You generate this huge amount of data," Venkatasubramanian said. "But the data are not going to be very useful unless you can make sense of it all, and that's where the computation and the modeling software come in."

The Purdue researchers are working with several companies interested in the method. In research with one company, engineers using the method took about 30 minutes to find a new material that would have taken three months with conventional techniques, Caruthers said.

"We have a number of strategic relationships with companies," Caruthers said. "We customize the software for specific applications because there is no single commercialized package that fits all uses."

Researchers will present specific experimental findings in March during an American Physical Society meeting in Indianapolis.

The research is being conducted through a new Center for Integrated Materials-To-Product Design, headed by Caruthers, which works with industry to speed the process of making products from newly discovered materials.

"As far as we can tell, this is the first and only center of its kind in the United States," said Venkatasubramanian, associate director of the new center. "There is no other place in a university environment that is taking this kind of perspective, going all the way from molecular level modeling to final property design and then having a center dedicated to this."

The center has received $1.4 million in seed funding from the 21st Century Research and Technology Fund, administered by the state of Indiana. The research also is funded by the National Science Foundation and private industry.

Note: This story has been adapted from a news release issued by Purdue University.

2004 Knowledge Discovery' Could Speed Creation Of New Products

2007-09-14T23:48:00.002-07:00

Knowledge Discovery' Could Speed Creation Of New Products

Science Daily — WEST LAFAYETTE, Ind. In the recent science-fiction thriller "Minority Report," Tom Cruise plays a detective who solves future crimes by being immersed in a "data cave," where he rapidly accesses all the relevant information about the identity, location and associates of the potential victim.

Purdue University graduate student Leif Delgass reviews chemical structures associated with points in a 3-D "scatter plot." The interactive graph is part of a system being developed at Purdue University that could dramatically speed up scientific discovery by enabling researchers to test hypotheses in real time using high-performance computing and artificial intelligence software. (Purdue News Service photo/David Umberger)

A team at Purdue University currently is developing a similar "data-rich" environment for scientific discovery that uses high-performance computing and artificial intelligence software to display information and interact with researchers in the language of their specific disciplines.

"If you were a chemist, you could walk right up to this display and move molecules and atoms around to see how the changes would affect a formulation or a material's properties," said James Caruthers, a professor of chemical engineering at Purdue.

The method represents a fundamental shift from more conventional techniques in computer-aided scientific discovery.

"Most current approaches to computer-aided discovery center on mining data in a process that assumes there is a nugget of gold that needs to be found in a sea of irrelevant information," Caruthers said. "This data-mining approach is appropriate for some scientific discovery problems, but scientific understanding often proceeds through a different method, a 'knowledge discovery' approach.

"Instead of mining for a nugget of gold, knowledge discovery is more like sifting through a warehouse filled with small gears, levers, etc., none of which is particularly valuable by itself. After appropriate assembly, however, a Rolex watch emerges from the disparate parts."

A team of researchers at Purdue led by Caruthers is developing a computer environment that allows experts to talk naturally in their specific scientific language. That way, the researchers don't have to deal with computerese and can take full advantage of the most advanced visualization capabilities to become more engaged in the scientific discovery process, Caruthers said.

Such a system could become crucial for enabling scientists to deal with the recent explosion of data now available to them. The source of this flood of data is "high-throughput" experimentation, in which hundreds or thousands of experiments are conducted simultaneously in tiny vessels that are sometimes as small as a few human hairs. Having so much information presents a challenge: it is difficult for researchers to find what they are looking for within this huge sea of data.

"You run the risk of drowning in data," said W. Nicholas Delgass, a Purdue professor of chemical engineering. "What you really want is knowledge, not data."

Purdue researchers believe they have a solution to the problem. They are developing a method to extract knowledge from data, promising to speed up the process of discovery in many areas of research, including work aimed at creating new drugs, fuel additives, catalysts and rubber compounds.

The method, called "discovery informatics," enables researchers to test new theories on the fly and literally see how well their concepts might work in real time via a three-dimensional display, said Venkat Venkatasubramanian, another professor of chemical engineering working to develop the new system.

The multidisciplinary effort involves researchers from Purdue's College of Engineering, School of Science, School of Technology, Information Technology at Purdue, or ITaP, and the e-Enterprise Center in Purdue's Discovery Park, a collection of six centers formed to speed the development of new technologies.

Discovery informatics depends on a two-part repeating cycle made up of a "forward model" and an "inverse process" and two types of artificial intelligence software: hybrid neural networks and genetic algorithms.

The forward model combines fundamental knowledge and rules of thumb with neural networks software that mimics how the human brain thinks to tell researchers how a particular material will perform.

"In the forward model, a researcher postulates a molecular structure or a product's formulation and then wants to predict what properties that structure or formulation will have," Delgass said.

The inverse process is just the opposite: Researchers enter the properties they are looking for, and the system gives them a molecular structure or formulation that will likely have those properties. The inverse process cannot begin until the forward model is completed because the former depends on information in the model.

"What we are talking about is an advanced method for product design," said Venkatasubramanian. "The product design problem is this: I want some material that would have the following mechanical, chemical, electrical properties and so on.

"I know what properties I want in order to get my job done, but I don't know what material, what molecular combinations, will give me that. It is a bit like 'Jeopardy.' You know the answer, but you are looking for the question."

The inverse process may use genetic algorithms, software programs that mimic the Darwinian survival-of-the-fittest evolutionary approach to find the best candidates. The algorithms cull the best materials and eliminate the poor performers, just like survival of the fittest, generating "mutations" of the best materials to create even better versions over time, and the software determines the chemical structures of those mutations.

The resulting formulas are tested and used to improve the forward model, and the cycle starts over again, progressively creating better and better solutions.

"Once we have the forward model, we use it to predict which possibilities are going to be good," Delgass said. "Many of them turn out to be bad, but all of the negative information essentially tells me that the model has a flaw because it initially said these were good possibilities, and they weren't.

"Now that I have an opportunity to fix the model, I have a repeating way of making the model better and better."

The cycle might be called a "forward-inverse loop," a method for creating mathematical models that are critical to the discovery process.

"Before you can create one of these models, you typically spend years discovering the fundamental scientific principles behind the problem," Caruthers said. "We want to drastically speed up that discovery process, so that it no longer takes years to create models for important industrial products and processes."

Before high-throughput experimentation, researchers were able to keep up with the amount of available data.

"It's a little bit like horse-and-buggy transportation 100 years ago in this country," said Venkatasubramanian. "The horse and buggy did 10 miles per hour, and your country road supported 10 miles per hour, so everyone was happy. But suddenly now you can produce a month's worth of data in a matter of hours via high-throughput experiments. It's like having a Ferrari on a country road. You can do 200 miles per hour, but you are still stuck driving on the country road.

"Now we need an interstate, a modeling superhighway."

Discovery informatics, which has numerous potential applications, is that modeling superhighway.

"The opportunities are enormous for engineers who work in product design, which is now largely done as an art form by formulation chemists," Caruthers said. "We want to retain the creative aspects that can only come from the human mind, while reducing the amount of guesswork now needed to create new catalysts and other materials.

"Researchers generally discover with an Edisonian, guess-and-test approach. Lots of intuition. Lots of experience. Lots of gray hair. And a little bit of luck. But that cycle is too long, too expensive."

With conventional methods, it might take several years and thousands of tests before hitting on the right formulation, whereas discovery informatics dramatically speeds up the process by using a computer to sample potential materials and requires a fraction of the usual number of laboratory experiments.

The method will be tested in a new Center for Catalyst Design headed by Delgass and funded with a three-year, $2.4 million grant from the U.S. Department of Energy and $1.7 million from the Indiana 21st Century Research and Technology Fund, established by the state to promote high-tech research and to help commercialize university innovations.

Catalysts in American industry account for billions of dollars in annual business revenues. That means even small improvements in catalyst performance can result in significant increases in profits, Delgass said.

Discovery informatics uses the scientific method to enable researchers to test new theories and hypotheses.

"In the scientific method, you make a hypothesis, you see whether the hypothesis fits the data it never does the first time," Caruthers said. "You then revise your hypothesis and test it back against the data. It's a little better, but it isn't right. You do it again, and you do it again, and eventually you get to where your data and your hypothesis match, and you say, 'Now I have knowledge.'"

Researchers in Purdue's e-Enterprise Center helped the chemical engineers create software prototypes needed to manage huge amounts of data and simulations, turning the information into interactive images, said Joseph Pekny, director of the e-Enterprise Center and a professor of chemical engineering.

Then information technology experts use supercomputers to run the complex software for applications such as predicting chemical reactions and then "visualizing" such data on a three-dimensional, 12-foot-wide, 7-foot-high display in the Envision Center, said Gary Bertoline, associate vice president for discovery resources at ITaP and a professor of computer graphics technology in Purdue's School of Technology.

"We are helping them look at large amounts of data all at the same time," said Laura Arns, a visualization and computer graphics application engineer at ITaP. "You can display information in stereo, in which the left and the right eye each get their own pictures, and you get a 3-D depth effect. To see the 3-D visualization, you wear special glasses that are like sun glasses."

A large 3-D high-resolution display, known as a tiled wall, allows researchers to look at an entire problem, including chemical and atomic structures, graphs and charts.

"You are no longer limited to the size of a computer screen," Caruthers said. "You now have a huge field of view."

Caruthers likens the display to the concept moviegoers saw in "Minority Report."

"We're almost there," Caruthers said. "We will soon have a sophisticated tool that shows researchers in real time whether a particular idea is on the right track."

The method allows scientists and engineers to take full advantage of human creativity.

"Discovery requires human beings making intuitive leaps," Caruthers said. "You try one thing. It doesn't work, you try something else. Sometimes you go off in an entirely new direction.

"But this process is very inefficient. What we are doing is enhancing the efficiency of this process, assisting the intuitive human mind by providing massive data and computing power."

The three engineers presented a paper about their method in July during an international conference, Foundations of Computer-Aided Process Design, at Princeton University. Purdue held a workshop on Sept 13 and 14 focusing on methods of visualizing and manipulating data for the design of new catalysts for chemical reactions. The workshop attracted representatives from national laboratories, industry, academia and the U.S. Department of Energy.

Work to develop the method began in 1988 with funding from the National Science Foundation. Further research has been funded by Lubrizol Co., the Indiana 21st Century Research and Technology Fund and Caterpillar Inc.

Note: This story has been adapted from a news release issued by Purdue University.

2007 Engineers prolong satellite life

2007-09-14T23:48:00.001-07:00

Engineers prolong satellite life

WEST LAFAYETTE, Ind., Sept. 6 (UPI) -- U.S. scientists have developed a new technique, involving maximizing the device's fuel stores, to extend the life of aging satellites.

Purdue University and Lockheed Martin Corp. researchers said their technique involves equalizing the amount of propellant left in a satellite's fuel tanks, allowing the satellite to consume all of its fuel before being retired from service.

That technique has saved $60 million for broadcasters by extending the service life of two communications satellites that would otherwise have been shut down.

Communications satellites are maintained in orbit about 22,500 miles above Earth by using small rocket thrusters. But the satellites must be replaced shortly before they run out of fuel to make sure they can be moved to make room for their replacements.

Although modern satellites generally have a single fuel tank, it was common years ago to design satellites with more than one tank, the researchers said. Consequently, there are many aging satellites in orbit that could benefit from the new newly developed technology.

The research was detailed in a paper in the Journal of Spacecraft and Rockets.

2002 Fractals Help UCLA Researchers Design Antennas For New Wireless Devices

2007-09-14T23:47:00.001-07:00

Fractals Help UCLA Researchers Design Antennas For New Wireless Devices

Science Daily — Antennas for the next generation of cellphones and other wireless communications devices may bear a striking resemblance to the Santa Monica Mountains or possibly the California coastline.

That is because UCLA researchers are using fractals -- mathematical models of mountains, trees and coastlines -- to develop antennas that meet the challenging requirements presented by the more sophisticated technology in new cellphones, automobiles and mobile communications devices. These antennas must be miniature and they must be able to operate at different frequencies, simultaneously.

"Manufacturers of wireless equipment, and particularly those in the automotive industry, are interested in developing a single, compact antenna that can perform all the functions necessary to operate AM and FM radios, cellular communications and navigation systems," said Yahya Rahmat-Samii.

Rahmat-Samii, who chairs the electrical engineering department at UCLA's Henry Samueli School of Engineering and Applied Science, leads the research in this area. His findings were reported in a recent issue of the Institute of Electrical and Electronics Engineers' Antennas and Propagation Magazine.

Fractals, short for "fractional dimension," are mathematical models originally used to measure jagged contours such as coastlines. Like a mountain range whose profile appears equally craggy when observed from both far and near, fractals are used to define curves and surfaces, independent of their scale. Any portion of the curve, when enlarged, appears identical to the whole curve -- a property known as "self-symmetry."

Rahmat-Samii found the mathematical principles behind the repetition of these geometrical structures with similar shapes could be applied to a methodology for developing antenna designs.

Using this method, he has developed antennas that meet two important challenges presented by the new generation of wireless devices. They conserve space and can operate simultaneously at several different frequencies.

His fractal methodology allows Rahmat-Samii to pack more electrical length into smaller spaces, he said. Increased electrical length means the antennas can resonate at lower frequencies.

Because fractal designs are self-symmetrical (repeat themselves), they are effective in developing antennas that operate at several different frequencies. "One portion of the antenna can resonate at one frequency while another portion resonates at another frequency," Rahmat-Samii said.

UCLA, where much of the early research on internal antennas was conducted in the mid 1990s, is today "one of the leading research institutions exploring the use of fractals in developing antenna design," Rahmat-Samii said.

The subject of fractals came into vogue during the last decade as new-age gurus claimed fractals were capable of all manner of feats. Serious use in engineering, however, has developed over the last five years, Rahmat-Samii said.

This is not the first time Rahmat-Samii has borrowed from other disciplines. He has experimented with using "genetic algorithms" -- the Darwinian notion of natural selection and evolution -- as a means of developing alternative antenna designs. In keeping with the evolutionary model, a computer program "mates" various antenna components to produce new designs. Just as nature does, the algorithm selects the "fittest" design. The process is complete when it has produced a design that meets the experimenter's objectives.

Although the method produces unanticipated results, it also provides few clues about the next iteration of the design, Rahmat-Samii said. Using fractals, however, makes the process more predictable, giving researchers more control over the results.

Note: This story has been adapted from a news release issued by University Of California - Los Angeles.

2004 Fast cars could be tuned by evolution

2007-09-14T23:45:00.001-07:00

Fast cars could be tuned by evolution

16:03 18 June 2004
Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues
Will

Can evolutionary theory help rival Formula 1 teams break Michael Schumacher's seemingly unassailable hold on top-flight motor racing? Computer scientists at University College London think it might.

Peter Bentley and Krzysztof Wloch have used genetic algorithms software that mimics evolution's drive for fitness to breed the best tuning configurations for racing cars.

Using the technique, they shaved a second off the best time achieved by an expert. They will present their results at a conference on evolutionary systems in Seattle next week.

Genetic algorithms mimic the principles of evolution to breed solutions to a problem. A population of potential solutions is tested for fitness and the best are cross-bred and mutated. The unfit members of the next generation are weeded out, simulating natural selection, leaving the fittest solutions to go on to breed.

Unfortunately Bentley and Wloch did not have any real cars to hand, so instead they applied their algorithm to virtual cars in the PC game Formula One Challenge.

This lets players set 68 variables governing the car's performance, including factors such as rev limits, gear ratios, tyre pressures and suspension damping. They say there is no reason why the same principle could not be applied trackside at Formula 1 races.

Track records

The team started with a population of randomly chosen tuning configurations, each of which was tested on two virtual tracks.

Recombination and mutation of the best 40 per cent were then used to come up with the next generation, some of which were faster still around the track. Eventually their system evolved configurations that consistently broke track records.

Bentley claims the technique would work even better if it were fed real-time performance telemetry from cars during a race. Genetic algorithms running in trackside computers could then be used to fine-tune the settings of a car during pit stops.

It could happen. UK software firm Yearstretch of Purley, Surrey, is already developing a similar technique for motor sports such as touring-car racing.

Pit-stop strategies

"We expect it to offer a gain in automatic set-up much as the UCL research suggests is possible," the firm's spokesman Paul Weighell says.

Genetic algorithms are already used in F1 to develop pit-stop strategies and design components. "F1 will no doubt use more GAs every year," Weighell says.

But John Nixon, a motor sport design expert at Cranfield University in the UK, warns that a car whose performance is based on evolved tuning parameters has limitations. "All of these things are based on assumptions," he says. "One crash that puts oil on a corner can throw all of them out."

Weblinks

2005 New photofit 'evolves' a suspect's face

2007-09-14T23:44:00.001-07:00

New photofit 'evolves' a suspect's face

10:00 19 March 2005
Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues.
Paul Marks

Enlarge image

Rather than piece a likeness together - as in a conventional E-Fit (left) - the Evo-Fit evolves a likeness in a series full-face stages (Image: ABM UK Ltd)

Half an hour after being mugged, the victim is again staring her attacker in the face. But the assailant has not returned. What the victim is looking at is an image on a police laptop running software that can "evolve" a realistic likeness within minutes, while her memory is still fresh.

This novel photofit system was unveiled in London, UK, last week at a conference on crime-fighting technology. The computerised photofit systems police now use store hundreds of variations of facial features, such as eyes, noses and chins, in a database.

A police officer interviews the witness and attempts to piece together a likeness. "They will look through a gallery of about 150 eyes and put the right ones, pastiche fashion, into a face. But witnesses find this a bit overwhelming," says Chris Solomon of the University of Kent in the UK. The procedure can take hours and the resulting composite is not very lifelike.

So Solomon's team, and Peter Hancock and Charlie Frowd at the University of Stirling in Scotland, are working independently on better ways to produce photofits using genetic algorithms. Engineers often use this type of software to come up with optimal designs for, say, Formula 1 cars, or the perfect mixture for an alloy. A genetic algorithm takes possible solutions to a problem and repeatedly "evolves" them until it finds the one that works best.

Face mutation

Kent's EigenFit software and Stirling's EvoFit package work in similar ways. Based on the sex, race and hairstyle of the person the witness remembers, the computer produces nine random faces, from which the witness chooses the one that seems the closest likeness. The algorithm then uses this face to mutate a new set of variants.

The cycle continues until the witness is happy with the likeness. Each generation can be calculated in seconds, making the process far quicker than retrieving facial features from databases and trying them one by one.

But just what is being evolved? Each face is represented by an array of 50 numbers called principal components. "If we change just one of these parameters it alters the face, albeit rather subtly," Solomon says. "It might make the skin a bit darker, more wrinkly, or move the nose up the face a bit." Once a feature, say the mouth, is correct it can be "locked", and the rest of the face evolved around it.

In early tests, volunteers were about twice as likely to recognise a face constructed through the algorithm-based software as through today's photofit mugshots, Solomon says. And when police in Northampton asked a victim of a crime to construct an image with EvoFit, "she was astounded at the quality of the likeness to her attacker", senior investigating officer Paul Spick told New Scientist. "The holistic way it produces a whole face is very impressive."

Unusual suspects
http://www.newscientist.com/article.ns?id=mg18424676.100
02 October 2004
Fast cars could be tuned by evolution
http://www.newscientist.com/article.ns?id=dn6019
18 June 2004
Animation lets murder victims have final say
http://www.newscientist.com/article.ns?id=dn4005
04 August 2003

Weblinks

2007 Eel feel helps wave power go with the flow

2007-09-14T23:43:00.001-07:00

Eel feel helps wave power go with the flow

16 April 2007
Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues
Paul

The simulated mutant fish slithers through the water, wriggling faster as it detects a change in the sea conditions (3MB .MPG video). It may sound like some Hollywood special effect, but the idea behind this fish is in fact to squeeze more energy out of wave power.

Leena Patel and her colleagues at the University of Edinburgh in the UK are using a genetic algorithm computer program, which mimics the way natural selection breeds fitter creatures, to improve the way their virtual lamprey swims in different sea conditions. They want to use these swimming motions to boost the efficiency of a novel type of wave-power device - a long, thin, eel-like machine called the Pelamis.

Made by Ocean Power Delivery of Edinburgh, the 140-metre-long Pelamis consists of four floating tubular segments (New Scientist, 20 September 2003, p 33). As the waves flex the segments (3.14MB .avi video, divx or xvid codec required), hydraulic rams inside them move in and out of power converters in the joints between the segments, generating up to 750 kilowatts of electricity. Three Pelamis machines are already generating power at a site off Portugal, while four will begin operating in the Orkney islands of northern Scotland in 2008.

However, oscillating machines like this cannot adapt when the wave speed changes. "So they operate at less than optimum efficiency," says Patel. To overcome this, she turned to the lamprey, which uses skin sensors to adjust its swimming motion as the current changes. Lampreys have a cluster of neurons in their spinal cord called a central pattern generator (CPG), which produce signals that drive the muscles to contract rhythmically and make them swim (Neurocomputing, vol 70, p 1139).

Patel took a computer model of a lamprey CPG and applied a genetic algorithm to mutate its connections repeatedly to see if she could "breed" successively better swimming motions under different conditions. This greatly extended the lamprey's repertoire of swimming patterns, and made it wriggle at up to 12.7 times per second, compared with just 1.7 times a second previously.

Initial simulations show that altering the flexibility of Pelamis's joints in line with these fitter swimming patterns could improve energy capture under different wave conditions, Patel says. The principles could be applied to any bobbing wave-power generator, she adds.

Max Carcas, a director of Ocean Power Delivery, thinks the idea may hold promise, but he says the company's own engineers are also working to improve the device's efficiency.

Peter Bentley, a computer scientist at University College London, says the work shows how much genetic algorithms have become accepted in engineering.

From issue 2599 of New Scientist magazine, 16 April 2007, page 28

2005 Robotic modelling reveals ancient hominid stride

2007-09-14T23:42:00.002-07:00

Robotic modelling reveals ancient hominid stride

12:07 21 July 2005
NewScientist.com news service
Will

An ancient human ancestor once thought to have shuffled its way across the plains of Africa in fact walked upright much like modern man, a study of robotic models has revealed.

UK researchers built robot-based computer models of Australopithecus afarensis - a human ancestor that lived more than three million years ago.

They constructed the computer model using a fossilised A. afarensis skeleton known as "Lucy", recovered from Ethiopia in 1974. The researchers then added virtual muscle to their simulation and used genetic algorithms to "evolve" the optimal walking movement for the creature.

"We compared the model’s speed and stride length with that of modern humans," says team member Weigie Wang at the University of Dundee. "We conclude that they definitely would have walked bipedally."

The researchers also found that the model of locomotion produced in their simulations closely matched a set of fossilised footprints thought to have been left by A. afarensis in Laetoli, Tanzania, some 3.6 million years ago.

Darwinian code

Genetic algorithms employ the principles of Darwinian evolution to come up with an optimised - or "evolved" - solution to a problem. A population of algorithms is tested and the most effective selected for survival, while the least successful are killed off.

The surviving algorithms are then recombined and mutated and tested again. Over thousands of simulated generations, the population becomes well adapted to tackling the problem at hand. The approach has proven its worth in many fields, such as automated product design and computer network topologies.

The algorithms used to evolve the A. afarensis walking style corresponded to different configurations of muscle mass, length and positions on the bone. These were tested for energy efficiency in walking-motion simulations on the computer.

"This is interesting work," says Chris Stringer, an expert in paleoanthropology at the Natural History Museum in London, UK. "It brings in more information about the skeleton of A. afarensis."

But Stringer notes that some uncertainty remains over precisely which species of hominid created the Laetoli footprints. For example, some researchers have proposed that afarensis-like remains discovered in Kenya in 1999 – similar in age to “Lucy” – be classified as a separate species, called Kenyanthropus. "One of the unknowns at this time is species diversity," Stringer told New Scientist.

Journal reference: Journal of the Royal Society Interface (DOI: 10.1098/rsif.2005.0060)

Early toolmakers cast off rock-banger image
http://www.newscientist.com/article.ns?id=dn7248
10 April 2005
World's oldest biped skeleton unearthed
http://www.newscientist.com/article.ns?id=dn7102
07 March 2005
Taste for meat made humans early weaners
http://www.newscientist.com/article.ns?id=dn6921
29 January 2005

Weblinks

2004 Organised chaos gets robots going

2007-09-14T23:42:00.001-07:00

Organised chaos gets robots going

09:45 01 November 2004
Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues
Will Knight

Enlarge image

Chaos in control

A control system based on chaos has made a simulated, multi-legged robot walk successfully. The researchers behind the feat say it may have brought us closer to understanding how people and animals learn to move.

Standard robots control their leg motion either through complex computer programs or by using so-called genetic algorithms to “evolve” a successful walking strategy. Both these options are time-consuming and require a lot of computer power.

Roboticists Yasuo Kuniyoshi and Shinsuke Suzuki wondered whether chaotic systems might also generate efficient walking behaviour. Chaotic systems behave in a way that means that small effects are amplified so rapidly that the systems’ behaviour becomes impossible to predict more than a short time ahead. Such chaotic systems are behind a number of phenomena, including the weather and the performance of financial markets.

The Tokyo University pair reasoned that just as the chaotic maths that determines the weather can produce clear patterns such as hurricanes and weather fronts, similar systems might underlie the movement patterns involved in locomotion. “We, and animals, seem to be able to work out how to move in different situations without going through thousands of trial-and-error situations like today’s robot-control software does,” says Kuniyoshi.

To test their idea, Kuniyoshi and Suzuki devised a computer simulation of a 12-legged machine in which each leg was controlled by a chaotic mathematical function. The functions were initially fed 12 parameters chosen at random. From then on, sensory information from each limb was fed back into the chaotic function that controlled it.

Going nowhere

The team found that certain combinations of starting parameters made the robot’s limbs rapidly adopt “walking-on-the-spot” behaviour, but the machine did not get anywhere. However, when they placed a weight at one end of the simulated robot (see graphic) they found that four of the legs seized up, allowing the front and back legs to dominate movement and let the robot scamper along.

The robot could also negotiate obstacles in its path. After scuttling about for a few seconds, its mode of locomotion would change to allow it to scramble over whatever was in the way. Although it was just a simulation, the software mimicked the robot’s performance in fine detail. Kuniyoshi is confident that the trick will work in a real robot.

Remarkably, the robot performed these tricks without any conventional programming. And its behaviour emerged far more quickly than it would if it had used genetic algorithms. Kuniyoshi suggests that his chaotic approach may have similarities to the way that biological systems learn to move.

“Many findings point to the presence of chaotic patterns in general in the human brain,” says Max Lungarella, who researches artificial intelligence at the University of Tokyo. But Kuniyoshi and Suzuki’s approach is still unconventional, he says. “It diverges radically from the traditional way of thinking about intelligence.”

Roberto Fernández Galán, a biophysicist at Carnegie Mellon University in Pittsburgh, Pennsylvania, also finds the approach intriguing, but he is sceptical about the Japanese team’s idea that chaos plays a role in animal locomotion. “It is surprising to achieve what they call goal-directedness with a chaotic robot,” he says.

Walking robot carries a person
http://technology.newscientist.com/article/dn4409
21 November 2003
Nine eyes help robots to navigate
http://technology.newscientist.com/article/dn4322
30 October 2003
Robot spy can survive battlefield damage
http://technology.newscientist.com/article/dn4075
20 August 2003

Weblinks

1994 may the fittest car win the race

2007-09-14T23:40:00.001-07:00

may the fittest car win the race

19 June 2004
Will Knight
Magazine issue 2452

CAN evolutionary theory help rival Formula 1 teams break Michael Schumacher's seemingly unassailable hold on top-flight motor racing? Computer scientists at University College London think it might.

Peter Bentley and Krzysztof Wloch have used genetic algorithms - software that mimics evolution's drive for fitness - to breed the best tuning configurations for racing cars. Using the technique, they shaved a second off the best time achieved by an expert. They will present their results at a conference on evolutionary systems in Seattle next week.

Unfortunately Bentley and Wloch didn't have any real cars to hand, so instead they applied ...

The complete article is 458 words long.

1993 Top marks for timetables in the generation game

2007-09-14T23:39:00.002-07:00

Top marks for timetables in the generation game

26 June 1993
From New Scientist Print Edition. Subscribe and get 4 free issues.
ELISABETH

Here is an examination question. How long does it take a university lecturer to devise an exam timetable for 90 students who can choose 8 papers from more than 60 being offered? All the exams must take place within seven days, there must be no clashes, and as few students as possible should have to sit two papers consecutively or more than two per day.

At the University of Edinburgh's artificial intelligence department the answer used to be: up to seven weeks. But now a computer program has done the job, cutting the time to one minute. And in the timetable that it drew up for this term, no student had to sit consecutive 90-minute exams - a significant improvement on the past two years.

Designed by David Corme, a research assistant, the timetabling program uses a 'genetic' algorithm. It makes up 100 random timetables, and divides them into 50 pairs which 'mate' with each other. Every pair produces two 'offspring' which take their characteristics from their parents. Each second-generation timetable is then assigned a score depending on how well it fits the timetabling conditions. This is rather like measuring how successful a living organism is at finding food.

The program next mates 50 pairs from the second generation. The probability of a particular timetable being chosen depends on its score, so the best could be selected several times. An especially good timetable might even mate with itself - in which case it would produce unchanged offspring. After several generations, the offspring converge on the best solution.

Corme believes there are many important areas where genetic algorithms could improve scheduling. For airlines, railways and coach operators, vehicles and their crews need to be in the right place at the right time. Such algorithms could also help to schedule jobs in engineering workshops.

Working with research student Hsiao-Lan Fang, Corme devised a simple code to represent the exam timetable. For example 3,7,11,2,7 represents the timetable in which exam 1 occupies the third time slot, exam 2 the seventh slot, exam 3 the eleventh slot and so on. In this example, exams 2 and 5 clash because they are both allocated to the seventh slot. Scoring is by penalties, with a large penalty for a clash and a smaller one if any student has to sit papers consecutively.

When the parent 3,7,11,2,7 is mated with another parent, such as 1,2,3,4,5, the digits or 'genes' are swapped about to generate the two children. This can be done in many different ways, such as swapping the first three and the last two to give 1,2,3,2,7 and 3,7,11,4,5. 'You then have to evaluate each of the offspring,' says Corme. 'You almost certainly find a better set of timetables and (eventually) you evolve one which is optimum.' Poor timetables are not removed from the population: 'You don't discard anything, just give it a lower chance of reproduction,' he says.

The program was tried out on the 1991 and 1992 timetables, which had been set manually. In 1991 the manual timetable produced 15 instances of students sitting consecutive exams: in the computer program, this scored 37 penalty points. The genetic algorithm produced a timetable that scored a perfect 0. In 1992, when there were more students, the manual timetable had 29 consecutive exams and two cases of three exams in a single day - a disappointing score of 101. The final genetic algorithm scored 3, representing just one student sitting consecutive papers.

This summer, with still more students, the course organiser did not even try to produce a timetable manually but handed over the task to the algorithm, which produced another perfect timetable. The department is now considering setting its lecture timetable by computer. Corme says that all you have to do to try the program on another problem is to think up the right notation to represent the problem and the right scoring system.

From issue 1879 of New Scientist magazine, 26 June 1993, page 19

2003 Humans and computers compete in virtual creature game

2007-09-14T23:39:00.001-07:00

Humans and computers compete in virtual creature game

17:00 05 December 2003
NewScientist.com news service
Will

An online game that lets contestants build and race virtual beasts is being used to pit humans against a variety of artificial intelligence algorithms.

The objective of Sodarace, which started at the end of November, is to construct a two dimensional creature that can travel over a certain type of terrain in the shortest possible time.

Each creature is constructed of "mass", muscles", "limbs" and "joints" which control the way it moves. These creations can then be raced over a piece of terrain. Creatures can have many limbs or none at all and can walk, wriggle or even jump along.

It is relatively simple to construct a creature by hand. But the game has been written so that a creature's key parameters can easily be fed into another computer program and artificial intelligence (AI) programmers are being invited to take part.

So far, Sodarace has attracted thousands of contestants from around the world. These include hobbyists and professional AI researchers. In the first round, a human player was able to outwit competing computer algorithms to develop the fastest creature.

'Offspring' algorithms

Peter McOwen, an AI expert at the University of London who helped organise the project, says the game provides useful way of comparing different AI approaches. "If you have an AI algorithm, you want to know how good it is at a known problem" he told New Scientist. "This is a fun way to show that your algorithm is better than someone else's."

McOwen's group is using genetic algorithms to "evolve" the fastest artificial creature. This involves creating a population of algorithms that compete with one another to make the best animal. The algorithms that work best are combined to create "offspring" algorithms that also compete.

Other research groups are using entirely different AI approaches. For example some involve neural networks - systems which simulate neurons in the human brain to tackle a problem. Other AI programs use or a process known as "simulated annealing" which whittles down strategies to find the optimal solution using the least effort.

The project was organised by University of London with a UK-based multimedia design company called Soda.

Gladiator-style 'wars' select out weak programs
http://www.newscientist.com/article.ns?id=dn3922
12 July 2003
Software gambler takes on the tipsters
http://www.newscientist.com/article.ns?id=dn3172
11 December 2002
'Animals' grown from an artificial embryo
http://www.newscientist.com/article.ns?id=dn2701
23 August 2002

Weblinks

1991 Will computers hold key to mental hospitals?

2007-09-14T23:38:00.001-07:00

Will computers hold key to mental hospitals?

02 November 1991
From New Scientist Print Edition. Subscribe and get 4 free issues.
CLIVE

Panels of experts which must decide whether to release potentially dangerous psychiatric patients from custody may in future seek advice from a computer. The Dangerous Assessment Database is a computer program which seeks to predict the likelihood that a released patient will be a danger to society.

Offenders in special psychiatric hospitals are considered for release by a panel of assessors which can include judges, psychiatrists, psychologists and nurses. Recent well-publicised cases of people being attacked by patients shortly after their release, such as that of Emma Brodie, highlight the weaknesses in the present procedures.

Eleven-year-old Emma Brodie was stabbed to death in April by Carol Ann Barrett, a complete stranger, in a shopping centre in Doncaster. Two days earlier Barrett had been released from the psychiatric unit of Doncaster Royal Infirmary.

At the same time, the judgments often err on the side of caution. For every genuinely dangerous person released, research suggests three individuals are kept locked up when they may be safe to discharge.

Ian Stringer, a psychologist who has worked for many years with dangerous offenders at the Rampton Special Hospital in Nottinghamshire and other institutions, developed the system in collaboration with a company called Risk Decisions. The company makes software for risk management in oil exploration and finance.

The system takes the form of a questionnaire program consisting of a about 1000 questions. By quizzing assessors the program gathers detailed information about the individual covering areas such as family background, childhood behaviour, and response to therapy. The information is weighted for reliability on a scale from hearsay, at the low end, to official reports where there have been attempts to corroborate evidence.

In addition, the program gathers information about the assessors themselves in an attempt to bring to the surface any underlying factors which might influence their judgment. 'People making judgments view information in different lights according to their training, their experience, their belief systems, and the contextual issues surrounding the case,' says Stringer.

The answers to the questionnaire are fed into the database. The risk analysis program uses a technique known as genetic algorithms, which mimics the process of evolution to find solutions to complex problems. Normal computer algorithms - the sets of instructions computers follow to solve a problem - are inadequate to tackle complex issues such as dangerousness because of the number of factors involved. Genetic algorithms do not seek exact solutions but aim instead for a 'best result'.

The best result is achieved by starting out with a 'population' of facts about the offender's life, such as a history of antisocial behaviour as a child. These are derived from the assessors' replies to the questions and only those facts which appear consistent between various assessors are included. The facts are also given a score depending on their importance and reliability.

These facts are represented as strings of numbers and are distributed randomly in a hypothetical array analogous to a population of living cells. The population then 'evolves' through a number of 'generations', following rules which define a fact's interactions with its neighbours and whether a fact replicates, simply survives or becomes extinct - only the fittest facts survive. Facts can undergo random changes analogous to genetic mutation and can also 'breed' with neighbouring facts by splitting in half and swapping over half its string of numbers.

After a number of generations a small selection of the most important facts will emerge. Stringer believes that the patterns of facts will 'help us make qualified decisions on the likelihood of dangerousness and what sort of situation is likely to increase dangerousness in an individual.'

The project is now beginning to collect data and systems are being installed in a number of institutions. Clive Hollin, senior lecturer in psychology at Birmingham University and research psychologist at the Glenthorpe Youth Treatment Centre, says that a computer system that gathered information relevant to a decision in an orderly way with weightings for different indicators 'might ease the process of coming to a decision'.

While it is 'science fiction' to think that a computer system could accurately predict human behaviour, Hollin thinks empirical research could show that the database 'may increase the accuracy of decision making - and that's valuable in itself.'

From issue 1793 of New Scientist magazine, 02 November 1991, page 22

1992 Why sales reps pose a hard problem

2007-09-14T23:37:00.002-07:00

Why sales reps pose a hard problem: What is the shortest route for travelling sales reps to visit all their clients? Mathematicians had hoped to find a complete solution, but they may have to settle for less

12 December 1992
From New Scientist Print Edition. Subscribe and get 4 free issues.
ARTURO

What do a manufacturer of printed circuit boards, a scientist studying the structure of crystals and a sales representative have in common? The scientist has to move the crystal into thousands of different orientations to measure the intensity of X-ray diffraction. The manufacturer has to move a drill around the board to make thousands of holes. And the sales rep has to visit scores of cities. If they want to do these things in the most economical way, all three have to solve a puzzle known to mathematicians as the travelling salesman problem.

The problem first appeared in the US during the 1930s in the newly born discipline - later called operations research - which uses mathematical analysis to solve problems of optimisation. The original version is about a sales rep who has to visit a number of cities. If the rep begins at one city and visits each of the others once before returning to the starting point, in which order should the cities be visited so that the total distance travelled is as short as possible? In the manufacture of a circuit board, the cities represent the holes to be drilled. In measuring X-ray diffraction, the cities correspond to the orientations of the crystal, and the distances correspond to the times needed to reposition the diffractometer between two measurements.

The problem may be simple to pose but it has turned out to be very difficult to solve. Despite the efforts of several generations of mathematicians and computer scientists, no one has found a complete solution. The distinction between a theoretical and a practical solution is crucial here, as is the difference between solving the whole problem and solving an instance of the problem. For example, Figure 1 depicts the shortest tour of 535 airports around the world, showing that this particular instance of the problem has been solved. But to solve the problem as a whole, one has to specify a method that will lead to the solution of every possible instance. And to be practical, it has to be solvable in a reasonable time.

How about adding the city-to-city distances for each possible tour and then picking the tour with the smallest length? This method will do when there are only a few cities, but it quickly becomes useless as the number of cities increases. With 30 cities, for example, the number of possible tours is approximately 2 x 10 32 (2 followed by 32 zeros, but the exact number is 30 x 29 x 28 . . . 2 x 1) and an exhaustive case-by-case search for the shortest tour would, in practice, be impossible to carry out. Even on a supercomputer, the calculation would take a thousand times the estimated age of the Universe.

So the challenge is to construct an explicit set of step-by-step procedures, an algorithm, that will always give an answer for however many cities are specified. And it has to be 'efficient' - meaning that there must be a reasonable relationship between the number of cities and the time the computer takes to find a solution to the problem.

In 1954, three mathematicians at Rand Corporation in Santa Monica, California, solved the first large-scale travelling salesman problem. George Dantzig, Delbert Fulkerson and Selmer Johnson applied techniques and algorithms borrowed from the new discipline of linear programming - a technique of mathematical modelling used to help in making quantitative decisions. The Rand mathematicians represented each possible tour of 49 real cities (Washington DC and 48 other large American cities) as a different vertex of a multidimensional polygon. Then the problem of finding the shortest tour became that of finding the vertex where a linear function (the 'tour length' function) reaches its minimum value.

Into four-figure problems

Building on this initial success, other mathematicians developed improved algorithms for the travelling salesman problem. In 1980, Manfred Padberg of the Leonard N. Stern School of Business at New York University and Harlan Crowder of IBM's Thomas J. Watson Research Center in Yorktown Heights, New York, employed linear programming techniques to solve several travelling salesman problems, the largest of which involved a tour of 318 cities.

Six years later, Padberg and Giovanni Rinaldi of the Institute for Systems Analysis, part of the Italian National Research Organisation in Rome, succeeded in solving a 2392-city problem for the electronics company Tektronics, which wanted to optimise the manufacture of a printed circuit board. This time the researchers used an algorithm based on a mathematical theory developed in the 1970s by the German mathematician Martin Grotschel and by Padberg himself. A Control Data Cyber-205 computer initially took 27 hours to solve the problem, but Padberg and Rinaldi improved the algorithm and reduced the running time to less than 3 hours. However, the same computer using the same algorithm took twice as long to solve a problem involving only 532 cities - an indication that running time depends on the distribution as well as the number of cities.

In April this year, a team of American mathematicians took the lead with an optimal solution for a tour of 3038 cities (see New Scientist, Science, 27 June). David Applegate of AT&T Bell Laboratories in New Jersey, Robert Bixby of Rice University, Vasek Chvatal of Rutgers University and William Cook of Bellcore in New Jersey used parallel computing on 30 Sparc2 stations to work out the route and to prove that it is indeed optimal. The program was run mostly at night when the computers would otherwise have been idle. An estimated 18 months of computer time was needed to complete the calculation.

Padberg sees no barrier to the size of real-life travelling salesman problems that can be solved, other than the limitations of current technology. 'Parallelisation and vectorisation of the computation,' he claims, 'are the most obvious avenues to take if one wants to increase solvable problem size.' Nevertheless, a practical solution to the whole problem remains elusive.

One of the attractions of the travelling salesman problem to mathematicians is that it is typical of a large class of difficult, and as yet unsolved, optimisation problems. They hope that if they can construct an efficient algorithm for the travelling salesman problem, they could apply it to other problems in the class. Central to this is a new branch of mathematics known as complexity theory, which studies not just algorithms but also how efficient they are.

EASY IS QUICK TO SOLVE

Mathematicians use the performance of algorithms to distinguish between 'easy' and 'hard' problems. To see whether a problem is easy or hard, mathematicians look at the formula which relates the time an algorithm takes to the number of objects in the problem to be solved. In general, the larger the number (n) of objects, the longer the time the algorithm will take to find the solution.

If running time grows as a constant multiple of a fixed power of n, such as n7, they say that the algorithm finds the solution in so-called polynomial time and that the problem is easy. For example, the problem of finding the shortest routes from a given city to each of n other cities is easy because it can be solved in polynomial time using an algorithm that requires less than n3 operations.

A HARD CASE

Mathematicians classify all problems that can be solved by a polynomial-time algorithm as class P. There are good reasons, both theoretical and empirical, for choosing a polynomial-time algorithm as the mathematical equivalent of a practical algorithm - that is, one that gives an answer in a reasonable time.

The travelling salesman problem is hard because no one has found an algorithm that computes the shortest tour of n cities in polynomial time. The running times for the best algorithms known for solving the travelling salesman and other hard optimisation problems usually grow exponentially, and are therefore useless for all practical purposes. If the solution of a problem of size n requires 2n operations, an instance of size 100 is unsolvable: even with a supercomputer it would take billions of years to get the answer. But 'hard' is only a provisional label, for tomorrow a clever mathematician may find a solution using a polynomial-time method and show that the problem is in fact easy.

A second class of problems in complexity theory is called nondeterministic polynomial, or NP. These are problems that can be solved by a nondeterministic algorithm in polynomial time. Normally, the term algorithm refers to a deterministic algorithm; one that consists of a sequence of steps, so that computation proceeds in a linear fashion. In nondeterministic algorithms, instructions can take the form 'Go to both A and B', and as a result the computation will branch like a tree into a number of parallel computations. A nondeterministic algorithm can be thought of as operating in two stages. In the first, the algorithm 'guesses' a possible answer to the problem; the second stage then serves to verify whether the guess is a solution.

The NP class contains all the problems in P because a deterministic algorithm in effect simply bypasses the guessing stage. The central question is whether there is anything in NP that is not in P. In other words, no one knows whether P NP, although this is widely believed to be the case. Those working in complexity theory, not unlike theologians, must have faith in the existence of their prime object of study.

Strictly speaking, the labels P and NP apply only to decision problems, or problems requiring a yes or no answer. But almost any problem may be expressed as a decision problem, so the distinction is often blurred. In NP, the hard problems may be loosely described as those whose solutions may be hard to find but are easy to check. For example, the travelling salesman problem is in NP because we can ask 'Is there a tour of length less than k?' If the answer is yes and a particular tour t is offered as evidence, it is then easy to check that the length of t is indeed less than k.

In 1971, Stephen Cook of the University of Toronto showed that a particular decision problem in formal logic, known as the satisfiability problem, could qualify as the 'hardest' problem in the class NP. This is because the satisfiability problem has the property that for any problem X in NP, there is a polynomial-time algorithm that transforms X into a special case of the satisfiability problem S. Problems such as S are called 'NP-complete', and Cook's finding implies that any polynomial-time solution of S can be converted into a polynomial-time solution of X. In other words, if S is in class P, so is every other problem in NP and there are no hard problems at all. Since then, many well-known hard problems in the class NP have been proved to be NP-complete including - you guessed it - the travelling salesman problem. The bottom line is that if there are such things as hard problems, the travelling salesman puzzle must be one of them.

TAKING THE APPROXIMATE ROUTE

In the meanwhile, the record-breaking algorithm that produced a solution for 3038 cities is still a long way away from the needs of chip manufacturers, where applications may require the drilling of as many as 1.2 million holes. In many practical applications of the travelling salesman problem, however, a tour that is nearly optimal may be as good as an exact solution. In certain processes, for instance, where a laser must move to 100 000 different points on a chip, a near-optimal path can significantly reduce expensive processing time. Cost may be another factor in opting for approximate solutions.

According to David Johnson, a mathematician at Bell Labs: 'Five hours on a multimillion dollar computer for an optimal solution may not be cost-effective if one can get within a few per cent in seconds on a PC.' Johnson and his colleague Jon Bentley have become experts in the art of finding approximate solutions for the travelling salesman problem. They firmly believe that finding optimal tours for large instances is just not feasible. Their approach involves designing and experimenting with heuristics: strategies or sets of rules designed to find near-optimal tours rather than exact solutions.

Some of these heuristics gradually build up a tour out of shorter paths. A simple example is the nearest-neighbour heuristic: start at an arbitrarily chosen city; choose as the second city the one closest to the first; choose as the third city the one closest to the second and not already visited, and so on. Finally, when you have visited every city, complete the tour by returning to the initial city.

A popular type of heuristic, called 'local optimisation', repeatedly improves an approximate solution by making local changes to a previously constructed tour. An example of this technique is the 2-Opt heuristic. Figure 2 illustrates a single 2-Opt swap where replacing the edges AB and CD by AC and BD produces a shorter tour. The 2-Opt heuristic applies such swaps to a tour until no further swaps can be made that would reduce the tour's length. For example, in the 32-city tour shown in Figure 3, the 2-Optimal tour is obtained after six swaps.

A much more sophisticated approach, known as the Lin-Kernighan algorithm, is the basis of a program created by Bentley and Johnson in collaboration with Lyne McGeoch of Amherst College in Massachusetts. The program can compute very good approximations in a relatively short time. When run on a fast processor with 256 megabytes of main memory, it takes less than 3 hours to give an answer that is within 1.5 per cent of the shortest tour of one million 'cities' - actually points on the unit square that the computer has randomly generated.

Physics and biology serve as models for two variants of local optimisation that have been tried on the travelling salesman problem (see 'Natural solutions give their best', New Scientist, 14 April 1990). The technique called simulated annealing is reasonably effective but slow. Inspired by the behaviour of crystals forming in a cooling metal, it involves exchanging two randomly chosen links in the tour to improve an approximate solution. Genetic algorithms are based on a kind of 'mating' of solutions selected from a population of possible solutions. The process is repeated for many 'generations' in a way that mimics natural selection, with randomness once more being a key element. Again, the technique gives mixed results.

Then there are neural networks. These are systems that model the massive interconnections of neurons in the human brain and have the ability to modify themselves by a process similar to learning. Artificial neural networks can be simulated by a computer program or actually built into, for example, a silicon chip. Could this branch of artificial intelligence hold the key to the solution of the travelling salesman problem?

Johnson says that he has never seen an impressive application of neural networks to the travelling salesman problem, or to any of the other hard optimisation problems. 'The hardware requirements increase rapidly,' he adds, 'and neural network models do not scale very well. As problems get bigger, they typically do not produce feasible solutions, much less good ones.' Johnson does not expect performance to improve even with the development of neural computers, where the networks are built into the hardware and not just simulated.

HARD PROBLEMS STAY HARD

Mathematicians will not consider the travelling salesman problem as solved until they find an efficient algorithm that can calculate the optimal tour for instances of arbitrary large size. But for practical applications of the problem, an approximate solution is the next best thing. For some hard problems (such as the bin packing problem of how best to fit objects into bins given their respective sizes), it is possible to construct polynomial-time algorithms that provide approximate solutions to any degree of accuracy desired. But a few months ago, Sanjeev Arora and Madhu Sudan of the University of California at Berkeley, Rajeev Motwani of Stanford University, and Carsten Lund and Mario Szegedy of Bell Labs found a powerful property of the class NP that had an unexpected connection with the travelling salesman and other difficult problems. Their result implies that if P NP, then there is a threshold beyond which it is just as hard to find a good approximation algorithm that will always work as it is to find a general exact solution.

There is much empirical evidence but no conclusive proof that the travelling salesman problem is intractable. Mathematicians may still cling to the hope of finding an efficient solution - or accept the fact that their algorithms cannot help all travelling reps find the most economical route.

Arturo Sangalli is in the department of mathematics at Champlain Regional College, Lennoxville, Quebec.

Further reading: The Traveling Salesman Problem, edited by E. L. Lawler et al, John Wiley & Sons, 1985.

From issue 1851 of New Scientist magazine, 12 December 1992, page 24

2006 Drummers tune in to robot rhythm

2007-09-14T23:37:00.001-07:00

Drummers tune in to robot rhythm

16 May 2006
NewScientist.com

Drum machines have done drummers out of a lot of work, so a robot percussionist might be expected to pile on the misery. But not Haile. Its developer, Gil Weinberg of the Georgia Institute of Technology in Atlanta claims it will help drummers rather than hinder them.

See a video of the drumming robot in action here (.mov format).

Haile uses its wooden arms to play a Native American powwow drum, facing a human drummer and striking the opposite side of the same drum. The robot detects the rhythm, loudness and pitch of the player's drum pattern and perfectly mimics their actions.

Haile then improvises by dividing, multiplying or skipping beats. "This creates variations of the user's rhythm while keeping the original feel," Weinberg says.

Weinberg now plans to use genetic algorithms to modify the beats in real time, to come up with new patterns.

From issue 2551 of New Scientist magazine, 16 May 2006, page 27

1994 Software's special agents

2007-09-14T23:36:00.001-07:00

Software's special agents: Tired of sifting through electronic mail, searching databases and scanning networks for interesting news? An intelligent agent could be what you need.

09 April 1994
From New Scientist Print Edition. Subscribe and get 4 free issues.
ELLEN

It is Monday morning, work is hectic and there is less than a week to go before your holiday, but you still haven't booked a flight or accommodation. What you need is a personal helper that can go out and comb the travel agencies' computer systems for you. A helper that knows you like walking rather than lazing in the sun, that knows where you like to sit on different types of aeroplane, and that can deliver video footage of a choice of hotels to your work computer or home TV set.

Sounds like a dream? Well, perhaps not. At a recent conference organised by Hewlett-Packard, Nicholas Negroponte, director of the media lab at the Massachusetts Institute of Technology described how the 'future of computing will be 100 per cent driven by delegating to, rather than manipulating computers'. His vision is of a world where people employ electronic helpers - agents - that learn their likes and dislikes, behaving, says Negroponte, 'like an English butler'.

Developing agents as sophisticated as this is not a simple task, and the world is still some way from an electronic Jeeves. But the coming of the information superhighway which will connect us all to electronic networks means that simpler software agents - computer programs that can learn from your online behaviour - will be much in demand. When you have 500 television channels pouring into your home, you'll need an agent which has learnt what your preferences are at different times of day and shows you your favourite items first. And pretty soon you'll find that agents are available to sort your e-mail, bringing to your attention quickly the sort of items you've looked at first in the past.

But before agents become commonplace helpers in home and office, they will provide powerful tools for managing complex networks in which one part of the system needs to know what is happening elsewhere. In huge phone systems, for example, call route-ings have to be constantly changed to avoid line failures. Agents can be sent out to check the state of the network or interrogate each other to negotiate the best routes. And if networks link many different types of computer, agents can act as reporters with the advantage of sharing a common language.

One of the first software agents, Archon, was of this type. It was developed by Nick Jennings of Queen Mary and Westfield College in London in response to a request from one of the Spanish electricity companies in 1987. The organisation wanted to connect all the computers that controlled distribution of electricity over the country's grid. But there was no simple way to link the many different makes of machine.

The organisation uses Archon agents to monitor the databases on each of the computers. Each agent selects relevant information from its database to send on to agents on other machines. If, for example, a power station is running at low output in one computer's sector, the agent might ask agents at other sectors computers if they are able to divert power.

Archon agents are essentially quite simple expert systems but their general properties are common to most agents. In the language of agent designers, each Archon agent has local knowledge of the computer it occupies, certain 'beliefs' about the function of agents on other machines (in the sense that assumptions about what other agents will do are built into its program) and a set of 'desires' or goals that it must achieve.

Chris Winter, who works in BT's labo-ratories near Ipswich, which have dev-eloped some slightly more intelligent agents, says that one of the main differences between agents and traditional database query programs is that agents can say 'no'.

'Normal computer programs issue commands that must be obeyed, whereas agents issue requests that can be turned down by other agents,' explains Winter. This is important if agents are to communicate meaningfully.

In the scientific community, astronomers have been among the first to take to software agents. Cindy Mason and her colleagues at NASA Ames Research Center, south of San Francisco, have created agents that can control the scheduling of the telescopes. Each telescope agent knows the capabilities of its own telescope and the current weather conditions at its location. It also has some information about other robotic telescopes, such as their location and what kind of equipment they have. When it can't meet one of its own astronomers' requests, it communicates with agents managing other telescopes via e-mail according to a set of rules. If, for example, the agent receives a request for a viewing and cloudy weather is forecast for its area, it will obey the rule: 'If I have bad weather and there's another agent with the right telescope at the proper latitude and longitude, then send a request to that agent for a viewing tonight.' After the request is sent, the agents negotiate to decide who gets priority at which telescope.

This procedure follows a policy of 'fairness': it takes into account the importance of the event (unusual events such as a supernova have a higher priority than observing binary stars), the long-term goals of each astronomer and his or her viewing 'history'. In negotiating with other telescope agents for time on their telescope, the agent in need of help identifies important observations that need to be rescheduled, and either trades time with or offers the other agent a one-off payment.

Not all agents will simply sit at their home computers and send e-mail to other agents. Many people who design agents believe that it will prove simpler to create agents which leave your computer, copy themselves to other locations where they can explore, and return with the data you requested.

The first 'mobile' agents began to appear in research laboratories a few years ago. 'Rodney' is one of them - a general purpose software robot or 'softbot' designed by Oren Etzioni and his colleagues at the University of Washington, Seattle. Rodney can travel on the Internet and find out information about people, manage computer files, and monitor events such as the arrival of urgent e-mail. Etzioni might ask Rodney to find the e-mail address and telephone number for Jane Smith, for example, adding that Jane is a biologist. Rodney thus reasons: 'I could find out her e-mail address by using netfind (an information tool on the Internet), but netfind requires the person's city and institution. How can I get that? I might be able to find papers or technical reports by her. So I need to go out and look at bibliographic databases, and search for Jane Smith.'

Fans of mobile agents say that the amount of space these small programs take up on the network is less than if agents stay in one place and send e-mail. But BT's Winter believes a more realistic reason for developing mobile agents is that it is easier to write the code because it is easier to visualise what they are doing.

Pattie Maes, a computer scientist at the Media Lab, uses many small mobile agents for her work on news filtering. Her 'population' of agents searches the 'newsgroups' - special interest groups on the Internet and pulls out articles of interest to the user. Unlike the simple rule-based logic used to develop most agent programs, Maes has used techniques from the field of artificial life, such as genetic algorithms that lay down rules on how to combine successful programs to produce new, hopefully better ones. Successful agents - those that consistently learn their owner's preferences and then bring back the right type of news stories - get to reproduce, while agents that fail, die.

Agents like these are much closer to Negroponte's vision of an electronic butler. They are also attracting a lot of attention from commercial companies. General Magic, a Californian software company has developed the Telescript Technology programming language. The company believes that its language will make it easy to develop new agents, whether they perform simple tasks such as sorting and distributing electronic mail or complex ones such as shopping for a bargain holiday.

Private eye

Other researchers want agents to learn about their owner's private life. Tom Mitchell, a computer scientist at Carnegie Mellon, Pittsburgh, says: 'We believe agents will need to know a lot about you.' He has developed a calendar agent which learns his preferences by monitoring the meetings he adds to his electronic diary. If you request a meeting with Mitchell, his agent can talk to your agent and agree the timing and duration. Agents can challenge you: if past meetings lasted 20 minutes, for example, and you request a meeting of an hour, Mitchell's agent might ask if you're really sure.

Mitchell's personal agent has hundreds of rules such as: 'If I'm meeting with one of my students and we haven't met yet this week, the meeting will probably be for an hour.' These are not written by him - the agent extracts them from its observation of Mitchell's electronic diary.

But if we trust agents with all this personal information, what happens if the agent does something unexpected? This fact has not been ignored by researchers. Agents are in many way similar to worm-style viruses. They are independent computer programs that can reproduce, migrate and run themselves on another machine. Even though agents may be 'benevolent worms', the idea of allowing an intelligent, virus-like program to roam the networks is unsettling to some people. But Winter says the security risks are probably no greater than those that already exist, and he says that many companies, such as General Magic, propose that agents run on 'virtual machines' - software that acts as a safety net for the real computer.

Other researchers are looking at laying down strict design rules that will prevent a benevolent agent turning into a psychotic killer. Etzioni and Daniel Weld have written a paper called 'The First Law of Robotics'. The title is a tribute to science fiction writer Isaac Asimov's I Robot defines the Three Laws of Robotics - rules that, according to popular fiction, will be programmed into every robot to prevent them from harming humans. A 'law of softbotics' would prevent an agent from damaging a computer.

The debate over how to keep agents trustworthy is likely to continue behind the doors of the research laboratories, but the desire for a personal servant may well outweigh concerns for security. The danger is that a worm can turn - providing a new piquancy to the phrase the butler did it . . .

Ellen Germain is a freelance writer based in New York.

From issue 1920 of New Scientist magazine, 09 April 1994, page 19

2007 Autonomous driving systems aim to drive dirty

2007-09-14T23:35:00.002-07:00

Autonomous driving systems aim to drive dirty

17:36 23 March 2007
NewScientist.com news service
Matthew

Autonomous model cars will race against one another in a contest designed to test different software approaches.

The contest is being organised by researchers at the University of Essex in the UK, who are creating an affordable and standardised autonomous vehicle kit to encourage others to get involved.

The kit will include a high-end commercial model car, a laptop, a GPS receiver, a USB controller and a camera. The aim is to encourage different research teams to develop autonomous racers using the same equipment, which will then race against one another at the 2008 World Congress on Computational Intelligence in Hong Kong.

Simon Lucas of Essex University says the competition will be similar to the DARPA Grand Challenge (see Desert racers – drivers not included), which involves full-sized vehicles, but will be far less prohibitive. "The challenges are the same for a full-size or model autonomous car, but you need pots of money," Lucus told New Scientist. "Our prototype hardware costs only £1000 ($2000)."

The contest will be preceded by a simulated competition held at the 2007 IEEE Symposium on Computational Intelligence and Games in April 2007. In this competition, the software used to control a car will be run on a simulator. The goal is to reach as many waypoints along the track as possible in a given time without crashing into a second virtual vehicle.

Aggressive racing

Competitors will be able to apply different programming techniques to autonomously direct their cars. Lucas and PhD student Julian Togelius plan to use software built around a learning, "evolving" algorithm.

Developing this involves testing hundreds of different algorithms against one another, then selecting the best ones for recombination and mutation – a process that mimics biological evolution. Videos created by the researchers shows the virtual cars in action.

The software developed by Lucas and Togelius has already demonstrated an ability to complete a course faster than a human controller and has even learned to drive aggressively, knocking into other simulated cars to achieve an advantage.

Lucas says a race involving actual cars, albeit model ones, will require greater skill. "The challenge is to use computer vision methods together with a range of other sensor data to race the car as fast as possible around the track while outwitting the opponent cars," he says. "To do so it needs to be smart and it needs adapt to the behaviour of the other cars as it drives."

Robot cars will race in real traffic
http://www.newscientist.com/article.ns?id=dn10220
03 October 2006
Fast cars could be tuned by evolution
http://www.newscientist.com/article.ns?id=dn6019
18 June 2004
Genetic algorithms evolve optimum satellite orbits
http://www.newscientist.com/article.ns?id=dn1437
16 October 2001

Weblinks

2006 Nuclear reactors 'evolve' inside supercomputers

2007-09-14T23:35:00.001-07:00

Nuclear reactors 'evolve' inside supercomputers

* 09:48 09 June 2006
* NewScientist.com news service
* Tom Simonite

Designing a nuclear reactor normally involves input from various specialists
Enlarge image
Designing a nuclear reactor normally involves input from various specialists
Advertisement

Nuclear reactors could be built more efficiently using supercomputers to artificially "evolve" designs, say engineers from the US Department of Energy's Oak Ridge National Laboratory in Tennessee.

They have found they can speed up the extremely complex process of designing a reactor and generate novel designs from scratch by simulating natural selection.

Designing a nuclear reactor normally involves input from various specialists and the resulting structure can be uniquely influenced by this collaborative process.

"The design that comes out of this lengthy process is typically sub-optimal," says Louis Qualls, a nuclear systems specialist at Oak Ridge National Laboratory. "If you started with a different person, or designed pieces in a different order, you would get a different system."
Natural selection

Qualls and his colleagues were looking for a more efficient design approach and found inspiration in biological evolution. They used software tools known as genetic algorithms to evolve different reactor designs. Similar algorithms are already used in many different fields to evolve highly efficient solutions to particular problems.

The algorithms they created first produce a population of reactor designs by randomising all the different design factors involved. Each design is then tested in a simulation for its "fitness", measuring its performance efficiency, running cost, safety and other parameters.

The designs that perform best are singled out for survival. They are mutated and recombined to create the next generation of designs. After many cycles, the potential of the most refined designs is evaluated by engineers.

"[Simulated evolution] will come up with some systems we would just never have thought of," Qualls says. "It won't replace the experts or come up with a finished design, but it makes it possible to consider options they wouldn't have had otherwise."
Safety first

The parameters used to decide which designs survive can also be tweaked to meet different overall criteria. "If I were a businessman I'd want to make the most profit," explains Qualls. "But a safety engineer would want one that is least likely to break down."

Qualls's team has used the approach to help design the reactor for a NASA spacecraft designed to one day travel to the asteroid belt. In this case, weight was the main design concern.

Andy Keane, an independent genetic algorithms expert at Southampton University, UK, says this approach has already proven useful in other fields of engineering.

But for very complex problems, such as nuclear reactor design, he says it is important to combine genetic algorithms with sophisticated methods of simulation and analysis. "Research is now focused on integrating genetic algorithms with other techniques and more powerful computation," Keane says. "This means we can produce more complete designs."
Related Articles

* Robotic modelling reveals ancient hominid stride
* http://technology.newscientist.com/article/dn7704
* 21 July 2005
* New photofit 'evolves' a suspect's face
* http://technology.newscientist.com/article/dn7143
* 19 March 2005
* Organised chaos gets robots going
* http://technology.newscientist.com/article/dn6582
* 01 November 2004

Weblinks

* Oak Ridge National Laboratory
* http://www.ornl.gov/
* Genetic algorithms, Wikipedia
* http://en.wikipedia.org/wiki/Genetic_algorithm
* Andy Keane, Southampton University
* http://www.soton.ac.uk/~ajk/

2007 Eel feel helps wave power go with the flow

2007-09-14T23:34:00.001-07:00

Eel feel helps wave power go with the flow

16 April 2007
Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues
Paul

Max Carcas, a director of Ocean Power Delivery, thinks the idea may hold promise, but he says the company's own engineers are also working to improve the device's efficiency.

Peter Bentley, a computer scientist at University College London, says the work shows how much genetic algorithms have become accepted in engineering.

From issue 2599 of New Scientist magazine, 16 April 2007, page 28

2003 Gladiator-style 'wars' select out weak programs

2007-09-14T23:33:00.002-07:00

Gladiator-style 'wars' select out weak programs

10:00 12 July 2003
Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues
Will

Computer scientists have found the ultimate way to debug their programs - let them compete against other programs in a gladiator-style tournament.

Dubbed Grid Wars II, the contest held at the ClusterWorld conference in San Jose, California, last month was like a software version of television's Robot Wars and Battle Bots. In each battle, programs fought to gain control of processing power in a huge parallel computer.

Besides giving computer scientists an excuse to tear themselves away from their terminals the contest also has scientific merit, according to some contestants. "Grid Wars gave me the opportunity to test my algorithm," says Mark Wenig, one of the finalists from NASA's Goddard Space Flight Center in Greenbelt, Maryland. "It is a perfect environment to test and compare different approaches."

The contest began with 236 different programs, submitted by universities, government research departments and software companies from around the world. The objective of each entrant was to fight for control of 2500 computer processors.

Attack or defence

A program can take over a neighbouring processor by firing virtual "bullets" at the program already occupying it. When a processor is hit three times the defending program loses control and is replaced by its aggressor. By communicating between occupied processors allied programs are able to coordinate an attack or defence.

Onlookers watched the algorithms on a screen that displayed each match. Each processor was represented by a square in a giant grid and each program by a different colour. To start off, programs fought it out in small groups. The winners of each group contest were then paired off in a 32-program knock-out contest.

When this was whittled down to the final two the atmosphere was nail-biting, says Matt Oberforger of Engineered Intelligence in Colorado, who organised the event. The final battle saw Wenig's program - created using genetic algorithms - take on a program designed by a computing student from Moscow State University.

Rogue and Cobra

NASA used a process that mimics natural selection to "evolve" the best fighting code, while the Russian chose to write his program by hand. "It was the US versus Russia, man against machine," says Oberforger.

For the first 400 out of 500 cycles the NASA program, "Rogue" was clearly dominating and had control of 1500 of the 2500 processors. But in the final moments the Russian contender, called Cobra, quickly defeated Rogue. "In the last hundred cycles the Russian program broke out and slowly ate up the genetic algorithm," says Oberforger. "Nobody really believed it would." The key to its success may have been its ability to communicate efficiently and hence spread quickly, he says.

Weblinks

2002 Winged robot learns to fly

2007-09-14T23:33:00.001-07:00

Winged robot learns to fly

* 09:30 17 August 2002
* Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues.
* Ian Sample

How the winged robot tries to fly (and cheat the scientists)
Enlarge image
How the winged robot tries to fly (and cheat the scientists)

Learning how to fly took nature millions of years of trial and error - but a winged robot has cracked it in only a few hours, using the same evolutionary principles.

Krister Wolff and Peter Nordin of Chalmers University of Technology in Gothenburg, Sweden, built a winged robot and set about testing whether it could learn to fly by itself, without any pre-programmed data on what flapping is or how to do it.

To begin with, the robot just twitched and jerked erratically. But, gradually, it made movements that gained height. At first, it cheated - simply standing on its wing tips was one early short cut.

After three hours, however, the robot abandoned such methods in favour of a more effective flapping technique, where it rotated its wings through 90 degrees and raised them before twisting them back to the horizontal and pushing down.

"This tells us that this kind of evolution is capable of coming up with flying motion," says Peter Bentley, who works on evolutionary computing at University College London. But while the robot had worked out how best to produce lift, it was not about to take off.

"There's only so much that evolution can do," Bentley says. "This thing is never going to fly because the motors will never have the strength to do it," he says.
Balsa wood wings

The robot had metre-long wings made from balsa wood and covered with a light plastic film. Small motors on the robot let it move its wings forwards or backwards, up or down or twist them in either direction.

The team attached the robot to two vertical rods, so it could slide up and down. At the start of a test, the robot was suspended by an elastic band. A movement detector measured how much lift, if any, the robot produced for any given movement.

A computer program fed the robot random instructions, at the rate of 20 per second, to test its flapping abilities. Each instruction told the robot either to do nothing or to move the wings slightly in the various directions.

Feedback from the movement detector let the program work out which sets of instructions were best at producing lift. The most successful ones were paired up and "offspring" sets of instructions were generated by swapping instructions randomly between successful pairs.

These next-generation instructions were then sent to the robot and evaluated before breeding a new generation, and the process was repeated.
Related Articles

* Genetic algorithm tunes up public speakers
* http://www.newscientist.com/article.ns?id=dn2560
* 17 July 2002
* Computer DJ uses biofeedback to pick tracks
* http://www.newscientist.com/article.ns?id=dn1563
* 14 November 2001
* Bouncing robots could advance planetary exploration
* http://www.newscientist.com/article.ns?id=dn80

Entelligence: Evolutionary Intelligence

Collective Intelligence and Evolution

Collective Intelligence and Evolution

new Journal: Evolutionary Intelligence

Evolutionary Intelligence

Swarm Intelligence journal

Swarm Intelligence

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

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

Oldest University Unearthed in Egypt

Oldest University Unearthed in Egypt

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

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

Several interesting papers from Hod Lispon about modeling

Pat Langley at Stanford has a strong interests in automated scientific discovery

Pat Langley

Institute for the Study of Learning and Expertise2164 Staunton Court, Palo Alto, CA 94306(650) 494-3884 (phone); (650) 494-1588 (fax)langley@isle.org

2007 John Koza's research focus

Toward automated discovery in the biological sciences.

Automated Scientific Discovery, the holy goal of AI? from AAAI

Automated Discovery research by Dr. Zytkow at UNCC

Publications

Learnable Evolutionary computation

PCA and exploratory analysis for linkage learning in Genetic algorithm

Learnable Evolution Model Non-Darwinian Evolutionary Computation

google adsense by Genetic algorithm?

Google Targeting Ads Based on Previous Queries

EDA Intelligent evolutionary design: A new approach to optimizing complex engineering systems and its application to designing heat exchangers

1997 Recent Work in Computational Scientific Discovery

Recent Work in Computational Scientific Discovery

Abstract

Introduction

Pioneering Work

Recent Work

Computational Discovery: Pros and Cons

Acknowledgments

References

genometri: company use genetic algorithms for product design

Clarient Obtains Exclusive License for Natural Selection, Inc.

Clarient Obtains Exclusive License for Natural Selection, Inc. Software to Develop Novel Cancer Markers

Nov 30 2006, 2:30 AM EST

1999 Computer Scientist To Explore Intricacies Of Biological Evolution

Computer Scientist To Explore Intricacies Of Biological Evolution

2000 Scientists Discover Evolutionary Origin Of Fins, Limbs

Scientists Discover Evolutionary Origin Of Fins, Limbs

2000 Supercomputers Help University Of Idaho Scientists Explore Genetics And Bioinformatics

Supercomputers Help University Of Idaho Scientists Explore Genetics And Bioinformatics

2005 Programmable Cells: Engineer Turns Bacteria Into Living Computers

Programmable Cells: Engineer Turns Bacteria Into Living Computers

2001 Genetic Algorithms "Naturally Select" Better Satellite Orbits

Genetic Algorithms "Naturally Select" Better Satellite Orbits

1999 Computers Use Darwinian Model To "Evolve" Fuel Additives

Computers Use Darwinian Model To "Evolve" Fuel Additives

2006 Engineers Take Page Out Of Nature's Playbook

Engineers Take Page Out Of Nature's Playbook

2003 Falling Prey To Machines?

Falling Prey To Machines?

2004 Survival Of The Fastest: Scientists 'Selectively Breed' Winning Formula One Cars

Survival Of The Fastest: Scientists 'Selectively Breed' Winning Formula One Cars

2000 Building Better Engines Through Natural Selection

Building Better Engines Through Natural Selection

1999 Evolving Algorithms Take Aim At Prostate Cancer

Evolving Algorithms Take Aim At Prostate Cancer

2002 New Method Speeds Up Discovery Of Materials

New Method Speeds Up Discovery Of Materials

2004 Knowledge Discovery' Could Speed Creation Of New Products

Knowledge Discovery' Could Speed Creation Of New Products

2007 Engineers prolong satellite life

Engineers prolong satellite life

2002 Fractals Help UCLA Researchers Design Antennas For New Wireless Devices

Fractals Help UCLA Researchers Design Antennas For New Wireless Devices

2004 Fast cars could be tuned by evolution

Fast cars could be tuned by evolution

Track records

Pit-stop strategies

Related Articles

Weblinks

2005 New photofit 'evolves' a suspect's face

New photofit 'evolves' a suspect's face

Face mutation

Institute for the Study of Learning and Expertise
2164 Staunton Court, Palo Alto, CA 94306
(650) 494-3884 (phone); (650) 494-1588 (fax)
langley@isle.org