A Bi-level Blocked Estimation of Distribution Algorithm with local search for Maximum Clique Problems

Maximum clique problem (MCP) is a complicated deceptive problem for estimation of distribution algorithms (EDAs). The univariate EDAs cannot utilize the correlations of the variables and the advanced EDAs perform poor due to the expensive computational cost in building the appropriate probability models. In this paper, by utilizing the special structure of MCP, a new Bi-level Blocked Probability model (BBP) is constructed, which achieves the relationships utilizing in a bivariate probability model at the computational cost of univariate probability model. Integrating promising neighborhood search techniques, a new EDA algorithm, called Bi-level Blocked Estimation of Distribution Algorithm (BBEDA) is proposed for MCP. Comparative experiments on extensive DIMACS Benchmark instances show that the proposed BBEDA can be competitive with the evolutionary algorithm with guided mutation (the best evolutionary algorithm reported so far) in terms of solution quality and computational performance.