遗传模拟退火融合算法求解工程二维排样问题  

Combination genetic simulated annealing algorithms for solving two-dimensional packing problem

作　　者：李敬花[1] 樊付见[1] 王昊[1] 余锋[1] 

机构地区：[1]哈尔滨工程大学船舶工程学院,黑龙江哈尔滨150001

出　　处：《计算机集成制造系统》2011年第9期1962-1967,共6页Computer Integrated Manufacturing Systems

基　　金：中央高校基本科研业务费专项资金资助项目;哈尔滨工程大学基础科研资助项目(002010260723)~~

摘　　要：为探索更高效的工程二维排样优化方法,给出了基于遗传模拟退火融合算法的工程二维排样优化方法。首先,建立以板材利用率为主优化目标的问题模型,并采用基于一定包络准则的凸多边形包络法对不规则形状进行近似处理;在此基础上,设计模型求解的遗传模拟退火融合算法,该算法结合遗传算法的快速全局搜索能力和模拟退火算法较强的局部搜索能力,以遗传算法做外层循环,以模拟退火做内层循环,通过模拟退火较强的局部搜索能力,改善外循环遗传算法的早熟现象,从而避免搜索过程陷入局部最优。最后,通过具体算例验证了该算法求解二维排样问题的可行性和有效性。To explore more efficient methods for two-dimensional（2D） packing optimization in engineering field,2D engineering packing optimization method based on Genetic Simulated Annealing Algorithms（GSAA） was proposed.Firstly,a mathematical model was constructed with plate utilization as optimization objective,and a convex polygons envelope method based on certain envelope criterion was used to conduct approximate processing of irregular shapes.On this basis,GSAA to solve this model was designed.This algorithm integrated the rapid global search capability of genetic algorithm with the strong local search capability of simulated annealing algorithm,moreover,genetic algorithm was used as outer loop and the simulated annealing algorithm was used as inner loop.By using strong local search capability of simulated annealing algorithm,the premature convergence of genetic algorithm was improved to avoid local optimum of searching process.Specific example was given to verified the feasibility and effectiveness of this algorithm to solving 2D packing problem.

关 键 词：二维排样优化 不规则形状 遗传算法 模拟退火算法 早熟现象 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]