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

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

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.