Shapiro J L
Department of Computer Science, University of Manchester, Manchester M13 9PL UK.
Evol Comput. 2005 Spring;13(1):99-123. doi: 10.1162/1063656053583414.
This paper considers a phenomenon in Estimation of Distribution Algorithms (EDA) analogous to drift in population genetic dynamics. Finite population sampling in selection results in fluctuations which get reinforced when the probability model is updated. As a consequence, any probability model which can generate only a single set of values with probability 1 can be an attractive fixed point of the algorithm. To avoid this, parameters of the algorithm must scale with the system size in strongly problem-dependent ways, or the algorithm must be modified. This phenomenon is shown to hold for general EDAs as a consequence of the lack of ergodicity and irreducibility of the Markov chain on the state of probability models. It is illustrated in the case of UMDA, in which it is shown that the global optimum is only found if the population size is sufficiently large. For the needle-in-a haystack problem, the population size must scale as the square-root of the size of the search space. For the one-max problem, the population size must scale as the square-root of the problem size.
本文考虑了分布估计算法（EDA）中一种类似于种群遗传动力学中漂移的现象。选择过程中的有限种群采样会导致波动，当概率模型更新时，这种波动会被强化。因此，任何只能以概率1生成单组值的概率模型都可能是该算法有吸引力的不动点。为避免这种情况，算法的参数必须以强烈依赖问题的方式随系统规模缩放，或者必须对算法进行修改。由于概率模型状态上的马尔可夫链缺乏遍历性和不可约性，这种现象被证明对一般的EDA都成立。在UMDA的情况下进行了说明，结果表明只有当种群规模足够大时才能找到全局最优解。对于大海捞针问题，种群规模必须按搜索空间大小的平方根缩放。对于单峰问题，种群规模必须按问题规模的平方根缩放。
