Topics in Modelling, Simulation and Optimization

Assignments

Assignment 1, due Tuesday Aug 16
Draw a graph of the percolation probability vs. seed probability. For an n x n grid, let each site be "on" with probability p. Then, a vertical percolation is said to occur if there is a path from a top-row vertex to a bottom-row vertex that traverses only through "on" vertices. Similarly a horizontal percolation exists if there is a path from a leftmost vertex to a rightmost vertex using only "on" vertices. A percolation exists if either a vertical or horizontal percolation exists. Let Q be the probability that a percolation is found. Since this depends on the seed probability p, we'll write this as Q(p). Your goal is to plot the graph Q(p) vs. p for a 20 x 20 mesh.

Assignment 2, due 10am Tuesday Aug 23
In this assignment, you will implement two algorithms for the Travelling Salesman Problem (TSP). The input to this problem is a list of points in the 2D plane. The objective is to find a tour of minimum length. Since the problem is NP-complete, you will implement two heuristics:

Genetic Algorithm. Implement the genetic algorithm discussed in class. You may use any mutation and crossover ideas of your own that you like.
Heuristic Algorithm. Implement any simple greedy heuristic, for the sake of comparison with the genetic algorithm.

To help you with evaluating the algorithm, I have provided both a test-set generator and a visual interface. Here's what you'll need to know/do:

Your algorithm (in Java) needs to be written in a single class that implements the TSPAlgorithm interface. As you will see, you need to implement your genetic algorithm in one method, and your heuristic in the other.
Note that each 2D point is represented with an instance of the class Pointd.
Download this jar file and unpack. You will see a variety of source files. Compile the file TSP.java (which will result in compiling the others).
To execute, run the file TSP:
```
       java TSP
    
```
Go to the File menu and load your algorithm. For this purpose, a file dialog will appear, showing you the files in the directory. You should click on the .class file corresponding to your algorithms (the one that implements the interface).
On the left side, you will see the the result of your genetic algorithm, and on the right the result from your heuristic. This lets you "eyeball" the effectiveness of each. Click on "Next Test" to try successive tests. You can also change the number of points if you like.
Important: please name your classfile using your username so that if I have all the files in one directory, there will be no confusion.

For your assignment, here's what you need to submit:

Email me your source file.
The results for about 10 test cases using 20 points and 30 points. Report the total cost using both your genetic algorithm and your heuristic. Give me a printout of your reults in class.
An explanation (hardcopy) of your mutation and crossover operators, if you use anything other than the ones described in class.

Assignment 3, due 10am Tuesday Aug 30
In this assignment you will simulate a forest fire and estimate some statistics related to the fire. In doing so, you will examine whether a power law underlies this phenomenon. You will revisit the 2D grid of cells that you used in Assignment 1, except that the grid will now have some dynamics. Consider a 2D grid of cells (such as the one in the Game of Life). Each cell represents a piece of land in a forest where a tree can grow. Initially, trees are randomly scattered through the landscape (i.e., some cells are randomly turned "on"). Here's how the simulation progresses:

The parameter p determines the growback rate of trees. Thus, at each timestep, each cell that doesn't have a tree will now contain a tree with probability p.
Initially, the landscape is empty. It is then populated according to the growback parameter. Thus, approximately p fraction of cells will have a tree initially.
Define a cluster of trees as a subset of trees, such that every pair of trees in the subset are connected by a path that goes through other trees. Here, each cell has four neighbors (not eight), except for cells at the borders of the landscape, which have fewer than four neighbors.
At each step, we simulate "lightning" as follows. Lightning strikes each cell with probability q. If lightning strikes a cell and the cell contains a tree, then the tree catches fire. Generally, q will be less than p.
We will assume instantaneous spread of fire. If a tree catches fire and burns, then all the trees in its cluster (of unburnt trees) catch fire and vanish from the landscape at that time step.
Thus, at each step, zero or more clusters will burn down. after which trees regenerate according to the growback rate. This process repeats indefinitely.
Let B(t) represent the number of trees that get burnt at step t. Similarly, let N(t) be the number of trees that are left standing at time step t (just before growback is applied).

Your goal is to study the following:

Plot N(t) vs. t for a number of different simulation runs. Is there a characteristic pattern that you observe? Can you explain it?
Create a histogram of the values of B(t) - does it follow a power law? What could explain the distribution?
Experiment with different ratios of q / p. What happens when p approaches the percolation threshold?
Name your file with your username, appended with "3" (to indicate that this is the third assignment).

Assignment 4, due 10am Tuesday Sept 6 (Click on this link)

Assignment 5, due 10am Tuesday Sept 13 (Click on this link)

There will be no more assignments beyond this. However, in the following week, I will expect you to start thinking about your project and start exploring ideas. Thus, please try to meet with me in the week of Sept 13 to finalize your project.