二维不规则形状物体的自动最优布局是属于NP完全的组合优化问题，使用传统的方法 很难得到满意解答.文章针对该问题提出了一个基于进化计算的算法，并以服装计算机辅助设计为例表明基于进化计算的算法卓有成效地应用到自动布局问题.为了得到关于问题的自然和有效的编码，将问题变换为一种与之等价的关于多边形的运动规划问题，根据问题的特性设计了算法的3个重要算子.在解的解码和评价过程中则综合地利用了已有的最优算法.%The two-dimensional object layout problem, i. e. layout two-dimensional polygonal pieces of some material inside a rectangular sheet of stock material of fixed width and minimum length, has been proved to be an NP complete combin atorial optimization problem, and it is hard to obtain a satisfying solution by traditional methods.In this paper, an Evolutionary Comp utation (EC) based algorithm about this problem is proposed and implemented, and also applied to an apparel CAD system,showing that it is very good at sol ving layout problem. In order to encode the problem's candidate soluti ons, the problem is transformed into its equivalent form about polygon motion planning.The algorithm adopts current optimal algorithms about polygon motion planning in decoding and evaluating candidate solutions.
展开▼
