Game-based Algorithms To The Independent Set And Vertex Cover Of Networks

In general,complex networks can be used to describe the relationships of different individuals,different populations,individuals and populations.The Maximum Independent Set Problem(MISP)and the Minimum Vertex Cover Problem(MVCP)are two classical NPhard and combinatorial optimization problems in the field of the complex networks.The MISP and the MVCP are closely related.And the research of them means a lot for other problems in the complex networks.The MISP is to find a set of vertices with the maximum cardinality,in which all vertices in the set are independent with each other.The MVCP aims to finding a minimum number of vertices of a network to cover all edges of the network.Both the MISP and the MVCP have many applications in a wide range of fields such as routing,network optimizing and so on.In this thesis,we firstly research the dynamics of the network’s game and then make a combination between the game dynamics of the networks and the classical local search scheme.Finally,we propose the Iterated Game-based Local Search Algorithm(IGLS)for the MISP and the Game-based Memetic Algorithms(GMA-MVC)for the MVCP.The extensive experimental results on different networks shows the excellent performance of the proposed algorithms.The main contributions of my works are as follows:1.Researching the game dynamics of complex networks and establishing the relationships between the Nash equilibrium(NE)of the asynchronous Prisoner’s Dilemma Game(PDG)of the network and the maximum independent set of the network.Inspired by memory-based game of the network,we prove that the game of the network will converge to the NE state with probability one by using the asynchronous game scheme.Finally,we find that the strict Nash equilibrium(SNE)of the asynchronous Snowdrift Game(SG)of the networks is a kind of vertex cover state.2.The Iterated Game-based Local Search Algorithm(IGLS)for the MISP is proposed.The traditional local search skills for the MISP can only accomplish one-vertex’s improvement in a round of operations.We proposed a new Game-based local search(GLS)scheme and it can achieve many kinds of improvement of the solution.In the meantime,there is an inherent perturbation operation during the local search process.In addition,we take use of the traditional iterated local scheme to escape form the local maximal solution by using the weak perturbation after a round of the local search.That is the proposed IGLS.Compared with other algorithms,the proposed IGLS can realize a better results since the strong local search ability and the inherent perturbation operation in the GLS.3.The Game-based Memetic Algorithm for the MVCP(GMA-MVC)is proposed.By using the classical memetic algorithm scheme,we treat each state of the network as an individual(chromosome)of the population.Each individual can describe a vertex cover set of the network.The memetic algorithm uses the global information during the population evolution by the crossover and the mutation operations.However,the crossover and mutation operations can lead the individuals to an illegal state since the MVCP must satisfy the condition that all edges of the networks have at least one vertex in the vertex cover set.As a result,we proposed the individual evolution based on the asynchronous SG of the network.Each individual will become a correct vertex cover state by playing the SG asynchronous until SNE since the SNE state is actually a vertex cover state.From the SNE state,each individual will do local search based on the SG for 7)0)times to improve itself.In the GMAMVC,both the population evolution and the individual evolution are conducted for using both the global and the local information to search for a better solution.Compared with other algorithms,the GMA-MVC can always obtain a better solution.