首页>
外文会议>IEEE Congress on Evolutionary Computation
>Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem
【24h】
Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem
We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the well-known Max-Min Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.
展开▼
机译:我们提出了一种新的蚁群优化(ACO)算法构建过程,该算法可处理欧氏旅行销售员问题(TSP),该算法可保留实例中点的凸包的排序。该过程的灵感来自对简单进化算法的理论分析,证明在实例的内部点数量不太大的实例上效率更高。我们将构造过程集成到了著名的Max-Min Ant System(MMAS)中,并根据经验表明,对于内部点数不太高的实例,它可以带来更有效的优化。
展开▼