Truss optimization has been approached using a wide variety of optimization techniques to optimize a realm of diverse truss structures which encompass vast applications. These techniques involve cross sectional and geometry optimization through sequential quadratic programming demonstrated by Smith, Hodgins, Oppenheim, and Witkin  which include roof trusses and the
Many truss optimization techniques may be captured within the structure of a conventional genetic algorithm where a global and effective search can be utilized. However, a conventional genetic algorithm operation has many limitations including:
1) Genetic input parameters are application specific
2) The initial population, which is randomly generated, has a significant impact on all offspring created
3) Mutation must be relied upon in order to achieve a global solution
4) Problems of increased complexity require extensive computational time for an adequate global solution
5) Global search solutions generally require user modification before the solution is located which satisfies the general purpose of the intended application
These hurdles are primarily attributed to the encoding or chromosome string of a conventional genetic algorithm. This chromosome string is a representation of the design where each value within the string correlates to a specific characteristic or trait associated with the investigated design.
The conventional genetic algorithm begins by generating an initial random population of chromosome strings. Each chromosome string value is applied to each truss element and the newly generated design is solved by a finite element routine where local parameters are calculated. Objective function and predetermined constraints based upon calculated local parameters and overall volume reduction are employed to reveal which strings are best suited to become parent strings. Subsequent to objective and constraint function evaluation, the fitness value of a string is assigned exclusively by the objective function, if and only if the individual string fails to violate any constraints. Design strings which possess failing constraint values are assigned fitness values determined by a penalty function. The overall value of the design is determined by the penalty function introduced by Equation (1).
i = 1,∙∙∙, number of constraints
The value f(x) or the objective function is incorporated to further reward or penalize the design by the total amount of what is to be maximized or minimized. The purpose of the penalty function R is to penalize designs analyzed which fail to meet important design limits where the initial value of R presented is 10. This penalty factor is user specified and increases by a constant numeric value once a specified number of generations have been produced which consists of a numerical value of 2. The inclusion of the number of the constraint function gi(x) is necessary to provide numerically how much the design has failed to meet the set of individual constraints. The overall fitness value is a reflection of the design, and due to the formulation of the penalty function, poor designs are eventually removed from the genetic process. The best strings are gathered into a “mating pool” where the genetic algorithm randomly selects chromosome strings to mate with one another. Chromosome characteristics are exchanged within each parent design string and offspring chromosome strings are produced. Special operators such as mutation are introduced to inject alternative designs to further enhance the evolutionary optimization process especially when utilizing a relatively small population size. For this study, the probability of mutation factor was set at 0.01. Ultimately the genetic algorithm relies on the randomness present in the initial gene pool, but quickly exploits information gathered in order to produce an efficient optimization. Goldberg  and Davis  discuss genetic algorithms in further detail. This genetic optimization procedure stimulates the need to improve the global nature of the search where a novel second phase approach is introduced by providing designer knowledge in the form of decision based rules. This second phase alters the fundamental chromosome string to a series of rule sequences to be executed based upon domain specific knowledge which either eliminates or significantly reduces the problems associated with the functionality of the traditional genetic algorithm.
Structures considered were support, transmission tower, and signboard trusses formulated by Logan  . Each truss member is considered a solid rod to simplify the moment of inertia criteria in the formulation of an element buckling constraint. A finite element solver is encoded into a series of subroutines which is utilized by the genetic algorithm within all phases constructed. The finite element solver which was programmed in Visual Basic  removes illegitimate designs which consist of singular matrix formulations and elements which fail to meet buckling criteria. Stress and displacement serve as the structural constraints for which the genetic algorithm accesses offspring designs. Additional constraints are implemented; however these constraints tailor toward the implementation of domain specific knowledge within phase two.
The phase one optimization methodology operates by the use of an evolutionary approach; however constant rules are introduced which ensures structural integrity among all offspring developed throughout the global search. This evolutionary approach generates truss structures which require the minimum amount of elements to sustain loading and constraint conditions. Additionally, the modulus of elasticity of elements throughout the optimization procedure is manipulated to allow for an assortment of materials to be present in the construction of a final phase one design. However, due to the formulation of local element stiffness matrices, element lengths, areas, and modulus of elasticity values are considered constants where a change in modulus of elasticity value may be interpreted as a change in area rather than material property.
The phase two optimization methodology refined the best phase one design from a “blank sheet of paper” point of view, where force and ground nodes are the only required constant nodal locations. Phase two manipulates element areas, nodal coordinates, removes existing nodes, and creates elements which are initially nonexistent. Structural integrity is maintained throughout the optimization procedure by the implementation of a finite element solver which calculates element stress and nodal displacement. Additional constraints which aid the phase two optimization procedure are element length, area, and nodal coordinate constraints.
Phase three refines the best design generated from phase two which utilizes the traditional genetic algorithm methodology. Each element within the final phase two design is subjected to area reduction to effectively produce active constraint values (i.e. gi(x) ≈ 0) indicating that an optimal solution has been located. A primary function of phases one and two is to generate the optimal topology of a truss structure, where any further removal of elements results in either a singular matrix or constraint violating solution. Phase two possesses the capability of reducing truss element areas; however phase three provides a more rigorous approach to refine the most optimal topological design.
3. Problem Formulation
The conventional genetic algorithm methodology is utilized by each phase to produce an efficient optimization. Phases one and three operate by the inclusion of a chromosome string where the length of the string is related to the total number of truss members currently present. Phase one manipulates two chromosome strings simultaneously which include a topological design string and a modulus of elasticity manipulation string. The chromosomes within the topological design string can potentially acquire the value of 0 or 1. These values contribute to the removal or addition of elements in the configuration of a genetic design. The modulus of elasticity manipulation string is composed of chromosome values from a predetermined range of 0.1 to 1 with a step size of 0.1 which potentially reduces the strength of elements when multiplied by a value within this numeric array. This concept is reintroduced into phase three where a predetermined range of values which consist of 0.1 to 1 with a step size of 0.01 are assigned to each chromosome to potentially reduce element areas and ultimately the overall volume of the structure.
Domain specific knowledge is introduced into the genetic algorithm global search solution in the form of decision based rules. This rule based approach alters the encoding strings of the conventional genetic algorithm. Each string is composed of chromosomes of which select and provide additional information to execute specified rules. Previous truss optimization approaches have incorporated some basic form of domain knowledge of truss structures; however they are limited in overall design efficiency. Kawamura and Ohmori  implement the configuration of truss designs through the generation of triangular element configurations which ensures structural stability for all offspring designs generated. However effective, this technique utilizes a constant methodology for truss design, where the concept of “designing from a blank sheet of paper” point of view is either limited or nonexistent. This novel second phase optimization approach incorporates domain specific knowledge of truss structures to manipulate nodal coordinates, element areas, remove nodes, and generate elements which were originally nonexistent. A chromosome string must be constructed in a sophisticated fashion to effectively distribute rules which refine the best design from phase one.
A general mathematical formulation of the alternate chromosome string is provided below.
The A field represents the number of rules to apply, Bi represents which of the rules to apply and the fields Ci, Di and Ei provide specific rule implementation information. The subscript n represents the maximum number of rules to be exercised during one modification of a selected design encoding.
The formulation of the objective function and constraints for the truss design examples considered are as follows:
i = 1,∙∙∙, number of elements
Here, Slimit and Dlimit are the maximum allowable stress and displacement while Smax (calculated) and Dmax (calculated) are the computed values. The formulation of Equations (4) and (5) generate ratios, which allow for normalization of constraint violation in the disparate magnitudes of the displacement and stress values as well as allow for a consistent graphical representation over the diverse set of designs within each genetic population. Both constraint equations produce positive values for any design which does not exceed the design limits.
4. Phase One
Initially, a random population of strings for both element selection and modulus of elasticity manipulation are generated when the phase one operation is launched. These two random strings function independently, yet are synchronized with each other to represent a single design. Elements are originally selected at random from the original design configuration which generates an initial population. These random elements chosen may not form a structure; therefore constant phase one structural rules were derived to ensure that arbitrary genetic designs are viable structures. The constant phase one rules are general in nature which ensure that they can be applied to a wide variety of truss structures and correct imperfections created by the genetic algorithm. Listed below are the phase one constant rules which mend genetic design deficiencies.
1) All force and ground nodes must be present
2) All force and ground nodes must be connected to at least two other nodes
3) All non force and non ground nodes must be connected to at least three other nodes
These rules seem simple but without them as high as 90% of the initial designs created by the genetic algorithm will not be structures. An example is provided below and illustrated within Figures 2-4 to demonstrate the phase one constant rule process of operation. Truss illustrations throughout this research were developed using AMSES software  , where numbered squares and circles within each truss configuration label each element and node present.
Figure 1. Fifteen element plane truss.
Figure 2. Plane truss phase one design.
Figure 3. Plane truss final design.
Since the phase one constant rules are general, the rules on occasion may fail to create a valid structure. Illegitimate structures are detected within the finite element algorithm and the solving process is halted. The defective design is sent
Figure 4. Objective Function versus Generation.
to the constraint subroutine and assigned a poor default value for both stress and displacement constraints.
5. Phase Two
The phase two optimization process is used to refine the best design from phase one by the implementation of domain specific knowledge provided by the user in the form of rules. The fundamental procedures of the genetic algorithm remain identical to the phase one methodology with the exception of the development of sophisticated rule execution strings. Each time the genetic algorithm locates a rule sequence for which both stress and displacement constraints are satisfied and an improvement in the objective function is achieved, the improved design now becomes the design considered for further optimization. Four rules were developed for the phase two operation, where each rule works independently or is synchronized with other rules to improve the objective function by reducing the overall volume within the current truss structure.
Listed below are the four rules developed which can be utilized in order to improve the phase one final design.
Rule one manipulates the area of elements selected by the genetic algorithm based upon calculated stress. Before genetic optimization begins, the user specifies the maximum allowable area each element can acquire. Upon the selection of rule one, the genetic code locates the maximum element stress within the current design and a comparison is made to the maximum allowable stress constraint. If the computed maximum element stress exceeds or falls below the maximum allowable stress constraint, then the area of the element pre-selected by the genetic algorithm is altered by a factor of 0.1 to 0.9 with a step size of 0.1. Once the area has been altered, the new area is evaluated by the maximum allowable area constraint, where areas which exceed the constraint are not introduced into the creation of a new design.
Similar to rule one, rule two manipulates the area of elements selected by the genetic algorithm. Area manipulation is based upon calculated nodal displacement rather than element stress. Once the selection of rule two has been identified, the genetic code locates the maximum nodal displacement from the current design and a comparison is made with the maximum allowable displacement constraint. If the computed displacement value exceeds or falls below the maximum allowable displacement constraint, the area of an element predetermined by the genetic algorithm is altered by a factor of 0.1 to 0.9 with a step size of 0.1. Once the area of the selected element has been manipulated, a maximum allowable area constraint determines if the altered area is a legitimate area to be considered for the creation of a new design.
The objective of rule three is to expand or compress element length, which is accomplished by altering the nodal coordinates of pre-selected nodes. Rule three manipulates the coordinates of non-force and non-ground nodes which are selected by the user. A user defined coordinate manipulation constraint was developed to specify how much each nodal coordinate can either be compressed or expanded. When rule three is selected nodes within the current design are examined to ensure that each predefined node still exists within the current design. Nodes that are no longer contained in the best design but were pre-selected to allow nodal coordinate manipulation are simply ignored. Once a pre-selected node is found within the current design, the genetic code determines if the coordinates of the particular node are to be expanded or compressed. Once the expansion or compression decision has been executed, the nodal coordinates are evaluated by a coordinate constraint which includes both the x and y directions to ensure that the manipulated coordinates fall within predefined guidelines.
Finally, rule four removes nodes and creates new elements which were previously nonexistent. This allows for the genetic algorithm to create a structure from a “blank sheet of paper” point of view while only requiring the genetic code to use preexisting ground and force nodes. Phase one within the genetic algorithm removes only elements and corresponding nodes based upon the original structural configuration. This is a legitimate optimization approach for if the designer’s intent were to keep the optimized structural configuration identical to the original structure. Phase two permits the user to create a design which allows for the possibility of developing a legitimate structure that does not resemble the original truss, but satisfies existing constraints. Rule four begins operation by the selection of an element which is not attached to a force or ground node. This non force and non ground node element is selected by the genetic algorithm. The genetic code locates within the selected element the node of highest order and removes the higher order node along with the selected element. Elements throughout the structure that connect with the higher order node are also removed from the design. Next, the lower order node of the selected element under investigation is examined to determine if the lower order node shares any nodes with the higher order node which when connected form additional elements. If the lower order node connects to the same node(s) that the higher order node was connected to those element(s) remain. However, if the lower order node does not connect to the same node(s) that the higher order node connects with new element(s) are created which connect the lower order node to the node(s) that connect with the higher order node.
6. Phase Three
The third and final phase of the truss optimization algorithm minimizes the overall volume of the best structure generated from phase two by reducing the area of truss members present. Area reduction is implemented by the use of a traditional global genetic algorithm search. Each element area can potentially be multiplied by a factor of 0.1 to 1 with a step size of 0.01. A phase three or global refinement search is not only necessary to further reduce the areas of the truss members present but to allow preset constraints to become active. The rules derived within phase two permit an increase or decrease in element area depending on specific rule criteria, however phase two aims to locate the optimal design topology which can be constructed from a “blank sheet of paper” point of view. An optimal topological design may be located to sustain loading conditions and satisfy constraints however satisfied the constraints may not be active. Hence a rigorous global search for the optimal area configuration is incorporated to ensure that the maximum amount of material is removed while locating an active constraint solution.
The specific input parameters utilized for each of the design exercises including population size, and number of generations of offspring to produce for both the phase one and phase two search processes are documented in Table 1. From this table, it is noted that both the population size as well as the number of generations increased as the number of elements increased in the phase one search. These parameters for phase two search remained constant, regardless of the number of truss elements contained in the design space mesh. This is a direct correlation to the length of the encoding string which increases for phase one as the number of elements increases, but remains fixed for the phase two search component. The results for each truss structure considered will be reviewed in detail. The phase one search is equivalent to a traditional genetic optimization, while the phase two search procedure represents the rule based, global search process.
The number of function evaluations required to run each example problem
Table 1. Truss Function Evaluations.
considered is determined via the equation
Function Evaluations = (6).
8. Example One
The first example is a fifteen element plane truss formulated by Logan  shown in Figure 1. The point of origin was ground node one. The plane truss was optimized with three sets of user defined genetic input parameters listed in Table 1. The initial modulus of elasticity and constant cross sectional areas for each element were preset to 210 GPa and 3E−4 m2 respectively. Maximum allowable stress and displacement constraints were 8 MPa and 0.002 m. Nodal forces ranging from 2000 N to 4000 N were applied to nodes three, five, and seven respectively. The phase one optimized fifteen element plane truss is provided in Figure 2 followed by the final design encompassing the combined outcome of both phases two and three is illustrated in Figure 3.
The phase one genetic optimization process removed five elements which included the removal of node eight. Both stress and displacement constraints were not violated at the conclusion of phase one however neither concluding constraint values are active. Since stress and displacement constraints are not active (i.e. g1(x), g2(x) > 0), at the conclusion of the phase one process, further improvement is possible. Figure 3 shows the final phase two result from which executed rules based upon domain specific knowledge are applied. Results consisting of objective function illustrating reduced truss volume and constraint values versus generation for the complete optimization process are provided in Figure 4 and Figure 5. Lastly, structural characteristics composing of the design in Figure 3 are depicted in Table 2 which outlines optimized element areas and modulus of elasticity values.
Recall that constraint values result from Equations (4) and (5) which produce constraint values without units.
9. Example Two
A transmission line truss developed by Logan  is shown in Figure 6 and is the next truss structure investigated. This thirty three element truss was subjected to two nodal forces applied to nodes twelve and seventeen. The point of origin was
Figure 5. Constraint versus Generation.
Figure 6. Transmission line truss.
Table 2. Plane truss phase three design parameters.
located directly under node seventeen at the ground level. The creation of this point of origin allowed all nodal coordinates to have positive x and y values. Nodal forces consisted of 2780 N and 3558 N, forces both in the negative x and y directions. Additional parameters consisted of an initial cross sectional area of 0.001935 m2 and a modulus of elasticity of 210 GPa for all elements considered. Preset stress and displacement constraints were 12 MPa and 0.00635 m. The phase one optimized transmission line truss is provided in Figure 7 followed by the final design encompassing the combined outcome of both phases two and three is illustrated in Figure 8. Results consisting of objective function illustrating reduced truss volume and constraint values versus generation for the complete optimization process are provided in Figure 9 and Figure 10. Lastly, structural characteristics composing of the design in Figure 8 are depicted in Table 3 which outlines optimized element areas and modulus of elasticity values.
10. Example Three
A signboard truss developed by Logan  is shown in Figure 11 and is the last
Figure 7. Transmission line truss phase one result.
Figure 8. Transmission line truss final design.
truss structure examined within this literature. This forty-one element truss was subjected to two nodal forces applied to nodes twenty and sixteen. The applied load is the total weight of the signboard divided by the two identified support nodes. Each force node supports 500 N in the negative y direction. The point of origin designated for this example was specified at ground node one. Additional structural properties included a modulus of elasticity provided by Logan  of 290E9 Pa and a constant cross-sectional area of each element of 3E−4 m2. Preset stress and displacement constraints consisted of 5E6 Pa and 0.001 m respectively. The phase one optimized transmission line truss is provided in Figure 12
Figure 9. Objective Function versus Generation.
Figure 10. Constraint versus Generation.
followed by the final design encompassing the combined outcome of both phases two and three is illustrated in Figure 13. Results consisting of objective function illustrating reduced truss volume and constraint values versus generation for the complete optimization process are provided in Figure 14 and Figure 15. Lastly, structural characteristics composing of the design in Figure 13 are depicted in Table 4 which outlines optimized element areas and modulus of elasticity values.
This multi-phase genetic algorithm approach resulted in the minimization of element volume while satisfying both stress and displacement constraints. Additionally, the inclusion of domain specific knowledge enabled the algorithm to generate alternative designs through the formation of new truss elements. Table 5 illustrates the total structural volume removed during each phase for each truss example investigated. Overall, through the use of domain specific knowledge, the genetic algorithm solution search is enhanced through solution convergence and intelligent design. Although the design outcome of the truss structures presented in Examples 2 and 3 do not illustrate symmetry, the intent of this rule based methodology is to illustrate the creativity enhancement within the design
Table 3. Transmission line truss phase three design parameters.
Table 4. Signboard truss phase three design parameters.
Figure 11. Signboard truss.
Figure 12. Signboard truss phase one result.
Figure 13. Signboard truss final design.
Figure 14. Objective Function versus Generation.
Figure 15. Constraint versus Generation.
Table 5. Volume Removed per Genetic Algorithm Phase.
process through the injection of domain specific knowledge.
 Smith, J., Hodgins, J., Oppenheim, I. and Witkin, A. (2002) Creating Models of Truss Structures with Optimization. ACM Transactions on Graphics (TOG), 21, 295-301.
 Hamza, K., Mahmoud, H. and Saitou, K. (2003) Design Optimization of N-Shaped Roof Trusses Using Reactive Taboo Search. Applied Soft Computing, 3, 221-235.
 Sandgren, E. and Cameron, T.M. (2002) Robust Design Optimization of Structures through Consideration of Variation. Computers and Structures, 80, 1605-1613.
 Frame 2D (2003) Frame 2D.