摘要翻译：
利用最近提出的组合景观模型--局部最优网络(LON)，我们对二次分配问题(QAP)的两类实例进行了深入的分析。这个网络模型是景观的一个简化，其中节点对应于局部最优值，边缘考虑了它们的吸引盆地之间的邻接概念。该模型的灵感来自物理化学中提出的势能表面的“固有网络”概念。从所谓的均匀QAP实例和真实QAP实例中提取的局部最优网络显示出明显区别这两类实例的特征。除了明确证实搜索难度随问题维数的增加而增加外，还提供了新的证实证据，解释了为什么用启发式搜索更容易精确求解真实类实例，而用统一类实例更容易近似求解。虽然局部最优网络模型仍在发展中，但我们认为它提供了一种新颖的组合景观视图，为新的分析工具和理解组合优化中的问题困难开辟了可能性。
---
英文标题：
《Local Optima Networks of the Quadratic Assignment Problem》
---
作者：
Fabio Daolio (ISI), S\'ebastien Verel (INRIA Lille - Nord Europe),
  Gabriela Ochoa, Marco Tomassini (ISI)
---
最新提交年份：
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中的材料。
--

---
英文摘要：
  Using a recently proposed model for combinatorial landscapes, Local Optima Networks (LON), we conduct a thorough analysis of two types of instances of the Quadratic Assignment Problem (QAP). This network model is a reduction of the landscape in which the nodes correspond to the local optima, and the edges account for the notion of adjacency between their basins of attraction. The model was inspired by the notion of 'inherent network' of potential energy surfaces proposed in physical-chemistry. The local optima networks extracted from the so called uniform and real-like QAP instances, show features clearly distinguishing these two types of instances. Apart from a clear confirmation that the search difficulty increases with the problem dimension, the analysis provides new confirming evidence explaining why the real-like instances are easier to solve exactly using heuristic search, while the uniform instances are easier to solve approximately. Although the local optima network model is still under development, we argue that it provides a novel view of combinatorial landscapes, opening up the possibilities for new analytical tools and understanding of problem difficulty in combinatorial optimization.
---
PDF链接：
https://arxiv.org/pdf/1107.4161