Research Projects

• 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).

• (Z1) Making single crystals by animated simulated annealing.
• (Z2) Modeling fluids with interactive molecular dynamics simulations.
  
• (Z3) Fractals.
  

• (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.

• (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.

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.
  

• (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