Simulated Learning and Genetic Programming with Application to Undecidable Problems

Created by W.Langdon from gp-bibliography.bib Revision:1.4420

  author =       "Jinhwa Kim",
  title =        "Simulated Learning and Genetic Programming with
                 Application to Undecidable Problems",
  school =       "University of Wisconsin",
  year =         "2001",
  address =      "Madison, USA",
  month =        "20 " # aug,
  keywords =     "genetic algorithms, genetic programming, TSP",
  URL =          "",
  size =         "201 pages",
  abstract =     "This study suggests two learning-based artificial
                 intelligence approaches for solving undecidable
                 problems, problems characterized by high expense to
                 accurately evaluate the quality of a candidate
                 solution. We show that there are important problems
                 that have this character and that the research
                 literature has largely ignored these types of problems.
                 We build upon the seminal work of Alan Turing and his
                 notion of an undecidable problem. Paraphrasing Turing's
                 definition in our context, a problem is undecidable if
                 it is impossible to accurately evaluate the quality of
                 a candidate solution in known finite time. We expand
                 this notion to include many important and practical
                 problems with the characteristic in quotes above, and
                 give examples. This research endeavours to identify new
                 systematic and effective solution methods for these
                 problems. We define and motivate a particularly
                 important undecidable problem, denoted P, as that of
                 finding an effective algorithm for an NP-hard problem,
                 a focal point for our investigation. We provide a
                 critical analysis of the only known general systematic
                 method for undecidable problems, i.e., statistical
                 theory that guides an experimenter to efficiently
                 design an experiment and interpret the results. Our
                 critical analysis focuses on the strengths and
                 weaknesses of this experimental design (ED) theory for
                 attacking problem P, and indicates the need for a
                 different approach. We propose a biologically motivated
                 approach that can be used for P, among other
                 undecidable problems. Simulated learning (SL) leaves it
                 up to the researcher to select candidate solutions, but
                 provides guidance on new and effective alternative
                 solutions by using schema in the experimental results.
                 SL is akin to response surface methodology (RSM), which
                 uses the history of results to suggest an alternative
                 candidate solution for evaluation. The jagged and
                 complex response surface of problem P likely renders
                 RSM ineffective. Evidence of the potential efficacy of
                 SL in extracting schema from candidate solutions is
                 gained though computational experiments with solving
                 travelling salesperson problems. SL appears to be
                 promising at distilling the schema of this decidable
                 problem with complex structure (i.e., NP-hard). Initial
                 experience with solving an undecidable problem is also
                 provided. We critique automated methods in the
                 literature that can be applied to problem P. This
                 motivates investigation of a genetic programming (GP)
                 approach based on a kernel representation scheme. We
                 specify the kernel in detail and show that it is
                 capable of representing many different search
                 algorithms from the literature. We implement the
                 GP/kernel approach and run computational tests. Our
                 evaluative analysis leads to suggestions for further
                 research on automated methods for undecidable
  notes =        "Supervisors: James G. Morris and Scott Webster

                 UMI Microform 3022972",

Genetic Programming entries for Jinhwa Kim