资源描述：
《蚁群算法在一维下料优化问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2008年12月机械科学与技术December2008第27卷第12期MechanicalScienceandTechnologyforAerospaceEngineeringVol.27No.12蚁群算法在一维下料优化问题中的应用吴正佳,张利平,王魁(三峡大学机械与材料学院,宜昌443002)吴正佳摘要:研究了一维下料优化问题,建立了一维下料的双目标多约束数学优化模型,并给出了求解模型的蚁群算法的具体实现过程;针对模型的特殊性,提出了零件编码和将所有下料方式首尾连接转化为蚂蚁路径的方法,并讨论了初始化参数变量的选择问题。通过一维下料实例进行验证,计算结果表明,此算法可
2、逼近理论最优解,收敛速度较快,理论上可以解决多规格大规模的一维下料优化问题。关键词:一维下料;蚁群算法;优化中图分类号:TB278文献标识码:A文章编号:100328728(2008)1221681204AnAntColonyAlgorithmforOne2dimensionalCutting2stockProblemWuZhengjia,ZhangLiping,WangKui(CollegeofMechanicalandMaterialEngineering,ChinaThreeGorgesUniversity,Yichang443002)Abstract:One2d
3、imensionalcutting2stockproblemwasstudied.Themathematicalmodelofone2dimensionalcut2ting2stockproblemforbi2objectiveandmulti2constraintsissetup.Tosolvethemodel,anantcolonyalgorithmisdeveloped.Inthisalgorithm,accessorychromosomeandthecutting2stockistransformedintoanantpath.Howtoselecttheini
4、tialparametersisdiscussed.Then,thealgorithmisappliedtoaone2dimensionalcutting2stockprob2lem.Computedresultsindicatethattheantcolonyalgorithmcanapproachthetheoreticaloptimalsolution,anditsastringencyisgood.Keywords:one2dimensionalcutting2stock;antcolonyalgorithm;optimization“下料问题(cuttings
5、tockproblem)”是把相同形大时,问题的规模会迅速增加变得非常复杂,利用这状的一些原材料分割加工成若干个不同规格大小零些算法求解不具有可操作性且很难或者几乎不可能件的问题,这类问题经常出现在计算机科学、工业工得到最优方案。由于下料问题不同于一般的数值性[3～5]程和机械制造等领域,在工程技术和工业生产中有优化,近年来又出现了应用遗传算法、贪婪算着重要和广泛的应用。精确求解下料问题属于NP法[6]、启发式算法[7]等算法和思想求解下料优化问问题,再加上下料方式数等限制后,这类问题的求解题,但这些新的算法不可避免会出现收敛速度慢,陷是比较复杂的,目前还不可能用一个精
6、确的方法来入局部极小值,计算时间长等问题。另外,蚁群算法求此问题。通过模拟搜索食物的行为,采用正反馈结构、并行计目前,国内外关于这方面的研究十分活跃,涌现算与启发式因子相结合的一种新兴的仿生优化算[1]出了不少近似算法,如线性规划,动态规划方法,尤其适合于求解组合优化问题。因此,本文针对[2]法等,但当原材料的数量和所需产品的个数都很这些问题,根据一维下料优化问题是一个经典的组合优化问题,提出了一种基于蚁群算法的新方法,并收稿日期:2007212205通过实例验证了该算法的有效性。作者简介:吴正佳(1964-),教授,博士,研究方向为信息系统与集成、机械制造及自动化,z
7、jwu@ctgu.edu.cn1682机械科学与技术第27卷1一维下料优化模型的建立式中:q为加权系数。给定n种长度的坯料l1,l2,⋯,ln,所需的数量对于一只蚂蚁来说,它根据信息素概率选择某分别为b1,b2,⋯,bn,已知原材料长度为L。一路径,因此,在一维下料优化问题中,首先将不同设有m种可能的下料方式,每种下料方式的重的和相同的零件进行编码,认为每个零件都是独立复次数为xj(j=1,2,⋯,m)。在方式j中,第i件坯料的,其次,将一条蚂蚁的行驶路径,看成所有的下料的重复次数为aij(i=1,2,⋯,n),每个切缝处由于方式首尾相连
