Hypergraph-based Evolutionary Design System
Inhaltsverzeichnis
Reference
E. Grabska, B. Strug, G. Ślusarczyk: Hypergraph-based Evolutionary Design System. In: Generative Art 2007.
DOI
Abstract
This paper deals with applying evolutionary methods in computer aided design. The design process is an iterative one consisting of several steps. It starts with a preliminary or conceptual design, which is then analyzed or tested in order to find out which of its elements must be redesigned or refined. The process of evaluation and optimization is repeated until an acceptable solution is found. Since designing can be treated in computer science as a search process, where all possible designs form a search space, it is possible to use search techniques such as evolutionary ones.
As evolutionary search consists in evaluating and refining possible solutions, it can be seen as analogous to a human design iterative process of analysis, testing and optimization. Similarly to the refinement step in human design, in evolutionary search designs to be transformed are determined according to their evaluation (fitness). The refinement step is often performed not on actual solutions (phenotypes) but on their coded equivalents (genotypes).
Since in design problems genotypes in the form of binary strings are very often insufficient we propose to use a graph-based representation of genotypes which enables us not only to express geometrical properties of an object but also its attributes (like color, material etc.) and relations between object components.
In this paper we adopt hierarchical hypergraphs as they can represent an artifact with both multi-argument relations and hierarchical dependence which are impossible to express by other structures. The greatest advantage of this representation is its ability to describe in a uniform way all types of relations and objects and to produce highly fitted individuals.
Using hypergraphs in an evolutionary search requires the adaptation of traditional evolutionary operators like cross-over and mutation. As the hypergraphs selected to be transformed by the evolutionary operators at the subsequent stage of the evolution and their structures are not known a priori the operator must be defined in a way which allows for an "online" computation of new hypergraphs. Genetic operators working on hypergraphs and the structure of an evolutionary design system is presented. The method is illustrated by examples of floor-layouts generated by a house design system, where structures of floor-layouts are represented by hypergraphs. In our approach a cross-over operation exchanges subgraphs representing the functional areas with different internal arrangements, while mutation affects local and global attributes as well as the graph structure (by adding or deleting subgraphs)
Extended Abstract
Bibtex
Used References
[1] P. J. Bentley, Generic Evolutionary Design of Solid Objects using a Genetic Algorithm, PhD thesis, UCL London 1), 3-38, (1997).
[2] Borkowski A., Grabska E., Nikodem P, and Strug B., Searching for Innovative Structural Layouts by Means of Graph Grammars and Evolutionary Optimization,, Proc. 2nd Int. Structural Eng. And Constr. Conf, Rome, (2003).
[3] De Jong K, Arciszewski T, and Vyas H, An Overview of Evolutionary Computation and its Applications, in. Artificial Intelligence in Engineerig,9-22, Warsaw, (1999).
[4] D.E.Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Reading, MA, Addison-Wesley, (1989).
[5] E. Grabska. A. Lachwa, G. Slusarczyk, K. Grzesiak-Kopec and J. Lembas; Hierarchical Layout Hypergraph Operations and Diagrammatic Reasoning, Machine GRAPHICS and VISION, (in print)
[6] E.Grabska,Theoretical Concepts of Graphical Modelling. Part one: Realization of CP-graphs. Machine GRAPHICS and VISION, 2(1993).
[7] Grabska, E.. Graphs and designing. Lecture Notes in Computer Science, 776 (1994).
[8] E.Grabska, W. Palacz, Hierarchical graphs in creative design. Machine GRAPHICS and VISION, 9(1/2), 115-123. (2000).
[9] Hajela P. and Lee, J, Genetic Algorith in Truss Topological OpJournal of Solids and Structures vol.32, no 22 , 3341-3357, (1995).
[10] Hoffman, C. M.,Geometric and Solid Modeling: An Introduction, Morgan Kaufmann, San Francisco, CA, (1989).
[11]Holland, J. H. Adaptation in Natural and Artificial Systems, Ann Arbor, (1975).
[12] Mantyla, M.,An Introduction To Solid Modeling, Computer Science Press, Rockville,MD,vol.87, (1988).
[13] Martin, R R and Stephenson, P C Sweeping of Three-dimensional Objects? Computer Aided Design Vol 22(4) (1990), pp. 223-234.
[14] Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin Heidelberg New York (1996).
[15] Michalewicz, Z. Fogel, D. B.: How to Solve It: Modern Heuristics.. Springer-Verlag, Berlin Heidelberg New York (2000).
[16] P. Nikodem and B. Strug: Graph Transformations in Evolutionary Design. Artificial Intelligence and Soft Computing - ICAISC 2004 Lecture Notes in Computer Science,vol 3070, pp. 456-461, Springer, 2004. http://link.springer.com/chapter/10.1007%2F978-3-540-24844-6_67
[17] Rozenberg, G. Handbook of Graph Grammars and Computing by Graph. Transformations, vol.1 Fundations, World Scientific London (1997)
[18] Barbara Strug: Hierarchical Representation and Operators in Evolutionary Design. Parallel Processing and Applied Mathematics (PPAM 2005), LNCS vol 3911, pp. 447-454 Springer 2006. http://link.springer.com/chapter/10.1007%2F11752578_54
Links
Full Text
http://www.generativeart.com/on/cic/papersGA2007/04.pdf
