并行遗传算法在装箱问题中的应用研究

《并行遗传算法在装箱问题中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行遗传算法在装箱问题中的应用研究山东大学硕士学位论文并行遗传算法在装箱问题中的应用研究姓名：王海龙申请学位级别：硕士专业：计算机软件与理论指导教师：邱洪泽20080405山东大学硕士学位论文摘要装箱问题是最经典的组合优化问题之一，同时也是算法分析理论中研究的重点。装箱问题源于现实生活，有着极为广泛和深厚的应用背景。例如装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等各领域有着广泛的应用。而且装箱问题理论的形成也有着深刻的意义，作为一种最早研究的NP难解问题，为其它NP难解问题的研究提供了理论性研究平台和诸多借鉴的典范。该问题已经有四十多年的研究历史，在此期间

2、，许多著名的组合优化方面的学者为装箱问题创建了比较完善的理论和丰富的算法，但是关于装箱问题及其算法的研究仍远未结束。本文利用并行遗传算法来求解一维装箱问题，针对一维装箱问题，围绕如何提高并行算法的效率以及求解的精度提出了一些关键性的技术。主要内容如下：1、本文比较了解决一维装箱问题较好的组遗传算法，针对组遗传算法交叉算子的不足，在叉的过程中增加了一种“替换”机制，从而提出了一种改进的交叉算子。此交叉算子能够保证染色体在交叉的过程中尽量的减少箱子的个数，同时尽可能使能箱子装满物品。2、为了提高种群的多样性，在进化的过程中跳出局部最优解，本文设计了新的变异算子，在变异的过程中主要

3、采取增加一个箱子，减少一个箱子，箱子数不变但箱子所装物品进行恰当重组的操作。3、从“多群体粗粒度"并性遗传算法模型入手，受“金字塔"模型的启发，本文提出了一种并行遗传算法的“金字塔层次模型’’，根据种群的平均适应度将各个种群分成不同的层次，每一层具有不同交叉和变异概率。层次较高的种群具有较低的交叉和变异概率，迁移时只是从低层次向高层次迁移。4、在迁移策略上，为了尽可能降低通信费用，本文提出了“双阈值”的迁移策略，根据相邻两层之间种群的适应度方差设置双阈值，将迁移分为三种情况：小于最小闽值时不迁移；介于两个阂值之间用下层的优秀个体去替换上层的较差个体；大于最大的阈值，进行层次调

4、整。5、在迁移周期上，本文采用的不固定间隔的迁移周期，当进化缓慢时才进行迁移的申请。山东大学硕士学位论文基于上述的研究，最后本文给出了实现并行遗传算法求解装箱问题的伪代码，并在实践中利用伪并行遗传算法来模拟并行遗传算法求解一维装箱问题，通过实际数据的运算精度和效率说明了这种算法的优越性。关键词装箱问题；并行遗传算法；金字塔层次模型；双阈值迁移；II山东大学硕十学位论文ABSTRACTBinPackingproblemBPPisoneofthemostfamouscombinatorialoptimizationproblem．Anditisthemphasisoftheana

5、lysisofapproximationalgorithms．AsoneofmeearlieststudiedNP?hardproblem,itworks髂aresearchplatformforthecomplexitytheoryandgivesdirectorsotherNP．Hardproblems．Binpackingcomesfromurlivesandhasmanyimportantapplicationssuch罄multiprocessorscheduling，resol／rceallocation，andreal。worldplanning，packing

6、andschedulingoptimizationproblems．theproblemshabeenstudiedmorethanfortyyears，manyfmouscombinatorialoptmizationresearchershavebuiltupintegratetheoriesandexploredmanyalgorithmsfortheproblem,but廿1etopicsarfarfromending．ByusingtheparallelgneticalgorithmtOsolvetheone．dimensionalbinpackingproblem

7、,fortheone?dimensionalpackingproblem，centeringonhowtOmprovetheefficiencyoftheparallelalgorithmsandthedatacomputingprecision，thepaperputsforwordanumberofkeytechnologies．Thefollowingkyelements：1．Bycomparingwththegroupinggeneticalgorithmacievingbetterresult