基于遗传算法与蚁群算法的矩形排料研究.pdf

基于遗传算法与蚁群算法的矩形排料研究
摘 要
优化排料是指在给定的板材上尽可能多的排放给定规格的零件, 使得板材的
利用率最高, 一个好的排料方案可以大大降低企业的生产成本, 提高企业的竞争
力, 因此优化排样成为众多企业所关注的重点, 矩形排样作为二维排料的基础,
对矩形排料的研究具有重大理论意义和应用价值 。
排料布局能从源头上解决效率和质量两方面的问题, 它涉及到计算几何 、 计
算机图形学 、 运筹学 、逻辑推理等多学科知识, 属于具有最高计算复杂性的优化
计算问题 问题 。就目前来言, 众多学者已经提出了各种方法 :遗传算法、
蚁群算法 、 模拟退火算法等优化算法, 本文通过比较得出遗传算法 、 蚁群算法各
自的优缺点, 融合提出了遗传 蚁群算法 。
考虑到大规模矩形排样问题中经常遇到的随机生成染色体与种群的问题, 对
基因编码和初始化种群做出了改进, 并在进行排料前做了预先处理, 收到良好的
效果 。
针对交叉算子, 提出了一类新的交叉方式, 使得交叉多样化, 保证了种群的
多样化, 有效的预防了早熟现象的发生 。
在处理实际问题中, 进行参数设置时, 蚁群算法往往只考虑到面积这一单一
因素, 本文综合考虑到面积与宽高比例两个因素, 动态生成了期望启发因子, 并
给出了一个相对合理的权重, 使得算法更加的完善 。
最后, 给出了两个实例, 说明该算法的有效性, 实用性 。
关键词 :矩形排料 遗传算法 蚁群算法 融合
I
R esearch on Layout of R ectangular Parts Based on G enetic
A lgorithm and Ant A lgorithm
A BSTRA CT
The optim al layout of rectangular means arraying as m any parts as possible on the
given plate, in order to improve the utilization ratio of the plate. A good solution can
decrease the cost of production obviously, im prove the com petition, so m any
m anufactures pay m ore and more attention to the optimal layout. T he layout of
rectangular is the basem ent of two-dim ensionality layout, so the research in layout of
rectangular is significant on the theory research and valuable on application.
Packing problem can solve the problem about both efficiency and quality from the
source, it is concerned with geom etry, com pu