3.1. Knowledge-rich evolution

Some ways of changing an evolutionary algorithm to add design knowledge include the specification of the selection process used to select individuals for reproduction, operators that perform reproduction, termination criteria to halt an evolutionary run, and the type of evolutionary algorithm.

Knowledge can be added to an evolutionary algorithm by using custom reproductive processes that increase the likelihood that good, or at least viable, individuals are created. This approach is particularly useful if standard evolutionary algorithms prove inefficient because many invalid individuals are created that must still be evaluated, slowing the exploration of useful areas of the design space. New reproductive operators can be as simple as ones that guard against creating invalid data structures, or they can be as complex as local search algorithms that perform local hill climbing, as in the case of memetic algorithms (Moscato, 1989). This approach is quite flexible and can be used to add knowledge that is specific only to the type of data structure being evolved or to the domain.

Some restraint should be exercised when applying domain-specific reproductive operators. One of the advantages of using evolutionary algorithms is that they can discover solutions that are unexpected by the implementer of the evolutionary system. The more knowledge that is added to the evolutionary algorithm in the form of heuristics restricting the search of a design space, the less likely the evolutionary system will discover unexpected solutions.

For problems that require the application of tacit knowledge or aesthetic judgments, a designer may chose to interact with the evolutionary process by providing subjective evaluations instead of a mathematical function (Sims, 1991). This can be accomplished by having the design enter a fitness value on a numerical scale that is translated into a fitness measure by scaling the value to a standard range and optionally combining it with other fitness measures (Witbrock & Reilly, 1999).

Alternatively, a designer can interact more directly with an evolutionary process by selecting which individuals in a population will survive to reproduce and form the next generation. Examples of this are the biomorphs of Dawkins (1986) and the selection of art alternatives by Todd and Latham (1992). Rosenman (1996, 1997) has the designer selecting possible candidates for solutions to components to be used in the next level assembly. Although interactive approaches allow subjective judgments, they slow the process and should be replaced by computational evaluation, if possible.

A more direct approach to incorporate knowledge into an evolutionary design system is to use a traditional knowledge-intensive approach to guide the progress of an evolutionary algorithm. In this hybrid model, an expert system, case-based reasoning system, or some other form of knowledge-rich, domain-specific design system would assist in the selection and adjustment of various aspects of the evolutionary design system in response to the particulars of a design problem.

The problem with adding significant amounts of domain knowledge to evolutionary algorithms is that they begin to lose their advantages as knowledge-lean models for nonroutine design. Although each piece of domain-specific knowledge that is added has the potential to produce a more powerful specialized problem solver, it also limits the possible forms that the evolutionary design system can generate. The evolution of unexpected solutions to design problems has been one of the hallmarks of evolutionary design to the extent that some observers have proposed that evolutionary design systems appear to be creative (Bentley, 1999; Goldberg, 1999). Adding excessive domain knowledge can strip the evolutionary algorithm of this ability, and the model returns to one of a knowledge-intensive optimization process that is more akin to routine designing.

3.2. Knowledge-efficient evolution

A second approach to improving the handling of design knowledge in evolutionary algorithms is to improve the efficiency of their use of existing knowledge. The advantage of this approach is that is allows the evolutionary algorithm to remain knowledge lean, thereby maintaining the greatest scope for evolving innovative solutions. Knowledge-lean evolutionary algorithms do not rule out the possibility of using knowledge-rich techniques at a later date. Increasing the efficiency with which an evolutionary algorithm uses domain knowledge generally involves some sort of adaptation or learning (i.e., the evolutionary algorithm must adapt the domain knowledge it is given to the specifics of the evolutionary run).

Genetic engineering (Schnier & Gero, 1996) is a good example of adapting representations during evolutionary search. Genetic engineering is founded upon the schema analysis of Holland (1975) and the building block hypothesis of Goldberg (1989). Genetic engineering uses statistical analyses of the genotypes evolved to find the most useful “building blocks” that emerge during an evolutionary run. The genetic engineering system finds the building blocks that appear most frequently in fit designs, extracts them from the genotypes, and encapsulates them as evolved genes. These evolved genes are then used to replace existing sequences of genes for the construction of new genotypes. This process of extracting useful building blocks and encapsulating them as evolved genes safeguards the knowledge represented by the schema from future disruption. The genetic engineering process allows the evolutionary system to explicitly code knowledge about useful design forms that is adapted to the specifics of the design problem.

3.3. Coevolution

Coevolution is the evolution of individuals within the context of other individuals either in the same population or in another population. Coevolution is pervasive in the natural world, with species being dependent on many other species for survival. A commonly cited case of coevolution is the “arms race” observed between species of predator and prey. Coevolution promises to solve the problem of providing context-sensitive information without the need to add complex context-sensitive fitness functions. The next two subsections give detailed descriptions of two coevolutionary approaches.

Maher and Poon (1996) proposed coevolutionary design models for nonroutine designing that use coevolution to evolve problems and solutions in tandem, permitting the exploration of a wide range of possible forms to a class of problems. They argue that designing is an iterative process of searching the design problem space, as well as the design solution space. The coevolutionary model of design searches both the problem space and the solution (design) space in tandem. The most important aspects of the coevolutionary model of design are that solutions are evaluated in the context of the evolved problems and problems are evaluated in the context of the evolved solutions. As a consequence, design proceeds as a compromise between solving the criteria for the design problem and altering the problem to suit the solutions at hand. In this way the coevolutionary process transforms an ill-defined problem that lacks the knowledge necessary to determine the relative importance of the criteria into a well-defined problem that can be solved using the resources available. The problem and solution search processes cooperate to solve an ill-defined problem in an efficient manner.

Potter and De Jong (1994) have proposed a quite different type of cooperative coevolution to evolve solutions by splitting up the evolutionary search of a single complex solution space into separate evolutionary processes that each search simpler solution spaces and cooperate to produce a complete solution.

In the cooperative coevolution genetic algorithm (CCGA), a problem is decomposed into a set of simpler problems, each of which is tackled by a separate evolutionary process. Information is implicitly communicated between evolutionary processes through the use of a shared fitness function. The shared fitness function provides a measure of how well each component works within the context of the other components evolved to solve the complete problem. This is accomplished by selecting representatives from each population and combining them into a single composite structure that can be evaluated by the single fitness function against the top level goal. Credit from evaluating the composite structure flows back to the individual subcomponents to reflect how well they collaborate with the other subcomponents to achieve the top level goal. Each individual solution is therefore evaluated within the context of the representative best solutions at the current time. As a consequence, the best solutions have a great deal of influence on the evolution of other components.

Like the coevolutionary design algorithm, the CCGA uses representatives, or collaborators, from each population to cooperate in solving the design problem. However, in this model, the representatives collaborate to form a complete solution rather than forming a problem–solution pairing. Selecting representatives in either approach can be done in many ways, but it is most easily done by selecting the member with the highest fitness value from each collaborating population.

Potter and De Jong (1994) have demonstrated their approach to evolutionary design in a variety of domains and have shown it to be effective. However, the problems tackled thus far with the CCGA have not been decompositions in the same sense that a designer might decompose a design problem in terms of subcomponents of different kinds that have their own specific requirements; instead, they are in terms of subsets of a set of similar elements that have the same requirements as the composite structure. The composite structure is an aggregate of like atomic elements, not “functional” components with differing requirements.

Chen and Brown (2002) have proposed a two-layered system in which components are generated and evaluated according to their success in making up a successful configuration. This work is demonstrated in the configuration of pipes on a Cartesian plane. It is limited to two levels.

5.1. Intrinsic and extrinsic fitness

Hierarchical evolution and cooperative coevolution share the concept of problem decomposition, although they differ to the degree to which the decomposition is applied. However, they have quite different means of defining evaluation criteria: hierarchical evolution evaluates components according to criteria defined at the component level, whereas cooperative coevolution evaluates components only at the superior problem level. The coevolutionary model of design developed by Maher and Poon (1996) is closer to hierarchical evolution in this regard. Even though it appears to evaluate both problem and solution at the same time, evolutionary searches are treated as independent “components” of the design situation and are evolved using quite separate fitness functions.

Hierarchical coevolution combines these two means of evaluating individuals by defining two types of fitness: intrinsic and extrinsic. Intrinsic fitness, as used by the evaluation criteria for hierarchical evolution, measures the success of a component to satisfy the criteria unique to its function. Evaluation criteria that define intrinsic fitness deal only with those aspects of the problem that affect a component directly. Extrinsic fitness, similar to the fitness evaluation in cooperative coevolution, measures the ability of components to cooperate with other components at the same level within the design situation of the immediately superior problem. Extrinsic fitness is the fitness of an individual with respect to its immediately superior assembly.

Representatives from the lower level component solution population are used to evolve new higher level problems by contributing to the intrinsic fitness evaluation of the higher level component solutions. In this way, the coevolutionary model of design exploration is mirrored in hierarchical coevolution between adjacent levels of the component hierarchy. Like the coevolutionary model of design exploration, hierarchical coevolution treats immediately superior solutions in the hierarchy of components as a population of potential problem definitions that define the design problem for lower level solution populations. The hierarchical coevolutionary model uses representatives from the problem population to define the extrinsic fitness function of lower level component by evaluating them within the context of the representative problems. At each level of the hierarchy the cooperative coevolution of components is guided by the evaluations of the assembly of the components evolved at the immediately superior level. The coevolution of components with a common fitness function at a higher level allows the communication of context-sensitive knowledge about the relationships between components. Knowledge is transferred implicitly from one evolutionary process to another through the shared evaluation of the two components at the assembly level. Intrinsic evaluations cover aspects of the design problem that are limited to the scope of a component and the subcomponents that make it up. Extrinsic evaluations cover aspects of the design problem that relate to its ability to function within the context of an assembled superior level component. As a consequence, intrinsic and extrinsic evaluations are related, and in general, the intrinsic evaluation of a component at one level is the extrinsic evaluation of its subcomponents.

The separation of intrinsic and extrinsic evaluations allows the context of a component to be limited to avoid the problems of having to evaluate a component within the context of all other components. The use of higher level intrinsic evaluations as lower level extrinsic evaluations over two levels of a hierarchy allows some information to be shared vertically without a need to reevaluate all of the other components that go to make up the tree. The determination of an overall fitness for an individual from the intrinsic and extrinsic fitness measures can be done in many ways. However, a simple means of combining intrinsic and extrinsic fitness functions is used in which the fitness evaluations are combined using a weighted sum to produce a fitness value that reflects the relative importance given to the intrinsic and extrinsic evaluation criteria. In this work, different weights for the intrinsic fitness and the extrinsic fitness were used.

During the initialization phase, only the intrinsic fitness is used to define the fitness of individuals. This is used as a bootstrapping process to provide some initial components for the coevolutionary processes to use.

Comparing hierarchical evolution and hierarchical coevolution, we can observe some important differences between the two approaches. Most important, the hierarchical coevolutionary model does not block the evolution of new solutions at any level of the component hierarchy until the lower levels have been completed. In the previous hierarchical evolution approach (Rosenman, 1996), each component population at the lower level was fully evolved over a number of generations, and potentially suitable components were selected before the next level of components (assemblies) was, in turn, evolved. In hierarchical coevolution, for each generation, components are evolved and used to generate the next level of component assemblies. The former approach was a breadthwise bottom-up approach, whereas the hierarchical coevolution approach is a depthwise bottom-up and then top-down approach.

6.1. Facility layout problems

Layout problems of the type described below are also known as facility layout problems and have been extensively studied in design computing, artificial intelligence, and computer science. The facility layout problem is applicable to several fields, including the layout of space in a building, the layout of components on printed circuit boards, and the packaging of goods in containers. Computer systems capable of solving layout problems have been developed using both knowledge-rich and knowledge-lean approaches. Different evolutionary algorithms (e.g., GA, genetic programming, evolutionary strategy, etc.) have been applied to layout problems using different representation schemes and have been shown to be good general-purpose methods when matched with appropriate representation schemes.

In general, the facility layout problem deals with a set of n rectangular facilities F = {f₁, f₂, … , f_n} that have to be located within a planar site. A connectivity matrix M = [m_ij]i, j = 1, … , n defines the connection weights between each pair of facilities f_i and f_j. The objective is to find a nonoverlapping arrangement of the facilities with minimal connectivity costs, calculated as

is the distance between facilities f_i and f_j. Variants of the facility layout problem have been introduced. For example, facility layout problems have been devised for irregular sites, sites with preoccupied regions, or multiple sites (Kuziak & Heragu, 1987; Meller & Gau, 1996).

6.2. The house layout problem

The house floor plan design problem set for the evolutionary algorithms below differs from the typical facility layout problems in several ways. The first is that the problem involves laying out a set of nonidentical, flexible facilities, in this case rooms. The size of the rooms are not predetermined; instead, constraints are supplied as ranges of valid areas and desired length to width ratios. The evolutionary algorithm must determine the most appropriate sizes and shapes of the rooms. The problem then naturally decomposes into a two-level hierarchy of subproblems (i.e., a standard facility layout problem to assemble rooms and a set of subproblems to determine size and shape of each room). In other words, this is both a topology and geometry problem.

The second difference in the layout problem is that the rooms can be grouped into zones in advance of an evolutionary run, such that each zone contains rooms that share related functions. The introduction of zones allows a designer some additional control over the placement of related rooms, beyond the specification of connection weights. The addition of a zone level also allows complex facility layout problems to be broken down into a set of simpler facility layout problems for the sake of efficiency. It provides a way for designers to add knowledge about the design process in a natural way.

As a consequence, the layout problem breaks down into a hierarchy of at least three levels. First, at the room level, an appropriate size and shape of each room must be determined. Second, at the zone level, related rooms must be arranged to minimize the connectivity costs of rooms within the zone. Third, at the house level, zones must be arranged to minimize the connectivity costs of rooms in different zones. The requirements of a house layout problem can be represented with the diagram shown in Figure 1. The diagram clearly illustrates the connectivity relationships between rooms and how rooms that have many connectivity requirements are grouped together into zones. Although for this implementation example the decomposition structure is given, in a full design situation, different evolutionary runs could be implemented with different decomposition structures.

A diagrammatic representation of the relationships between rooms, zones, and the house with three zones.

The subproblems at each level of the problem hierarchy have different objectives, and the fitness functions used to evolve possible solutions reflect this. The details of the evolutionary processes, representations, and evaluation functions used to evolve rooms, zones, and houses are given in the next subsection. At each level, the weighted function for combining intrinsic and extrinsic fitnesses used in the examples was a 2:1 ratio. That is, the intrinsic fitness was weighted twice as much as the extrinsic fitness.

6.3. Hierarchical coevolution of house layouts

6.3.1. Room evolution

Rooms are represented using integer genotypes with two genes. The first gene is used to encode the width of the room, and the second gene is used to encode the length. The actual length and width of a room are calculated by multiplying the integer value of each gene by 0.1 m. Expressed genotypes are represented as rectangular shapes that can be rotated and positioned within higher level assemblies as required.

Rooms are evaluated using an intrinsic fitness function that compares each room's area and length to width ratio with predefined ranges of desired areas and aspect ratios. The fitness functions for a room are defined by specifying minimum and maximum values for area and width to length ratio, Area_min, Area_max, Ratio_min, and Ratio_max. The evaluation functions take a common approach in evolutionary computing by turning the hard constraints that would disallow rooms that fall outside the minimum and maximum values into soft constraints that allow rooms to have areas and ratios outside these ranges but with increasing penalties, incurred as loss of fitness. The shape of the fitness function used for evaluating the area of a room is illustrated in Figure 2; a similar function is used for evaluating the shape of a room.

The shape of the fitness function for the evaluation of the area of a room.

Some of the evaluation functions for rooms in the following examples have been made deliberately vague by specifying wide ranges of acceptable areas and ratios. As a result, the evaluation functions define a large plateau in the intrinsic fitness landscape for rooms that are equally “good” from the perspective of a room's requirements. Vague descriptions of requirements are common in design when the acceptability of a design relies on contingent factors. The objective of using them in the following experiments has been to show that hierarchical coevolution can help resolve vague requirements by allowing different levels of the hierarchy to interact.

The evaluation of the area and width to length ratio of each room provides the hierarchical coevolutionary algorithm with a measure of the intrinsic value of the room (i.e., the ability of the room to support its assigned function). Each room is also evaluated within the context of the zone to which it belongs, providing a measure of its extrinsic fitness. The details of the zone evaluation functions are given in the next subsection. When a zone is being evaluated, it uses the best rooms currently available. However, when a room is being evaluated in the context of a zone, it replaces the current best room of its type.

6.3.2. Zone evolution

Zones are represented as slicing tree structures (STSs; see Schnecke & Vornberger, 1997). An STS for n rooms is a binary expression tree in which each leaf node is a label indicating a type of room and each internal node represents the spatial relationship between its two child substructures. Using the STS, zones are constructed using a sequence of join operations between pairs of rooms or between pairs of partially constructed zones that place the second substructure directly north, south, east, or west of the first substructure, as illustrated in Figure 3.

The bottom-up construction of a zone using a slicing tree structure (STS).

As well as being illustrated as a tree, STSs can also be written as symbolic expressions, using Polish notation. For example, the STS expression (N R₁R₂) places room R₂ directly north of room R₁, and the STS expression (N (W R₁R₂)R₃) places room R₂ west of room R₁ and room R₃ north of the substructure (R₁·R₂) that contains rooms R₁ and R₂. Each join operation also specifies whether either of the substructures should be rotated and if so by how much. Rotations are specified clockwise in 90° increments. The result of joining two rooms is a partially constructed zone. Zones are combined in much the same way as rooms. When zones are joined, they may be rotated. The Polish notation represents the genotype for zones and houses. The bounding box of each zone is used to calculate the relative positions of the zones such that the bounding boxes of the rotated zones touch.

The intrinsic fitness of each zone is evaluated in terms of the connectivity between the rooms it contains. The fitness measures for a zone are assessed by substituting the labels in the STS with the current best rooms available from the lower level. To evaluate the connectivity between rooms, a matrix of connection strengths between rooms is used. A simple connectivity matrix together with the graph of connections that it defines between rooms is shown in Figure 4. Each zone is also assigned an extrinsic fitness based on how well the zone works with other zones in the current best house. The zone being evaluated is constructed with the current best rooms. It is then used in place of the best zone of its type in the evaluation of the best house. This method of evaluating the extrinsic fitness of a zone works in much the same way that rooms are evaluated in the context of zones.

A connectivity matrix for a zone Z1 and two possible solutions for the room layout.

6.3.3. House evolution

Houses are represented in similar way to zones (i.e., using a STS genotype), but they contain zone identifiers. Houses are constructed in a very similar way to zones. Houses are composed by joining and rotating zones, or partially constructed houses, according to the operators at the internal nodes of the tree. Figure 5 illustrates the construction process for a house consisting of three zones and shows how a complex house can be built with only two join operations.

The bottom-up construction of a house using a slicing tree structure (STS) to represent the zones to join at leaves and the join operations at internal nodes.

Each house is evaluated by assessing the connectivity between rooms in different zones and the compactness of the house. In addition, each house can also be evaluated in terms of its fit to a predetermined site. The connectivity of rooms in different zones is used to evaluate the connectivity of the house. Only the interzone connections between rooms in different zones are considered because connections between rooms in the same zone are evaluated by the appropriate zone. By assessing the connectivity of two rooms in different zones, a pressure to rotate one of the zones may be exerted if the zones are adjacent but the rooms are separated. For example, although we could define that a utility zone should be connected to a living zone, it does not say how these two zones should be connected; instead, by defining that the laundry should be connected to the kitchen, we can provide additional domain knowledge. Commonly, interzone connections are defined between hallways in different rooms thereby specifying their function as a means of getting between various parts of a house.

The compactness of a house is evaluated by penalties for not using all of the space within its bounding box. In addition to the compactness measure, a house can be evaluated within the context of a site. The site evaluation function penalizes a house for extending beyond the bounds of a site or for underutilizing the available area in the site. Figure 6 illustrates the calculation of site evaluation.

An illustration of the evaluation of a house in the context of a site.

6.4. Example 1: Evolving a hallway

The aim of this experiment is to show that the desired topology of rooms, specified in the connectivity matrix for a zone, can have a significant effect on the development of rooms. This simple experiment is again limited to the coevolution of rooms within a single zone. There are five rooms in this example, four of which have been constrained to evolve toward squarelike shapes, and the fifth of which has been constrained only in its size. Figure 7 shows the connectivity graph and the area and aspect ratios for this example.

The connectivity graph for the zone and the room evaluation parameters used to evolve a hallway R3 that connects rooms R1, R2, R4, and R5.

The connectivity graph shows that four of the rooms, R₁, R₂, R₄, and R₅ are connected to the fifth room R₃. The fifth room is thereby defined to act as a hallway connecting all of the other rooms. The zone must arrange the rooms R₁, R₂, R₄, and R₅ around R₃ to minimize connectivity costs. Figure 8 illustrates three stages of the evolution of a zone, including the genotype representation of the zones.

Three stages in the evolution of a zone in hierarchical evolution, showing the evolution of a hallway. (Rotations of 0° have been omitted from the descriptions of the tree structures for brevity.)

The first STS shown in Figure 8 shows an early solution to the problem of connecting all of the other rooms to R₅ after all of the rooms have adapted to the arrangement evolved by the zone. This solution is good, but it is suboptimal, which allows the continued search for better zone layouts. The second STS in Figure 8 shows a later stage in the evolutionary process, when the zone has rearranged the rooms into a zone with a better connectivity evaluation at the expense of compactness.

The room evaluations for this stage are also lower in general than for the earlier stage because the rooms are adapting to the requirements of the new zone arrangement. One of the most interesting observations to make about the evolutionary process illustrated in Figure 8 is the way that R₃ elongates from the second to the third STS to fill all of the space left between the two pairs of rooms: R₁ and R₂ and R₄ and R₅. The elongation of R₅ is entirely caused by the extrinsic evaluations of the room at the zone level in the context of its function as a hallway.

This example shows the effectiveness of the coevolutionary process at influencing the evolution of rooms as the extrinsic zone evaluations change radically. We can also observe a shift in the style of the evolutionary design process in early and late stages of the design process. The style of the design process shifts from the evolution of approximate room shapes in the early stages of design to a more detailed design process once a good zone has been found. In the early stages of the evolutionary process, when many different room arrangements compete in the zone evolutionary process, the room shapes have to alter radically from one generation to the next. As the zone-level evolutionary process settles on a good arrangement of rooms, it provides a more stable environment for the room evolutionary processes to evaluate new rooms. The style of the evolutionary processes shifts from the development of approximate room shapes to a process of fitting rooms into the stable zone. This example shows the coevolutionary process of reformulating intrinsic fitness in a two-level hierarchy. In the next example, it will be shown how this process can be extended across multiple levels.

6.5. Example 2: Evolving a small house

This example shows how a hierarchy of coevolving processes exchanges information that reduces the complexity of specifying the design problem a priori. In this experiment the hierarchy was extended to all three levels to demonstrate that evolutionary pressure (i.e., information) can flow from one level to another, even when those levels are not adjacent and the pressures must be transmitted through an intermediate level. In this example, a small house layout is evolved. The small house (SH) contains two zones: a living zone (LZ) and a sleeping zone (SZ). The living zone contains a living room (LR), a dining room (DR), a kitchen (Ki), and an entrance (En). The sleeping zone contains two small bedrooms (B1 and B2), a master bedroom (MB), and a bathroom (Ba). The constraints placed on each room and the connectivity relationships between them are illustrated in Figure 9.

The design problem specification for a small house.

The zones are evaluated according to the connectivity requirement on their respective rooms and do not have a compactness evaluation function. Without this criterion, the zones are free to evolve into a wide range of possible configurations.

At the house level, the entrance and the hallway must connect. This requirement forms part of the extrinsic fitness measure for the zones. Therefore, between the hallway in the sleeping zone and the entrance in the living zone, the weight of the connection is 10.0 because the connectivity between these two spaces is essential. The house is also evaluated on the compactness of the overall shape. The compactness of house designs is the result of an evaluation function defined at that level rather than of the careful manipulation of compactness evaluation functions throughout the hierarchy. The entrance has an additional requirement over previously presented hallways that it must touch the boundary of the house. This requirement is implemented as an evaluation function of evolved houses. The addition of the requirements that En touches one of the outside edges of the house and connects with Ha in the sleeping zone means that En must touch two outside edges of LZ.

Figure 10 shows the results of the best run out of 15 runs of the hierarchical coevolution on the above problem. Each run was implemented for 300 generations. Five of the 15 runs generated satisfactory designs: 6 were reasonably satisfactory, and the other 4 solutions were not satisfactory.

The results of the hierarchical coevolution of a small house.

Figure 10a–f shows the best house for each of the generations shown. At generation 10, the room sizes and room connectivities have been satisfied, but the house compactness is still poor, as there is some amount of “white space” in the bounding box. In addition, the entrance and hallway are not connected. Note, however, that the pressure at the house level for the entrance to have external access has resulted in a change of shape of the entrance. At generation 50, the compactness is increased; at generation 200 the house is fully compacted but now the entrance and hallway are out of line; at generation 250 all the room size constraints are satisfied, the zone room connectivities are maximized, the house is fully compacted, the entrance and hallway connectivity is maximized, and the entrance access to the exterior is satisfied.