论文标题
分析顶点盖的灰色盒子操作员
Analysis of a Gray-Box Operator for Vertex Cover
论文作者
论文摘要
组合优化问题是进化算法的突出应用领域，其中（1+1）EA是研究最多的算法之一。我们通过使用专门的突变操作员引入一些问题知识来扩展该算法，该突变算子在假设解决方案的数量至关重要的假设下起作用，因为在组合优化中经常发生。这种轻微的修改增加了纠正错误放置位的机会，同时保留了（1+1）ea的简单性和问题独立性。作为我们算法的应用，我们在某些情况下检查了顶点覆盖问题，我们表明它会导致渐近的更好的运行时间，甚至发现与常规（1+1）EA相比，具有更高概率的最佳解决方案。确切地说，我们比较了路径上的两种算法的性能以及在尺寸$ n $的完整二分图上的性能。关于路径，我们证明，对于特定的初始配置，\ alg1+1的期望为$θ（n^4）$迭代，而修改将其降低到$θ（n^3）$，并且目前的实验证据表明达到了这种配置。关于完整的两部分图，我们的修改在多项式时间内找到了最佳的概率，$ 1-1/2^{ω（n^ξ）} $对于每个正常数$ξ<1 $ $
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size $n$. Regarding the path we prove that, for a particular initial configuration, the \alg1+1 takes in expectation $Θ(n^4)$ iterations while the modification reduces this to $Θ(n^3)$, and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability $1-1/2^{Ω(n^ξ)}$ for every positive constant $ξ< 1$, which improves the known probability of $1-1/\text{poly}(n)$ for the (1+1) EA..
