Simulated Learning and Genetic Programming with Application to Undecidable Problems
Created by W.Langdon from
gpbibliography.bib Revision:1.7546
 @PhdThesis{Jinhwa_Kim:thesis,

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 = "https://books.google.co.uk/books?id=ITWcAAAAMAAJ",

URL = "http://search.proquest.com/docview/251815652",

size = "201 pages",

abstract = "This study suggests two learningbased 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 NPhard 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., NPhard). 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
problems.",

notes = "Supervisors: James G. Morris and Scott Webster
UMI Microform 3022972",
 }
Genetic Programming entries for
Jinhwa Kim
Citations