These papers are arranged into five groups, then arranged roughly by date of publication (newer papers come first).
- Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and Code Bloat
-
- Note:
- This dissertation has been reformatted from its originally published version, in order to reduce the number of pages (by about 100) and to increase readability. It comes in two forms: a one-sided printing version and a two-sided printing version. The two-sided printing version has a few blank pages added to make sure that chapters always start on the front side of a page. If you can print two-sided, I strongly recommend it. If referring to page numbers in the thesis, please use the two-sided version.
- Author:
- Sean Luke
- Formats:
-
(Recommended) Two-Sided Version in PDF (3.9 M, 178 pages)
(Recommended) Two-Sided Version in Gzipped PostScript (.ps.gz) (3.3 M, 178 pages)
One-Sided Version in PDF (3.9 M, 165 pages)
One-Sided Version in Gzipped PostScript (.ps.gz) (3.3 M, 165 pages)
- Citation:
- Luke, Sean. 2000. Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and Code Bloat. Ph.D. Dissertation, Department of Computer Science, University of Maryland, College Park, Maryland.
- Abstract:
- Genetic Programming is an evolutionary computation technique which searches for those computer programs that best solve a given problem. As genetic programming is applied to increasingly difficult problems, its effectiveness is hampered by the tendency of candidate program solutions to grow in size independent of any corresponding increases in quality. This bloat in solutions slows the search process, interferes with genetic programming's searching, and ultimately consumes all available memory. The challenge for scaling up genetic programming is to find the best solutions possible before bloat puts a stop to evolution. This can be tackled either by finding better solutions more rapidly, or by taking measures to delay bloat as long as possible.
This thesis discusses issues both in speeding the search process and in delaying bloat in order to scale genetic programming to tackle harder problems. It describes evolutionary computation and genetic programming, and details the application of genetic programming to cooperative robot soccer and to language induction. The thesis then compares genetic programming breeding strategies, showing the conditions under which each strategy produces better individuals with less bloating. It then analyzes the tree growth properties of the standard tree generation algorithms used, and proposes new, fast algorithms which give the user better control over tree size. Lastly, it presents evidence which directly contradicts existing bloat theories, and gives a more general theory of code growth, showing that the issue is more complicated than it first appears.
- Errata:
-
- In Algorithm 2 (p. 6), the line P<-P\{q} should read P<-P\{s}
- Figures 5.2 through 5.5 (p. 38-39) are not in proper evolutionary-time order. The proper order is 5.4, 5.5, 5.2, 5.3.
- Two Fast Tree-Creation Algorithms for Genetic Programming
-
- Author:
- Sean Luke
- Formats:
-
- PDF
Gzipped PostScript (ps.gz)
- Citation:
- Luke, Sean. 2000. Two fast tree-creation algorithms for genetic programming. In IEEE Transactions on Evolutionary Computation 4:3 (September 2000), 274-283. IEEE.
- Abstract:
- Genetic programming is an evolutionary optimization method that produces functional programs to solve a given task. These programs commonly take the form of trees representing LISP s-expressions, and a typical evolutionary run produces a great many of these trees. For this reason, a good tree-generation algorithm is very important to genetic programming. This paper presents two new tree-generation algorithms for genetic programming and for "strongly-typed" genetic programming, a common variant. These algorithms are fast, allow the user to request specific tree sizes, and guarantee probabilities of certain nodes appearing in trees. The paper analyzes these two algorithms and compares them with traditional and recently proposed approaches.
- Three RoboCup Simulation League Commentator Systems
-
- Authors:
- Elisabeth Andre, Kim Binsted, Kumiko Tanaka-Ishii, Sean Luke, Gerd Herzog, and Thomas Rist
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- E. Andre, K. Binsted, K. Tanaka-Ishii, S. Luke, G. Herzog, and T. Rist. 2000. Three RoboCup simulation league commentator systems. In AI Magazine, 21:1 (Spring 2000), 57-66. AAAI.
- Abstract:
- Three systems which generate real-time natural language commentary on the RoboCup simulation league are presented, and their similarities, differences, and directions for the future discussed. Although they emphasize different aspects of the commentary problem, all three systems take simulator data as input, and generate appropriate, expressive, spoken commentary in real time.
- The Perfect C. elegans Project: An Initial Report
-
- Authors:
- Hiroaki Kitano, Shugo Hamahashi, and Sean Luke
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Kitano, H., S. Hamahashi, and S. Luke. The perfect C. elegans project: an initial report. In Artificial Life, 4:2 (Spring 1998), 141-156. MIT Press.
- Abstract:
-
The soil nematode Caenorhabditis Elegans (C. elegans) is the most investigated of all multi-cellular organisms. Since the proposal to use it as a model organism, a series of research projects have been undertaken, investigating a wide range of on various aspects of this organism. As a result, the complete cell lineage, neural circuitry, and various genes and their functions have been identified. The complete C. elegans DNA sequencing and gene expression mapping for each cell at different times during embryogenesis will be identified in a few years. Given the abundance of collected data, we believe that the time is ripe to introduce synthetic models of C. elegans to further enhance our understanding of the underlying principles of its development and behavior. For this reason, we have started the Perfect C. elegans Project, which aims to ultimately produce a complete synthetic model of C. elegans cellular structure and function. This paper describes the goal, the approach, and the initial results of the project.
- Biology: See It Again -- for the First Time
-
- Authors:
- Sean Luke, Shugo Hamahashi, Koji Kyoda, and Hiroki Ueda
- Formats:
-
Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S., S. Hamahashi, K. Kyoda, and H. Ueda. 1998. Biology: See It Again -- for the First Time. In IEEE Intelligent Systems. 13:5 (September/October 1998). 6-8.
-
First Paragraph:
- Computer science owes a huge debt to biological systems. The field itself came about largely as an attempt to understand and replicate the function and abilities of the brain, a complex biological creation. From this early lineage has sprung many subfields derived largely from biological metaphors: computer vision, neural networks, evolutionary computation, robotics, multi-agent studies, and much of artificial intelligence. In some areas, the computer has bested its biological counterparts in efficiency and simplicity. But for many domains, even after decades of hard work, the biological "real thing" is still superior to the artificial algorithms inspired by it.
- Evolving SoccerBots: A Retrospective
-
- Author:
- Sean Luke
- Note:
- This short invited paper was meant to complement the more complete GP98 and RoboCup97 papers, and an AI Magazine sidebar, by discussing things that could have been improved from our previous attempt.
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S. 1998. Evolving soccerbots: a retrospective. In Proceedings of 12th Annual Conference of the Japanese Society for Artificial Intelligence (JSAI).
- Abstract:
- In the RoboCup97 robot soccer tournament, we entered a team of softbot programs whose player strategies had been entirely learned by computer. Our team beat other human-coded competitors and received the RoboCup97 Scientific Challenge award. This paper discusses our approach, and details various ways that, in retrospect, it could have been improved.
- Web Agents That Work
-
- Authors:
- Sean Luke and James Hendler
- Note:
- The figures in this paper are large, so I provide versions of the paper below both with or without the figures.
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
Gzipped Postscript (.ps.gz) without Figures 1-3
PDF without Figures 1-3
- Citation:
- Luke, S. and J. Hendler. 1997. Web Agents That Work. In IEEE Multimedia. 4:3 (July-September 1997). IEEE Press. 76-80.
- First Paragraph:
- There are two kinds of information-seekers currently wandering the World-Wide Web. First there are us humans, the web-surfers for whom the Web was designed. Second, there are increasing numbers of automated systems, Web agents, which gather information from the Web on our behalf. At the present time, humans far outnumber web agents, but this could soon change: as the sheer volume of information on the Web increases,and the ratio of junk to useful information continues to grow, we will increasingly rely on agents to dig through all that muck to find our gems for us.
- Note:
- This article covers similar issues as the paper, Ontology-based Web Agents.
- Fighting Bloat With Nonparametric Parsimony Pressure
-
- Authors:
- Sean Luke and Liviu Panait
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S., and L. Panait. 2002. Fighting Bloat With Nonparametric Parsimony Pressure. In Parallel Problem Solving from Nature - PPSN VII (LNCS 2439). Juan Julian Merelo Guervos et al, eds. Springer Verlag. 411-421.
- Abstract:
-
Many forms of parsimony pressure are parametric, that is final fitness is a parametric model of the actual size and raw fitness values. The problem with parametric techniques is that they are hard to tune to prevent size from dominating fitness late in the evolutionary run, or to compensate for problem-dependent nonlinearities in the raw fitness function. In this paper we briefly discuss existing bloat-control techniques, then introduce two new kinds of non-parametric parsimony pressure, Direct and Proportional Tournament. As their names suggest, these techniques are based on simple modifications of tournament selection to consider both size and fitness, but not together as a combined parametric equation. We compare the techniques against, and in combination with, the most popular genetic programming bloat-control technique, Koza-style depth limiting, and show that they are effective in limiting size while still maintaining good best-fitness-of-run results.
- Is the Perfect the Enemy of the Good?
-
- Authors:
- Sean Luke and Liviu Panait
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S., and L. Panait. 2002. Is the Perfect the Enemy of the Good? In GECCO-2002: Proceedings of the Genetic and Evolutionary Computation Conference. W. B. Langdon et al, eds. Morgan Kauffman. 820-828.
- Abstract:
-
Much of the genetic programming literature compares techniques using counts of ideal solutions found. These counts in turn form common comparison measures such as Koza's Computational Effort or cumulative Probability of Success. The use of these measures continues despite past warnings that they are not statistically valid. In this paper we too criticize the measures for serious statistical problems, and also argue that their motivational justification is faulty. We then present evidence suggesting that ideal solution counts are not necessarily positively related to best-fitness-of-run statistics: in fact they are often inversely correlated. Thus claims based on ideal solution counts can mislead readers into thinking techniques will provide superior final results, when in fact the opposite is true.
- Note:
- This paper won the Best Paper of Conference award for the Genetic Programming track.
- Lexicographic Parsimony Pressure
-
- Authors:
- Sean Luke and Liviu Panait
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S., and L. Panait. 2002. Lexicographic Parsimony Pressure. In GECCO-2002: Proceedings of the Genetic and Evolutionary Computation Conference. W. B. Langdon et al, eds. Morgan Kauffman. 829-836.
- Abstract:
-
We introduce a technique called lexicographic parsimony pressure, for controlling the significant growth of genetic programming trees during the course of an evolutionary computation run. Lexicographic parsimony pressure modifies selection to prefer smaller trees only when fitnesses are equal (or equal in rank). This technique is simple to implement and is not affected by specific differences in fitness values, but only by their relative ranking. In two experiments we show that lexicographic parsimony pressure reduces tree size while maintaining good fitness values, particularly when coupled with Koza-style maximum tree depth limits.
- A Comparison of Two Competitive Fitness Functions
-
- Authors:
- Liviu Panait and Sean Luke
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Panait, L. and S. Luke. 2002. A Comparison of Two Competitive Fitness Functions. In GECCO-2002: Proceedings of the Genetic and Evolutionary Computation Conference. W. B. Langdon et al, eds. Morgan Kauffman. 503-511.
- Abstract:
-
Competitive fitness is the assessment of an individual's fitness in the context of competition with other individuals in the evolutionary system. This commonly takes one of two forms: one-population competitive fitness, where competition is solely between individuals in the same population; and N-population competitive fitness, often termed competitive coevolution. In this paper we discuss common topologies for one-population competitive fitness functions, then test the performance of two such topologies, Single-Elimination Tournament and K-Random Opponents, on four problem domains. We show that neither of the extremes of K-Random Opponents (Round Robin and Random-Pairing) gives the best results when using limited computational resources. We also show that while Single-Elimination Tournament usually outperforms variations of K-Random Opponents in noise-free problems, it can suffer from premature convergence in noisy domains.
- Note:
- This paper was nominated for the Best Paper of Conference award for the Genetic Algorithms track.
- When Coevolutionary Algorithms Exhibit Evolutionary Dynamics
-
- Authors:
- Sean Luke and R. Paul Wiegand
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S. and R. P. Wiegand. 2002. When Coevolutionary Algorithms Exhibit Evolutionary Dynamics. In the Workshop on Understanding Coevolution: Theory and Analysis of Coevolutionary Algorithms (at GECCO 2002). A. Barry, ed. 236-241.
- Abstract:
-
The task of understanding the dynamics of coevolutionary algorithms or comparing
performance between such algorithms is complicated by the fact the internal fitness
measures are subjective. Though a variety of techniques have been proposed to
use external or objective measures to help in analysis, there are clearly properties
of fitness payoff (e.g., intransitivity) which call such methods into question in certain
contexts. We present a model of competitive fitness assessment with a single
population and non-parametric selection (such as tournament selection), and show
minimum conditions and examples under which an objective measure exists,
and when the dynamics of the coevolutionary algorithm are identical to those of
a traditional EA.
We also discuss terminological difficulties in the coevolution
literature, and present a detailed description of external measures presently
in use in the literature.
- When Short Runs Beat Long Runs
-
- Author:
- Sean Luke
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S. 2001. When short runs beat long runs. In GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference. Lee Spector et al, eds. Morgan Kaufmann. 74-80.
- Abstract:
-
What will yield the best results: doing one run n generations long or doing m runs n/m generations long each? This paper presents a technique-independent analysis which answers this question, and has direct applicability to scheduling and restart theory in evolutionary computation and other stochastic methods. The paper then applies this technique to three problem domains in genetic programming. It discovers that in two of these domains there is a maximal number of generations beyond which it is irrational to plan a run; instead it makes more sense to do multiple shorter runs.
- A Survey and Comparison of Tree Generation Algorithms
-
- Authors:
- Sean Luke and Liviu Panait
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S., and L. Panait. 2001. A survey and comparison of tree generation algorithms. In GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference. Lee Spector et al, eds. Morgan Kaufmann. 81-88.
- Abstract:
-
This paper discusses and compares five major tree-generation algorithms for genetic programming, and their effects on fitness: RAMPED HALF-AND-HALF, PTC1, PTC2, RANDOM-BRANCH, and UNIFORM. The paper compares the performance of these algorithms on three genetic programming problems (11-Boolean Multiplexer, Artificial Ant, and Symbolic Regression), and discovers that the algorithms do not have a significant impact on fitness. Additional experimentation shows that tree size does have an important impact on fitness, and further that the ideal initial tree size is very different from that used in traditional GP.
- "Genetic" Programming
-
- Authors:
- Sean Luke, Shugo Hamahashi, and Hiroaki Kitano
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S., S. Hamahashi, and H. Kitano. 1999. "Genetic" programming.
In GECCO-99: Proceedings of the Genetic and Evolutionary
Computation Conference, Banzhaf, W. et al, eds.
San Fransisco: Morgan Kaufmann.
- Abstract:
-
Much of evolutionary computation was inspired by Mendelian genetics.
But modern genetics has since advanced considerably, revealing that
genes are not simply parameter settings, but interactive cogs in a
complex chemical machine. At the same time, an increasing number of
evolutionary computation domains are evolving non-parameterized
mechanisms such as neural networks or symbolic computer programs.
As such, we think modern biological genetics offers much in helping
us understand how to evolve such things. In this paper, we present
a gene regulation model for Drosophila melanogaster. We
then apply gene regulation to evolve deterministic finite-state
automata, and show that our approach does well compared to past
examples from the literature.
- Character Design for Soccer Commentary
-
- Authors:
- Kim Binsted and Sean Luke
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Binsted, K. and S. Luke. 1998. Character design
for soccer commentary. In Robot Soccer World Cup II: Proceedings
of the second RoboCup Workshop, H. Kitano, ed. 23-35. Springer-Verlag.
- Abstract:
- In this paper we present early work on an animated talking head
commentary system called Byrne. The goal of this project is to
develop a system which can take the output from the RoboCup soccer
simulator, and generate appropriate affective speech and facial
expressions, based on the character's personality, emotional state,
and the state of play. Here we describe a system which takes
pre-analysed simulator output as input, and which generates text
marked-up for use by a speech generator and a face animation
system. We make heavy use of inter-system standards, so that future
versions of Byrne will be able to take advantage of advances in the
technologies that it incorporates.
- Reading Between the Lines: Using SHOE to Discover Implicit Knowledge from the Web
-
- Authors:
- Jeff Heflin, James Hendler, and Sean Luke
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Heflin, J., Hendler, J., and Luke, S. 1998. Reading between the lines: using SHOE to discover implicit knowledge from the web. In AI and Information Integration, Papers from the 1998 Workshop. (WS-98-14). AAAI Press. 51-57.
- Abstract:
- This paper describes how SHOE, a set of Simple HTML Ontological Extensions, can be used to discover implicit knowledge from the World-Wide Wide Web (WWW). SHOE allows authors to annotate their pages with ontology-based knowledge about page contents. In previous papers, we discussed how the semantic knowledge provided by SHOE allows users to issue queries that are much more sophisticated than keyword search techniques, including queries that require retrieval of information from many sources. Here, we expand upon this idea by describing how SHOE's ontologies allow agents to understand more than what is explicitly stated in Web pages through the use of context, inheritance an dinference. We use examples to illustrate the usefulness of these features to Web agents and query engines.
- A Revised Comparison of Crossover and Mutation in Genetic Programming
-
- Authors:
- Sean Luke and Lee Spector
- Note:
-
This paper is a revision of a previous paper, with statistical correction and a considerable new set of data. However, the original also has some data that does not appear here, so you may want to consider getting both.
Also: Figures 1 through 4 are separated from the rest of this paper (they're not that big though). Be certain to get them as well as the paper itself. Finally: if you downloaded a copy of this paper prior to May 20, 1998, its graphs were wrong; get the revised revised version. :-)
- Formats:
- Gzipped Postscript (.ps.gz) without Figures 1-4.
Figures 1 through 4, as Gzipped Postscript (.ps.gz)
The whole paper as PDF
- Citation:
- Luke, S. and L. Spector. 1998. A Revised Comparison of Crossover and Mutation in Genetic Programming. In Proceedings of the Third Annual Genetic Programming Conference (GP98). J. Koza et al, eds. 208-213. San Fransisco: Morgan Kaufmann.
- Abstract:
- In [Luke and Spector 1997] we presented a comprehensive suite of data
comparing GP crossover and point mutation over four domains and a wide
range of parameter settings. Unfortunately, the results were marred by
statistical flaws. This revision of the study eliminates these flaws,
with three times as much the data as the original experiments had. Our
results again show that crossover does have some advantage over mutation
given the right parameter settings (primarily larger population sizes),
though the difference between the two surprisingly small. Further, the
results are complex, suggesting that the big picture is more complicated
than is commonly believed.
-
Genetic Programming Produced Competitive Soccer Softbot Teams for RoboCup97
-
- Author:
- Sean Luke
- Note:
-
This paper is similar to an earlier workshop paper.
The key difference being that the workshop paper, which was not for a
Genetic Programming audience, is short on experimental details and long
on introductions to how GP works. There also exists a
short invited paper
detailing how this experiment could have been improved.
Also available is a short sidebar
for an AI Magazine article.
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
- Citation:
- Luke, S. 1998. Genetic Programming Produced Competitive Soccer Softbot Teams for RoboCup97. In Proceedings of the Third Annual Genetic Programming Conference (GP98). J. Koza et al, eds. 204-222. San Fransisco: Morgan Kaufmann.
- Abstract:
-
At RoboCup, teams of autonomous robots or software softbots compete in
simulated soccer matches to demonstrate cooperative robotics techniques in
a very difficult, real-time, noisy environment. At the IJCAI/RoboCup97
softbot competition, all entries but ours used human-crafted cooperative
decision-making behaviors. We instead entered a softbot team whose
high-level decision making behaviors had been entirely evolved using
genetic programming. Our team won its first two games against
human-crafted opponent teams, and received the RoboCup Scientific
Challenge Award. This report discusses the issues we faced and the
approach we took to use GP to evolve our robot soccer team for this
difficult environment.
- A Comparison of Crossover and Mutation in Genetic Programming
-
- Authors:
- Sean Luke and Lee Spector
- Superceeded by:
- A Revised Comparison of Crossover and Mutation in Genetic Programming. The revised version has new data which corrects some statistical flaws in the original.
- Note:
-
Figures 1 through 4 of this paper are very large, and so have been separated from the paper below.
- Formats:
-
Gzipped Postscript (.ps.gz) without Figures 1-4
Figures 1 and 2 alone, in Gzipped Postscript (.ps.gz)
Figures 3 and 4 alone, in Gzipped Postscript (.ps.gz)
The whole paper as PDF
- Citation:
- Luke, S. and L. Spector. 1997. A Comparison of Crossover and Mutation in Genetic Programming.
In Genetic Programming 1997: Proceedings of the Second Annual Conference (GP97).
J. Koza et al, eds. San Fransisco: Morgan Kaufmann. 240-248.
- Abstract:
-
This paper presents a large and systematic body of data on the relative
effectiveness of mutation, crossover, and combinations of mutation and
crossover in genetic programming (GP). The literature of traditional
genetic algorithms contains related studies, but mutation and crossover in
GP differ from their traditional counterparts in significant ways. In
this paper we present the results from a very large experimental data set,
the equivalent of approximately 12,000 typical runs of a GP system,
systematically exploring a range of parameter settings. The resulting
data may be useful not only for practitioners seeking to optimize
parameters for GP runs, but also for theorists exploring issues such as
the role of "building blocks" in GP.
- Ontology-based Web Agents
-
- Authors:
- Sean Luke, Lee Spector, David Rager, and James Hendler
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
- Citation:
- Luke, S., L. Spector, D. Rager, and J. Hendler. 1997. Ontology-based Web Agents. In Proceedings of the First International Conference on Autonomous Agents (AutonomousAgents97). W. L. Johnson, ed. New York: Association for Computing Machinery. 59-66.
- Abstract:
- This paper describes SHOE, a set of Simple HTML Ontology Extensions which
allow World-Wide Web authors to annotate their pages with semantic
knowledge such as "I am a graduate student" or "This person is my graduate advisor". These annotations are expressed in terms of ontological knowledge which can be generated by using or extending standard ontologies available on the Web. This makes it possible to ask Web agent queries such as "Find me all graduate students in Maryland who are working on a project funded by DoD initiative 123-4567", instead of simplistic keyword searches enabled by current search engines. We have also developed a web-crawling agent, Exposée, which interns SHOE knowledge from web documents, making these kinds queries a reality.
-
Evolving Teamwork and Coordination with Genetic Programming
-
- Authors:
- Sean Luke and Lee Spector
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
Postscript (.ps)
- Citation:
- Luke, S. and L. Spector. 1996. Evolving Teamwork and Coordination with Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference.. J. Koza et al, eds. Cambridge: MIT Press. 141-149.
- Abstract:
- Some problems can be solved only by multi-agent teams. In using genetic
programming to produce such teams, one faces several design decisions.
First, there are questions of team diversity and of breeding strategy.
In one commonly used scheme, teams consist of clones of single individuals;
these individuals breed in the normal way and are cloned to form
teams during fitness evaluation. In contrast, teams could also consist of
distinct individuals. In this case one can either allow free interbreeding
between members of different teams, or one can restrict interbreeding
in various ways. A second design decision concerns the types of
coordination-facilitating mechanisms provided to individual team members;
these range from sensors of various sorts to complex communication systems.
This paper examines three breeding strategies (clones, free, and restricted)
and three coordination mechanisms (none, deictic sensing, and name-based
sensing) for evolving teams of agents in the Serengeti world, a simple
predator/prey environment. Among the conclusions are the fact that
a simple form of restricted interbreeding outperforms free interbreeding
in all teams with distinct individuals, and the fact that name-based
sensing consistently outperforms deictic sensing.
- Cultural Transmission of Information in Genetic Programming
-
- Authors:
- Lee Spector and Sean Luke
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
- Citation:
- Spector, L. and S. Luke. 1996. Cultural Transmission of Information in Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference.. J. Koza et al, eds. Cambridge: MIT Press. 200-208.
- Abstract:
-
This paper shows how the performance of a genetic programming system
can be improved through the addition of mechanisms for non-genetic
transmission of information between individuals (culture). Teller
has previously shown how genetic programming systems can be enhanced
through the addition of memory mechanisms for individual programs
[Teller 1994]; in this paper we show how Teller's memory mechanism
can be changed to allow for communication between individuals within
and across generations. We show the effects of indexed memory and
culture on the performance of a genetic programming system on a symbolic
regression problem, on Koza's Lawnmower problem, and on Wumpus world
agent problems. We show that culture can reduce
the computational effort required to solve all of these problems.
We conclude with a discussion of possible improvements.
- Note:
-
Discussion of this paper appeared as part of the Scientific American (Oct. 96) column "Computing: Programming with Primordial Ooze" (p. 50).
- Culture Enhances the Evolvability of Cognition
-
- Authors:
- Lee Spector and Sean Luke
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
- Citation:
- Spector, L. and S. Luke. 1996. Culture Enhances the Evolvability of Cognition. In Cognitive Science 1996 Conference Proceedings (CogSci96).
- Abstract:
- This paper discusses the role of culture in the evolution of cognitive
systems. We define "culture" as any information transmitted between
individuals and between generations by non-genetic means. Experiments
are presented that use genetic programming systems that include special
mechanisms for cultural transmission of information. These systems
evolve computer programs that perform cognitive tasks including mathematical
function mapping and action selection in a virtual world. The data show
that the presence of culture-supporting mechanisms can have a clear
beneficial impact on the evolvability of correct programs. The implications
that these results may have for cognitive science are
briefly discussed.
- Code Growth Is Not Caused By Introns
-
- Authors:
- Sean Luke
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- S. Luke. 2000. Code growth is not caused by introns. In Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference (GECCO-2000). 228-235.
- Abstract:
-
Genetic programming trees have a strong tendency to grow rapidly and relatively independent of fitness, a serious flaw which has received considerable attention in the genetic programming literature. Much of this literature has implicated introns, subtree structures with no effect on the an individual's fitness assessment. The propagation of inviable code, a certain kind of intron, has been especially linked to tree growth. However this paper presents evidence which shows that denying inviable code the opportunity to propagate actually increases tree growth. The paper argues that rather than causing tree growth, a rise in inviable code is in fact an expected result of tree growth. Lastly, this paper proposes a more general theory of growth for which introns are merely a symptom.
- SHOE: A Knowledge Representation Language for Internet Applications
-
- Authors:
- Jeff Heflin, James Hendler, and Sean Luke
- Note:
- A revised version of this paper formed Chapter 2 ("SHOE: A Blueprint for the Semantic Web") of the book Spinning the Semantic Web, edited by Dieter Fensel, James Hendler, Henry Lieberman, and Wolfgang Wahlster. MIT Press. 2003. ISBN 0-262-06232-1
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Also Available As:
- UMCP-CSD Technical Report CS-TR-4078, or UMCP-UMIACS Technical Report UMIACS-TR-99-71, accessible online at the Library of the Department of Computer Science, University of Maryland at College Park.
- Citation:
- Heflin, J. Hendler, and S. Luke. 1999. SHOE: A Knowledge Representation Language for Internet Applications. Technical Report CS-TR-4078. Department of Computer Science, University of Maryland at College Park.
- Abstract:
- It is our contention that the World Wide Web poses challenges to knowledge representation systems that fundamentally change the way we should design KR languages. In this paper, we describe the simple HTML Ontology Extensions (SHOE), a KR language which allows web pages to be annotated with semantics. We present a formalism for the language and discuss the features which make it well suited for the Web. We describe the syntax and semantics of this language, and discuss the differences from traditional KR systems that make it more suited to modern web applications. We also describe some generic tools for using the language and demonstrate its capabilities by describing two prototype systems that use it. We also discuss some future tools currently being developed for the language. The language, tools, and details of the applications are all available on the World Wide Web at http://www.cs.umd.edu/projects/plus/SHOE/
- Coevolving Soccer Softbots
-
- Author:
- Sean Luke
- Note:
- This is a short sidebar about the RoboCup project. A more complete paper can be found here.
- Formats
- Gzipped PostScript (.ps.gz)
PDF
- Citation:
- Luke, S. 1998. Coevolving Soccer Softbots. In AI Magazine 19:3 (Fall 1998), pp. 54.
- First Paragraph:
- The University of Maryland RoboCup simulator entry (Sean Luke, Charles hohn, Jonathan Farris, Gary Jackson, and James Hendler) consisted entirely of computer-evolved players developed with Genetic Programming. Genetic Programming is a branch of evolutionary computation which uses natural selection to optimize over the space of computer algorithms. Unlike other entrants who fashioned fine-tuned softbot teams from a battery of relatively well-understood robotics techniques, maryland's goal was to see if it was even possible to use evolutionary computation to develop high-level soccer behaviors that were competitive with the human-crafted strategies of other teams. While evolutionary computation has been successful in many fields, evolving a computer algorithm has proven challenging, especially in a domain like robot soccer.
- Co-evolving Soccer Softbot Team Coordination with Genetic Programming
-
- Authors:
- Sean Luke, Charles Hohn, Jonathan Farris, Gary Jackson, and James Hendler
- Note:
- This paper has an early original version written before the project was completed, and a later version written after the project and after the RoboCup97 competition at IJCAI97 in Nagoya, Japan. The later version is far better, with corrected and new information, but is also much larger byte-wise. Also available is a short sidebar for an AI Magazine article. There also exists a similar paper written for GP97 which discusses more of the project implementation details but spends little time explaining what Genetic Programming is and how it works. And finally, there exists a
short invited paper
detailing how this experiment could have been improved.
- Formats:
- The early version in Gzipped PostScript (.ps.gz)
The early version in PDF
The later version in Gzipped PostScript (.ps.gz)
The later version in PDF
- Citation (for the early original paper):
- Luke, S., C. Hohn, J. Farris, G. Jackson, and J. Hendler. 1997. Co-evolving Soccer Softbot Team Coordination with Genetic Programming. In Proceedings of the RoboCup-97 Workshop at the 15th International Joint Conference on Artificial Intelligence (IJCAI97). H. Kitano, ed. IJCAI. 115-118.
- Citation (for the later paper -- the preferred citation):
- Luke, S., C. Hohn, J. Farris, G. Jackson, and J. Hendler. 1998. Co-evolving Soccer Softbot Team Coordination with Genetic Programming. In RoboCup-97: Robot Soccer World Cup I (Lecture Notes in Artificial Intelligence No. 1395), H. Kitano, ed. Berlin: Springer-Verlag. 398-411.
- Abstract:
-
Genetic Programming is a promising new method for automatically generating functions and algorithms through natural selection. In contrast to other learning methods, Genetic Programming's automatic programming makes it a natural approach for developing algorithmic robot behaviors. In this paper we present an overview of how we apply Genetic Programming to behavior-based team coordination in the RoboCup Soccer Server domain. The result is not just a hand-coded soccer algorithm, but a team of softbots which have learned on their own how to play a reasonable game of soccer.
- Ontology-Based Knowledge Discovery on the World-Wide Web
-
- Authors:
- Sean Luke, Lee Spector, and David Rager
- Superceeded by:
- Ontology-based Web Agents
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
HTML
- Citation:
- Luke, S., L. Spector, and D. Rager. 1996. Ontology-Based Knowledge Discovery on the World-Wide Web. In Working Notes of the Workshop on Internet-Based Information Systems at the 13th National Conference on Artificial Intelligence (AAAI96). A. Franz and H. Kitano, eds. AAAI. 96-102.
- Abstract:
- This paper describes SHOE, a set of Simple HTML Ontology Extensions. SHOE allows World-Wide Web authors to annotate their pages with ontology-based knowledge about page contents. We present examples showing how the use of SHOE can support a new generation of knowledge-based search and knowledge discovery tools that operate on the World-Wide Web.
- Evolving Graphs and Networks with Edge Encoding: Preliminary Report
-
- Authors:
- Sean Luke and Lee Spector
- Formats:
- Gzipped Postscript (.ps.gz)
PDF
- Citation:
- Luke, S. and L. Spector. 1996. Evolving Graphs and Networks with Edge encoding: Preliminary Report. In Late Breaking Papers at the Genetic Programming 1996 Conference (GP96). J. Koza, ed. Stanford: Stanford Bookstore. 117-124.
- Abstract:
-
We present an alternative to the cellular encoding
technique for evolving graph and network structures
via genetic programming. The new technique, called
edge encoding, uses edge operators rather than the node operators
of cellular encoding. While both cellular encoding and edge encoding
can produce all possible graphs, the two encodings bias
the genetic search process in different ways; each may therefore be most
useful for a different set of problems. The problems for which
these techniques may be used, and for which we think edge encoding may
be particularly useful, include the evolution of recurrent neural
networks, finite automata, and graph-based queries to symbolic knowledge
bases. In this preliminary report we present a technical description of
edge encoding and an initial comparison to cellular encoding.
Experimental investigation of the relative merits of these encoding
schemes is currently in progress.
- Using the Parka Parallel Knowledge Representation System (Version 3.2)
-
- Authors:
- William Anderson, Brian Kettler, Sean Luke, and James Hendler
- Formats:
- Gzipped PostScript (.ps.gz)
PDF
- Also Available As:
- UMCP-CSD Technical Report CS-TR-3485, accessible online at the Library of the Department of Computer Science, University of Maryland at College Park.
- Citation:
- Anderson, W., B. Kettler, S. Luke, and J. Hendler. 1995. Using the Parka Parallel Knowledge Representation System (Version 3.2). Technical Report. Department of Computer Science, University of Maryland at College Park.
- Abstract:
- Parka is a symbolic, semantic network knowledge representation system that takes advantage of the massive parallelism of supercomputers such as the Connection Machine. The Parka language has many of the features of traditional semantic net/frame-based knowledge representation languages but also supports several kinds of rapid parallel inference mechanisms that scale to large knowledge-bases of hundreds of thousands of frames or more. Parka is intended for general-purpose use and has been used thus far to support A.I. systems for case-based reasoning and data mining. This document is a user manual for the current version of Parka, version 3.2. It describes the Parka language and presents some examples of knowledge representation using Parka. Details about the parallel algorithms, implementation, and empirical results are presented elsewhere.