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

《基于遗传-蚁群算法的矩形排料研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、·机械制造与研究·蔡汉明，等·基于遗传一蚁群算法的矩形排料研究基于遗传一蚁群算法的矩形排料研究蔡汉明，刘汉斌，冯琳(青岛科技大学机电工程学院。山东青岛266061)摘要：1-I-对矩形件排料问题，将遗传算法与蚁群算法进行融合，提出新的遗传一蚁群算法，并提出了最佳融合时机，最后给出实例证实了遗传一蚁群算法在解决矩形排料问题上的有效性。关键词：矩形排料；遗传算法；蚁群算法中图分类号：TG386文献标志码：B文章编号：1671-5276(2011)06-0024-03ApplicationofGeneticAlgorithmtoLayoutofRectangularCAIHan-ming，

2、LIUHan-bin，FENLin(QingdaoUniversityofScience&Technology，Qingdao266061，China)Abstract：Thisarticlecombinesthegeneticalgorithmandantalgorithmabouttheproblemoflayoutofrectangular，proposesthenewgenetic—antalgorithmandpointsoutthebestcombinedtime．Andfinalyitgivesanexampletoprovethatthisnewalgorithmis

3、efective．Keywords：layoutofrectangular；geneticalgorithm；antalgorithm种方法简单易行，但初始种群的优良程度得不到保证。采0引言用随机的方法产生初始群体很难获得较好的初始群体，即使经过较长时间的运算，也不一定得到令人满意的求解结优化排料是指在给定的板材上尽可能多的排放给定果。种群规模的大小对遗传算法的性能影响很大，规模越规格的零件，使得板材的利用率最高，一个好的排料方案大，群体中个体的多样性就越高，算法陷入局部解的危险可以大大降低企业的生产成本，提高企业的竞争力，因此性就越小，但太大会使算法的计算量增加。本文在具体实优化排

4、样成为企业所关注的重点，矩形排样作为二维排料现时按矩形件个数的多少按面积大小分成三类并按初始的基础，对矩形排料的研究具有重大理论意义和应用的优先级高到低的次序进行分类，确定出矩形排放顺序，价值。用三个三维数组存放这三类矩形件，首先，排放第一类，当布局问题引起人们普遍关注始于加世纪中叶，但是第一类排放完成后再排放第二数，然后是第三类，这样就直到七十年代后期，随着计算机技术和运筹学的发展，计能有效地克服因随机性带来的大规模冗余，提高了初始种算速度突飞猛进，才使得对优化下料问题的理论研究得以群的质量。付诸实践。而且在此后10多年的时间里，此领域的研究空前活跃。模仿人工排样并辅以人工经验和逻

5、辑，学者们1．2适用度函数设计了众多的启发式算法。设n个小矩形的面积分别为A，模板的宽为，高无遗传算法与蚁群算法是当代应用最为广泛的两种算限。将个小矩形，布局在模板上，耗用模板的高度为日，法，将两者结合在一起能有效的提高算法的收敛速度，提定义适应度函数为：高解的质量。A1遗传算法r()遗传算法是仿真生物遗传学和自然选择的机理，通过1．3选择操作人工方式构造的一类搜索算法。某种程度上说遗传算法依适应度函数，按轮盘赌的选择方式选择生存概率大是对生物进化过程进行的模拟仿真。它仿照染色体的基因在进化的过程中进行选择交叉变异生成下一代种群。的个体进入子代。初始化完成后，进行迭代，每次迭代计算每

6、一个个体的适1．4交叉算子应度函数，生成新的种群，基于这种进化机制，保证遗传算法收敛到一个较满意的解。染色体交叉操作I：1)首先选取一个交叉位置；2)互换交叉位置以后的1．1半确定性编码基因片断；3)将重复的基因片断进行处理。常见的产生初始种群的方法是随机生成初始种群，这染色体交叉操作Ⅱ：作者简介：蔡汉明(196O一)，男，湖北黄陂县人，教授，硕士研究生导师，主要研究方向为CAD／CAM技术。·24·http：／／ZZHD．chinajourna1．net．cnE-mail：ZZHD@chainajouma1．net．ca《机械制造与自动化》·机械制造与研究·蔡汉明，等·基于遗传-蚁

7、群算法的矩形排料研究1)利用随机函数在[1，n]之间随机产生两个不相同度，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径过程的数，定位染色体进行交叉片断；2)将两随机数之间的基中的受重视程度，值越大，则该状态转移概率越接近于贪因片断进行相互交换；3)对新产生的染色体进行整理，处婪规则；理原则，从左到右进行比较，对新产生的染色体相同基因rabuk——为禁忌表，保证蚂蚁对同一城市的多次访进行交换，保证两新染色体无重复基因；问，每一只蚂蚁都保存一个列表禁忌表Tabu