三维装箱问题的模型与改进遗传算法
关于三维装箱算法问题, 一些算法理论, 感觉对这方面的应用有一定帮助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
模拟AM与FM调制解调系统
实验 1 ：模拟AM调制解调系统幅度调制解调技术是一种最简单的模拟调制方法，而且通过幅度调制容易理解调制的概念。本实验通过 LabVIEW 编程产生信号频率、幅度等参数可变的基带信号和载波信号，实现 AM 调制和解调，观察参数变化对已调信号的影响。并通过仿真运行整个 AM 调制解调系统，学习掌握代码调试方法，验证程序的正确性。实验 2 ：模拟FM调制解调系统利用 LABVIEW 仿真，产生基带信号频率、载波频率及频偏等参数可变的 FM 调制解调系统，观察参数变化对被调制信号以及其 FFT 功率谱的影响。并通过仿真运行整个 FM 调制解调系统，学习掌握代码调试方法，验证程序代码的正确性。通信原狸与系统实验报告【程序设计】1、总体程序实验1:模拟AM调制解调系统AM信亏波形翌(时)波信号上边带下边带正弦波形(时域)载波幅值制信号湖形图(时域)调制值颗谱测量AM洞制信号波形因(罚信号「·(峰值100000实验2:模拟FM调制解调系统载波率f(Hz)仿真信号3网回區最大偏移量f(Hz仿真信号2信号基带率和b(HzPower SpectruA圆周信号域仿真信号FM调制信号弦10000001000000导数dxdt)Simulate正弦通信原理与系统实验报告2、部分函数图音分函数图Hilbert变换函数部至复数转换复数至极坐标转换交流和直流分量估计归一化波形【实验内容】实验1:模拟AM调制解调系统1、按(P2713)的实验步骤1完成AM调制2、按(P2)的AM解调原理的提示完成AM解调根据实验教程,仿真信号快速ⅥI与频谱测量快速Ⅵ发其最终对话框选项设置如下:信号关型O幅(均方慢)加后的辅轴入信号5.583643幅度(峰直盐r变谱功增密赏占空比5.5050450D2040.60B口加难声声型099999阳果览种子值验时识相对于更开时间吧对(日期与时于均数日100000仍真平集时轴更信号采枉盈重置相位,种子和时标识乐月连续生成生递每次环口整数需吗数信号名称实玩无样数10o信号名称取商在前面板中设置参数如卜:载波幅值调制幅值11.:1戴冷200m1……4006008001000020406080100120140160180200调制频率0250500750100012501500175020000204060801001201401601802004通信原理与系统实验报告设置好参数后,运行程序,结果如图所示载波信号波形(时域)弦M4M制信号波形(时域正弦20020015050-15020020000.020.040.060.080.100.020.040.060.080.1时间时间AM调制信号形图(数城)开F:(值)四4M解号形(时城)5002050150200-15010020030040050000.020.040.060.080.1频率时间分析:观察“AM调制信号波形图(时域)”图可知:经过AM调制将调制信号加载到载波信号上后,形成的包络恰好与基带信号一致。观察“ΔM调制信号波形图(频域)”图可知:最左边的频谱为基带信号的频谱,而右边的三个频谱从左到右依次为下边带fc-fb,载波fe,上边带fc+fb的频谱。观察“AM解调信号波形图(时域)”图可知:解调后的信号与基带信号基本重合,说明运用包络检波法解调信号成功。改变实验参数增大基带信号的幅度,其他参数不变分析:如下图所示,前两幅图分別为增大基带信号幅度前的调制信号的时域图和频域图,后面两幅图为增大基带信号幅度后的调制信号的吋域图和频域图。通过观察图像可发现:增大基带信号樞度,其他参数不变的情况下:调制信号在时域上的幅度随基带信号幅度的增大而増大,而频域上不发生变化。5通信原狸与系统实验报告AM调制信号波形图(时域)AM调制信号波形(频域)应(F·(值)3005020050100200150300200-00.020.040.060.080.1100200300400500时间AM调周制信号波形图(时城)AM调制信号波形图(频域)正弦(FT·(峰值)50200100-1001002003000.020.040.060.080.10100200300400500时间频率增大基带信号的频率,其他参数不变分析:如下图所示,前两幅图分别为增大基带信号频率前旳调訇信号的时域图和频域图,后面两幅图为增大基带信号频率后的调制信号的时域图和频域图。通过观察图像可发现:增大基带信号频率,其他参数不变的情况下:调制信号在时域上的频率随基带信号频率的增大而增大,而频域上也发生了右移。AM调制信号波形图(时域MAM调制信号波形图(城)F·(峰值))M5020010050100200150-30020000.020.040.060.080.10100200300400500时间频率通信原理与系统实验报告AM调制信号波形图(时域)AM调制信号波形图(颈域)正弦·(峰值)50-200100500100-10020030020000.020.040.060.080.10100200300400500时间增大载波信号的幅度,其他参数不变分析:如下图所示,前两幅图分别为增大载波幅度前的调制信号的时域图和频域图,后面两幅图为增大载波幅度后的调制信号的时域图和频域图。通过观察图像可发现:增大载波幅度,其他参数不变的情况下:调制信号在时域上的幅度随载波信号幅度的增大而增大,而频域上不发生变化。AM调制信号波形图(时域)正弦AM调制信号波形圈(频域)H·(峰值)30050200010-500-100-200-150300-20000.020.040.060.080.10100200300400500时间频率AM调制信号波形图(时域)正弦AM制号形(炫)芷奸:()人503000200100细10020015030040020000.020.040.060.080.110200时间频率通信原狸与系统实验报告增大载波信号的频率,其他参数不变分析:如下图所示,前两幅图分别为增大载波频率前的调制信号的时域图和频域图,后面两幅图为增大载波频率后的调制信号的时域图和频域图。通过观察图像可发现:增大载波频率,其他参数不变的情况下:调制信号频率在时域上的频率随载波信号频率的增大而增大,而频域上也发生了右移。AM调制信号波形图(时城正弦AM调制信号波形图(颁域)正弦任FT·(峰值)3002000100200-300-20000.020.040.060.080.10100200300400500时间频率AM调制信号波形图(时域)正凶M制儒号形图(域):(峰)300502001000-100-20030020000.020.040.060.080.10100200300400500时间实验2:模拟FM调制解调系统、按(322.3)实验内容完成FM的调制2、按(3223)的实验内容元成FM的解调根据实验教程,仿真信号快速Ⅵ与频谱测量快速ⅥI及其最终对话框选项设置如下通信原理与系统实验报告配雪仿真信号[真台号3]生造量结果预范所选到早3、02691幅度(蜂值位(D功幸造C线性O功率造移量占空比O092Hanning君果候嚣均方根对测经开始间保待O姆对(日期与时词)半均数目C仿真菜对钟申仨号·以可达到最速度运行里相位种了和时标日相位軍预100日)来用端牛应信号名称O当平均时用信号类型名偏学会称□开相位150200250300350400450500阳确定联群取篇□帮数在前面板中设置参数如下:基带频率fb(Hz)载波频率fe(Hz)20000400006000080000100000110000033000005000007000009000001E+6最大偏移量t(Hz)20000400006000080000100000120000140000160000180000205410设置好参数后,运行程序,结果如图所示基带信号(时域正弦A载反信号(时域)正弦0.5000.5-0.505E-50.00010000150.00025E-50.00010.000150.0002时间时间时城须域FM调制信号(时域正弦0.50.52E-6E-58E-50.00010.000120.000140.000160.000180.0002时司通信原理与系统实验报告时域频域FM调制信号(域)正弦(功率-1002000500000150000025000003500000450000055000006500000750000085000001E+7频率FM解调信号(时域)正弦2E-56E-58E-50.00010.000120000140.000160.000180.0002时间分析:观察“FM调制信号(时域)”图与“FM调制信号(频域)”图可知:经过FM调制后产生的波形与原理相符合;观察“AM解调信号波形图(时域)”图可知:解调后的信号与基带信号基本重合,说明运用非相关包络检波法解调信号成功。改变实验参数≯增大基带信号的频率,其他参数不变分析:如下图所示,前两幅图分别为增大基带信号频率前的调制信号的时域图和频域图,后面两幅图为增大基带信号频率后的调制信号的时域图和频域图。通过观察图像可发现:增大基带信号频率,其他参数不变的情况下:调制信号在时域上的频率随基带信号的频率的增大而增大。
- 2021-05-06下载
- 积分：1
|
联系客服（QQ：3324461878）
