Adaptive Networks and Control Laboratory, Department of Electronic Engineering, Fudan University, Shanghai 200433, China.
IEEE Trans Cybern. 2013 Jun;43(3):948-56. doi: 10.1109/TSMCB.2012.2218805. Epub 2012 Oct 18.
To solve the vertex cover problem in an agent-based and distributed networking systems utilizing local information, we treat each vertex as an intelligent rational agent rather than an inanimate one and provide a spatial-snowdrift-game-based optimization framework to vertex cover of networks. We analyze the inherent relation between the snowdrift game and the vertex cover: Strict Nash equilibriums of the spatial snowdrift game are the intermediate states between vertex-covered and minimal-vertex-covered states. Such equilibriums are obtained by employing the memory-based best response update rule. We also find that a better approximate solution in terms of the minimal vertex cover will be achieved by increasing the individuals' memory length, because such a process optimizes the individuals' strategies and helps them convert from bad equilibriums into better ones. Our findings pave a new way to solve the vertex cover problem from the perspective of agent-based self-organized optimization.
为了解决基于代理的分布式网络系统中的顶点覆盖问题，利用局部信息，我们将每个顶点视为智能理性代理，而不是无生命的代理，并提供基于空间推雪球游戏的网络顶点覆盖优化框架。我们分析了推雪球游戏和顶点覆盖之间的内在关系：空间推雪球游戏的严格纳什均衡是顶点覆盖和最小顶点覆盖状态之间的中间状态。通过使用基于记忆的最佳响应更新规则，可以获得这种均衡。我们还发现，通过增加个体的记忆长度，可以获得更好的最小顶点覆盖近似解，因为这个过程优化了个体的策略，帮助它们将坏均衡转化为更好的均衡。我们的发现为从基于代理的自组织优化的角度解决顶点覆盖问题开辟了一条新途径。
