高级检索

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

    AN OPTIMIZATION LAYOUT SOLUTION BASED ON GENETIC ALGORITHM

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

       

      Abstract: The optimization of two-dimensional irregular object layout is a basic problem in computer science and operational research, and has found key applications in many industries, such as VLSI manufacturing, ship-building, sheet metal and clothing, etc. But the current results from traditional methods do not satisfy real applications. In this paper, a genetic algorithm about this problem is proposed and implemented, and then applied to an apparel CAD system. Firstly a formal description of the problem is proposed, and then the problem is transformed into one kind of equivalent form about polygon motion planning. Three genetic operators are also designed according to characteristics of the problem, and the algorithm adopts current optimal algorithms about polygon motion planning in decoding and evaluating candidate solutions. Experimental result shows that the proposed algorithm is good at solving the layout problem.

       

    /

    返回文章
    返回