Adaptive Hybriu Algorithm for Solving 2D Circle Packing Problem

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

混合算法的邻域结构变更研究及在排样问题上的应用

本文研究了全局搜索算法和局部搜索算法的混合机制,设计了基于邻域搜索和遗传算法的混合搜索算法。该算法结合了遗传算法的全局搜索特性和邻域局部贪婪搜索特性;在分析排样问题碰靠过程特征的基础上,构建了排样问题邻域假设,当邻域假设满足时,遗传算法+邻域搜索能很好发挥作用;当不能判断邻域结构是否满足邻域假设时,提出了建立遗传算法+匹配变邻域的搜索算法,该算法兼顾了组合优化中邻域搜索的局部搜索无效的情况,实现了匹配的变邻域混合算法在排样优化问题中的应用。实例结果标明,排样图形不一样,其求解难度不一样,该算法均搜索到了更好的排样模式,验证了算法的有效性。     

混合算法在排样问题上的应用研究

结合全局搜索算法和局部搜索算法的互补特性,研究设计了串行和镶嵌两种混合模式,实现了基于邻域搜索和遗传算法的混合算法;在分析排样问题中图形碰靠的相关性特征的基础上,构建了排样问题的邻域假设和匹配邻域结构,基于混合算法获得了排样问题的优化解;实例结果标明,该算法在搜索到了更好的排样模式,验证了算法的有效性。     

矩形件排样问题的遗传算法求解

本文研究了求解矩形件正交排样优化问题的遗传算法。同时，将矩形件正交排样问题转化为一个排列问题，提出了求一个排列所对应的排样图的下台阶算法（改进的ＢＬ算法）将下台阶算法与遗传算法相结合，用于矩形件排样问题的求解，给出了该算法的实现。用该算法对文献中的两个算例进行了求解，结果表明该算法获得了比ＢＬ算法更好的解，是一种较为行之有效的方法。     

矩形件排样优化的一种近似算法

本文对理论上属于ＮＰ－完备问题的二维矩形件优化排样问题，构造了一个效率高、速度快、可令人满意的一种近似算法，该算法的主要思想是在排样过程中根据一种局部最优原则不断地动态产生一些较小的矩形，然后对这些小矩形区域排样，同时也消去一些已排过的矩形区域，直至所有的矩形件被排完，根据本文算法我们开发了一个矩形件排样系统。     

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

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

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。     

遗传算法在矩形件优化排样中的应用

遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。     

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

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

基于遗传算法的不规则件优化排样研究

提出了一种基于遗传算法的不规则件优化排样的求解方法,通过剩余矩形匹配算法实现解码和局部寻优,并结合正交靠接算法实现自动排样。实例证明,该方法是有效的。     

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

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

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

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

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

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

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

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

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

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

求解矩形Packing问题的基于遗传算法的启发式速归策略

An improved heuristic recursive strategy combining with genetic algorithm is presented in this paper. Firstly, this method searches some rectangles, which have the same length or width, to form some layers without waste space, then it uses the heuristic recur sive strategies to calculate the height of the remaining packing order and uses the evolutionary capability of genetic algorithm to reduce the height. The computational results on several classes of benchmark problems have shown that the presented algorithm can compete with known evolutionary heuristics. It performs better especially for large test problems.     

求解矩形Packing问题的基于遗传算法的启发式递归策略

An improved heuristic recursive strategy combining with genetic algorithm is presented in this paper. Firstly, this method searches some rectangles, which have the same length or width, to form some layers without waste space, then it uses the heuristic recursive strategies to calculate the height of the remaining packing order and uses the evolutionary capability of genetic algorithm to reduce the height. The computational results on several classes of benchmark problems have shown that the presented algorithm can compete with known evolutionary heuristics. It performs better especially for large test problems.     

A new heuristic algorithm for the circular packing problem with equilibrium constraints

The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search is put forward for solving this problem.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search doing repeated work,the algorithm adopts the strategy of tabu search.In the pr...     

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

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