矩形布局问题的全局搜索关键技术

The problem of rectangular layout is not only a hot topic in the field of computer science and combinatorial optimization, but also an urgent problem to solve the cutting and filling of rectangular plate in industry as well. Based on the previous research, in view of the lack of research on the canyon landforms in a pattern and the shortcoming of the widely used local preferred method whose search is only on the surface of the pattern, this project explores a dynamic beam search algorithm with ability of entering the interior of the pattern by creating and alternately calling the rule vectors to. Based on the algorithms, in accordance with the connection between any two nodes on a space tree and their common ancestor, we study a global search strategy for internal search in depth pattern after constructing long term historical data chain by taking advantage of on path relinking technology.Finally, based on the associative mechanism of the global search strategy and double tabu strategy, we pursue a new hybrid global search method to enhance the search within the pattern by merging dynamic beam search, path relinking and tabu search technology. .This project is not only a new attempt for solving the problem of rectangular layout, but also a new idea of the global search on the solution space tree. The results can provide both a theoretical basis for solving the high dimensional rectangular layout problem and plate cutting scheme for our provincial furniture manufacturing enterprises.

矩形布局问题是计算机科学和组合优化领域的研究热点问题，也是工业上矩形板材切割与填装亟需解决的难题。本项目在前期研究的基础上，针对当前对格局中峡谷地貌缺少研究以及广泛使用的局部择优方法只在格局表面进行搜索的不足，通过创建并交替调用规则向量，研究可以进入格局内部搜索的动态集束搜索算法。在此算法的基础上，根据解空间树上任意两个节点与其公共祖先的连接关系，利用路径重连技术构建解的长期历史数据链，研究可深入格局内部搜索的全局搜索策略。最后，基于这种全局搜索策略和双层禁忌策略的联合使用机制，研究融合动态集束搜索、路径重连技术和禁忌搜索技术的新型混合式全局搜索方法以增强对格局内部的搜索，提升算法优化性能。.本项目既是对当前求解矩形布局问题的一种新尝试，也是基于解空间树的全局搜索的一个新思路，其结果可以为求解高维矩形布局问题提供理论依据，并为我省家具制造企业提供板材切割方案支持。

本项目研究典型的NP-难问题——矩形切个问题，本项研究具有很深的应用背景，例如玻璃切割、钢材切割、产品包装、文本排版以及物品摆放等等。高效求解算法可以提高生产效率、降低成本，还可以启发设计求解相关难问题的高效算法。本项目主要研究内容主要涵盖以下三个部分，项目成果包括在国内外期刊上发表论文14篇（SCI收录4篇，EI收录9篇），获PAAP 2019 最佳论文奖。获1项发明专利和3项软件著作权。.其一，提出基于动态规划的集束搜索算法：在构造离散集的做法时，将切割位置的右边界与上边界扩展到最大；仅在不带缺陷的子板上做标准切割，在带缺陷的子板上做去标准化处理；考虑缺陷区域的边界位置，设计拟人策略，在距离缺陷左右边界外和上下边界外的一个单位处进行子问题分解。算法将问题分解为多个局部矩形切割问题。在第一阶段切出毛坯，用集束搜索法求解每个区域，定义以边距为指标的动作选择规则，并对其进行了逐一操作，求解局部最优解，从而达到全局最优目标。.其二，提出结合剪枝策略的高效递归算法：同时以板材左(下)边界和板材包含的缺陷右(上)边界为起点，组合货物的宽高构造切割点离散集，推广了Herz定理的结论；重新定义了纯净板的下界，它仅由纯净板与货物尺寸的比例关系来确定；为缺陷板定义一种下界，并结合离散集的组合性，提出剪枝策略。.其三，研究萤火虫算法的基本特性以及对它的基础改进策略：通过动态步长模型调整萤火虫算法在演化过程中的搜索状态——调节吸引力参数，保持萤火虫群体在搜索过程中的空间多样性；设计具有alpha和beta的比例调整策略，提出一种基于距离控制的自适应步长策略；提出一种基于欧氏度量和维数变异的萤火虫算法，它的EM策略使萤火虫向最近的邻居学习，当萤火虫比它的邻居更好时，它会向种群中最好的个体学习。除了上述内容之外，本项目在安全方案中NP难题的高效求解等方面进行了相关研究，取得一定的研究成果。