摘要翻译：
最近，连通性的性质被认为是设计多目标组合优化(MOCO)的局部搜索技术的强大动力。事实上，当连通性成立时，用至少一个非支配解初始化的基本Pareto局部搜索允许穷举地识别有效集。然而，这在实践中很快变得不可行，因为有效解决方案的数量通常随实例大小呈指数增长。因此，我们通常必须处理一个有限大小的近似，在那里必须找到一个好的样本集。本文提出了双目标多重长路径问题，通过实验证明，在第一个问题上，即使有效集是连通的，在有效集的抽样中，局部搜索可能优于简单的进化算法。相反，在第二个问题上，局部搜索算法可以成功地逼近一个不连通的有效集。然后，我们认为连通性并不是设计MOCO局部搜索启发式所要研究的唯一性质。这项工作为多目标适应度景观的正确定义开辟了新的讨论。
---
英文标题：
《On the Effect of Connectedness for Biobjective Multiple and Long Path
  Problems》
---
作者：
S\'ebastien Verel (INRIA Lille - Nord Europe), Arnaud Liefooghe (INRIA
  Lille - Nord Europe, LIFL), J\'er\'emie Humeau (INRIA Lille - Nord Europe),
  Laetitia Jourdan (INRIA Lille - Nord Europe, LIFL), Clarisse Dhaenens (INRIA
  Lille - Nord Europe, LIFL)
---
最新提交年份：
2012
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Neural and Evolutionary Computing        神经与进化计算
分类描述：Covers neural networks, connectionism, genetic algorithms, artificial life, adaptive behavior. Roughly includes some material in ACM Subject Class C.1.3, I.2.6, I.5.
涵盖神经网络，连接主义，遗传算法，人工生命，自适应行为。大致包括ACM学科类C.1.3、I.2.6、I.5中的一些材料。
--
一级分类：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中的材料。
--

---
英文摘要：
  Recently, the property of connectedness has been claimed to give a strong motivation on the design of local search techniques for multiobjective combinatorial optimization (MOCO). Indeed, when connectedness holds, a basic Pareto local search, initialized with at least one non-dominated solution, allows to identify the efficient set exhaustively. However, this becomes quickly infeasible in practice as the number of efficient solutions typically grows exponentially with the instance size. As a consequence, we generally have to deal with a limited-size approximation, where a good sample set has to be found. In this paper, we propose the biobjective multiple and long path problems to show experimentally that, on the first problems, even if the efficient set is connected, a local search may be outperformed by a simple evolutionary algorithm in the sampling of the efficient set. At the opposite, on the second problems, a local search algorithm may successfully approximate a disconnected efficient set. Then, we argue that connectedness is not the single property to study for the design of local search heuristics for MOCO. This work opens new discussions on a proper definition of the multiobjective fitness landscape.
---
PDF链接：
https://arxiv.org/pdf/1207.4628