The traditional way of tackling discrete optimization problems is by using local search on suitably defined cost or fitness landscapes. Such approaches are however limited by the slowing down that occurs when local minima, that are a feature of the typically rugged landscapes encountered, arrest the progress of the search process. Another way of tackling optimization problems is by the use of heuristic approximations to estimate a global cost minimum. Here we present a combination of these two approaches by using cover-encoding maps which map processes from a larger search space to subsets of the original search space. The key idea is to construct cover-encoding maps with the help of suitable heuristics that single out near-optimal solutions and result in landscapes on the larger search space that no longer exhibit trapping local minima. The processes that are typically employed involve some form of coarse-graining, and we suggest here that they can be viewed as avatars of renormalisation group transformations.
翻译:传统的离散优化问题解决方法是通过在适当定义的代价或适应度景观上使用局部搜索。然而,当典型的多峰景观遇到局部最小值时,这些方法受到限制,因为搜索过程会减慢。解决优化问题的另一种方法是通过使用启发式近似方法来估计全局代价最小值。在此,我们通过使用覆盖编码图来结合这两种方法,将过程从较大的搜索空间映射到原始搜索空间的子集。关键思想是使用合适的启发式方法构建覆盖编码图,单独选择出接近最优解的解,并在较大搜索空间上产生不再出现诱捕局部最小值的景观。通常采用的过程涉及某种形式的粗粒化,我们在此建议这些过程可以被视为重整化群变换的化身。