遗传算法优化反转排序：精确性提升与Auyeung-Abraham方法比较

本文探讨了反转排序问题在遗传算法求解中的应用，特别是针对无符号排列的复杂性。排序排列逆转是理论计算机科学中的一个难题，尤其是在寻找将一个基因组转换为另一个基因组的最短反转序列时，这个问题具有极高的组合和代数难度。二十年来，尽管平均数逆转等特定问题尚未得到解决，但无符号排列的反转排序问题因其挑战性而备受关注。 作者提出了一种基于Auyeung和亚伯拉罕方法的遗传算法，该方法在处理符号情况时能够生成近似解决方案，并为目标问题提供精确解的一种途径。这种标准遗传算法利用了符号操作，旨在优化搜索过程。为了进一步提升算法性能，文中还介绍了一种改进的遗传算法，通过在初始代引入反转操作并消除两个断点，引入了启发式机制，以提高近似率。 为了控制算法精度，文中开发了一个1.5近似算法的正确实现，作为基准。实验结果显示，改进后的遗传算法和标准算法相比，能够提供更精确的输出，超过了1.5近似算法以及先前已知遗传方法的结果。这些研究是由FAPDFPRONEX和CNPq等机构资助的，展示了对遗传算法在复杂问题求解上的深入探索。 关键词包括排序排列逆转、遗传算法、近似算法，表明这项工作不仅关注理论挑战，也关注实际应用中的效率和精度提升。本文的成果对于理解和优化基因组重排分析，以及相关领域的算法设计具有重要意义。