Performance Analysis And Optimization Of Heuristic Algorithms On The MAXCUT Problem

MAXCUT Problem is one of the most famous NP-Hard problems. Even its mostsimplest form,2-MAXCUT Problem, is NP-Hard which means there are no polynomialalgorithms that could optimize the2-MAXCUT Problem in polynomial time, unless NP=P.Heuristic algorithm is a kind of approximation algorithms that are proposed to solveincredibly complex optimization problems, such as NP-Hard problem. Instead of findingoptimal for a problem, heuristic algorithm finds an acceptable approximation in polynomialtime. MAXCUT Problem has been a research hot field for the last several decades, andnumbers of researchers are interested about it. Lots of heuristic algorithms are proposed tosolve MAXCUT Problem, such as Evolutionary Algorithm and Ant Colony Optimization.However, most of studies are based on empirical experiments, and rigorous theoreticalanalyses are little. The main contributions of this paper are stated as follows:(1) This paper analyzes and compares the performance of three base heuristic algorithmson the2-MAXCUT Problem, which are RLS (Random Local Search),(1+1)-EA andRandomWalk. The results reveal that (1+1)-EA finds a0.5-approximation using timeO (n3)and RandomWalk finds a (12α)-approximation using time O (n (1+1/(3+2α)) n). Besides,we analyze the running time of forward mentioned heuristic algorithms on an instance-thecomplete bipartite graph. Results show that all three algorithms can optimize the completebipartite graph in polynomial time, and(1+1)-EA and RLS are both outperform RandomWalk.(2) We concern about both performance analysis and optimization of heuristic algorithmson the2-MAXCUT Problem. In order to get rid of the low efficiency and instability of naiveevolutionary algorithm, we proposed a new hybrid improved evolutionary algorithm. Weadopt a new local optimization strategy to decide whether a vertex of the graph should bemoved. Moreover, we also adopt the parameters self-adaptation strategy to overcome theinstability of naive EA and design a novel improved selection schema for the algorithm.Finally, we compare our algorithm to several approximation algorithms for MAXCUTProblem. The experimental results show that our algorithm achieves performanceimprovement of20%when comparing to the naive EA and it outperforms most of otherapproximation algorithms on both quality and computational time.