三维装箱问题的模型与改进遗传算法
关于三维装箱算法问题, 一些算法理论, 感觉对这方面的应用有一定帮助144效学的实践与认识40着∑(B,*v)≤VB,B,PD,PWy=0或者1v∈{1,2,…,D},y∈{1,2,…,W},z∈{1,2,…,H},j∈{1,2,…,n}(12目标函数是箱子未装填物品的空间最少(亦即空间浪费最少)条件(2)确保子的1个装填空间单元被装填不超过1次即保证物品间不会互相嵌入;(3)式说明上层物品会有支撑,不会悬空(4),(5),(6)式说明物品装箱位置约束;(7),(8},(9)说明物品的摆放问;(11)是箱子的容积约束2這传算法21遗俊法遗传算法(GAs)是建立在达尔文进化论基础上的搜索算法,它从代表问题潜在解的个种群( population)开始,而一个种群则由经过基因(gene)编码 coding)的一定数目的个体individual)组成遗传算法采用了自然进化模型,如选择,交叉变异等计算开始时,一定数目S个个体(父个体1、父个体2……)即种群随机地初始化,并计算每个个体的适应度函数第一代也即初始代产生如果不满足优化准则,开始产生新一代的计算为了产生新一代按照适应度选择个体,父代通过基因重组(交叉)而产生子代所有的子代按一定的概率变异然后重新计算子代的适应度,将子代插入到种群中取代父代构成新的一代循环执行这一过程,直到满足优化准则22算法设计2.21编码方法采用矩阵编码方法,用多维数组(二维矩阵表示染色体结构,数组元素表示染色体基因,编码清晰,易于理解,遗传算子操作方便染色体S=(L,P,Px,Py,T)来表示问题的一个解其中:向量L=(Li,L1,…,Ln)为待装箱物品的一个排列;向量P=(Bn,B1,…,B3n)为对应于排列L的B,一个排列向量Px=(PB,PB,…,PB)为对应于排列L的PB一个排列向量Py=(PB,PB},…,PB为对应于排列L的PBx一个排列矩阵T=(x2=欢面为对应于排列L的装箱物品坐标22适值函数问题的目标是最小化箱子的浪费空间,适应度函数可定义为空间利用率函数(S代表染色体C1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net2期陈德良,等:三维装箱问题的模型与改进遗传算法Fitness(s)(∑B3*v/若∑(B;*v)≤V否则23解的不可行性,罚函数与评估函数由于对染色体作遗传运算时可能获得不可行的子代,惩罚技术是用遗传算法解约束优化问题中最常用的技术,本质上它是通过惩罚不可行解将约束优化问题转化为无约爽问题就本文讨论的问题而言,惩罚项包括:1)物品在装箱时不交叠,即满足约束条件{2},有着∑By≤1g:(S)1,否则2)物品装箱时不能出现悬空即满足约束条件(3),有0若∑B-B+)>0g2(S)=(151,否则3)物品装箱不能超出箱子边界,即满足约束条件(4,(5)和(6),有0若吃+B(Pp++Pwy*吗)≤D1,否则0若+B*(PD*+PWy*m)≤W941,否则(17)95(S)=0,若x+B*h;≤H8)1,否则eat(s=∑9(S)b=1那么,式(14)至(18)任何一个取值为1,都是不可行评估函数eval(S)=Fitness(S)*(5-Genalty (S)24算法步骤)初始化进化代数计数器,随机产生一定数目(大于设定的初始种群规模)的染色体;2)利用式(14)检验初始种群染色体可行性,对不可行解旋转赌轮接受小部分不可行解,与可行解构成初始种群3)对初始种群染色体进行遗传运算;①按照式(14)至(20)计算评估函数:⑩按顺序交叉方法产生子代;④变异算子;4)旋转赌轮选择染色体;)重复3至4)直到完成给定的循环次数;C1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net数学的实践与认识40卷6)确定最好的染色体作为最优解3实验结果我们用C++编程实现了上述算法在配置为CPU24GH/512 Mb ram的微机上,用随机产生的数据进行实验取遗传算法运行参数为:{群体大小进化代数,交叉概率,变异概率}-{100,50,0.85,0.05}用随机产生的数据进行实验,求解20个种类100件物品的装箱问题,得到最好解耗时小于1秒;计算50个种类200件物品的装箱问题,得到最好解耗时小于2秒以下是3类共16件物品的装箱问题.实验数据图2,第!行为箱子尺『;第2至第4行为待装箱物品,每行第1个数据表小序号第2至镌4数据分别为物品尺寸,第5个数据表示物品件数在计算转桌中包含数据依次是:序号,是否装载,物品长,物品宽,物品高,纵向坐标横向坐标,垂向坐标纵向长度,横向长度,垂向长度(图4).从图4可知第12号物品未能装箱,物品装箱的顺序可以从“序号列中得出.绘制的物品装箱示意图见图31421,2,乙2,2,图2实验数据图3装箱示意图文件((格式(Q帮助新 s REPORT耗时:.1 most g sec次数:01615积:7580001016每a0库:92.875989名寸:=280;y=1210;2=300NO: P st Din 1 Din 2 in 3 C xC YPu y Pu 2202002002002001002812B20020012010010020012鲁2020012010020020020020012B100100212021201215024015824815015561111111111115152每000ao00015150240202020055020200201002001215502D0200120100100201205s012020028012015024075000015024815015024075015015024a152002009o002002001002012090020012日未装相物品121501502年图1计算结果o1994-2010ChinaAcademicJournalElectronicPublishingHousealLrightsreservedhttp://www.cnki.net2期陈德良,等:三维装箱问题的模型与改进遗传算法1474结束语装箱问题是一常见而难解的优化问题,利用遗传算法求解时,随机产生的初始解会出现大量的不可行解(装箱物品占用空间出现大量交叠),本文将箱子内部空间划分为一个个立方体单元:算法的第2)步对标准遗传算法做了修改通过剔除大量不可行解提高算法的收敛速度,实验结果表明此算法运算过程及绪果稳定,具有较强的实际应用价值能有效解决复杂的三维装箱何题,今后将继续研究将该方法运用到其它不同的有关装箱问题或组合优化问题中参考文献[1] John J, et al. An improved algctithra for the ncn-guillctine-constraincd cutting-stock problem(JIOperational Resee ch Society, 19 /0,+1: 141-149[2] Coffmau E. G, et al. ver age-case analysis of cutting and packing in two dimensions [J]. Euro. Jof Operatic al Reseaich, 1990, 44: 134-14413) Fabien C, et al. A Two-phase heuristic for the two-dinensional cutting-stock problem [J. Opera-tional Research Society, 1991, 42: 39-744 Martello Silvano, Pisinger, David, and Vigo, Daniele. The Three-Dimensional Bin Packing ProblemJ. Operations Research, 2000 Informs. Vol. 48: 256-267]何大勇,査建中,姜义东遗传算法求解复杂集装箱装载问题方法研究向]软件学报,201,12(9):13801385阿]张德富魏丽军陈青山陈火旺等.三维装箱问题的组合启发式算法软件学报,2007,18(9):20832089A Mixed Integer Programming Model ofThree-Dimensional Bin-Packing Problem and ImprovedGenetic AlgorithmsCHEN De-liang, 2, CHEN Zhi-yaSchool of Traffc &z transportation Engineering, Central South University, Changsha 41076, China)(2. Logistics School, Central South University of Forestry Technology, Changsha 410004, ChinaAbstracts The three-dimensional bin-packing problem is complicated but a high level ofinterest in developing effective way to solve this kinds of NP-hard problem. First a MixedInteger Programming model was worked out in this paper, which resorted to dividing box spaceinto unit cube. Then an improved genetic algorithm was mainly developed. Tests on hundredsof problems show that this algorithm makes the most of volume utilization in minimal timeKeywords: three-dimensional bin-packing problem; space division; mixed integer program-ming model; improved genetic algorithmso01994-2010ChinaAcademicJournalElectronicPublishinghOuse.Allrightsreservedhttp://www.cnki.net
- 2020-12-05下载
- 积分:1
FLUENT经典算例合集7个
案例分析的电子书《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)目录前言..2目录FLUENT经典算例翻译之一算例1介绍如何使用 Fluent算例4非定常可压缩流动模型.52算例5辐射与自然对流模拟·:······99FLUENT经典算例翻译之二算例13使用非预混燃烧模型151算例15蒸发性液体喷雾建模.∴214算例18使用混合物多相模型和欧拉多相模型..∴252算例21使用欧拉多相粒子传热模型垂··D垂垂垂。看垂垂垂看D看垂·D4。垂278ww.myCFDcn《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)算例1介绍如何使用 Fluent引言此向导通过图例说明了一个发生在混合弯管处的两维湍流流动和传热问题的求解方法和过程。这种混合弯管的结构常见于发电厂和化工厂的管道系统中。正确计算出弯管内流体交汇处附近的流场和温度场分布,对于设计合适的入口管道位置具有重要意义通过此向导,用户可学会以下内容●在 Fluent中输入网格文件使用混合单位制去定义儿何体和流体的属性设置强制对流的湍流流动的流体物性和边界条件迭代计算并使用残差监视器监测计算过程及其收敛性●使用隔离求解器进行求解使用等势图检察流场和温度场●运用二阶离散化方法重新计算以获得更佳的温度分布对网格进行温度梯度自适应,进一步求解更佳的温度场分布前提条件在学习此向导之前,假设用户还没有使用 Fluent的给验,不过,已经学习过用户指南第一章中的简单算例,并且熟悉 Fluent的界面及其指南中的规约可题描述问题如图1-1所小。一股温度为26℃的冷流体流入大管道,在弯管处与另股温度为40℃热流体混合。管道的长度单位为英寸,而流体的属性和边界条件则使用国际单位。入口管道的雷诺数为2.03×105,因此,选择湍流流动模型。4ww.myCFDcn《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)P =100 kg/viscosity8x14FConductivity: k=0.537 Y4 miK2SpC Ic Heat 9=4216 Jkg-k6酽.2mT1121m图图1-1问题说明准备工作1.从 Fluent的文件光盘中拷贝文件 elbow/ elbow, msh到电脑的 Fluent作日录中对于Unⅸx系统,当把文件光盘放入电脑光驱后,可以在以下目录找到这个文件:/ edrom/uent61/help/ tuttles述 cdrom为电脑的光驱目录对于 windows系统,当把文件光盘放入电脑光驱后,可以在以下冂录找到个文件cdrom: fluent 6.1 help tutfiles上述 cdrom为电脑的光驱目录2.启动 Fluent,选择2D求解器。ww.myCFDcn《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)第1步:与网格相关的操作读取网格文件 elbow, mshFilc→Read+}CascSelect fileFiterh,于d,SH,GRdirectoriesFileshome user tutorial/elbow. msh/home userautorialaCase Filehome /user/tutorialoKFiterCancela)在 Files项中点击选中 elbow. msh,然后点击OK完成操作。注意当 Fluent读取网格文件的同时,信息会不断显示在反馈窗口内,报告网格转化的过程。当读取网格文件完毕, Fluent的反馈窗凵会显示共读取了918个三角形的流体单元,以及许多带着不同分区标识符的边界面。2.网格检查。Grid→} Check6ww.myCFDcn《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)F1uent的信息反馈窗口会显示如下信息:Grid checkDomain extentscoordinate:min(m)=0.0000009+00,max(m)=6.400001e+01y- coordinate:min(m)=-4.538534e+00,max(m)=6.400000e+01Volume slatisticsminimum volume (m3): 2.782193c-01maximum volume (m3):3.926232e+00total volume (m3):1.682930e+03Face area statisticsminimum face area (m2):8.015718e-01maximum face area(m2):4. 118252e+00Checking number of nodes per cellChecking number of faces per cellChecking thread pointers.Checking number of cells per faceChecking face cellsChecking bridge facesChecking right-handed cellsChecking face handednessChecking element type consistencyChecking boundary typesChecking face pairs.Checking periodic boundaries.Checking node countChecking nosolve cell countChecking nosolve face countChecking face childrenChecking cell childrenChecking storageww.myCFDcn《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)Done注意网格检查结東后,信息反馈窗∏会以默认的SI单位制给出网格在ⅹ轴和Y轴上的最大和最小值,并将报告出网格的賦它特性。网格检查还会报告出有关网格的任何错误。需要特别注意的是,确保最小体积不能是负值,否则 Fluent无法进行计算。在SI单位制中,默认单位是m,若想改变单位制,使用 in ches:可以打开 Scale grid对话框。3.平滑(或者交换)网格Grid→} Smooth/swap…Smooth/Swap GridsmoothSwap InfoMethodNumber SwappedskewnessMinimum skewnesscumber visitedNumher of lerationsSmoothCloseFluent读取网格文件后,平滑三角形或四边形网格是一个良好的习惯,那样能确保使用质量铰好的网格进行计算。a)点击按钮 Smooth,再点击按钮Swap,重复上述操作,直到 Fluent报告没有需要交换的面为止。若 Fluent再无法通过交换改善网格质量,则没有平面可被交换了。b)点击 Close关闭对话框。ww.myCFDcn《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)4.更改网格的长度单位Grid→ scalea)在 Units conversion(单位转换)项的 Grid was created ln(网格长度单位)的右侧下拉列表中选择In(代表选择了英寸b)点击 Scale按钮,更改长度单位。在 Domain extents栏中采用了默认的SI单位制,长度单位为mc)点击按钮 Change length Units,设定 inches(英寸)为此次计算采用的长度单位确保Xmax(in)和Ymax(in)中数值为64英尺。(如图1.1)Scale gridScale factorsUnit a conversion00254rid Was Created In inY0+0254Change Length UnitsDomain extentsXmax [in]E4400001Ymin (in534Ymax(in) 64scaleUnscaleCloseHeld)计算采川的长度单位已被吏改为 inches(英寸),此时便能正确反映网格的几何尺寸注意此算例的求解过程中,除了长度外,其它单位均采用SI制。一般来说,没有必要对其它单位进行改动。按照上述的操作,长度单位已被确定为 inches若用户想采用别的单位制作为长度单位,如mm,可以在 Define的下拉菜单中打开 Set units对话框,进行更改。ww.myCFDcn《数值计算与工程仿真》专刊一 FLUENT HELP算例精选中文版(→)5.显示网格。(图1.2)Display→Grid,,Grid DisplOptionsEdge TypeSurfaces三彐p Mores今Atermal-3pressure-outlet-7H Edgesv feature velocity-inlet-5p facesy outlineuelocily-inlet-rall-4Partitionswall-iiShrink factor到终安Surface Types且彐Surface eame patternclip-surfHatchfanOutline InteriorDIsplayColorsCloseHelpa)确保在 surfaces项屮的所有表面都被选屮,然后点击 Display。ww.myCFDcn
- 2020-11-30下载
- 积分:1