Simulated Annealing Project

Search Using Simulated Annealing and Gradient Descent

This assignment was first created and used for two semesters at the University of Southern California in the Artificial Intelligence Course CSCI561 and CSCI460. Some changes have been made to make this a self-guided project. The original homework can be found cool-ai.com

Problem 1 - Preparation

A major video game manufacture has hired you to figure out how to minimize the amount of sleep their programmers get by adjusting different items in the workspace. For instance, you could:

Turn the amount of caffeine added to their coffee up or down.
Adjust the lights to be brighter or dimmer.
Adjust the average pay up or down.
Make their seats harder or softer.
Turn up or down the volume on the corporate Muzak.
Reduce or increase trace amounts of Xylene in the air.

You can tell how much sleep each programmer is getting based on feedback from a microchip each one has been implanted with in their head. You then have a digital readout with the average amount of sleep for all the programmers.

Problems 1-4

Thinking about methods we have studied so far, what would you do to find the optimal adjustments for the workplace items in order to minimize sleep? Describe how you would implement such a method in this situation.
The video game manufacture asks you if you can guarantee that you will find the absolutely optimal workspace settings such that programmers get the least amount of sleep possible. What do you tell them?
You notice that one of your former TA’s from CS 561 now works at the video game manufacturer and you want to be nice to him. Could you use the same procedure to maximize the amount of sleep each programmer gets?
It turns out one of the officers at the software manufacturer is a real big fan of Charles Darwin. He asks you to figure out a way to do the sleep minimization using a genetic algorithm. How might you change the experiment to use a genetic algorithm? You may assume there are enough programmers and resources at your disposal to carry out such an optimization.
Allowing you to assume this last question is worth no points, is the plight of each programmer more Orwellian or Kafkaesque?

Problem 2 Coding and Experiments

You are a zookeeper in the reptile house. One of your rare South Pacific Tufted Wizzo lizards (Tufticus wizzocus) has just had several babies. Your job is to find a place to put each baby lizard in a nursery. However, there is a catch, the baby lizards have very long tongues. A baby lizard can shoot out its tongue and eat any other baby lizard before you have time to save it. As such, you want to make sure that no baby lizard can eat another baby lizard in the nursery (burp).

For each baby lizard, you can place them in one spot on a grid. From there, they can shoot out their tongue up, down, left, right and diagonally as well. Their tongues are very long and can reach to the edge of the nursery from any location. Figure 1 shows in what ways a baby lizard can eat another.

Figure 1 (A) the baby lizard can attack any other lizard in a red square. Thus it can be seen that a baby lizard can eat another lizard to its top, bottom, left right or diagonal. (B) In this setup both lizards can eat each other.

In addition to baby lizards, your nursery has some trees planted in it. Your lizards cannot shoot their tongues through the trees nor can you move a lizard into the same place as a tree. As such, a tree will block any lizard from eating another lizard if it is in the path. Additionally, the tree will block you from moving the lizard to that location. Figure 2 shows some different valid arrangements of lizards

Figure 2 Both nurseries have valid arrangements of baby lizards such that they cannot eat one another. (A) with no trees, no lizard is in a position to eat another lizard. (B) Two trees are introduced such that the lizard in the last column cannot eat the lizard in the second or fourth column.

You will write a program in c++ that will take in an input file that has an arrangement of lizards and trees and will output a new arrangement of lizards (no you can’t move the trees) such that no baby lizard can eat another one. You will be required to create a program in GNU C++ (g++) that finds the solution. For this project we will use simulated annealing. Additionally, you should be able to run several different test files and give some analysis of your running.

For this using c++ is of course optional. This can easily be done in Java or Matlab.

Input: Your input will start with a single number, n, followed by the n x n nursery. It will have a 0 where there is nothing, a 1 where there is a lizard and a 2 where there is a tree. You will output a new file exactly like the first (except for one extra line, see below), but with the correct lizard positions. So for instance, an input file arranged like figure 2b would look like:

8							
0	0	0	0	0	1	0	0
1	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0
0	1	0	0	2	0	0	1
0	0	0	0	0	0	0	0
0	0	1	0	0	2	0	0
0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0

The name of your input file will be specified as the first command line argument in your program.

Output: At command line an output filename will be specified as the second argument in your program. The output is the last state of your program. If you found a solution, the output file should contain that solution. Else if you did not find a solution, output the last state. You will specify that you found a solution by placing a 1 at the last line of your output. If you found no solution, place a 0. Thus, if your output looks like figure 2a, your output file will look like this:

8							
0	0	0	0	0	1	0	0
1	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0
0	1	0	0	0	0	0	0
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0
0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0
1

(note that the output example shown here does not correspond to the above input example; the two are not related, since, again, you cannot move (or remove) any tree that may be present).

Experiments

Your program will be run on several different input examples and each time should output the solution if one exists. Additionally, keep track of the amount of time your program takes to run, in number of steps. So, you will need to keep a counter that increments by one every time you move one of your baby lizards. Additionally, you will need to be able to change the temperature schedule to find the one that works best. Thus, by keeping track of the number of steps it takes, you can determine which method worked the best.

Note on time restrictions

If your program takes longer than 30 seconds on any of the example problems you're probably not doing this correctly. In reality, this should run quite quickly on a modern computer.

Questions

Why is simulated annealing a good algorithm for this problem? (think about complexity and other considerations)
What would be reasonable temperature decrease schedules to use for this problem? To answer this question you will need to do some search on the web to find which schedules other people have typically been using for various problems solved using simulated annealing. Tell us about at least three different possible schedules. Include equations and function graphs for each schedule as well as the URL from which you found it.
Experiment with the different temperature schedules you found and conduct a comparative analysis, running your algorithm on at least 25 different problems of various sizes each time (that is, create inputs for 25 problems of your choice; then run your program on that same set but each time using a different temperature decrease schedule. It is okay if your program has to be recompiled to select which schedule to use. When you send us your code, just have the best schedule as your default. Motivate your answer with a table showing some measure of performance on your 25 test problems (for example, steps taken) for your different schedules. Like in (2), you should test at least 3 different schedules. Include a conclusion on which schedule seems superior with supporting statistics and illustrations.
In addition to using simulated annealing, could you also have used genetic algorithms to solve this problem? If so, how would you have done it (just explain, you do not have to code), if not, then why?

Project Material

Simulated Annealing material.rar - Rar can be opened with WinRAR

External Links

Optional: Suggestions for Giving this as a Project for a Large Class

This project can also be given to a whole class. If the class is large then it is helpful to automate the handing in and grading of projects. Grading of the coding part can be semi-automated. The idea is to give students a stub of the script you will use to grade their project so that they can check to make sure their project is compatible with your grading scripts. Additioanlly, you might want to download the original project from here given to the students since the infos on this page have been changed for self-guided study. These are the directions we gave the students. They are of course just a suggestion.

Due: By class Day, Date, Time

Guidelines

This assignment has a written and a programming component. You can see how much each part of the assignment is worth by the percentage next to it. For the written part, please turn in typewritten answers. You are not English majors, however blatant spelling and grammatical errors may cost you points, so be sure and run the spell check at least once. Answers on the written part will require justification and a simple yes/no answer will almost certainly garner you little or no points. In general, it is safer to write longer answers than shorter ones, but stay focused as a long but off-topic answer will not work either. This way, we can discern your train of thoughts better and grant partial credit for a wrong answer, if you were on the right track. Graphs must be neat and tidy. Hand-drawn graphs are OK, but computer-drawn graphs (e.g., made with Adobe Illustrator or Microsoft Power Point) are preferred. If you draw a graph by hand, be sure and use a straight edge (ruler) so it looks neat.

For the programming part, you will be provided sample inputs and at least one sample output. Since each homework is checked via an automated Perl script, your output should match the example format exactly. Failure to do so will most certainly cost some points. Since the output format is simple and there is an example on the web, this should not be a problem. Additionally, if your code generates a large number of warnings during compilation, you may lose points, so try and eliminate compile-time warnings. Additionally, your code should be well documented. If something goes wrong during compile and grading, if the fix proves easy, the amount of points lost will be far less. As such, documentation makes fixing easier, so it is to your advantage to do so.

You will be provided with a stub Perl script called “stubby.pl”, which works like the grading Perl script. You can run this script to make sure that your project will work properly. Thus, it is expected that your project will run through the grading Perl script without problems. Pedantically, we assert it will cost you points if your code does not run on the Perl script correctly. You will be able to tell if your output is correct if stubby shows each of the lines from your program output is exactly the same as from the comparison file which shows what output you should be getting.

To run stubby, copy it to your code directory along with the input, output and comparison files. Be sure to be in your code directory then type “perl stubby.pl”. The script is loaded with all sorts of output and feedback, so you should be able to see what it is doing if for some reason it isn’t working for you. If you don’t understand the script and want to know more about Perl, go to http://www.perl.org/.

Small amounts of extra credit (not more than 10% total) are given for all sorts of things. So long as you meet the base homework requirements anything creative, fun, interesting or outright cool will most likely earn you extra credit. What is cool and earns you extra credit is somewhat subjective and bound to the whim of the grader.

Other information

For this assignment and many others you will be required to parse input and output files. To help you out, a file called “proj1.cpp” is in the homework 1 folder on den. This is an example file on how to open, read in and then dump a file back out to disk. You may use parts of this code for your homework if you wish.

To compile this file, try something like:

g++ proj1.cpp -o proj1

Then to run it, try something like:

./proj1 matrix2.mat out2.mat

This will read in the matrix file “matrix2.mat” and dump it back out to another file “out2.mat”.

Handing in the Assignment

Since the class is very large it is important to hand in your homework as directed. The homework is due before class on the due date shown. There are two parts of the homework, which you must hand in. These are:

Your code tar/gzipped in one file. Do not send the binaries. - This should just include your uncompiled code and a readme file called readme.txt. When I run tar/gzip to uncompress your file, it should uncompress into its own directory. To keep things uniform, do not use bzip2. I should then be able to run my stubby Perl script and grade your code. See below on how to tar/gzip your code.
Your written part on paper. You must submit a paper copy either in class or in a drop-box in front of my office in Building (NOTE: the Building building closes at 5:00pm). Late submissions will be noted. Be sure your homework is stapled together and is generally tidy.

Be sure that your name is clearly visible on all material you hand in. To hand in your code you can compress it with tar/gzip with a command like:

tar –czvf my.name.hw1.code.tgz my.name.hw1.code

You might also try:

tar –cvf my.name.hw1.code.tar  my.name.hw1.code

then type

gzip my.name.hw1.code.tar

This will compress the contents of the directory named “my.name.hw1.code” into a single file my.name.hw1.code.tgz. If you need more info on this, try “man tar”.

Electronic Submission of code

Generally it is helpful to have an electronic submission system. However, if you do not, then just skip this.

You need to submit the assignment electronically using the EXACT following command FROM YOUR UnixMachine ACCOUNT.

submit -user csci561 -tag hw1 my.name.hw1.code.tgz

Be sure and substitute “my.name” with your own name. The submit command will immediately respond with a SUCCEEDED if your submission of file "my.name.hw1.code.tgz" is successful. That will be your means to know that your homework has reached the right place. Your submissions will be time stamped, so we will know the exact time when you made the submission.

What exactly is Stubby?

This is very important. We use a Perl script to automate the grading process. Stubby is a Perl script we give to you so that you can check and make sure that your project conforms to specifications. That is, you can use Stubby to make sure that your assignment when handed in will run with our grading script. Thus, we have our own grading script like stubby, which we use to grade your project. By checking to make sure your project works with stubby, you make sure that your project will work with our automated grading script.

It is important to note that we will not use your version of stubby. We have our own script. As such, if you edit stubby to work with your code and not the other way around, this will not be very helpful. Additionally, since there are so many projects to grade, it is imperative that your program work with the grading Perl script. If your program does not work with the grading Perl script you will lose points.

Mundhenk 01:05, 2 February 2007 (UTC)