IEEE Trans Cybern. 2015 Aug;45(8):1491-8. doi: 10.1109/TCYB.2014.2354343. Epub 2014 Sep 12.
The maximum cut (MAX-CUT) problem is to find a bipartition of the vertices in a given graph such that the number of edges with ends in different sets reaches the largest. Though, several experimental investigations have shown that evolutionary algorithms (EAs) are efficient for this NP-complete problem, there is little theoretical work about EAs on the problem. In this paper, we theoretically investigate the performance of EAs on the MAX-CUT problem. We find that both the (1+1) EA and the (1+1) EA*, two simple EAs, efficiently achieve approximation solutions of (m/2)+(1/4)s(G) and (m/2)+(1/2)(√{8m+1}-1), where m and s(G) are respectively the number of edges and the number of odd degree vertices in the input graph. We also reveal that for a given integer k the (1+1) EA* finds a cut of size at least k in expected runtime O(nm+1/δ(4k)) and a cut of size at least (m/2)+k in expected runtime O(n(2)m+1/δ((64/3)k(2))), where δ is a constant mutation probability and n is the number of vertices in the input graph. Finally, we show that the (1+1) EA and the (1+1) EA* are better than some local search algorithms in one instance, and we also show that these two simple EAs may not be efficient in another instance.
最大切割（MAX-CUT）问题是在给定的图中找到一个顶点的二分图，使得两端位于不同集合的边数达到最大。尽管已经有几项实验研究表明进化算法（EA）对于这个 NP 完全问题非常有效，但对于该问题的 EA 理论研究却很少。在本文中，我们从理论上研究了 EA 在 MAX-CUT 问题上的性能。我们发现，两种简单的 EA，即（1+1）EA 和（1+1）EA*，能够有效地获得输入图中边数 m 和奇数度顶点数 s(G)的近似解 (m/2)+(1/4)s(G)和(m/2)+(1/2)(√{8m+1}-1)。此外，我们还揭示了对于给定的整数 k，（1+1）EA在期望运行时间 O(nm+1/δ(4k))内找到大小至少为 k 的切割，在期望运行时间 O(n(2)m+1/δ((64/3)k(2)))内找到大小至少为 (m/2)+k 的切割，其中 δ 是一个常数突变概率，n 是输入图中的顶点数。最后，我们证明了（1+1）EA 和（1+1）EA在一个实例中优于一些局部搜索算法，并且我们还证明了这两种简单的 EA 在另一个实例中可能效率不高。
