Foundations of Genetic Programming book

FOGP'99 Workshop on
FOUNDATIONS OF GENETIC PROGRAMMING

Bird-of-a-feather Workshop
at the
1999 Genetic and Evolutionary Computation Conference
( GECCO-99 ) 1999

Purpose:

Producing useful theoretical results in genetic programming has been very difficult, although the situation is improving now. In the workshop we want: We will address questions such as:

Are we at the limit of schema-based approaches? Or, how can we extend them? On what sort of questions will they be useful?

How useful is fitness landscape analysis? How can it be bolstered? Where does it have shortcomings in terms of operator analysis? Can new operators overcome these? How could we measure the tradeoff between the computational expense of learning about a problem in order to set up powerful operators versus using that computation to solve it with a generic form of an evolutionary algorithm?

What can we learn from theoretical biology? Topics might include Price's variance theorem, Fisher's fundamental theorem of selection, Wright's theories of evolution in (semi-)isolated (island, demes) populations, punctuated equilibrium and mass extinctions, gene epistastis, etc. Do modern molecular studies of evolution offer any valuable insights?

Hand-designed problems are not well linked to real-world problems. The demonstration or comparison problems (e.g. artificial ant, boolean multiplexer, parity) have the same linkage issue. How can the gap be closed?

How can experimental approaches yield general knowledge? Can we set up a formal methodology researchers can follow to elucidate their results and provide reproduction of results and solid bases for comparison?

On what dimensions could we classify (real world) problems to be approached by GP? What complexity characterizations are most useful? What prevents a useful taxonomy of GP-hardness from being derived? What are the fundamental limitations of search using GP?

Clearly the above is not intended to be an exclusive list and other new theoretical developments are also welcome.

Background:

The theory in evolutionary computation has led and can lead to a very deep understanding of evolutionary algorithms. This understanding is necessary to be able to propose better algorithms, operators and fitness functions, and to understand the fundamental limits of search/optimisation. Developing a theory for GP is therefore of paramount importance to lead this field in the right direction. Also, the theory developed for GP may have lead to breakthroughs in the theory of other evolutionary algorithms based on variable size representations.

Format of Workshop

The 2 hour workshop will consist of 15-minute presentations which will be grouped appropriately. Each group of talks will be followed by 10 minute discussions led by a committee member where the attendees will be asked to help the leader record the findings, suggestions and proposals.

Discussion Documents:

Preface
Jason M. Daida ps Reconnoiter by Candle: Identifying Assumptions in Genetic Programming
W. B. Langdon ps html Linear Increase in Tree Height Leads to Sub-Quadratic Bloat
Peter Nordin, Wolfgang Banzhaf, Frank D. Francone ps Compression of Effective Size in Genetic Programming
Riccardo Poli ps Schema Theory without Expectations for GP and GAs with One-Point Crossover in the presence of Schema Creation
Justinian Rosca ps Genetic Programming Acquires Solutions by Combining Top-Down and Bottom-Up Refinement
Xin Yao ps Universal Approximation by Genetic Programming
Byoung-Tak Zhang ps Bayesian Genetic Programming

Photographs