Moving block sequence and organizational evolutionary algorithm for general floorplanning with arbirtrarily shaped rectilinear blocks

Liu, J., Zhong, W., Jiao, L. and Li, X. (2008) Moving block sequence and organizational evolutionary algorithm for general floorplanning with arbirtrarily shaped rectilinear blocks. IEEE Transactions On Evolutionary Computation, 12 5: 630-646. doi:10.1109/TEVC.2008.920679

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Liu, J.
Zhong, W.
Jiao, L.
Li, X.
Title Moving block sequence and organizational evolutionary algorithm for general floorplanning with arbirtrarily shaped rectilinear blocks
Journal name IEEE Transactions On Evolutionary Computation   Check publisher's open access policy
ISSN 1089-778X
1941-0026
Publication date 2008-10
Sub-type Article (original research)
DOI 10.1109/TEVC.2008.920679
Volume 12
Issue 5
Start page 630
End page 646
Total pages 17
Editor D. B. Fogel
X. Yao
Place of publication Piscataway, NJ, United States
Publisher IEEE
Collection year 2009
Language eng
Subject C1
080108 Neural, Evolutionary and Fuzzy Computation
890202 Application Tools and System Utilities
Abstract A new nonslicing floorplan representation, the moving block sequence (MBS), is proposed in this paper. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game, Tetrisreg. Since no extra constraints are exerted on solution spaces, the MBS is not only useful for evolutionary algorithms, but also for dealing with rectangular, convex rectilinear, and concave rectilinear blocks, similarly and simultaneously, without partitioning rectilinear blocks into subblocks. This is owed to a special structure designed for recording the information of both convex and concave rectilinear blocks in a uniform form. Theoretical analyses show that the computational cost of transforming an MBS to a floorplan with rectangular blocks, in terms of the number of blocks, is between linear and quadratic. Furthermore, as a follow-up of our previous works, a new organizational evolutionary algorithm (OEA) based on the MBS (MBS-OEA) is proposed. With the intrinsic properties of the MBS in mind, three new evolutionary operators are designed in the MBS-OEA. To test the performance of the MBS-OEA, benchmarks with hard rectangular, soft rectangular, and hard rectilinear blocks are used. The number of blocks in these benchmarks varies from 9 to 300. Also, the MBS-OEA and several well-designed existing algorithms are compared. The results show that the MBS-OEA can find high quality solutions for various problems. Additionally, the MBS-OEA shows a good performance in solving the problems with 300 hard rectangular blocks, 100 soft rectangular blocks, and 100 hybrid blocks, including both soft rectangular and hard rectilinear blocks. This illustrates that the MBS-OEA is not only suitable for solving a wide range of problems, but also competent for solving large-scale problems. Finally, a set of specific experiments is designed to identify the key component that is mainly responsible for the good performance of the MBS-OEA.
Keyword Evolutionary algorithms
Floorplanning
Moving block sequence
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status Non-UQ

 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 14 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 25 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 16 Apr 2009, 19:42:43 EST by Donna Clark on behalf of School of Information Technol and Elec Engineering