Course Information

"Genetic Algorithms and Genetic Programming"

Computer Science 426 (CS 426)

Biomedical Informatics 226 (BMI 226)

Stanford University

Last updated: August 1, 2004

· General Course Information for Course for the Most Recent (Fall 2003) Quarter

· Sources of Software for Genetic Algorithm (GA) and Genetic Programming (GP)

· Sources of Additional Information about Genetic Algorithms (GA), Genetic Programming (GP), and Other Aspects of Genetic and Evolutionary Computation (GEC)

General Course Information for Course for the Most Recent (Fall 2003) Quarter

This course has two main aims.

· First, the course teaches about the subject matter of genetic algorithms and genetic programming and demonstrates the dozens human-competitive results that have been automatically generated in a routine manner with a de minimus amount of pre-supplied human knowledge, analysis, intelligence, and information. These human-competitive results include the automated re-creation of over 21 previously patented inventions and the automated creation of patentable new inventions.

· Second, the course provides experience in the planning, executing, writing up, and evaluating research. During the first half of the course, the genetic algorithm and genetic programming are described, with emphasis of the various different techniques in the field and the wide variety of different types of problems to which these techniques can be applied. Four problem sets provide experience in actually using software for both the genetic algorithm and genetic programming. Before the halfway point in the course, each student proposes an individual project. The proposed project ideas are discussed in one or more individual meetings and one particular project is agreed upon between the instructor and the student. During the second half of the course, the lectures focus on advanced material while the student carries out the agreed project. The student writes up his or her work in the form of a 10-page paper (in the style of a conference paper). At the last meeting of the class, students turn in multiple copies of their papers and each student leaves the last class with four randomly chosen papers from other students. In the one-week take-home final, the student acts as a peer reviewer and writes an individual evaluation of each of the four papers and then writes an overall evaluation ranking the four papers. The student papers are published in a book (which each student receives) that is placed in the Mathematics Library at Stanford University (and posted on-line). Thus, the course provides experience in the entire research sequence (that is, planning, executing, writing up, and evaluating research).

This course was first taught at Stanford in 1988. This course was last offered in fall 2003 quarter at Stanford University as Computer Science 426 (CS 426) and Biomedical Informatics 226 (BMI 226). It has been offered as EE 392K in certain years. Starting in 1993, books containing the Student Papers written by students in this course are available in the Mathematics Library in the Main Quad at Stanford University. These books are also available for purchase from the Custom Publishing Department of the Stanford Bookstore. Student papers from the artificial life course (CS 425) for 1993 and 1994 are also similarly available. PDF files of student papers for Fall 2003 quarter are available on-line. PDF files for student papers for Spring 2002 quarter are available on line.

There is no future scheduling for this course at this time.

	Lecturer	John R. Koza, Consulting Professor (Biomedical Informatics and Electrical Engineering)
	Lecturer Email	koza@stanford.edu NOTE: Be sure to mention “CS 426” in subject line
	Lecturer WWW	http://www.smi.stanford.edu/people/koza/
	Lecturer Phone
	TA	Thom Adams
	TA E-Mail	tadams@stanford.edu NOTE: Be sure to mention “CS 426” in subject line
	Course Web Page	http://www.genetic-programming.com/coursemainpage.html CURRENT STANFORD STUDENTS: Course materials are also available on the Stanford University Course Ware site at https://coursework-f.stanford.edu/coursework/; however, this web page contains additional information, including links to software and other sources of information on the web.
	Class Times	Monday and Wednesday 3:15 PM – 4:30 PM
	Class Location	Thornton 102
	Office Hours	Usually before or after class or by appointment
	SCPD TV and Web	· Broadcast on TV by Stanford Center for Professional Development (SCPD) on a delayed basis at 7:15 PM-8:30 PM on SITN channel E-5
	Prerequisites	No knowledge of biology, genetic algorithms, or genetic programming is assumed. Computer programming ability in some language is necessary for projects.
	Course Structure	· 21 lectures · 4 relatively simple problem sets during first half of course · No mid-term · Student-selected project – to be written up as a 10-page paper (which will be bound into a book after end of the quarter, distributed to all students, and placed in Math/CS Library) · Take home final consisting of reading four 10-page papers written by other students in the class and writing anonymous “peer review” of the four papers · The grade is based (in descending order) on the project paper; the take-home final; the problem sets, and class participation.
	Books	· Goldberg, David E. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley l989. · Koza, John R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: The MIT Press 1992. · There will NOT be any course notes from the Stanford Bookstore
	Library Reserve	Various books and videotapes on reserve are at Math/CS Library (4th floor – Building 380)
	Old Hand-Outs and Returns at end of quarter	· Extra copies of hand-outs and return of items not returned in class will be deposited "Handout Hangout" (HOHO) on the first floor in Venture wing of the Gates Building · Please bring back to class all hand-outs not entirely covered during the lecture in which they were handed out.
	Key Dates	· First lecture – Wed, Sept 24, 2003 · Project proposal approved Wed Oct 29, 2003 · Last lecture - Wed December 3, 2003 · Projects due at 3:15 PM– Wed December 3, 2003—No Extensions!!! · Take-Home Final distributed at end of last class on Wed December 3, 2003 · Take-Home Final due – Wed December 10, 2003 – 3:15 PM · Grades due Tues Dec 16, 2003 · Distribution of course book and paper reviews – Tues Dec 30, 2003

· PDF copy of version A of schedule of lectures and deadlines for course for fall 2003quarter. This schedule is APPROXIMATE and subject to change during the quarter.

· PowerPoint (PPT) file of overview lecture (No. 1 — September 24, 2003) (about 5 Megabytes).

· PDF file of introduction to genetic algorithms (GA) (lecture No. 2 — September 29, 2003)

· PDF file of introduction to genetic programming (GP) (partially covered in lecture No. 3)

· PDF file of supplementary material to accompany Genetic Programming I Video (lectures No. 4, 5, and 6)

· PDF file of lecture on automatically defined functions (ADFs) and computational effort (parts of lecture No. 6 and 7)

· PDF file on introduction to developmental genetic programming (part of lecture No. 9)

· PDF file on introduction to architecture-altering operations in genetic programming (part of lecture No. 10)

· PDF file on introduction to memory and storage in genetic programming (part of lecture No. 10)

· PDF file on introduction to iterations, loops, and recursion in genetic programming (part of lecture No. 10)

· PDF file on handling limited validity structures with genetic algorithms (part of lecture no. 10)

· PDF file on the transmembrane segment identification problem (iteration, memory, and ADFs) (part of lecture no. 10)

· PDF file on assembly code genetic programming and compiling GP (part of lecture No. 11)

· PDF file on time-saving techniques for genetic algorithms and genetic programming (part of lecture No. 11)

· PDF file on parallelization of genetic algorithms and genetic programming (part of lecture no. 12)

· PDF file on evolvable hardware, field-programmable gate arrays, and minimal sorting network problem (part of lecture No. 13)

· PDF file on layout (placement and routing) of analog circuits (part of lecture No. 16)

· PDF file on evolution of antennas by means of genetic algorithms and genetic programming (part of lecture No. 16)

· PDF file on automatic synthesis of circuits — Methods — part 1

· PDF file on automatic synthesis of circuits — Passive Circuits — part 2

· PDF file on automatic synthesis of circuits — Active Circuits — part 3

· PDF file on automatic synthesis of circuits — Novelty-Driven Evolution — part 4

· PDF file on automatic synthesis of circuits — More Passive Circuits — part 5

· PDF file on automatic synthesis of circuits — Parameterized Topologies for Circuits — part 6

· PDF file on automatic synthesis of controllers — Basic material – part 1

· PDF file on automatic synthesis of controllers — Improved tuning rules for PID controllers — part 2

· PDF file on automatic synthesis of controllers — Basic parameterized topologies — part 3

· PDF file on automatic synthesis of controllers — Advanced parameterized topologies — part 4

· PDF file on introductory ideas in molecular biology

· PDF file of lecture on symbolic regression

· PDF file on automatic synthesis of metabolic pathways and genetic networks

· PDF file on evolution of detectors for pattern recognition using genetic programming

· PDF file on cellular location problem using genetic programming

· PDF file on Genetic Programming Problem Solver (GPPS)

· PDF file on comparison on various search and learning algorithms

· PDF file on review of problems in Genetic Programming (1992) book

· PDF file of talk by John Koza on “Importance of Reuse” at Evolvable Hardware (EH-2003) conference in Chicago on July 9, 2003

· PDF file of talk by John Koza on “Emergence of Creativity” at University of Michigan / Santa Fe Institute workshop on emergence in Ann Arbor on November 11, 2003

· PDF copy of Problem Set No. 1 for fall 2003 quarter

· PDF copy of Problem Set No. 2 for fall 2003 quarter

· PDF copy of Problem Set No. 3 for fall 2003 quarter

· PDF copy of Problem Set No. 4 for fall 2003 quarter

· PDF copy of Student Survey page for fall 2003 quarter. Please be sure instructor has this if you did not turn it in during lecture no. 1.

· PDF file of take-home final-exam for fall 2003 quarter

· WORD file of take-home final exam for fall 2003 quarter

· How to Select and Write Up Your Project, including the project selection sheet due Wed Oct 29, 2003

· WORD file with format instructions for your 10-page paper

· PDF file with format instructions for your 10-page paper

· PDF files of student papers for Fall 2003 quarter

· PDF file of guest lecture by Jason Lohn of NASA Ames on evolvable antenna, analog circuits, and field-programmable gate arrays (November 24, 2003)

ST5 antenna evolved by Jason Lohn and his group on Evolvable Systems at NASA Ames

Sources of Software for Genetic Algorithm (GA) and Genetic Programming (GP)

· Genetic Algorithm (GA) software (for use on problem set No. 3 and possible use in projects)

· ILLiGAL (Illinois Genetic Algorithms Laboratory) headed by David E. Goldberg of the University of Illinois

· ILLiGAL has an extensive collection of software available by FTP, including versions of the Simple Genetic Algorithm (SGA) in both PASCAL and C from Goldberg’s 1989 book, messy GA software, and Learning Classifier System (LCS) software. Click on http://www-illigal.ge.uiuc.edu/sourcecd.html

· GENESIS genetic algorithm (GA) software by John Grefenstette

· Instructions (text file) by John Grefenstette

· Explanation (HTML) by Darren Lewis (2002 TA)

· Explanation (PPT) by Thom Adams (2003 TA)

· GENESIS code from the GA ARCHIVE, click on http://www.aic.nrl.navy.mil/galist/

· Open BEAGLE code for both genetic algorithm (GA) and genetic programming (GP)

· Open BEAGLE web page

· EO — Simple Genetic Algorithm (SGA) code in C++

· EO web page

· Click here for an extensive set of links to other genetic and evolutionary computation software in various programming languages.

· Genetic programming (GP) software (for use on problem set No. 3 and possible use in projects)

· ECJ software in Java by Sean Luke of University of Maryland and George Mason University

· ECJ web page

· Explanation (PPT) of ECJ code by Thom Adams (2003 TA)

· Lil-GP software in Java by Bill Punch of Michigan State University

· Explanation (PPT) of Lil-GP by Darren Lewis (2002 TA)

· Additional explanation (HTML) of Lil-GP by Darren Lewis (2002 TA)

· Lil-GP is available from the web site of the GARAGe (Genetic Algorithms Research and Applications Group) at Michigan State University by clicking on http://garage.cps.msu.edu/software/lil-gp/lilgp-index.html

· Dave’s Genetic Programming Code in C (DPGC) by David Andre

· Explanation by David Andre (PDF file)

· DPGC code (tar.gz file) (369 KB, 41 files)

· GP code by Lee Spector of Hampshire College

· PushGP is a genetic programming system that evolves programs in the Push programming language. Visit http://hampshire.edu/lspector/push.html

· LGP is a linear, steady-state genetic programming engine in Common LISP. Visit http://hampshire.edu/lspector/code.html

· MidGP is a Common LISP stack-based genetic programming engine similar to HiGP. Visit http://hampshire.edu/lspector/code.html

· Little LISP software in Genetic Programming (Koza 1992) book

· PDF file on Little LISP software for GP for lecture no. 6 or no.7

· “Little LISP” Computer Code for GP, as contained in 1992 book Genetic Programming (Koza 1992)

· GP code in C++ by Bill Landgon of University College London

· Available by FTP at ftp://cs.ucl.ac.uk/genetic/gp-code/

· GP code in PERL by Bob MacCallum of Stockholm Bioinformatics Center

· PerlGP—strongly typed, grammar based, GPL'd GP in Perl

· Open BEAGLE code for both genetic algorithm (GA) and genetic programming (GP)

· Open BEAGLE web page

· GPLAB is a Genetic Programming toolbox for MATLAB by Sara Silva

· GPLAB web page

· Click here for an extensive set of links to other genetic and evolutionary computation software in various programming languages.

Sources of Additional Information about Genetic Algorithms (GA), Genetic Programming (GP), and Other Aspects of Genetic and Evolutionary Computation (GEC)

· The GA Archives containing software, information about conferences, research groups, and other aspects of the field of genetic algorithms

· To subscribe to the EC-Digest mailing list (an approximately weekly moderated-mail list about all aspects of genetic and evolutionary computation, including information about conferences in the field)

· To subscribe to the GP mailing list (an unmoderated mailing list), send e-mail to genetic_programming-subscribe@yahoogroups.com or visit http://groups.yahoo.com/group/genetic_programming/

General Course Information for Course for the Most Recent (Fall 2003) Quarter

Sources of Software for Genetic Algorithm (GA) and Genetic Programming (GP)

Sources of Additional Information about Genetic Algorithms (GA), Genetic Programming (GP), and Other Aspects of Genetic and Evolutionary Computation (GEC)

Other Links