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.