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

9508700 Lee摘要研究人员对随机过程的分析很感兴趣，这些随机过程与两种广泛使用的全局优化算法：模拟退火法和遗传算法有关。在一维空间中，经典的模拟退火法可以在连续时间内模拟为具有漂移的扩散过程。给定一个要最小化的函数，漂移项是该函数导数的负数；无穷小的方差，也称为冷却速率，与时间的对数成反比。在较温和的假设下，已经证明了这样的扩散在分布上收敛到一个随机变量，该随机变量的分布集中在要最小化的函数的全局极小值上。研究人员正在研究这样一个猜想，即如果一个人用对称的稳定过程代替布朗运动作为模型中的噪声源，那么一个人可以以与时间成正比的速度冷却某个负幂，这比经典模型所需的对数冷却要快得多。从它的名字可以猜到，遗传算法是基于遗传学的想法。研究人员正在研究遗传算法在最优划分问题上的效率。她还比较了遗传算法和确定性算法的性能。优化问题几乎出现在人类的每一项工作中。企业希望最大化利润，最大限度地降低成本。许多工业机器人被编程，以便机器人在有限的时间内以最小的能量完成其分配的任务。本文研究了两种广泛使用的计算机密集型优化算法：模拟退火法和遗传算法的性能改进方法。例如，模拟退火法已被用于集成电路的计算机辅助设计、图像处理和蛋白质结构建模。顾名思义，模拟退火法是一种基于退火法物理过程中的概念的算法，在退火法中，物质被加热，然后缓慢冷却。遗传算法模仿了达尔文进化论中的“适者生存”的概念。

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.