COSC 6367 --- Evolutionary Programming ( Dr. Eick )


The Joy of Living - Max Ernst (1936)

2012 Course Summary

Evolutionary Computing studies a wide range of problem-solving techniques which are based on principles of biological evolution, such as natural selection and genetic inheritance. These techniques are currently widely applied to a variety of problems, ranging from practical applications in industry and commerce to leading-edge scientific research.

The course will be giving an introduction to evolutionary computing and discuss the application of evolutionary computing to search, optimization, machine learning, design, simulation of evolution in biological and other systems, and art. It will also provide a sound introduction to related fields, namely search and numerical optimization. Moreover, we will take a closer look at approaches which try to understand what rules guide the evolution of complex systems, such as the evolution of cities, and at work which centers on developing agent-based systems which solve problems collaboratively. In particular, in the part of the course agent-based modeling and simulation, software platforms for agent-based modelling, and swarm intellgence approaches will be covered.

The course is quite "hands-on" and project-oriented and with less emphasis on exams; there will be will be a final exam and two review-style quizes. As the course covers a smaller field more time will be allocated to explaining principles and applications of evolutionary computing in more depth, and in assisting students with the course projects. There will be 3 course projects, including a group project which count 50% towards the course grade. The course exam and the two quizzes ount 49% towards the course grade, and 1% are allocated to attendance and extra credit. Overall, the workload for the course will be less than for the Data Mining course I teach every fall semester (about 75%, is my best guess).

News COSC 6367

Course Information Spring 2012

Syllabus: Link to Spring 2012 COSC 6367 Syllabus
Prerequisites: the course is more or less self-contained, students should have sound programming skills; students can use programming languages of their own preferences in course project.
Focus: Theory and application of evolutionary programming and other related areas in evolutionary and natural computation centering on genetic algorithms and programming, evolution strategies, classifier systems, artificial life, and other models that rely on evolutionary principles. Students will perform course projects that apply the discussed techniques to optimization problems, to develop adaptive systems, to the simulation of biological and cultural systems, and to producing computer art.
Teaching Philosophy: The course will be very project oriented; you will develop medium-sized software systems that employ evolutionary computing paradigms in 3 course projects. Alternatively, you can choose to investigate a subject and give a oral presentation (+ report or webpage) as your third project. In addition to regular lectures there will be a lot of project related discussions during the lectures.
Textbook: A.E Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, second edition or later, 2007 or later (Eiben Textbook Transparencies)

The 6367 Team

Instructor: Dr. Christoph F. Eick
Office hours: TU 2-3:15p and TH 1-1:45p in 589 PGH
e-mail: ceick@uh.edu
TA: Zechun Cao
Office hours: TU/TH 9:30-10:30a (in 313 PGH)
Zechun's 6367 Website
TA Email: zechun.eps12@gmail.com
6367 Google News Group

Tentative 2012 Course Schedule

Quiz1: Th., March 8
Quiz2: Tu. April 10
Final Exam: Tu., May 8, 11a(!)-1:10p
Deadlines:
Project 1: March 1
Project 2: Short report on April 18, 15-25 minute demos on April 19
Project 3: Fr., May 4, 11p (submit your report to both Zechun and Dr. Eick

2012 Reviews

Feb. 28 Review1 Questions and Answers
Review2 on March 6 will go through the search algorithms introducted earlier
April 5 Review3 (will mostly discuss the Swarm Intelligence Book Chapter)
May 1 Review4 (will go through some older final exam questions and will discuss the solutions to Quiz2)

2012 Class Transparencies

Course Organization and Introduction Evolutionary Computing:
Course Information (Part1,Part2)
Knapsack Problem (will be used as an example for how EC works).
Obitko.com Tutorial (will be used to demo some EC systems)
Example Applying EC to the Travelling Salesman Problem

Survey Evolutionary Computing:
Eiben Chapter1
Eiben Chapter2
Student February 2010 Questions
Eiben Chapter3 Genetic Algorithms
Overview ES
Eiben Chapter4 Evolution Strategies
Eick on Using EC for Transportation Problems
Project1-07
Eiben Chapter6 Genetic Programming
2003 Koza & Poly Genetic Programming Tutorial
A Field Guide to Genetic Programming
Review of Popular Search Techniques (Search1, Search2, Search3)
What is Unique about EC---if Compared with Other Search Teachniques?
Eiben Chapter8 Parameter Control
On Numerical Optimization Problems
Constraints Handling in Numerical Optimzation (Tutorial by Cuello; added in 2012; slides 1-28, 38-41, 49-51, 59 and 79-81 will be discussed in the lecture)

Swarm Intelligence/Agent-based Modeling:
Book Chapter on Swarm Intelligence by D. Corne, A. Reynolds, and Eric Bonabeau (please read the whole chapter, except you can skip Section 3.1 as Ant Colony Optimization will not be discussed in COSC 6367; moreover, there are slides associated with that article: Dr. Eick's Discussion of the Book Chapter and Particle Swarm Optimization (PSO)---which might be worth to look at)
Overview what will be covered about Swarm Intelligence and Agent-based Modeling
Swarm Intelligence: Nature's way to system engineering (We will scan through first 25 slides of this excellent introductory tutorial on Swarm Intelligence by Gianni Di Cara from the University of Lugano in Switzerland)
Wikipedia on Agent-based Models
Macal&North's Introduction to Agent-based Modeling and Simulation (just look at slides 1-10 and 24-30)
Drogoul's Introduction to Agent-based Systems (slightly better and more up-to-date than the Macal/North-Introduction; slides 5, 11-12, 19-22, 27-34, 37, and 49-52 will be covered in the lecture on April 3, 2012)
Introduction NetLogo Agent-based Modeling Package
Swarm Robots (Swarmanoids are swarms of interacting, diverse robots; a Smarmanoids video can be found at Marco Dorigo's Website, Havard's Kilobot Website---Kilobots a very small and cheap swarm robots and Robots which fly and collaborate---watch demonstration which starts at 10:43)
Introduction to Swarm Intelligence and its Application to Optimization (subset of slides (numbers 1-25, 38, 47-50, 63) of a tutorial of Li and Engelbrecht are used in the lecture)

More on Evolutionary Computing:
Eiben Chapter9 (Spatial Considerations)
Eiben Chapter13 (Evolutionary Art)
Eiben Chapter11 Theoretical Foundation of EC
Co-Evolution (might or might not be discussed based on time)
Eiben Chapter10 (Memetic Alg.; might not be covered in 2012)

Evolutionary Learning:
Dr. Eick's Introduction to Machine Learning with EC
XCS Tutorial by Stewart Wilson (in pdf-format)
Bull Paper Review
Introduction to Reinforcement Learning
Probabilistic Model Building Genetic Algorithms
Learning to Predict and Classify ( added on April 18, 2010)

Miscellaneous:
Introduction to Artificial Life
Brief Introduction to Soft Computing (only the first 11 transparencies will be used)
Will Brown's Presentation on Useful AI Techniques
Teaching Material of the Spring 2001 Teaching of Evolutionary Programming

2012 Course Projects

Project1

Project2 (Deliverables and Deadlines: A short report (discussing 1. Project2 Goals 2. Approach Chosen 3. Summary) will be due on April 18 and groups will survey and demo their work during the class on April 19) will be a group project and will focus on emergent behavior, swarm intelligence, and agent-based modeling and simulation in general and on simulating the behavior of wolf packs (also see A Day of a Wolf in a Wolf Pack, WolfQuest Game, Example Wolf-Sheep-Grass Simulation, Swarm Behavior) in particular. Activities will start after Spring break, but it would be great, if you could do little reading during Spring break. Likely, we will use REPAST in the project, although groups might also consider NetLogo to implement their agent-based modeling and simulation systems; NetLogo models can be imported into REPAST.

Project 3

Grading

Students will be responsible for material covered in the lectures and assigned in the readings. All assignment and project reports are due at the date specified. No late submissions will be accepted after the due date. This policy will be strictly enforced.
Seveal times during the semester I will check class attendance at randomly chosen dates, and an attendence score will be computed from how many of the those lectures you attended.

Translation number to letter grades:
A:100-90 A-:90-86 B+:86-82 B:82-77 B-:77-74 C+:74-70
C: 70-66 C-:66-62 D+:62-58 D:58-54 D-:54-50 F: 50-0

Only machine written solutions are accepted (the only exception to this point are figures and complex formulas) in the assignments. Be aware of the fact that our only source of information is what you have turned in. If we are not capable to understand your solution, you will receive a low score. Moreover, students should not throw away returned assignments or tests.

Students may discuss course material and homeworks, but must take special care to discern the difference between collaborating in order to increase understanding of course materials and collaborating on the homework / course project itself. We encourage students to help each other understand course material to clarify the meaning of homework problems or to discuss problem-solving strategies, but it is not permissible for one student to help or be helped by another student in working through assignment problems and in the course project. If, in discussing course materials and problems, students believe that their like-mindedness from such discussions could be construed as collaboration on their assignments, students must cite each other, briefly explaining the extent of their collaboration. Any assistance that is not given proper citation may be considered a violation of the Honor Code, and might result in obtaining a grade of F in the course, and in further prosecution.

Useful Links Spring 2010

  • Bull's "Introduction to Learning Classfier Systems; Butz' XCS Software
  • Hitchhiker's Guide to Evolutionary Computing
  • Biologically Insprired Robotics Network (Biro-net aims to understand the underlying mechanisms that allow natural and robotic agents to adapt and survive in uncertain and dynamic environments).
  • DEMO (Dynamic and Evolutionary Machine Organization)
  • On Genetic Drift
  • Reinforcement Learning Repository at UM Amherst (reinforcement learning and classifier systems have a lot in common)
  • Epimorph Virtual Creatures(Video, general information)---donated by Paul Ledbetter III.
  • Image Creation through Cellular Automata "Ying Yang Fire"

    Previous Quizzes and Exams

    Quiz1 2012 (Answer Sheet for Quiz1)
    Quiz2 2012 (Solution Sketches for Quiz2)
    Quiz2 2010 (Quiz2 in 2010)
    Quiz1 2008 (Answer Sheet for Quiz1)
    Quiz2 2008 (Answer Sheet for Quiz2)
    Quiz1 2007 (Answer Sheet for Quiz1)
    Quiz2 2007 (Answer Sheet for Quiz2)
    2010 Final Exam with Solution Sketches
    2007 Final Exam
    2008 Final Exam
    Solution Sketches 2012 Final Exam

    EC Software

    Jing Zhang's Survey EC Programming Environments
    Java Genetic Algorithm Library---you are allowed to use this library or any other library for the course programming projects---donated by Abraham Bagherjeiran.
    ECJ---a Java-based EC Research systems (GMU)
    Discipulus Genetic-Programming Software
    Sipper's Genetic Programming for Games
    LISP-Code of a "simple" Symbolic Regression System that employs Genetic Programming. To run the system save the file as gp.l, login into a Sun-workstation and type:
    akcl
    (load "gp.l")
    (run-gp 30 #'eval1)
    (bye)

    Journals, Conferences, and Books

    Evolutionary Computation Journal

    2007 Projects

    Project1: Project1 Specification, Supplement to the Specification of Project1. Moreover, Paul Ledbetter used an optimization package to obtain the following "optimal" solutions for cost-function1 --- the linear cost function. Solutions for the Quadratic Transporatation Problem (generated by Justin Thomas).
    Project2: Specification
    Project3: Specification

    2010 Projects

    Project1: Solving Balanced Transportation Problems (What to submit no later than March 6, 11p to Chun-sheng)
    Project2: Survey on a Subfield of Evolutionary Computing (group project; each group will investigate a different theme)
    Project3: Learning to Predict with Genetic Programming

    2008 Projects

    Project1: Travelling Salesman
    Project1 Specification
    TSP Benchmark

    Project2: Developing Adaptive Systems

    Project3 2008

    last updated: May 13, 2012




    created by YingYangFire