复杂网络是现实中复杂系统的抽象,自然界和人类社会中的很多系统都是以网络的形式存在的,这些网络错综复杂,各式各样,但拥有一些共通的特性。比如朋友关系网络、电力网、生态系统网、国家间的竞争与合作关系、药物相互作用关系等等。其中,系统中的个体对应于复杂网络中的节点,系统中个体之间的关系对应于复杂网络中节点之间的边。研究复杂网络,对促进人类现实社会和科学技术的进步有深远的意义。复杂网络的最小节点覆盖问题(MVCP)是一个著名组合优化问题,其目的在于找出给定网络的最小节点集合以覆盖所有的边。现实中的很多问题最终都可以归结为最小节点覆盖问题,其在现实中也有着广泛的应用,比如规划问题,网络优化等方面,同时也是解决一些其他重要问题的关键点,如测算网络的鲁棒性等。作为一个NP难问题,虽然成为研究热点已有时日,但已经提出的解决该问题的算法大都有不尽人意的地方,我们经过研究试验,结合进化算法的全局搜索能力,与博弈进化的局部搜索能力,提出了基于雪堆博弈的自然进化算法GEA和基于雪堆博弈的变异搜索算法SVS,两个算法各有所长。通过大量实验,考察算法在解决复杂网络的最小节点覆盖问题上的表现,验证其有效性。本文的主要工作如下:1.基于记忆的最优反应算法。该算法为复杂网络的最小节点覆盖问题提出一种新的解决思路,利用局部信息和理性个体的记忆能力,启发式地求得MVCP问题的解。我们通过充分的实验,分析该算法的特性以及在不同网络上的性能表现,并深刻剖析其原理,以帮助更好地解决最小节点覆盖问题。2.基于雪堆博弈的自然进化算法。我们借鉴自然进化思想,将网络的节点覆盖结果,即网络中所有节点的状态(覆盖或不覆盖)集合看作一个染色体,作为种群进化中的个体。将网络的节点覆盖与博弈理论相结合,每个节点与自己的邻点进行雪堆博弈,根据最优反应规则获得当前策略并更新策略,当整个网络达到纳什均衡状态时,完成局部最优解搜索。个体组成种群,再通过种群的进化更新,完成全局最优解搜索。通过实验对比,这种算法表现出优于当前经典算法的性能。3.基于雪堆博弈的变异搜索算法。我们将网络中的节点视为理性个体,赋予其判断最优策略的能力,并拥有一定的记忆能力。将博弈理论与复杂网络的节点覆盖问题相联系,引入空间雪堆博弈和基于记忆的最优反应规则,个体通过与邻点的博弈获得当前最优策略并更新记忆。所有个体根据各自的记忆更新策略再博弈,最终网络会达到纳什均衡状态,完成解的初步搜索。再根据自然进化,对初步解进行变异操作,通过进化搜索最终达到全局最优。通过实验,详细分析了算法在不同网络的表现及背后原理,验证了算法对各种网络的最小节点覆盖问题都很很好的适应性。