三维装箱问题的模型与改进遗传算法
关于三维装箱算法问题, 一些算法理论, 感觉对这方面的应用有一定帮助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
专用集成电路设计实用教程
IC设计经典教材,《专用集成电路设计实用教程》专用集成电路设计实用教程虞希清编著大學出瓶社图书在版编目(CIP)数据专用集成电路设计实用教程/虞希清编著.一杭州:浙江大学出版社,2007.1ISBN978-7-308-05113-2专..Ⅱ.虞..Ⅲ.集成电路一电路设计一高等学校一教材Ⅳ.TN402中国版本图书馆CIP数据核字(2006)第165341号专用集成电路设计实用教程虞希清编著任编辑张真封面设计张真出版发行浙江大学出版社(杭州天目山路148号邮政编码310028)(E-mail:zupress@mail,hz,zj.cn)(网址http://www.zjupress.com排版杭州好友排版工作室印刷杭州浙大同力教育彩印有限公司开本787mm×1092mm1/16印张18.25字数467千印数2001-3000版印次207年1月第1版2007年7月第2次印刷书号ISBN978-7-30805113-2定价38.00元版权所有翻印必究印装差错负责调换内容提要在现代的IC设计中,工程师们广泛地使用数字电路的逻辑综合技术。工程师们使用RTL代码和IP描述设计的功能,进行高级设计,用综合工具对设计进行编辑和优化,以实现满足设计目标的电路。根据多年为客户进行技术培训,技术支持和IC设计的经验,笔者编写了本书。书中主要介绍了IC设计的基本概念,设计流程和设计方法,并就工程师们在设计中常见的问题,提供了解决方法。本书的特点是实用性强全书共分九章,第一章概述EC设计的趋势和流程;第二章介绍用RTL代码进行电路的高级设计和数字电路的逻辑综合;第三章陈述了IC系统的层次化设计和模块划分;第四章详细地说明如何设置电路的设计目标和约束;第五章介绍综合库和静态时序分析;第六章深入地阐述了电路优化和优化策略;第七章陈述物理综合和简介逻辑综合的拓扑技术;第八章介绍可测性设计;第九章介绍低功耗设计和分析本书的主要对象是IC设计工程师,帮助他们解决IC设计和综合过程中遇到的实际问题。也可作为高等院校相关专业的高年级学生和研究生的参考书。前言本书在 Synopsys公司的逻辑综合培训资料基础上编写而成。从事EDA工作和ASIC设计已有十几年了。在给中港台ASIC设计工程师提供的技术培训和支持中,工程师们曾提出了设计和使用设计工具中遇到的各种各样的问题。教学相长,在和工程师讨论问题、提供解决方案的过程中,我得到了很多的经验和启发。在为用户解决一些实际问题,为他们提供培训后,我曾收到热情的掌声和感谢信。用户的掌声和谢意给了我很大的鼓励和鞭策,使我下决心要编写一本实用的中文版的集成电路设计教程和手册,以答谢用户们的支持和帮助。本书讲究实用性,希望其中的内容能帮助ASIC设计工程师清楚明了IC设计的基本概念,IC设计的流程,逻辑综合的基本概念和设计方法,解决进行IC设计时和工具使用时所遇到的问题。全书共分九章,第一章概述IC设计的趋势和流程;第二章介绍用RTL代码进行电路的高级设计和数字电路的逻辑综合;第三章陈述了IC系统的层次化设计和模块划分;第四章详细地说明如何设置电路的设计目标和约束;第五章介绍综合库和静态时序分析;第六章深入地阐述了电路的优化和优化策略;第七章陈述物理综合和简介逻辑综合的拓扑技术;第八章介绍可测性设计;第九章介绍低功耗设计和分析本书的主要对象是IC设计工程师,帮助他们解决IC设计和综合过程中遇到的实际问题。也可作为高等院校相关专业的高年级学生和研究生的参考书。在本书的编写过程中,得到了 Synopsys中国区高级技术经理常绍军先生的大力支持。常绍军先生、资深的应用技术顾问李昂先生和冯源先生审阅了本书,并提出了宝贵的意见和建议。在此,表示衷心的感谢。在本书编写过程中,得到了全家的支持,深表谢意!由于时间仓促,知识水平有限,书中难免有不足和错误之处,敬请各位专家,IC设计工程师和同行们批评指正,不胜感激。来函可发电子邮件( Email: victory_snps@ yahoo.com.hk)。虞希清2006年11月于 Synopsys香港目录第一章集成电路设计概论1.1摩尔定律………………∴…………11.2集成电路系统的组成1.3集成电路的设计流程第二章数字电路的高级设计和逻辑综合132.1RTL硬件描述语言设计132.1.1行为级硬件描述语言( Behavioral Level hdi)132.1.2寄存器传输级硬件描述语言( RTL HDI)172.1.3结构化硬件描述语言( Structure HDL)………………………………232逻辑综合(L。 gic Synthesis)…………………272.2.1逻辑综合的基本步骤…282.2.2综合工具 Design Compiler302.2.3目标库和初始环境设置鲁·自自音甲·是着音鲁备.··非曲●d■···●····第三章系统的层次化设计和模块划分353.1设计组成及 DC- Tcl…·自音···········日·········.···卡器日音是·晶自鲁bt·。……353.1.1设计物体( Design Object)鲁音自353.1.2 DC - Tcl简介香看·鲁·鲁·鲁.鲁自春3.2层次( Hierarchy)结构和模块划分( Partition)及修改463.2.1层次结构的概念463.2.2模块的划分…息鲁483.2.3模块划分的修改·看。51第四章电路的设计目标和约束…°。●看。面●554.1设计的时序约束…普·非鲁·鲁击曲■554.1.1同步( Synchronous)电路和异步( Asynchronous)电路…4.1.2亚稳态( Metastability)574.1.3单时钟同步设计的时序约束…血D。e574.1.4设计环境的约束724,1.5多时钟同步设计的时序约束…………794.1.6异步设计的时序约束832专用集成电路设计实用教程4.1.7保持时间( Hold Time)854.2复杂时序约束看香鲁e鲁曲鲁。自鲁自。a。自鲁自。鲁4.2.1多时钟周期( Multi-Cycle)的时序约束874.2.2门控时钟的约束904.2.3分频电路和多路传输电路的时钟约束鲁·看看看鲁924.3面积约束……………………………96第五章综合库和静态时序分析…985.1综合库和设计规则···········.······.··4·a·.·····◆···—985.1.1综合库……5.1.2设计规则1075.2静态时序分析5.2.1时序路径和分组1125.2.2时间路径的延迟1145.2.3时序报告和时序问题的诊断鲁·.···.·自击击合音。甲。。。●。。●……115第六章电路优化和优化策略…1206.1电路优化..···4····;··.·.·.·.·a·a·;··1226.1.1 Synopsys的知识产权库- Design Ware1236.1.2电路优化的三个阶段………………………1266.2优化策略…………1346.2.1编辑策略垂由d垂……1356.2.2自动芯片综合( Automated Chip Synthesis)………………………………1416.3网表的生成格式及后处理144第七章物理综合1487.1逻辑综合(L。 gic Synthesis)遇到的问题……………………1487.2物理综合( Physical Synthesis)的基本流程鲁鲁自谁…………………………1517.3逻辑综合的拓扑技术( Topographical Technology)…………162第八章可测试性设计…1748.1生产测试简介…………1748.2可测试性设计鲁D曹吾音·非·自·········着4鲁4鲁是1768.2.1物理瑕疵和故障模型1768.2.2D算法( D algorithm)1788.3测试协议( Test protocol)1858.4测试的设计规则·●鲁q鲁·音鲁鲁D鲁香曹音音音·自自··。·非鲁曲··●1908.4.1可测试性设计中的时钟信号1908.4.2三态总线和双向端口的测试。非……………………198录8.5门级网表可测试问题的自动修正2048.6扫描链的插入2088.7可测试设计的输出和流程2228.8自适应性扫描压缩技术………225第九章低功耗设计和分析2299.1工艺库的功耗模型…………2319.2功耗的分析…鲁鲁鲁……………2379.3低功耗电路的设计和优化2519.3.1门控时钟电路25293.2操作数分离………2619.3.3门级电路的功耗优化●·4·■D鲁曹春击自由2669.3.4多个供电电压( Multi-VDD)…2749.3.5电源门控………276参考文献……………………281第一章集应电路设计概记集成电路( Integrated Circuits)是现代电子设备的重要组成部分。因此,成功设计集成电路对整个电子信息技术产业的发展起到重要的作用。由于科技的发展,半导体芯片的集成化程度越来越高,设计的系统越来越复杂,规模越来越大,设计的性能越来越髙,功耗也越来越大,这些不断地给芯片设计工程师和电子设计自动化( Electronics Design Automation,简称EDA)厂商提出新的课题和挑战。1.1摩尔定律摩尔提出著名的“摩尔定律”已经40多年了。1965年4月,摩尔在《电子学( Electronics)》杂志上发表文章预言,半导体芯片上集成的晶体管数量将每年翻一番。1975年,他又提出修正说,芯片上集成的晶体管数量将每两年翻一番。晶体管数量MOORES LAWIntels Tanuma 2 Processo1000000000ante△nmtele Pentium Pr100000000Intels Pentium m Processoitels Pentium Pro10000000Intelstuma Printels*v Proces1000000Intel388 pre28610000080801000080084004●100019701975198019851990199520002005年度图1.1.1图1.1.1为在过去25年, ntel CPu中晶体管增长的情况。集成电路的规模不断地稳
- 2021-05-06下载
- 积分:1