NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Improving Search Properties in Genetic ProgrammingWith the advancing computer processing capabilities, practical computer applications are mostly limited by the amount of human programming required to accomplish a specific task. This necessary human participation creates many problems, such as dramatically increased cost. To alleviate the problem, computers must become more autonomous. In other words, computers must be capable to program/reprogram themselves to adapt to changing environments/tasks/demands/domains. Evolutionary computation offers potential means, but it must be advanced beyond its current practical limitations. Evolutionary algorithms model nature. They maintain a population of structures representing potential solutions to the problem at hand. These structures undergo a simulated evolution by means of mutation, crossover, and a Darwinian selective pressure. Genetic programming (GP) is the most promising example of an evolutionary algorithm. In GP, the structures that evolve are trees, which is a dramatic departure from previously used representations such as strings in genetic algorithms. The space of potential trees is defined by means of their elements: functions, which label internal nodes, and terminals, which label leaves. By attaching semantic interpretation to those elements, trees can be interpreted as computer programs (given an interpreter), evolved architectures, etc. JSC has begun exploring GP as a potential tool for its long-term project on evolving dextrous robotic capabilities. Last year we identified representation redundancies as the primary source of inefficiency in GP. Subsequently, we proposed a method to use problem constraints to reduce those redundancies, effectively reducing GP complexity. This method was implemented afterwards at the University of Missouri. This summer, we have evaluated the payoff from using problem constraints to reduce search complexity on two classes of problems: learning boolean functions and solving the forward kinematics problem. We have also developed and implemented methods to use additional problem heuristics to fine-tune the searchable space, and to use typing information to further reduce the search space. Additional improvements have been proposed, but they are yet to be explored and implemented.
Document ID
19970026890
Acquisition Source
Johnson Space Center
Document Type
Other
Authors
Janikow, Cezary Z.
(Missouri Univ. Saint Louis, MO United States)
DeWeese, Scott
(Missouri Univ. Saint Louis, MO United States)
Date Acquired
August 17, 2013
Publication Date
June 1, 1997
Publication Information
Publication: National Aeronautics and Space Administration (NASA)/American Society for Engineering Education (ASEE) Summer Faculty Fellowship Program: 1996
Volume: 2
Subject Category
Computer Programming And Software
Accession Number
97N26033
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
Document Inquiry

Available Downloads

There are no available downloads for this record.
No Preview Available