Semester A, 2002-2003

Lecturer: Prof. Moshe Sipper

Projects must be submitted by the end of the semester: Friday, January 17, 2003.

Project Assignment

• Itay Gofer: Ants
• Ayelet Eltahan, Ornit Hochman: Coevolution
• Michael Kaufman, Omer Caspi: Braitenberg
• Inbal Gal, Pavel Grabarnick: DNA Computing
• Amit Barzilai: Self-replication
• Polina Koslitzky: Braitenberg
• Joshua Kraer, Amit Kazmirsky: Genetic Programming / Genetic Algorithms
• Doron Eitan, Aliza Hason: Self-replication
• Sariel Tidhar: Coevolving CAs
• Or Arieli, Yariv Barak: Ants
• Offir Gonen: GA for solving Guards in Gallery Problem
• Sharon Darie: Self-rep or ants

Course Description

• Students will work on software projects in the area of bio-inspired computing (evolutionary computation, cellular computing, artificial self-replication, cellular automata, and more) and artificial life.

Manadatory Reading

• Introductory Paper on Evolutionary Algorithms

General Reference

• Machine Nature: The Coming Age of Bio-Inspired Computing

Administrative Details

• Web: http://www.cs.bgu.ac.il/~sipper/courses/topicsai02a/.
• Prerequisite: Complexity, Algorithm Design, Data Structures
• Credits: 2.
• Time: Wednesday 12-14.
• 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 seven sections:
  1. A short introduction of the domain being investigated
  2. A description of the problem or phenomenon studied
  3. An explanation of the methods and algorithms employed
  4. A description of your programmed system
  5. An account of the results obtained
  6. Some interesting conclusions
  7. Bibliographic references

List of Projects:

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. Coevolving nonuniform 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/Competitive 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.
   J. Paredis, (1996c), Coevolutionary Computation, Artificial Life Journal, Vol. 2, No. 4.
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. 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.)
7. 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.
8. Work with Khepera robots.
9. Genetic programming (working with one of the existing packages). See paper by Brad Dolin, J.J. Merelo available from Kluwer Online (a copy is available here).
10. Adaptive environmentics.
11. DNA Computing simulator.