论文部分内容阅读
二维矩形件优化排样问题普遍存在于玻璃、钢板、木材、纸张、制衣和船舶等行业中。一个好的排样方案可以节省原材料,降低生产成本,直接给企业带来经济效益,提高企业的核心竞争力。该问题在理论上是具有最高计算复杂性的NP完全问题,随着问题规模的扩大,将很难用精确算法求得最优解。因此,开展对二维矩形件优化排样问题的研究具有重要的理论意义和工程应用价值。 本文在分析矩形件优化排样问题特点的基础上,建立了该问题的数学模型,分别应用三种方法进行优化求解,对不同约束条件下的算例的求解结果进行了比较和分析。 首先采用遗传算法对矩形件排样问题进行了求解。在求解过程中,给出了遗传算法求解的编码方法、适应度函数的定义、遗传算子以及关键参数。经过具体的算例求解,发现该算法在一般情况下可以求得较好的优化结果。 然后针对遗传算法在初始解群分布不均匀,容易陷入局部最小值而过早收敛的缺点,提出一种免疫算法对矩形件排样问题进行了求解。算例求解的结果表明,免疫算法中的基于浓度的群体更新策略可以有效地保持抗体的多样性,改善早熟收敛现象,取得了比遗传算法更好的优化结果,但是存在算法运行时间偏长的缺点。 最后在基本免疫算法的基础上,通过重新定义抗体间的相似度,改进抗体浓度的计算方法,并加入接种疫苗操作,提出了一种改进的免疫算法。经过具体算例的求解和比较分析,发现其求解结果在总体上优于遗传算法和免疫算法,并且算法的运行速度比基本免疫算法有了明显的提高。