求解矩形件优化排样的自适应模拟退火遗传算法

作者：蒋兴波; 吕肖庆; 刘成城

来源：计算机辅助设计与图形学学报, 2008, (11): 1425-1431.

• 自适应模拟退火遗传算法
• 模拟退火算法
• 自适应遗传算法
• 形件优化排样
• 启发式布局算法 adaptive simulated annealing genetic algorithm
• simulated annealing algorithm
• adaptive genetic algorithm
• optimal packing of rectangles
• heuristic layout algorithm

矩形件优化排样是一个NPC问题,在工业界有着广泛的应用.针对该问题,提出一种自适应模拟退火遗传算法.采用一种基于环形交叉算子和环形变异算子的自适应遗传算法来自动调整交叉和变异概率;同时引入模拟退火算法对个体适应度大于平均适应度的个体进行退火处理.自适应模拟退火遗传算法充分发挥了自适应遗传算法与模拟退火算法各自的全局搜索能力与局部搜索能力.对比实验表明,该算法结合改进的最左最下布局算法解决矩形件优化排样问题更加有效.

• 单位
  北京大学; 中国人民解放军第二军医大学; 北京大学王选计算机研究所