نمایندگی کلی غیر مستقیم برای بهینه سازی سیستم طراحی مولد توسط الگوریتم های ژنتیکی: برنامه برای طراحی سیستم مبتنی بر دستور زبان

Generative design systems coupled with objective functions can be efficiently explored through the use of stochastic optimization algorithms, such as genetic algorithms. The first step in implementing genetic algorithms is to define a representation, that is, the data structure representative of the genotype space and its mathematical relation to the data of the phenotype space — the variables of the real problem. This can be a hard task, particularly if the design system contains dependency between variables. This paper presents a general representation, which enables the use of standard variation operators, allows defining both continuous and discrete variables from a single type of gene and is easily adaptable to different problems, with a larger or smaller number of variables. This representation was created to solve the representation problem in the design system for Frank Lloyd Wright's prairie houses, a shape grammar that was converted into a parametric design system.

A generative design system is a model composed of a set of computational rules that are applied to generate alternative designs [1], [2] and [3]. In addition to enabling the desired design variety, rules encode constraints to create only the intended output. Therefore, through a well-designed system of rules, generative design systems have the capability of maintaining stylistic coherence and design identity while generating diverse designs. The advantage of having alternative designs is to allow choosing the one that better fits a certain context or achieves a defined objective. Frequently, this can be translated into an objective function, linked to the design system. Within the flexibility of the design system, variables (in the form of rule applications and/or parameters) can be edited to improve the value of the objective function, looking for the best performing design. However, for a large number of variables, search algorithms are a much more efficient method to explore the solution space. Of course, this requires design systems to be programmed in numerical computing languages. Exhaustive search is the ideal method for small solution spaces. Exact optimization algorithms, such as linear programming, branch-and-bound and dynamic programming, are very proficient in finding the best solution in convex solution spaces. However, in general, generative design systems involve very large and non-convex solution spaces. Therefore, stochastic optimization algorithms are the most appropriate search method, even though they do not guarantee finding the global optimal solution. Among them, genetic algorithms have been proven to find high quality solutions in large solution spaces and in reasonable time periods [4]. The first step in solving an optimization problem with genetic algorithms is to define an adequate representation and a corresponding genotype–phenotype mapping. The real-world problem involves variables. Genetic algorithms work with genes, the corresponding entities for the variables. The representation is the definition of the genes and the genotype–phenotype mapping is the mathematical relation between genes and variables. The informal term “genetification” is sometimes used as a mnemonic for the task of creating the representation and the genotype–phenotype mapping. The two main requirements for a representation are encoding all the possible solutions of the problem and enabling the application of the variation operators to them (crossover and mutation). Although some bibliography focuses specifically on this subject, crafting or choosing an adequate representation is not an easy task, since it is still the result of intuitive analysis and the latter depends on some experience in the field [5]. The motivation for the research presented in this paper was the problem of finding an adequate representation for the design system for Frank Lloyd Wright's prairie houses, with its optimization in foresight [6] and [7]. The objective function for the design optimization problem, provided that it involves a non-convex solution space, is independent from the representation and its requirements. Several objective functions are possible, ranging from simple geometric features – like footprint area, external surface, volume, etc. – to more complex performance measures, like energy consumption [8], daylight illuminance [9], acoustic performance [10], structural fitness [11], and so on. Although coupling design systems and genetic algorithms is not a novel approach, this specific study entailed some singularities. The design system for Frank Lloyd Wright's prairie houses is a shape grammar. Although a conversion method was outlined in [7], for converting the grammar (a non-numerical design system) into a parametric design system (a numerical design system), the latter, among other characteristics, contains dependency between variables. Consequences of this characteristic restrict the use of the most obvious representation, the direct representation [5], unless customized, problem-specific, variation operators are crafted. However, the objective of this study was solving not only this one problem but also to create a general representation and corresponding genotype–phenotype mapping, which could be implemented on other design systems with similar characteristics. As such, an essential feature for this representation was to use standard variation operators [4], such as those included in common commercial optimization tools. The literature already includes some examples of coupling shape grammars with genetic algorithms, but in none the representation was sufficiently explicit or generic to enable its application to this design system. In [12], a direct representation was used and variation operators were customized to the problem. In [13], the representation used is not explicit. Nevertheless, it does not cover all the variables of the design system, since some variables remain constant during the optimization runtime, due to limitations of the software used. This means that the optimization process, in each run, is not exploring all the solution spaces but only part of it. In [14], tree data structures are used in the representation, each tree being formed by a different number of nodes. This representation was crafted for a shape grammar composed of one rule only, which basically divides a shape into two, and this can be repeated indefinitely. Although interesting, this representation is not adequate for Frank Lloyd Wright's design system, due to large differences between the two grammars. The design system presented in [15] is not a shape grammar, it is a parametric design system, but its constrained structure, in which “each variable is associated with explicit upper and lower limits”, resembles the structure of the converted Frank Lloyd Wright's design system, presented in [7]. In addition, this design system also involves defining continuous and discrete variables to generate designs. A direct representation was used but, in this case, it was possible to apply a standard crossover and a standard mutation (however, not all standard variation operators could be applied). An analogous representation could be crafted for Frank Lloyd Wright's design system, although this would not be generic, as intended. The representation proposed here can be seen as a generalization of this one. The remainder of the paper is organized in the following way. Section 2 presents the grammar for Frank Lloyd Wright's prairie houses and its conversion to a parametric design system. Section 3 explains the problem that the representation must solve. Section 4 presents and discusses the proposed representation. Section 5 validates the proposed representation, by solving the identified problem and successfully being used in an optimization problem. Section 6 draws the main conclusions from this study.

This paper presents a general indirect representation for optimization of generative design systems by genetic algorithms. This representation enables the use of standard variation operators, such as those included in common commercial optimization tools, allows defining both continuous and discrete variables from a single type of gene and is easily adaptable to different problems, with a larger or smaller number of variables. Besides being generic, this representation is very simple to apply. These two qualities make it very useful for inexperienced optimization users, who wish to find optimal design solutions to some objective function, for instance, energy consumption or daylight illuminance. The proposed indirect representation involves genotypes represented by arrays, of equal size, of floating-point values defined in the [0, 1] interval and a genotype–phenotype mapping composed of three linear equations and a rounding function. Any combination of values within the [0, 1] interval is possible to form a genotype (resulting from crossover or mutation), therefore, any variation operators may be used. The genotype–phenotype mapping is basically a routine called by the design system program each time the value of a variable has to be defined. For each variable, the genotype–phenotype mapping requires, besides the gene from the genotype, the input from the design system program of the inferior and superior limits of the range of the variable and an increment, which allows the genotype–phenotype mapping to define both continuous and discrete variables. This representation was created to solve the representation problem in the design system for Frank Lloyd Wright's prairie houses, a shape grammar that was converted into a parametric design system. Due to the consequences of dependency between variables in the design system, it was shown that using a direct representation would disable the application of standard crossover operators. Using the proposed indirect representation, a standard crossover was successfully applied. In addition, this representation was used in solving an optimization problem by a genetic algorithm of a commercial tool, containing standard variation operators. This design system generates phenotypes of different sizes. This representation, requiring genotypes of equal size, when applied to it, entails redundancy and epistasis, both undesirable in optimization problems. These could be avoided or minimized by using a direct (or problem-specific) representation. In summary, the adverse effects of redundancy and epistasis are the cost of having a general representation. Further research would be necessary to determine if the benefits derived compensate this cost.