三维装箱问题的模型与改进遗传算法
关于三维装箱算法问题, 一些算法理论, 感觉对这方面的应用有一定帮助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
mqtt物联网数据传输协议
引用github的资源https://mcxiaoke.gitbooks.io/mqtt-cn/Introduction3.2 CONNACK一确认连接请求o3.3 PUBLISH-发布消息o34 PUBACK一发布确认o35 PUBREC-发布收到(QoS2,第一步)°36 PUBREL-发布释放(QoS2,第二步)°3.7P∪ BCOME一发布完成(QoS2,第三步)o3.8 SUBSCR|BE-订阅主题o39S∪BACK-订闶确认o3.10 UNSUBSCR|BE-取消订阅3.11 UNSUBACK-取消订阔确认3.12P| NGREG一心跳请求3.13 PINGRESE一心跳响应o3.14D| SCONNECT一断开连接第四章一操作行为第五章一安全第六章一使用 Websocket第七章一一致性目标附录B-强制性规范声明旧版文档已过期,建议使用 GifTbook版本最新版本:V1.0.12015.10.22文档连接中文版HTMLMQTT3.1.1中文版中文版PDFMQTT3.1.1中文版英文版HTMLMQTT Version 3.1.1英文版PDFMQTT∨ ersion3.1.1许可协议署名-非商业性位用-相同方式共享4.0国际联系方式IntroductionBloghttp://blog.mcxiaoke.comGithub:https://github.com/mcxiaoke.Email:github@mcxiaoke.com开源项目·Rx文档中文翻译:htts:/! github. com/mcxiaoke/ RXDOCS·MQTT协议中文版:htps:/ github. com/ mcxiaoke/mgttAwesome-kotlin:httpsgithub.com/mcxiaokelawesome-kotlin.Kotlin-koi:https:/github.com/mcxiaoke/kotlin-koiNeXt公共组件库:htps!/github.com/xiaoke/Android-Next· PackerNg极速打包:htts;/ github. com/mcxiaoke/ packer- ng-pluginGradle渠道打包https://github.com/mcxiaoke/gradle-packer-plugin·VentuS实现xBus:htps;/github.com/miaoke/BuS磨菇饭App:htps:! github. com/mcxiaoke/minicat·饭否客户端:https:/github.com/mcxiaoke/anfouapp-opensourceVolleyt:https://github.com/mcxiaoke/android-volley第一章-MQTT介绍第一章概逃 Introduction1.1MQTT协议的组织结构 Organization of MQTT本规范分为七个章节:第一章一介绍第二章一MQTT控制报文格式第三章一MQTT控制报文·第四章一操作行为第五章一安全第六章一使用 Websocket第七章一一致性日标附录B一强制性规范声明12术语 Terminology本规范中用到的夭键字必须MUST,不能 MUST NOT,要求 REQUIRED,将会 SHALL,不会 SHALL NOT,应该 SHOULD,不应该 SHOULD NOT,推荐 RECOMMENDED,可以MAY,可选 OPTIONAL都是按照 TE RFC2119[RFC2119]中的描迹解释。网络连接 Network ConnectionMQTT使用的底层传输协议基础设施。客户端使用它连接服务端。它提供有序的丶可靠的丶双向字节流传输。例子见42节应用消息App| ication Message MQT协议通过网络传输应用数据。应用消息通过MQT传输时’它们有关联的服务质量(QoS)和主题( Topic)客户粥C|ient使用MQπT的程序或设备。客户端总是通过网络连接到服务端。它可以发布应用消息给其它相关的客户端。●订阅以请求接受相关的应用消息。·取消订阅以移除接受应用消息的请求从服务端断开连接第一章-MQTT介绍服务端 Server个程序或设备,作为发送消息的客户端和请求订阅的客户端之间的中介σ服务端接受来自客户端的网络连接。接受客户端发布的应用消息。·处理客户端的订阅和取消订阅请求。转发应用消息给符合条件的已订阅客户端订 Subscription订阔包含一个主题过滤器( Topic Filter)和一个最大的服务质量(QoS)等级。订阅与单个会话( Session)关联。会话可以包含多于一个的订阅。会话的每个订阅都有一个不同的主题过主题名 Topic Name附加在应用消息上的一个标签’服务端巳知且与订阔匹配。服务端发送应用消息的一个副本给每一个匹配的容户端订阅。主题过滤器 Topic Filter订阅中包含的一个表达式,用于表示相关的一个或多个主题。主题过滤器可以使用通配符。会话 Session客户端和服务端之间的状态交互。一些会话持续时长与网络连接一样·另一些可以在客户端和服务端的多个连续网络连接间扩展。控制报文 MQTT Contro| Packet通过网络连接发送的信息数据包。MQTT规范定义了十四种不同类型的控制报文,其中一个( PUBLISH报文)用于传输应用消息。1.5数据表示 Data representations1.51二进制位Bits字节中的位从0到7。第7位是最高有效位’第0位是最低有效位。1.52整数数值 Integer data values整数数值是16位’使用大湍序( big-endian,高位字节在低位字节前面)。这意味着一个16位的字在网络上表示为最高有效字节(MSB),后面跟着最低有效字节(LSB)1.53UTF8编码字符串UTF8 encoded strings后面会描逑的控制报文中的文本字段编码为UTF8格式的字符串。UTF8[RFC3629]是一个高效的υ ncode字符编码格式’为了攴持基于文本的通信’它对ASC∏字符的编码做了优化第一章-MQTT介绍每一个字符串都有一个两字节的长度字段作为前缀,它给出这个字符串UTF8编码的字节数,它门在图例1.1UTF8编码字符串的结构中描述。因此可以传送的UTF-8编码的字符串大小有个限制,不能超过65535字节除非另有说明’所有的UTF-8编码字符串的长度都必须在0到65535字节这个范围内。图例1.1UTF8编码字符串的结构 Structure of ute8 encoded strings进制位7-0yte字符串长度的最高有效字节(MsB)byte 2字符串长度的最低有效字节(LSB)byte 3如果长度大于0,这里是UTF-8编码的字符数据。UTF-8编码字符串中的字符数据必须是按照 Unicode规范[ Unicode]定义的和在RFC3629[RFC3629]中重申的有效的UTF8格式。特別需要指出的是,这些数据不能包含字符码在U+D800和U+DFFF之间的数据。如果服务端或客户端收到了一个包含无效UTF-8字符的控制报文”它必须关闭网络连接[MQTT1.53-]。UTF-8编码的字符串不能包含空字符U+0000如果客户端或服务端收到了一个包含U+0000的控制报文’它必须关闭网络连接MQTT-1.53-2]数据中不应该包含下面这些 Unicode代码点的编码。如果一个接收者(服务端或客户端)收到了包含下列任意字符的控制报文,它可以关闭网络连接U+0001和U+00F之间的控制字符∪+007F和∪+009F之问的控制字符Unicode规范定义的非宇符代码点(例如U+ OFFFF)Unicode规范定义的保留字符(例如U+ OFFFF)UTF-8编码序列0XEF0xBB0XBF总是被解释为U+FEFF(零宽度非换行空白字符)’无论它出现在字符串的什么位置’报文接收者都不能跳过或者剥离它[MQTT-153-3]。非规范示例 Non normative example例如,字符串A是一个拉丁字母A后面跟着一个代码点U+2A6D4(它表示一个中日韩统表意文字扩展B中的字符)这个字符串编码如下图例12UTF8编码字符串非规范示例UTF-8 encoded string non normative example第一章-MQTT介绍Bit54byte 1字符串长度MSB(0x0O)00byte 2字符串长度LSB(0×05)byte 3A(0×41)00000bye4(0×F0)000byte 5(OXAA)00byte 6(0×9B)0byte 7(0×94)0001.6编辑约定 Editing conventions本规范用黃色高亮的文本标识一致性声明·毎个一致性声明都分配了一个这种袼式的引用:[MQTT××x-y]项目主页MQTT协议中文版第二章一MQTT控制报文格式第二章MQTT控制报文格式 MQTT ControPacket format目录第一章-个绍第二章一MQTT控制报文格式第三章一MQTT控制报文·第四章一操作行为第五章一安全第六章一使用 Websocket第七章一一致性目标附录B-强制性规范声明2.1MQTT控制报文的结构 Structure of an MQTTControl packetMQπT协议通过交換预定义的MQTT控制报文来通信。这一节描逃这些报文的格式。MQTT控制报文由三部分组成’按照图例2.1-MQ∏控制报文的结构描逃的顺序图例21-MQTT控制报文的结构Fixed header固定报头’所有控制报文都包含Variable header可变报头·部分控制报文包含Payload有效载荷·部分控制报文包含22固定报头 Fixed header每个MQTT控制报文都包含一个固定报头。图例2.2-因定报头的格式描逑了因定报头的格式图例22-固定报头的格式第二章一MQTT控制报文格式Bit65432byte 1MQTT控制报文的类型用于指定控制报文类型的标志位byte 2剩余长度221MQTT控制报文的类型 MQTT Control Packet type位置:第1个字节,二进制位7-4表示为4位无符号值,这些值的定义见表格2.1-控制报文的类型表格2.1-控制报文的类型名字值报文流动方向描述Reserved禁止保留CONNECT客户端到服务端客户端请求连接服务端CONNACK2服务端到客户端连接报文确认PUBLISH两个方向都允许发布消息PUBACK丙个方向都允许QoS1消息发布收到确认PUBREC5两个方向都允许发布收到(保证交付第一步)PUBREL两个方向都允许发布释放(保证交付第二步PUBCOMP7两个方向都允许QoS2消息发布完成(保证交互第三步)SUBSCRIBE8客户端到服务端客户端订阅请求SUBACK9服务端到户风请求摄文确认UNSUBSCRIBE10客户端到服务端客户端取消订阋请求UNSUBACK服务端到客戶端取消订阔报文确认PINGREQ12客户端到服务端跳请求PINGRESP13服务端到客户端心跳响应DISCON№ECT14客户端到服务端客户端断开连接Reserved15禁止保留222标志Fags固定报头第1个字节的剩余的4位[30]包含每个MQTT控制报文类型特定的标志,见表格22-标志位。表格2.2中任何标记为“保留”的标志位·都是保留给以后使用的·必须设置为表柊中出的值[MQT「-22.2-1。如果收到非法的标志’接收者必须关闭网络连接。有美错误处理的详细信息见4.8节MQTT2222]
- 2021-05-06下载
- 积分：1
