基于雪堆博弈的复杂网络最小节点覆盖

发布时间：2018-03-16 02:29

本文选题：复杂网络　切入点：雪堆博弈　出处：《西安电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：复杂网络是现实中复杂系统的抽象,自然界和人类社会中的很多系统都是以网络的形式存在的,这些网络错综复杂,各式各样,但拥有一些共通的特性。比如朋友关系网络、电力网、生态系统网、国家间的竞争与合作关系、药物相互作用关系等等。其中,系统中的个体对应于复杂网络中的节点,系统中个体之间的关系对应于复杂网络中节点之间的边。研究复杂网络,对促进人类现实社会和科学技术的进步有深远的意义。复杂网络的最小节点覆盖问题(MVCP)是一个著名组合优化问题,其目的在于找出给定网络的最小节点集合以覆盖所有的边。现实中的很多问题最终都可以归结为最小节点覆盖问题,其在现实中也有着广泛的应用,比如规划问题,网络优化等方面,同时也是解决一些其他重要问题的关键点,如测算网络的鲁棒性等。作为一个NP难问题,虽然成为研究热点已有时日,但已经提出的解决该问题的算法大都有不尽人意的地方,我们经过研究试验,结合进化算法的全局搜索能力,与博弈进化的局部搜索能力,提出了基于雪堆博弈的自然进化算法GEA和基于雪堆博弈的变异搜索算法SVS,两个算法各有所长。通过大量实验,考察算法在解决复杂网络的最小节点覆盖问题上的表现,验证其有效性。本文的主要工作如下:1.基于记忆的最优反应算法。该算法为复杂网络的最小节点覆盖问题提出一种新的解决思路,利用局部信息和理性个体的记忆能力,启发式地求得MVCP问题的解。我们通过充分的实验,分析该算法的特性以及在不同网络上的性能表现,并深刻剖析其原理,以帮助更好地解决最小节点覆盖问题。2.基于雪堆博弈的自然进化算法。我们借鉴自然进化思想,将网络的节点覆盖结果,即网络中所有节点的状态(覆盖或不覆盖)集合看作一个染色体,作为种群进化中的个体。将网络的节点覆盖与博弈理论相结合,每个节点与自己的邻点进行雪堆博弈,根据最优反应规则获得当前策略并更新策略,当整个网络达到纳什均衡状态时,完成局部最优解搜索。个体组成种群,再通过种群的进化更新,完成全局最优解搜索。通过实验对比,这种算法表现出优于当前经典算法的性能。3.基于雪堆博弈的变异搜索算法。我们将网络中的节点视为理性个体,赋予其判断最优策略的能力,并拥有一定的记忆能力。将博弈理论与复杂网络的节点覆盖问题相联系,引入空间雪堆博弈和基于记忆的最优反应规则,个体通过与邻点的博弈获得当前最优策略并更新记忆。所有个体根据各自的记忆更新策略再博弈,最终网络会达到纳什均衡状态,完成解的初步搜索。再根据自然进化,对初步解进行变异操作,通过进化搜索最终达到全局最优。通过实验,详细分析了算法在不同网络的表现及背后原理,验证了算法对各种网络的最小节点覆盖问题都很很好的适应性。
[Abstract]:Complex networks are abstractions of complex systems in reality, and many systems in nature and in human society exist in the form of networks. These networks are complex and varied, but they have some common characteristics, such as the network of friends. Power grids, ecosystem networks, competition and cooperation between countries, drug interactions, etc., where individuals in the system correspond to nodes in complex networks, The relationship between individuals in the system corresponds to the edges between nodes in a complex network. It is of great significance to promote the progress of human society and science and technology. The minimum node coverage problem of complex networks (MVCPP) is a famous combinatorial optimization problem. The purpose of this problem is to find the minimum set of nodes in a given network to cover all edges. Many problems in reality can eventually be attributed to the minimum node coverage problem, and it also has a wide range of applications in reality, such as planning problems. Network optimization is also the key point to solve some other important problems, such as calculating the robustness of network. As a NP-hard problem, it has been a hot topic for some time. However, most of the algorithms that have been proposed to solve this problem are unsatisfactory. We have studied and tested the global search ability of evolutionary algorithm and the local search ability of game evolution. This paper proposes a natural evolutionary algorithm (GEA) based on snowdrift game and a mutation search algorithm (SVS) based on snowdrift game. Through a large number of experiments, the performance of the algorithm in solving the minimum node coverage problem of complex networks is investigated. The main work of this paper is as follows: 1. An optimal response algorithm based on memory. This algorithm provides a new solution to the minimum node coverage problem of complex networks, using local information and the memory ability of rational individuals. Heuristic solution of MVCP problem is obtained. Through sufficient experiments, we analyze the characteristics of the algorithm and its performance on different networks, and deeply analyze its principle. In order to help solve the minimum node coverage problem better. 2. A natural evolutionary algorithm based on snowdrift game. We use the idea of natural evolution to cover the nodes of the network. That is, the set of states of all nodes in the network is regarded as a chromosome, as an individual in the evolution of the population. The node coverage of the network is combined with the game theory, and each node plays snowdrift game with its neighbors. According to the optimal response rule, the current strategy is obtained and updated. When the whole network reaches Nash equilibrium, the local optimal solution search is completed. The performance of this algorithm is better than that of the current classical algorithm. 3. The mutation search algorithm based on snowdrift game. We regard the nodes in the network as rational individuals. The game theory is connected with the node coverage problem of complex network, and the spatial snowdrift game and the memory-based optimal response rule are introduced. The individual obtains the current optimal strategy and updates the memory through the game with the adjacent point. All the individuals play games according to their own memory update strategy. Finally, the network will reach the Nash equilibrium state, complete the initial search of the solution, and then according to the evolution of nature, the network will reach the state of Nash equilibrium, and then according to the evolution of nature, The mutation operation of the initial solution is carried out, and the global optimization is finally achieved by evolutionary search. Through experiments, the performance of the algorithm in different networks and the principle behind it are analyzed in detail. It is verified that the algorithm is very adaptive to the minimum node coverage problem of various networks.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】