资源描述：
《三维装箱问题的遗传算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2010年6月电脑学习第3期三维装箱问题的遗传算法研究***周昕纪颖摘要：本文以集装箱自动装载系统为例，根据货物放置方向、装载容积等约束条件，给出了有效的解码算法，提出了一种改进遗传算法，并通过实例数据进行了实验结果分析。关键词：三维装箱遗传算法优化中图分类号：TP301．6文献标识码：A文章编号：1002－2422（2010）03－0117－03ResearchonGeneticAlgorithmforThreeDimensionalContainer－PackingProblemZhouXinJiYingAbstract:Basedonautomati
2、ccontainer－packingsystem,thepapertakesintoaccountthedirectionofthegoods,loadingcapa－cityandotherconstraints,anditcontributesaneffectivedecodingalgorithmwithimprovedgeneticalgorithm,thereforeanalyzestheresultbasedonexperimentaldata．Keyword:Three－dimensionalContainer－PackingGeneticA
3、lgorithmOptimization1装箱问题的数学模型（3）货物装载容积的约束:货物装载的总容积不得大集装箱三维装载优化问题可描述为:在一定约束条件于集装箱的最大装载容积。限制下,将一批货物按照适当的装载方法装入同一集装箱（4）稳定性的约束:货物装载应该使重心位于允许的中,使得集装箱的容积利用率或装载质量利用率最大,从范围内而确保整体稳定,以利于运输安全。而增强对集装箱的合理有效使用。为方便建模，约定如下：（5）承载能力的约束:在装载中,货物所能承受的最大货物简化为长方体,高度相等且均小于集装箱尺寸；货物压力受限制。以水平方向放置于集装箱中任位置而不
4、受配置位置限制。（6）货物装载顺序:不同的货物在装载中应按不同的1．1目标函数及约束条件优先顺序装载。1．1．1目标函数描述1．2货物装载遵循的方向次序原则装箱的目标可描述为如下的最大化函数[6]：定义集装箱箱门所在端为后端，集装箱在坐标系中的nn位置关系如图1所示。则在集装箱中装载货物遵循以下原Maxz＝λΣ（liwihi）／V＋（1－λ）Σ（giδi）／G（1）则:i＝1i＝1其中li、wi、hi、gi分别表示货物i（i＝1,2,芽,n）（1）依次沿左侧至右侧方向（即y轴方向）、前端至后的长、宽、高和质量；V，G分别表示集装箱的最大装载容积端方向（即x
5、轴方向）放置每一层。和最大装载质量。λ是0－1变量，当追求目标为容积利用（2）沿下端至上端方向（即z轴方向）逐层放置。率最大时λ＝1，当追求目标为装载质量利用率最大时λ＝z上端前端0；δi是0－1变量,若货物i装载则δi＝1,否则δi＝0。H右端本文旨在确定一种集装箱装载方案，以便将所有货物o装入集装箱中；如果不能完全装入，则找到一个待装子集，y左端或者使集装箱的空间利用率最高。则问题的目标函数可描述为：下端Wnx后端Maxz＝Σ（liwihi）／V（2）i＝1图1集装箱在坐标系中的位置1．1．2约束条件2基于遗传算法的问题求解装箱约束条件如下:遗传算法是
6、一种基于达尔文进化论思想的全局最优化（1）货物放置方向的约束:在装载中,货物只能水平放算法。在问题求解过程中，模仿自然界生物进化过程，以被置，不能旋转。索空间中的每一个点表示每一个生物个体，从任一代初始（2）货物装载质量的约束:货物装载的总质量不得多群体出发，通过随机选择、交叉、变异等过程，使群体进化到于集装箱的最大装载质量。搜索空间中越来越理想的区域。收稿日期：2010－03－31*周昕哈尔滨理工大学计算机科学与技术学院讲师（黑龙江，哈尔滨150080）。**纪颖哈尔滨理工大学计算机科学与技术学院副教授（黑龙江，哈尔滨150080）。·117·遗传算法的
7、优越性主要表现在搜索过程中不易陷入局协调。部最优，即使在所定义的适应度函数不连续的情况下，也能在交叉过程中，由[1，3n]间按均匀分布随机产生两个以极大的概率找到最优解[7]。整数a，a（a＜a）作为父代两个个体S，S的交叉位，1212122．1编码预处理若a1＞n，则交叉仅在sn＋1至s3n段间进行，直接交换交叉定义货物水平放置方向为货高与箱高相互平行的放置位间对应位置的基因而其余基因保持不变；若a2≤n，则交状态，则集装箱最多装载层数M计算:叉仅在s1至sn段间进行，采取序交叉方法；若a1≤n且a2＞nM＝H／hi（3），则交叉在两段间分别进行，s1至
8、sn段采取序交叉方法对在进行个体编码之前，做如下的编码预处理：a1
