发帖
雷达卡
摘要翻译：
本文介绍了求解最大团问题的一种新的随机局部搜索算法DLS-MC。DLS-MC在迭代改进阶段和平台搜索阶段之间交替，迭代改进阶段将合适的顶点添加到当前组中，平台搜索阶段将当前组的顶点与当前组中不包含的顶点交换。顶点的选择完全基于在搜索过程中动态调整的顶点惩罚，并使用扰动机制来克服搜索停滞。DLS-MC的行为由单个参数惩罚延迟控制，惩罚延迟控制顶点惩罚减少的频率。我们的经验表明，DLS-MC在很大范围内的DIMACS基准实例中，在最大团问题上取得了比现有算法更大的性能改进。
---
英文标题：
《Dynamic Local Search for the Maximum Clique Problem》
---
作者：
H. H. Hoos, W. Pullan
---
最新提交年份：
2011
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, during which vertices of the current clique are swapped with vertices not contained in the current clique. The selection of vertices is solely based on vertex penalties that are dynamically adjusted during the search, and a perturbation mechanism is used to overcome search stagnation. The behaviour of DLS-MC is controlled by a single parameter, penalty delay, which controls the frequency at which vertex penalties are reduced. We show empirically that DLS-MC achieves substantial performance improvements over state-of-the-art algorithms for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.
---
PDF链接：
https://arxiv.org/pdf/1109.5717
京公网安备 11010802022788号
