二维不规则图形排样问题的一种混合求解算法

针对二维不规则图形排样问题,实现了一种基于启发式定位策略与自适应遗传算法的混合排样算法(AGAHA)。首先,考虑到单一指标的放置策略容易陷入局部最优的问题,提出了一种基于临界多边形(NFP)的混合放置策略,综合考虑排样效果的整体紧密度和局部紧密度。之后,为了提高搜索最优解的效率,在优化图形的顺序时使用了自适应遗传算法,在标准遗传算法的基础上,根据种群适应度的变化,自适应地改变交叉与变异概率。最后,利用文献中的标准测试案例和实际生产中的案例分别进行测试,结果表明:AGAHA算法在多数案例上较普通遗传算法结合BL算法更优,并且在实际案例中也取得了优于人工排样的结果。