论文部分内容阅读
最大割问题(MAXCUT Problem)是著名的NP难问题，即使形式最简单的2-最大割问题(2-MAXCUT Problem)也属于NP难问题。这意味着，不存在任何算法能在多项式时间内为其找到最优解，除非NP=P。启发式算法是为了快速求解时间复杂度极高的组合优化问题(如NP难问题)而提出的一类近似算法。启发式算法与确定性算法的主要区别在于：启发式算法利用某些特殊的信息在多项式时间内寻找问题的近似解，而并非最优解。在过去的几十年，最大割问题作为一个研究热点一直被众多专家学者关注着。为了求解最大割问题，大量启发式算法被提出，如演化算法、蚁群算法等，但多数研究只从实验的角度估算算法的时间复杂度，而基于严格理论推导的研究成果却十分稀少。本文的主要工作包括：(1)本文从理论的角度分析和比较了三种著名的启发式算法在2-最大割问题上的近似性能，它们分别是：随机局部搜索算法(Random Local Search, RLS)，(1+1)-演化算法((1+1)-Evolutionary Algorithm，(1+1)-EA)和随机游走算法(RandomWalk Algorithm)。分析结果表明：(1+1)-EA寻找一个0.5-近似解的时间上界是O (n3)；随机游走算法寻找一个(12α)-近似解(α≥0)的时间上界是O (n (1+1/(3+2α)) n)。此外，为了深入了解不同启发式算法求解最大割问题的效率差异，本文分析了这三种算法求解完全二分图的时间复杂度。分析结果表明，这三种启发式算法都能够在多项式时间内找到完全二分图的最优解，且(1+1)-演化算法与随机局部搜索算法算法的性能均优于随机游走算法。(2)除了关注启发式算法在最大割问题上的性能分析，本文还关注启发式算法在最大割问题上的性能优化。在求解最大割问题时，朴素演化算法的稳定性较差、且容易出现过早收敛的现象。为了克服这些缺点，本文对朴素演化算法进行了改进。首先，本文在朴素演化算法中混合了一种局部优化策略来提高算法求解的质量；同时，本文为算法设计了自适应变异算子和交叉算子，它们可以克服算法的过早收敛。此外，本文通过降低“种群的浓度”来改进“比例选择算子”的性能。为了验证改进算法的有效性，本文研究了当前求解最大割问题的几种近似算法，并进行了实验对比。实验结果表明，本文提出的改进演化算法比朴素演化算法的性能好20%，且算法在求解最大割问题上的效率和质量上均优于大多数近似算法。