论文标题
完美的边缘传输置换重组
Perfect Edge-Transmitting Recombination of Permutations
论文作者
论文摘要
跨界是重新组合两个父母的遗传特征的过程。对于许多应用于排列的应用，相关的遗传特征是相邻元素对，也称为置换顺序中的边缘。没有错误的边缘的重组被认为是一个NP硬质问题，通常通过引入新边缘或只能产生各种后代的启发式方法来近似。在这里，我们得出了一种用于置换的算法，该算法在二次平均计算时间内，可以实现边缘的完美传输并产生所有可能后代的均匀采样。该算法及其推导揭示了循环跨界（CX）和边缘组装跨界（EAX）之间的联系，并提供了这些良好的算法的新视角。我们还描述了对算法的修改，该算法为不对称旅行推销员问题生成了数学上最佳的后代。
Crossover is the process of recombining the genetic features of two parents. For many applications where crossover is applied to permutations, relevant genetic features are pairs of adjacent elements, also called edges in the permutation order. Recombination of edges without errors is thought to be an NP-hard problem, typically approximated by heuristics that either introduce new edges or are only able to produce a small variety of offspring. Here, we derive an algorithm for crossover of permutations that achieves perfect transmission of edges and produces a uniform sampling of all possible offspring, in quadratic average computation time. The algorithm and its derivation reveal a link between cycle crossover (CX) and edge assembly crossover (EAX), offering a new perspective on these well-established algorithms. We also describe a modification of the algorithm that generates the mathematically optimal offspring for the asymmetric travelling salesman problem.
