Scalability, generalization and coevolution -- experimental comparisons applied to automated facility layout planning

ABSTRACT

Several practical problems in industry are difficult to optimize, both in terms of scalability and representation. Heuristics designed by domain experts are frequently applied to such problems. However, designing optimized heuristics can be a non-trivial task. One such difficult problem is the Facility Layout Problem (FLP) which is concerned with the allocation of activities to space. This paper is concerned with the block layout problem, where the activities require a fixed size and shape (modules). This problem is commonly divided into two sub problems; one of creating an initial feasible layout and one of improving the layout by interchanging the location of activities. We investigate how to extract novel heuristics for the FLP by applying an approach called Cooperative Coevolutionary Gene Expression Programming (CCGEP). By taking advantage of the natural problem decomposition, one species evolves heuristics for pre-scheduling, and another for allocating the activities onto the plant. An experimental, comparative approach investigates various features of the CCGEP approach. The results show that the evolved heuristics converge to suboptimal solutions as the problem size grows. However, coevolution has a positive effect on optimization of single problem instances. Expensive fitness evaluations may be limited by evolving generalized heuristics applicable to unseen fitness cases of arbitrary sizes.

REFERENCES

• 1: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 2: Thelma D. Mavridou , Panos M. Pardalos, Simulated Annealing and Genetic Algorithms for the Facility LayoutProblem: A Survey, Computational Optimization and Applications, v.7 n.1, p.111-126, Jan. 1997 [doi>10.1023/A:1008623913524]
• 3: Kenneth O. Stanley , Risto Miikkulainen, A Taxonomy for artificial embryogeny, Artificial Life, v.9 n.2, p.93-130, Spring 2003 [doi>10.1162/106454603322221487]
• 4: Peter J. Bentley, Evolutionary Design by Computers with CDrom, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 5: Marcus Furuholmen , Mats Hovin , Jim Torresen , Kyrre Glette, Continuous Adaptation in Robotic Systems by Indirect Online Evolution, Proceedings of the 2008 ECSIS Symposium on Learning and Adaptive Behaviors for Robotic Systems, p.71-76, August 06-08, 2008 [doi>10.1109/LAB-RS.2008.13]
• 6: Marcus Furuholmen , Kyrre Glette , Jim Torresen , Mats Hovin, Indirect Online Evolution --- A Conceptual Framework for Adaptation in Industrial Robotic Systems, Proceedings of the 8th international conference on Evolvable Systems: From Biology to Hardware, September 21-24, 2008, Prague, Czech Republic [doi>10.1007/978-3-540-85857-7_15]
• 7: Meller, R., Gau, K.: The facility layout problem: Recent and emerging trends and perspectives. Journal of Manufacturing Systems 15(5) (1996) 351--366
• 8: Singh, S., Sharma, R.: A review of different approaches to the facility layout problems. The International Journal of Advanced Manufacturing Technology 30(5) (2006) 425--433
• 9: Michalek, J., Choudhary, R., Papalambros, P.: Architectural Layout Design Optimization. Engineering Optimization 34(5) (2002) 461--484
• 10: Jaime Garces-Perez , Dale A. Schoenefeld , Roger L. Wainwright, Solving facility layout problems using genetic programming, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California
• 11: Janny Leung, A new graph-theoretic heuristic for facility layout, Management Science, v.38 n.4, p.594-605, April 1992 [doi>10.1287/mnsc.38.4.594]
• 12: Liggett, R.: Automated facilities layout: past, present and future. Automation in Construction 9(2) (2000) 197--215
• 13: Mitchell A. Potter , Kenneth A. De Jong, A Cooperative Coevolutionary Approach to Function Optimization, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.249-257, October 09-14, 1994
• 14: Ferreira, C.: Gene Expression Programming: a New Adaptive Algorithm for Solving Problems. Arxiv preprint cs.AI/0102027 (2001).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures; Performance measures

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
coevolution, development, facility layout problem, gene expression programming