School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, UK
Optimisation and Logistics, University of Adelaide, Adelaide, SA 5005, Australia
Evol Comput. 2016 Spring;24(1):183-203. doi: 10.1162/EVCO_a_00147. Epub 2015 Feb 20.
Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem and the generalised travelling salesperson problem in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl ( 2012 ) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) evolutionary algorithm working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the problem can be solved in fixed-parameter time with the global structure representation. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently. For the generalised travelling salesperson problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) evolutionary algorithm working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.
双层优化问题近年来在组合优化领域引起了越来越多的关注。在本文中，我们分析了一些用于双层优化问题的进化算法的运行时间。我们在参数复杂性的背景下研究了两个 NP 难问题，即广义最小生成树问题和广义旅行商问题。对于广义最小生成树问题，我们分析了 Hu 和 Raidl（2012）提出的两种方法，这两种方法涉及通过所选可能解决方案的表示来区分彼此的聚类数量。我们的结果表明，使用跨越节点表示的（1+1）进化算法对于该问题不是固定参数进化算法，而使用全局结构表示可以在固定参数时间内解决该问题。我们为每种方法提供了困难实例，并通过证明它们可以非常有效地解决彼此的困难实例，表明这两种方法是高度互补的。对于广义旅行商问题，我们根据问题实例中的聚类数量来分析该问题。我们的结果表明，使用全局结构表示的（1+1）进化算法是该问题的固定参数进化算法。
