Guturu Parthasarathy, Dantu Ram
Department of Electrical Engineering, College ofEngineering, University of North Texas, Denton, TX 76203-1277, USA. e-mail:
IEEE Trans Syst Man Cybern B Cybern. 2008 Jun;38(3):645-66. doi: 10.1109/TSMCB.2008.915645.
Many graph- and set-theoretic problems, because of their tremendous application potential and theoretical appeal, have been well investigated by the researchers in complexity theory and were found to be NP-hard. Since the combinatorial complexity of these problems does not permit exhaustive searches for optimal solutions, only near-optimal solutions can be explored using either various problem-specific heuristic strategies or metaheuristic global-optimization methods, such as simulated annealing, genetic algorithms, etc. In this paper, we propose a unified evolutionary algorithm (EA) to the problems of maximum clique finding, maximum independent set, minimum vertex cover, subgraph and double subgraph isomorphism, set packing, set partitioning, and set cover. In the proposed approach, we first map these problems onto the maximum clique-finding problem (MCP), which is later solved using an evolutionary strategy. The proposed impatient EA with probabilistic tabu search (IEA-PTS) for the MCP integrates the best features of earlier successful approaches with a number of new heuristics that we developed to yield a performance that advances the state of the art in EAs for the exploration of the maximum cliques in a graph. Results of experimentation with the 37 DIMACS benchmark graphs and comparative analyses with six state-of-the-art algorithms, including two from the smaller EA community and four from the larger metaheuristics community, indicate that the IEA-PTS outperforms the EAs with respect to a Pareto-lexicographic ranking criterion and offers competitive performance on some graph instances when individually compared to the other heuristic algorithms. It has also successfully set a new benchmark on one graph instance. On another benchmark suite called Benchmarks with Hidden Optimal Solutions, IEA-PTS ranks second, after a very recent algorithm called COVER, among its peers that have experimented with this suite.
由于具有巨大的应用潜力和理论吸引力，许多图论和集合论问题已得到复杂性理论研究人员的充分研究，并被发现是NP难问题。由于这些问题的组合复杂性不允许对最优解进行穷举搜索，因此只能使用各种特定于问题的启发式策略或元启发式全局优化方法（如模拟退火、遗传算法等）来探索近似最优解。在本文中，我们针对最大团查找、最大独立集、最小顶点覆盖、子图和双子图同构、集合包装、集合划分和集合覆盖等问题提出了一种统一的进化算法（EA）。在所提出的方法中，我们首先将这些问题映射到最大团查找问题（MCP）上，然后使用进化策略来解决该问题。所提出的用于MCP的带有概率禁忌搜索的不耐烦EA（IEA-PTS）将早期成功方法的最佳特性与我们开发的许多新启发式方法相结合，以产生一种性能，在用于探索图中最大团的EA中达到了当前的先进水平。对37个DIMACS基准图进行实验的结果以及与六种先进算法（包括来自较小EA社区的两种算法和来自较大元启发式社区的四种算法）的比较分析表明，IEA-PTS在帕累托字典序排名标准方面优于EA，并且在与其他启发式算法单独比较时，在某些图实例上具有竞争力的性能。它还在一个图实例上成功地设定了一个新的基准。在另一个名为“具有隐藏最优解的基准”的基准套件上，IEA-PTS在对该套件进行实验的同类算法中，仅次于最近一种名为COVER的算法，排名第二。
