三维装箱问题的遗传算法研究

２０ｌＯ耳６月　电　脑　学　习　第３期　三维　装箱问题的遗传算法研究　周　昕　纪颖”　摘　要：本文以集装箱自动装载系统为例。根据货物放置方向　装载客积等约束条件。给出了有效的解码算法．提出了一种改进　遗传算法．并通过实例数据进行了实验结果分析。　关键词：三维装箱　遗传算法　优化　中图分类号：ＴＰ３０１．６　文献标识码：　Ａ　文章编号：１００２—２４２２（２０１０）０３—０１１７—０３　Ｒｅｓｅａｒｃｈ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｔｈｒｅｅ　Ｄｉｍｅｎｓｉｏｎａｌ　Ｃｏｎｔａｉｎｅｒ－Ｐａｃｋｉｎｇ　Ｐｒｏｂｌｅｍ　Ｚｈｏｕ　Ｘｉｎ　Ｊｉ　ＹｉＩｌｇ　Ａｂｓｔｒａｃｔ：　Ｂａｓｅｄ　ｏｎ　ａｕｔｏｍａｔｉｃ　ｃｏｎｔａｌｎｅｒ－ｐａｃｋｉｎｇ　ｓｙｓｔｅｍ，ｔｈｅ　ｐａｐｅｒ　ｔａｋｅｓ　ｉｎｔｏ　ａｃｃｏｕｎｔ　ｔｈｅ　ｄｉｅｒｃｔｉｏｎ　ｏｆ　ｔｈｅ　ｇｏｏｄｓ，ｌｏａｄｉｎｇ　ｃａｐａ－　ｃｉｔｙ　ａｎｄ　ｏｔｈｅｒ　ｃｏｎｓｔｒａｉｎｔｓ，ａｎｄ　ｉｔ　ｃｏｎｔｒｉｂｕｔｅｓ　ａｎ　ｅｆｆｅｃｔｉｖｅ　ｄｅｃｏｄｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｓｉｔｈ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ，ｔｈｅｒｅｆｏｒｅ　ｎａａｌｙｚｅｓ　ｔｈｅ　ｒｅｓｕｌｔ　ｂａｓｅｄ　ｏｎ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｄａｔａ．　Ｋｅｙｗｏｒｄ：　Ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌ　Ｃｏｎｔｉａｎｅｒ－Ｐａｃｋｉｎｇ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　１装箱问题的数学模型　（３）货物装载容积的约束：货物装载的总容积不得大　集装箱三维装载优化问题可描述为：在一定约束条件　于集装箱的最大装载容积。　限制下，将一批货物按照适当的装载方法装入同一集装箱　（４）稳定性的约束：货物装载应该使重心位于允许的　中，使得集装箱的容积利用率或装载质量利用率最大，从　范围内而确保整体稳定，以利于运输安全。　而增强对集装箱的合理有效使用。为方便建模，约定如下：　（５）承载能力的约束：在装载中，货物所能承受的最大　货物简化为长方体，高度相等且均小于集装箱尺寸；货物　压力受限制。　以水平方向放置于集装箱中任位置而不受配置位置限制。　（６）货物装载顺序：不同的货物在装载中应按不同的　１．１目标函数及约束条件　优先顺序装载。　１．１．１目标函数描述　１．２货物装载遵循的方向次序原则　装箱的目标可描述为如下的最大化函数旧：　定义集装箱箱门所在端为后端，集装箱在坐标系中的　位置关系如图１所示。则在集装箱中装载货物遵循以下原　Ｍａｘ　ｚ＝　∑（１。Ｗｉ　ｈｉ）／ｖ＋（１一　）∑（＆６　）／Ｇ　（１）　ｉ　１　ｉ≈ｌ　则：　其中Ｉｊ、ｗｉ、ｈｉ、　分别表示货物ｉ（ｉ＝Ｉ，２，？，１３）　（１）依次沿左侧至右侧方向（即Ｙ轴方向）、前端至后　的长、宽、高和质量；Ｖ，Ｇ分别表示集装箱的最大装载容积　端方向（即ｘ轴方向）放置每一层。　和最大装载质量。　是０－１变量，当追求目标为容积利用　（２）沿下端至上端方向（即ｚ轴方向）逐层放置。　率最大时　＝１，当追求目标为装载质量利用率最大时　＝　Ｚ＾　０：６　ｉ是０—１变量，若货物ｉ装载则６　ｉ：１，否则／５　ｉ　上端　前端　＝Ｏ。　本文旨存确定一种集装箱装载方案，以便将所有货物　端　装入集装箱中；如果不能完全装入，则找到一个待装子集，　ｙ　或者使集装箱的空间利用率最高。则问题的目标函数可描　左端　述为：　Ｍａｘ　ｚ＝　（１ｊ　ｗｊ　ｈｉ）／ｖ　（２）　，　后端　ｉ＝１　图１集装箱在坐标系中的位置　１．１．２约束条件　２基于遗传算法的问题求解　装箱约束条件如下：　遗传算法是一种基于达尔文进化论思想的全局最优化　（１）货物放置方向的约束：在装载中，货物只能水平放　算法。在闯题求解过程中，模仿自然界生物进化过程，以被　置，不能旋转。　索空间中的每一个点表示每一个生物个体，从任一代初始　（２）货物装载质量的约束：货物装载的总质量不得多　群体出发，通过随机选择、交叉、变异等过程，使群体进化到　于集装箱的最大装载质量。　搜索空间中越来越理想的区域。　收稿日期：２０１０—０３—３１　周昕哈尔滨理工大学计算机科学与技术学院讲师（黑龙江，哈尔滨１５００８０）。　￥纪颖哈尔滨理工大学计算机科学与技术学院副教授（黑龙江，哈尔滨１５００８０）。　．１ｌ７．　遗传算法的优越性主要表现在搜索过程中不易陷入局　协调。　部最优，即使在所定义的适应度函数不连续的情况下，也能　以极大的概率找到最优解ｆ７ｌ。　２．１编码预处理　在交叉过程中，由［１，３　ｎ】间按均匀分布随机产生两个　整数ａ。，ａ：（ａ　＜ａ２）作为父代两个个体ｓ，，Ｓ：的交叉位，　若ａｔ＞ｎ，则交叉仅在ｓ　。至ｓ，　段间进行，直接交换交叉　定义货物水平放置方向为货高与箱高相互平行的放置　状态，则集装箱最多装载层数Ｍ计算：　Ｍ＝Ｈ／ｈｉ　（３）　位间对应位置的基因而其余基因保持不变；若ａ２≤１１，则交　叉仅在ｓ。至Ｓ　段间进行，采取序交叉方法；若ａｌ≤ｎ且ａ２＞ｒｉ　，则交叉在两段间分别进行，ｓ。至ｓ。段采取序交叉方法对　在进行个体编码之前，做如下的编码预处理：　ａｎ￣ｎ位间的基因进行重组，ｓ　至ｓ知段问直接对应交换１１＋　ｌ—ａ：位间的基因。　（１）货物编号：按自然数序列对待装货物进行编号，ｉ　＝１，２，…，ｎ　ｏ　（２）放置方向编号：若货物的放置方向为ｌｉｄ　Ｌ，ｗｉ／Ｗ　，ｈｉ／Ｈ，则编号为１：若货物的放置方向为ｗｉ∥Ｌ，ＩＶ／Ｗ，ｈｉ　∥Ｈ，则编号为２。　２．２个体编码及解码嘲　编码时考虑货物放置方向及装载顺序约束，每种装载　方案对应一个编码长度为３　ｎ的符号串个体Ｐ＝（８。，ｓ’…．，　Ｓｉ，…ｓｎ，８ｎ“，８ｍ－２，…，￥ｗｄ，…，ｓ＇』，ｓ　ｌ，ｓ　＋２，…，ｓ　，…，Ｓ３ｎ）。基因　ｓ　一ｓ　表示货物装载顺序编号，ｆｉｔ［１，ｎ】间随机产生的一　系列非重复整数排列组成，　并且基因ｓ。一ｓ　所在位置序列　号１，２，…，ｎ与货物编号一一对应。基因Ｓｎ＋Ｉ￣Ｓ知表示货物　的放置方向编号，由【１，２】间随机产生的一系列可重复整　数排列组成；基因Ｓ２ａ＋ｌ—ｓ，　表示装载层数编号，由【０，Ｍ】间　随机产生的一系列可重复整数排列组成，ｓ　＝０表示货　物ｉ不装载。　个体解码方法：　（１）基因ｓ　，Ｓ　，Ｓ　之间具有一一对应关系，即基因　８　表示的具有某装载顺序的货物ｉ按照基因ｓ　表示的放　置方向装载至基因ｓ　表示的层中。　（２）ｓ　取值小的货物先装，取值大的货物后装。　（３）基因８　表示的放置方向按照编码预处理进行解　码。　（４）货物在箱中的装载遵循所规定的方向次序原则。　２．３遗传算子　２．３．１选择　选择算子的目的是把优化的个体（或解）遗传到下一　代，或通过配对交叉产生新的个体遗传到下一代。选择算子　的操作是建立在群体中个体的适值基础上，采用轮盘赌选　择方法，复制Ｎ个个体。若某个体ｉ，其适应度为ｆｉ，则选挥　概率为：　Ｐｉ＝￡／　（４）　ｉ＝Ｉ　选择适应度最大的个体组成新一代种群。　２．３．２交叉　交叉算子是把两个父代个体的部分结构加以替换重　组，而生成新个体，在遗传算法中起核心作用。交叉算子的　设计一般与所求解的具体问题有关，而且要和编码方式相　２．３．３变异　变异算子是对染色体的某些基因座上的基因值作变　动，作用是维持群体的多样性，避免算法早熟收敛甚至无法　寻到全局最优解。　对个体采取变异操作过程：在【ｎ＋ｌ，３ｎ】间按均匀分布　随机产生一个整数ｂ：作为基因Ｓｎ＋ｌ￣Ｓ　间的变异位，若ｎ＋　１≤ｂ：≤２ｎ则将该位基因值替换为相异编号值；若２　ｎ＋　１≤ｂ。≤３ｎ则将该位基因值替换为【０，Ｍ】间随机产生的一　整数。　２．４适应度计算　通过个体适应值的大小来评价群体中个体所对应装载　方案的优劣，对于违反装载质量约束、装载容积约束和装　载重心约束的个体，在求解其适应值的过程中要给予相应　的惩罚以确保符合条件而较优的个体有较大的生存机会。　２．５终止准则　采用设定最大迭代次数的方法来判断是否终止。　３结束语　对集装箱货物装载问题提出了一种改进遗传算法，解　决了简化模型下的集装箱货物装载的求解问题，方法简单　易行。　参考文献　［１　Ｊ］ｏｈｎｓｏｎ　Ｄ　Ｓ．计算机和难解性一ＮＰ完全性理论导论．张立昂，　译．北京：科学邮版社，１９９０．　【２】Ｋｈｏｏ　Ｗ　Ｓ，Ｓａ．ｒａｔｅｈａｎｄｒａｎ　Ｐ，Ｓｕｎｄａｒａｒａｊａｎ　Ｎ．Ａ　ｇｅｎｅｔｉｃ叩一　ｐｒｏａｃｈ　ｆｏｒ　ｔｗｏ　ｄｉｍｅｎｓｉｏｎａｌ　ｐａｃｋｉｎｇ　ｗｉｔｈ　ｃｏｎｓｔｒａｉｎｔ　Ｓ【Ａ】．Ｐｒｏ—　ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｐａｒｔ　ＩＩ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔａｔ—　ｉｏｎａｌ　Ｓｃｉｅｎｃｅ　ＩＣＥＳ【Ｃ】．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＣＡ，ＵＳＡ：Ａｌｅｘａｎｄｒ－　ＯＶ，２００ｌ，２９１—２９９．　【３】Ａｎｄｒｅａ　Ｌｅｄｉ，Ｓｉｌｖａｎｏ　ＭａｒｔｅＨｏ，Ｄａｎｉｅｌｅ　Ｖｉｇｏ．Ａｐｐｒｏｘｉｍａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｈｅ　ｏｒｉｅｎｔｅｄ　２　ｄｉｍｅｎｓｉｏｎａｌ　ｂｉｎ　ｐａｃｋｉｎｇ　ｐｒｏｂｌｅｍ　【Ｊ】．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９９，１　１２：１５８—　１６６．　【４】Ｌｉｐｎｉｔ　ｓｋｉｉ　Ａ　Ａ．Ｕｓｅ　ｏｆ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｓｏｌｕｔｉｏｎ　ｏｆ　ｔｈｅ　ｅｒｃｔａｎｇｌｅ　ｐａｃｋｉｎｇ　ｐｒｏｂｌｅｍ【Ｊ１．Ｃｙｂｅｒｎｅｔｉｃｓ　ａｎｄ　Ｓｙｓｔｅｍｓ　Ａｎａｌｙ—　ｓｉｓ，２００２，３８（６）：９４３—９４６．　【５】许光泞，俞金寿．改进遗传算法求解三维集装箱装载问题【Ｊ】．　上海：华东理工大学学报，２００７，３３（３）：４２５－－４２８．　【６】翟钰．三维装箱问题的混合遗传算法研究．上海：上海交通大　学硕士论文，２００７．　２０１Ｏ年６月　电　脑　学　习　第３期　基于驱动的进程创建监控的实现　刘利‘　戚建亮　摘　要：介绍了驱动开发技术背景及应用．讲述ＳＳＤＴ　ＨＯＯＫ方法．实现监控ＮｔＣｒｅ｛ｌｔｅＰｒｏｅｅ￣ｓＥｘ系统服务。ＲＩＮＧ３应用程序和　驱动程序的交互。ＲＩＮＧ３应用程序和驱动程序的同步实现基于驱动的进程创建监控。　关键词：驱动　进程创建　中图分类号：ＴＰ３１　１．１　文献标识码；　Ａ　文章编号：１Ｏｏ２－２４２２（２０１０）０３—０１　１９－－０２　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　Ｍｏｎｉｔｏｒｉｎｇ　Ｐｒｏｃｅｓｓ　Ｃｒｅａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｄｒｉｖｅ　Ｌｉｕ　Ｌｌ　Ｑｉ　Ｊｉａｎｌｉａｎｇ　Ａｂｓｔｒａｃｔ：　Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈｅ　ｂａｃｋｇｒｏｕｎｄ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｄｒｉｖｅｒ　Ｄｅｖｅｌｏｐｍｅｎｔ　ｔｅｃｈｎｄｏｇ＇ｙ　８ｒｅ　ｉｎｔｒｏｄｕｃｅｄ　ａｎｄ　ｄｅｓｃｒｉｂｅｄ　ｉｎ　ｄｅ—　ｔａｉｌｅｄ．Ｔｈｅ　ｆｉｒｓｔ　ｏｎｅ　ｉｓ　ＳＳＤＴ　ＨＯＯＫ　ｍｅｔｈｏｄ　ｔｏ　ａｃｈｉｅｖｅ　ｃｏｎｔｒｏｌ　ＮｔＣｒａｃｔｅＰｒｏｅｅｓｓＥｘ　ｓｙｓｔｅｍ　ｓｅｒｖｉｃｅｓ，ｔｈｅ　ｓｅｃｏｎｄ　ｏｎｅ　ｉｓ　ｉｎｔｅｒａｃｔｉｏｎ　ｂｅｔｗｅｅｎ　ＲＩＮＧ３　ａｐｐｌｉｃａｔｉｏｎ　ａｎｄ　ｄｒｉｖｅｒ，ａｎｄ　ｔｈｅ　ｔｈｉｒｄ　ｏｎｅ　ｉｓ　ＲＩＮＧ３　ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　ｄｒｉｖｅｒｓ　ｓｙｎｃｈｒｏｎｉｚａｔ—　ｉｏｎ，ｗｈｉｃｈ　ａｃｈｉｅｖｅ　ｍｏｎｉｔｏｒｉｎｇ　ｐｒｏｃｅｓｓ　ｃｒｅａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｄｒｉｖｅ．　Ｋｅｙｗｏｒｄ：　Ｄｆｉｖｅｒ　Ｐｒｏｃｅｓｓ　Ｃｒｅａｔｉｏｎ　１背景简介　来锁住ＳＳＤＴ后再修改，或者调用ＩｎｔｅｄｏｅｋｅｄＥｘｃｈａｎｇｅ（）来　随着互联网的全民化，木马、病毒成为困扰网络安全的　修改。系统服务ＮｔＣｒｅａｔｅＰｒｏｃｅｓｓＥｘ（）的参数如下：　一个重要的因素，各主流安全软件推出了基于行为判断的　ＮＴＳＹＳＡＰＩ　主动防御技术，简易的实现其中功能之一：进程创建监控。　Ｎ　ｒｓＴＡＴＵＳ　下面的实例是基于驱动程序的，监控的是进程的创建。　ＮＴＡＰＩ　ＮｔＣｒｅａｔｅＰｒｃｅｅｓｓＥｘ（　当进程需要创建时，监控模块会弹出如图１所示的一个窗　０ＵＴ　ＰＨＡＮＤＬＥ　ＰｒｏｃｅｓｓＨａｎｄｌｅ．　口，询问是否同意创建这个进程，点击“确定”，进程可以正　ＩＮ　ＡＣＣＥＳＳ　ＭＡＳＫ　ＤｅｓｉｅｒｄＡｃｅｅｓａ，　常运行；点击“取消”，这个进程将无法运行，同时弹出拒　ＩＮ　ＰＯＢＪＥＣ　１　１Ｔｌ’ＲＩＢＵＴＥＳ　ＯｂｊｅｃｔＡｔｔｉｒｂｕｔｅｓ．　绝运行窗口。　ＩＮ　ＨＡＮＤＬＥ　ｌｎｈｅｒｌｔＦｍｍＰｒｏｃｅｓｓＨａｎｄｌｅ，　ＩＮ　ＵＬＯＮＧ　ＣｒｅａｔｅＦｌａｇｓ，　ＩＮ　ＨＡＮＤＬＥ　ＳｅｃｔｉｏｎＨａｎｄｌｅ　ＯＰＴＩＯＮＡＬ，　ＩＮ　ＨＡＮＤＬＥ　ＤｅｂｕｇＯｂｊｅｃｔ　ＯＰＴＩＯＮＡＬ，　ＩＮ　ＨＡＮＤＬＥ　ＥｘｅｅｐｔｉｏｎＰｏｒｔ　ＯＰＴＩＯＮＡＬ，　ＩＮ　ＵＬＯＮＧ　ＪｏｈＭｅｍｈｅｒＬｅｖｄ　）；　当ＲＩＮＧ３的应用程序需要创建一个进程时，参数ＯＵＴ　ＰＨＡＮＤＬＥ　ＰｒｏｃｅｓｓＨａｎｄｌｅ会在进程创建成功后返回该进程　图１　的ＨＡＮＤＬＥ。　２通过ＳＳＤＴ　ＨＯＯＫ方法实现监控ＮｔＣｒｅａｔｅＰｒｏ—　通过该方法可以获取创建这个进程的父窗口的ＰｌＤ和　ｃｅｓｓＥｘ系统服务　即将创建的进程的路径。驱动程序是没有自己独立的进程　要监控进程的创建，简单而有效的方法是ＳＳＤＴ　的，而是“依附”在调用者的进程中，当ＲＩＮＧ３有进程创建　ＨＯＯＫ。Ｓｙｓｔｅｍ　Ｓｅｒｖｉｃｅ　Ｄｉｓｐａｔｈ　Ｔａｂｌｅ是系统服务派送表，　进程而进入ＨＯＯＫ后的ＮｔＣｒｅａｔｅＰｒｏｅｅｓｓＥｘ（），通过调用　通过ＳＳＤＴ　ＨＯＯＫ中的系统服务ＮｔＣｒｅａｔｅＰｍｃｅｓｓＥｘ（），所　（）可获得调用ＮｔＣｒｅａｔｅＰｒｏｃｅｓｓＥｘ（）进　有来自ＲＩＮＧ３的进程创建请求都会调用它。如果要更彻底　程的进程信息，调用ＰｓＧｅｔＣｕｒｒｅｎｔＰｒｏｃｅｓｓｌｄ（）能获得调用　的监控进程的创建，可以ＨＯＯＫ更深层的ＰｓｐＣｒｅａｔｅＰｒｏｅｅｓｓ　ＮｔＣｒｅａｔｅＰｒｏｃｅｓｓＥｘ（）进程的进程ＰＩＤ（进程标识符）；通过　（），详细内容请参考相关资料。　参数中的ＳｅｃｆｉｏｎＨａｎｄｌｅ，获得对应的ＦｉｌｅＯｂｊｅｃｔ，再通过　ＳＳＤＴ　ＨＯＯＫ时需要注意多线程安全性：可以用ＭＤＬ　ＦｉｌｅＮａｍｅ获得即将创建的进程的路径。　ｆ７】ａＥｄ，平，曹立明．遗传算法一理论、应用与软件实现【Ｍ】．西安：　【８］ｂ雷，等．基于遗传算法的集装箱单箱三维装载优化问题［Ｊ】．　西安交通大学出版社，２００２．　北京：中国铁道科学，２００４（８）．　收稿日期：２０１０－０４—１４　刘利大庆师范学院计算机系本科学生（黑龙江，大庆１６３７１２）。　・ｌ１９・