Problem Representation in Genetic Algorithms: Emergence of Genomic Self-Similarity in Location Independent Representations

Annie S. Wu, University of Central Florida

This talk introduces the proportional genetic algorithm (PGA) and discusses the evolution of genomic organization in a PGA.

Knowledge representation is an important issue in the development of machine learning algorithms such as the genetic algorithm (GA). A representation determines what can be expressed, which in turn determines the concepts thatcan or cannot be learned. How a problem is represented in a learning algorithm also defines the shape of the landscape on which a learning algorithm searches which in turn determines the connections between candidate solutions and determine how a learning algorithm traverses the solution space.

Typical binary-encoded GA representations are order-based representations that are compact and efficient but limit the evolvability of the GA. Problems such as positional bias and Hamming cliffs further limit the performance of a typical GA. We analyze the effectiveness of a general, multi-character representation in which information is encoded solely in terms of the presence or absence of genomic symbols on an individual. As a result, the ordering of the genomic symbols is free to evolve in response to other factors, for example, in response to the identification and formation of building blocks. Experimental analyses indicate that when the ordering of genomic symbols in a GA is completely independent of the fitness function and therefore free to evolve along with the candidate solutions that they encode, the resulting genomes self-organize into self-similar structures that favor the desirable property of a positive correlation between the form and quality of solutions.

Speaker Biography

Dr. Annie S. Wu is currently an assistant professor in the School of Computer Science at the University of Central Florida (UCF). She received a Ph.D. in Computer Science and Engineering from the University of Michigan under the guidance of Professors John Holland and Robert Lindsay. Before joining UCF, she was a National Research Council Postdoctoral Associate at the Navy Center for Applied Research in Artificial Intelligence at the Naval Research Laboratory. Dr. Wu has written over 45 peer-reviewed publications in the area of evolutionary computation. Her research has been funded by Intelligent Systems Technology Inc., DARPA, ITT Industries, Naval Research Laboratory,NAWCTSD, and SAIC. She is a member of the Executive Board of the ACM Special Interest Group for Genetic and Evolutionary Computation (SIGEVO) and a member of the editorial boards of the Evolutionary Computation Journal and the Journal of Genetic Programming and Evolvable Machines.