标题： 基于模型的遗传算法的工作原理属于PAC框架：问题分解的数学理论 显示英文标题

标题： The working principles of model-based GAs fall within the PAC framework: A mathematical theory of problem decomposition

摘要： 链接、建筑块和问题分解的概念在遗传算法（GA）领域早已存在，并在数十年中指导了基于模型的GAs的发展。 然而，它们的定义通常模糊，使得发展理论支持变得困难。 本文提供了一个与算法无关的定义来描述链接的概念。 通过这个定义，本文证明了任何具有有限链接度的问题都是可分解的，并且可以通过链接学习实现适当的问题分解。 本文给出的分解方法也从理论上为具有有限难度和建筑块的近似可分解问题提供了新的视角。 最后，本文将问题分解与PAC学习联系起来，并证明在某些条件下，这些问题的全局最优解和最小分解块是PAC可学习的。 显示英文摘要

摘要： The concepts of linkage, building blocks, and problem decomposition have long existed in the genetic algorithm (GA) field and have guided the development of model-based GAs for decades. However, their definitions are usually vague, making it difficult to develop theoretical support. This paper provides an algorithm-independent definition to describe the concept of linkage. With this definition, the paper proves that any problems with a bounded degree of linkage are decomposable and that proper problem decomposition is possible via linkage learning. The way of decomposition given in this paper also offers a new perspective on nearly decomposable problems with bounded difficulty and building blocks from the theoretical aspect. Finally, this paper relates problem decomposition to PAC learning and proves that the global optima of these problems and the minimum decomposition blocks are PAC learnable under certain conditions.