基于Backbone的空间收缩与划分算法

Space contracting and decomposing algorithm based on Backbone

搜索空间的规模和复杂程度是决定问题求解难度的重要因素,而解空间的信息往往可以引导搜索找到最优解。在已知JSP空间结构的基础上,提出一种空间收缩与划分算法。算法利用搜索算法获得的较优解,结合组合优化问题解的backbone的概念,将搜索空间收缩并划分为一个或多个优解域,在优解域内再进行小规模问题的优化。该算法不必在求解前或求解过程中进行大量的统计分析工作,可以利用求解信息对解空间的地形进行估计,提高求解速度和解的质量。实验结果也证明了算法的有效性。

The scale and complexity of search space are important factors to decide the solving difficulty of an optimization problem. The information of solution space may lead searching to optimal solutions. Based on the known space structure of job shop scheduling problem, a space contracting and decomposing algorithm is proposed. This algorithm makes use of the good solutions found by searching algorithms, contracts the search space and decomposes it into one or several optimal regions combined with the concept of Backbone of combinatorial optimization solutions. And optimization of small - scale problems is carried out in optimal regions. Statistical analysis is not necessary before or through solving in this algorithm, and solution information is used to estimate the landscape of search space, which enhances the speed and solution quality. The experiments results testify the efficiency of this new algorithm.