A Parameterized Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms
作者： Per Kristian Lehre , Dogan Corus , Mojgan Pourhassan , Frank Neumann
DOI:
关键词:
摘要: Bi-level optimisation problems have gained increasing interest in the field of combinatorial recent years. With this paper, we start runtime analysis evolutionary algorithms for bi-level problems. We examine two NP-hard problems, generalised minimum spanning tree problem (GMST), and travelling salesman (GTSP) context parameterised complexity. For problem, analyse approaches presented by Hu Raidl (2012) with respect to number clusters that distinguish each other chosen representation possible solutions. Our results show a (1+1) EA working nodes is not fixed-parameter algorithm whereas global structure enables solve time. present hard instances approach are highly complementary proving they other's very efficiently. instance. problem.
arxiv.org参考文章(17)
Andrew M. Sutton, Frank Neumann, A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling parallel problem solving from nature. pp. 52- 61 ,(2012) , 10.1007/978-3-642-32937-1_6
Kalyanmoy Deb, Ankur Sinha, Solving Bilevel Multi-Objective Optimization Problems Using Evolutionary Algorithms Lecture Notes in Computer Science. pp. 110- 124 ,(2009) , 10.1007/978-3-642-01020-0_13
Stefan Kratsch, Per Kristian Lehre, Frank Neumann, Pietro Simone Oliveto, Fixed parameter evolutionary algorithms and maximum leaf spanning trees: a matter of mutation parallel problem solving from nature. pp. 204- 213 ,(2010) , 10.1007/978-3-642-15844-5_21
Bin Hu, Günther R. Raidl, An evolutionary algorithm with solution archive for the generalized minimum spanning tree problem computer aided systems theory. pp. 287- 294 ,(2011) , 10.1007/978-3-642-27549-4_37
Kalyanmoy Deb, Ankur Sinha, An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm Evolutionary Computation. ,vol. 18, pp. 403- 449 ,(2010) , 10.1162/EVCO_A_00015
Dogan Corus, Per Kristian Lehre, Frank Neumann, The generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisation genetic and evolutionary computation conference. pp. 519- 526 ,(2013) , 10.1145/2463372.2463442
Matteo Fischetti, Juan José Salazar González, Paolo Toth, A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem Operations Research. ,vol. 45, pp. 378- 394 ,(1997) , 10.1287/OPRE.45.3.378
Young-Soo Myung, Chang-Ho Lee, Dong-Wan Tcha, On the generalized minimum spanning tree problem Networks. ,vol. 26, pp. 231- 241 ,(1995) , 10.1002/NET.3230260407
Andrew Koh, Solving transportation bi-level programs with Differential Evolution congress on evolutionary computation. pp. 2243- 2250 ,(2007) , 10.1109/CEC.2007.4424750
Francois Legillon, Arnaud Liefooghe, El-Ghazali Talbi, CoBRA: A cooperative coevolutionary algorithm for bi-level optimization congress on evolutionary computation. pp. 1- 8 ,(2012) , 10.1109/CEC.2012.6256620