论文部分内容阅读
研究了二维矩形packing这一类NP难度问题。在黄文奇等人提出的拟人型穴度算法的基础之上，提出了基于动作空间的拟人型穴度算法，通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法既继承了原有穴度算法的优势，又能够快速地得到面积利用率较高的布局图案。重点研究了二维矩形装填问题，给出了格局、动作空间、占角动作、平整度、评价标准和比较策略的定义。基于动作空间，简化了对不同放入动作的评价，明显缩短了计算时间。在算法的设计中，着重考虑了如何分割矩形框内的剩余空间使放入块与周围的已放入块更紧密、采用哪种数据结构使得剩余空间的更新更快捷、如何选取一个唯一的占角动作使之遵循“可持续发展的路线”、选取哪种搜索策略可以使结果不断趋近全局最优解而不至于陷入局部最小值的陷阱。进一步地，将此算法适当调整以求解二维strip packing问题和二维矩形packing价值优化问题。针对二维strip packing问题的特点，结合了加1法和二分法以求解已知矩形敞口框的最优高度和未知矩形敞口框的最优高度的两类子问题。针对二维矩形packing价值优化问题的特点，修改了占角动作的比较策略，加入了放入块的单位价值作为比较因子，并将目标函数调整为所有放入块的总价值。对二维矩形装填问题、二维strip packing问题和二维矩形packing价值优化问题，试算了国际上著名的相关算例。所提出的算法均能在较短的时间内得到较优的结果。对二维矩形装填问题，在Hopper和Turton提出的21个著名算例的每个实例上，所提出的算法均在较短的时间内得到了面积利用率为100%的最优布局；对Burke等人提出的13个算例，得到了7个最优解且平均面积利用率为99.84%，刷新了目前国际上已见发表的最好结果。对二维strip packing问题和二维矩形packing价值优化问题，所提出的求解算法的计算结果也接近国际上已见发表的最好结果。