Mathematical Sciences: Stochastic Models for Simulated Annealing and the Genetic Algorithm

点击翻译按钮获取中文摘要

9508700 Lee Abstract The investigator is interested in the analysis of stochastic processes which are connected to two widely-used algorithms for global optimization: simulated annealing and the genetic algorithm. In one dimension, classical simulated annealing can be modeled in continuous time as a certain diffusion process with drift. Given a function to be minimized, the drift term is the negative of the derivative of that function; and the infinitesimal variance, also called the rate of cooling, is inversely proportional to the logarithm of time. Under mild assumptions, it has been shown that such a diffusion converges in distribution to a random variable whose distribution is concentrated on the global minima of the function to be minimized. The investigator is studying the conjecture that if one uses a symmetric stable process in place of Brownian motion as the source of noise in the model, then one can cool at a rate proportional to time to a certain negative power, which is much faster than the logarithmic cooling required in the classical model. The genetic algorithm, as might be guessed from its name, is based on ideas from genetics. The investigator is investigating the efficiency of the genetic algorithm for the optimum partitioning problem. She is also comparing the performance of the genetic algorithm with deterministic algorithms. Optimization problems occur in almost every human endeavor. Businesses want to maximize profits and minimize cost. Many industrial robots are programmed so that the robot will accomplish its assigned task with a minimum amount of energy within a finite time period. This research studies ways to improve the performance of two widely-used computer-intensive algorithms for optimization: simulated annealing and the genetic algorithm. Simulated annealing has been used, for example, in computer-aided design of integrated circuits, in image processing, and in modeling the structure of proteins. As its name suggests, simulated annealing is an algorithm based on concepts from the physical process of annealing, where a substance is heated and then cooled slowly.. The genetic algorithm imitates the concept of "survival of the fittest" from Darwinian evolution.