Research And Application Of Ant Colony Algorithm For The Maximum Clique Problem

Ant colony algorithm is a kind of swarm intelligence algorithm inspired by the foraging behavior of ants. It is originally used to solve the traveling salesman problem. So far, it has become the effective method to solve the issue of combinatorial optimization. The maximum clique is a classical combinatorial optimization problem, owning a wide range of applications in social networks, computer vision, fault diagnosis and other fields. So in this paper, we use the ant colony algorithm to solve the maximum clique problem.This paper summarizes the research status of the maximum clique problem and ant colony algorithm, and then describes the study status of using ant colony algorithm to solve the maximum clique problems in detail. This paper studied the position of the pheromone——vertices and edges, and did experimental analysis of the important parameters in the algorithm. When the ant colony algorithm solves maximum clique problem, some don’t have high accuracy of solution and generally go with a slow convergence speed. To solve these problems, this paper proposed an improved algorithm. By increasing the diversity to solve the local optimum. This paper proposed a new mixed ant transfer strategy, including roulette strategy and supplement choosing strategy. Among them, supplement choosing strategy was mainly used to improve the probability of the less choose node, expanding the search space and increasing the diversity of the solution at the same time. However, the supplement choosing strategy could cause an increase in convergence time, so we further introduced the local improvement strategy to improve the algorithm convergence speed and precision of the algorithm. DIMACS is the internationally standard benchmark used to measure the algorithm performance of solving maximum cliques. Experiments indicated that our improved algorithm was efficiedt and feasible.Cohesive subgroup is a typical social network structure, and the full connected subgraph is the most compact cohesive subgroup in social network analysis. Therefore, finding the maximum clique of the social network is one of the research emphases and owns great significance. The improved algorithm solved the social network of cohesive subgroup structure of the social network data sets. Results of the simulation experiment showed the effectiveness of the improved algorithm.