Semester B, 2001-2002

Lecturer: Prof. Moshe Sipper

Projects must be submitted by the end of the semester: Friday, June 21, 2002.

Course Description

Manadatory Reading

• Introductory Paper on Evolutionary Algorithms

List of Projects (constantly updated):

1. Searching for Solutions to the Traveling Salesman Problem (TSP) using an Algorithm Simulating a Nest of Ants.
   Source: Dorigo M., V. Maniezzo & A. Colorni (1996). The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1):29-41.
2. Genetic Art: Creating Computer Images via Evolution.
   Source: K. Sims, Artificial Evolution for Computer Graphics, Computer Graphics, Vol. 25, No. 4, July 1991, pp. 319-328.
3. Co-Evolving Non-Uniform Cellular Automata to Perform Computations.
   Source: M. Sipper, Co-Evolving Non-Uniform Cellular Automata to Perform Computations, Physica D, vol. 92, pp. 193-208, 1996.
4. Cooperative Coevolution.
   Source: M. A. Potter and K. A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, Vol. 8, No. 1, Spring 2000.
5. Self-Replicating Loops.
   Source: H. Sayama A New Structurally Dissolvable Self-Reproducing Loop Evolving in a Simple Cellular Automata Space, Artificial Life, Vol. 5, No. 4, Fall 1999.
   More information can be found here.
6. Using Self-Replicating Loops to Solve the (NP-Complete) Problem of Satisfiability.
   Source: H.-H. Chou and J. A. Reggia, Problem Solving During Artificial Selection of Self-Replicating Loops, Physica D, Vol. 115, No. 3-4, 1998, pp. 293-312. The abstract is available here, and the article itself can be photocopied at the central library.
   Also read the following article about the Trend environment.
7. A Simulator for Braitenberg Vehicles (a series of simulated robots, going from very simple ones to more complex ones).
   Source: V. Braitenberg, Vehicles: Experiments in Synthetic Psychology, The MIT Press, 1984, Cambridge, Massachusetts. (A small, beautifully written book.)
8. Select a hard problem you've encountered during your computer-science studies, and attempt to solve it with a genetic algorithm.
   Source: M. Tomassini, Evolutionary Algorithms.
9. A Java Applet Demonstrating the Workings of a Genetic Algorithm (must work in browser mode).
   Source: M. Tomassini, Evolutionary Algorithms.

Administrative Details

• Course reference: 202-1-4791.
• Web: www.cs.bgu.ac.il/~sipper/courses/topics02b/.
• Prerequisite: The course is intended for third-year students.
• Credits: 2.
• Time: Monday 10-12.
• Place: Building 34, Room 9.
• Grade:
  • 70%: Project evaluation.
  • 30%: Final report.
• Students may work on their own or in pairs.
• The final report (between 10-20 pages) should include the following sections:
  • a short introduction of the domain being investigated;
  • a description of the problem or phenomenon studied;
  • an explanation of the methods and algorithms employed;
  • a description of your programmed system;
  • an account of the results obtained;
  • (hopefully...) some interesting conclusions;
  • bibliographic references.