Effectiveness of an evolutionary algorithm for the multi‐objective rectangular packing problem
Effectiveness of an evolutionary algorithm for the multi‐objective rectangular packing problem
复制标题
DOI：
10.1002/ecjb.20427
复制
发表时间：
2007-12
期刊：
影响因子：
--
通讯作者：
Shinya Watanabe;T. Hiroyasu;M. Miki
中科院分区：
文献类型：
--
作者：
Shinya Watanabe;T. Hiroyasu;M. Miki
研究了矩形装箱问题，并研究了邻域培养遗传算法（NCGA）的有效性。本文提出的NCGA是一种新的遗传算法，它将多目标遗传算法中特有的邻域交叉机制与有效的搜索机制相结合。所提出的方法在典型的测试问题的有效性已经在过去的研究中取得了令人满意的结果。另一方面，矩形布局问题被应用于布局规划，例如大规模集成电路中的芯片面积最小化。这是一类离散的组合问题，已知搜索困难，需要很长时间才能得到解。本文将矩形布局问题描述为一个多目标问题，以布局的纵横长度为目标。序列对被用作块放置表示，并且PPEX被用作交叉过程。使用这些过程，NCGA的有效性进行了研究。为了比较，其他三种方法-NSGA-II，SPEA 2，和非NCGA（NCGA没有邻域交叉）-进行了研究。© 2007 Wiley Periodicals，Inc. Electron Comm Jpn Pt 2，90（12）：111-120，2007;在线发表于Wiley InterScience（www.interscience.wiley.com）。DOI 10.1002/ecjb.20427
This paper considers the rectangular packing problem and investigates the effectiveness of the neighborhood cultivation genetic algorithm (NCGA). NCGA, which we proposed, is a new algorithm in which the unique mechanism of neighborhood crossover is combined with effective mechanisms for search in multi-objective GA proposed in the past. The effectiveness of the proposed method in typical test problems has already been investigated with satisfactory results in past studies. The rectangular packing problem, on the other hand, is applied to floor planning, such as chip area minimization in large-scale integrated circuits. It is a kind of discrete combinatorial problem in which it is known that the search is difficult and a very long time is required until the solution is obtained. This paper formulates the rectangular packing problem as a multi-objective problem with the vertical and horizontal lengths of the placement configuration as the objectives. The sequence-pair is used as the block placement representation, and PPEX is used as the crossover procedure. Using these processes, the effectiveness of NCGA is investigated. For comparison, three other methods—NSGA-II, SPEA2, and non-NCGA (NCGA without neighborhood crossover)—are investigated. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 90(12): 111–120, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20427