Game-based Evolutionary Optimization To The Minimum Vertex Cover Of Networks

Complex network is an abstract of the realistic complex system. Many systems in both nature and the human society exist in the form of network. These networks are various, at the same time have a number of common characteristics, such as friends networks, power grids, ecosystem network, competition and cooperation between countries, drug interactions relations, etc. Among them, an individual in the system corresponds to a vertex in the complex network, and the relationship between the individuals in system corresponds to an edge between vertexes in the complex network. The further study of these complex networks not only has an practical and essential significance to people's work and life, but also has a profoundly scientific significance for the development of the nature and the whole human society.The minimum vertex cover problem of complex networks(MVCP) is a well-known combinatorial optimization problem, which aims to find the minimum set of vertexes to cover all of the edges in the given network. Many problems in reality can ultimately be translated into the minimum vertex cover problem, such as planning, network optimization, etc. It has a wide range of applications and is also the key point to solve some other important issues like measuring of the robustness of networks. As an NP-hard problem, although the MVCP has become a hot topic for some time, the proposed algorithms have undesirable places. We combine the snowdrift game theory with natural evolution, and then propose game evolutionary algorithm(GEA) and snowdrift-game-based variation search algorithm(SVS), which have their own strengths. Through a lot of experiments, we verify the good performance in the MVCP, showing their effectiveness. The main contents of this thesis are as follows:Memory-based best response algorithm. This paper proposes a new method for vertex cover problem of complex networks, using only local information and giving the rational individuals memory ability, heuristically obtaining solutions. With fully experiments, we inspect features and performance of the algorithm on different networks, and profoundly analyze the principles to help solve vertex cover problem.Game evolutionary algorithm. We learn from the natural evolution thoughts, regarding the vertex cover of networks as chromosomes, being an individual of the evolutionary population. Combining the vertex cover problem with the game theory, each vertex operates snowdrift game with its own adjacent vertex, get its best current strategy according to the best response rule and update its strategy. It will have completed local optima searching when the entire network reach the Nash equilibrium. The population consists of individuals, and then update the population through evolution process, completing global optimal solution. Through experiments, it shows that the algorithm is superior to the current classical algorithms.Snowdrift-game-based variation search algorithm. The vertex of the networks is regarded as a rational individual, possessing the ability to determine its optimal strategy, and has some memory. Game theory and the MVCP of the complex network are connected. We introduce the space snowdrift game and the best response rule, and the individuals obtain optimal current strategy through game and then update their memory. All individuals update their strategies according to their memory and operate game again, and eventually the network will reach the Nash equilibrium, completing the initial search for solutions. Employing the natural evolution, the individuals mutate, and eventually reach the global optimum through evolutionary search. It is concluded from experiment results that the algorithm possesses good adaptability to different networks.