基于遗传算法的最优布局问题求解

摘要

二维不规则形状物体的自动最优布局问题是一个在许多生产实践如VLSI制造、造船、金属切割和纺织等中有关键应用的重要问题,也是一个计算机科学和运筹学中的基本问题,但使用传统的方法很难得到满意解答.针对该问题,提出了一个基于遗传算法的求解方法,并将它应用到服装计算机辅助设计中去.给出了此问题的形式化描述,并将问题归约为一种关于多边形运动规划的等价形式.根据问题的特性设计了算法的3个重要算子,在解的解码和评价过程中则充分利用了已有的关于多边形运动规划的最优算法.实验结果表明所提出的方法能较好地解决最优布局问题.