基于在线检测动态一维下料问题的GPU并行蚁群算法.pdfVIP

学兔兔 第 36卷 第 8期 仪 器 仪 表 学 报 VoL36No．8 2015年 8月 ChineseJournalofScientificInstrument Aug．2015 基于在线检测动态一维下料 问题的 GPU并行蚁群算法 鲁 强，周 新 (中国石油大学(北京)地球物理与信息工程学院 北京 102249) 摘 要：随着在线检测技术发展 ，生产线上的物料需要根据检测结果进行快速切割 。已有一维下料优化问题是根据全局 目标进行建模的，其最优化算法不能满足实时调整切割方案 的要求。本文首先根据物料在线检测及切割特点提出了动 态多规格一维下料优化问题，并给出最优化模型 ；然后结合 GPU特点创建并行蚁群算法来求解多规格动态一维下料 问 题，以保证在有限时间内求得近似最优结果 ；经过算法分析证明，对于大规模数据变量 ，并行蚁群算法效率高于传统蚁群 算法。通过实验表明，在大规模数据量下 ，此并行蚁群算法与传统蚁群算法和分支定界算法相比，能够在较短时间内得 到较优切割方案。 关键词：动态一维下料问题；并行蚁群算法 ；在线检测；GPU计算 中图分类号：TP301 TH74 文献标识码：A 国家标准学科分类代码：510．40 GPU parallelantcolonyalgorithm forthedynamicone-dimensional cuttingstockproblem based on theon—linedetection LuQiang，ZhouXin (CollegeofGeophysicsandInformationEngineering，ChinaUniversityofPetroleum，Beijing102249，China) Abstract：Withthetechnologydevelopmentinon-linedetection，materialsontheproductlineneedtobecutquicklyaccordingtothete- sultofreal—timedetection．Asexistingone—dimensionalcuttingstockproblems(CSP)focusonthemodelglobal optimizationsolution， theiralgorithmsarenotsuitabletocomputetheoptimalcuttingpatternwhichareoftenadjustedbythedetection．Here，thedynamicone’ dimensionalCSPwithmultiplestocklengthsisproposedtosupportthecharacteristics，whichcutstheoptimalstockbaseonon—linede— tection．Inordertogaintheapproximateoptimalsolutioninthelimitedtime，aparallelantcolony(ACO)algorithmiscreatedbythefea— tureofGPU．Throughtheanalysis，theparallelACO algorithm hasbetterperformancethanclassical ACO algorithm whentheyprocess large—sealevariables．Experimentalresultseonfil3TlthattheGPUparallelACO algorithm canobtainthebettersolutioninashorttime， comparedwithclassical ACO algorithm andthebranc