On genetic algorithms
On genetic algorithms
复制标题
DOI：
10.1145/225298.225326
复制
发表时间：
1995-07
期刊：
影响因子：
--
通讯作者：
E. Baum;D. Boneh;Charles Garrett
中科院分区：
文献类型：
--
作者：
E. Baum;D. Boneh;Charles Garrett
我们分析了称为剔除的遗传类型算法和各种其他算法在我们称为 ASP 的问题上的性能。剔除对于这个问题来说几乎是最佳的，具有高度的噪声容忍度，并且是最著名的方法。 。在某些政权中。我们证明学习伊辛感知的问题可以简化为噪声 ASP。这些结果提供了对 GA 进行严格分析的示例，并深入了解 C、A 何时以及如何击败竞争方法。为了分析遗传算法，我们将其视为一种特殊类型的下鞅。我们证明了这个下鞅上的一些新的大偏差界限，这使我们能够确定算法的运行时间。
We analyze the performance of a Genetic Type Algorithm we call Culling and a variety of other algorithms on a problem we refer to as ASP. Culling is near optimal for this problem, highly noise tolerant, and the best known a~~roach . . in some regimes. We show that the problem of learning the Ising perception is reducible to noisy ASP. These results provide an example of a rigorous analysis of GA’s and give insight into when and how C,A’s can beat competing methods. To analyze the genetic algorithm, we view it as a special type of submartingale. We prove some new large deviation bounds on this submartingale w~ich enable us to determine the running time of the algorithm.