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 to
1 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
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. Index Terms-Very large scale integration,Floorplanning,Moving block sequence, Evolutionary algorithms,Organization
2 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. Index Terms⎯Very large scale integration, Floorplanning, Moving block sequence, Evolutionary algorithms, Organization
I.Introduction Floorplanning is an essential step in the hierarchical physical design of deep sub-micron very large scale integration(VLSI)circuits.It involves planning the positions and shapes of a set of blocks on a chip to optimize circuit performances.Blocks must be placed without being overlapped.As the technology moves into the deep sub-micron era,circuit sizes and complexities are growing rapidly and floorplanning has become even more important than it was before.Although floorplanning has been studied extensively,most previous works used simulated annealing (SA)as the search algorithm and handled rectilinear blocks by partitioning them into a set of rectangular sub-blocks.Therefore,it is still challenging and practically useful to find a nonslicing floorplan representation that is not only suitable for evolutionary algorithms (EAs)because of their high potential,but can also handle both rectangular and rectilinear blocks,similarly and simultaneously,without partitioning rectilinear blocks into sub-blocks.This paper presents the moving block sequence(MBS)as a new nonslicing floorplan representation to meet the above requirements. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game,Tetris As in Tetris we place blocks on a chip,one by one.Each block starts from an initial position and moves on the chip,until it reaches an appropriate position.In Tetris each block always appears on the top of the screen,and it is the players who find an appropriate position for each block during the descending process.In the MBS,on the other hand,four initial positions are designed from where the blocks could be moved to other places,according to the move rules. An MBS is designed to be composed of two tuples,one denoting the permutation of
3 I. Introduction Floorplanning is an essential step in the hierarchical physical design of deep sub-micron very large scale integration (VLSI) circuits. It involves planning the positions and shapes of a set of blocks on a chip to optimize circuit performances. Blocks must be placed without being overlapped. As the technology moves into the deep sub-micron era, circuit sizes and complexities are growing rapidly and floorplanning has become even more important than it was before. Although floorplanning has been studied extensively, most previous works used simulated annealing (SA) as the search algorithm and handled rectilinear blocks by partitioning them into a set of rectangular sub-blocks. Therefore, it is still challenging and practically useful to find a nonslicing floorplan representation that is not only suitable for evolutionary algorithms (EAs) because of their high potential, but can also handle both rectangular and rectilinear blocks, similarly and simultaneously, without partitioning rectilinear blocks into sub-blocks. This paper presents the moving block sequence (MBS) as a new nonslicing floorplan representation to meet the above requirements. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game, Tetris®. As in Tetris®, we place blocks on a chip, one by one. Each block starts from an initial position and moves on the chip, until it reaches an appropriate position. In Tetris®, each block always appears on the top of the screen, and it is the players who find an appropriate position for each block during the descending process. In the MBS, on the other hand, four initial positions are designed from where the blocks could be moved to other places, according to the move rules. An MBS is designed to be composed of two tuples, one denoting the permutation of
block names and the other the initial positions of blocks.Each block is placed on the chip in the order it occurs in the permutation.There are four choices for the initial position and no extra constraints are exerted on the solution space.Hence,it is easy to design effective crossover operators for EAs on such a solution space.Owing to a special structure designed for recording the information of both convex and concave rectilinear blocks,the MBS can handle them in the same way as the rectangular blocks,namely,without partitioning them into sub-blocks.The MBS has a smaller solution space,(n22),than several existing representations,such as the sequence pair(SP)[1],the bounded-sliceline grid(BSG)[2],the transitive closure graph(TCG)[3],the TCG-S [4],the corner sequence(CS)[5],and so on. The solution space of each of the SP,the TCG,the TCG-S,and the CS is(n!)2,and that of the BSG is n!C(n2,n),where n is the number of blocks. From another viewpoint,the MBS can also be considered an extension of the bottom-left (BL)method,the most documented heuristic approach in the field of cutting and packing, because the BL has only one initial position.Other similarities and differences between the MBS and the BL are detailed in Subsection II.C. On the basis of the MBS,a new organizational evolutionary algorithm (OEA),the MBS-OEA,is proposed.OEAs are a new kind of EA proposed in our previous works,and have been successfully applied to classification problems [6],numerical optimization problems [7],and satisfiability problems [8].In this paper,three new operators,namely,the splitting operator,the annexing operator,and the training operator are designed on the basis of the MBS,so that the framework of the OEA is applicable to solving floorplanning problems. This paper is organized as follows.Section II discusses some related work.Section III
4 block names and the other the initial positions of blocks. Each block is placed on the chip in the order it occurs in the permutation. There are four choices for the initial position and no extra constraints are exerted on the solution space. Hence, it is easy to design effective crossover operators for EAs on such a solution space. Owing to a special structure designed for recording the information of both convex and concave rectilinear blocks, the MBS can handle them in the same way as the rectangular blocks, namely, without partitioning them into sub-blocks. The MBS has a smaller solution space, (n!22(n-1)), than several existing representations, such as the sequence pair (SP) [1], the bounded-sliceline grid (BSG) [2], the transitive closure graph (TCG) [3], the TCG-S [4], the corner sequence (CS) [5], and so on. The solution space of each of the SP, the TCG, the TCG-S, and the CS is (n!)2 , and that of the BSG is n!C(n 2 , n), where n is the number of blocks. From another viewpoint, the MBS can also be considered an extension of the bottom-left (BL) method, the most documented heuristic approach in the field of cutting and packing, because the BL has only one initial position. Other similarities and differences between the MBS and the BL are detailed in Subsection II.C. On the basis of the MBS, a new organizational evolutionary algorithm (OEA), the MBS-OEA, is proposed. OEAs are a new kind of EA proposed in our previous works, and have been successfully applied to classification problems [6], numerical optimization problems [7], and satisfiability problems [8]. In this paper, three new operators, namely, the splitting operator, the annexing operator, and the training operator are designed on the basis of the MBS, so that the framework of the OEA is applicable to solving floorplanning problems. This paper is organized as follows. Section II discusses some related work. Section III
gives the definition of the moving block sequence.Section IV presents the algorithm transforming an MBS to a floorplan.Section V introduces the MBS-OEA in detail. Experiments are given in Section VI.Section VII provides an experimental study that aims to identify the mechanism that is mainly responsible for the effectiveness of the MBS-OEA. Finally,some conclusions and future work are provided in Section VIII. IⅡ.Related Work Many researchers proposed various algorithms for floorplanning problems by applying different mathematical tools.Among these,stochastic optimization algorithms were the most popular and had attracted increasing attention.These algorithms employed methods of perturbing floorplans and searching for better solutions.As this kind of method can design specific operations based on the characteristics and complexities of problems,the quality of solutions was generally high.To optimize floorplans by stochastic optimization algorithms, the representation is one of the key and fundamental issues. The representation has been studied extensively.In general,there are two kinds of floorplans,slicing and nonslicing.A slicing floorplan can be obtained by recursively cutting rectangles horizontally or vertically into smaller rectangles;otherwise,it is a nonslicing floorplan.Slicing floorplan representations have smaller solution spaces and can describe any slicing structure with no redundancy.But in practical applications,most designs belong to nonslicing floorplans. Therefore,nonslicing floorplan representations have recently attracted much attention. Although this kind of representation is of more general utility and can utilize the area more effectively and achieve better routability,it is more complex and difficult to embody such
5 gives the definition of the moving block sequence. Section IV presents the algorithm transforming an MBS to a floorplan. Section V introduces the MBS-OEA in detail. Experiments are given in Section VI. Section VII provides an experimental study that aims to identify the mechanism that is mainly responsible for the effectiveness of the MBS-OEA. Finally, some conclusions and future work are provided in Section VIII. II. Related Work Many researchers proposed various algorithms for floorplanning problems by applying different mathematical tools. Among these, stochastic optimization algorithms were the most popular and had attracted increasing attention. These algorithms employed methods of perturbing floorplans and searching for better solutions. As this kind of method can design specific operations based on the characteristics and complexities of problems, the quality of solutions was generally high. To optimize floorplans by stochastic optimization algorithms, the representation is one of the key and fundamental issues. The representation has been studied extensively. In general, there are two kinds of floorplans, slicing and nonslicing. A slicing floorplan can be obtained by recursively cutting rectangles horizontally or vertically into smaller rectangles; otherwise, it is a nonslicing floorplan. Slicing floorplan representations have smaller solution spaces and can describe any slicing structure with no redundancy. But in practical applications, most designs belong to nonslicing floorplans. Therefore, nonslicing floorplan representations have recently attracted much attention. Although this kind of representation is of more general utility and can utilize the area more effectively and achieve better routability, it is more complex and difficult to embody such
representations.There were no such efficient representations other than the constraint graphs until the SP [1]and the BSG [2]appeared in the mid-1990s.Subsequently,several efficient representations were proposed,such as the O-tree [9],the B'-tree [10],the corner block list (CBL)[11],the TCG [3],the TCG-S [4],the twin binary sequences(TBS)[12],the CS [5], and so on.However,most stochastic optimization algorithms using these representations were SA.Moreover,these representations were designed for rectangular blocks and cannot handle rectilinear blocks directly A.Stochastic Optimization Algorithms In the field of floorplanning,SA is much more popular than EAs.Several researchers used general SA to search solution spaces [1]-[5],[10]-[12].They perturbed the current floorplan according to properties of the employed representation and decreased the temperature according to a pre-defined cooling schedule.Additionally,on the basis of the SP, [13]proposed an orthogonal SA algorithm (OSA)with an efficient generation mechanism (EGM)for solving floorplanning problems.The EGM sampled a small number of representative floorplans and then efficiently derived a high-performance floorplan using a systematic reasoning method for the next move of the OSA,based on the orthogonal experimental design. In recent years,EAs have attracted increasing attention because they are suitable for solving complex and ill-defined problems.They have been successfully applied to the fields of numerical optimization [14],constraint satisfaction problems [15],data mining and knowledge discovery [16],[17],neural networks [18],and so on. There were also a few studies on the application of EAs to floorplanning problems. 6
6 representations. There were no such efficient representations other than the constraint graphs until the SP [1] and the BSG [2] appeared in the mid-1990s. Subsequently, several efficient representations were proposed, such as the O-tree [9], the B* -tree [10], the corner block list (CBL) [11], the TCG [3], the TCG-S [4], the twin binary sequences (TBS) [12], the CS [5], and so on. However, most stochastic optimization algorithms using these representations were SA. Moreover, these representations were designed for rectangular blocks and cannot handle rectilinear blocks directly. A. Stochastic Optimization Algorithms In the field of floorplanning, SA is much more popular than EAs. Several researchers used general SA to search solution spaces [1]-[5], [10]-[12]. They perturbed the current floorplan according to properties of the employed representation and decreased the temperature according to a pre-defined cooling schedule. Additionally, on the basis of the SP, [13] proposed an orthogonal SA algorithm (OSA) with an efficient generation mechanism (EGM) for solving floorplanning problems. The EGM sampled a small number of representative floorplans and then efficiently derived a high-performance floorplan using a systematic reasoning method for the next move of the OSA, based on the orthogonal experimental design. In recent years, EAs have attracted increasing attention because they are suitable for solving complex and ill-defined problems. They have been successfully applied to the fields of numerical optimization [14], constraint satisfaction problems [15], data mining and knowledge discovery [16], [17], neural networks [18], and so on. There were also a few studies on the application of EAs to floorplanning problems
Cohoon et al.in [19]offered the classical work on using genetic algorithms (GAs)for floorplanning.The arrangement of rooms on the layout surface was represented in the genotype by a postfix expression that was not normalized of the corresponding slicing tree. Schnecke et al.in [20]used a GA to manipulate the binary slicing tree directly for floorplanning.However,the crossover involved complex repair mechanisms simply to ensure that the offspring represented a legal slicing floorplan.Valenzuela et al.in [21]presented a GA that used a slicing tree construction process.They used an order-based representation that encoded rectangles and binary operations into a simple permutation of structures and a decoder that converted the permutation of structures into a normalized postfix expression. Generally speaking,applications of EAs to floorplanning problems are much fewer than those of SA.Although some researchers [19]-[21]used EAs,their works were all based on the slicing structure instead of the nonslicing structure.This restricted the popularization of these methods to some extent.In our opinion,the reason for fewer applications of EAs is that the nonslicing floorplan representations are generally very complex and solution spaces are constrained.In this case,EAs with traditional evolutionary operators (e.g.,crossover)tend to create infeasible individuals during the search.To boost the development of EAs in the field of floorplanning,it is important to design new nonslicing floorplan representations that do not exert extra constraints on solution spaces and facilitate effective crossover operators. B.Floorplanning Problems with Arbitrarily Shaped Rectilinear Blocks In the simplest situation of floorplanning,all blocks are rectangular.However,in real design,as some of the circuit blocks come from design re-use,they are not necessarily rectangular.To fully optimize some predefined cost metric,for example,area,wirelength,or
7 Cohoon et al. in [19] offered the classical work on using genetic algorithms (GAs) for floorplanning. The arrangement of rooms on the layout surface was represented in the genotype by a postfix expression that was not normalized of the corresponding slicing tree. Schnecke et al. in [20] used a GA to manipulate the binary slicing tree directly for floorplanning. However, the crossover involved complex repair mechanisms simply to ensure that the offspring represented a legal slicing floorplan. Valenzuela et al. in [21] presented a GA that used a slicing tree construction process. They used an order-based representation that encoded rectangles and binary operations into a simple permutation of structures and a decoder that converted the permutation of structures into a normalized postfix expression. Generally speaking, applications of EAs to floorplanning problems are much fewer than those of SA. Although some researchers [19]-[21] used EAs, their works were all based on the slicing structure instead of the nonslicing structure. This restricted the popularization of these methods to some extent. In our opinion, the reason for fewer applications of EAs is that the nonslicing floorplan representations are generally very complex and solution spaces are constrained. In this case, EAs with traditional evolutionary operators (e.g., crossover) tend to create infeasible individuals during the search. To boost the development of EAs in the field of floorplanning, it is important to design new nonslicing floorplan representations that do not exert extra constraints on solution spaces and facilitate effective crossover operators. B. Floorplanning Problems with Arbitrarily Shaped Rectilinear Blocks In the simplest situation of floorplanning, all blocks are rectangular. However, in real design, as some of the circuit blocks come from design re-use, they are not necessarily rectangular. To fully optimize some predefined cost metric, for example, area, wirelength, or
routability,it is important to deal with floorplanning problems with arbitrarily shaped rectilinear blocks.There are a few existing partition-based approaches that use the well-known representations. Xu et al.in [22]explored the conditions of the feasible SP for L-shaped blocks.Kang et al.in [23]derived three necessary and sufficient conditions for recovering the shapes of convex rectilinear blocks based on the SP.Fujiyoshi et al.in [24]derived a necessary and sufficient condition of the feasible SP for rectilinear blocks.Nakatake et al.in [25]handled pre-placed and rectilinear blocks using the BSG.Kang et al.in [26]used the BSG and the SP to solve the topology constrained block packing for ordered convex rectilinear blocks and extended the method to handle arbitrary rectilinear blocks.Pang et al.in [27]and Wu et al.in [28]used the O-tree and the B'-tree,respectively,to handle rectilinear blocks.Ma et al.in [29] used the CBL to deal with the placement abutment constraint and extended the method to deal with L-and T-shaped blocks.Lin et al.in [30]derived necessary and sufficient conditions of the feasible TCG for the sub-blocks.Additionally,Chu et al.in [31]dealt with the problem of giving a preliminary floorplan and changed the shapes and dimensions of some soft blocks to L-shaped to fill up the empty space. From the literature cited,we can see that most previous works on floorplanning problems with rectilinear blocks partitioned rectilinear blocks into a set of rectangular sub-blocks and operated on sub-blocks under some constraints induced from the original rectilinear blocks. However,as the original rectilinear blocks were partitioned,some additional operations became necessary to retrieve the original shapes after packing,resulting in a larger computational cost.Thus,it is necessary to design a representation that can handle rectilinear 8
8 routability, it is important to deal with floorplanning problems with arbitrarily shaped rectilinear blocks. There are a few existing partition-based approaches that use the well-known representations. Xu et al. in [22] explored the conditions of the feasible SP for L-shaped blocks. Kang et al. in [23] derived three necessary and sufficient conditions for recovering the shapes of convex rectilinear blocks based on the SP. Fujiyoshi et al. in [24] derived a necessary and sufficient condition of the feasible SP for rectilinear blocks. Nakatake et al. in [25] handled pre-placed and rectilinear blocks using the BSG. Kang et al. in [26] used the BSG and the SP to solve the topology constrained block packing for ordered convex rectilinear blocks and extended the method to handle arbitrary rectilinear blocks. Pang et al. in [27] and Wu et al. in [28] used the O-tree and the B* -tree, respectively, to handle rectilinear blocks. Ma et al. in [29] used the CBL to deal with the placement abutment constraint and extended the method to deal with L- and T-shaped blocks. Lin et al. in [30] derived necessary and sufficient conditions of the feasible TCG for the sub-blocks. Additionally, Chu et al. in [31] dealt with the problem of giving a preliminary floorplan and changed the shapes and dimensions of some soft blocks to L-shaped to fill up the empty space. From the literature cited, we can see that most previous works on floorplanning problems with rectilinear blocks partitioned rectilinear blocks into a set of rectangular sub-blocks and operated on sub-blocks under some constraints induced from the original rectilinear blocks. However, as the original rectilinear blocks were partitioned, some additional operations became necessary to retrieve the original shapes after packing, resulting in a larger computational cost. Thus, it is necessary to design a representation that can handle rectilinear
blocks directly C.Cutting and Packing Problems One might argue that the MBS is similar to the bottom-left(BL)and the bottom-left-fill (BLF)methods [32],[33]used in the field of cutting and packing.In the BL,each block starts from the top-right corner and slides as far as possible to the bottom,and then as far as possible to the left.These successive vertical and horizontal movements are repeated until blocks lock in a stable position.The BLF is a modified version of the BL and can fill the holes in placed rectangles. Although all the BL,the BLF,and the MBS move blocks on a region,the BL and the BLF have only one initial position,namely,the top-right location,whereas the MBS has four initial positions.Moreover,the MBS has four move rules corresponding to the four initial positions.To illustrate the usefulness of these extra choices for the initial positions and the move rules in the MBS,a group of experiments on the MBS with only one or two initial positions is carried out and the results are presented in Subsection VII.A. On the other hand,there is a major difference between cutting and packing problems and floorplanning.In the former,the width of the region is fixed and only the height needs to be minimized,whereas in the latter,there are no constraints on the regions,and the area needs to be minimized.Additionally,in the field of cutting and packing,problems are usually categorized into orthogonal problems (where blocks are rectangular)[34]and irregular problems [35].The emphasis of the MBS is to handle rectilinear blocks,which are more general than rectangular blocks,but are a special case of irregular blocks. EAs are also used in the field of cutting and packing.In 1985,Smith [36]first applied 9
9 blocks directly. C. Cutting and Packing Problems One might argue that the MBS is similar to the bottom-left (BL) and the bottom-left-fill (BLF) methods [32], [33] used in the field of cutting and packing. In the BL, each block starts from the top-right corner and slides as far as possible to the bottom, and then as far as possible to the left. These successive vertical and horizontal movements are repeated until blocks lock in a stable position. The BLF is a modified version of the BL and can fill the holes in placed rectangles. Although all the BL, the BLF, and the MBS move blocks on a region, the BL and the BLF have only one initial position, namely, the top-right location, whereas the MBS has four initial positions. Moreover, the MBS has four move rules corresponding to the four initial positions. To illustrate the usefulness of these extra choices for the initial positions and the move rules in the MBS, a group of experiments on the MBS with only one or two initial positions is carried out and the results are presented in Subsection VII.A. On the other hand, there is a major difference between cutting and packing problems and floorplanning. In the former, the width of the region is fixed and only the height needs to be minimized, whereas in the latter, there are no constraints on the regions, and the area needs to be minimized. Additionally, in the field of cutting and packing, problems are usually categorized into orthogonal problems (where blocks are rectangular) [34] and irregular problems [35]. The emphasis of the MBS is to handle rectilinear blocks, which are more general than rectangular blocks, but are a special case of irregular blocks. EAs are also used in the field of cutting and packing. In 1985, Smith [36] first applied
GAs to packing problems.At the same time,Davis [37]summarized the techniques for applications of GAs to epistatic domains using the example of two-dimensional (2D)bin packing.Since then,various packing problems,ranging from regular to arbitrary shapes in two or more dimensions,have been approached.In these approaches,individuals were represented as permutations of blocks.A placement heuristic was used to decode the representation by packing the pieces in the order given by the permutation.This approach remained popular for cutting and packing problems [38],[39].There were also several approaches by incorporating the bound information of the branches of search trees into GAs [40].Hopper and Turton [41]had reviewed applications of GAs to packing problems.They also conducted an empirical study of meta-heuristic and heuristic algorithms for 2D packing problems [42]. In the field of cutting and packing,because individuals are usually represented as permutations of blocks,the only task of EAs is to optimize the permutations.However,the MBS has two tuples,permutation and initial position.Thus,the task of the MBS-OEA is to optimize not only the permutation,but also the initial positions. III.Moving Block Sequence Representation The blocks in floorplanning can be classified into three types:hard rectangular blocks (HRaBs),soft rectangular blocks(SRaBs),and hard rectilinear blocks(HRiBs).Regardless of the type of blocks,the goal of floorplanning is to determine the shapes and locations of a set of blocks so that no block overlaps and to minimize some predefined cost metric induced by a floorplan.Each block is free to rotate. Given a floorplanning problem with n blocks,B=(Bo,B1,...,B1),let F(B)denote a 10
10 GAs to packing problems. At the same time, Davis [37] summarized the techniques for applications of GAs to epistatic domains using the example of two-dimensional (2D) bin packing. Since then, various packing problems, ranging from regular to arbitrary shapes in two or more dimensions, have been approached. In these approaches, individuals were represented as permutations of blocks. A placement heuristic was used to decode the representation by packing the pieces in the order given by the permutation. This approach remained popular for cutting and packing problems [38], [39]. There were also several approaches by incorporating the bound information of the branches of search trees into GAs [40]. Hopper and Turton [41] had reviewed applications of GAs to packing problems. They also conducted an empirical study of meta-heuristic and heuristic algorithms for 2D packing problems [42]. In the field of cutting and packing, because individuals are usually represented as permutations of blocks, the only task of EAs is to optimize the permutations. However, the MBS has two tuples, permutation and initial position. Thus, the task of the MBS-OEA is to optimize not only the permutation, but also the initial positions. III. Moving Block Sequence Representation The blocks in floorplanning can be classified into three types: hard rectangular blocks (HRaBs), soft rectangular blocks (SRaBs), and hard rectilinear blocks (HRiBs). Regardless of the type of blocks, the goal of floorplanning is to determine the shapes and locations of a set of blocks so that no block overlaps and to minimize some predefined cost metric induced by a floorplan. Each block is free to rotate. Given a floorplanning problem with n blocks, B={B0, B1, …, Bn-1}, let F(B) denote a