Introduction
The process of architectural design involves self-expression of the architect and requires a lot of imagination to pass on ideas and values that have social significance. Architectural objects also often refer to the cultural and historical context. Maintaining the required character of new architectural projects without discouraging the appropriate innovation is an important design challenge.
This problem is related to one of the important contemporary challenges of computer-aided architectural design, which is the aesthetic evaluation of architectural objects supported by a computer (Schnier and Gero, Reference Schnier and Gero1996; Tarko and Grabska, Reference Tarko and Grabska2011; Garip and Garip, Reference Garip and Garip2012; Mars and Grabska, Reference Mars and Grabska2015). Usually in such a situation a question regarding the existence of automatic evaluation of aesthetic arises. An essential aspect of the automatic aesthetic evaluation of architectural objects taken into account is prototypicality (i.e., the degree to which an object is representative of a general class of objects) (Whitfield and Slatter, Reference Whitfield and Slatter1979). Another aspect is related to the reconstruction of the human process of visual perception, taking place in the identification and evaluation of architectural objects which activate aesthetic response.
In our approach to support aesthetic evaluation by a computer, we use the theory proposed by Biederman (Reference Biederman1987). The main idea of this theory is that the brain contains mechanisms to identify three-dimensional (3D) structural components of objects that are called geons. The brain stores geon components of objects together with a description of how they are connected. Taking into account both prototypicality and visual perception, we rely on the Biederman structural skeleton composed of geons.
It is difficult to equip computer programs with knowledge needed to imitate a human way of thinking and sense of aesthetics during the automatic design process. However, an evolutionary approach to design gives a chance to imitate to some degree the biological processes in order to obtain objects with high aesthetic values.
One of the main difficulties arising when applying Genetic Algorithms in a given design space is the choice of two search spaces, namely the phenotype space and the genotype space. In the former space, elements of the design domain are visualized, while the latter one contains their representations. In general, the genotype representation may not provide complete information about the corresponding phenotype. The advantage of the proposed approach is such a choice of both spaces that the genotypes are automatically generated from phenotypes without any loss of information.
As evolutionary search consists in evaluating and refining possible solutions, it is highly analogous to the human design iterative process of analysis, testing, and optimization (Mitchell, Reference Mitchell1996). Similarly, to the refinement step in human design, in evolutionary search, designs to be modified are determined according to their evaluation (fitness). The refinement step is often performed not on actual solutions (phenotypes) but on their coded equivalents (genotypes). In the work of Schnier and Gero (Reference Schnier and Gero1996), genotypes are used as a representation of architectural layout components in evolutionary design. Yet, in human design, the process is usually directed not only by the desire to obtain an optimal artifact but also such a one that meets certain requirements. Design requirements are often related to characteristic features of objects, their desired functions or constraints (Jupp and Gero, Reference Jupp, Gero, Argamon, Burns and Dubnov2010). The problem of architectural space planning according to certain design criteria is also described in Wong and Chan (Reference Wong and Chan2009).
The aim of this paper is to present a new approach to the aesthetic-oriented and characteristic-directed evolutionary design of architectural object prototypes. The proposed methodology is intended for the creative experimentation with potential solutions based on the exploration of compositions of shapes which meet some constraints. Design characteristics are understood as sets of specific features which constitute a discriminant of a class of architectural forms. As the aesthetic evaluation of architectural objects is associated with visual perception, we propose to take a human perception model as the foundation for automatic assessment of generated models. The presented method is based on the Biederman visual perception model, in which object recognition is assumed to be performed by the exploration of component shapes and relations between them. In our approach, architectural object prototypes are generated as configurations of some basic solids (De Jong and Van der Voordt, Reference De Jong, Van der Voordt, De Jong and Van der Voordt2002). Each prototype has its representation in the form of an attributed composition graph, where nodes denote components, bonds assigned to nodes represent component surfaces, while edges describe spatial relations between these surfaces. Such a representation enables us not only to express geometrical properties of an object but also its attributes (like size, material, etc.).
In the genetic algorithms considered in this paper, all prototypes are represented in two forms: in the encoded graph-based form of genotypes and in the decoded form of phenotypes. During the process of evolution, the graphs representing designs (genotypes) are modified by mutation and crossover operations. After each step of evolution, a new generation of 3D models (phenotypes) is rendered.
Using graph representations of design objects during the evolutionary search process requires the adaptation of traditional evolutionary operators, which operate on bitstrings (Goldberg, Reference Goldberg1989), as well as defining an appropriate fitness function. In Kane and Schoenauer (Reference Kane and Schoenauer1996), where genetic algorithms are used for structural topology optimization of cantilever plates, specific genetic operators for matrix-based representations of plate genotypes are introduced. In De Silva Garza and Maher (Reference De Silva Garza and Maher1999), the similar operators are used for matrix-based genotype representations in order to obtain layout designs of residences which satisfy the requirements imposed by feng shui. However, in both of the above-mentioned approaches submatrices extracted from parent genotypes and interchanged in a crossover operation have the same size, while in case of this operation performed on graphs, extracted subgraphs can have a different number of connections in their parent graphs. As in our approach, the graphs selected to be interchanged and their structures are not known a priori, a crossover operation must be defined in a way which allows for a dynamic computation of resulting graphs. A mutation operation can affect both local and global attributes as well as the graph structure (by adding or deleting subgraphs).
A fitness function is determined by the fuzzy evaluation of designs, which determines to what degree each phenotype fulfills aesthetic criteria and adheres to specified design characteristics. Many criteria and requirements determined in the specification of the designed architectural form are soft, that is, they are to be fulfilled in some degree. There are also hard criteria and requirements, which are to be fully satisfied, and sharp ones, the fulfillment of which would be desirable but is not absolutely necessary. As most design problems involve several conflicting standards, the weights determining the importance of the specified criteria and requirements should be determined. Thus, even an incoherent and inconsistent design specification can be compatible with the specific project. The criteria weights have a huge impact on the subsequent assessments of project compliance with the specification.
There are two main approaches to aesthetic evaluation: the semantic scale measurement relating to the Thurstone method and computational aesthetic methods. The semantic scale measurement is aimed to analyzing individual preferences regarding the quality of the visual appearance of architectural objects. An interesting example was presented in Santosa and Fauziah (Reference Santosa and Fauziah2016), where the appearance of the restaurant facade was evaluated. The considered scale contained items classified according to the intensity level, from high to low. As a result of public preferences, an independent T-sample test was carried out in order to compare the opinions of two different groups, that is public opinion with professionals (practitioners and scientists in the field of architecture).
Most of the semantic scale measurements refer to specific aspects, with particular emphasis on those that relate only to the positive and negative effects associated with individual preferences. According to statistical analysis, the following five words with their antonyms can be used to characterize perceptual and aesthetic buildings: attractive, unattractive, novel, common, simple, complex, boring, interesting, like, dislike (Garip and Garip, Reference Garip and Garip2012).
Computational aesthetic methods utilize a software application of aesthetic measurement. Usually, the aesthetic measurement is based on the measure of order and complexity defined by Birkhoff. According to Birkhoff, the aesthetic value of objects is included in their visual advantages. In practice, both the aspects of order and complexity are defined depending on the class of objects which is subject to aesthetic evaluation. Visual quality is also perceived by aspects of visual design such as sequence, order, repetition, rhythm, balance, shape, size, scale, proportion, pattern, hierarchy, direction, and similarity (Tjalve, Reference Tjalve1979).
In this paper, aesthetic evaluation is based on Birkhoff's aesthetic measure for polygons Birkhoff (Reference Birkhoff1933) adapted for 3D solids (Tarko and Grabska, Reference Tarko and Grabska2011). Aesthetic criteria taken into account in our approach include soft criteria, like a number and diversity of object components, hard criteria like equilibrium, and sharp criteria like relations of order, that is, symmetry and alignment to the same plane. Symmetrical and harmonic forms with optimal equilibrium are preferred; however, some elements of chaos, that make the shape more interesting, may occur. Another soft criterion is adhering to specified design characteristics. The degree to which design characteristics are met is evaluated in respect to the ratio of the present patterns to the number of geons an object is built of. The proposed selection function prefers objects with higher aesthetic values (Kaplan, Reference Kaplan1987).
The successive steps of the proposed approach are as follows:
• phenotypes of architectural objects are described as configurations of basic solids,
• the design patterns corresponding to object characteristic features are specified,
• each phenotype is represented in the form of an attributed composition graph being its genotype,
• evolutionary algorithms act on genotypes,
• evolutionary operators (crossover and mutation), which are introduced to act on the graphs, are based on the specified design patterns,
• the values of the fitness function are determined by the fuzzy evaluation based on the Birkhoff's aesthetic measure and the degree to which design characteristics are met, and
• individuals with the highest scores (best fitted) are chosen for reproduction in the selection process.
This paper contributes to the field of computer-aided architectural design based on evolutionary algorithms by proposing evolutionary operators, which preserve design characteristic, and a fitness function, which is determined by the fuzzy evaluation of designs.
The paper is organized as follows. In the section “Object phenotype representation”, the recognition-by-components (RBC) perception model is explained, and phenotypes of architectural objects are presented as configurations of elementary shapes. In the section “Object genotype representation”, the representation of objects in the form of attributed composition graphs, which constitute genotypes for the evolutionary algorithm, is presented. Section “Evolutionary operators on graphs” contains the specification of graph-based mutation and crossover operators. The fitness function, which is based on the fuzzy evaluation of designs, and the selection function are described in the section “Fitness function”. Section “Implementation” describes the implementation of the approach and presents examples of designing buildings having desirable features specified by the design patterns. Finally, the conclusion is drawn.
Object phenotype representation
As we do not know how exactly aesthetic evaluation is performed by a human brain, it is very difficult to equip computer tools with proper rules of computing aesthetic values of architectural objects. Because the aesthetic evaluation of architectural objects is related to perception, it seems a promising solution to use a human visual perception model in order to assess the quality of phenotypes in an evolutionary algorithm focused on aesthetic values. There are two main perception theories. The view-dependent model concentrates on recognition based on memorized views of an object – identification occurs when the most similar view is found. The view-independent model assumes that object recognition is performed by dividing a perceived form into basic components and exploring their shapes and relations between them. Although probably both models take part in human perception, the second one appears to be more appropriate for the purpose of computational design (Wallendorf et al., Reference Wallendorf, Zinkhan, Zinkhan, Hirschman and Holbrook1981).
In our approach, a set of elementary shapes is used to construct phenotypes of architectural objects. This enables us to analyze the properties of object components and relations between them. On this basis, one can specify the fitness function, which prefers such hard-to-define elements of beauty like order, harmony, rhythm, coherence, etc. (Tjalve, Reference Tjalve1979; Gardner and Krishnamurti, Reference Gardner and Krishnamurti2008).
Architectural forms can be seen as configurations of some basic solids, which are determined on the basis of the RBC theory developed by Biederman (Reference Biederman1987). RBC assumes that most objects can be divided into elementary shapes called geons, characterized by lack of sharp concavities. Biederman distinguished 36 3D geon types, each of them defined by four non-accidental properties: cross-section edges (curved or straight), cross-section size change (constant, contract, or expand and contract), cross-section symmetry (vertical, vertical and rotational, or none), and axis type (straight or curved). These properties are easy to recognize independently of the point of view and cost of their perception is low. Except that, each geon can be also described by a set of metric properties, like size or location, which take a longer time to be processed and perception of them is prone to errors.
Figure 1 presents an example of geon types with different non-accidental properties. The solid shown in Figure 1a has straight edges, vertical and rotational cross-section symmetry, the constant cross-section size, and the straight axis. Figure 1b presents a geon with curved edges, no cross-section symmetry, the contracting cross-section size, and the straight axis. The geon shown in Figure 1c has curved edges, vertical and rotational cross-section symmetry, the contracting cross-section size, and the curved axis.
Fig. 1. Examples of geons.
Object recognition is performed by the analysis of geon types that compose an object and exploration of relations between geons. There are two main types of relations recognizable independently of the point of view: the end-to-end relation, in which two geons have a common surface (Fig. 2a), and the end-to-side relation, in which a surface of one geon is attached to the larger surface of another geon (Fig. 2b).
Fig. 2. Relations between geons: (a) end-to-end and (b) end-to-side.
Using geons as basic primitives offers at least two advantages. As geons are based on object properties that are viewpoint independent, a single geon specification describes an object from all possible viewpoints. Moreover, a relatively small set of geons forms an alphabet of shapes that can be combined to form complex objects, so the representation is efficient. On the other hand, using RBC theory, it may be difficult to produce a geons-and-relations description of a real object, as it does not provide a mechanism to reduce the complexities of real objects to geon shapes.
Our approach to evolutionary design is driven by design characteristics which should be present in the design object. It means that we aim at the automatic design process which preserves a set of elements that are characteristic or desirable for the object. It should be noted that in many cases, these elements must be arranged in some predefined way (Simon, Reference Simon and Eastman1975; Alexander et al., Reference Alexander, Ishikawa, Silverstein, Jacobson, Fiksdahl-King and Angel1977). We assume that the designer interactively selects parts of the initially created designs, which correspond to object characteristic features, and in this way specifies the design patterns. The system evaluates the degree to which design characteristics are met in respect to the ratio of the present patterns to the number of geons an object is built of.
In order to illustrate our approach to the design process, we have chosen a design task of creating prototypes of tiny houses, that is, dwelling units significantly smaller than an average house (Kilman, Reference Kilman2016). Figure 3 presents some examples of tiny house models, which have been used to form the initial population of the presented evolutionary program. The task specification assumes that each building should be equipped with a window and a terrace. These requirements are treated as patterns corresponding to object characteristic features. In each of the designs shown in Figure 3 several of these patterns are present, so they met design characteristics in some degree. Such patterns can be defined by the designer by simply selecting all the geons that constitute their shape. For instance, the block with a “window pattern” contains two geons arranged in the end-to-side relation. After selecting the geons to the pattern group, the designer may also specify values of attributes that are essential for the pattern. These can be both attributes describing non-accidental properties of geons (defining their types) and attributes describing their metric parameters like dimensions, dimensions ratios, and number of cross-section edges. Figure 4 presents one of the possible arrangements of geons used to define the block-with-a-“window pattern” with the list of required attributes. The attributes of the geon to the wall of which the window is adjacent (geon1) are not specified, which means it can be any type of solid. The window geon (geon2) has height attribute set to 1. This will result in components resembling planar figures yet still thick enough to be visible in the building structure.
Fig. 3. Examples of tiny houses.
Fig. 4. Definition of the block-with-a-“window pattern”.
Object genotype representation
The design process can be modeled by a search process. In evolutionary search evaluation of possible solutions enables the system to make decisions about which of them are useful to keep in future genetic algorithm cycles. This refinement step is often performed not on actual phenotypes but on their coded equivalents called genotypes.
The proposed approach uses composition graphs with bonds (Grabska and Borkowski, Reference Grabska and Borkowski1996) as the representation of design object phenotypes. Graph nodes represent components (parts) of the object being designed, bonds assigned to nodes represent component surfaces, while directed edges connecting bonds express relations between these surfaces. Nodes are labeled by the names of components (or types of components), and edges are labeled by the names of relations between them.
In case of designing buildings, graphs encode building genotypes. The graph nodes are labeled by the names of the building elements represented by geons. To each node, two groups of attributes are assigned. The attributes of the first group describe non-accidental properties of geons, while attributes of the second group describe their metric parameters. Node bonds represent types of geon surfaces, and their number varies depending on the cross-section shape. The edges labeled ee represent the end-to-end relation, the edges labeled es represent the end-to-side relation.
Figure 5 presents a composition graph representing the building phenotype shown in Figure 3a. Each node is labeled by a number representing a geon type (“0” is for geons with vertical and rotational symmetry, constant cross-section size, straight axis, and straight edges, while “2” is for geons with vertical symmetry, constant cross-section size, straight axis, and straight edges). Bonds labeled by letters represent geon surfaces. The line segments between nodes and bonds define the assignment of bonds to nodes. Bonds labeled “a” denote the bottom basis, “b” denote the top basis, and the others denote side surfaces of a geon. The edges are denoted by bold arrows. All graph edges are labeled by es. Two of them represent connections between the bottom surface of the upper cuboid with the top surfaces of the middle cuboids, two of them represent connections between bottom surfaces of the middle cuboids and the top surface of the lower cuboid, while three others represent connections of window geons to the side surfaces of cuboids.
Fig. 5. A composition graph representation of the building from Figure 3a.
As design objects are represented by composition graphs also patterns corresponding to characteristic features of objects should be represented by composition (sub)graphs (Ślusarczyk et al., Reference Ślusarczyk, Strug and Stasiak2016; Strug et al., Reference Strug, Ślusarczyk and Grabska2017). These patterns are first interactively specified by the designer in the created building forms as the result of his personal selection of the required features. It should be noted that the patterns are specified on the basis of their structure and in some cases also some conditions on attributes have to be satisfied.
Figure 6a–c shows three examples of composition graphs representing fragments of buildings in which a window and a terrace are present. The first pattern represents a window connected to a side surface of a geon, the second one represents a window connected to the top surface of a geon, while the third one represents a terrace adjacent to a building block. To verify if the bottom geon represents a terrace, the value of the height attribute assigned to this geon should be checked. We assume it cannot be greater than 0.5 m.
Fig. 6. Examples of composition graphs representing patterns.
Evolutionary operators on graphs
As in this paper, an evolutionary algorithm acts on designed objects genotypes in the form of composition graphs, the genetic operators for such graphs have to be defined. The graph-based equivalent of a standard crossover operator requires establishing subgraphs that would be exchanged during the process of evolution. When a crossover is performed on two selected graphs, G and H, the subgraphs g and h, respectively, are selected in these graphs. Then, each subgraph is removed from a graph and inserted into the second one. As a result, two new graphs are generated. However, there may exist edges connecting nodes belonging to a chosen subgraph with nodes which do not belong to it. Such edges are called embedding of a subgraph. So, removing a subgraph from a graph and placing it in another one requires a method allowing for proper reconnection of these edges. The underlying idea is that all edges should be reconnected to nodes representing similar components as nodes they were connected to in the graph from which they were removed. The similarity of components represented by graph nodes is defined on the basis of node labels. It is assumed that nodes with the same labels correspond to similar components, as they represent the same type of geons. In cases when such reconnection is impossible, the dangling edges are removed.
It is important to notice, however, that the graphs to be crossed over and their respective subgraphs are selected during the execution of the evolutionary algorithms, so the embedding transformations cannot be defined a priori (as it is in graph grammars (Rozenberg, Reference Rozenberg1997)). The idea behind the algorithm that generates automatically such embedding transformations is to preserve the relations between the nodes as much as possible, that is to connect each edge removed from one graph to a node in the second graph that represents the same or similar object (i.e., has the same label) (Strug et al., Reference Strug, Grabska and Ślusarczyk2014).
In addition to dealing with the graph embedding problem, in case of using the evolutionary process to generate designs adhering to specified characteristics an additional step must be performed. During the process of selecting subgraphs in graphs to be crossed over, it is possible that the subgraphs (called patterns) representing object characteristic features will be broken. As a result, new graphs generated by the genetic operator could not represent designs having specific features. To prevent such a situation, we introduce the notion of an unbreakable subgraph. An unbreakable subgraph is a subgraph, which represents a predefined characteristic. At the outset of a design process, a set of unbreakable subgraphs associated with a given set of characteristics is specified. Then, in each graph G representing a design all unbreakable subgraphs are found and stored together with their position in the design in a set B G.
After selecting two graphs G and H to be crossed over, its subgraphs g and h are selected. In the first step, a starting node v is selected in graph G, and a similar node w is selected in graph H. Each of these nodes represents a geon located on the ground (a ground geon), which is indicated by a metric attribute defining the location of its bottom basis. Then, two numbers, i and j, are randomly chosen for the size of the subgraphs in both G and H. Then, in graph G starting from node v, we select adjacent nodes until the subgraph built reaches i nodes. Each time a node x is selected in G to be added to the subgraph g, it is checked against the set B G to verify if it belongs to any of the unbreakable patterns. If no, it is added to subgraph g and the selection of the subsequent node is performed. If node x belongs to some pattern, either the whole pattern has to be added to subgraph g being generated or none of its nodes. This decision is based on the size of the subgraph. If adding the whole pattern would not exceed the selected size i of subgraph g it can be added; otherwise, node x is not added to subgraph g and the selection process is continued. If the whole pattern is added to g, it is also added to the set of unbreakable patterns B g associated with g and removed from the set B G associated with G. Similarly, in graph H, a subgraph is built starting from node w. As a result, we obtain two subgraphs, g and h, and at the same time, two sets of unbreakable patterns, B g and B h.
Having selected the two subgraphs, a crossover operation can be performed. Formally, a crossover operator cx is defined as a 6-tuple (G, H, g, h, T, U), where G, H, g, and h are graphs and their subgraphs, selected for crossover, respectively. Thus,
• G = (V G, E G),
• H = (V H, E H),
• g = (V g, E g),
• h = (V h, E h), where
• V g ⊂ V G, V h ⊂ V H,
• E g ⊂ E G′E h ⊂ E H.
The crucial elements of this operator are T and U that are called embedding transformations, that is, they describe how edges of the embedding are to be reconnected. They are sets of pairs of the form (n, n′), where n denotes a node to which an edge was assigned originally and n′ is the one to which it will be assigned in a new graph.
As a result of the crossover, we obtain two graphs G′ and H′. Graph G′ is constructed in such a way that it contains all nodes and edges remaining from G after removing g, all nodes and edges from h and edges connecting nodes from G–g and h obtained by applying transformation T. Thus,
•
${G}^{\prime} = (V_G-V_g\cup V_h\comma \,{\rm } E_G-E_g-{\rm Emb}(g\comma \,G)\cup E_h\cup E_T)\,\,{\rm and}$•
${H}^{\prime} = (V_H-V_h\cup V_g\comma \,{\rm } E_H-E_h-{\rm Emb}(h\comma \,H)\cup E_g\cup E_U)\comma \,$where Emb(x,X) is the set of all edges having one end in set x and another one in set X, that is the embedding of the subgraph x in the graph X.
Sets E T and E U represent sets of new edges generated by the application of the embedding transformations U and T, respectively.
Moreover, the set B G' is obtained by summing sets B G and B h. In an identical way, graph H′ is constructed from H–h and g and set B H' from sets B H and B g.
In Figure 7a,b, two buildings and their corresponding composition graphs chosen for reproduction are depicted. On both of them, design patterns representing selected characteristics are marked by the dashed line, and subgraphs g and h selected for the crossover operation are marked with the thick solid line. In both composition graphs, the selected subgraphs contain one of the unbreakable patterns. After the crossover, two new graphs are constructed according to the method described above. Building phenotypes and their composition graphs obtained after the crossover operation on composition graphs shown in Figure 7a,b are presented in Figure 8a,b.
Fig. 7. Two buildings chosen for reproduction and their composition graphs.
Fig. 8. Two composition graphs obtained after the crossover operation on graphs from Figure 6 and their corresponding building phenotypes.
In order to introduce new features to the population, the evolutionary algorithm uses a mutation operator. In this paper, the mutation operator can modify the graph structure by deleting and adding nodes, changing a relation type, changing an attribute value of a single geon (which in case of attributes describing non-accidental properties results in a new geon type), or changing an attribute value in all the geons of the selected type. The examples of these four types of mutation in the building from Figure 3a are shown in Figure 9a–d, respectively. Beneficial mutations have a chance to be copied into the next generations.
Fig. 9. Examples of mutation in the building from Figure 3a.
Fitness function
The best-fitted individuals are chosen for reproduction during the selection process. In this paper, a fitness function is determined by the fuzzy evaluation of designs, which determines to what degree each phenotype fulfills aesthetic criteria and adheres to specified design characteristics.
As it has been considered, the proposed aesthetic evaluation of architectural objects is associated with visual perception. This way of evaluation is closely related to the intuitive appreciation of aesthetic preferences, which plays an important role in the practical rating of architectural designs (Scruton, Reference Scruton1979). The intuitive approach can be an element of a common sense in architectural analysis. For instance, the human sense of balance, that is the concept of visual equilibrium, is innate. The effect of unbalanced architectural objects causes anxiety and lack of comfort (Gardner and Krishnamurti, Reference Gardner and Krishnamurti2008).
Many criteria and requirements determined in the specification of the designed architectural form are soft, that is, they are to be fulfilled in some degree. There are also hard criteria and requirements, which are to be fully satisfied, and sharp ones, the fulfillment of which would be desirable but is not absolutely necessary.
In our approach, aesthetic evaluation is based on Birkhoff's aesthetic measure for polygons adapted for 3D solids (Mars and Grabska, Reference Mars and Grabska2015). Human sense of aesthetics correlates with our urge for gathering information about the environment. Therefore, the presence of some kind of order increases the aesthetic quality of an object; however, a highly ordered structure may not deliver enough information, as it can be too predictable. It is essential then to ensure optimal balance between the unexpected and the ordered.
Aesthetic criteria taken into account in our approach include soft criteria, like a number and diversity of object components, hard criteria like equilibrium, and sharp criteria like relations of order, that is, symmetry and alignment to the same plane. Symmetrical and harmonic forms with optimal equilibrium are preferred; however, some elements of chaos, that make the shape more interesting, may occur.
Another soft criterion is adhering to specified design characteristics. It is not necessary for the designed object to contain all of the elements marked by the designer in order to preserve the required characteristics, although the high degree of satisfying design characteristics is desirable. As we have sets of patterns associated with newly generated graphs, we are able to evaluate the degree to which design characteristics are met by the designed objects by calculating the values of the membership function specified for the ratio of the present patterns to the number of geons an object is built of. The individuals who do not have any desirable characteristic features are removed from the population.
To obtain this result, we construct a fuzzy fitness function that rewards the following:
1) equilibrium existence,
2) the high degree of satisfying design characteristics,
3) the medium degree of fullfillment of relations of order, that is, symmetry and alignment to the same plane (the membership function is computed for the number of satisfied relations of the same type in respect to the number of geons in these relations), and
4) the rather low number of types of geons used.
The first condition concerns both an aesthetic and a functional requirement of an architectural object and enables us to obtain a prototype that is possible to be built. The second condition ensures that the building satisfies some design characteristics. In the result of the third condition, objects with the average number of different relations of order in which a high number of geons takes part are preferred, which enables novelty, as some geons of the solid are arranged in a different way than others, and at the same time, the coefficient of chaos decreases. The fourth condition ensures the diversity of components and at the same time prevents confusion, inevitable when an object consists of too many different elements.
Let us specify the following components of the fitness function:
• equilibrium E which is equal to 0 or 1,
• the degree S of the high satisfaction of design characteristics, computed according to the membership function for the term high specified for the ratio of the present patterns to the number of geons an object is built of (denoted by n). This function is shown in Figure 10. It should be noted that phenotypes can satisfy design characteristics in different degrees, as their genotypes can contain many different unbreakable subgraphs.
• the degree of alignment A, where the membership function is presented in Figure 11, is computed for the number of satisfied relations of alignment type in respect to the number of geons in these relations. On the x-axis, there is the ratio of the number of alignment relations between object's geons (i.e., a number of different planes and lines geons are aligned to) to the number of geons which take part in these relations, where the number of geons an object is built of is denoted as n,
• the degree of vertical symmetry V, and the degree of rotational symmetry R, where the number of relations of vertical symmetry between object's geons is understood as the number of different vertical axes of symmetry in the object and number of relations of rotational symmetry between object's geons is understood as the number of different axes of rotational symmetry in an object, are computed in the same way as A,
• the degree T of the low number of geon types used, is computed according to the membership function for the term low number, which is shown in Figure 12. The number of possible geon types is equal to 36, while the value low characterizing the number of geons used denotes the number from 1 to 4.
Fig. 10. A membership function of the term high describing the satisfaction of design characteristics.
Fig. 11. A membership function for the order relations.
Fig. 12. A membership function of the term low describing the number of geons used.
The fitness function of the proposed algorithm is defined by the formula:
$$M = E\; \ast\; S \;\ast \;\lpar {A + V + R + T} \rpar$$It should be noted that such components of the above formula like high satisfaction of design characteristics (S), the alignment of building geons (A), the satisfaction of symmetry relations (V, R), the low number of geons used (T) are computed in a fuzzy way using fuzzy set membership functions presented in Figures 10–12.
Figure 13 presents some results of computing the fuzzy fitness function for examples of buildings. The values of the fitness and the respective components of the formula used are shown in Table 1. The numbers in brackets in the form m/n, in columns A and V, denote the number (m) of relations present (alignment or symmetry) and the number (n) of geons which take part in these relations. The numbers in brackets in column T denote the number of geon types used. The value M for the fourth design (Fig. 13d) is the lowest one, as this form satisfies the design characteristics only in degree 0.45.
Fig. 13. Examples of buildings evaluated by the fitness function.
Table 1. The characteristics related to buildings presented in Figure 13
Implementation
The proposed approach has been implemented in Java with the use of Primefaces framework and run on the Apache Tomcat server. Javascript library three.js based on WebGL is used for visualization of building models, while vis.js library performs graph visualization.
The evolutionary algorithm starts with a population of individuals with the required features. Models of buildings composing the initial population are created by the user. Their number depends on the user's preferences, although it must be greater than three. The required features are indicated by the user, who selects geon configurations by clicking on adjacent geons of a building. Such configuration can be further edited by specifying required attribute values. By default, all non-accidental properties of geons are specified, and all metric properties are unrestricted. Figures 14–16 illustrate a process of defining the block-with-a-“window pattern”. Default settings of the chosen geon configuration (geons in dark gray in Fig. 14) are presented in Figure 15. In this configuration, the window geon (Geon2) is defined as a prism attached to another prism (Geon1). The modified settings presented in Figure 16 allow for any type of the window geon providing that the axis height is 1, which means the solid is almost planar. The window geon can be attached to any type of geon.
Fig. 14. Geons chosen for the block-with-a-“window pattern”.
Fig. 15. Default settings of the block-with-a-“window pattern”.
Fig. 16. Modified settings of the block-with-a-“window pattern”.
Once the initial population is defined, its internal representation in the form of graphs is automatically generated and the evaluation is performed by the fitness function and individuals with the highest scores are chosen for reproduction. The crossover rate is 80%. The chosen individuals are randomly paired. Each pair produces two children with the use of the crossover operator. In random cases (the mutation rate is 5%), the mutation operator modifies a child. The new population is created from the reproducing pairs and their children. The resultant population is presented to the user, who can then select an option “Next generation”, which makes the whole process start again. Figure 17 shows some examples of individuals obtained during the evolution process with the initial population of the four buildings presented in Figure 3. The values of the fitness function and the respective components of the formula used to compute them for objects shown in Figure 17 are given in Table 2. It should be noted that on the contrary to numerical problems which have an optimal solution, in case of applying evolutionary methods to design processes the optimal design solution usually does not exist. Therefore, in our approach, the optimization of the fitness function values is less important than creative exploration of potential solutions. However, assessing the degree of creativity enhancement of the generated designs would require a test involving human designers.
Fig. 17. Examples of individuals generated during the evolution process.
Table 2. The characteristics related to buildings presented in Figure 17
Conclusion
The aim of this paper is to present a new approach to characteristic-oriented creative design evaluated in a fuzzy way. This approach is based on the combination of three methods – recognition, generation, and evaluation. The Biederman RBC theory is used to recognize the design structure. An evolutionary algorithm is proposed as a generative tool, which enables obtaining the variability of design structures enhancing the creativity of the design process. The proposed fuzzy evaluation mechanism takes into account both aesthetic criteria and the degree to which design requirements corresponding to object characteristic features are satisfied.
Aesthetic evaluation is strictly connected with visual perception. Therefore, it seems reasonable to combine aesthetic measure with an object recognition model in a generative tool that complies with aesthetic rules. RBC theory gives an opportunity to examine components and relations between them. Birkhoff's aesthetic measure adapted for 3D objects matches well with such an approach, as it is based on a similar examination, although it obviously does not cover every aspect of human aesthetic sense.
An evolutionary process has been used to stimulate the creativity of the designer and to suggest an aesthetic evaluation mechanism for architectural object prototypes encoded in the fitness function. A design structure of an architectonic object has been determined on the basis of the Biederman's structural skeleton of the object. This kind of higher-level structural analysis is a way of making clear genotype representations in the form of graphs.
As in the proposed approach, a composition graph is used as a genotype, equivalents of standard genetic operators are defined on graphs. These operators are more complex than standard binary ones, but they provide us with benefits like the possibility of coding relationships between components of an artifact and ability to introduce structural changes which compensate for it. The strongest point of a graph-based representation is its ability to represent in a uniform way all types of relations and objects, and to preserve some required characteristics of the design.
As most design problems involve several conflicting standards, in future we would like to specify weights determining the importance of the design criteria and requirements. Thus, even an incoherent and inconsistent design specification can be compatible with the specific project. The criteria weights have a huge impact on the subsequent assessments of project compliance with the specification.
In future research, the strength of unbreakability of patterns will be also defined. In this paper, none of the patterns designated as unbreakable can be broken. Yet, it can be observed that in some situations, it is possible that a given pattern is present in a graph multiple times; thus, breaking one of the occurrences would still allow for the required features to be preserved, but at the same time give possibly more freedom for creative results.
Further research will also deal with semi-automatic construction of a graph grammar on the basis of a given set of building models. Then, the initial population of buildings will be generated by means of this grammar. Sequences of the applied grammar rules can be used as genotypes in the proposed algorithm, and a crossover operation will be realized on such sequences.
It should be noted that the proposed method can be used to support creative engineering design of machines or products, represented as compositions of geons, as the evolutionary process generates variability of design structures which can be evaluated according to aesthetic criteria. However, for other applications of the presented method, there is a need to examine also semantic scale measurement (Garip and Garip, Reference Garip and Garip2012) and comparing them with the computational aesthetic method proposed in this paper. Comparison of the results of formal aesthetic measurements with an intuitive assessment of the same representatives of the given class of artifacts gives us the opportunity to modify the aesthetic measure depending on the type of application.
Ewa Grabska received her PhD (1982) in mathematics from the Jagiellonian University, and DSc (1997) in computer science from the Institute of Computer Science, Polish Academy of Sciences, and the title of professor from the President of Poland in 2013. Since 2008, she has been a professor at the Department of Physics, Astronomy and Applied Computer Science of the Jagiellonian University. Her research areas include computer-aided design, graph transformations, visual communication, computational ontology, engineering, and computer games.
Grażyna Ślusarczyk received her PhD degree in computer science from the Institute of Fundamental Technological Research, Polish Academy of Sciences, in 1999 and DSc in computer science from the Department of Automatic Control, Electronics and Computer Science of Silesian University of Technology in 2012. Since 2006, she has been working as an Assistant Professor at the Department of Physics, Astronomy and Applied Computer Science of the Jagiellonian University. Her research interests include computer-aided graphic design, visual languages, knowledge-based reasoning, evolutionary design, multi-agent systems, and graph grammars. She has published over 80 journal and conference papers on these subjects.
Barbara Strug received her PhD in computer science from the Institute of Fundamental Technological Research, Polish Academy of Sciences, in 2002 and DSc in computer science from the Department of Applied Computer Science, AGH University of Science and Technology, Kraków, in 2014. She is an Assistant Professor at the Department of Physics, Astronomy and Applied Computer Science of the Jagiellonian University. Her research interests include computer-aided design, knowledge representation, graph-based representation and graph transformations, graph mining and graph kernels. She is an author of over 80 papers and attended numerous conferences. She is a member of ACM.
Agnieszka Mars is a PhD student and a research assistant at the Department of Physics, Astronomy and Applied Computer Science of the Jagiellonian University in Kraków. Her research interests include computer-aided design and artificial creativity.
