Conquering hierarchical difficulty by explicit chunking: substructural chromosome compression

ABSTRACT

This paper proposes a chromosome compression scheme which represents subsolutions by the most expressive schemata. The proposed chromosome compression scheme is combined with the dependency structure matrix genetic algorithm and the restricted tournament replacement to create a scalable optimization tool which optimizes problems via hierarchical decomposition. One important feature of the proposed method is that at the end of the run, the problem structure obtained from the proposed method is comprehensible to human researchers and is reusable for larger-scale problems. The empirical result shows that the proposed method scales sub-quadratically with the problem size on hierarchical problems and is able to capture the problem structures accurately.

REFERENCES

• 1: R. Descartes. A discourse on the method of rightly conducting the reason, and seeking truth in the sciences {Veitch, J. (trans.)}. In T. Sorell, editor, A Discourse on Method: Meditations and Principles, pages 3--57. Everyman, London, UK, 1994. Original work published 1637.
• 2: C. Fernandez. Integration Analysis of Product Architecture to Support Effective Team Co-location. Master thesis, Massachusetts Institute of Technology, 1998.
• 3: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 4: D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992.
• 5: G. R. Harik. Finding multiple solutions in problems of bounded difficulty. IlliGAL Report No. 94002, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1994.
• 6: G. R. Harik. Linkage Learning via Probabilistic Modeling in the ECGA. IlliGAL Report No. 99010, University of Illinois at Urbana-Champaign, Urbana, IL, Feb. 1999.
• 7: G. R. Harik, E. Cantú-Paz, D. E. Goldberg, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Proceedings of 1997 IEEE International Conference on Evolutionary Computation, pages 7--12, 1997.
• 8: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 9: M. Hutter and M. Zaffalon. Distribution of mutual information from complete and incomplete data. Computational Statistics and Data Analysis, 48(3):633--657, 2005.
• 10: G. D. Kleiter. The posterior probability of Bayes nets with strong dependences. Soft Computing, 3:162--173, 1999.
• 11: S. Kullback and R. A. Leibler. On information and sufficiency. Annual Mathematical Statistics, 22:79--86, 1951.
• 12: P. Larrañaga and J. Lozano, editors. Estimation of Distribution Algorithms. Kluwer Academic Publishers, Boston, MA, 2002.
• 13: Martin Pelikan , David E. Goldberg, Bayesian optimization algorithm: from single level to hierarchy, 2002
• 14: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference, pages 511--518, 2001.
• 15: J. Rissanen. Modeling by shortest data description. Automatica, 14:465--471, 1978.
• 16: D. Sharman, A. Yassine, and P. Carlile. Characterizing modular architectures. ASME 14th International Conference, pages DTM--34024, Sept. 2002.
• 17: H. A. Simon. The Science of Artificial. The MIT Press, Cambridge, Massachusetts, 1968.
• 18: D. V. Steward. The design structure system: A method for managing the design of complex systems. IEEE Transactions on Engineering Management, 28:77--74, 1981.
• 19: M. Toussaint. Compact genetic codes as a search strategy of evolutionary processes. Foundations of Genetic Algorithms 8 (FOGA 2005), pages 75--94, 2005.
• 20: Richard A. Watson , Greg Hornby , Jordan B. Pollack, Modeling Building-Block Interdependency, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.97-108, September 27-30, 1998
• 21: R. A. Watson and J. B. Pollack. Hierarchically consistent test problems for genetic algorithms: Summary and additional results. Late breaking papers at the Genetic and Evolutionary Computation Conference, pages 292--297, 1999.
• 22: Richard A. Watson , Jordan B. Pollack, Modular Interdependency in Complex Dynamical Systems, Artificial Life, v.11 n.4, p.445-458, December 2005 [doi>10.1162/106454605774270589]
• 23: A. Yassine, D. R. Falkenburg, and K. Chelst. Engineering design management: An information structure approach. International Journal of production research, 37(13):2957--2975, 1999.
• 24: T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-p. Chen. Genetic algorithm design inspired by organizational theory: Pilot study of a dependency structure matrix driven genetic algorithm. Proceedings of Artificial Neural Networks in Engineering 2003 (ANNIE 2003), pages 327--332, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms, Design

Keywords:
analyze, chromosome compression, chunking, genetic algorithms, hierarchy, linkage learning, model building