融合蚁群算法和遗传算法的矩形件排样问题研究.pdfVIP

摘要 摘要 矩形件排样是指将若干尺寸相同或不相同的矩形零件在给定的矩形板材上 以最优的方式排布。矩形件排样问题普遍存在于工程领域中，如钣金下料、玻 璃切割、造船、车辆、家具生产、报刊排版、服装和皮革裁剪等。较好的排样 方案可以最大限度地节约原材料，提高原材料利用率，从而降低生产成本，在 经济上制造可观的效益。 在理论上，矩形件排样问题属于组合最优化问题和具有最高计算复杂性的 NP完全问题。用现在常用的计算理论和方法很难精确地求得问题的最优解，只 能在一定的时间范围内求其局部最优的近似解。启发式智能优化方法是近年发 展起来的非常活跃的研究领域，如遗传算法、模拟退火算法、蚁群算法、神经 网络、粒子群算法等，它们都可以有效的解决组合优化和NP类问题。 本文是在介绍了遗传算法和蚁群算法各自特点的基础上，提出将两种算法 相融合来求解矩形件排样问题。融合算法的前阶段采用遗传算法，充分利用遗 传算法的快速随机性、全局收敛性的优点，获得排样序列的部分优化解，并以 此作为下阶段蚁群算法的初始信息素分布；融合算法后阶段采用蚁群算法，利 用其优良的正反馈机制和高效收敛性的优点，精确求得最优排样序列。 此外，本文在建立矩形件排样问题数学模型的基础上，分析了常见的矩形 件给定排放顺序的排放算法的优缺点，提出了一种改进的排放算法。该算法充 分考虑矩形件长度和宽度对排样效果的影响，加入了旋转策略，并改进了有哪些信誉好的足球投注网站 策略。将此改进算法分别与遗传算法和融合算法结合求解矩形件排样问题，计 算实例表明了该改进排放算法更为有效，并能够和融合算法较好的结合，得到 更好的排样效果。 关键词：矩形件排样 改进排放算法蚁群算法遗传算法算法融合 Abstract A bstract meansto ofdifferentsizeorsame Reetangluarpacking arrangerectangluarparts sizeata withthe is givenrectangularplate optimalway．Rectangluarpackingproblem facedin assheetmetal of field，such glass， commonlyengineering cutting，machining of andSO shipbuilding，manufacturingautomobiles，clothing，furnituremanufacturing be the on．Withabetter materialcan saved packingpattern，the obviously,and costCanbe economicbenefitsCanbeincreased． production reduced，and isacombinatorial and Rectangluarpackingproblem optimizationproblem totheNPcomlete withthemost in belong