SECTION VIII – Evolutionary computing
2. Basic notions of EC in the context of a generative design system
GENOTYPE AND PHENOTYPE
The individual in a population is called a phenotype while information necessary to build the individual is called a genotype. The genotype encodes the phenotype. In the process of natural selection, the phenotypic traits are considered (such as individual’s strength, speed, hunting skills, ability to conceal etc.) defining the individual fitness. But it is the genotype that undergoes modifications during reproduction.
In terminology of a design process, the phenotype finds its analogue in the building model, and the phenotypic features in the building
characteristics. The genotype has no direct analogue. In order to apply EC into design generation, one needs to construct a genotype, i.e., to find a way of encoding the building model.
GROWTH FUNCTION
The function that builds the phenotype using the genotype as an input parameter is called the growth function. Constructing the phenotypes and the genotypes in terms of mathematical objects is a significant challenge. Some guidelines of how the phenotype (the building model) should be constructed are given in section V.3.
In the generative design system, the growth function should allow generation of a possibly broad set of building models, or in EC terms, it should secure a possibly large search space. It should not block the
development of some of the building models, because of the limitations in its definition.
To ensure the near-decomposability of a building model, it is desirable to create a growth function that would produce hierarchically structured phenotypes. The transition from a genotype to a phenotype should yield building elements that are grouped. Each modification of a genotype should result in a reconfiguration of groups of elements rather than building elements.
Finally, the growth function should be implemented in a way that discards spatially deficient building models, i.e., models that include spatial errors or inconsistencies such as overlapping spaces (overlapping windows, doors, rooms)32. It should also ensure that all the necessary building elements are
32Alternatively, the spatially inconsistent building models can be discarded by a technique called penalty function. The penalty function is discussed later.
present in a building model. For example, each room must be connected to at least one another room; and there should be at least one entrance to the building.
MODIFICATION AND SELECTION
In the evolutionary process, individuals strive for survival, and those best fitted reproduce and transfer their characteristics to their offspring. To ensure optimal development, these characteristics are not only copied, but also modified by a mutation or a recombination. The mutation is a change of randomly selected elements of the genotype. In the recombination, fragments of genotypes of two different individuals are combined to form a new genotype. It is important that the modification process happens at the genotypic level, while selection is based on phenotypes.
Accordingly, two mechanisms take place in the evolutionary processes:
modification and selection. These mechanisms improve the fitness of individuals in successive populations. The modification creates the necessary diversity within the population (providing a novelty) while the selection increases the average quality of solutions (Eiben and Smith, 2007: 16).
ADAPTIVE LANDSCAPE – LOCAL OPTIMUM AND GLOBAL OPTIMUM
The relationship between the fitness of a building model and its
characteristics can be represented graphically. In a simplified scenario, where there is only one design objective, for example a building footprint 100m2, the graph would be a 2-D curve. In figure 13, the vertical axis represents the building model fitness and the horizontal axis represents the different configurations of building elements, resulting in a different footprint area (a building characteristic).
Figure 13. An adaptive landscape of a building model with one characteristic (footprint of a building).
When there is more than one building characteristic (which is usually the case), the line becomes a surface (figure 14) or generally a multidimensional space. The line, the surface or the space is called an adaptive landscape.
Figure 14. An adaptive landscape of a building model with two characteristics (footprint of a building and building cost). The design intention is a building footprint of about 100m2 and possibly low building cost. In this figure, the degree of fitness of a building model is indicated by more or less darker shades of grey. The cost of a building cannot drop beyond a certain level, which is indicated by the white shape at the bottom of the figure.
In complex combinations of building characteristics, finding the most fitted building model can be difficult. There could be many building models of comparably high fitness, positioned in very different places on the adaptive landscape. Each of these models would satisfy different set of design objectives. For example, one building model can suit the functional requirements – space adjacencies, room distribution and room area – but at the same time be energy inefficient. Another building model can meet aesthetic expectations, but it can be expensive. Both of them might have
similar fitness, but their position on the landscape would be different. And, both would be represented in a form of ‘peaks’ on the adaptive landscapes.
So, the fact that a building model is placed ‘higher’ on the adaptive landscape than its neighbours does not mean that there is no other, better fitted building model. The best-fitted models in the fragment of adaptive landscape are referred to as local optima, while the best-fitted model in the whole adaptive landscape is referred to as a global optimum.
Figure 15. A local optimum and a global optimum.
Figure 15 illustrates the concept of a global and a local optimum in the context of generating a building model. The configuration of rooms is the only design objective. On the diagram, the horizontal axis represents building models that have different configurations of rooms. The vertical axis
represents fitness of a building model with the design intention. The hatched area represents the scope of building models that have been generated and examined in the hypothetic generative design process. Even a relatively good configuration of rooms obtained in the process (local optimum M on the diagram) does not guarantee that there is no better solution (global optimum G on the diagram).
The building models that lie close to model M on the diagram are its small modifications. It is apparent, that in order to generate model G, the system needs to intensely modify model M.
Alternatively, in the context of an ordinary design process, one can assume, that model M is developed by a designer, based on his or her intuition and skill. The hatched area would represent a designer’s scope of anticipation of alternative building models. The designer can anticipate only these alternatives that are relatively small modifications of building model M, and which thus lie in the neighbourhood of M. According to this diagram, the designer is unable to assess the quality of the models, which are large modifications of M (which lie outside the neighbourhood of M). In order to develop a better building model, the designer needs to introduce a large modification to model M, which would correspond to a considerable repositioning on the adaptive landscape.
GENETIC DRIFT
In connection with the adaptive landscapes that contain a number of local optima, it is worthwhile to mention a phenomenon called a genetic drift. This phenomenon is undesirable, because it might reduce diversity in a population of building models.
Often, two (or more) building models are almost equally fitted, but they owe their fitness to different set of building elements. Building models J and M on figure 16 lie on different positions on the adaptive landscape. However, because these building models are never equally well fitted (here M is slightly better), the probability that the offspring of the fitter will be more numerous is greater. This effect will be even stronger in the next cycle, and will gradually eliminate the offspring of the less fitted building model (model J). Consequently, this would deprive the population of its variety, neglecting potentially desirable building models. The effect of the genetic drift would
‘push’ the population development in undesired direction. The initial
population containing the two building models would eventually ‘stick’ to the local optimum, as the offspring of the model J would disappear from the population. Even though the building model M is best fitted at the outset of generation process, the development of J is more beneficial, as it is closer to the global optimum.
Figure 16. Genetic drift – a population might lose highly fitted individuals (J) that are close to the global optimum, following the proliferation of other highly fitted individuals (M).
In the context of the ordinary design practice, the design process, which starts with two or more competing versions of a building model, can end up too quickly in only one version of the building model. Focusing on one solution might rule out other, potentially even better solutions, too soon.
PREMATURE CONVERGENCE
Looking at the selection and the modification from another perspective, the selection can be described in terms of exploitation, as it narrows down and focuses the search, while modification might be described in terms of exploration, as it shifts the focus of the search. In this context, the evolutionary search can be seen as a trade-off between exploration and exploitation. Too much exploration leads to inefficient search, and too much exploitation narrows down the scope of the search too quickly (Eiben and Smith, 2007: 29). Extensive exploitation might cause a phenomenon termed a premature convergence. This happens when the population loses variety too rapidly and reaches only the nearest local optimum.
The analogue to premature convergence might take place in an ordinary design process as well. If during the early, conceptual design phase, no alternative building models were tested, then there would be a great chance
that the project would not develop its full potential. In figure 17, instead of exploring many diverse alternatives, the search resources are focused on six relatively similar building models (K, L, M, N, O, P), which encompass a narrow area of the adaptive landscape. Here, the design exploitation
dominates over the design exploration. Even though a fairly good solution is found very quickly (building model O) it is only a local optimum.
Unfortunately, the potential of this design situation is only partially realised – the global optimum is not found.
Figure 17. Exploitation. The search resources are focused on relatively small area of the adaptive landscape.
Figure 18 illustrates a different situation. As in the previous scenario, the resources are the same and they include six building models (C, G, J, M, P and S). However, now these models are allocated over a much broader area of the adaptive landscape. Three best-fitted building models – G, P and S – are selected for further development. The diversity of the initial set of building models (the fact that they are dispersed across a large area of the adaptive landscape) made it possible to discover the global optimum (which is in the neighbourhood of the model S).
Comparing this example of exploration to the previous example of exploitation, here the initially best-fitted model P is weaker than the initially best-fitted model O in exploitation. Nevertheless, after a few modification
steps in the exploration scenario, the model S ‘climbs up’ the hill, quickly overrating the model O, which is ‘trapped’ in the local optimum.
Figure 18. Exploration. The search resources are allocated over large area of the adaptive landscape.