Abstract
Most existing placement algorithms were designed to handle blocks that are rectangular in shape. In this paper, we show how a genetic algorithm (GA) is used to construct an optimal arrangement of two-dimensional rectilinear blocks. Our approach does not require the orientation of each block to be fixed. To transform the placement problem to a GA problem, we devised a decoding technique known as circular placement. The novelty of the circular placement technique is that it configures the rectilinear blocks by building up potentially good groupings of blocks starting from the corners of the placement area. To complement the circular placement approach, we present a methodology for deriving a suitable objective function. We confirm the performance of our GA-based placement algorithm by presenting simulation results of some problems on tiling with up to 128 polyominoes. The algorithm described in this paper has great potential for applications in packing, compacting and general component placement in the various disciplines of engineering.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y. Akiyama, A. Yamashita, M. Kajiura, and H. Aiso, “Combinatorial optimization with Gaussian machines,” Proceedings of International Joint Conference on Neural Networks'89, Washington, 1989, vol. 1, pp. 533–540.
Y. Davidor, Genetic Algorithms and robotics: A Heuristic Strategy for Optimization, World Scientific: Singapore, pp. 45–92, 1990.
L. Davis, “Job shop scheduling with genetic algorithms,” Proceedings of First International Conference on Genetic Algorithms and Their Applications, Lawrence Erlbaum Associates, Hillsdale, NJ, 1985, pp. 136–140.
A.E. Dunlop and B.W. Kernighan, “A procedure for placement of standard-cell VLSI circuits,” IEEE Transactions on Computer Aided Design, vol. 4, no. 1, pp. 92–98, 1985.
M. Gardner, “Mathematical games,” Scientific American, pp. 112–115, 1975.
D.E. Goldberg, Computer-Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning, Doctoral Dissertation, University of Michigan, 1983.
D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, pp. 1–214, 1989,.
D.E. Goldberg and R. Lingle, Jr., “Alleles, loci, and the traveling salesman problem,” Proceedings of First International Conference on Genetic Algorithms and Their Applications, Lawrence Erlbaum Associates, Hillsdale, NJ, 1985, pp. 154–158.
S.W. Golomb, Polyominoes, Scribner: New York, 1965.
S.W. Golomb, “Polyominoes which tile rectangles,” Journal of Combinatorial Theory, vol. A 51, pp. 117–124, 1989.
J.J. Grefenstette and J.E. Baker, “How genetic algorithms work: A critical look at implicit parallelism,” Proceedings of Third International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1989, pp. 20–27.
J.J. Grefenstette and J.M. Fitzpatrick, “Genetic search with approximate function evaluations,” Proceedings of First International Conference on Genetic Algorithms and Their Applications, Lawrence Erlbaum Associates, Hillsdale, NJ, 1985, pp. 112–120.
J.H. Holland, Adaptation in Natural and Artificial Systems, University Michigan Press: Ann Arbor, MI, pp. 75–120, 1975.
J. Horn, D.E. Goldberg, and K. Deb, “Long path problems,” Proceedings of Third Conference of Parallel Problem Solving from Nature, Springer-Verlag, Berlin, Germany, 1994, pp. 149–158.
H. Kargupta, K. Deb, and D.E. Goldberg, “Ordering genetic algorithms and deception,” Proceedings of Second Conference on Parallel Problem Solving from Nature, Amsterdam, North-Holland, 1992, pp. 47–56.
C.L. Karr, “Design of an adaptive fuzzy logic controller using a genetic algorithm,” Proceedings of Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1991, pp. 450–457.
M.S. Klamkin and A. Liu, “Polyominoes on the infinite checkerboard,” Journal of Combinatorial Theory, vol. A 28, pp. 7–16, 1980.
D.A. Klarner, “Packing a rectangle with congruent N-ominoes,” Journal of Combinatorial Theory, vol. 7, pp. 107–115, 1969.
M.H. Lim, S. Rahardja, and B.H. Gwee, “A GA paradigm for learning fuzzy rules,” (to appear) in International Journal for Fuzzy Sets and Systems, North-Holland, 1995.
H. Muhlenbein, “How genetic algorithms really work,” Proceedings of Second Conference on Parallel Problem Solving from Nature, Amsterdam, North-Holland, 1992, pp. 15–26.
J.D. Schaffer, R.A. Caruana, L.J. Eshelman, and R. Das, “A study of control parameters affecting on-line performance of genetic algorithms for function optimization,” Proceedings of Third International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1989, pp. 51–60.
S. Sutanthavibul, E. Shragowitz and J. B. Rosen, “An analytical approach to floorplan design and optimization,” IEEE Transactions on Computer Aided Design, vol. 10, no. 6, pp. 761–769, 1991.
Y. Takefuji and K.C. Lee, “A parallel algorithm for tiling problems,” IEEE Transactions on Neural Networks, vol. 1, no. 1, pp. 143–145, 1990.
T.C. Wang and D.F. Wong, “Optimal floorplan area optimization,” IEEE Transactions on Computer Aided Design, vol. 11, no. 10, pp. 992–1002, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gwee, B.H., Lim, M.H. Polyominoes tiling by a genetic algorithm. Comput Optim Applic 6, 273–291 (1996). https://doi.org/10.1007/BF00247795
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00247795