GSet Dataset

The objective of the max-cut problem is to cut any graph in such a way that the total weight of the edges that are cut off is maximum in both subsets of vertices that are divided due to the cut of the edges. Although it is an elementary graph partitioning problem, it is one of the most challenging combinatorial optimization-based problems with tons of application areas that make this problem highly admissible. Due to its admissibility, the problem is solved using the Harris Hawk Optimization algorithm (HHO). Though HHO effectively solved some engineering optimization problems; in the field of combinatorial optimization-based problems, the number is very few with better outcomes than any other available metaheuristic algorithms in contemporary times. Thus HHO along with some additional operators is used to solve the max-cut problem. Synthesis and decomposition operators are used to modify the fitness of the hawk in such a way that they can provide precise results. A mutation mechanism along with an adjustment operator has improvised the outcome obtained from the updated hawk. To accept the potential result, the acceptance criterion has been used, and then the repair operator is applied in the proposed approach. The proposed system provided comparatively better outcomes on the G-set dataset than other state-of-the-art algorithms. It obtained 533 cuts more than the discrete cuckoo search algorithm in 9 instances, 1036 cuts more than PSO-EDA in 14 instances, and 1021 cuts more than TSHEA in 9 instances. But for four instances, the cuts are lower than PSO-EDA and TSHEA. Besides, the statistical significance has also been tested using the Wilcoxon signed rank test to provide proof of the superior performance of the proposed method. In terms of solution quality, MC-HHO can produce outcomes that are quite competitive when compared to other related state-of-the-art algorithms.

最大割问题（max-cut problem）的优化目标为：对任意给定图进行割分，使得因边割分而划分出的两个顶点子集之间，被切断的边的总权重达到最大值。尽管其属于基础的图划分问题，但却是最具挑战性的组合优化类问题之一，且拥有海量应用场景，这使得该问题具备极高的研究价值与应用必要性。鉴于该问题的研究价值，本文采用哈里斯鹰优化算法（Harris Hawk Optimization, HHO）对其进行求解。尽管HHO已在部分工程优化问题中实现了有效求解，但在组合优化领域，能实现优于当前主流元启发式算法性能的应用案例仍十分有限。因此，本文将HHO与若干附加算子相结合，用于求解最大割问题。其中，合成与分解算子用于调整鹰群个体的适应度，以获取更为精准的求解结果；变异机制与调整算子则进一步优化了更新后的鹰群个体所得到的求解结果。在所提方法中，首先通过接受准则筛选潜在最优解，随后应用修复算子对解进行修正。所提算法在G集数据集（G-set dataset）上的求解性能相较其他前沿先进算法更为出色。在9个测试实例中，其获得的割边数较离散布谷鸟搜索算法多出533；在14个测试实例中较PSO-EDA算法多出1036；在9个测试实例中较TSHEA算法多出1021。但在4个测试实例中，其割边数低于PSO-EDA与TSHEA算法。此外，本文采用威尔科克森符号秩检验（Wilcoxon signed rank test）对求解结果进行统计学显著性检验，以验证所提方法的性能优势。在求解质量层面，MC-HHO算法的求解结果与其他相关前沿先进算法相比，具备较强的竞争力。

搜集汇总

背景与挑战

背景概述

GSet Dataset是一个专注于最大割问题的图论数据集，用于测试和比较组合优化算法。该数据集基于Harris Hawk Optimization算法（HHO）及其改进版本MC-HHO，在G-set数据集上进行了评估，结果显示MC-HHO在多数实例中优于其他先进算法（如离散布谷鸟搜索、PSO-EDA和TSHEA），并通过统计测试验证了其性能优势。数据集适用于图论和优化研究，采用CC BY 4.0许可证开放访问。