求解三维装箱问题的混合模拟退火算法

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.     

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

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

基于禁忌搜索的启发式算法求解球体Packing问题*

为求解具有NP难度的球体Packing问题,通过将禁忌搜索方法与基于自适应步长的梯度下降法和二分法相结合,提出了一个启发式算法。对50个等球算例进行了实例测试,算法改进了其中44个算例的目前最优结果。大量的实例计算结果表明,该启发式算法是求解球体Packing问题的一个有效算法。     

An efficient heuristic algorithm for arbitrary shaped rectilinear block packing problem

Arbitrary shaped rectilinear block packing problem is a problem of packing a series of rectilinear blocks into a larger rectangular container, where arbitrary shaped rectilinear block is a polygonal block whose interior angle is either 90° or 270°. This problem involves many industrial applications, such as VLSI design, timber cutting, textile industry and layout of newspaper. Many algorithms based on different strategies have been presented to solve it. In this paper, we proposed an efficient heuristic algorithm which is based on principles of corner-occupying action and caving degree describing the quality of packing action. The proposed algorithm is tested on six instances from literatures and the results are rather satisfying. The computational results demonstrate that the proposed algorithm is rather efficient for solving the arbitrary shaped rectilinear block packing problem.     

正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.     

基于改进最低水平线方法与遗传算法的矩形件排样优化算法

传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造 成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理, 提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采用分阶段设置遗传 算子的方法,改善算法的搜索性能与效果。通过改进最低水平线方法与基于分阶段遗传算子的 遗传算法相结合,共同求解矩形件排样问题。排样测试数据表明,所提出的矩形件排样优化算 法能够有效改善排样效果,提高材料利用率。     

带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.     

求解2D条带矩形Packing问题的迭代启发式算法

为求解二维矩形条带装箱问题,提出了一种新颖而有效的启发式算法.算法主要包括矩形装载适应度的计算规则和树型迭代搜索规则,通过选择最高适应度的矩形来装载空间.对大量国际上公认的Benchmark问题实例的计算结果表明,相对于当前的很多著名算法,提出的算法更加有效.     

A framework for learning in search-based systems

We provide an overall framework for learning in search based systems that are used to find optimum solutions to problems. This framework assumes that prior knowledge is available in the form of one or more heuristic functions (or features) of the problem domain. An appropriate clustering strategy is used to partition the state space into a number of classes based on the available features. The number of classes formed will depend on the resource constraints of the system. In the training phase, example problems are run using a standard admissible search algorithm. In this phase, heuristic information corresponding to each class is learned. This new information can be used in the problem solving phase by appropriate search algorithms so that subsequent problem instances can be solved more efficiently. In this framework, we also show that heuristic information of forms other than the conventional single valued underestimate value can be used, since we maintain the heuristic of each class explicitly. We show some novel search algorithms that can work with some such forms. Experimental results have been provided for some domains     

New heuristics for one-dimensional bin-packing

Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimal bin slack (MBS) heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic. The most effective algorithm turned out to be one based on running one of the former to provide an initial solution for the latter. When tested on 1370 benchmark test problem instances from two sources, this last hybrid algorithm proved capable of achieving the optimal solution for 1329, and could find for 4 instances solutions better than the best known. This is remarkable performance when set against other methods, both heuristic and optimum seeking.Scope and purposePacking items into boxes or bins is a task that occurs frequently in distribution and production. A large variety of different packing problems can be distinguished, depending on the size and shape of the items, as well as on the form and capacity of the bins (H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution: a Typology and Bibliography, Springer, Berlin, 1992). Similar problems occur in minimising material wastage while cutting pieces into particular smaller ones and in the scheduling of identical processors in order to minimise total completion time. This work addresses the basic packing problem, known as the one-dimensional bin packing problem, where it is required to pack a number of items into the smallest possible number of bins of pre-specified equal capacity. Even though this problem is simple to state, it is NP hard, i.e., it is unlikely that there exists an algorithm that could solve every instance of it in polynomial time. Solution of more general realistic packing problems is probably contingent upon the availability of effective and computationally efficient solution procedures for the basic problem. In this work we present several heuristics capable of doing that. Extensive computational testing attests to the power of these heuristics, as well as to their computational efficiency.     

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

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

柔性作业车间调度问题的一种启发式算法

为了研究多目标柔性作业车间调度问题,基于甘特图和搭积木经验进行了分析,提出了一种组合优先规则和基于此优先规则的启发式算法.组合优先规则面向完工时间、关键机床负荷和总负荷三个指标,改变规则中各数据项的比例可调整三个指标所占的比例;算法采用随机方式调整三个指标的比例,并微调最优解对应的比例.能随机产生多个高质量调度解.算法...     

Packing unequal circles using formulation space search

In this paper we present a heuristic algorithm for the problem of packing unequal circles in a fixed size container such as the unit circle, the unit square or a rectangle. We view the problem as being one of scaling the radii of the unequal circles so that they can all be packed into the container. Our algorithm is composed of an optimisation phase and an improvement phase. The optimisation phase is based on the formulation space search method whilst the improvement phase creates a perturbation of the current solution by swapping two circles. The instances considered in this work can be categorised into two: instances with large variations in radii and instances with small variations in radii. We consider six different containers: circle, square, rectangle, right-angled isosceles triangle, semicircle and circular quadrant. Computational results show improvements over previous work in the literature.     

二维离线非旋转装箱问题的一个混合算法

针对二维离线非旋转装箱问题,在凹角和适应值的思想的基础上,提出了一个改进型的Best-Fit启发式算法,并结合基于自然数编码的遗传算法构建了混合算法。同时在遗传迭代过程中,引入二维装箱问题的下界思想作为迭代的终止条件之一,减少了遗传算法无效迭代次数,另外根据问题自身特点,有效地降低了染色体长度,提高了整体的计算速度。在36个标准测试案例的测试基础上与一些经典的算法进行了比较,实验结果表明该算法在工业生产可接受的时间内与其他经典的算法相比能够获得更为满意的结果。     

求解矩形装箱问题的一种近似算法

提出了利用近似算法求解二维矩形装箱问题的最小高度的一种方法。该方法基于启发式递归策略和遗传算法。利用启发式递归策略把所有大小各异的矩形都装入宽度固定的矩形容器中，并计算装完后所需容器的高度，用遗传算法的进化能力优化高度，使得所需容器的高度尽可能小。计算数据证明这种方法能够得到很好的结果，特别是对数据量大的测试问题，效果更好。     

柔性作业车间调度分析及其启发式算法

针对多目标柔性作业车间调度问题,基于甘特图和搭积木经验进行了分析,提出了一种组合优先规则和基于此优先规则的启发式算法。组合优先规则面向完工时间、关键机床负荷和总负荷三个指标,改变规则中各数据项的比例可调整三个指标所占的比例。算法采用随机方式调整三个指标的比例,并微调最优解对应的比例,能随机产生多个高质量调度解。对比测试表明,算法求解质量更高,运行速度快,稳定,可直接用于在其他调度算法中产生初始解,或者用于动态调度。     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.     

A heuristic method for learning Bayesian networks using discrete particle swarm optimization

Bayesian networks are a powerful approach for representing and reasoning under conditions of uncertainty. Many researchers aim to find good algorithms for learning Bayesian networks from data. And the heuristic search algorithm is one of the most effective algorithms. Because the number of possible structures grows exponentially with the number of variables, learning the model structure from data by considering all possible structures exhaustively is infeasible. PSO (particle swarm optimization), a powerful optimal heuristic search algorithm, has been applied in various fields. Unfortunately, the classical PSO algorithm only operates in continuous and real-valued space, and the problem of Bayesian networks learning is in discrete space. In this paper, two modifications of updating rules for velocity and position are introduced and a Bayesian networks learning based on binary PSO is proposed. Experimental results show that it is more efficient because only fewer generations are needed to obtain optimal Bayesian networks structures. In the comparison, this method outperforms other heuristic methods such as GA (genetic algorithm) and classical binary PSO.     

基于布通率的FPGA装箱算法

提出一种基于FPGA布通率的装箱算法.选择连接因子最小的节点作为种子节点;采用基于布通率的启发式函数来选择最合适的逻辑单元(LE)装箱到可配置逻辑单元(CLB)内部.可以同时减少装箱后CLB之间的线网数和CLB引脚的外部使用率,从而减少布线所需的通道数.该算法和已有算法相比较,线网数和布线通道数都减少约30%. 算法的时间复杂度仍然是线性的.