Evolutionary algorithms solve problems by simulating the evolution of a population of candidate solutions. We focus on evolving permutations for ordering problems like the traveling salesperson problem (TSP), as well as assignment problems like the quadratic assignment problem (QAP) and largest common subgraph (LCS). We propose cycle mutation, a new mutation operator whose inspiration is the well known cycle crossover operator, and the concept of a permutation cycle. We use fitness landscape analysis to explore the problem characteristics for which cycle mutation works best. As a prerequisite, we develop new permutation distance measures: cycle distance, $k$-cycle distance, and cycle edit distance. The fitness landscape analysis predicts that cycle mutation is better suited for assignment and mapping problems than it is for ordering problems. We experimentally validate these findings showing cycle mutation's strengths on problems like QAP and LCS, and its limitations on problems like the TSP, while also showing that it is less prone to local optima than commonly used alternatives. We integrate cycle mutation into the open-source Chips-n-Salsa library, and the new distance metrics into the open-source JavaPermutationTools library.
翻译:进化算法通过模拟候选解决方案人群的演变来解决问题。 我们注重于诸如旅行销售人员问题(TSP)等订购问题的不断变化的变异性,以及诸如二次分配问题(QAP)和最大共同子子集(LCS)等分配问题。 我们提议循环突变, 一个新的突变操作者, 其灵感来自众所周知的跨周期操作者, 以及变异周期概念。 我们利用健身环境分析来探索周期变异最有效的问题特征。 作为先决条件, 我们开发新的变异距离测量标准: 周期距离、 美元周期距离和周期编辑距离。 健身环境分析预测周期变异性更适合分配和绘图问题, 而不是命令问题。 我们实验性地验证这些结果, 显示循环在QAP 和 LCSS等问题上的强势, 及其对 TSP 等问题的局限性。 同时显示它比常用的替代方法更不易被本地选取。 我们将循环变异化纳入开放源 Chips- n- Salsa 图书馆, 以及新的远程测量系统 。