03364nas a2200421   4500008004100000245016000041210006900201300001400270490000700284520195900291653003402250653001902284653002902303653002202332653002902354653002702383653003402410653002902444653002202473653002302495653001702518653002502535653002702560653004502587653002002632653004502652653001702697653002002714653002502734653003002759653001602789653002002805653001502825653002402840100002602864700001502890856003702905       2008                        eng d00aAn Impatient Evolutionary Algorithm With Probabilistic Tabu Search for Unified Solution of Some NP-Hard Problems in Graph and Set Theory via Clique Finding0 aImpatient Evolutionary Algorithm With Probabilistic Tabu Search   a645 - 6660 v383 a<p>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.</p>
10aAlgorithm design and analysis10aClique finding10acombinatorial complexity10aComplexity theory10acomputational complexity10aevolutionary algorithm10aevolutionary algorithms (EAs)10aevolutionary computation10agenetic algorithm10aGenetic algorithms10agraph theory10aHeuristic algorithms10amaximum clique finding10ametaheuristic global optimization method10aNP-hard problem10aNP-hard problems in set and graph theory10aoptimisation10aPareto analysis10aPerformance analysis10aprobabilistic tabu search10aprobability10asearch problems10aset theory10asimulated annealing1 aGuturu, Parthasarathy1 aDantu, Ram  uhttps://nsl.cse.unt.edu/node/207