蚁群算法在一维下料优化中的应用

《蚁群算法在一维下料优化中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、蚁群算法在一维下料优化中的应用摘要：本文研究了一维下料优化问题，建立了一维下料优化的双目标多约束数学优化模型,并给出了求解模型的蚁群算法的具体实现过程；针对模型的特殊性，提出了零件编码和将所有下料方式首尾连接转化为蚂蚁路径的方法。通过一个一维下料实例进行验证，计算结杲表明，此算法可逼近理论最优解，收敛速度较快，理论上可解决多规格大规模的一维下料优化问题。关键词：一维下料；蚁群算法；优化；AntColonyAlgorithmsforOne-dimensionalCutting-stockProblemAbstract:One-dimensionalcutting-st

2、ockproblemwasstudied.Basedontheseanalyses,themathematicalmodelofone-dimensionalcutting-stockproblemforbi-objectiveandmultirestrictedconditionissetup.Tosolvethemodel,aanlcolonyalgorithmisdeveloped.Inthisalgorithm,accessorychromosomeandthecutting-stockasant^spathispresentbecauseofthespe

3、cialpointofthemodel.Then,anone-dimensionalcutting-stockproblemisshown.Computeresultsindicatedthattheantcolonyalgorithmcanapproachasuperiorsolutionoftheories,anditsastringencyisgood・Intheory,itcansolvethelarge-scaleofone-dimensionalcutting-stockproblem.Keywords:one-dimensionalcutting-st

4、ock;antcolonyalgorithms;optimization1引言"卜料问题(cuttingstockproblem)”是把相同形状的一些原材料分割加工成若干个不同

5、规格大小的零件的问题，这类问题经常出现在计算机科学、工业工程和机械制造等领域，在工程技术和工业生产屮有着重要和广泛的应用。精确求解下料问题屈于NP问题，再加上下料方式数等限制后，这是问题的求解是比较复杂的，目前还不可能用一个精确的方法来求此问题。一维下料优化问题是讨论从一种规格的材料中，分割出各种不同长度的坯料，以使材料的利用率最高，从而达到最大限度地节约材料。目前，国内外关于这方面的研究十

6、分活跃，并涌现出了不少近似算法，如线性规划⑴，动态规划方法⑵等，但当原材料的数量和所需产品的个数都很大时，问题的规模会迅速增加变得非常复杂，利用这些算法求解不具有可操作性且很难或者几乎不可能得到最优方案。由于下料问题不同于一般的数值性优化，近年来又出现了应用遗传算法⑶、贪焚算法⑷、启发式算法⑸等算法和思想求解下料优化问题，但是这些新的算法不可避免会出现收敛速度慢，陷入局部极小值等问题。因此本文针对这些问题，根据一维下料优化问题是一个经典的组合优化问题，提出了一种基于蚁群算法的新方法，并采用实例进行验证，得到了很好的效果。2一维下料优化模型的建立，加)给定〃种长度的坯

7、料厶,厶，人,所需的数量分别为％已知原材料长度为Lo设有m种可能的下料方式，每种下料方式的重复次数为®(j=1,2,,m)0在方式丿•中，第i件坯料的重复次数为a(i(z=1,2,曲)，每个切缝处由于据缝所产生的损耗为厶从而建立如下数学模型:目标函数：加m打minF=厶工①—工工也內j=lj=l/=1minmL+Ls—工(/,+Ls)a、j>0,(7=1,2,1=11,(7=1,2,,m)工®®y=i,2,,/?)2一维下料优化的蚁群算法设计蚁群算法(antcolonyalgorithm)最初是由意大利学者M.Dorigo等提出的一种基于种群的启发式仿生进化系统。蚁

8、群算法最早用于解决著名的旅行商问题(TSP,travelingsalesmanproblem),采用了分布式正反馈并行计算机制，易于与其他方法结合，并具有较强的鲁棒性⑹。如今，这一新兴的仿生优化算法已经成为人工智能领域的一个研究热点，目前对其研允己渗透到多个应用领域，在国内外许多学术期刊和重要国际会议上，蚁群算法已成为交叉学科屮一个非常活跃的前沿性研究问题。根据信息素更新策略的不同，M.Dorigo提出了三种不同的基本蚁群算法模型，分别称Z为Ant-Cycle模型>Ant-Quantity模型及Ant-Density模型⑺，本文提出采用Ant-Cycle模型。3