|
||
| Spring Quarter 1997 | Project Team: | |
| Project Sponsor: | Alp Sendil | (Manager) |
| Gregory Abowd | Enda Sullivan | (Architect) & (QA) |
| Bob Sumner | (Programmer) | |
| Lynn Bacher | (Technical Writer) | |
The DNA project is divided into five major components:
The requirements for these modules have been outlined in the Requirements Document. A graphical overview is show above in Figure 1.
The main access to our project is via a web page, the "voting" page, which is an HTML form (see User Interface below). This page resides on a web server along with the following:
The user selects their three favorite images, ranked first, second, and third, and clicks the "submit" button. When this button is activated, a CGI script takes these votes and updates the corresponding data file for the image. It then increments the vote count file. When the vote count reaches the maximum (currently at 5 votes), the "voting page" is shut down while the "learning process" takes place. The files are locked until the new generation of images is finished.
A start command is then sent to the "learning process". This program reads the nine (9) data files and the nine (9) color map files. The data files contain formulas for fractal images. The formulas are brought together to form new combinations. These new formulas are used to generate nine new images with a "fractal generator".
After the new formulas are generated, they are stored in nine (9) new .frm files. Ten processes are forked using the fractal generation program, xFractInt. The first nine are using the formula files to make the next generation of images for the voting page. The tenth run is to generate a larger image of the "winning" image. The "winner" is the image that had the highest number of votes in the previous voting session.
When then images have been created, they are saved back to the original location on the web server. The files are then unlocked, the "voting page" is refreshed, and new votes can be cast.
Listed below are the requirements we expect our project to meet. We briefly describe how the architecture meets these requirements. For a more detailed explanation of the requirements, see the Requirements Document .
The user is provided with a web page to make selections. A CGI script gathers the information a user inputs. The choices are saved in files on the web server where they can be retrieved by the learning algorithm.
The CGI script sets up the data files so that the learning algorithm can develop the next generation of formulas. A more detailed view of the layout of these data files can be seen below. The learning process combines the data from the files and produces parameters that the fractal generator can use.
The xFractInt program was able to meet our requirements for both color and fractal generation. The color maps will be now be incorporated into the learning algorithm.
Our learning algorithm and fractal generation had to be placed on a separate, more powerful computer. The web server that we can access would not be able to generate ten fractal images in the time frame required.
We used an HTML form to gather information from the user. The layout of the form allows the user to make only three selections.
By using a web page we are able to have simple instructions available to the user. With HTML we are also able to provide additional links to more in depth explanations.
Our web page is located on rossem.cc.gatech.edu [www-int.cc.gatech.edu]. When a user first sees the page, they will see 9 fractal images at the top of the page. The images are numbered from 1 to 9 and are linked to .gif files. More information is given in Permanent Storage about these files.
The images should be presented in a table with clear labels. The background should be light and innocuous, so as to not conflict with the images. Below the table, the user should have the ability to rate an image as first, second, or third choice. The user may submit only 3 choices. In theory, they could pick the same picture as all 3 choices, i.e. they might really like picture 5, in which case they can rate it as first, second and third choice. The HTML prevents them from selecting more than one picture as first or second or third choice, (i.e. there can only be 1 picture for each).
There will be a "submit" button that is clicked when the user has finished making selections. This will start the vote counting process.
There will be 9 image files stored in .gif format. They should be 150 x 100 pixels in dimension. This is to limit the amount of time required at the fractal generation stage. The images are numbered from 0 to 8, because they will eventually end up in a C++ array that is indexed from 0. Each image will be saved in the form, '4s.gif' (where 's' stands for small and '4' the number of the image). These files must be world readable and writeable (chmod 666).
There will be 9 data files associated with each image. For example, the file for image #4 will be called '4.data' - where the '4' corresponds with the picture '4s.gif'. The files will look similar to the format below:
25
4
1 sin 2 0
2 + 3 4
3 z 0 0
4 sqrt 5 0
5 5 0 0
The first line indicates how many votes this particular image has received to date. Each time new fractals are generated, this number is reset to 0. Each vote of 3rd place, would result in this being increased by 5 points, a 2nd place vote, would increase it by 10, and a first place vote would increase it by 15.
Each of the next lines, represent in a tree structure a complete formula to generate that image with the xFractInt program. The second line represents how many nodes are in the tree. The logic is explained in the Learning Algorithm section. These files must be world readable and writeable (chmod 666).
There are also nine color maps associated with each image. For example, the file for image #4 will be called '4.map' - where the '4' corresponds with the picture '4s.gif'. An example map is available for viewing. The three columns represent RGB color values, with the first column being red values, the second is green, and the third is blue. These files cannot contain any text. They should also have at least 256 colors. These files must be world readable and writeable (chmod 666 ).
The file 'vote.count' simply contains the number of votes we have had in the current generation. It starts at 0 and counts 1, 2, 3,...until it reaches the cut off number. Currently set at 4, for a total of 5 votes. This file must be world readable and writeable (chmod 666).
There is a file called 'winner.gif' that is a larger, more detailed version of one of the fractal image. The final size is 640 x 480 pixels. The winning image is generated from the formula of the smaller image that received the most votes. This file must be world readable and writeable (chmod 666).
Again, this is just a state file that just holds the current generation number. This file must be world readable and writeable (chmod 666).
Overview of the Vote Processing Code
Eventually the user makes his/her selections and clicks the submit button, at which point, a perl script will receive the output of the HTML form [via STDIN]. In this form, each picture has a variable name, and the perl script will parse through the output and figure out how many votes each picture received. The script updates the first number in each of the .data files that received a vote. For example if I vote like this:
The first line in the file, '5.data' would be incremented by 15, the first line in the file, '4.data' would be incremented by 10, and the first line in the file, '9.data' would be incremented by 5.
The 'vote.count' file is incremented. When the fifth vote is cast, the perl script knows it is time to update the images. A start message is sent to the learning process. For reasons specific to the internal web server at the COC, the perl script generates an e-mail message which is blank apart from the subject line that says "FRACTAL_VOTE". This mail message is sent to an account, where procmail is running to filter mail.
Upon getting such a message, procmail will call a simple shell script on this account. This will do nothing more than rsh a process on our fractal generation machine. There are 2 reasons for having this script. First we need the process to run on a machine with significant computing power, and there is no way for the webserver to (securely) start a process on that machine. This intermediate layer, while a bit slow, will ensure that the we have permissions to do this, and also prevent us from having to make very insecure .rhosts entries. Ideally, the entire project is contained on one system, eliminating this entire mailing process.
Overview of the Learning Algorithm Code
Overview of the Color Map Code
At this point, the learning has begun. It begins by reading the current .data files and parsing them into an array of tree data structures. The data files are as following:
25
4
1 sin 2 0
2 + 3 4
3 z 0 0
4 sqrt 5 0
5 5 0 0
As we discussed above, the first line is the number of votes. The second line is the number of nodes in the tree structure. Each of the next lines, represent in a tree structure a complete formula to generate an image with the xFractInt program. The logic goes like this:
[Unique ID#] [Contents of node] [ID # of node on left] [ID # of right node]
If the ID# listed for a child is 0, then there is no child there. The above code would create this tree:
Sin
|
|
+
/ \
/ \
z Sqrt
|
|
5
5 4 0 2 1 2 1 25 1.500000 2 12 3 3 25 3.500000
There are 5 votes.
There are 4 nodes in the tree.
Where the following is represented as:
2 = '+' 25 = real number 12 = 'cos'
So this gives us a tree:
+
/ \
/ \
1.5 cos
|
|
3.5
The learning algorithm then uses the number of votes as a percentage of how strong that particular file is (note: all 9 files are read in, none DIE, its just some will have 0 votes which means they have a very high likelihood of dying in the genetic algorithm anyway).
After reading in the 9 files, this program will do the learning process. Basically, it takes a branch from one tree and moves it to another tree. When this process is completed, there will be six new formulas. These formulas are saved with the top three formulas from the previous generation, to files with a .frm suffix.
In the meantime, the color maps are being merged also. When two color maps are combined, their RBG values are read into two arrays. The first array is multiplied by a random percentage. The second array is multiplied by that same percentage minus 1. The elements of the two arrays are added together to produce the new color map. The new color maps are stored back in their original locations.
After the formulas are derived, nine processes are forked using the .gif and .map files as parameters to the program xFractInt. This program generates the final .gif images. These images are then written back to the original locations. A tenth process w as also forked to produce the "winning" image. It is written back to "winner.gif".
The user accesses the DNA project via a web page. The initial web page is the voting page. On the voting page, the user sees nine fractal images. From these images they are able to choose their top three favorites. They are restricted to making only three selections. They do have they ability to cast all of their votes toward one image. In Figure 1, a prototype of the voting page is shown.
Figure 1.
The user then selects their favorites by selecting the image they like under the "First Choice", "Second Choice", and "Third Choice" list boxes. When finished, the user clicks on the "submit" button. The votes are stored in files for each image. The vote count is incremented in its file. The user sees a new screen pop up. This screen tells them how many more votes are needed until a new generation of images is created.
After five sets of votes have been received, the image generation process starts. A screen appears preventing the user from submitting votes. In the future, we may have a graphical version showing the generation progress.
While you are waiting for the new images to generate, you can also view the history page. This page shows previous generations and the winning images from each.
Once the generation is complete, the main voting page returns with new selections available to be judged. The user can now cast votes again. At the same time, the "winning" image (the one with the most votes) is sent to a separate webpage where it can be displayed for viewing.
We envision a framed screen that hangs on the wall. Every hour (or sooner) a new image will be displayed.
DNA Home Page
Last Modified 5/15/97 -- C. Lynn Bacher
(lynn@cc.gatech.edu)
