分析哈明空间中突变与重组的有益概率,优化进化算法参数。
Analysis and Optimization of Probabilities of Beneficial Mutation and Crossover Recombination in a Hamming Space
- 基于几何与组合分析推导出距离最优解球面间的转移概率。
- 发现突变最优半径随距离增加而减小,近优解处进化变慢。
- 重组在群体子空间内平衡有益/有害概率,可加速近优解搜索。
受费希尔几何模型启发,本文分析了任意有限字母表下哈明空间中字符串的有益突变与交叉重组概率。将减少到最优解距离的变异视为有益。通过几何与组合分析,推导出围绕最优解的球面间转移概率的闭式表达,完整描述了多代演化中距离变化的马尔可夫过程。这为优化突变与重组算子参数提供了基础。本文推导出使突变与交叉进入最优解的概率最大化的最优突变与重组半径条件。分析揭示两类算子的关键差异:突变可覆盖整个搜索空间,但有益突变概率随距离增加而下降,最优突变半径应随之减小,导致接近最优时进化减速;而重组作用于由当前种群定义的子空间,有益与有害重组概率趋于平衡,其方差在哈明空间中具有平移不变性,表明重组可弥补突变缺陷,提升近优解区域的进化速率。
原文摘要 · Abstract (English)
Inspired by Fisher's geometric approach to study beneficial mutations, we analyse probabilities of beneficial mutation and crossover recombination of strings in a general Hamming space with arbitrary finite alphabet. Mutations and recombinations that reduce the distance to an optimum are considered as beneficial. Geometric and combinatorial analysis is used to derive closed-form expressions for transition probabilities between spheres around an optimum giving a complete description of Markov evolution of distances from an optimum over multiple generations. This paves the way for optimization of parameters of mutation and recombination operators. Here we derive optimality conditions for mutation and recombination radii maximizing the probabilities of mutation and crossover into the optimum. The analysis highlights important differences between these evolutionary operators. While mutation can potentially reach any part of the search space, the probability of beneficial mutation decreases with distance to an optimum, and the optimal mutation radius or rate should also decrease resulting in a slow-down of evolution near the optimum. Crossover recombination, on the other hand, acts in a subspace of the search space defined by the current population of strings. However, probabilities of beneficial and deleterious crossover are balanced, and their characteristics, such as variance, are translation invariant in a Hamming space, suggesting that recombination may complement mutation and boost the rate of evolution near the optimum.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。