DR. PAISOUD KIRZAYE
Genetic Algorithm (GA) is widely adopted in optimization and also the improvement of its optimization performance is attracting many researchers’ attentions. In solving practical problems within the process of architectural design, the ways of converting design problems into mathematical models that may be addressed by GA are of great significance in achieving final optimal results. However, no such rule which will be applied to such conversion has been developed thus far. In general, problems which might be addressed by GA will be divided into combinatorial problems and numerical problems. during this paper, by means of attempting to disintegrate a sophisticated architectural problem into combinatorial and numerical problems, the author discusses feasibility and practicality of solving these two styles of problems simultaneously utilizing GA and discloses both advantages and drawbacks of GA by comparing with other algorithms.
Genetic Algorithms are introduced into architectural design field normally since a dozen years ago because of its special robustness and comparatively simple implementation. Ever since then, they need been adopted particularly in optimizing the layouts of floor plans (Michalek et al., 2002) and site plans (Finucane et al., 2006), optimizing building façade designs(Caldas and Norford, 1999), optimizing styles of building structures (Papapavlou and Turner, 2009), and in some conceptual design (Soddu, 2005). However, unlike in other purely research project fields, problems in architectural designs are often mixed with social and esthetic factors which can’t be described by mathematical models. When a designer attempts to optimize design problems with the assistance of GA, facing such complexities inherent in architectural designs, he or she should convert specific problems into combinatorial and/or numerical problems that may be addressed by GA. Particularly within the case of combination of those two sorts of problems, drastic expansion of searching space is seen as a troublesome test for GA’s searching ability. a way to utilize Genetic Algorithms, a way to convert design problems and the way to effectively control the dimensions of searching space are three major subjects in optimizing architectural designs using GA. during this paper, the optimization of modeling for schematic design of ancient Yangzhou South City-Gate Ruins Museum exemplifies the introduction of the applying process for optimizing architectural designs with the assistance of GA, yet because the disclosure of both advantages and drawbacks of GA by comparing it with other non-heuristic algorithms.
In order to preserve the historical remains – the traditional Yangzhou South City-Gate Site – an outsized shell structure is meant as a museum to shelter the ruins. For the sake of avoiding any damage to the location, no strut is provided within the positioning area to support this large-span structure with the size of 80 m long, 40 m wide and 11 m tall. As designed, the full structure consists of several irregular triangular faces while each face is crammed with textures of normal angles formed by steel beams interconnected horizontally and vertically (Figure 1). it’s clear that continuity and completeness of the textures are important factors affecting the performance of the entire structure. However, since the shell shape is irregular, it’s difficult to make sure the textures’ continuity at turning points of some triangular faces. Therefore, the first task of optimization is to attenuate such discontinuous edges.
Fig.1 Structure of the shell
In addition, so as to ensure sufficient spaces for the convenience of construction treatment, the intersection points, i.e., vertexes of every regular triangle within the textures, should be kept removed from the turning points as further as possible.
Since building structures and shapes are subject to changes of design purposes during the look process, optimization programming is additionally required to produce immediate and direct feedbacks on design changes.
In order to simplify issues, an abstract geometrical model is introduced to explain the building structure as a full, with beams and nodes become abstract line segments and points (Figure. 2). To avoid ambiguity, triangular faces of structures and shapes are defined as triangular faces, edges shared by two triangular faces as shared edges, edges of single triangular face as border edges, end points of shared edges as vertexes, end points of border edges as border vertexes, vertexes of standard triangles too proximate to shared edges as close points, and shared edges which can be split in their unfolding process as split edges.
Fig. 2. Abstract geometrical model.
Discontinuity of textures is related to unfolding ways of three-dimensional bodies onto a two-dimensional plane. In doing so, some shared edges must be split. as an example, there are many ways to unfold a straightforward triangular pyramid. The longer the split edges are, the poorer the continuity of textures are going to be (Figure 3). So this problem has been transformed into the one targeting at trying to find a mix way of the shortest split edges. it’s obvious that this is often a combinatorial problem.
fig.3. Different ways to unfold triangular pyramid
Furthermore, the number of close points depends on the textures of the regular triangles and therefore the relative position and angle of graphics after unfolding (Figure 4).
Figure 4. Close points
4.1. Split edge optimizing algorithm
Concerning the way of attempting to find unfolding algorithm for the shortest split edges, Genetic Algorithm is applied tentatively. However, in doing so, its searching scope expands at an exponential order with increasing number of vertexes and it’s difficult to see whether the optimal solution has been identified. As a result, it’ll motivate difficulties for subsequent optimization. Therefore, an alternate algorithmic rule is intended by analyzing rules for the unfolding process. Here lists both algorithms and also the comparison between them.
4.1.1. supported Genetic Algorithm
Selection of split edges is related to the sequence of joining shared edges together. as an example, for a triangular pyramid without bottom face, first, its three faces are unfolded into a two-dimensional space. If their shared edges are joined together in several sequences, the results obtained are diversified (Figure 5).
Figure 5. Different results of various sequences.
In turn, chromosome is coded in step with permutation encoding style. Each gene represents the ID number of the shared edge while chromosomes are various combinations of those ID numbers. Length of the chromosomes is that the total number of the shared edges (Table 1). If there are n shared edges, then searching space are going to be as large as n!.
Table 1 permutation coding
Since the chromosomes are ordered sequences, the commonly used single-point crossover algorithm will break the sequence and generate illegal solutions. Alternatively, partially matched crossover is adopted. Two chromosome fragments are taken out from parent chromosomes for exchange (Table 2). In offspring chromosomes generated from the method, the repetitive genes produced from exchange are replaced by corresponding genes inside chromosome fragments (Table 3).
Mutation operator randomly selects two genes from chromosomes, i.e., ID numbers of shared edges and exchanges their positions (Table 4).
Chromosome’s fitness is that the total length of un-split shared edges. The longer the length is that the better continuity and fitness are. Its formula is as following:
In which, s is fitness, n is that the total number of shared edges; Li is that the length of ith shared edge. When shared edges aren’t split, Hi=1; otherwise Hi=0. At the identical time, roulette algorithm is employed to pick out chromosomes from the population. Figure 6 shows the changes of optimal solutions during the unfolding process.
Figure 6. Changes of optimal solutions during unfolding.
4.1.2. supported sorting
It is clear that when a three-dimensional shell structure is unfolded, each vertex owns a minimum of one shared edge ranging from itself to be split. for example, a triangular pyramid has just one vertex, so splitting one in every of the perimeters ranging from now can unfold this shape (Figure 3). within the case of objects with numerous vertexes, their shapes may be unfolded in order that all shared edges of the three-dimensional object is arranged in keeping with their lengths from the shortest to the longest if each vertex has its own split edge. the subsequent rules will be applied to work out whether this edge should be assumed to be the split edge.
1.If its two ends are vertex and border vertex, respectively, assume it to be the split edge attributed to the vertex.
2. If its two ends are both vertexes which don’t own their own split edges, assume it to be the undetermined edge shared by the 2 vertexes. Once either of them gets another split come on the later determination process, this undetermined edge is attributed to the opposite vertex. If one in all them has already owned one split edge, this edge are often attributed to the opposite vertex. If both vertexes own split edges, this edge may be abandoned. If one in every of the 2 vertexes owns one undetermined edge and therefore the other of them owns un-split edge, this edge are attributed to the one owning undetermined edge on a prioritized basis. If two vertexes both own undetermined edges, it’ll be attributed to the vertex with the shorter undetermined edge on a prioritized basis. still put each shared edge into the formula until all vertexes have their own split edges.
3. If some split edges form a circle, it implies that the form is split into two sections, which isn’t desired. during this case, we’d like to pick the second shortest edge with the littlest length increment to substitute one split go up the circle.
The speed of unfolding becomes much faster after introducing this algorithm, enabling managing an outsized amount of vertexes (Figure 7).
Figure 7. The results of unfolding a 3d shape with 100 vertexes
4.2. Projection optimization algorithm
During projection process, two approaches will be applied to scale back the quantity of critical points. the primary one is to regulate relative positions and angles of projected textures on the unfolded shape. The second is to tune position of the shell’s vertex. Therefore, the chromosome could be a sequence composed of vectors of three elements (Table 5).The three elements of a vector represent its values on axes x, y and z, respectively. the primary two vectors of the chromosome represent relative position and angle of the textures of the regular triangle. Other vector represents the displacement of every vertex. Values of vectors are limited to a particular range to make sure that changes of the structure and shape aren’t too drastic.
Table .5 The Chromosome
Single-point crossover is applied to crossing process. Once one crossover point is randomly selected, new offspring are generated when two parent chromosomes exchange their chromosome fragments behind crossover points.
In order to make sure the chromosome mutate, genes inside chromosomes are randomly selected and replaced with randomly generated vectors.
Chromosome’s fitness is reciprocal of the full number of close points. When an everyday triangle is projected onto an unfolded shape, positions of its vertexes and distances between them and therefore the surrounding shared edges may be calculated. If the gap is a smaller amount than certain threshold, it’s marked as an in depth point.
Here we’ve proposed corresponding algorithms for major problems in design. the following step are going to be the way to select and arrange these algorithms. In split edge optimization algorithm, genetic-algorithms-based approach is seemingly not as effective as sequence-based algorithm in terms of searching ability. Since in projection optimization algorithm, splitting and unfolding ways for newly generated objects could change with operations in positions of every object’s vertexes, we’d like to embed split edge optimization algorithm into projection optimization algorithm before obtaining relatively complete searching space. If we embed one Genetic Algorithm into another Genetic Algorithm, the number of calculations required is big. If changes caused by vertex movements are uncounted and two Genetic Algorithms are combined in successive order for application, some searching space are going to be neglected. Considering all the above factors, sequence-based split edge optimization algorithm embedded into projection optimization algorithm is adopted within the optimization process.
The optimization program is written with java language and JMonkey Engine is employed to produce 3d rendering and shading. the entire optimization process will be conducted within the following three steps:
1st step: Enter the vertexes of the shell’s triangular faces (Figure 8).
Figure 8. Input points.
2nd step: Delaunay Triangulation is employed to come up with triangular faces (Figure 9). During this generation process, connecting relations between points and edges, connecting relations between points and triangular faces, and neighboring relations between triangular faces also are established for further calculating.
Figure 9. Triangulation.
1.3rd step: Use Genetic Algorithm to accomplish the optimization.Generate certain number of random chromosomes.
2.Adjust the position of every vertex of the three-dimensional object per each gene inside the chromosome to provide new corresponding object.
3.Use split edge optimization algorithm to calculate splitting ways for every object and unfold it into a two-dimensional plane (Figure 10).
Figure 10. Unfolding.
4.Project the textures of the regular triangle onto the unfolded shape in keeping with the primary two genes inside chromosome (Figure 11).
Figure 11. Projection.
5.Calculate fitness of every projecting way.
6.Select the chromosome with the optimal fitness. If it’s better than current maximum fitness, update this fitness, recover the projected and unfolded shape back to three-dimensional state, and draw it on the image interface (Figure 12).
Figure 12. Refolding.Determine whether optimization has to be continued. If not, stop the program.
8.Use roulette algorithm to pick chromosome to be inherited by the subsequent generation.
9.Perform crossover and mutation operations to the chromosome of latest generation and return to the 2nd step operation.
By comparing the 2 unfolding algorithms, it will be seen that Genetic Algorithm is a smaller amount difficult to comprehend. Generally speaking, farewell mutually knows the way to code chromosome and the way to assess fitness, he or she will be able to optimize problems by using Genetic Algorithm and don’t must consider functional relations between inputs and outputs. it’s special advantages in optimizing np problems. If one has no other better algorithm in optimization, Genetic Algorithms are often an affordable choice. However, as a heuristic random searching algorithm, it involves huge computation load. First, it’s a parallel searching algorithm, which implies calculation load will multiply with the rise of the amount of chromosome lengths and individuals in a very population. Second, calculations can not be once for all, the optimal solution must be approached by continuous iterations. Its ability for achieving optimal solution and also the time consumed for achieving the answer are random to an excellent degree. When considering two optimization problems embedded within one another, it’s difficult to attain optimization. just in case that some requirements in terms of optimization efficiency are recommend, or the optimal solution must be obtained, Genetic Algorithm isn’t an appropriate choice. during this case, functional relations need to be considered. However, with respect to a number of the architectural design problems, the optimal solutions expressed in numbers or values aren’t necessarily what architects would really like. Genetic Algorithm may provide diversified approximately optimal solutions for architects for his or her references. In turn, architects can make their own judgments after considering all other design factors on a comprehensive basis.
L.G. Caldas, L.K. Norford
A Genetic Algorithm Tool for Design Optimization ACADIA ‘99, Salt Lake City (1999)
E.L. Finucane, C. Derix, et al.
Evolving urban structures using computer optimisation techniques Generative Art (2006)
J. Michalek, R. Choudhary, et al.
Architectural layout design optimization Engineering Optimization, 34 (2002), pp. 461-484
Papapavlou, A., Turner A., 2009. Structural evolution: a genetic algorithm method to come up with structurally optimal Delaunay triangulated space frames for dynamic loads. In: 27th eCAADe Conference, Istanbul.
Soddu, C., 2005. Visionary Variations of Milano, from〈http://soddu2.dst.polimi.it/asialink/de1.htm〉.Google Scholar
DR. MASOUD MIRZAEE