Research On Local Search Algorithms For Solving Clique Extension Problems

Given an undirected graph,we find a vertex subset,so that any two vertices of the subset are adjacent.Such vertex subset is called a clique.The maximum clique problem is to find a clique with the largest cardinality,it is a well-known combinatorial optimization problem and a NP-complete problem.The maximum clique problem is widely used in information retrieval,bioinformatics,fault diagnosis,etc.The maximum edge weighted clique problem and the clique partitioning problem are extensions of the clique problem,they have stronger expression ability and wider application,and have been proved to be NP-hard combinatorial optimization problems.There are two kinds of algorithms to solve these two problems: exact algorithms and heuristic algorithms.Exact algorithms can give optimal solutions of the problem,but as the scale of the problem grows,exact algorithms will struggle to solve the problem,and heuristic algorithms have emerged at the historic moment,such as local search algorithms,tabu algorithms,and so on,this kind of algorithm can give optimal solutions or suboptimal solutions to the problem in a reasonable time.Heuristic algorithms have the characteristics of simple ideas,easy implementation,high efficiency and generality.In this paper,local search algorithms for solving the maximum edge weighted clique problem and the clique partitioning problem are studied.The maximum edge weighted clique problem is applied in the fields of experimental design,signal transmission,computer vision,etc.We propose a local search algorithm based on multiple rules to solve the problem.The algorithm first proposes a scoring strategy to evaluate the benefits of add and swap operations,then uses a vertex weighting strategy to increase the diversity of the solution,and uses a configuration checking strategy to avoid the cycling problem.By combining three strategies,the algorithm proposes multiple rules to select the added vertex and exchanged vertex pairs.Based on these rules,an efficient local search algorithm is proposed,namely local search based on multiple rules(LSMR).Experimental results show that LSMR is superior to compared algorithms in terms of solution quality and calculation efficiency.The clique partitioning problem has been widely used in the fields of airport logistics,social sciences,etc.We propose a local search algorithm based on two-model to solve the problem.Firstly,the algorithm mainly uses a two-model local search procedure to improve the quality of the current solution.Secondly,a perturbation procedure is proposed to increase the diversity of solutions,and the perturbation strength is updated self-adaptively according to the current solution.Based on these two procedures,a novel two-model local search with the adaptive parameter(TMLS?SA)is proposed.Experimental results show that TMLS?SA is better than compared algorithms in terms of solution quality.