Pelillo Marcello, Torsello Andrea
Dipartimento di Informatica, Università Ca' Foscari di Venezia 30172 Venezia Mestre, Italy.
Neural Comput. 2006 May;18(5):1215-58. doi: 10.1162/089976606776241011.
Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.
进化博弈论模型，尤其是所谓的复制方程，最近已被证明在近似求解最大团及相关问题方面非常有效。该方法围绕图论中的一个经典结果展开，该结果将最大团问题表述为一个标准的（连续）二次规划，并利用这些模型的动力学性质，在一定的对称假设下，这些模型具有一个李雅普诺夫函数。在这封信中，我们在几个方面对以前沿这些思路开展的工作进行了推广。我们引入了一类广泛的博弈动力学方程，称为收益单调动力学，复制动力学是其中的一个特殊实例，并表明它们具有与标准复制方程完全相同的动力学性质。这些性质使该族中的任何一个成员都成为求解标准二次规划，特别是最大团问题的潜在启发式方法。在随机以及DIMACS基准图上进行的大量模拟表明，这类动力学比复制方程快得多且至少同样准确。然而，与这些模型相关的一个问题是它们无法摆脱较差的局部解。为了克服这一缺点，我们关注用于通过模仿过程对行为演化进行建模的收益单调动力学的一个特定子类，并研究当正则化参数被允许取负值时其平衡点的稳定性。对这些性质的详细分析提出了一类用于最大团问题的退火模仿启发式方法，其基于在模仿优化过程中有原则地改变参数的思想，以避免出现不必要的低效解。实验表明，所提出的退火过程确实有助于通过最初将动力学驱动到状态空间中有希望的区域来避免较差的局部最优解。此外，这些模型在最大团问题上优于诸如平均场退火等当前最先进的神经网络算法，并且与强大的基于连续的启发式方法相比也毫不逊色。
