【硕士论文】混合遗传算法在服装自动排版中的应用研究.pdf

《【硕士论文】混合遗传算法在服装自动排版中的应用研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、‘Y767271分类号：UDC密级：编号：0313502078◇幽隳跨硕士学位论文混合遗传算法在服装自动排版中的应用研究学位申请人：一导师姓名及职称专业名称张含辉王若梅副教授计算机软件与理论：00五年五月二日混合遗传算法在服装自动捧版中的应用研究摘要服装样片的自动排版问题，在经过对待排版的衣片轮廓进行预处理后，转化为二维不规则多边形的自动最优布局问题，该问题属于NP完全的组合优化难题，具有真实和广泛的应用背景。到目前为止在这～问题上取得较好求解效果的方法是启发式搜索方法，但是该方法本质上属于局部寻

2、优，不能得到满意的近似最优解。而遗传算法是一类借鉴生物自然选择和自然遗传机制的随机搜索方法，从一个点群开始寻优，而不是从一个初始点开始寻优。理论上已经证明“3遗传算法能以随机的方式寻求到问题的最优解。标准遗传算法求解该问题时，算法的搜索空间随着多边形个数的增加而呈指数增加，而且在执行过程中常常产生大量不可行解，需花费很多无谓的时间去处理它们而造成收敛速度慢，效率低。另外，标准遗传算法具有通用性，求解方法往往不是解决特定问题的最有效的方法，它比专门针对该问题的知识型启发算法的求解效率要差，虽然这种知

3、识型启发算法保证不了一定能够找到问题的最优解。因此，在将遗传算法应用于自动排版的已有研究中，通常算法的效率低，实用性差。本文针对启发式算法和标准遗传算法在求解该问题时各自的缺陷，结合二者的优点，将从实际排版经验得到的启发式信息引入标准遗传算法，建立了～种启发式混合遗传算法，将问题的解空间压缩至某个包含高性能解的子空间上，再进行遗传搜索。算法首先在结合实际服装CAD排版的特点和目前国内外研究工作的基础上，提出一种合理恰当的编码方案，然后将启发式信息应用到初始群体的生成中，缩小了问题的解空间，避免了对

4、大量无谓解的搜索。另外，在综合前人用启发式搜索方法对该问题所做研究而取得最优算法的基础上，本文给出了详细的解码过程，并根据问题的特性设计了遗传算法中的三个重要算子。关键词：自动排版，服装CAD，启发式搜索，遗传算法混合遗传算法在服装自动捧版中的应用研究Theauto-markerproblemofapparelpiecescanbeconvertedtotheauto-markerproblemofthetwo-dimensionalrandompolygonal，whichisaNP-compl

5、etehardproblemandwidelyexistsinmanypracticalindustries．Theclassicalwayofsolvingsuchproblemistheheuristicsearchingmethod．Butit'shardforthismethodtofindasatisfyingoptimalsolution．Geneticalgorithm(GA)isakindofrandomsearchingmethodbasedontheideaofthenatur

6、alevolutionandinheritancemechanism，whichstartssearchingforanoptimalsolutionfbmagenerationinsteadofanindividual．IthasbeenprovedthatGAisabletofindtheoptimalsolutioninarandomway⋯．However，whenthestandardGA(SOA)isusedinsolvingsuchproblem，thesearchingspacei

7、ncreasesgreatlywiththeincreasingofthepolygonnumber,andtherearcagreatdealofinfeasiblesolutionsthattakemuchtimet0bedealtwithsothattherunningspeedissloweddown．Furthermore，SGAisaquitegeneraloneandisnotthebestwaydirectedtothegivenproblemforlackingofrelated

8、heuristicinformation，soit’susuallylessefficientthantheheuristicsearchingmethod，thoughitwouldn’tnecessarilygettheoptimalsolution．ThisthesiscombinestheadvantagesoftheheuristicsearchingalgorithmandGAbyimportingtheheuristicinformationformedfmmthep