摘要翻译：
在本文中，我们研究了执行计算多数任务的细胞自动机(CAs)。这个任务是一个很好的例子，说明什么是复杂系统中的涌现现象。我们对使这种特殊的健身景观变得困难的原因感兴趣。第一个目标是研究这样的景观，因此它在理想情况下独立于用于搜索空间的实际启发式。然而，第二个目标是了解一种针对这个特定问题空间的好的搜索技术应该具备的特征。我们以各种方式统计量化搜索这一景观的难易程度。由于中立性，很难对整个景观进行基于抽样技术的调查。所以，我们从顶部探索景观。虽然没有一个CA能够完美地完成该任务，但已经找到了几个高效的CA来完成该任务。利用这些CAs之间的相似性和景观中的对称性，我们定义了奥林匹斯景观，它被认为是当地已知的最佳景观（blok）的“天堂之家”。然后我们度量了这个子空间的几个性质。虽然在这个子空间中比在整个景观中更容易找到相关的CAs，但有一些结构原因阻止了搜索者在奥林匹斯山中找到过度匹配的CAs。最后，我们在Olympus平台上研究了遗传算法的动力学和性能，以证实我们的分析，并寻找高效的CAs来解决大多数问题。
---
英文标题：
《Fitness landscape of the cellular automata majority problem: View from
  the Olympus》
---
作者：
S\'ebastien Verel (I3S), Philippe Collard (I3S), Marco Tomassini
  (ISI), Leonardo Vanneschi (DISCO)
---
最新提交年份：
2007
---
分类信息：

一级分类：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 study cellular automata (CAs) that perform the computational Majority task. This task is a good example of what the phenomenon of emergence in complex systems is. We take an interest in the reasons that make this particular fitness landscape a difficult one. The first goal is to study the landscape as such, and thus it is ideally independent from the actual heuristics used to search the space. However, a second goal is to understand the features a good search technique for this particular problem space should possess. We statistically quantify in various ways the degree of difficulty of searching this landscape. Due to neutrality, investigations based on sampling techniques on the whole landscape are difficult to conduct. So, we go exploring the landscape from the top. Although it has been proved that no CA can perform the task perfectly, several efficient CAs for this task have been found. Exploiting similarities between these CAs and symmetries in the landscape, we define the Olympus landscape which is regarded as the ''heavenly home'' of the best local optima known (blok). Then we measure several properties of this subspace. Although it is easier to find relevant CAs in this subspace than in the overall landscape, there are structural reasons that prevent a searcher from finding overfitted CAs in the Olympus. Finally, we study dynamics and performance of genetic algorithms on the Olympus in order to confirm our analysis and to find efficient CAs for the Majority problem with low computational cost.
---
PDF链接：
https://arxiv.org/pdf/0709.3974