求解矩形条带装箱问题的动态匹配启发式算法

矩形条带装箱问(RSPP)是指将一组矩形装入在一个宽度固定高度不限的矩形容器中,以期获得最小装箱高度.RSPP理论上属于NP难问题,在新闻组版、布料下料以及金属切割等工业领域中有着广泛的应用.为解决该问题,采用了一种混合算法,即将一种新的启发式算法--动态匹配算法--与遗传算法结合起来.混合算法中,动态匹配算法能根据4类启发式规则动态选择与装填区域相匹配的下一个待装矩形,同时将装箱后所需容器高度用遗传算法的进化策略进行优化.时2组标准测试问题的计算结果表明,相对于文献中的已有算法,提出的算法更加有效.     

求解单容器矩形装箱问题的混合算法

单容器矩形装箱问题是一个典型的组合优化问题,其在工业界有着广泛的应用。首先提出了一种新的启发式布局算法,即底部匹配算法,该算法在矩形的装入过程中根据五种启发式规则自动选择与装填区域相匹配的下一个矩形。然后将底部匹配算法与遗传算法相结合形成混合算法来求解单容器矩形装箱问题。实验结果表明,与已有算法相比,该文提出的算法更加有效。     

基于宽容分层策略的启发式排样算法

针对2D Packing排样方法中存在的择优匹配思想与排样优劣评估的平衡性问题,基于多目标优化的宽容分层策略提出一种新颖有效的择优匹配启发式排样算法。首先,定义排样空间和匹配值,计算入排零件与排样空间的宽、高匹配值,然后建立统一的多目标优化函数模型,并根据目标函数值的大小来确定排放优先规则。特别针对一般可排入匹配情况,可在目标函数模型中通过设置和调整宽容值,最后实现多种排样布局的最优化。对benchmark问题的7类数据实例的计算结果表明,该算法相对于底部左齐择优匹配（LLABF）和水平线择优匹配（LSBF）算法,Gap的平均值可降低了2%;在C1P1+C3P1以及C2~C7随机构成的两组混合数据测试中（矩形数量为33和66）,排样高度达到24和339。该算法也可用于多类型异形零件的排样过程。     

网络集群计算系统中的并行任务调度

基于多处理机并行任务调度模型，探讨网络集群计算系统中的并行任务调度问题，首先证明了一般网络集群计算系统中调度算法的可近似性难度，然后提出了三种不同的启发式算法：最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法；然后根据大量的模拟实验对这些算法以及文献中已提出的调度算法进行了比较分析，结果表明该文的启发式算法比文献中的算法在性能上效果更好。     

矩形件优化排样的一种启发式算法

对大规模矩形件正交排样问题,提出了一种快速高效的启发式排放算法。对当前的可排放位置（水平线）,用贪婪算法从未排矩形件中选择可排放于该水平线的最优矩形件组合块;根据各个排放位置与其对应的矩形件组合块的匹配程度,选择最优的可排放位置（最优水平线）优先排放。在排放时,为了便于后续排放,先将待排放位置对应的矩形件组合块从低到高进行排序,再排放。对E.Hopper提供的规模最大的一类实例进行计算,排样率都在99%以上,平均排样率达到了99.38%,平均计算时间只用了1.12秒。与相关文献最好结果进行了比较,结果表明该文算法解决大规模的矩形件排样具有高效性。     

蚁群算法求解复杂集装箱装载问题

针对复杂集装箱装载问题(CLP),应用启发式信息与蚁群算法求解了最优装载方案。首先,建立了复杂集装箱装载问题的数学模型,利用蚁群算法对解空间的强搜索能力、潜在并行性及可扩充性,结合三空间分解策略将布局空间依次分割;然后,装入满足约束条件的最优货物块,完成不同大小三维矩形货物的装载布局。在此基础上,设计了基于空间划分策略的蚁群算法。最后以700件货物装入40尺(12.025m)高柜箱进行计算,结果表明该方法能提高集装箱的空间利用率,同时兼顾了多个装载约束条件,可应用性好。     

一种改进的VLSI电路有效布局算法

采用重心矩形约束[1]进行VLSI布局会出现以下问题:(1)布局边界的浪费,出现不可利用的小区域;(2)放置模块时可能会出现模块放置在实际有效区域内却因为重心约束成为非法放置。为了解决该问题,提出了一种改进文献[1]的VLSI布局启发式算法:通过设计模块的优先顺序进行合理布局,并辅助于边界矩形来解决重心矩形约束出现的问题;对模块布局放置的多个可能位置进行比较,并将其放置在优先度最高的适当区域。用Banchmark(ami33,ami49)和文献[1]的数据进行测试,结果表明新算法:(1)算法简洁高效,运行时间短;(2)布局结果明显好于文献[1]。     

N皇后问题的启发式算法探讨

搜索策略的选择与设计是人工智能领域问题求解的核心问题之一,直接影响到问题求解过程中存储空间的占用和计算的复杂性,影响到问题求解的效率。在给出N皇后问题形式化描述和现有搜索算法的基础上,设计了3种解决N皇后问题的启发式算法,并将其与深度优先和宽度优先等搜索策略进行了分析和比较,得出了几点关于设计启发式算法的启示。     

求解闭环布局问题的混合编码阈值接收算法

闭环布局问题本质上是一个混合优化问题。根据问题的特点,本文设计了一种基于混合编码的阈值接收(Mixed-coding Threshold Accepting, MTA)算法来求解该问题。MTA算法将矩形环的宽度和高度作为解编码的一部分,使算法能够同时搜索设施的最优放置顺序和矩形环的大小。为了评估MTA算法的性能,利用文献中普遍使用的13个测试实例进行了实验。结果表明,MTA算法在9个测试实例上找到了新的最优布局方案,性能明显优于现有的元启发式算法。     

用MFC动态编程实现8数码问题求解

介绍了深度优先算法、宽度优先算法、启发式搜索算法3种方法实现8数码问题,分析了3种算法的可采纳性系统的特点,并用MFC编程实现.     

圆形件卷材排样问题的一种定序定位算法

圆形件卷材排样问题是指将一组不同半径的圆形件互不重叠的排放在宽度指定的 卷材上,使得占据的卷材长度最小。针对该问题提出一种定序定位启发式优化算法。设计基于 最大穴度的定位算法,对于每个特定排样序列,计算待排样圆形件在当前布局的所有可行放置 位置的穴度,选择穴度最高的一个位置放置圆形件;更新当前布局,继续排放剩余圆形件,直 到所有圆形件均排放进卷材为止。采用遗传算法对排样序列进行遗传进化得到多种不同的排样 方案,选择耗费卷材长度最小的一种排样方案作为最终解。实验结果表明,本文算法排样方案 耗费卷材长度较小,且算法计算时间相对合理。     

Heuristics for two-dimensional strip packing problem with 90° rotations

This paper proposes a deterministic heuristic algorithm (DHA) for two-dimensional strip packing problem where 90° rotations of pieces are allowed and there is no guillotine packing constraint. The objective is to place all pieces without overlapping into a strip of given width so as to minimize the total height of the pieces. Based on the definition of action space, a new sorting rule for candidate placements is proposed such that the position for the current piece is as low as possible, the distance between the current piece and other inside pieces is as close as possible, and the adverse impact for further placements is as little as possible. Experiments on four groups of benchmarks showed the proposed DHA achieved highly competitive results in comparison with the state-of-the-art algorithms in the literature. Also, as a deterministic algorithm, the DHA could achieve high quality solutions by only one independent run on both small-scale and large-scale problem instances and the results are repeatable.     

求解不等圆Packing问题的一个启发式算法

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.     

单规格一刀切矩形排样问题的启发式搜索算法

针对单规格一刀切二维矩形排样问题,提出了一种启发式搜索算法,称为大小工件分治择优匹配(bigitem smallitem divide-and-conquer best-fit,简称BSDBF)启发式算法.该算法基于组化规则,提出了大小工件分治策略和组块快速举荐算法,是对组化策略的关键补充,这对优解获得至关重要.然后,择优选择适应度高的组块进行递归排样,贪心获得各块板材的排样方案.最后,基于设计的工件拆分方法,对初始解进行后处理小规模重排,进一步提升解的质量.因为没有随机因素,其获得的优解可复现,也是BSDBF算法区别于其他算法的典型特征.大量Benchmark案例的实验结果表明,BSDBF算法求解质量优于其他算法报道结果.     

数字微流控生物芯片布局的拟人遗传组合算法

数字微流控生物芯片布局问题是芯片设计的关键问题,它是在二维微流控阵列上为每个操作布局一个合适的物理位置,以达到完成所有操作的微流控阵列总面积最小和总时间最短两个目标。构建了拟人遗传组合算法,应用拟人启发式算法来控制数字微流控模块的布局过程,用遗传算法对布局结果进行多目标优化,以多元体液检测为实例,模拟了数字微流控生物芯片的布局优化过程。实验结果表明该算法不仅达到了优化目标,且优于并行混合模拟退火算法。     

求解二维正交矩形布局问题的动态填空启发式算法

为更高效解决二维正交矩形布局问题,建立该问题的数学模型,改进BL算法规则;为寻找布局过程中的空余平面,建立了新颖的图形矩阵化理论。最后提出一种动态填空（DFB）启发式算法,制定了四条动态调整机制,结合遗传算法对该问题进行求解。大量算例测试显示：DFB算法可达到100%的平面利用率,极大提高了BL算法的效率,并且可以适用于大规模布局问题。     

用于求解二维圆形排样问题的自适应混合算法

针对二维圆形版面不等圆排样问题,在最小局部距离定位布局策略的基础上,引入紧凑度和适应度,提出基于拟矩形排样的自适应启发式算法,并与以自然数编码的遗传算法相结合构建混合算法。该混合算法发挥两者的全局搜索能力与局部寻优能力。在标准测试算例上,与一些经典算法进行比较,结果表明,该算法能够在更短的时间内获得更为满意的结果。     

云计算中能耗和性能感知的虚拟机优化部署算法

优化虚拟机部署是数据中心降低能耗的一个重要方法。目前大多数虚拟机部署算法都明显地降低了能耗,但过度虚拟机整合和迁移引起了系统性能较大的退化。针对该问题,首先构建虚拟机优化部署模型。然后提出一种二阶段迭代启发式算法来求解该模型,第一阶段是基于首次适应下降装箱算法,提出一种虚拟机优化部署算法,目标是最小化主机数;第二阶段是提出了一种虚拟机在线迁移选择算法,目标是最小化待迁移虚拟机数。实验结果表明,该算法能够有效地降低能耗,具有较低的服务等级协定(SLA)违背率和较好的时间性能。     

基于遗传模拟退火算法的不规则多边形排样

将遗传授拟退火算法应用于计算机辅助排样领域，设计了一种基于遗传模拟退火技术的启发式排样算法．该算法能够处理不规则多边形的排样问题；同时，给出一种对象的几何表达方式，可以忽略高度不规则形状带来的复杂性影响．该算法通过基于遗传模拟退火算法的全局优化概率搜索，寻找排样件在排样时的最优次序及各自的旋转角度，然后采用基于左下角(BL)策略的启发式排样算法实现自动排样．