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. You should write a little essay for each of the two Exercises that you find at the end of each section of the lab. 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:
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 combination ("sex") in which an offspring inherits its rules from two parents.
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 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
- Change the "Plants Grow" setting to "In Rows".
- Change the "Approximate Population" to 30.
- Change the "Mutation Probability" to 0.25%.
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? What behaviors did the populations of Eaters develop? (Give some specific examples.) What happened over the long term? 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 "bable fish", a small fish that creatures all over the galaxy stick in their ears. The bable fish instantly translates speech in any language. Someone with a bable fish in his, her, or its ear can understand any language.
In the real world, the BableFish translation engine is an advanced machine translation system. It can be found at
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 BableFish 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 two out of the following three exercises:
- If you know one of the non-English languages that are available, try translating an English Web page into that language. (This will work even for languages that use non-English alphabets, such as Chinese and Korean.)
- Try translating a Web page in some other language into English. For example, the Web site of the German computer magazine c't is at http://www.heise.de/ct/. Note that links on the translated page will lead to translated versions of the linked pages. You might want to start with the German, French, or Italian editions of Yahoo, which you can find at http://de.yahoo.com, http://fr.yahoo.com, and http://it.yahoo.com.
- A classic test of machine translation is to translate something from English into another language and then back to English. Try it. Note that after the first translation, you can cut and paste the translation into the text input box to do the reverse translation. (A common but unlikely story has "The vodka is good, but the meat is bad" being translated into Russian and back. Supposedly, the result was "The spirit is willing, but the flesh is weak.")
Exercise 2: What is your reaction to the current state of machine translation? How does BableFish 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