论文部分内容阅读
计算机辅助优化排样问题就是将一系列形状各异的物件排放在给定的材料上,找出物件的最优排布,使得给定材料的利用率最高,以达到节约材料,提高效益的目的。从数学计算复杂性理论看,优化排样问题属于具有最高计算复杂性的NP完全问题,至今还无法找到解决该问题的有效多项式时间算法。传统的排样工作都是人工依靠经验进行的,时间长并且效果不理想。由于生产实际的需要,人们迫切需要利用现代科技来解决这一问题。智能优化算法作为现代信息技术,已被广泛应用于许多领域。本文以智能优化算法为基础,尝试用遗传算法解决排样问题,实验结果证明本文提出的方法是有效的。本文的主要工作如下:
(1)针对矩形件排样问题,本文在建立其数学模型的基础上,将遗传算法应用于计算机辅助排样领域,提出了一种改进的解码算法-最低水平线法,将最低水平线法和遗传算法相结合,用于求解矩形件排样问题。该方法首先将矩形件的排样问题转化为便于优化求解的排列问题,然后应用遗传算法的全局优化概率搜索能力进行优化求解,优化计算过程中应用最低水平线法将排样序列转化为排样图。用该算法对一些矩形,圆形和三角形的算例进行了求解,取得了很好的排样结果,并分析了中间出现的各种问题。
(2)应用遗传算法求解二维不规则物件排样问题,首先利用改进的包络矩形算法求取不规则物件的包络矩形,将二维不规则物件的排样问题转化为矩形件的排样问题,然后应用遗传算法进行优化求解,在求解过程中应用自适应调整规则对物件的排样位置进行微调,排样结果表明该算法是有效的。在综合利用计算几何、计算机图形学、组合优化的知识的基础上,提出了基于自动碰撞来解决二维不规则物件的思路。
(3)三维集装箱方面,本文在考虑一些实际应用中的约束条件外,提出了一种三维集装箱装载的时分片算法。在装载的同时不断对三维体虚拟切割分片,然后利用改进的剩余空间法对片空间进行分析和虚拟装填,通过非完全树的结构和递归搜索过程来实现最优装载模式的求解,并通过若干片的重新组合实现货物的重心平稳最优化。
(4)利用遗传算法我们采用面向对象的开发技术,在JAVA开发环境下,通过对不同算例,不同参数的数值试验,进一步分析了遗传算法中参数设置对排样结果的影响。给出了在不同场合参数设定的建议,提高了算法的适应性,拓宽了应用领域。实例分析表明,本文提出的理论和方法具有良好的实用价值。