CPSC 120, Spring 2001
Lab 13
Genetic Algorithm / Machine Translation

In today's lab, you will look briefly at two very different types of artificial intelligence. Do this lab using Internet Explorer under Windows. There are no files for you to save, and there is no need to use your Linux account. You should write a short essay for each of the two Exercises. Turn in your answers at the end of the lab.

A Genetic Algorithms Demo

The Genetic Algorithm applies ideas from biological evolution to problem solving on a computer. Evolution is a kind of "learning" in which the knowledge or abilities of a population improve over time. In this lab, you will look at a demo of the Genetic Algorithm in which a population of simulated organisms evolves over a series of generations. To find the demo and an explanation of what it does, go to:

http://math.hws.edu/xJava/GA/

Start up the applet and let it run for a while. You'll see red "Eaters" that can move around in an environment eating green "Plants". Each Eater is very much like a Turing machine. It has an internal state which is represented by a number from 0 to 15. It can "see" the item that is directly in front of it. This item can be either a Plant, another Eater, an empty space, or a wall. At each time step, the Eater makes a move. It can move backwards, move forwards, rotate 90 degrees left, or rotate 90 degrees right. It bases its move entirely on its current internal state and on the item that it sees in front of itself. At the same time, it can change its internal state. Whenever an Eater moves onto a spot that contains a Plant, it eats the plant. At the end of each "year" (250 moves), the Eaters reproduce. Eaters that have eaten more plants have a better chance or reproducing. During the reproduction, there can be mutations in the Eater's rules. This can introduce new behaviors. There can also be genetic recombination ("sex") in which an offspring inherits its rules from two parents instead of one.

The results of all this is that the population of Eaters tends to get better at eating. Even though no individual Eater learns anything during its life, the population as a whole does seem to learn. It might even be called creative in a certain sense, because the behaviors that develop in the population were not programmed in. On the other hand, there are definite limits to what the Eaters can do. No Eater, for example, will ever be able to see what is behind it, and they will never be able to increase the number of their internal states.

Watch the applet for a number of generations. You will see that the Eaters seem to learn new behaviors (such as moving forwards) that make them better at finding and eating plants. A Statistics window shows the average number of plants eaten by each Eater in a given generation. This number will tend to increase with time, as the Eaters learn new behaviors. If you see a star next to one of these numbers, it means that that's the best average seen so far. When you see a few asterisks in a row, it's a good bet that the Eaters have "learned" something new. You can speed up the process by setting the "Speed" menu to "Fastest". At this speed, the world is not drawn, so time goes by very quickly. You can switch back to a slower speed to see how the latest generation of Eaters is behaving.

The "World Design" menu lets you change characteristics of the world. After watching the original world for a while -- and maybe playing with some of the parameters in the "World Design" menu -- set up the following "world": Start from the default settings. (If you've changed some of the settings, close the World window and open a new one.) Then, in the World Design menu:

I have found these settings to have a good probability of leading to interesting and well-defined behaviors over the long term. You can watch for a while and then maybe let it run at fastest speed while you do other things. Look back later, after a few thousand generations, to see what the Eaters have learned.

Exercise 1: What did you observe when you ran the Genetic Algorithms Demo? When you used the settings given above and let the world run for a large number of generations, what behaviors did the populations of Eaters develop? (Give some specific examples.) Would you say that there was any real learning or creativity? Why or why not?

A Machine Translation Demo

In the essential science fiction trilogy, The Hitchhikers Guide to the Galaxy, Arthur Dent encounters the "Babel Fish", a small fish that creatures all over the galaxy stick in their ears. The Babel Fish instantly translates speech in any language. Someone with a Babel Fish in his, her, or its ear can understand any language.

In the real world, the BabelFish translation engine is an advanced machine translation system. It can be found at

http://babel.altavista.com/

The translator will attempt to translate between English and several other languages. There are two ways to use it: You can select the "Text" option and type some text into the box. Select the type of translation you want, such as "English to Chinese" or "Italian to English". Click the "Translate" button. The BabelFish translation will be shown at the top of the next page. Alternatively, you can select the "Website" option and enter the URL for a Web site, such as http://math.hws.edu/eck/cs120/. Select the type of translation you want. When you click the "Translate" button, you'll get a translation of that Web page. (If the page is very long, only part of it will be translated.) Be patient! It might take a little while to get a response.

You should do at least two out of the following three exercises:

Exercise 2: What is your reaction to the current state of machine translation? How does BabelFish do with short phrases? How does it do with sentences and paragraphs? Why do you think translation is so hard? Comment on some of the specific translations that you found.

David Eck, eck@hws.edu, May 2001 and April 2002