On the analysis of the (1+ 1) evolutionary algorithm for the maximum leaf spanning tree problem
A lot of heuristic algorithms, such as Evolutionary algorithms (EAs), are used to solve the
maximum leaf spanning tree (MLST) problem which is non-deterministic polynomial time
hard (NP-hard). However, the performance analysis of EAs on the MLST problem has
seldom been studied theoretically. In this paper, we theoretically analyze the performance of
the (1+ 1) EA on the MLST problem. We demonstrate that the (1+ 1) EA obtains 5-
approximation ratio and 3-approximation ratio on this problem in expected polynomial …
maximum leaf spanning tree (MLST) problem which is non-deterministic polynomial time
hard (NP-hard). However, the performance analysis of EAs on the MLST problem has
seldom been studied theoretically. In this paper, we theoretically analyze the performance of
the (1+ 1) EA on the MLST problem. We demonstrate that the (1+ 1) EA obtains 5-
approximation ratio and 3-approximation ratio on this problem in expected polynomial …
A lot of heuristic algorithms, such as Evolutionary algorithms (EAs), are used to solve the maximum leaf spanning tree (MLST) problem which is non-deterministic polynomial time hard (NP-hard). However, the performance analysis of EAs on the MLST problem has seldom been studied theoretically. In this paper, we theoretically analyze the performance of the (1+1) EA on the MLST problem. We demonstrate that the (1+1) EA obtains -approximation ratio and 3-approximation ratio on this problem in expected polynomial runtime O(nm2) and O(nm4), respectively, where n is the number of nodes and m is the number of edges in a connected undirected graph. Furthermore, we reveal that the (1+1) EA can outperform the local search algorithms on two instances of the MLST problem.
Taylor & Francis Online以上显示的是最相近的搜索结果。 查看全部搜索结果