Moving Block Sequence and Organizational Evolutionary Algorithm for General Floorplanning with Arbitrarily Shaped Rectilinear Blocks Jing Liu',Member;IEEE Weicai Zhong',Member;IEEE Licheng Jiao,Senior Member,IEEE, Xue Li2,Member IEEE Institute of Intelligent Information Processing,Xidian University,Xi'an 710071,China 2School of Information Technology and Electrical Engineering,The University of Queensland,Brisbane, Qld 4072,Australia E-mail:neouma@163.com 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,Tetris Because 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 sub-blocks.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 to1 Moving Block Sequence and Organizational Evolutionary Algorithm for General Floorplanning with Arbitrarily Shaped Rectilinear Blocks Jing Liu1 , Member, IEEE Weicai Zhong1 , Member, IEEE Licheng Jiao1 , Senior Member, IEEE, Xue Li2 , Member IEEE 1 Institute of Intelligent Information Processing, Xidian University, Xi’an 710071, China 2 School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, Qld 4072, Australia E-mail: neouma@163.com 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, Tetris®. Because 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 sub-blocks. 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