搜索
上海交通大学硕士学位论文数控等离子切割机的路径优化姓名：何汉武申请学位级别：硕士专业：控制工程指导教师：陈卫东;俞力生20081130上海交通大学工程硕士学位论文摘要第I页数控等离子切割机的路径优化摘要当今中国的船舶工业高速发展，各种先进的自动化设备广泛应用于生产以提高生产效率。钢材切割是船舶制造的第一道工序，先进的数控等离子切割机的使用不断增多。数控等离子切割机所使用程序的切割路径规划的好坏直接影响了切割的效率。本文对切割路径规划的优化进行研究，并提出两种不同的优化算法来优化切割路径，以减少切割空行长度，增加切割有效工作时间，从而提高切割效率。在数学上切割路径优化问题可以转化为TSP问题。TSP问题应用广泛，是昀经典的NP-hard组合优化问题之一。由于其计算的复杂性较高,长期以来,研究者一直在寻求快速、高效的近似算法,以便在合理的时间内解决问题。目前解决TSP问题一般采用传统启发式算法和现代启发式算法。都是依据经验或法则来搜索合理的解。在传统算法中本文提出贪婪算法来研究解决该问题。贪婪算法是一步算法，主要受贪婪法则的控制。它的实现过程相较简单，计算时间较短，而且优化结果较好。为解决贪婪算法的解不与其它可行解比较的问题，本文首次提出了在局部点内进行局部可行解之间比较求优的办法来求得更好的解。经过实验证明贪婪算法生成的切割路径相较于TRIBON程序生成的路径的优化效果也比较明显。遗传算法(GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索的现代启发式算法。它特别适合于处理传统搜索算法上海交通大学工程硕士学位论文摘要第II页解决不好的复杂和非线性问题。遗传算法计算结果的好坏主要受到各遗传算法参数的影响，而计算复杂度主要受群体规模、遗传代数等参数控制。遗传算法在参数的选择上仍缺乏有力的理论证明，所以需要大量的试验来验证参数的合理性。本文在基本遗传算法的基础进行了改进，首先使用新的路径编码方式来减少路径编码长度、降低计算复杂程度；其次应用改进的选择算子，在运行初期减小不同个体的适应度差异避免早熟现象，后期增加个体的适应度差异来快速收敛，提高算法效率。通过实例有力验证了该算法的有效性，平均能够减少空行路径15%。结论指出：贪婪算法和遗传算法在解决切割路径优化问题时都表现出一定的潜力，并取得了非常不错的效果。但他们都无法做到完美。实际上应该针对不同的需求和实际情况采用更合适的算法。昀后对今后的研究提出展望。关键词：切割路径优化，数控等离子切割，TSP问题，贪婪算法，遗传算法上海交通大学工程硕士学位论文ABSTRACT第III页PATHOPTIMIZATIONOFNCPLASMACUTTINGMACHINEABSTRACTNowadayschina’sshipbuildingindustrydevelopsrapidly,andvariousadvancedauto-machineisappliedtomanufactureinordertoimproveefficiency.Steelcuttingisthefirstworkingprocedureofshipbuilding,andadvancedNCplasmacuttingmachineisusedwidely.Theprogram’spathprogrammingofNCplasmacuttingmachineaffectthecuttingefficiencydirectly.Inthispaper,weresearchthecuttingpathscheduling,andsuggesttwodifferentoptimizationalgorithmforthecuttingpath.Andweexpectthattheycanreducethecuttingblankline,increaseeffectivecuttingtime,soastoimprovethecuttingefficiency.CuttingpathoptimizationproblemcanbereturnorchangedintoTSP(TravelingSalesmanProblem).TSPisoneofthetypicalNP-hardproblemsincombinatorialoptimizationproblemwhichisknownforitsdiverseapplications.Becauseofdifficultyofitssolution,especiallyforlarge-scaleproblem,forlongtimeresearchershadbeentryingtofindfastandefficientapproximatealgorithmsinordertosolveprobleminreasonabletime.NowwecurrentlyadopttraditionalheuristicsmethodsandmodernheuristicsalgorithmstosolvetheTSP,whichsearchthereasonablesolutionbyexperienceandprinciple.Wechoosegreedyalgorithmintraditionalmethods.Greedyalgorithmisone-stepalgorithm,andmainlycontrolledbygreedycriterion.Greedyalgorithmiseasytorealize,it’scomputingtimeisshort,andoptimizationresultisacceptable.Tosolvetheproblemthatitssolutionisn’tcomparedwithotherviablesolutions,thispaperfirstputforwardcomparingthelocalviablesolutionsinlocalpointstoaskforbettersolution.Experimentprovedthatthe上海交通大学工程硕士学位论文ABSTRACT第IV页cuttingpathgeneratedbygreedyalgorithmisobviouslybetterthanthepathgeneratedbyTRIBONsoftware.Thegeneticalgorithm(GA)isahighlyparallel,randomandself-adaptingsearchalgorithm,whichrefertothebiologyheredityandevolutionprocess.Itisespeciallyfitforcomplexandnon-linearproblemwhichtraditionalsearchalgorithmcan’tdealwithwell.Thevariousparameterofgeneticalgorithmallaffectthefinalresult,andtheparameterssuchascolonysize,hereditygenerationsetccontrolthecomputingtime.Thechoiceofalgorithm’sparameterisstilllackofpowerfultheoreticproof,sowemustensuretherationalityofparametersviamuchexperiment.InThispaperweamelioratethebasicgeneticalgorithm.FirstlyweuseanewChromosomecodingtoreducethelengthofpathcoding，todebasethedegreeofcomplication.Secondlyweapplyreformativeselectarithmeticoperators.Ininitialstageitminishthediversityoftheindividual’sfitnessdegreetoavoid“prematurity”,andinendstageitincreasethediversityoftheindividual’sfitnessdegreetoconvergencerapidly,toimprovethealgorithm’sefficiency.Experimentationsvalidatethevalidityofthealgorithm,whichreducethecuttingblanklineaveragely15%.Inconclusion,greedyalgorithmandgeneticalgorithmhaveshownsomepotentialtodealwithcuttingpathoptimizationproblem,andgainpreferableresult.Buttheyallcan’tsolingtheproblemtothenines。Actuallyweshouldadoptappropriatealgorithmintermofdifferentrequestanddifferentinstance.Atlast,weexpectthefutureofthisresearch.Keywords:cuttingpathoptimization,NCplasmacuttingmachine,TSP,greedyalgorithm,geneticalgorithm上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本授权书。本学位论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日上海交通大学工程硕士学位论文第一章引言第1页第一章引言1.1我国船舶行业背景在当今世界，随着经济全球化，世界各国之间的贸易往来更加频繁，商品运输需求量也随之急剧增加。据统计世界各国贸易货物运输量的2/3由商船承运。在大洲之间、国家之间的货物运输方式上，船舶运输有着不可替代的优势[1]。目前，我国对外贸易货运量的90%由远洋船队承担，运输商品需要散货船、油船、集装箱船、化学品船、天然气船等各种远洋船舶。此外，运送旅客需要客船、保卫海疆需要军舰、开发利用海洋和江河需要调查船、工作船、渔船……。这些都表明船舶工业在我国的重要基础地位[1]。近20年来，中国船舶工业成功地实现了由军转民的战略大调整，造船生产获得较大发展，从1982年占世界造船产量的份额的0．8％，提高到2006年占世界造船产量的份额的的19%，连续12年成为仅次于日本、韩国之后的世界第3造船大国。至2007年6月底，新接船舶订单4262万载重吨，同比增165%，占世界市场份额42%，手持船舶订单1.054亿载重吨，占世界市场份额28%。目前，已有三家造船企业手持船舶订单入围世界造船企业前10强。另外，还有上海江南长兴造船基地、广州龙穴造船基地、青岛海西湾造修船基地等正在建设的大型造船基地已陆续开工。目前国