Research Projects
Instructions:
- Submit your project preferences by email to Prof. Simha
by Feb 19, 2000. Submit a list of 3-5 projects in order of priority
(highest first).
- You may wish to talk to a project's supervising professor
for additional detail.
- Although you are not constrained to continue the same project
into the summer, it is recommended that you do so (if you are
planning to stay on in the summer).
Prof. Zhang's projects:
- (Z1) Making single crystals by animated simulated
annealing.
- (Z2)
Modeling fluids with interactive molecular dynamics simulations.
- (Z3) Fractals.
Prof. Simha's projects:
- (S1) String-elasticity as a metaphor for algorithm design.
In this project, you will implement two algorithms
for the well-known Traveling Salesman problem.
The first is the well-known Lin-Kernighan heuristic
whereas the second is an unusual algorithm in that
it uses ideas from the physics of elastic bands
in deriving an algorithm.
Summer follow-on: Improve the elastic algorithm using
suitable decompositions.
- (S2) Visualization of algorithm performance.
In this project, you will implement the simulated annealing
algorithm and the the simulated n-body algorithm for
a location problem. These algorithms are described in
a paper. Then, you will implement a visualization of
the algorithms' progress in Java for a particular type of
input data.
Summer follow-on: Add a genetic algorithm to the project.
- (S3) Delivery-truck scheduling problem.
In this project, you will implement the simulated annealing
algorithm, together with a heuristic of your own
to solve the delivery-truck problem. In this problem,
you are given customer demands, a delivery schedule,
and a map. The goal is to schedule truck routes so
that all deliveries can be made by their delivery times.
Summer follow-on: apply other heuristics such as TABU search.
Prof. Leemis' projects:
- (L1) Computational Probability.
Many problems in probability can be solved easily by
hand. When the problems are slightly modified, however,
they become computationally difficult. The purpose of
this project is to identify such probability problems
and solve them with the computer algebra system Maple
with the aid of a new language known as APPL (A Probability
Programming Language).
Summer follow-on: More work on identifying and solving
these problems.
- (L2) Censoring analysis.
Right-censoring complicates the analysis of a data set of
survival times. There is no known exact method for determining
an interval estimate for a Type I (time) censored sample drawn
from and exponential population. This project evaluates the
various approximate methods via a large-scale Monte Carlo simulation.
Summer follow-on: Extension to other censoring mechanisms
and other distributions.
Prof. Park's projects:
All of my research projects are related to the artificial societies
model. For all these projects you would first add to the model you
are building for the first artificial societies project. What you
would add is "agent reproduction" (as will be discussed in the second
artificial societies lecture). Then, with this new model the projects
are as follows.
- (P1) Disease transmission
Study disease transmission in the artificial society. Each agent
has an immune system, baby agents inherent their immune system from their
parents, there is a fixed "pool" of diseases that circulate within the
artificial society, diseases are spread when the agents are in close
contact, etc. When compared to a disease-free society, what is the
impact of disease on the agent population?
- (P2) Trade
Extend the landscape model to include a 2nd resource, then study
"trade" (economic interaction) within the society. That is, agents
that have lots of one resource but little of the other will engage
in trade with other agents that have an opposite distribution of
resource wealth. What is the steady-state "price" at which this
trade occur?
- (P3) Hunter/gatherer
Extend the agent model to include two types of agents, "hunters" and
"gatherers". The gatherers roam the landscape collecting resource; the
hunters roam the landscape looking for gatherers from which they will
steal resource via "combat" (which can produce agent death). Under
what conditions will the society be able to achieve a stable (non-zero)
population of both hunters and gatherers?
- (P4) Any of the other model extensions discussed in the book by Epstein and
Axtell.
Prof. Trosset's projects:
- (T1) Discrepancy Functionals for Simulation-Based Estimation.
Simulation-based estimation involves comparing a sample generated by an
actual stochastic process with samples generated by stochastic
simulation. The comparison is accomplished by a discrepancy function
that quantifies how much one sample resembles another. Various functions
are possible; for some examples, it may require some ingenuity to develop
an appropriate one. This project will involve performing numerical
experiments that compare the efficacy of various discrepancy functions
and/or developing appropriate discrepancy functions for some unusual
applications. It may be continued this summer and/or as a senior thesis
next year.
- (T2) Direct Search Algorithms for Optimizing Stochastic Simulations.
The numerical optimization community often recommends direct search
algorithms for optimization in the presence of noise. However, recent
theoretical results challenge the propriety of this recommendation. This
project will explore the efficiency of direct search algorithms when
function evaluation is uncertain. It will involve implementing (or
modifying existing implementations of) several direct search algorithms
and performing numerical experiments that document their performance.
It may be continued this summer and/or as a senior thesis next year.
- (T3) Stochastic Approximation Algorithms for Optimizing Stochastic
Simulations.
An important theme of recent research on stochastic approximation is the
premise that gradients should be estimated from as little information as
possible. In contrast, it seems plausible that repeated sampling of the
objective function might result in better estimates and more efficient
algorithms, albeit at greater expense per iteration. Such an algorithm
was proposed by Dupuis & Simha. The central issue is whether it is more
efficient to do many inexpensive iterations or fewer iterations of greater
expense. This project will involve implementing several stochastic
approximation algorithms and performing numerical experiments intended to
shed light on this issue. It may be continued this summer and/or as a
senior thesis next year.
Last modified: Feb 14, 2000