求解矩形排样问题的离散粒子群算法

《求解矩形排样问题的离散粒子群算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、合肥工业大学硕士学位论文求解矩形排样问题的离散粒子群算法姓名：陈钊申请学位级别：硕士专业：信息管理与信息系统指导教师：刘心报20090401求解矩形排样问题的离散粒子群算法摘要矩形优化排样问题作为优化下料问题的一个分支，通常是指在给定矩形板材上排放所需的矩形件，要求板材的材料利用率最大化。该问题属于典型的组合优化问题并且被证明是NP完备问题。本文针对矩形排样问题，通过规定的排样规则(剩余矩形排样法)将问题转化为组合优化问题。考虑到矩形排样问题的解空间是离散不连续的，提出了一种适用于改问题的离散粒子群优化算法。首先根据组合优化问题及离散

2、量的特点，对粒子群算法中粒子的位置、速度及其运算规则进行了重新定义和修改，利用剩余矩形排样法进行解码计算材料利用率并做为适应度函数值，进行迭代搜索找出最优解从而解决问题。通过与其他典型算法进行了仿真比较，结果表明，在最优解搜索上具有很好的性能。关键字：矩形优化排样，组合优化，剩余矩形排样法，离散粒子群算法SolvingtherectanglepackingproblemofthediscreteparticleswarmalgorithmAbstractRectanglepackingproblemisakindofcuttingpr

3、oblem，usuallyconsistsofpackinggwenrectanglepmcesintoalargerectanglestockplate，witharequirementofmaximumusageofthestockplate．ItisatypicalcombinationoptimizationandhasbeenprovedtobeaNP-completeproblem．Inthisthesis，rectanglepackingproblemwillbeconvertedintocombinatorialopt

4、imizationproblemthroughthenestinglayoutrules(rectanglefillalgorithm)．BecauseofthesolutionspaceoftherectanglepackingproblemiSdiscretenotcontinuous．adiscreteparticleswarmoptimizationalgorithmwasbeenpresented．Firstofall，accordingtothecharacteristicsofdiscretecombinatorialo

5、ptimizationproblem，theparticle’Sposition．velocityandcomputingruleswereredefinedandmodified．ThenusingtherectanglefillalgorithmtodecodeandcalculatetheutilizationofmaterialsasthefitnessfunctionofDPSO。htheend，theoptimalsolutionoftheproblemwillbefoundbyiterativesearch．Throug

6、hthecomparingwiththeothertypicalalgorithms．theresultsofthisDPS0algorithmshowabetterperformanceinthesearch．Keyword：rectanglepacking，combinatorialoptimization，rectanglefillalgorithm，DPSO插图目录图2-1矩形排样问题的坐标系⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．7图2-2文献[31]BL算法排样示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．10图2-3文献[32]BLF算法排样示意图⋯⋯

7、⋯⋯⋯⋯⋯⋯⋯⋯10图2-4文献[19]下台阶算法排样示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯．11图2-5文献[33]最低水平线算法排样示意图⋯⋯⋯⋯⋯⋯⋯⋯12图2-6文献[24]剩余矩形表示法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．12图2-7剩余矩形排样法切割示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．13图3-1粒子群算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．17图4-1剩余矩形排样法排样过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．27图4-2离散粒子群算法求解矩形排样问题流程图⋯⋯⋯⋯⋯⋯．．29图4—3实例一⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．29图4-4实例二⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

8、⋯⋯⋯⋯．．29图4-5实例三⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．30图4-6实例四⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．31图4-7实例五⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．31图4-8实例六⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯