三维装箱问题的模型与改进遗传算法
关于三维装箱算法问题, 一些算法理论, 感觉对这方面的应用有一定帮助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
Google word2vec算法 数学原理
文档是 word2vec 算法 数学原理详解。word2vec是google的一个开源工具，能够仅仅根据输入的词的集合计算出词与词直接的距离，既然距离知道了自然也就能聚类了，而且这个工具本身就自带了聚类功能，很是强大。32预备知识本节介绍word2v中将用到的一些重要知识点,包括 sigmoid函数、 Bccs公式和Huffman编码等821 sigmoid函数sigmoid函数是神经网络中常用的激活函数之一,其定义为1+e该函数的定义域为(-∞,+∞),值域为(0,1).图1给出了 sigmoid函数的图像0.56图1 sigmoid函数的图像sigmoid函数的导函数具有以下形式(x)=0(x)1-0(x)由此易得,函数loga(x)和log(1-0(x)的导函数分别为log a(a)-1 a(a),log(1 o(a))l-a(a),(2.1)公式(2.1)在后面的推导中将用到32.2逻辑回归生活中经常会碰到二分类问题,例如,某封电子邮件是否为垃圾邮件,某个客户是否为潜在客户,某次在线交易是否存在欺诈行为,等等设{(x;)}温1为一个二分类问题的样本数据,其中x∈Rn,∈{0,1},当v=1时称相应的样本为正例当v=0时称相应的样本为负例利用 sigmoid函数,对于任意样本x=(x1,x2,…,xn),可将二分类问题的 hypothesis函数写成h(x)=o(6o+b1x1+62+…+bnxn)其中θ=(0,61,…,On)为待定参数.为了符号上简化起见,引入x0=1将x扩展为(x0,x1,x2,……,xn),且在不引起混淆的情况下仍将其记为ⅹ.于是,he可简写为取阀值T=0.5,则二分类的判别公式为ho(x)≥0.5:X)=0,ha(x)6),可分别用000001、010、011、100、101对“A,E,R,T,F,D”进行编码发送,当对方接收报文时再按照三位一分进行译码显然编码的长度取决报文中不同字符的个数.若报文中可能出现26个不同字符,则固定编码长度为5(25=32>26).然而,传送报文时总是希望总长度尽可能短.在实际应用中各个字符的出现频度或使用次数是不相同的,如A、B、C的使用颗率远远高于X、Y、Z,自然会想到设计编码时,让使用频率高的用短码,使用频率低的用长码,以优化整个报文编码为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀),可用字符集中的每个字符作为叶子结点生成一棵编码二叉树,为了获得传送报文的最短长度,可将每个字符的岀现频率作为字符结点的权值赋于该结点上,显然字使用频率越小权值起小,权值越小叶子就越靠下,于是频率小编码长,频率高编码短,这样就保证了此树的最小带权路径长度,效果上就是传送报文的最短长度.因此,求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点,由字符出现频率作为其权值所产生的 Huffman树的问题.利用 Huffman树设计的二进制前缀编码,称为 Huffman编码,它既能满足前缀编码的条件,又能保证报文编码总长最短本文将介绍的word2ve工具中也将用到 Huffman编码,它把训练语料中的词当成叶子结点,其在语料中岀现的次数当作权值,通过构造相应的 Huffman树来对每一个词进行Huffman编码图3给岀了例2.1中六个词的 Huffman编码,其中约定(词频较大的)左孩子结点编码为1,(词频较小的)右孩子编码为0.这样一来,“我”、“喜欢”、“观看”、“巴西”、“足球”、“世界杯”这六个词的 Huffman编码分别为0,111,110,101,1001和100000欢观有巴西足球图3 Huffman编码示意图注意,到目前为止关于 Huffman树和 Huffman编码,有两个约定:(1)将权值大的结点作为左孩子结点,权值小的作为右孩子结点;(②)左孩子结点编码为1,右孩子结点编码为0.在word2vee源码中将权值较大的孩子结点编码为1,较小的孩子结点编码为θ.为亐上述约定统一起见,下文中提到的“左孩子结点”都是指权值较大的孩子结点3背景知识word2vec是用来生成词向量的工具,而词向量与语言模型有着密切的关系,为此,不妨先来了解一些语言模型方面的知识83.1统计语言模型当今的互联网迅猛发展,每天都在产生大量的文本、图片、语音和视频数据,要对这些数据进行处理并从中挖掘出有价值的信息,离不开自然语言处理( Nature Language processingNIP)技术,其中统计语言模型( Statistical language model)就是很重要的一环,它是所有NLP的基础,被广泛应用于语音识别、机器翻译、分词、词性标注和信息检索等任务例3.1在语音识别亲统中,对于给定的语音段Voie,需要找到一个使概率p(Tcrt| Voice最大的文本段Tert.利用 Bayes公式,有P(Teact Voice)p(VoiceTert)p(Text)P(Veonce其中p( Voice Teat)为声学模型,而p(Tert)为语言模型(l8])简单地说,统计语言模型是用来计算一个句子的概率的概率模型,它通常基于一个语料库来构建那什么叫做一个句子的概率呢?假设W=m1:=(n1,w2,…,tr)表示由T个词1,2,…,ur按顺序构成的一个句子,则n,U2,…,wr的联合概率p(W)=p(u1)=p(u1,u2,…,r)就是这个句子的概率.利用 Baves公式,上式可以被链式地分解为1)=p(u1)·p(u2l1)·p(vai)…p(ur1-)3.1其中的(条件)概率p(1),p(U2mn1),p(u3),…,p(urln1-1)就是语言模型的参数,若这些参数巳经全部算得,那么给定一个句子1,就可以很快地算出相应的p(1)了看起来妤像很简单,是吧?但是,具体实现起来还是有点麻烦.例如,先来看看模型参数的个数.刚才是考虑一个给定的长度为T的句子,就需要计算T个参数.不妨假设语料库对应词典D的大小(即词汇量)为N,那么,如果考虑长度为T的任意句子,理论上就有N种可能,而每种可能都要计算T个参数,总共就需要计算TN个参数.当然,这里只是简单估算,并没有考虑重复参数,但这个量级还是有蛮吓人.此外,这些概率计算好后,还得保存下来,因此,存储这些信息也需要很大的內存开销此外,这些参数如何计算呢?常见的方法有 II-gram模型、决策树、最大熵模型、最大熵马尔科夫模型、条件随杋场、神经网络等方法.本文只讨论n-gram模型和神经网络两种方法.首先来看看n-gram模型32n-gram模型考虑pko4-)(k>1)的近似计算.利用 Baves公式,有p(wr wi)P(uP(w根据大数定理,当语料库足够大时,p(k4-1)可近似地表示为P(wwi)count(wi)(3.2)count(a其中 count(u4)和 count-)分别表示词串t和v-在语料中出现的次数,可想而知,当k很大时, count(o4)和 count(4-1)的统计将会多么耗时从公式(3.1)可以看出:一个词出现的慨率与它前面的所有词都相关.如果假定一个词出现的概率只与它前面固定数目的词相关呢?这就是n-gran模型的基本思想,它作了一个n-1阶的 Markov假设,认为一个词出现的概率就只与它前面的n-1个词相关,即-1)≈p(kk-1+),于是,(3.2)就变成了p(wxJuk-)count(n+1countri(3.3以〃=2为例,就有p(uk4-1)≈count(k-1, Wk)count(Wk-1)这样一简化,不仅使得单个参数的统计变得更容易(统计时需要匹配的词串更短),也使得参数的总数变少了那么, n-gran中的参数n取多大比较合适呢?一般来说,n的选取需要同时考虑计算复杂度和模型效果两个因素表1模型参数数量与n的关系模型参数数量1( ingram)2×1052(bigram)4×10103( trigram)8×10154(4grm)16×10在计算复杂度方面,表1给出了n-gram模型中模型参数数量随着n的逐渐增大而变化的情况,其中假定词典大小N=2000(汉语的词汇量大致是这个量级).事实上,模型参数的量级是N的指数函数(O(N"),显然n不能取得太大,实际应用中最多的是采用n=3的三元模型在模型效果方面,理论上是π越大,效果越奷.现如今,互联网的海量数据以及机器性能的提升使得计算更高阶的语言模型(如n>10)成为可能,但需要注意的是,当n大到一定程度时,模型效果的提升幅度会变小.例如,当n从1到2,再从2到3时,模型的效果上升显著,而从3到4时,效果的提升就不显著了(具体可参考吴军在《数学之美》中的相关章节).事实上,这里还涉及到一个可靠性和可区别性的问题,参数越多,可区别性越好,但同时单个参数的实例变少从而降低了可靠性,因此需要在可靠性和可区别性之间进行折中另外, n-gran模型中还有一个叫做平滑化的重要环节.回到公式(3.3),考虑两个问题:若 count(uk-n+1)=0,能否认为p(kln1-1)就等于0呢?若 count(kn+)= count(uk-+1,能否认为p(uur-)就等于1呢?显然不能!但这是一个无法回避的问题,哪怕你的语料库有多么大.平滑化技术就是用来处理这个问题的,这里不展开讨论,具体可参考[11总结起来,n-gram模型是这样一种模型,其主要工作是在语料中统计各种词串岀现的次数以及平滑化处理.概率值计算好之后就存储起来,下次需要计算一个句子的概率时,只需找到相关的概率参数,将它们连乘起来就好了然而,在机器学习领域有一种通用的招数是这样的:对所考虑的问题建模后先为其构造一个目标函数,然后对这个目标函数进行优化,从而求得一组最优的参数,最后利用这组最优参数对应的模型来进行预測对于统计语言模型而言,利用最大似然,可把目标函数设为plwlConteat(w))∈C其中C表示语料( Corpus), Context(u)表示词U的上下文( Context),即周边的词的集合.当 Context(u)为空时,就取p( Context(w)=p(u).特别地,对于前面介绍的 n-gran模型,就有 Context(mn)=2-n+1注3.1语料￠和词典仍的区别:词典仍是从语料￠中抽取岀来的,不存在重复的词;而语料C是指所有的文本內容,包括重复的词当然,实际应用中常采用最大对数似然,即把目标函数设为∑ logp(u( ontext(o)(3.4)然后对这个函数进行最大化从(3.4)可见,概率p( CONtex()已被视为关于和 Context()的函数,即p(w Context(w))= F(w, Conteact(w), 0)
- 2020-06-14下载
- 积分：1
