Rosenberg Noah A
Department of Human Genetics and Bioinformatics Program, University of Michigan, 2017 Palmer Commons, Box 2218, 100 Washtenaw Avenue, Ann Arbor, MI 48109-2218, USA.
J Theor Biol. 2005 Nov 7;237(1):17-22. doi: 10.1016/j.jtbi.2005.03.026.
It was recently conjectured by H.A. Orr that from a random initial point on a random fitness landscape of alphabetic sequences with one-mutation adjacency, chosen from a larger class of landscapes, no adaptive algorithm can arrive at a local optimum in fewer than on average e-1 steps. Here, using an example in which the mean number of steps to a local optimum equals (A-1)/A, where A is the number of distinct "letters" in the "alphabet" from which sequences are constructed, it is shown that as originally stated, the conjecture does not hold. It is also demonstrated that (A-1)/A is a sharp minimum on the mean number of steps taken in adaptive walks on fitness landscapes of alphabetic sequences with one-mutation adjacency. As the example that achieves the new lower bound has properties that are not often considered as potential attributes for fitness landscapes-non-identically distributed fitnesses and negative fitness correlations for adjacent points-a weaker set of conditions characteristic of more commonly studied fitness landscapes is proposed under which the lower bound on the mean length of adaptive walks is conjectured to equal e-1.
最近，H.A. 奥尔猜想，从更大一类景观中选取的具有单突变邻接的字母序列随机适应度景观上的随机初始点出发，没有自适应算法能够在少于平均 (e - 1) 步的情况下达到局部最优。在此，通过一个例子表明，到局部最优的平均步数等于 ((A - 1)/A)，其中 (A) 是构建序列所使用的“字母表”中不同“字母”的数量，结果表明，如最初所述，该猜想不成立。还证明了 ((A - 1)/A) 是具有单突变邻接的字母序列适应度景观上自适应行走所采取步数的均值的一个尖锐最小值。由于达到新下界的例子具有一些通常不被视为适应度景观潜在属性的特性——非均匀分布的适应度以及相邻点的负适应度相关性——因此提出了一组较弱的条件，这些条件是更常研究的适应度景观所特有的，据此推测自适应行走的平均长度下界等于 (e - 1)。
