【摘 要】
：
二维矩形条装箱问题（Two-dimensional strip packing problem,简称2DSPP）是一个NP难的组合优化问题,它在现实世界的许多领域都有应用,比如在货物的装载、内存的管理、玻璃的切割加工等有实际需求。目前,求解2DSPP的启发式算法是以改进初始解的改进启发式算法为主。这类算法中,能有效扩大搜素范围的启发式算法不仅能够改进解的质量,同时也能提高求解的效率。膜计算是受生物
论文部分内容阅读
二维矩形条装箱问题（Two-dimensional strip packing problem,简称2DSPP）是一个NP难的组合优化问题,它在现实世界的许多领域都有应用,比如在货物的装载、内存的管理、玻璃的切割加工等有实际需求。目前,求解2DSPP的启发式算法是以改进初始解的改进启发式算法为主。这类算法中,能有效扩大搜素范围的启发式算法不仅能够改进解的质量,同时也能提高求解的效率。膜计算是受生物细胞内物质生化反应的启发而抽象出的计算模型。膜进化算法（Membrane Evolutionary Algorithm,简称MEA）是基于膜计算模型与进化计算思想提出的一种进化计算框架,已经被应用于多个NP难问题的求解并获得了较好的效果。本文研究了影响2DSPP解质量与求解效率的主要因素,为有效扩大求解过程中的搜素范围提出了矩形选择的新策略和改进的启发式算法,并进一步设计了更有效的膜进化算法。本文的主要研究工作包括:（1）提出了角增量多级评分策略和两步选择策略使矩形的选择更合理,提出了分层构造策略来改进构造性启发式算法以找到更好的解。（2）提出了一个求解2DSPP的两步选择和多级评分算法（TwoStepselection and Multi-level Scoring Algorithm,简称TSMSA）。为了增加寻优搜索范围和防止算法陷入局部最优,TSMSA中使用了局部搜索和模拟退火算法。在2DSPP的基准零浪费和非零浪费数据集上的实验表明,TSMSA能提升大部分实例的解质量。（3）为了进一步提高解的质量,本文结合膜计算的思想,提出了一种基于膜进化算法框架求解二维矩形条装箱问题的膜进化算法（Membrane Evolutionary Algorithm for Two-Dimensional Strip Packing Problem,简称MEA2DSPP）。在该算法中,首先设计了MEA2DSPP的膜结构及其初始膜对象,然后设计了4个进化算子来对膜和膜内的对象进行进化。通过与TSMSA在零浪费和非零浪费数据集上实验结果的比较,在6个数据集上MEA2DSPP的结果更好。本文的研究成果为解决2DSPP提供了一个新的思路,验证了膜进化算法在求解2DSPP上具有可行性和有效性,也为膜进化算法解决其它NP难问题提供了参考。
其他文献
随着公众对饮食健康要求的不断提高,对淡水鱼类食用方面的要求也由数量转为质量,人们更倾向于购买肉质鲜美且营养价值高的生态鱼。目前,对于生态鱼的分级主要依靠人工作业,劳动强度大、效率较低,而且会对鱼造成不同程度的损伤,影响生态鱼的经济价值。由于生态鱼的健康、生态、绿色等优势特征是隐性的,难以通过外观、肉眼识别,故在市场上容易存在水库生态鱼和饲料养殖鱼混卖的现象,消费者花费较高价钱买回来却是低价的饲料养
2021年,中国电子信息制造业实现营业收入141285亿元,实现利润总额8283亿元,利润率为5.86%,其中由于质量缺陷造成的低利润率、生产成本浪费尤为严重,因此提高质量、降低生产成本变得愈发迫切。表面贴装技术（Surface Mount Technology,SMT）目前广泛应用于电子信息制造行业,通过从SMT工艺数据中挖掘有价值的信息,来提高对于SMT质量缺陷的成因、质量级别、缺陷种类的分析
随着生产力的快速发展,机械设备的数量与日俱增。滚动轴承是各种机械设备最为核心的部件之一,其具有应用范围广、使用频率高、运行时间长和运行环境复杂等特点。在规模效应的作用下,滚动轴承发生故障的概率大大增加,发生故障时产生的影响也更加巨大。因此对滚轴轴承进行高效准确的故障诊断,是机械设备系统安全稳定运行的重要保障。本文针对现有的恒工况和变工况滚动轴承故障诊断方法的缺陷,从深度学习恒工况诊断和迁移学习变工
随着信息化的快速发展,量子计算理论和实验的进展对基于计算复杂性假设的经典密码协议提出了挑战。因此,安全性基于物理学定律的量子密码协议受到了越来越多的关注。其中,量子密钥分发协议经过充足的实验发展,已经在实践中被用于保护信息安全。除量子密钥分发协议以外,基于量子密钥分发的量子保密查询是另一种具有实用潜力的协议,此类协议是量子密码学的重要内容,是解决对称保密信息获取问题的量子方案,但是缺乏实际的安全性
本文主要探究深度学习目标检测算法在缺陷检测方向的应用,研究内容分为两部分,分为桥梁病害检测和摄像模组脏污检测。在桥梁病害检测方面,桥梁在世界的发展历史悠久,已成为了人民生活的重要组成部分。在桥梁运行过程中难免会出现各种病害等,所以对桥梁可能出现的病害进行检测是一项非常重要的任务。传统的人工桥梁病害检测方法专业性强、检测成本高、准确度不够,因此,利用机器视觉技术开发一种稳定高效的桥梁病害检测方法迫在
坩埚下降法又称布里奇曼晶体生长法,是一种常用的晶体生长方法。这种方法常用于制备碱金属和碱土金属卤化物和氟化物单晶。由于可以把原料密封在坩埚里,减少了挥发造成的泄漏和污染,使晶体的成分容易控制;操作简单,可以生长大尺寸的晶体。可生长的晶体品种也很多,且易实现程序化生长。但是在晶体生长过程中难于直接观察。难以建立晶体缺陷产生与演变规律,不能控制晶体缺陷的形成。其根本原因在于无法实时获取晶体生长的固-液
数字图像作为一种信息载体,具有直观性、灵活性强等特点,被广泛应用在网络通信等领域。但数字图像容易被非法复制和传播,这给军事、医疗等敏感场景下的数据传输与存储带来较大的安全隐患,所以维护数字图像的安全尤为重要。密文图像信息隐藏是以密文图像为载体的信息隐藏技术,同时做到了载体图像内容保护和秘密信息嵌入,具有广泛的应用前景。但目前密文图像信息隐藏算法通常难以平衡嵌入容量和载体图像的恢复质量,实现较好的综
交通流量预测是缓解交通拥堵的方法之一,而交通流量受到多种因素的影响,使得准确预测交通流量具有非常大的挑战性。目前大多数的交通流量预测方法使用图卷积网络和长短期记忆网络等不同的组件分别获取交通流量的时间相关性和空间相关性。最近出现了只用时空图图卷积来同步处理时空相关性的交通流量预测模型,它们通过构建局部时空图来学习交通流量数据的时空相关性。但是这些模型存在以下问题:第一,这些模型仅使用连续时刻的流量
磁耦合无线电能传输（Wireless Power Transfer,WPT）系统通过电磁场或电磁波载能/传能原理,结合谐振技术可以在一个较远的距离内为用电设备无线供电,具有安全无接触的优点,耦合机构是WPT的关键。然而,耦合机构的传能性能对于能量接收（拾取）机构的位置姿态都较为敏感,偏差较大时就会导致输出功率大幅下降。对于一些需要在空间中移动或转动的用电设备的无线供电,传统的耦合机构模式对能量传输
流量仪表标定装置是计量部门和仪器生产厂商进行检定测试的重要设备。在多批量、高精度的标定场景下,任何设备老化及零部件的微小改变都有可能影响标定精度。因此,实现标定装置运行状态的实时监测、健康程度的快速评估,对提升标定装置稳定性、可靠性、企业生产效率及产品质量有重要意义。本文对某仪表公司的液体流量仪表标定装置进行调研分析,针对运行状态监测不全面、设备健康程度掌握不及时等问题,展开了对流量仪表标定装置监