1.3.1.» .n . .3... . {a ’cfimw - Z a? . stifle? . . ‘ . 355. fa. s . , . $3“? .3 . e . , E313 . ._. La . I. l 3 I)-lln e 2.2 . ‘ z..u“§§..n. V l ‘ Jain?” ‘ n:.H..1.....L I: Ian Vina-Pu! A s \(Abu‘flJ-u 31m: 2. 2... . “39!!! u... , . :83.flu _ . hill). i: ............_}ht . .EA 2: 5 10:3..19R 31.1: v ~ V ..l :3. . .. 5 gun, r .. Z. i . z! Pr...2.saoan..t..t:. w)4-I in! 31-"! 2.17 ‘ . .r 2.. “fiarlhen. . ‘ in“... . V l L, f . a! ‘ . hf. ..... 3.... 11. if... 1 5711.12 :5qu. 12.15:: x .51.} .51.. 5...... IQ.) .4 I...» I], 32...)?» 0.6. . x 3: 4.... LI. in” ‘ 3.395? ““31... 2 .1. :16 ‘ A059,; .3 2.!" 1.}; (vigil...- . ‘ ai-l)!.‘? \:D \ , 41555;? v .. vun I. u... . 1. 3.....Y; 1 : £51. {3.2253531 I, inst-Ari it Ox 3515:! i. . 3!. {Eusgh‘v fund. .3. .r \‘ It‘huuri T 51;. Qty.) . I? ~X 43 . .VI. .: 9.1.5... 1! all-5 13$...“er .3. yfiwzgga €5._,§,,,§%§.. rut... ...n9y£.un I; ‘ ‘ ¢ IV I . .36 . 3 .3: V V I 1...: . . THESiS Z ’7 1(- 1 ‘1‘ ,fi-VJ LIBnAnv Y Michigan State University This is to certify that the dissertation entitled TOPOLOGY OPTIMIZATION USING GENETIC ALGORITHMS WITH SUPERELEMENT DOMAIN DISCRETIZATION presented by Eric Christopher Myers has been accepted towards fulfillment of the requirements for MS . Mechanical Engineering degree in 5% flw Major professor Ayusézg, 20w MS U is an Affirmative Action/Equal! Opportunity Institution 0- 12771 PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE Jtszgfiy mm W.“ Topology Optimization Using Genetic Algorithms with Superelement Domain Discretization BY Eric Christopher Myers A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTERS OF SCIENCE Department of Mechanical Engineering 2000 ABSTRACT Topology Optimization Using Genetic Algorithms with Superelement Domain Discretization BY Eric Christopher Myers When using Genetic Algorithms in Topology Optimization there are two great disadvantages. The first is requiring the Finite Element Method to calculate displacements and the second is the large search space for the genetic algorithm. A method proposed to decrease the calculation time is to group a predefined number of elements and form them into a superelement. The search space is also reduced by eliminating poor material/void superelement configurations since these will not provide any useful structure to the design. The “good” configuration superelements can then be arranged in a domain by the Genetic Algorithm. The performance of the design is based upon material connectivity, displacement, and mass. To further aid in the search, the Injection Island method will be applied utilizing two different migration approaches: Domain Refinement Approach and Superelement Hierarchy Approach. The two migration approaches were compared for the performance of resulting structures, fitness and overall run time. Neither proved to be more beneficial than the other due to limited computational resources but did provide well-structured designs. The final results demonstrated that the superelement method is beneficial for use with the genetic algorithm. To my parents ACKNOWLEDGMENTS i would like to acknowledge both my advisors Dr. Erik Goodman and Dr. Ron Averill. Dr. Goodman has been extremely helpful in applying the genetic algorithm code GALOPPS. His insight and ideas for improving the genetic algorithm search were a tremendous help. Dr. Averill has been extremely helpful in applying the finite element code and modeling of the design domain. His insight and guidance were a tremendous benefit. Lastly, I would also like to acknowledge Dave Eby who provided help in the gray areas of applying a finite element model within the genetic algorithm. TABLE OF CONTENTS List of Tables .................................................................................................. vi List of Figures ................................................................................................. vii List of Abbreviations ....................................................................................... x Chapter 1 Introduction 1.1 Introduction .................................................................................... 1 1.2 Objective ........................................................................................ 3 1.3 Background ................................................................................... 4 1.4 Literature Review ........................................................................... 9 Chapter 2 Superelement Configuration Determination 2.1 “Good” and “Poor" Superelement MateriaWoid Configurations 21 2.2 Superelement Check ..................................................................... 25 Chapter 3 Superelement Stiffness Matrix Calculations 3.1 Superelement Stiffness Matrix ....................................................... 36 3.2 Application of the Superelement Stiffness Matrices ...................... 39 Chapter 4 Genetic Algorithm 4.1 Introduction and Background ......................................................... 46 4.2 Two-Dimensional Crossover ......................................................... 50 4.3 Two-Dimensional Mutation ............................................................ 54 4.4 Fitness Equation ............................................................................ 58 4.5 Domain Refinement Approach ...................................................... 64 4.6 Superelement Hierarchy Approach.. ............................................. 69 4.7 Two-Dimensional Mutation for Superelement Hierarchy Approach ...................................................... 73 4.8 Design Evaluation .......................................................................... 77 Chapter 5 Migration Approach Comparison Overview 5.1 Overview ....................................................................................... 82 5.2 Domain Refinement Approach Results .......................................... 85 5.3 Superelement Hierarchy Approach ................................................ 97 5.4 Migration Approach Comparisons and Conclusions ...................... 110 5.5 Future Work ................................................................................... 116 References ..................................................................................................... 1 19 LIST OF TABLES Table 3.1.1. MateriaWoid properties used in the stiffness matrix calculation ............................................................................. 36 Table 4.4.1. Coefficients and base values used in the fitness equation ......... 60 Table 4.5.1. Base displacement values for each level of superelement resolution ............................................................................. 67 Table 5.1.1. GA parameter values used in the Domain Refinement Approach ....................................................................... 83 Table 5.1.2. GA parameter values used in the Superelement Hierarchy Approach ................................................................ 83 Table 5.2.1. Fitness arguments of the best resulting designs from level one ......................................................................................................... 92 Table 5.2.2. Fitness argument of the best resulting designs from level two ......................................................................................................... 94 Table 5.2.3. Fitness arguments of the best resulting designs from level three ....................................................................................................... 96 Table 5.3.1. Fitness arguments of the best resulting designs from level one ......................................................................................................... 103 Table 5.3.2. Fitness arguments of the best resulting designs from level two ......................................................................................................... 106 Table 5.3.3. Fitness arguments of the best resulting designs from level three ....................................................................................................... 106 Table 5.3.4. Fitness arguments of the best resulting designs from level four ........................................................................................................ 109 vi LIST OF FIGURES Figure 1.3.1. Schematic of cantilever beam model ........................................ 4 Figure 1.3.2. Example of a meshed domain using triangle elements and explanation of how elements are arranged to form a superelement .............. 5 Figure 2.1.1. Examples of good materiaVvoid superelement configurations for one material island .................................................................................... 21 Figure 2.1.2. Example of “good” materiaVvoid superelement configuration for more than one material island ............................................. 23 Figure 2.1.3. Examples of “poor" materiaVvoid superelement configurations .......................................................................... 23 Figure 2.2.1. Example of integer conversion to binary form, which represents materiaVvoid superelement configuration ..................................... 25 Figure 2.2.2. Summary flowchart of configuration checking algorithm ......................................................................................................... 26 Figure 2.2.3. Individual triangle element numbering scheme ......................... 27 Figure 2.2.4. Summary flowchart of the material island finder algorithm ........ 28 Figure 3.1.1. Nodal form of superelement before and after condensing out the internal 5 nodes from the stiffness matrix ........................................... 38 Figure 3.2.1. Plot of calculation time in CPU seconds versus number of elements/superelements for reading stiffness matrix from file ....................... 41 Figure 3.2.2. Plot comparing calculation time in CPU seconds versus number of elements/superelements for calculating stiffness matrix ............... 42 Figure 3.2.3. Flowchart summarizing the steps in calculating the stiffness matrix in the USELM subroutine ....................................................... 43 Figure 4.1.1. Example of a 2x2 superelement domain showing the numbering scheme for the superelements ..................................................... 47 Figure 4.2.1. Arrangement of outer edge indexes for equal odds of selection ............................................................................................ 51 Figure 4.2.2. Example of cut line joining two randomly chosen endpoints ..... 52 vii Figure 4.3.1. Neighbor selection patterns for each element type ................... 55 Figure 4.4.1. Base design used for determining base mass and displacement ......................................................................... 60 Figure 4.4.2. Penalty curves used to determine coefficients in fitness equation .............................................................................................. 61 Figure 4.5.1. Migration mapping of Domain Refinement Approach ................ 65 Figure 4.5.2. Example of mapping an element to the next domain level ........ 66 Figure 4.6.1. Example superelements from each of the four levels of superelement hierarchy ................................................................................. 69 Figure 4.6.2. Migration mapping for Superelement Hierarchy Approach ........ 70 Figure 4.7.1. Neighbor pattern for mutation of the first level .......................... 73 Figure 4.7.2. Neighbor pattern for mutation of the second level ..................... 74 Figure 4.7.3. Neighbor patterns for mutation of the third level ....................... 75 Figure 4.8.1. Summary flowchart of the design evaluation procedure ............ 78 Figure 5.2.1. Plots of fitness versus time at each level including all three runs ................................................................................................... 87 Figure 5.2.2. Plots of mass versus time at each level including all three runs ................................................................................................... 88 Figure 5.2.3. Plots of displacement versus time at each level including all three runs ................................................................................................... 90 Figure 5.2.4. Plots of material islands versus time at each level including all three runs ................................................................................................... 91 Figure 5.2.5. Resulting design from level one for all three runs ..................... 92 Figure 5.2.6. Resulting designs from level two for all three runs .................... 93 Figure 5.2.7. Resulting designs from level three for all three runs ................. 95 Figure 5.3.1. Plots of fitness versus time at each level including all three runs ................................................................................................... 98 viii Figure 5.3.2. Plots of mass versus time at each level including all three runs ................................................................................................... 100 Figure 5.3.3. Plots of displacement versus time at each level including all three runs ................................................................................................... 101 Figure 5.3.4. Plots of material islands versus time at each level including all three runs ................................................................................................... 102 Figure 5.3.5. Resulting designs from level one for all three runs .................... 104 Figure 5.3.6. Resulting designs from level two for all three runs .................... 105 Figure 5.3.7. Resulting designs from level three for all three runs ................. 107 Figure 5.3.8. Resulting designs from level four for all three runs ................... 108 Figure 5.4.1. Resulting final designs from Domain Refinement Approach ..... 111 Figure 5.4.2. Resulting final designs from Superelement Hierarchy Approach ................................................................ 112 Figure 5.4.3. Plot of fitness versus run for comparison of migration approaches ..................................................................................... 113 Figure 5.4.4. Plot of Run time versus run for comparison of migration approaches ..................................................................................... 114 LIST OF ABBREVIATIONS CPU Central Processing Unit DOF Degrees Of Freedom E Young’s Modulus FEM Finite Element Method GA Genetic Algorithm GALOPPS Genetic Algorithm Optimized for Portability and Parallelism System iiGA Injection Island Genetic Algorithm SE Superelement MARC Mentat Analysis Research Corporation USELM User Element Subroutine p Material Density v Poisson’s Ratio Chapter 1 INTRODUCTION 1.1 Introduction The use of genetic algorithms for structured topology optimization usually requires the use of a finite element calculation to obtain a design’s displacement(s), which is a requirement to evaluate its performance. The finite element calculation typically requires a large amount of time for each individual to be evaluated in the genetic algorithm. This amount of individual evaluation time is dependent upon the element resolution of the design domain. This evaluation time summed over many individuals and many generations results in a lengthy run time of the genetic algorithm to obtain a solution. A fine element mesh is desired to generate a good design, which constitutes a disadvantage of using genetic algorithms for topology optimization. Increasing element resolution in turn increases the search space for the genetic algorithm. When using a domain of elements where each single element consists as one of two states of either material or void, the total number of possible designs is 2", where n is the number of elements. As can be seen, this number can grow very quickly, greatly increasing the search space, causing a longer run duration for the genetic algorithm. This also constitutes a disadvantage to the genetic algorithm of using a fine element resolution. A method is proposed to reduce the finite element calculation time as well as the search space. Both reductions are achieved by creating a new element or superelement using 16 standard 3-node plane stress triangle elements arranged into particular configurations. The superelement will provide decreased calculation time by reducing the size of the domain’s overall stiffness matrix. The search space is reduced by eliminating undesirable materiaVvoid superelement configurations, thus limiting the search space to only the more desirable configurations. 1.2 Objective The main objective of this thesis is to demonstrate that superelement domain discretization will provide reasonable structures and decrease the overall amount of time that it takes for the genetic algorithm to obtain an optimal solution. This is an area that poses the greatest challenge to the genetic algorithm in the area of topology optimization, as compared to the homogenization method. The genetic algorithm is much more robust than the homogenization method. The homogenization method relies on many assumptions and complicated equations for the topology calculation. These assumptions and mathematical equations also tend to limit complicated geometry as well as the number of loads and constraints for the design domain. The robustness of the genetic algorithm extends its ability to optimize various loadings or constraints placed upon a beam or optimize for more than one criterion, such as vibration and strength, simultaneously. There will be no comparisons to any results or calculation times of the homogenization method. Instead, two different representation schemes and migration approaches will be set up, analyzed, and compared. The two approaches are labeled Domain Refinement Approach and Superelement Hierarchy Approach. These two approaches are fairly different in the approach that they take to migration, which will determine whether either provides an advantage over the other. 1.3 Background The optimization objective and the model can now be presented. The objective of this topology optimization is to minimize mass subject to a maximum displacement constraint of the node with the applied load as stated below; F(x1,x2,x3,...,xn)=[y1,y2,y3,...,yn] Minimize: mass Constraints: displacement 5 .3567 mm Where the function F(x) represents the mass of the design dependent upon the state variables x1 - xn. The model to be optimized will consist of a cantilever beam which will be fully constrained on one end, with a vertical load of 1440 N directed upwards centrally located on the other end. A schematic of the model is shown below in Figure 1.3.1. The beam has a length of .16 m and a height of .10 m and A .////// Figure 1.3.1. Schematic of cantilever beam model will consist of a thin uniform thickness of .003 m. The domain dimensions as well as the constraint and load locations are the same as used in the topology study used by Bendsee et al. [3]. The uniform thickness allows for the use of 3-node, 2-DOF/node plane stress triangles for calculating the displacement of the loaded node. The design domain for a particular case may be meshed as shown below in Figure 1.3.2. ———> v i Figure 1.3.2. Example of a meshed domain using triangle elements and explanation of how elements are arranged to form a superelement The triangular elements are arranged so that four elements comprise a block and each individual triangle will consist of either material or void. The individual triangular elements will provide good materiaVvoid resolution, unlike that of square elements. The triangles allow for less material within a block as well as angled material configurations. As with square elements, an edge of a band of material may appear very rough or jagged unless many elements are used. The triangular elements can be arranged to produce a non-vertical, non-horizontal edge that is smooth; therefore not as many elements are required to provide a smooth edge, as is the case for the square elements. From Figure 1.3.2, which is a fairly small domain, it can be seen that in order to obtain a design of high resolution, many triangular elements are required, which results in a long displacement calculation time. Arranging the triangular elements so that 4 blocks or 16 triangle elements comprise a superelement as circled in Figure 1.3.2 can shorten this long calculation time. The 16 triangle elements are assembled into the superelement global stiffness matrix, yielding an element as shown at the bottom of Figure 1.3.2. After the 5 internal nodes from the global stiffness matrix are condensed out, the resulting superelement consists of 8 nodes around the perimeter. The use of superelements provides a great advantage to the finite element calculation. Essentially, fewer elements are solved within the given domain, which translates into a smaller global stiffness matrix for the domain. For a superelement which consists of 16, 3-node 2-DOF per node elements, the matrix has the size 26x26 before condensing. After condensing, the matrix is reduced to a 16x16 where 10 DOF are concealed. To illustrate how this reduction translates to the design domain, an example will be used. If the domain consists of 144 elements as in Figure 1.3.2, this translates to 9 superelements. A total of 90 DOF are concealed from the domain’s global stiffness matrix, which reduces the number of calculations and yields a quicker calculation time. Superelements also provide an advantage to the genetic algorithm. For a particular superelement, there are 216 or 65,536 total possible materiaVvoid configurations. Many of these superelement materiaVvoid configurations are undesirable and can be eliminated, reducing the overall total possible to 1341 “good” configurations. This elimination of undesirable configurations reduces the search space of the genetic algorithm, which increases the searching efficiency. As in the case of Figure 1.3.2, if the full triangle elemental domain is used in the search, there is a very large number of possible designs, a total of 2144 or 2.23E+43, which is a vast search space. Using the good superelement configurations for the same domain yields a search space of 13419 or 1.40E+28, which is still large but dramatically smaller than using the full triangle elemental configuration. This will ultimately yield an optimized design much more quickly. To increase the search efficiency of the genetic algorithm further, the injection island method developed by Lin et al. [22] will be applied. An example of how the injection island method is applied to a design, and its benefits, were demonstrated by Eby [9]. The injection island genetic algorithm (iiGA) uses multiple subpopulations employing different representations of the search space in different subpopulations. The injection island method searches for a design in subpopulations at a lower resolution and passes or migrates a good design on to other subpopulations using a greater resolution, for further refinement. Two different iiGA representation and migration approaches will be used in the study, which will compare their performances. The first iiGA migration approach, labeled as Domain Refinement Approach, will use three different representations or domains that increase successively the number of superelements. The coarsest resolution will contain a small number of superelements, allowing for a small search space. This will yield a rough outline of the design shape. This shape is then passed on to the next level of resolution, after re-mapping the design to the refined domain. This process continues until the finest resolution is reached. The second iiGA migration approach, labeled Superelement Hierarchy Approach, will utilize different materiaVvoid resolutions within the superelement. There are four hierarchy levels of material/void configurations used for this approach. The first and coarsest level restricts the entire superelement to only material or void. The second level divides the superelement into four blocks of material/void configurations. The third level splits the blocks of the second level into triangles, which allows for angled configurations. The fourth and final level is the finest hierarchy, consisting of yet smaller triangle elements. A design, as done in the previously mentioned iiGA migration approach, is found in a rough outline and then migrated to the next level for further refinement, and the process is continued until the final resolution is reached. In this way the finest level can find an optimal design much sooner than if it were searched as the only domain. The search space is greatly reduced at the lowest levels of resolution, allowing the genetic algorithm to be pointed in the correct direction for the search. Ultimately, applying the superelement coupled with the injection island method will provide a fast search for a very fine resolution design domain. we. 1.4 Literature Review Optimization is very beneficial in the field of engineering. It has many applications in the areas of structures, mechanical systems, manufacturing, and electronics. Structures can be optimized to provide the greatest strength at the lightest weight, which is beneficial in many products such as automobiles and aircraft. Mechanical systems can be optimized for many parameters. One parameter may be to provide quick motion with minimal oscillation; other possible parameters for example, are the locations and the size of counterweights, as demonstrated by Eschenauer—Koski [10]. There are many applications in manufacturing as well, that mainly involve structures, but one other is for layout optimization for minimal material scrap, as shown by Eschenauer-Koski [10]. This provides the best utilization of the material so that minimal scrap is produced. The last area, electronics, has many applications as well. Typical applications include finding resistor or capacitor values that provide voltages or frequencies of specific values. In every one of the previously mentioned areas for applying optimization, there is a specific goal or objective that is desired of the design. Each of these problems may require many parameters that are dependent upon other adjustable parameters. The determination of these parameters becomes very difficult by a simple calculation or by trial and error. Some form of computational method will often be required to determine these parameters. There are various methods for calculating the parameters of the optimal design, but two main areas of computation involve gradient and exhaustive search algorithms. The main focus will be on structures, involving the two computational methods mentioned previously for achieving an optimal design. This literature review will discuss calculation procedures as well as some examples for three classes of optimizations; which are size, shape, and topology optimizations. The size optimization finds the optimal size or thickness of members in a current design of a structure. The two classes of shape and topology optimization are similar in concept, but differ greatly in the domain representation. The calculations between the gradient search and an exhaustive search algorithm are very different. The gradient search usually utilizes the gradient method where the derivative of the equation that describes the model is used to find the optimal design. This factor tends to limit the applicability of the gradient search for complicated loading conditions on structures, for example. Using the gradient method with FEM equations is not straightforward and may require the equations to be manipulated in some way. Many studies have been done using FEM equations directly by Bendsee [4], Hajela and Jih[14], Haslinger and Neittaanmaki [15], and Jansen[17]. Usually with gradient search FEM optimizations a strain energy equation is used, which describes the overall energy state of the design. As will be explained later, the strain energy equation is minimized. This represents a system’s tendency to gravitate toward a minimum energy state. 10 Fl 0', Ps s The exhaustive search algorithm can utilize the FEM equations that describe the domain directly. The exhaustive search algorithm is a brute force approach where every possible design is run through and analyzed to find the best design. Depending on the design, there could be many possibilities and a method is required to provide a smarter search. One such algorithm for smart searching is the Genetic Algorithm (GA), which uses bit strings or chromosomes to describe the domain. The process of using a GA and what is encompassed is explained by Jenkins [19] and Goldberg [11]. It uses these chromosomes analogously to the use of chromosomes found in living organisms. The chromosome describes the design’s attributes and is evaluated for performance. A part of the chromosome representing one design is then exchanged with part of another. If one of the chromosomes contains a relatively favorable trait that happens to be passed on to another, it may encounter a chromosome with some other favorable trait. Much in the way living organisms evolve to suit their environments, a design as well can evolve to suit its objective and constraints. Size optimization in structures improves a current design by finding dimensions that will satisfy a set of objective and constraints. The most popular type of problems for this optimization is sizing the beams of a truss. Depending on the cross-section of the beams, specific dimensions can be adjusted that will provide adequate strength while decreasing the mass. Some of the studies done on sizing tmss beams were demonstrated by Jensen [20], Nakanishi and Nakagiri [28], and Picuga [29]. 11 "I r '5 q ”to. ‘79.-- )(f-Jn’f " "‘ A 10-beam truss structure analyzed by Picuga [29] is optimized not only for beam size but also for multiple loads with vibration and other factors which will not be mentioned in order to avoid confusion. The beams of the entire truss are of constant cross section but can vary dimensionally. A gradient search is used in which FEM equations are manipulated so that the structure is optimized by using compliance to provide the lowest value of strain energy. Studies conducted on sizing of trusses have also been done with exhaustive search algorithms such as GA’s (Genetic Algorithms) by Jensen [20], and Rajan [32]. The studies conducted by Rajan [32] experimented with other factors but included sizing of various truss structures. The beams of the entire truss were of a constant cross section, but the dimensions of the beams could be varied. The study conducted by Jensen [20] was very similar, where a 10-bar truss was used and the beams were optimally sized to support the given load and constraints. The gradient search for sizing as done by Picuga [29] has advantages mainly in the time of finding the optimal design. The gradient search is somewhat limited for complicated problems due to its dependence on applying the gradient method. As shown by the problem represented by Jensen [20] using a 10-bar truss, the formulation of an equation by hand to describe the system by would be very time-consuming, with significant room for human error. With the benefit of FEM commercial code, these types of problems can be handled fairly easily. The dimensions for standard beam cross sections can be more precisely determined by the gradient search than by the genetic algorithm. The exact 12 '- dimension required for the detail of the beam cross section can be specified. The only disadvantage with this is that many of these standard beam cross sections may not be readily available from the manufacturer with the calculated dimensions. The GA can also compute these numerical values for beam dimensions, but the search can be taken further. Instead of calculating the beam dimensions the chromosome can be configured to reference a library of standard beam cross- sections and dimensions. The GA will select beams from this library and find the best cross section and dimensions as well as placement in the model for the beams. Shape optimization is probably the most computationally intensive of the three, whether gradient or exhaustive search algorithms are used. The optimization involves finding the optimal shape of a structure that will satisfy the specified requirements. Usually the FEM is used, where locations of beam elements or optimal cross-sections of a beam are to be determined. The beam placement optimization involves an initial layout of all possible beam locations, as analyzed by Belding [2]. There are many examples of these types of problems - various areas are studied by Hyca [16], Murotsu et al. [27], Nakanishi and Nakagiri [28], and Rajan [32], and there is a study on hole shape optimization by Backlund and Rikard [1]. The gradient search studies done by Hyca [16]'in'.lolved optimizing the cross-sectional shape of a thin walled beam. Using standard beam assumptions, a complicated bending equation using nonwarpable cross-sections was 13 formulated, involving the outer perimeter of the beam as one of the variables. The beam was clamped on one end, and there was a roller on the other, with a distributed load placed along the entire length of the beam. It was found that the beam cross-section resulted as approximately rectangular. Also, shear-lag was eliminated using theoretically nonwarpable cross-sections. The gradient search shape optimization of a truss structure, as done by Murotsu et al. [27], didn’t rely on the failure criterion of the material exclusively for the optimization - i.e. on Young’s modulus. Instead, failure probabilities dependent on dimensions of each member were used. This allowed for the analysis of buckling for specific truss members as well. The analysis was compared to optimal trusses found using the failure criteria of Young’s Modulus. It was found that the Young’s Modulus failure criterion provides sufficient results where no buckling would occur in the compared results. Another study of shape optimization - that of hole shape in a composite carbon fiber panel - was conducted by Backlund and lsby [1]. The original panel utilized standard round holes for lightening, but the maximum size of the hole was required while maintaining the panel’s same strength. The study was done using gradient search, and found that elliptical holes provided the same strength and reduced material further than using standard round holes. Genetic Algorithms have also been used successively in shape optimization of trusses. A 2-D cantilever truss frame and a 3-D beam cube structure are analyzed by Nakanishi and Nakagiri [28]. A layout of all possible locations of beams or ground structure is first set in the 2-D cantilever problem. 14 The 2-D cantilever ground structure is solved using four different objectives and constraints. The results obtained by the genetic algorithm are then compared to results from gradient searches. The results of the genetic algorithm and gradient search calculations were very similar. The 3-D cube beam structure also had an initial ground structure specified. The 3-D cube structure was subjected to various loading conditions that resulted in differing final designs. These final designs determined by the genetic algorithm were compared to results from that of gradient searches, and are very similar. Another shape optimization of trusses using the genetic algorithm was conducted by Rajan [32]. The study that was conducted actually included all three types of optimization in one design, and all were calculated simultaneously. The beams of the truss were optimized for size; the shape of the structure was optimized by the location of beams based upon a ground structure, and a topology optimization was done for location of constraints, which will be discussed later. Two sizes of trusses were examined - a 6-node and a 14-node truss. The results from both size trusses were very good and compared similar to those of gradient search results. One important point found was that the ground structure played a very important role in the shape of the optimal truss design. This demonstrates the versatility of the genetic algorithm, where all three types of optimizations can be applied to one design. 15 I wgts ‘f "v‘ ."‘0 ’ _p_‘¢ ..., '9' ‘J .u a‘p The area of topology optimization is fairly new but has had many great advances both in the gradient search calculation and using the genetic algorithm. Topology optimization is similar to shape optimization but instead of determining the placement of beams, a domain of plane stress elements is specified. These plane stress elements contain either a composite of material and void or are composed entirely as either material or void. The optimal placement of the material and void is to be determined within the domain to satisfy the objective and constraints. The optimal structure that is composed of material will appear in the domain, representing the optimal shape. The gradient search has had great success at finding optimal topology structures in the shortest time. This short calculation time is attributed to the homogenization method, which was developed by Bendsee et al. [3] and studied by Belding [2]. The homogenization method uses a microstructure of cells to characterize the material properties of the elements in the design domain. The cells contain a composite of void and material. Each cell has within it a rectangular hole, with its size determining the cell’s material properties. The classical problem for topology optimization is the 2-D cantilever beam problem. The beam is fully clamped at one side while a point load is placed at the other. The homogenization method provides very impressive results, as found by Belding [2] and Bendsee et al. [3]. The structures are well defined and symmetrical about their centerlines. Topology optimization by the homogenization method has been extended to three-dimensions as well, as studied by DeRose [7][8]. The microstructure cell 16 c to. was simply expanded to a cube called a voxel, where dimensions within the cube determine the amount of material/void composition. A symmetric cube was used in one of the cases studied that resulted in a very impressive design. It was noted that the 3-D finite element calculation required a long time and a large amount of disk storage. DeRose [8] later used Wavelet-Galerkin techniques to reduce the amount of calculation time and the amount of disk storage. These techniques proved beneficial in similar problems and provided improved calculation time and smaller storage requirements. The 2-D cantilever beam has been studied successfully using genetic algorithms as well. The GA has one inherent disadvantage, which is the long calculation or search time required, because many designs must be evaluated, and each is done using FEM to calculate displacements for the design. When the domain element resolution becomes very fine, the calculation time becomes longen A study conducted by Chapman et al. [6] used the cantilever model in an analysis to determine a way to reduce the search space. This would ultimately reduce the required time of the search as well. The main idea was to limit the chromosome to a maximum length. As the design domain utilized more elements the length of the chromosome would increase. In order to maintain a specified chromosome length, the domain was broken up into quadrants such that a chromosome described a quadrant. Now many chromosomes of smaller lengths as compared to one chromosome of a very long length described the domain. The advantage for using smaller 17 chromosome length lays in the crossover and mutation operations, alleles in shorter chromosomes have better odds of being cut or mutated than those of a long chromosome. In other words, change doesn’t occur as quickly in long chromosomes as compared to short chromosomes. The final results were fairly good, in a study where a course element resolution varied from coarse up to very fine resolution. The very fine resolution obtained a reasonable structure within a reasonable amount of time due to utilizing the method of shortening the chromosomes. The fine domain was run without chromosome shortening and no reasonable design was found after searching for a very long time. Another study utilizing genetic algorithms for the cantilever problem was done by Chapman and Jakiela [5], which attempted to compare results of the GA to that of the homogenization method. In order to obtain similar results, the fitness calculations required the use of the compliance equation for the performance evaluation. The resulting design by the GA fared very well, where the mass was less than that of the homogenization method. The structural shape was very similar, but lacked exact symmetry about the centerline. A beam’s cross-sectional shape can also be optimized by topology optimization. A study done by Jensen [20] looked at optimizing the cross section of an automobile bumper beam. The beam was loaded in the center, simulating a rear end collision, and constrained at both ends, which simulated the bumper attachment to the car. Plastic, aluminum and steel materials were used, and the beam cross-sections were allowed to develop in segments. The cross section of 18 W ‘I‘ . "‘..c '0 the beam could vary independently in each segment. The resulting cross-sections tended to an l-beam shape regardless of the material used. There have been many advances in genetic algorithms that have allowed for reductions in the search time for optimal designs. Use and development of the GA is relatively new, and much research is still required to demonstrate its capabilities. One area that has been improved is the method of crossover. There are several ways that the loci can be selected and exchanged between two chromosomes. A study done by Kane and Schoenauer [21] examines the performance of various types of crossovers specifically on two-dimensional shape optimization. The types of crossovers examined include 1-point, 2-point, block-2, block-3, diagonal and uniform crossovers. The 1-point , 2-point, and uniform are the standard crossovers utilized in many GA problems that are not of two- dimensional shape optimizations. The 2-block and 3-block crossovers require that the chromosome be in two-dimensional array form, where the respective number of blocks of indices is exchanged between the chromosomes. The diagonal crossover also uses the chromosome in its two-dimensional array form and selects indices to be exchanged diagonally. The various crossovers were run in the search and examined without using mutation. It was found that the 2-block provides the best results, but diagonal, block-3, and uniform crossovers were not far behind. Overall, the two-dimensional crossovers provided much better results than the standard 1-point and 2-point crossovers for a two-dimensional optimization. This indicates that the crossover is 19 problem dependent and should be a consideration when applying a GA for the search. Another advancement in the use of genetic algorithms is the capability of parallel processing. It provides a great advantage when many processors can run, searching many populations simultaneously and providing a large reduction in search time. There have some studies where examples have been used to demonstrate the advantages(for example, by Goodman ef al. [12], Punch et al. [30][31]). Though the big gains in parallel genetic algorithms require multiple processors, loosely coupled, running in parallel, such hardware does provide a definite advantage in search time for the genetic algorithm. The parallel processing capability has spawned another advancement in the genetic algorithm search. The Injection Island Genetic Algorithm provides a great advantage in many problem, as demonstrated by Lin et al. [22] and Eby [9]. A coarse search space is searched initially, which can provide a good, but rough, design. This design can then be migrated to another level where it can be refined further in a slightly larger search space. This process can be repeated up to a very fine level where the search space is very large. This process helps point the large search space in the correct direction for the search for the optimal design, which ultimately reduces the search time. 20 Chapter 2 SUPERELEMENT CONGIFURATION DETERMINATION 2.1 “Good” and “Poor" Superelement MateriaWoid Configurations The placement of material/void within a superelement is very crucial. Poor material/void placement can produce a superelement that is very undesirable or doesn’t contribute any valuable structure or strength to the domain. With this in mind a subset of “good” configurations were decided upon which were thought to provide desirable structure, to contribute to overall domain strength, and to provide good superelement-to-superelement connectivity. A couple examples of good materiaVvoid configurations are shown A B 1 material island Material encompasses Connected >=2 sides complete side Figure 2.1.1. Examples of good material/void superelement configurations for one material island in Figure 2.1.1. The first step for a “good" configuration requires that there be at most one island of material within the superelement, where an island of material is defined as a set of connected material elements as shown in Figure 2.1.1 (A). Two material (non-void) elements are adjacent if and only if they share two 21 nodes. A material element i is connected to a material element j if i is adjacent to j or if i is adjacent to a material element connected to j. If all the material elements are connected within the superelement in this fashion, a single material island will result. This insures that the superelement will not contain any configurations where several elements are connected at one node, creating a high torque where a large displacement could occur. If the superelement contains one material island then the following condition must also be present. The condition is that material elements must continuously connect to at least two edges of the superelement, which means that at least one of the two elements on each edge for at least two edges must contain material. The configuration shown in Figure 2.1.1 (A) is connected to three sides due to at least one material edge element existing on each side. The other condition shown in Figure 2.1.1 (B) is only allowed for one material island superelements as well but only for four special cases of material along one edge. This contradicts the condition previously stated for material being connected to at least two sides. This particular case was required for mapping elements from a smaller to a larger element resolution. The mapping of one element from the smaller domain required four elements in the larger domain. Therefore a superelement as shown in Figure 2.1.1 case (B) would result. The mapping process will be explained in greater detail in Section 4.5. One condition was allowed for cases for more than one material island. This condition allowed any combination of material elements along only the edge of the superelement. The case shown in Figure 2.1.2 is one particular case, but 22 Any combination of edge elements Figure 2.1.2. Example of good materiaVvoid superelement configuration for more than one material island any combination containing material only in edge elements is allowed. These were allowed because they may add mass for stiffening onto edges of beams or used as bracing. A few examples of poor material/void configurations are shown below in Figure 2.1.3. As can be seen in Figure 2.1.3, for the case of more than one Material islands >1 Single nodes at sides Connected at 1 side Figure 2.1.3. Examples of poor material/void superelement configurations material island, there can be points where elements meet together at one node. This can cause unstable configurations due to high torque at these points resulting in large displacements. 23 The second case where single nodes or points at the edge occur can also cause problems similar to the last case. Though the problem isn’t apparent from looking at the configuration, this superelement could be connected to an adjoining superelement that has a similar shape resulting in many material elements connected to one node. Eliminating these particular configurations reduces the possibility of this problem occurring. The last case is where material is connected at only one side of the superelement, but contains internal material elements. As can be seen from Figure 2.1.3 (C) a beam is formed that cantilevers off an edge. This will not provide any structural strength over a configuration with only one edge element, so these particular cases were discarded. 24 2.2 Superelement Check A program was written that applied particular checks to each of the 65,536 (216) material/void configurations. The flowchart in Figure 2.2.2 outlines the configuration-checking algorithm. The first element of the program must be able to provide every possible material/void configuration. This was achieved by using the range of 0-65.535 and converting each integer within this range into its binary form. An example of the process is shown below in Figure 2.2.1. In an integer's binary form, a 0 5047 i Convert to binary number 0001001110110111 l Binary represents meterialNoid elements Figure 2.2.1. Example of integer conversion to binary form, which represents materiaVvoid superelement configuration represents void and a 1 represents material, which defines the superelement’s materiaVvoid configuration. This binary form is then used in the program for the checks to see if it passes the specified restrictions of the previous section. 25 check for comb. of edge elements passto or I check for nodes dong edges pass-0 or I check for one edge specii case pass-0 or I prim to file pass 1 index config. nunber pri" to file; pass. config. nunber. binary form Figure 2.2.2. Summary flowchart of configuration-checking algorithm 26 The number of material islands within the superelement configuration is first counted. This determines which checks will be applied, as can be seen in Figure 2.2.2. If there is one island, then a series of checks are utilized; otherwise the superelement edge is checked for combinations of edge elements. A summary flowchart of the island finder algorithm is shown on the next page in Figure 2.2.4. The binary materiaVvoid representation of a superelement is required for use in the island finder. This binary number is used to create a list of material elements where an element is added if it is represented by a 1and ignored if represented by a 0. In this way, the material list only contains the numbers of elements that are material. The numbering of the individual triangle elements is shown below in Figure 2.2.3. 2 6 1 3 5 7 4 8 1D 14 9 11 13 15 12 16 Figure 2.2.3. Individual triangle element numbering scheme The material list is first transferred to a-master list. The master list will be used and modified to keep track of what material elements have been either checked for adjacent material elements or checked as an adjacent material 27 @ Ahab binary coding/ ~Shift indices below \I/ up one in masterlist ' -index mle' OTW‘. ”a? 4ndex addinc add masteristhral] to rite master ist from comectivityladdinc] maerial elemere in array stat=0 ehileaddnol-re - \4 stop-lofmal.el f step-1 J, J, at get element number search maerti list C5D from for masterlstbrd] connectivity [read‘nc] search domain to I“ “I find element type \ erist \L index readnc We element numbers of 3 adjacent sides teach masterlist to deten'nine if mxerid elemens it masterlist -shift indices below to I it masterist -Increment addino for each found -add elements found to connectlvtyladdim] Figure 2.2.4. Summary flowchart of the material island finder algorithm 28 element. If an element number to be checked is found, it is removed from the master list. The remaining elements are then shifted up one index. The entire material list is run through to check for connected material elements. If a material element given in the material list is not found in the master list the checking and counting of material elements is skipped. The unfound element is assumed to be already counted as part of an island. This is done to ensure that no material elements are overlooked. The master list is searched for the element number from the material list of the current index of the variable val, which ranges from 0-65.535 as seen in Figure 2.2.4. When the material element number is found in the master list, it is first written to another list, which is the connectivity list. The connectivity list will contain the connected material elements that are part of the continuous material path. The remaining master list indices are then shifted up as mentioned previously, the number of islands variable numisle is indexed by one, and the variable addinc is indexed by 1. The variable addinc as seen in Figure 2.2.4 keeps track of the number of entries in the connectivity list. Due to the configuration of the triangular elements within the superelement, the entire superelement must be searched in a sequential manner in order to determine an element’s location. The triangle elements have four orientations within each block. To better visualize, element 1 from Figure 2.2.3 would be type 1, element 2 is type 2, element 3 is type 3, and element 4 is type 4. Each element of type 1 is searched throughout the entire superelement; then type 2 is searched, etc., until the number matches the one from the connectivity list. 29 This element type is important due to the numbering scheme and shape of the elements, so that the three adjacent elements can be calculated correctly. Once the current element’s location is determined, it is then searched on all three sides (or two, depending upon location) for an adjacent material element using the master list. Each adjacent material element found is added to the connectivity list and removed from the master list. Addinc is then indexed for each one found. After all adjoining material elements have been found and added to the connectivity list, the variable readinc is indexed by 1. The readinc variable keeps track of the current index being used in the connectivity list as shown in Figure 2.2.4. The next element in the connectivity list is then searched on all three sides and any adjacent material elements are added to the connectivity list. This process is repeated until the end of the connectivity list is reached, which occurs when addinc becomes equal to readinc. When this condition occurs, it indicates that no more material elements have been added to the connectivity list for the current material path. After the end of the connectivity list is reached, the next material element number in the material list is searched for in the master list. If this particular element is in the master list, then another island exists and numisle is indexed by 1. The set of connected material elements found for this next element is appended to the connectivity list. Else if no elements exist in the master list then the number of islands is equal to the current value of numisle. After the material islands have been counted, the type of check can be determined and performed. If there is one island, the configuration check is 30 e - ' . ""“f"-‘lwe‘ . composed of two checks that mainly look at the material elements at the edges of the superelement so that the restrictions for good superelement materiaVvoid configurations are satisfied. The superelement configuration is initially assigned a 0 indicating a poor configuration. The configuration passes through each check successively, if it passes the restrictions it is assigned a 1. The following two checks are done only if the superelement consists of one material island, otherwise these operations are not necessary and only the absence of any internal (non-edge) elements must be determined. The first edge check is for the material to be connected to at least two edges of the superelement. This implies that there must be a continuously connected material path including material edge elements from at least two sides of the superelement, and is intended to alleviate the cantilever beam configuration. The edge elements are numbered 1,2,6,7,9,12,15, and 16, as seen in Figure 2.2.3. The material list from the island finder is used, and the known edge elements are searched in this list. The sides of the superelement are checked in sequence to determine if at least one of the two edge elements on the edge is material. If so, then a counting index is incremented, until at least two edges are found that satisfy this condition. Since this check is only done if one material island exists, it is clear that the material path between the edges is connected. Once two connected edges are found, there is no need to search any further for other edges since at least two edges is the requirement. If the superelement passes, it is assigned a 1 and 31 continues on to the next check for single nodes on an edge. Othenrvise if the superelement has one or fewer edges containing material, pass remains 0 and the next edge check is skipped. The second edge check eliminates single node edge configurations or points. This check is also only done if one material island exists and if the superelement passes the previous mentioned case for material elements connected to at least two sides. This check uses a list of internal element numbers 3,4,5,8,10,11,13,14 in Figure 2.2.3. These elements essentially make up the inner diamond of the superelement. The material list array is used from the island finder and is searched to determine if the material configuration contains an internal element number. If it does the internal element is searched on two of the three sides towards the superelement edge for material elements. Depending on the material configuration of these two elements they could produce one node on the edge. If the connected element positioned (not an internal element) along the superelement edge is material, then a single node on the edge will not result. If the other connected element that is an internal element is a material element then there is an extra condition, which will be required. This extra condition is that the connected intemal element must have a connected material element that is positioned along the edge, which will prevent a point from occurring. As an example and in referring to Figure 2.2.3, if element 8 is material then the first part of the check is to see if elements 14 or 7 are material. If element 7 is material then there is no chance of an edge node or point occurring. 32 .’ I” ‘.‘u- 2. 4 1“; ' .- I "3 - o On the other hand if element 14 was the only material element then element 15 would also have to be material in order to prevent a point from occurring. If the superelement doesn’t contain any points or single node edges then it retains the assigned number of 1. It is then passed on as a “good” configuration, useable for the design domain. Othenlvise, it is assigned a 0 and is ignored. The third check is done for the four special cases of “one-edge” superelements. This check was only done if the superelement didn't have at least two connected sides. Due to this condition already existing to eliminate one-sided superelements, a method was required to bypass this restriction. To achieve this, the binary forms that describe the materiaVvoid configurations for all four cases were converted to integers. When these particular cases are reached, they fail the first check for connected to at least two sides; therefore a special check for their configuration numbers was added. Those four configurations would be allowed to pass. If the superelement configuration passes, then the configuration number is indexed. The index is the “good superelements configuration number”, which ranges from 0-1340, and will be used for reference in the finite element and genetic algorithm programs. This configuration number, and a 1, which identifies it as a “good” configuration is written to a file; if the configuration is poor, then a 0, which identifies it as a “poor" configuration is written to this same file. This file is used to determine which superelement configurations are “good” or “poor" over the entire range of 1-65,536. If the superelement configuration is good, then the corresponding “good superelement configuration number" (range of 0-1340) can 33 be referenced. The binary form of the good superelement configurations is written to another file that is referenced for converting the good configuration numbers to the corresponding binary form. The other edge check is done only if there is more than one island of material. This check is to determine if the configuration only contains a combination of edge material elements. The list of internal elements is used to search the material list from the island finder routine. If any of the internal element numbers are found in the material list, then the configuration doesn’t pass. If none of the internal elements are found in the material list, then the superelement passes. As each superelement configuration is checked and worthiness is evaluated, the good configurations or the configurations that pass the previously specified conditions are renumbered in the range of 0 -1340. A number can now refer to each “good” superelement configuration, which is required for the finite element calculation as well as the genetic algorithm as will be explained later. The numbering of the good superelement configurations in this way allows for easy reference of the binary form of the superelement configuration required for the calculation of its stiffness matrix. The FEM calculation is accomplished by using the commercial software package, MARC. MARC was utilized mainly for its ability to call a subroutine USELM that allows for a user specified stiffness matrix. When MARC is solving for a particular domain, the USELM subroutine will first read an external file that contains a list of the superelement configurations that 34 are to be used in the domain. This provides an exact representation of the domain so that the stiffness matrices can be calculated accordingly. 35 Chapter 3 SUPERELEMENT STIFFNESS MATRIX CALCULATIONS 3.1 Superelement Stiffness Matrix The material properties for both void and material are given below in Table 3.1.1. The material used is a standard aluminum with the material Table 3.1.1. MateriaWoid properties used in the stiffness matrix calculation CompositionllYoung’s Modulus (Pa) Poisson’s Ratio Density (kgmfil Aluminumjl 7.20x10‘° 0.33 2810 Void || 1000 0 0 | properties as given. The void was given a Young’s Modulus of 1000 Pa to prevent a singular domain global stiffness matrix from occurring. This value is indicated to be correct from Chapman et al. [6], where a Young’s modulus of at most 10'5 times that of the material used is shown to behave essentially as a void. The void was given a Poisson’s ratio of zero in order to prevent any influence on the material elements, so that it essentially behaves as void. The calculation of the superelement stiffness matrix is fairly straightforward. The stiffness matrices for each of the 16 individual plane stress elements are calculated using Equations (1) through (3) as shown, given by Logan [23]. The 16 elemental stiffness matrices were then assembled into the superelements global stiffness matrix, resulting in a 26x26. As can be seen from equation (1) the [B] matrix only requires calculations for the differences of the x and y coordinate values of each node location of each 36 lBl=2iAozL 01. 01.. (1) [fltoflzofiso Afitkflzkfls where 761.23 = Y2.” " )’3.1.2 11.2.: = x,“ ‘szJ E l v 0 (2) [D]=— v 1 0 H; 0 0 1;" 2 [Kl=tAlB]’[DIBl <3) respective element. Due to the fact that the cantilever beam domain is divided uniformly, the difference calculations for the B’s and X’s for each respective element will be the same values regardless of the position of the superelement. This allows for the ability to use one set of coordinates, where the superelement can be applied anywhere in a uniformly spaced domain. In other words, a calculated stiffness matrix can be applied in the domain independent of the exact global nodal coordinates. Now that the 26x26 global stiffness matrix has been assembled, it may be condensed to conceal the 5 internal nodes that are not required. As shown on the next page in Figure 3.1.1, the superelement will be converted from the 13-node form to the 8-node form after the condensing, where 10 DOF have been concealed. The superelement will now essentially be similar to an 8-node quad as far as element shape, but will have very different properties. 37 .e ' . vi.- ‘ U _. hr" 0 1'1:- I I '0\’ ‘I VII (n 11 12 13 6 Figure 3.1.1. Nodal form of superelement before and after condensing out the internal 5 nodes from the stiffness matrix. To conceal or condense out nodes from the stiffness matrix, it is required that the specified displacements be solved analytically and then substituted back into the stiffness matrix. Each index in the stiffness matrix is now changed to include a relation to each displacement condensed out of the stiffness matrix. This is accomplished by Equation (4), as given by Reddy [33]. The index 13,]. is where (4) i at c j ¢ c the new value of the specified index. The value of C is the location of the row and column of the displacement to be condensed out. Every index i and] are evaluated except for the Cu, row and column. In other words, every index except for those in the Cu, row and column is modified, since this is the row and column to be condensed out of the matrix. After each index has been calculated, the Cm row and column now may be discarded; this is accomplished by shifting up all the rows below, and shifting to the left all the columns on the right. This method is 38 repeated 10 times for the 5 nodes, where there are 2 DOF for each node, reducing the global superelement stiffness matrix to the final size of 16x16. The connectivity of the superelement requires a specific order, due to the assembly of the 16 triangle elements. The original connectivity for the 16, 3-node plane stress triangle elements is utilized for assembly of the superelement’s stiffness matrix. Once assembled and due to the linear form of the stiffness matrix, the equations for each successive node is arranged in an ascending order. The first node (1) is located at the first row of the stiffness matrix and the last node (13) is located at the last row of the stiffness matrix. This requires that the connectivity order of the superelement also be of an ascending order for applying the superelement’s stiffness matrix. The resulting connectivity order is shown on the right in Figure 3.1.1. 39 . r. ‘ -v;‘.“\.(v’ . ?'.= 3.2 Application of the Superelement Stiffness Matrices An interface is now required so that the superelement stiffness matrices can be used within a finite element program. The finite element program MARC was used mainly for its ability to call a subroutine USELM that would allow the user to specify an element’s stiffness matrix. The main obstacle was the retrieval of the stiffness matrices into the subroutine. The first thought was to store all the stiffness matrices in an external file and read them from this file, as they were needed. This would eliminate any extra calculation time of the stiffness matrices during the genetic algorithm run. The stiffness matrix file was generated by a separate program written in “C”, which used an extemal file prepared by the configuration checking algorithm as explained in Section 2.2. This external file contained the binary forms of the “good” superelement configurations. The algorithm would calculate all 1341 stiffness matrices using this file and write their 16x16 forms to another external file. The read time of the stiffness matrix file was required to be as fast as possible. To achieve this, the file would be required to have the form of direct access, where entries are accessed by pointers. The only problem was that the USELM subroutine required FORTRAN, as mentioned previously the stiffness matrix calculation algorithm was written in “C”. This required a FORTRAN program which read the formatted stiffness matrix file from the “C” program and convert it to a FORTRAN direct access file. It was found that direct access was essential to provide reasonable calculation times. 40 e x {.5 ... . 1 .‘1 A Sun Ultra-SPARC UNIX station was used in the calculation. It was found that the read time of the external file was so high that the solution times of the domain using superelements was similar to that when just using triangle elements-thus no time advantage. The plot shown in Figure 3.2.1 provides the CPU Calculation Time vs. Number Elements/Superelements Reading Stiffness Matrix from External File 3 a. .9. +Trlange Elements é +Stperalements :3 at o Elements/Swordsman Figure 3.2.1. Plot of calculation time in CPU seconds versus number of elements/superelements for reading stiffness matrix from file. comparison. The vertical axis denotes the calculation time in CPU seconds, and the horizontal axis displays the number of triangle elements with the corresponding number of superelements. There are instances where the superelement domain calculation time exceeds that Of the full triangle element domain. Instead, it was found that the solution times were faster by eliminating the need for reading and just generating the superelement stiffness matrices as they were needed. The finite element calculation timesavings using superelements can be seen in Figure 3.2.2. The calculations were also run on a Sun Ultra - 41 CPU Calculation Time vs. number Elements/Superelements Calculating Stiffness Matrix as Required 450 400 (r ‘g‘ 350 ~- 3 3000 g 250 .. +Trtangle Elements 8 200i +Stperelements i: a a O e‘ was swasfig; was fiffig‘g‘ Elements I Smerelemente Figure 3.2.2. Plot comparing calculation time in CPU seconds versus number of elements/superelements for calculating stiffness matrix. SPARC UNIX station. It should be noted that the calculation times given include the total time for MARC to complete the entire run and not just the time for the matrix solution. The horizontal axis contains the number of triangle elements along with the corresponding number of superelements and the vertical axis contains the calculation time in CPU seconds. As can be seen in Figure 3.2.2, there is a small advantage at the lesser number of elements but the greatest advantage occurs at the larger number of elements. The calculations using superelements resulted in at least half the time as compared to using triangle elements. A brief description will now be given to explain how the superelement stiffness matrices were obtained by the USELM subroutine using the method mentioned previously. The flowchart shown in Figure 3.2.3 provides a summary 42 MARC calls , USELM Road SE config. / Binary form ref. from tray in memory 26x20 stiffness matrix calculated Stiffness marix condensed to 16x 16 L Stiffness matrix reamed to MRO |__ Figure 3.2.3. Flowchart summarizing the steps in calculating the stiffness matrix in the USELM subroutine of the overall calculations that are done in the USELM subroutine. It should also be noted that the USELM subroutine is called once for every element (superelement) in the domain; i.e., for 8 elements, USELM is called 8 times. The first item required by MARC is an input file that describes the cantilever model. The input file provides information about the type and number of elements, as well as their connectivity. The loads and constraints are also supplied to the input file. For the Domain Refinement Approach three different input files were required due to the various domains of superelement resolution. The Superelement Hierarchy Approach only required one input file, which both cases will be explained later in Chapter 4. 43 Once MARC is ready for the stiffness matrices to be entered it will call the USELM subroutine as shown at the top of Figure 3.2.3. The USELM will next read an external file that contains the superelement configuration numbers ranging from 0 - 1340. This external file read was unavoidable but does not affect calculation time dramatically. This is the same file that was mentioned previously in Section 2.2 that contains the “good” configuration numbers. The configuration number will be used to reference the binary form of the superelement representing its materiaVvoid configuration, which was explained previously in Section 2.2. The USELM subroutine contains all 1341 binary forms of the superelement material/void configurations that are placed into an array upon execution. This storing of the binary forms allows for the elimination of reading an external file for the stiffness matrix, resulting in a quicker calculation time. The binary form is then used to determine which triangle elements within the superelement are either material or void for their calculation, and for assembly. The calculation of the stiffness matrix is quick, where each element has a 6x6 stiffness matrix yielding the assembled superelement stiffness matrix as a 26x26. Finally, the superelement stiffness matrix is condensed to its useable form as a 16x16. This resulting superelement stiffness matrix is then transferred to MARC, where it can be assembled into the domain’s global stiffness matrix. This entire process is then repeated for the next element (or superelement). MARC also produces an output file that contains pertinent information for retrieval. The main component of interest is the displacement for any particular 44 node. This value can easily be obtained using code that will look through the output file and find the resulting displacement value. 45 Chapter 4 GENETIC ALGORITHM 4.1 Introduction and Background The genetic algorithm is analogous to natural genetics in that it combines traits of two parent chromosomes to produce a child that contains traits-whether good or bad-of both parents. If the child combination of traits produces a fitness as good or better than the fitness of the rest of the population, than it will tend to survive combining its traits with another to produce its own offspring. A child may also receive one or more imperfectly copied genes from its parents, which may result in worse, or occasionally better performance for the organism. This is known as a mutant or a mutation of the gene on the chromosome. If the defective chromosome provides an advantage to the organism over the rest of the population, it will likely survive to produce offspring with this same particular advantage. This overall adaptation process is continually repeated until the chromosome is refined so that the organism becomes well adapted to the environment within which it lives. In this study the chromosome will represent a design specifying the superelements of the domain. The chromosome consists of the same number of fields (loci), as there are superelements within the domain. Each field represents its respective superelement - the first field represents the first superelement, the 46 second field represents the second superelement, and so on. An example of a 2x2 domain of superelements is shown Figure 4.1.1. Figure 4.1.1. Example of a 2x2 superelement domain showing the numbering scheme for the superelements A possible chromosome of the domain shown in Figure 4.1.1 would be shown as: 5 1340 15 1085 Each field or allele represents a particular materiaVvoid configuration number for its respective superelement. As can be seen in Figure 4.1.1 the superelements are numbered in an ascending rowwise order, and in this case the chromosome contains four fields or alleles. Each field of the chromosome has a range of 0 - 1340, which represents one of the 1341 good superelement materiaVvoid configurations. (It should be noted that a conversion is required from the range of 0 - 1340 to the range of 1 - 1341 for use in the MARC USELM subroutine, due to the requirement that the subroutine be written in FORTRAN, where as GALOPPS is written in C.) In order for the design to improve, the parent designs (chromosomes) will need to combine their traits via a process known as crossover, to produce two child designs (chromosomes). The parents are selected using a type of selection 47 algorithm, which is either random or based upon their fitness’, where an individual’s fitness is an evaluation of the design based upon its performance (relative to the design goals and constraints). After the parents are selected, a cutting point is randomly selected and the chromosomes are recombined to produce a child. To illustrate, the two following 12 632 421 1025 . . . — '— —; the out line, Wthh IS the 564 9 1336 987 parents have been selected vertical line directly after the first allele is randomly selected. The alleles on the right side of this line, which are underlined, will be exchanged between the two , , 12 0 1336 987 parent chromosomes. The two resulting children are " “‘— — ; 564 632 421 1025 where the out line is left for reference. To illustrate mutation, a possible chromosome that corresponds to Figure 4.1.1 is given as 21 1125 _5_6_4 5, where the underlined allele has been randomly chosen for mutation. A new value is randomly chosen in the range from 0 - 1340 and placed in this allele. If the new randomly chosen value were 99, for example, then the chromosome becomes 21 1125 2 5 and is introduced into the population for evaluation of its fitness. The better its fitness, the more likely that it will survive to produce offspring. Due to the two-dimensional nature of the design domain that the chromosome string represents in this case, special crossover and mutation operations were required. It was found that the standard one-point, two-point crossovers and uniform random mutation do not provide adequate adaptations to obtain good search of the design space within a practical amount of time. Instead, 48 a two-dimensional crossover was utilized, which provided crossover with contiguous 2-D subregions of the design domain instead of contiguous one- dimensional substrings of the chromosome. A two-dimensional mutation provided mutations that altered the materiaVvoid states in randomly chosen contiguous areas of one or more superelements, instead of acting only on individual triangle elements. An explanation of the operation of the two-dimensional crossover and mutation follows. 49 4.2 Two-Dimensional Crossover A two-dimensional crossover allows for the exchange of alleles among an increased array of more problem-appropriate crossover boundaries, as compared to the conventional two-point crossover. A study conducted by Kane and Schoenauer [21] compares outcomes of various crossover schemes, finding that 2-D crossover provides better exchange of alleles for chromosomes of a 2-D representation. The chromosome is transformed into a two-dimensional array in which the indices mimic the locations of each superelement within the domain. The line of crossover or cut line is then run between two randomly selected indices that lie on the edge of the array. After the out line has been established, one of the two sides of the cut line is randomly selected and all the alleles from this side are exchanged with the mating chromosome. This will ultimately provide a more problem-appropriate exchange of alleles between the two chromosomes, since it tends to preserve 2-D regions of co-adapted alleles more faithfully than conventional two-point crossover. To illustrate the two-dimensional crossover, consider a chromosome given as follows: 124 521 8 695 O 36 1025 87 314 525 73 12 1340 51 696 1258, which represents a 4x4 domain of 16. This chromosome is then reconfigured into a two-dimensional array as follows; 50 124 521 8 695 O 36 1025 87 314 525 73 12 1340 51 696 1258 which expresses to the locations of the superelements in the domain. The cut line for the crossover will run from any one (“first”) index on an outer edge to an index on another (different) outer edge. The first indices are organized in groups to provide equal odds of being selected as well as controlling the out line. The edge indices are arranged as shown below in Figure 4.2.1. The edge indices of the array were grouped together into eight groups, which are 0 1 2 I124 H521 Sj I 695] 7 0 36 1025 87 3 314 525 73 12 “340” 51 696 ”1258] B 5 4 Figure 4.2.1 . Arrangement of outer edge indexes for equal odds of selection I boxed and numbered as represented in Figure 4.2.1. The “comer" groups 0,2,4, and 6 contain, for any size domain, one entry each. The groups 1,3,5, and 7 have to contain one or more entries for the two-dimensional crossover to work properly. The first group is selected uniform randomly from the numbers 0 through 7. After the first selection, a rule comes into effect that prevents certain situations from occurring. The rule is that the other randomly selected group cannot lie in the same row or column as the first selected group. This prevents the entire chromosome from being exchanged with the other, which would effectively just 51 cause the two chromosomes to be swapped with no exchange of alleles. As an example of the process, if the first randomly selected group were group 0, then the random choices for the second group are narrowed down to 3,4, and 5. If the first randomly selected group was 1. then the random choices for the second group are narrowed down to 3.4.5.6, and 7. After the groups have been determined, then if applicable, the indices within the group are randomly selected. This only occurs for the cases of groups 1,3,5, and 7. Once the two-endpoint indices are determined, the indices between these points must be calculated to define the cut line. This is done by formulating a linear equation using the two endpoint indices. This equation provides the column/row given the next row/column from the starting point index. The linear equation was formulated for both rowwise and columnwise calculation, which means that if given the row, the column was calculated, or if given the column, the row was calculated. This formulation was unavoidable due to the many possible placements of the out line. The out line can run on any angle as well as horizontal and vertical. An example of a possible out line is shown below in Figure 4.2.2. In this example, the rows are calculated by going 124 521 8 695 01025 87 525 73 12 1340 51 696 1258 Figure 4.2.2. Example of cut line joining two randomly chosen endpoints along columnwise. 52 After the out line has been established, one of the two sides is randomly selected for exchange with the mating chromosome. To illustrate, refer to Figure 4.2.2, all the alleles in the cut line and on the left or right side will be exchanged with the corresponding alleles of the other parent. Once the alleles are exchanged between the parents, the chromosomes are rearranged back into the original long string form and returned to the genetic algorithm for evaluation. 53 4.3 Two-Dimensional Mutation The random modification of alleles within the chromosome does not provide an adequate and systematic mutation for a two-dimensional domain. Random allele mutation is not optimal because it does not take into account the two-dimensional domain that is used in this case. To provide a more beneficial mutation a two-dimensional subregion of adjacent loci will be altered in a specific random manner. This is accomplished at the triangle element level of the domain by first randomly selecting one triangle element. There is no dependency what so ever on the location of the triangle element within the superelement for the random selection, the triangle element is just randomly selected from the domain. The randomly selected triangle element and a predetermined pattern of its neighboring elements are then randomly switched from their current materiaVvoid conditions in the manner described below. This essentially provides a material rearrangement within a small area, which can improve or deteriorate the design. A detailed explanation of this overall process is now discussed. Once a chromosome has been targeted for mutation, it is first converted from its superelement configuration form where each allele ranges from 0-1340, to its binary (materiaVvoid) form, corresponding to a decimal integer in [0-65.536]. Now that the chromosome is in its binary form, a bit or element is randomly selected. Next a series of operations is executed to modify not only the selected element, but also the predetermined pattern of its neighboring elements. The patterns of the selected neighbor elements are dependent upon the orientation of 54 the randomly selected element. There are four element orientations and four corresponding patterns. The four patterns are shown in separate 2x2 domains in Figure 4.3.1 . Typet Type 2 \\ x”, \\ , \ / \\ /’ \\ ’I/ \\ \\ / \\ ,I’” )V y \ I 2'“, / /\< t , x/ \ , \\ /\ / \‘\ / \ x \ ”/’\\ \\ / \\ // \\ /,/ “\>(\\ //x\\ ,//K\ \‘\\\ ,/ ‘\\/ ‘\ // /’ \\ / \ \ ’ \(u’ 2\ x x < 2x , >< / \ / . / / . / . / \ , \ Um3 Wm4 \( \ ’ \ / \ /. .\ /. .\ ,, / \ , \\ /\\\ “\ / \./ \/ \. / \\ / >< \\\/ \‘ /\\\ /&\ //’ I \\\ ll/ Figure 4.3.1 . Neighbor selection patterns for each element type The black area represents the randomly selected element and the shaded areas are the neighbor pattern. The differences in the patterns. which are dependent upon element orientation, were selected so that each orientation would cause a change in the domain. If the same pattern was used it would be rotated about, causing similar changes. As can be seen in the cases for Type 1 and Type 2 in figure 4.3.1, there is not much difference between the patterns other then the location of two elements. The patterns were determined by educated guesses on how areas of elements should be affected by moving material around in an area. The sizes of 55 (of-‘0 N w h . “A ' . ' -“ . . . Nxh.-\.h~ fi-fi these patterns could be larger, but then too much change may occur at once, possibly misdirecting the search. In order to assign a neighbor pattern for the mutation the orientation of the randomly chosen element is required, which is one of the four possible. This is accomplished similarly to the element type search used in the island finder. The element numbers in the domain of each specific orientation is calculated in sequence, to determine if it matches the number of the randomly selected element. Once it matches, an orientation number (0-3) is assigned and the neighbor pattern can be determined. The surrounding element numbers in the neighbor pattern are calculated and, along with the randomly chosen element. are stored in an array. If the randomly selected element is located near an edge or comer. the entire neighbor pattern as shown is not present. The element values for the missing entries are not calculated and left as zero. A binary coin toss determines the new material condition of the selected elements in the array. Each element is determined separately and the outcome from the coin toss is placed back into the corresponding element’s index in the binary form of the domain. Due to the fact that this bit flipping occurs at the bit level. bad superelement configurations can occur. A check is required so that bad configurations are not allowed to pass. The binary form of the domain is converted to integer form in 16-bit intervals. The values calculated from the 16-bit intervals are then looked up in an array that tells whether a configuration is good or bad. and also provides the configuration number if it is a good configuration. If all the new configuration numbers are good, 56 the number of material islands within the domain is counted. If the domain contains fewer than six islands, the mutant chromosome is allowed into the population for evaluation. Otherwise, the coin toss process is repeated and the material conditions of the selected elements are then determined. This process is repeated up to 25 times for the same randomly selected element. This is done in order to provide enough tries at finding a good material shift in that particular region. If nothing is found for the area of the randomly selected element. then another element is randomly selected, allowing up to 50 tries of randomly selected elements. If nothing is found after 50 different elements, then the chromosome is returned to the population unchanged. 57 4.4 Fitness Equation The fitness equation provides a value that is a measure of the design’s performance. Therefore, the fitness equation is the key that directs the search of the genetic algorithm toward the optimal design. The design’s performance is evaluated by penalizing several parameters of the design, such that designs that are going astray will accrue a small fitness value. A design that is favorable will be assigned a large fitness value. The larger the value of the fitness, the more fit or desirable the design. The fitness equation involves penalties for three primary arguments including mass (which is to be minimized), displacement (which is to be kept below a maximum limit). and the number of material islands (where one island is desired). The fitness equation is given in Equations (5) through (9). The mass is Nmass = mass (5) base] Ndisp - .dzsp (6) dzsp + k Nnumisle = M (7) numisle + k1 Ndispl = .dzsp (8) dzsp + k2 Fitness = C0 — Aleass —- Blly’disp — Banumisle — B3Ndisp1 (9) normalized linearly with a base mass. the displacement penalty function is normalized hyperbolically and can be modified by k, and the material islands penalty is normalized hyperbolically which can be modified by the constant k1. 58 There is also an extra term that works to fine tune the design, labeled Ndisp1. it helps to decrease the mass and displacement further than the Nmass and Ndisp terms alone can accomplish. The Ndisp1 penalty function is normalized hyperbolically and can also be modified by the constant term kg. The variables in the penalty functions such as mass represent the design’s mass, disp represents the design’s displacement, and numisle represents the design’s number of material islands. Since there is no base reference in the penalty functions for the displacement, number of islands, or the fine-tuning term. the values for k. R1. and k2 had to be chosen so that the penalty gradient was acceptable in the vicinity of the respective base values. After the base values of displacement and number of material islands have been achieved in the search there is no need to further penalize the design for this success. The penalty curves do not go to zero prior to the base value, this is due to the function itself not going to zero in these instances. Therefore the coefficients require the appropriate modification. The coefficients Co, A1. and B3 are the only constants that remain unchanged throughout the run. The constants B1 and B2 become zero when their respective values are less than or equal to their respective base values. The constants Co. A1, B1, 82. 83, k, k1, and k2 are predetermined by examining penalty curve plots and behavior of preliminary runs of the genetic algorithm. A table of the coefficients and the base values is given in Table 4.4.1 . The base values were determined by creating a base design and calculating the mass and the displacement. A picture of the base design is shown 59 fl’i-t‘.“ Table 4.4.1. Coefficients and base values used in the fitness equation .357 mm Mass .071655 Figure 4.4.1. Base design used for determining base mass and displacement in an 8x8 domain in Figure 4.4.1. The lightly shaded regions represent the material elements and the white regions represent void. The placement of material for this design is cognizant of the shape for the desired optimal design. This particular design was to be used for comparison with the results of the genetic algorithm, and for initial setting of some fitness “base” values, as explained above. The coefficients were chosen to provide a fairly large change in the penalty 60 value near the base values, to drive the genetic algorithm toward the optimal design. The coefficients were set such that the genetic algorithm would tend to first find one material island. This argument was penalized the greatest, ~the largest coefficient of 90 - in order that the search initially starts in the correct direction. The displacement was next reduced within range of its base value. After a design was found to satisfy theses two parameters the genetic algorithm would tend to search to reduce the mass while maintaining good values of displacement and number islands. The plots of the penalty curves are given in Figure 4.4.2. The plots show Mass Penalty Function 4° I I I I I I l l I 30 ----- : ----- — U) I l I W l I I 320 ------ ------ a ----- — 'o . I N I I I 10 ----- + ————— -I ----- -l ————— d I I I o 1 l I 0 0.05 0.1 0.15 0.2 mass (kg) Materid Islands Penalty Function 90 ; . r . I I 3380—- --r----' ------------- a g I l c I I .Z l l g 70 ----- :- — — - -: -------------- ~ I l 60 l I I 1 0 20 40 60 80 100 materlal islands Displacement Penalty Function 53 I I I I l I l l I as ------ ' ----« a. l I 9’- : . 264 ------ -. —————————— — o l I h 2 I 62 ------ + ----- + ---------- ~ I I l l l l l I I 60 I l l 2 4 6 8 10 disp(m) x104 Fine-Tuning Penalty chtlon 4 1 . . . 1 ' I l l -35 —————— ' ————— 4 ----- — O. l I I .2., I I I U l i I .Z l l I m a---- ------ : ----- ~ I l l I t I 2.5 I l 1 2 4 6 8 10 disp(m) x104 Figure 4.4.2. Penalty curves used to determine coefficients in fitness equation the penalty function multiplied by its respective coefficient value versus its respective fitness argument. As can be seen in Figure 4.4.2, the mass penalty is 61 linear, with a minimum value of zero mass and a maximum value corresponding to the entire domain consisting of material. The displacement penalty curve is shown in the region of interest near the base displacement value. As can be seen there is a reasonable amount of change in the penalty value between 3.567E-4 and 4E-4. This provides a reasonable amount of difference between the various designs to drive the genetic algorithm to find displacements below the base displacement value. If this area were fairly flat, then there would not be enough pressure to drive the genetic algorithm towards a better design. This reasoning was carried over to the remaining penalty curves as well. The material island’s penalty curve is fairly steep. There was a very large penalty given if the number of material islands exceeded 1, which drives the genetic algorithm to reduce the islands initially. The final penalty curve is that of the fine-tuning term. It is shown in the area of the base displacement value. It adds a little extra penalty, which is dependent upon the displacement. The importance of this term will become more apparent when the displacement and island base values have been reached. The coefficients to these two terms become zero leaving the mass and the fine-tuning term remaining. With this in mind it can be seen why the extra fine-tuning term is beneficial. After the base value of displacement is achieved, there is no longer a penalty for the displacement and no indication if it results to be less than the base displacement, hence no drive to reduce the displacement. The extra term takes 62 this into account, which provides the extra penalty to reduce displacement. The fine-tuning term also aids in reducing the mass. This is due to these two final terms providing the balance of penalty between each other. 63 4.5 Domain Refinement Approach Migration involves the sharing of individuals (designs) between populations. This provides useful information (“building blocks”) found in one population to other populations. This in turn allows an entire set of populations to search more effectively. The injection island method takes advantage of migration but in a particular way. Within the entire set of populations used in a problem, a subset of the populations has a small search space, thus allowing a rough design to be found and to direct further search. Individuals found in this population set are shared with another specific population set that uses a somewhat larger search space. after the individuals are mapped into the new representation. thus aiding in directing the search further. Individuals found from this population set are then shared with populations with a still larger search space. thus directing their search to yield the final design. In summary. a rough design is found and is refined further and further through each specific population set until the finest refinement is reached. The injection island method ultimately provides a reduction in search space and decreases the genetic algorithm run time. The approach used in this case for the injection island method involves using an increasing element (superelement) resolution in three domains. The first level or domain will consist of a 2x2 domain of superelements, the second level will consist of a 4x4 domain of superelements and the final level will consist of. an 8x8 domain of superelements. A schematic of the migration mapping which 64 o It: shows where the individuals are shared along with the populations assigned to the levels is shown in Figure 4.5.1. This migration mapping will allow an Figure 4.5.1. Migration mapping of Domain Refinement Approach individual to be continually improved as well as improving upon the other populations as it travels through all the populations. In Figure 4.5.1 the circles represent the populations and the number within the circle is the population number. The first level consists of populations 0 - 2, the second level consists of populations 3 - 5, and the third level consists of populations 6 - 8. The arrows represent the direction in which the individuals are shared. At each migration event (every Kth generation of the genetic algorithm), the best Individual of each population is migrated within the level whereas individuals migrarting between levels consist of the best individual plus two random individuals. Individuals migrating between levels cannot be used directly. They first require a transformation or mapping due to the different element resolution of the domains. This mapping provides an exact replica of the individual as represented in the courser domain. remapped to the finer resolution domain. The mapping is 65 directional, where only a lower resolution domain can be mapped to a higher resolution domain and not the opposite. The mapping takes one triangle element and maps it to four corresponding triangle elements in the finer domain resolution. This type of mapping is similar to the method used by Chapman et al. [2][3]. An example is shown below in Figure 4.5.2. As can be seen one block or four triangle elements are now Figure 4.5.2. Example of mapping an element to the next domain level contained within one superelement after mapping. This requires that the finer resolution domain contain twice as many superelements in both rows and columns as the domain being mapped. This is the reason for the size of the domains that were selected. Since the first domain is a 2x2, the next domain size is required to be a 4x4, which is twice the size. This is repeated to the last domain so that the 4x4 can be mapped correctly to an 8x8. Thus any individual can be mapped exactly to a corresponding individual in a finer-resolution domain. As can be seen from Figure 4.5.1 there is a migration of individuals from population 2 to population 6. Since the initial re-mapping function was constructed to map only to the next immediate domain. this requires a special operation for 66 mapping. in which the chromosome is mapped twice. The design is mapped from the 2x2 domain to the 4x4 and then mapped directly to the 8x8. This migration was included mainly to keep the finest resolution designs from falling behind the preceding two levels with respect to fitness. This allows the finest level’s populations to be influenced by good individuals from level one, directing it fairly soon to refine these designs, allowing it to achieve final result quicker. Once the individual has been mapped, it must be reevaluated. This is due to the error associated with the finite element method for calculating displacements. The finer the resolution of elements, the less the error in the calculation but in this case, since a specified number of elements were used the error could not be avoided between domains. This error due to the FEM calculation is small but due to the sensitivity of the penalty functions. the fitness value was greatly affected by changes in the displacement value of a lower resolution domain with respect to the base value of the finest resolution domain. In order to alleviate this error individual base displacement values for each level of element resolution were calculated for the base design. These individual base values were used to evaluate the fitness of the designs at its respective level. The values used for level 1 through level 3 are shown below in Table 4.5.1. Table 4.5.1. Base displacement values for each level of superelement resolution 1 Base Displacement Level 1 0.2130 | 2 | 0.3085 | | 3 | 0.3567 | 67 The value of the level 3 displacement is reinstated for comparison which was given in Section 1.1 as the displacement constraint of the optimization objective. This maintained each levels fitness calculations similar to each other so that a design from a lower resolution domain was not underrepresented in a domain of finer resolution. 68 4.6 Superelement Hierarchy Approach This approach is different than the method previously covered in Section 4.5. It utilizes one domain of superelement resolution that can be of any size. Instead of utilizing several domains of various superelement resolutions, the number of material elements in each superelement Is varied providing levels of hierarchy. This still provides a rough design that is then gradually refined through several successive levels. In this migration approach four levels of superelement materiaVvoid hierarchy were required. An example of a superelement from each level of hierarchy is shown below in Figure 4.6.1. The superelement of the first Level 1 Level 2 . . . . . . . , . . . , 1' 4' . . . . . . . . . . . . . / . . t . . Level 3 Level 4 Figure 4.6.1. Example superelements from'each 0f the four superelement hierarchy levels level either contained all material elements or all void elements. The second level was refined down to the four comer blocks, each of which contains four triangle 69 elements, which are either all material or all void. The third level splits the blocks of the second level into triangles with hypotenuses running from lower left to upper right, which contains two triangle elements. Then the final level of hierarchy is the full sixteen triangle elements within the superelement. The migration population mapping utilized sixteen populations in a 4x4 representation. A schematic of the population is shown below in Figure 4.6.2. As Ist Level - 1 bit ®®® I l 2nd Level - 4 bits (awe 3rd Level - 8 bits @e o—>® —)® 4th Level - 16 hits @a 0665) 90 Figure 4.6.2. Migration mapping for Superelement Hierarchy Approach can be seen from Figure 4.6.2, there are four populations per level of hierarchy. The best design from a population is shared with its neighbor, as shown by the directional arrows. When a design or individual is passed within its own level, there is no mapping required. When an individual is passed from one level to the next, a mapping is required so that the superelement material configuration is represented identically in the next level. The migrations within the level share only the best individual, where as individuals shared between levels consist of the best and two randomly selected individuals. 70 The migration mapping between levels is accomplished by determining all possible superelement materiaVvoid configurations of the binary forms from each resolution level. As an example, the first level contains only 2(2‘) possible configurations - either a 0 or 1. The next level. with four blocks, has 24 or 16 total possible configurations. The third level has eight triangles, therefore a total of 28 or 256 total configurations. Likewise, the finest level has 216 or 65,536 total configurations. Therefore, each level of element hierarchy is treated separately, and each level has its own family of possible good and bad configurations. There will be some materiaVvoid configurations that are not desired and will need to be eliminated. This elimination is accomplished by using the superelement configuration check algorithm as described previously in Section 2.2. The bit representation for each level will be different in length due to the number of materiaVvoid entities within each superelement level. Each materiaVvoid entity is described by one bit. The first level contains only one bit describing the entire domain. the second level contains four bits - one for each block, and the third level contains eight bits - one for each half block. These shorter bit lengths are simply converted to a sixteen-bit length and run through the same superelement configuration-checking algorithm as the full resolution case. The number of good configurations that resulted for the first level was 2, for the second level resulted as 14, and for the third level was 46. Given a set of good superelement ccnfiguration numbers for each level. some sort of mapping to each higher level was required. An array was constructed that contained a list of all the equivalent superelement configurations 71 for mapping from one level to the next. The equivalent superelements from level one were renumbered to the corresponding configuration numbers from level two. Level two configuration numbers were renumbered to the equivalent configurations from level three and the same was done to level three configurations from level four numbers. This provided an easy and quick reference for the mapping of configuration numbers from one level to the next. A consequence of using this particular migration approach is the inconsistencies among hierarchy levels. Each level had to be treated individually for certain cases due to the shapes of material entities and numbering scheme utilized for each level. One case. which will be explained in the next section is that of the two-dimensional mutation. The same principle was applied as explained previously in Section 4.3, where material and void are shifted within certain areas but each level was treated individually due these inconsistencies. 72 4.7 Two-Dimensional Mutation for Superelement Hierarchy Approach This type of mutation does not differ in principle and process from the mutation described previously in Section 4.3. The chief difference is that each level of hierarchy had to be treated individually due to the shape of the material entities within the superelement. The same process was used, in which an allele was randomly chosen, the neighbors where then determined, configurations converted to bit form, the bits were randomly flipped, then the new configurations were checked for acceptability and islands counted. A brief explanation will be given for the neighbor pattern for the first three levels; the fourth level was described previously in Section 4.3. The first level of hierarchy utilized the entire superelement as either material or void. This provided very coarse changes to the domain at this level. The neighbor pattern used in this level is shown in Figure 4.7.1. Figure 4.7.1 . Neighbor pattern for mutation of the first level 73 The neighbor pattern Is shown in a 4x4 domain from which it can be seen that it covers a fairly large area. The dark block is the randomly selected allele and the surrounding shaded areas are the affected neighboring superelements. The second level utilized the four blocks within each superelement as either material or void. This split the superelement into quarters, allowing for a little more refinement of the domain. The neighbor pattern is shown below in Figure 4.7.2. The neighbor pattem is shown in a 2x2 domain, and also covers a Figure 4.7.2. Neighbor pattern for mutation of the second level fairly large area. The dark block is the randomly chosen allele, and the surrounding shaded area is the affected neighbors. The third level refined the hierarchy of the second level another step by halving the blocks. This resulted in two orientations of the triangle material entities as well as two neighbor patterns. These two orientations were selected to provide different results for each of the two triangle orientations. Othewvise. the same neighbor pattern would have been used for both orientations not allowing for differing changes in the domain. 74 The random selection of the triangle element was not dependent on the location within the superelement, the element was selected randomly from the domain. After an element is selected the orientation of the triangle entity was first required so that the correct neighbor pattem would be used. This was done in a similar fashion to the finest 16-superelement case where the entire domain was searched systematically for the first type, then the second. When the triangle entity number was matched with that from the domain search it was assigned a number to describe its orientation. The neighbor pattern is shown in Figure 4.7.3 Figure 4.7.3. Neighbor patterns for mutation of the third level in a 2x2 domain. The first orientation is shown on the left and the second orientation is shown on the right as the dark triangular area. The surrounding shaded areas are the affected elements for mutation. As can be seen, the neighbor pattern differs between the two orientations. Each contains the same shape but is rotated opposite from each other. These particular neighbor patterns were selected so that material and void could be shifted in specific directions within a fairly large 75 area. This would affect the design somewhat dramatically but locally, in hopes that the mutation can provide an improved design. 76 4.8 Design Evaluation The genetic algorithm requires a value that pertains to a chromosome’s (design’s) fitness to gauge how well it performs. This can only be given by evaluating the design for specific parameters and returning to the genetic algorithm a value representative of its performance. In the fitness equation, in Section 4.4 the design is evaluated based upon the calculation of the arguments mass, displacement and number of material islands. The calculation and logical determinations of these arguments will now be explained. A design is run through a series of calculations in its evaluation. The flowchart shown in Figure 4.8.1 provides a summarized outline of the procedure. The number of material islands is counted, and then the mass is calculated. The calculation of the displacement is dependent upon the number of material islands that are in the design. Since displacement calculation is expensive, it is limited only to designs with fewer than a specified number of islands. The first and probably most important component to be obtained is the number of material islands. The chromosome requires a conversion from its integer form to its binary form of representation of the good superelement configurations. This conversion is required because the island finder algorithm requires the binary representation of the domain in order to determine the number of Islands. This algorithm works similarly to the one used for counting islands of the individual superelements explained previously in Section 2.2. The main difference is that the material list contains the material triangle elements from 77 / c.2222... / 1. Convert chrom from integer to binary I count materid islands slz Cdcdate mass <6 mal islands Write SE conflgs to external fie I RtnlMRC I Lookupcdculated dsplacementvalm —_)QE_ Set values of coefficients __~.|;_ Calculus fitness Set displacement to a vine of .6 Figure 4.8.1. Summary flowchart of the design evaluation procedure 78 at” 3‘ ;... ‘9‘. the entire domain instead of just one superelement. The materiaVvoid elements are counted and tracked by storing them in an associated array to be used in other calculations. A special property used in the island finder algorithm is that no seed elements are specified. Seed elements could be placed at locations where there must absolutely be material. such as at the load point and constrained points and a check could be done so that there is a material path between these elements. This was used in the study done by Chapman et al. [5][6], where seed elements were used at both the constrained locations and at the load location. This was thought to constrain the shape of the resulting design. This island finder algorithm allows more freedom for the genetic algorithm to find the best location of material for the constraints as well as the load. The genetic algorithm is able to determine that the absence of material in these critical areas results in a poor design; therefore, seeding is neglected. The mass is calculated next, which is a straightforward calculation. The number of material elements is known, since it was counted in the island finder routine. An individual triangle element volume is known and the aluminum’s density is known. The mass is simply the product of the number of material elements, individual triangle element volume and the aluminum’s density. The last calculation. which is the most expensive time-wise, is the displacement. This calculation is expensive because it requires the use of MARC, even though superelements are used to reduce the calculation time. Because of this expense, the displacement is only calculated for cases where the domain 79 contains no more than a specified number of islands. The limiting number of islands used in this case was 5. If this value was exceeded, then a large displacement value of 0.5m was used for the displacement and MARC was not run. For designs containing more than 5 islands, it was thought that the designs were extremely poor and would not contribute to any design improvement. It was thought that designs with the number of islands within the specified limit were more likely contribute. Shifting material around in certain areas may cause islands of material to join together, thus reducing the number of islands and possibly improving the overall design. To initiate MARC for calculating the displacements. a file must first be written that contains information about the current design. The external file written contains the chromosome, but is converted by adding one to each entry for the FORTRAN coding used by MARC. The MARC subroutine USELM first reads the external file for the element number that it currently requires; the associated superelement configuration number is returned and is used to reference its binary form within the USELM subroutine. Using this binary form. the stiffness matrix can be calculated and returned to MARC. This process is repeated for every superelement in the domain, with the USELM subroutine called for each superelement. After each superelement’s stiffness matrix has been calculated. they are assembled into the domain’s global matrix and the displacements are calculated. The calculated displacements are written to an output file from which the 80 displacement value for the node of interest may be read. This resulting displacement is stored as a variable for use in the fitness equation. Once all the values for mass, number of islands, and displacement have been determined, the coefficients used in the fitness equation can be set. The coefficients that are dependent upon the value of displacement and number of material islands are set accordingly. The design’s fitness is then ready to be evaluated using the fitness equation explained in Section 4.4. This fitness value is then returned to the genetic algorithm. 81 Chapter 5 APPROACH REPRESENTAION COMPARISON 5.1 Overview A comparison between the migration approaches was conducted to determine which provides the greatest benefit - the best design in the quickest time. Each used an 8x8 domain of superelements as the domain for the final design - that is they are solving the same problem at the same final resolution. Every other aspect was made as similar as possible, as far as the probability of crossover, probability of mutation and selection, etc., are concerned. The genetic algorithm GALOPPS. developed by Goodman [6], was used in both searches. The tables located on the next page in Table 5.1.1 and Table 5.1.2 summarize the parameters and values that were used in the genetic algorithm. The parameters in Table 5.1.1 were used in the Domain Refinement Approach and the parameters in Table 5.1.2 were used in the Superelement Hierarchy Approach. The probability of mutation was varied in the Domain Refinement Approach due to the varying sizes of the domain. It was found that a large mutation rate yielded a level’s optimal design much sooner than a small one, but too large a value would cause the search to go astray, taking longer to find the optimum. The mutation rate was not varied for the Superelement Hierarchy Approach because the domains were all the same size. Increasing the mutation 82 Table 5.1.1. GA Parameter values used in the Domain Refinement Approach Parameter Pop 0 Pop 1 Pop 2 Pop 3 Pop 4 Pop 5 Pop 6 Pop 7 Pop 8 PM” 50% 50% 50% 40% 40% 40% 40% 40% 40% (per IndIvrdual) emf?” 75% 75% 75% 75% 75% 75% 75% 75% 75% (per IndIvrdual) Tournament Size 3 3 3 3 3 3 3 3 3 Popsize 30 30 30 30 30 30 30 30 30 Alpha size 1341 1341 1341 1341 1341 1341 1341 1341 1341 Numfields 4 4 4 16 16 16 64 64 64 Gens/Cycle 3 3 3 3 3 3 3 3 3 Cycles 400 400 400 400 400 400 400 400 400 Random seeds Run 1 0.056 0.1 12 0.168 0.224 0.28 0.336 0.392 0.448 0.504 Run 2 0.9 0.376 0.00008 0.125 0.97 0.451 0.28 0.56 0.309 Run 3 0.95 0.426 0.05008 0.175 0.99 0.501 0.33 0.61 0.359 Table 5.1.2. GA parameter values used in the Superelement Hierarchy Approach Size size Numfields Random 0.025 0.0313 0.0313 0.0375 0.05 0.315 0.315 0.675 2 0.0063 0.0063 0.0125 25 88 3 0.25 0.25 0.95 0.95 0.875 0.875 0.05 rate for the low material resolution levels was found to cause it to fall far behind the others. This level would still be improving, but would not finish before the others. thus not allowing these new improvements to be shared with the other populations. 83 As can be seen from the tables above. there were three runs for each migration approach used. The main reason for this was to demonstrate that the genetic algorithm did not by chance find a suitable optimal design. (The random seeds for each population were changed for each run.) The numbers shown above in both tables were randomly selected with no specific pattern in mind. The random seed numbers provide a reference for the random selection of the initial population. It the same random seed numbers were used again the same results as the previous run would likely occur. The following two sections will describe and display the results for each migration approach separately. This will include results from all three runs for each migration approach. A comparison of the performance for each migration scheme will then be given in a separate section. 84 5.2 Domain Refinement Approach Results The search utilized the parallel search capabilities of GALOPPS. The parallelism allows multiple processors to search simultaneously but asynchronously, with each population sharing the required information with other populations. In many instances, including this one, one population is assigned to a processor. A total of nine processors were used - one population per processor. The determination for using the nine-population migration scheme was mainly due to the limited computer resources. Using nine processors. allowed for the most populations per level with three levels of domain resolution. A larger set of populations was tried, with three levels and four populations per level. This required two populations on the same processors, which yielded similar results as given below, but required much more time for the search. The first set of results will display the performance of the genetic algorithm using the domain refinement approach by showing various plots. The plots will show the change in the designs arguments such as fitness, mass, displacement, and material islands, over the course of the run. At each time, only the values for the best individual of that generation are plotted. A picture of the best resulting design of each level for the three runs is also shown. Figure 5.2.1 shows the change in fitness with time for each population of all three runs. The first run is at the top, the second run is in the middle, and the third run is on the bottom. The curves differ slightly between each run. but all end in the same vicinity, indicating that the resulting design is not found by random 85 chance. The fitness curves of the first level are shallow, whereas the curves of the higher resolutions are fairly sharp. This is due to the first level finding good design’s and migrating them to the next level, which causes the sharp increase in fitness. The first level finds its optimal solution in approximately an hour. while the higher levels required much more time to find their resulting designs. There is also a maximum fitness value that is obtainable in each level. This can be seen in Figure 5.2.1, where the first level’s best fitness is slightly less than the second level’s and the second level’s is slightly less than the third’s This is mainly due to the triangle element size, which is large at the first level and becomes smaller for the higher resolution levels. The size of these elements dictates the amount of mass per element, thus causing the limitations of fitness by preventing “fine-tuning”. This occurrence can best be seen in Figure 5.2.2. The plots show the change in mass for each level with time for all three runs. As can be seen, the mass continually decreases with time as the genetic algorithm seeks the optimal design. The curve shows that the mass starts out very large and is continually trimmed in the design until the limit is reached. This can be seen in each level, with the mass decreasing further with each level. The plots of the displacement versus time are shown in Figure 5.2.3. The displacements start out very low, due to the initially large mass values. As the mass is trimmed the displacement then increases. A good range of displacement values is reached fairly quickly, and the displacements tend to stay within this area for the rest of the run. This indicates that the genetic algorithm is 86 Level 1; Pops 0-2 I I 170 ------- I ______ . I I I 165 I —————— : ...... J I I I 160 1 0 2000 4000 190 185 180 165 190 L 0 2000 l 4000 6000 185 180 Fheee 171 170 165 Level 1; Pops 0-2 I l Figure 5.2.1. Plots of fitness versus time at each level including all three runs L 1000 2000 3000 160 200 180 160 140 120 100 80 60 40 20 FITNESS RUN 1 Level2; Pops 3-5 x10 Elapsed Time (sec) FITNESS HUN 2 Leve12;Pope 3-5 x 10‘ Elapsed Time (sec) FITNESS HUN 3 Level 2; P95. 3-5 T x 10 Elapsed Tlme (sec) 87 190 185 180 175 170 185 160 0 200 180 100 140 120 Level 3; Pope 6-8 f an--- ‘ O MASS OPTIMIZATION RUN 1 Level I; Pops 0-2 Level 2; Pops 3-5 0.11 0.11 0.105 0.1 0.1 0.095 0.09 g 0.09 a 0.08 3 0.085 - 0.081 0.07 0075‘ 0.08 0.07 0.085 0.05 x10 Elapsed Time (sec) MASS OPTIMIZATION RUN 2 0.11 “m." "P”? 0'2 0.1 " 'P 0.1 I I 0.1051L_--.:_--_:_____ 0.095 ------------ II I I I f I —°— POD 0 0.09 _. 0.09 0.1‘ ----1 —— Popt I“ I —e-— P092 ‘ ’ I I 0.085 00957---#----r-—-- 000 I I I I 0.08 '1 E 009- -—-«—---1----« § : I 0.075 . 0.07 5 0.005- ---a——-—----~ : : 0.07 e ooe~ -4~———L-—-- 000 I I 0.085 ‘ I I I. - — — L- — — —- .4 0.075 | 0.08 _, I 0.05 0-07r--- 'f--'* 0,055 ----------- -< I 0.085 ' ‘4‘ 0.05 0.04 0 2000 4000 8000 0 2 4 8 0 X1 Elapsed Tlme (sec) MASS OPTIMIZATION RUN 3 0.11 0.11 ”'3'”; P”? 3'5 0.11 I I 0.105" ' ' °1___| —o—Pop4 0.1 ' '1 7 —-— Pop 5 0.1 : —0— Pop 8 I 0.09 0.095 0.09 -: I E 0.09 I 0.08 o 0.08 g 0.085 0.07 0.07 0.08 0.08 0.05 \ 0.05 1 ’ . 4 2000 3000 0 0 0 1 1000 x 10‘ Elapsed Tlme (see) Figure 5.2.2. Plots of mass versus time at each level including all three runs of domain resolution. 88 rearranging as well as eliminating mass in order to maintain this displacement range. This in turn indicates that the fitness equation has been set up correctly in order to drive the genetic algorithm toward the optimal design. The last set of plots is that of the number of material islands versus time, in Figure 5.2.4. The number of material islands drops off very quickly early in the run. This worked as desired so that the genetic algorithm was not wasting time searching for designs with more than one island. This was also the heaviest penalized parameter in the fitness equation. Of course, some individuals in each population my have had more than one material island. but those individuals never had the highest fitnesses. so these plots are “stuck” at one material island, the best value. The fact that the mass, and thus fitness, of the third run’s best solution was significantly smaller than the masses and fitnesses of runs one and two indicates that the GA. using the population sizes, number of populations, etc., is not converging towards a unique optimal solution. Rather, other runs might possibly find other better solutions. At a greater expense in time, however, it appears likely that such a solution could be found, for this size of problem. 89 DISPLACEMENT OPTIMIZATION RUN 1 5 .a x10 Level 1; Pope 0-2 0| _—-1 x104 Levelz; Pops 3-5 1 T 110-. Level 3; Pope 6-8 T 5 _-————_————-—< -—-—-—— ———-—-———--—q Displacement (m) —--—Pop8 15—..-" -v- Pop? —o—P038 -------------- I ' 0.5>-------'------1 I I I 0 I L o l 4000 0 2 4 8 0 5 10 4 x10 DISPLACEMENT O X10 y 5 X104 Level 1; P908 0-2 451-—-4----r---« 45 I I I I 4P--_-I-_--I----—‘ 4 ------------ I I 35¢---4-———f———e 35 l I 3»—-—4--——»--—e 3 l I r I Displacemenum) M '0 0| I I I I - .1-- I I I I I I I I I 70 '° 2' 15~---4—---L---— 15—-——4---- l l l I I I 1~---1----r---— 1—---fi--‘-r I I I _._ Pop 0 _._ os—-- Pop, --- 05~-- —e— Pop 2 -o- o I I o I 0 2000 4000 8000 0 2 x1 ‘ x10. , Elapsed Time (sec) ‘ DISPLACEM‘ENT OPTIMIZATION RUN 3 -‘ 5 x 10' LveveI1;P'ops 0-2 5 x10 Level 2; Pops 3-5 5 x ‘0 Lei/0131 Pops 6-8 I I I I 45 ---4———-r-—-— 45 I l 4 ' ' 4 3.5 g a i g 2 16L—-—4---—L———~ Is I l l I 1~---n----r---‘ I I I _._ Pop 0 0.5»--- Pepi ---4 0.5 —9— Pop 2 0 1 I 0 0 0 1000 2000 3000 0 2 4 8 x10‘ EIIDSOO Time (980) Figure 5.2.3. Plots of displacement versus time at each level including all three runs 90 MATERIAL ISLANDS OPTIMIZATION RUN 1 Level3:Pops 0-2 Level2;Pops 3-5 Level3;Pops 6-8 5 T 5 I I 5 I l I l l 4.5- ------ : ------ ~ 4.5»-—--J'--——'-----I 4.5» ------ : ------ -« I I l l I j 41>- ------ I ------- 44>-----1----r-----1 40 ------ I ------ i j A _._.p o —~—Pop3 +P°P6 3.5»---- 5 P33, ~ a.s--——-:I_.—pop4 « 3.5 ----- «--—Pop7 7. o _._pop2 I —o—Pop5 +P093 2 31> ------ I ------- 31>----’-—--L----« 3i» ------ ‘ ------ —I g I I I I 3 l I I I O 2.5» ------ I ------- 2.5-----1---—r----~ 2.5 ------- I ------ < I I l l I l I I 3 24> —————— , ------ « 21>--——‘—----,—---e 2» ------ I ------ e Z I I I I 1.5~ ------ ' ------ .. 1.5»—----‘--—-L—--« 1.5» —————— I ------ « I I I I I I I I ”Woo-d limos-4 ti—~---- I I I I l I I I 0.5»- ------ | ------ -I 0.51—----,—---,-—-- 0.5b ------ I ------- I l r I o L 0 g l o I 0 2000 4000 0 2 4 6 0 5 10 It ‘ xio‘ Elapsed Time (sec) MATERIAL ISLANDS OPTIMIZATION RUN 2 5: Level 3; Pop; 02 5 Level 2; Pops 3-5 5 Level 3;Pops 6-3 I I l l I I I 4.5>-——-1'--——I———-« 4.5--—--:—-—-,—---~ 4.5»- ------ , ------- I ——-—Pop0 I —°—Por>3 —-—Pop8 41.__—JI-°"P°PI -1 4»———JI-"—P°P4 4I.--—- —-—Pop7 . I _._. p092 I —o— Pop_5 —o— Pop8 I I I I l 3.5>-----1----r-----1 3.5"“-'1-"-f'“—" 3.5~ ------ I ------- 3 I I I I I I I I l l 5 3"""’I""I""‘ 3’"""I"”‘I"""‘ 30' TTTTTT I """" ‘ 2 I I I I I '525~—-—-4---—|-----I 2.5r-~—--4---—I----« 2.5- ------ I ------ -« '2 I I I I I E I I l I l 3 2*-——1-‘--{-----1 21>~—-1----f—-‘-'1 24> ------ | ------ '1 z I I I I I i.5»——--J---—-'—-—--1 1.51-----I—--—-'----~ 1.51- —————— ' ------ 4 I I I l I I I I I I 1 :::::: ---( WW4 11_-—-——-I l I I I I r I I I l 0.5»-—---1———--,———--4 0.51---—-1---—.-—--« 0.5»— ------ , ------ -1 I I I I I o I I o I I o I O 2000 4000 6000 0 2 4 6 0 5 10 4 Elapsed Time (sfcIo x10 MATERIAL ISLAND OPTIMIZATION RUN 3 5 Level 3; Pops 0-2 5: Level 2; Pope 3-5 5 Level 3; Pope 6-8 I I I I I l I I I _4 _______ l ______ _‘ 4.5F----'----|----- 4.5>-----‘----.--—- 4.5 I I l I l I 4.---.4__--I..---. 4L-_-.I---_I.__-.. 41y ...... l ...... q l i I I I I I I 1 I 3.5--——1--—-¢--—--( 3,5»—----,----.-----I 3.5» ------ I ------ -I l I l l I g 3>--—-—:I_._popo « 31>-—-—: —o—Pop3 3«»----<—o—Pop6 .I 3 ' +Popt , +509; “-209; ‘6 2.5I---—41—°"’°p2 . 2.5---—4 ° -°p 2.sr---- - °p l I I I I E I l I I I z 2I>--~1-—-—-,--—--1 2"""l“"f"""‘ 21> ------ . ------ I l l I I I 1.5 —--J'---—}----+ 1.5----JI---—'L----I 1.5 ------- : ------ 4 I l r I I J 11 e 1 I: ‘r é—G-I 1 --- I l I 1 I osr---{----}—--« os~—-—4---—}---4 05» ------ I ------ 4 I l I I I o __ o I I o l 0 1000 2000 3000 0 2 4 8 0 5 10 x1 Elapsed Time (sec) Figure 5.2.4. Plots of material islands versus time at each level including all three runs 91 The best design that resulted from level one, which consisted of a 2x2 domain of superelements, is shown below in Figure 5.2.5, and was the same for all three runs. It has a fairly symmetric shape and is a very coarse but Run 1,2, &3 Figure 5.2.5. Resulting design from level one for all three runs reasonable design. The shaded elements represent material and the unshaded elements represent void. A table of the fitness parameters obtained from each run is shown below in Table 5.2.1. The fitness values do not vary between runs, Table 5.2.1. Fitness arguments of the best resulting designs from level one Run Material islands Generation Individual P ulalion Run Time sec 1 1 46 1676 0 2938 2 1 64 L £91 I 0 I 4020 3 1 34 I 1247 I 0 I 2148 regardless of the random seed value used. This supports the hypothesis that the design found is the optimal solution in this level. This provides an excellent basis for the higher resolution levels. 92 Run 1 Run 2 Run 3 Figure 5.2.6. Resulting designs from level two for all three runs 93 ‘ 0.” The second level, which consisted of a 4x4 domain of superelements, yielded designs shown in Figure 5.2.6. The influence of the design found in the first level is evident in this level. The structure contains two legs that are constrained at the wall and the loaded and is pointed, between these two ends is the supporting structure. As can be seen in Figure 5.2.6, these designs vary slightly from each other. This is also evident from the fitness arguments, which are shown below in Table 5.2.2. The only difference in the inputs among these runs is the random Table 5.2.2. Fitness arguments of the best resulting designs from level 2 1 40. 2 187.979878 0.051 107 0.000309 1 1 155 28446 3 48670 3 187.837707 0.051634 0.000306 1 1 180 29145 5 48939 seed values. The different value causes the genetic algorithm to search using a different path, which ultimately leads to a slightly different final design. Increased number of generations may have been required for the runs that did not perform as well as the others. Changing the GA parameters (i.e. population size, mutation, etc.) would tend to alleviate this, but time didn’t permit repeating all runs with different parameters. The third and final level, which consisted of the 8x8 domain of superelements, yielded the designs shown in Figure 5.2.7. These designs show the influence from the second level. A similar material structure to that of the second level is evident, but the mass has been trimmed quite considerably. These designs also vary from run to run, but are still fairly similar to each other. A table of the fitness arguments is given in Table 5.2.3. The values are 94 Run 1 Run 2 Run 3 Figure 5.2.7. Resulting designs from level three for all three runs 95 Table 5.2.3. Fitness arguments of the best resulting designs from level 3 188.901173 0.047155 .000356 180 28904 2 188.86451 0.047287 0.000356 1 182 29094 3 189.599478 0.044653 0.000356 1 116 27467 fairly similar to each other, providing evidence that the results are close to the same. It should also be noted that these values of fitness are also similar to those of the previous level given in Table 5.2.2. The third run produced better results than the previous two runs. It found a particular internal structure, which probably aided in keeping the same displacement so that the mass could decrease further. This cross structure is evident in the third run design at the second level, which was the worst of the three runs. This type of structure is not evident on the previous two runs. The two previous runs would probably never have found this cross structure, because the designs they found were already better in fitness. This points out a characteristic of the iiGA approach — that best designs at one level are not necessarily the best starting points for search at a higher level of resolution. However, the gains appear to outweigh this negative characteristic, because of the rapidity of focusing search on good regions of the design space, even if not necessarily the global best region. It is clear that no claim of having found a global optimal solution can be made, but that the process has identified reasonably good solutions in areasonable amount of time. 96 5.3 Superelement Hierarchy Approach Results This migration approach also utilized the parallel capabilities for multiple processors in GALOPPS. This migration approach required four levels, which made it a difficult to use one population per processor, given the number of processors available. If this were done, there could only be two populations per level. It was thought that this would not be adequate, due to the size of the search space for each level. Instead, a total of 16 populations were used, with two populations per processor. This allows for four populations per level. This doubles the wall clock time required, since each processor’s workload is doubled. The first set of results display the performance of the genetic algorithm using the Superelement Hierarchy Approach. The plots will show the change in the fitness function arguments - such as fitness, mass, displacement, and material islands - over the course of the run. A picture of the best resulting design of each level for the four runs is then given. Figure 5.3.1 shows the change in fitness with time for all four levels for all three runs. As in the previous section, the first run is at the top of the figure, the second run is in the middle, and the third run is at the bottom. The fitness curves gradually rise, indicating that change occurs over the entire run. This displays that each level is benefiting the next, but not so dramatically that a high fitness is quickly reached. This is primarily due to the still relatively large search space of eachleveL 97 Level 1; Pope 0-3 190 185 180 2175I -------- —I IL 170>- —°—PopO —~—Pop1 +Pop2 ‘°5>_ —o—Pop3 160 0 5 x10‘ Level 1;Pops 0-3 0 165 160 Level 1; Pope 0.3 l I I I 166b --~ I I I 160 ----‘----« . I . l l 175"""I’"""'-“ -—o—P°po —-—Pop1 _ —o—Pop2 __ ‘70 —o-—POP3 l l l 165>----I-—---4 I l l 160 4 0 5 10 x10‘ 190 185 FITNESS RUNI Level2:'Pops 4-7 190 Level 3' -_...-r-._.. --——4 P0 I 8-11 160 ----,—-—-— I l l 175 >---—l---—-4 I I I l I l _ I , I 170 _._. Pep4 170 _.._ Pops —-—Pop5 —-—Pop9 —o—Pop6 +P0910 165 - ‘*_rp°°7 155» 'T' ?°"" I l I I I I 1 L 10 1 600 5 10 60 5 10 ‘ 110‘ 190 185 180 175 170 - FITNESS RUN 2 Level 2; Pope 4-7 0 185 180 I75 I70 Level 3; Pope 6-11 0 >————-—-— FITNESS RUN 3 Level 2: Pope 4-7 —°—Pop4 —-—Pep5 ‘-o—PopO -I —o—Pop7 I I I ----- or—-——< I I I I 5 10 x 10 Eleeped Time (eec.) 100 185 160 175 I70 - Level3; Pope 6-1 —°— Pop6 —-— PopD —o— P0910 —o— Pop11 1 I I I ..... r‘ - I I I I 5 Level4gPope12-15 I 190 175---——I———--< I I l l "OI ——o—Pop12 —-—Pop13 —o—Pop14 ‘°5_ -—o-—Pop15 . 1 I l 160 ‘ 5 10 x10‘ Level 4; Pop: 12-15 00 180 160 I I 1‘ol'"’—I"-—-—I I I 120 ----- I-----4 0 | I --—Pop13 60> —o— Pop14 —o—P0915 I 60‘---*:-----I I 40l-----‘---- I L;__ 200 5 10 x10. Level4;Pope12-15 10 186 180 175 170 Figure 5.3.1. Plots of fitness versus time at each level including all three runs 98 The fitness increases with increasing level, as can be seen in Figure 5.3.1. This occurs for the same reasons as in the Domain Refinement Approach, except that it might be more prevalent in this case. The amount of mass can only be reduced by a limited amount per level, due to the assigned materiaVvoid configurations, thus limiting the obtainable fitness values. The plots of mass versus time for the four levels for all three runs are shown in Figure 5.3.2. The mass decreases with each level of resolution. The design in each population starts out very heavy and is gradually trimmed down, as in the Domain Refinement Approach. The plots of displacement versus time are shown in Figure 5.3.3. The displacements start out fairly small, which coincides with the large amount of mass used initially. As the mass is trimmed and rearranged, the displacement approaches its maximum allowed value, which is specified as the constraint. The number of material islands versus time is shown in Figure 5.3.4. The number of islands quickly drops to one, as desired. It stayed at one through the rest of the search. This indicates that the genetic algorithm was not astray and did not waste time searching through undesirable designs. 99 MASS OPTIMIZATION RUNI ' - I :P 4-7 Level3;Po 00-11 Level4;Po 012-16 Levelt.Pop0 0 3 .0” Leve 2 ope 0.0. j p .095 . p 0.006 ----I—--__IO.00 -‘--r----—4 0.00 I I 0.0. ____I______I0.006 Po ‘2 -— Pop 0 P 0.075 _._ Pop 13 PepO 0.00 P ”975 ‘ Pop 10 0914 Pop 16 Pop11 075 ____I______ V e g 0.07 0.07 ----r--———I i 0.07 ----l---.._4 p.065 -‘--- -- .— 0.005 I- 0.005 ----r---.I 0.06 ——————— .. 0.00 0.00 ....... .1 ”55 ------ “0.005 -—I---.... 0.066 005 4 - . ' -I 0.05 .r-—.— I 0'0 .045 L .045 I so 0 5 1 0 5 1° 110' Eleeped Time (sec) TIMIZATION RUN 2 Level3;Pop0 0-11 Level4;Pop012o16 .006 I I ‘4 .Ippes «000 ----I.-_-.. 0.00 «0.005 . -———I.-___. 0.005 -« 0.00 A 0.00‘ —‘-«0.o7s . I ~ g 0.075 0.075 --------- «007 --——L---_. 3 007 0.07 -——«0.005 . --_-I.-__.. 0.000 --------- . 0.00 , _. 0.00 -— «Ines I 0.055 -< 0.05 . --I._--.. 0.05 .040 4 I 0 10 0 I 4 x 10 Eleeped Time (eec) MASS OPTIMIZATION RUN 3 Level 1 : Pope 0-3 Level 2; Pope 4-1 Level 3: Pope 0-11 Level 4; Pope 12-15 0.006 , l .005 l 0.00 .006' —°—Pop0 I —¢—Pop4 009‘: -"— Popl 20.00 .. —- P095 ' IDI+P°P2 I—o—Pepc —+—Popa —+—Pop7 0.00 _0.005 " .085 0.005I;----r—-—-—D II ' 0.00 I 0.08 0.08*----*-----I 0075 0.07 0.065 0.05 0.000 0.00r----I—---— I 0.055 o_os 0 I 0.055 1 0.05 .045 l 0 5 10 5 10 X10. x10. :10. x10. Eleeped Time (see) Figure 5.3.2. Plots of mass versus time at each level including all three runs 100 Displacement (m) .. Level 1; Pope 0-3 10 5 1.5» ---------- I.5~-—--I—-———« 1.5 ----- :—-—--« I I '5 —o—Pop0 ‘ 1” —o—Pop4 ‘ 1L'—o—I’op6 —-—Pop1 —-—Pep5 -—Pop0 0.5% -o— Pep2 -« 0.5... -o— Peps -< 0.5 P‘ —0— Pop 10 A —o—-Pop3 —o—Pop7 —o——Pop11 0 0 ‘ 0 ‘ 0 5 0 5 10 0 5 10 x10‘ x10‘ “0‘ Elepeed Time (eec) DISPLACEMENT OPTIMIZATION RUN 2 :10" Level 1. Pope 0-3 x10“ Level 2. Pope 4-7 ‘ Io-aLevel 3: Pope 6-11 5 6 6 6 I l 45 --—-L---+ 45 --——y---« I 4 J 4 """I'"“" 3.6 --l 3.6 ---4 :5: 3 I I““L’"‘_I 3I-----I----— _._ Pop0 _’- P093 2.6I- —-—Pop1 ~ 2.6M"""P°P9 —-0- P092 + P0910 —.— P0 3 —0— Pop11 g 2'- T p 2" I I I I 1.5 ----- :—----— 1.5 ----- IL---— 1.6I-----:----- I I I 1F----r——-— 1~----r---H 1~----h-——— I I I 0.5»-----:----— 0.6 ----- :----—I 0.5~----:----— I l I o I I I 0 2 4 00 5 10 0° 5 10 :10. ‘ :10. Dleplecement (m) M 2.5-----*------l L -°—Pep0 " --—Pep1 A +Pop2 1.5-- —-0— P093 A I I 1I—---—I——-——--I I l 0.5I-----,- ----- l 4L 0° 5 10 110‘ Figure 5.3.3. Plots of displacement versus time at each level including DISPLACEMENT OPTIMIZATION RUNI 2.6-----l-----* I —-—Pop4 2’ ——-—Pop5 ‘ +Pop6 1.5..- —+—Pop7 A I I ‘n——-—'—————< I 0.5 ----- :- ----- I I 00 6 II 10 Elepeed Time (sec) :10" Level 2; Pope 4-75 x 10 DISPLACEMENT OPTIMIZATION RUN 3 If I: Elepeed Time (see) all three runs 101 I————-t——--——‘ I —°—Pop6 —-—Pop0 +Pop10 - —.—- Pop11 I _- p—-—-'——-——q .. Level 3: Pope 0-11x 1 0.. Level4; 10 I I ----L’_-_I I I ----r—_——1 15----—f---~ I 1..----r.-—-_I I 0.5 ——-:-—-5 I I 00 5 10 110‘ b- x 10" Level 1;Pope 0-35 x 10" Level2: Pope 4-75 110.. Level 3: Pope 6-151x Io-ILevel 4; Pope 12-16 -—---i-----< Pop 12 Pop13 P0p14 Pop 16 I —.— —.- I" —°— —.._. r-q ---—f--——-< Pep012-15 -0 Level 4: Pope 12-1 6 MATERIAL ISLANDS OPTIMIZATION RUN 1 5 Level 1: Pope 0-3 Level2; Pepe 4-7 Level 3; Pope 6-11 Level4;P0p012-15 5 Tr 5 v 5 v I I I 4.5 ---------- . 4.5 ----- :-—-—-~ 4.55————:——-—— 4.5 ----- :----—< I I I 45 --------- « 41>----:'------‘ 4<»-—-—-—:——-——-< 4>—--—II-----< I I I S'SI” «:73? q 3'5" —0— P004 1 3'5” —- Pop! ” 3'5? -°- P0912 " _._ popI --— Pops --— Pop9 —-— Pop 13 2 30- _._ p092 . 30— -o- Pops « so —9— Pop10 .. 3. —o— Pop14 .4 g _,_ Pop3 —I— Pop? —r— Rop11 _._ R0915 32.5I --------- - 2.5»—---II-----< 2.5 ----- :—--——J 2.sr—--—t---—-I l I I I g 20 ---------- 2-----I---—-~ 2i>----I——--—~ 2I>-——-I----—- 2 l I l 15I- -------- -« 16»---—I—----I 1.6r---—IL-———~ 15 ----- :—--——< I I l 1 = a = IIL-oo-—< Tim-fl “Lo--. I I I 05» --------- 4 05 ----- :- ----- 0.5 ----- :-----— 05 ----- }-----. I I I o o I I o L 0 5 O 5 10 0° 5 10 0 5 10 x10 :10 x10‘ 1: 10‘ Eleeped Time (eec) MATERIAL ISLANDS OPTIMIZATION RUN 2 Level 1:Pop0 0-3 Level2: Pope 4-7 Level 3; Pope 6-11 Level4;Pop012-15 I I I I 4.5F——-—:----—-I 4.5 ----- f—-—-I 4.6~----:----— 4.6~----:--———+ l l l I 4 ----- r----- 4If—"-“I‘—"" 40----r----- 4r----I---~-< l l I I I I 1 4 3.5 ’- __._ POD 0 "' 3.5 " POD 4 3.5 " _._ POD 8 3.5 " "‘ —o— Pop12 g 31>I+Pop2 -« 3D- —o—Pope ~ 301+P°PI° 0r~+90914 g —+- P093 —+— Pop? —¢- P0911 —‘— IPOPI5 T I I 32.5~----I----— 2.5 ----- I-——--- 2.5~--—-r—---~ 2.5 ----- I----—~ I I I I g 2_——_—:.-_—_ 2.————:————« 2..——--:———_5 24>-—-—:-----« I I _I I I 1.5~----:—---- t.5>--—-I-——- 1.5P---—IL---—~ 1.5 ----- IL----~ I l l l IIPOOOP—O---I 1————I—————I 2._-__I..__.._. 2""'I“'“—I 21p——-—~I——--_I I I I I 1.5 ----- II----~ 1.6»----I‘----—I 1.6~—---IL---—~ 1.5>-----IL----« I I I I 11H--— 1. -- II—u-a--— 11_-.-— l I I I 05r~——-:--——-< 05~----:-—--—~ 0.5~—---:-----I 06~----:---—— I I I I 0 ‘ 0 1 0 1 0 1 0 5 10 0 5 10 0 5 10 0 5 10 x10‘ x10‘ :10‘ Figure 5.3.4. Plots of material islands versus time at each level including all three runs 102 The designs that resulted from level one are shown in Figure 5.3.5. The first level used the hierarchy in which the superelement was either completely material or completely void. This can be seen in the Figure 5.3.5, where the designs are composed as blocks of superelements. The resulting designs are very coarse, but do provide a good basis for the search of the next level of hierarchy. This level provides a general outline of the shape for the final finest hierarchy level. - The designs from each run are similar, but differ in the internal structure. Each design’s resulting fitness arguments are shown in Table 5.3.1. Table 5.3.1. Fitness arguments of the best resulting designs from level one 0.05901 0. 2 185.024326 0.061 1 17 0.00035 1 217 5557 3 185.051405 0.061117 0.000342 1 519 13261 As can be seen from the table, the fitness values are very similar. The differences between the runs can be attributed to the random seed selection and to not allowing for more generations in the run. The resulting designs for the second level are shown in Figure 5.3.6. The second level of hierarchy is that of four blocks per superelement that can contain either material or void. The designs in each run resemble the design found in level one. The designs have had more mass trimmed to provide an improved design. The designs fitness arguments of the best designs at level two are shown in Table 5.3.2. The values continue to remain fairly similar, although the first run found a better fitness than the other two. 103 Run 1 Run 2 .7 ‘5 —f I_ iE ‘— Run 3 Figure 5.3.5. Resulting designs from level one for all three runs Run 1 Run 2 Run 3 Figure 5.3.6. Resulting designs from level two for all three runs 105 Table 5.3.2. Fitness arguments of the best resulting designs from level two 187.800379 0.051 107 0.000355 1 567 1 2 187.508232 0.0521 61 0.000355 1 586 14947 72133 3 187.512486 0.052161 0.000353 1 553 14168 4 69496 The results from the third level of hierarchy are shown in Figure 5.3.7. The third level utilized the hierarchy of half the blocks of the last level, introducing angled material configurations. This can be observed in Figure 5.3.7, where the results are influenced from level two but now include angled beam-like areas. The fitness arguments for the third level are given in Table 5.3.3. Table 5.3.3. Fitness arguments of the best resulting designs from level three 1 1 2 1 88.751795 0.047682 0.000357 1 530 13586 8 62822 3 188.166891 0.04979 0.000356 1 598 15261 8 71 170 As can be seen from the table, the values are still fairly similar, other than the second run, which has a slightly better design at this level. The results of the fourth and final level of hierarchy are given in Figure 5.3.8. This level consisted of the finest materiaVvoid resolution, which provided the final design. As can be seen from Figure 5.3.8, the designs are fairly similar in the outer shape, but as in the results of the other migration approach, the internal structure varies slightly. 106 Run 1 Run 2 Run 3 Figure 5.3.7. Resulting designs from level three for all three runs 107 Run 1 Run 2 Run 3 Figure 5.3.8. Resulting designs from level four for all three runs 108 The resulting fitness arguments are given in Table 5.3.4. As can be Table 5.3.4. Fitness arguments of the best resulting designs from level four 1 1 2 1 88.97504 0.046892 0.000356 577 14689 14 68869 3 1 88.569508 0.048341 0.000357 596 1 5267 14 70906 seen, the fitnesses were fairly similar to each other for the final design, and the first run found the best design. The large amount of variation among runs, even at level two, makes it clear that a global search has not been achieved. However, a variety of reasonably good solutions have been produced after exploring only a miniscule fraction of the total search space at the final (fourth) level of hierarchy. 109 5.4 Migration Approach Comparisons and Conclusions The results from the final level of each approach will be used in the comparison. Neither approach appeared to produce a globally optimal solution. Given more processors or more time, either may have performed much better than represented here. The comparisons here examine only the final designs in terms of mass (material placement), fitness and calculation times. These particular areas are of main interest and should be sufficient for comparing the performance between the two migration approaches. The final resulting structures between the two approaches appear to be very similar. Given the differences between the two approaches the similarity of shape of the resulting designs alone was very rewarding. In fact, the results of both schemes are similar to the designs found by Chapman et al. [6]. The final designs for each run are shown in Figures 5.4.1 and 5.4.2 for reference. In the first two runs, the Superelement Hierarchy Approach appears to have more internal structure as compared to the domain resolution designs. The material resolution also appears to be more consistent in overall structure regardless of the random seeds used. All three runs exhibit similar internal structure, even though the third run’s outer structure is shifted upwards slightly. The structure of the Domain Refinement Approach appears to be smoother than those of the Superelement Hierarchy Approach. This is due to the smooth structure found in the first level, which the final design is a resultant. The structures of the Superelement Hierarchy Approach are more jagged due to also the bases of the first level being that of blocks of material. 110 Run 1 Run 2 Run 3 Figure 5.4.1. Resulting final designs from Domain Refinement Approach 111 Run 1 Run 2 Run 3 Figure 5.4.2. Resulting final designs from Superelement Hierarchy Approach 112 The fitness values found by the two migration approaches were also fairly similar. The Superelement Hierarchy Approach on average resulted in a better fitness than the Domain Refinement Approach (Figure 5.4.3). However, because Migration Approach Fitness Comparison 189.8 * 189.6 189.4 189.2 g 189 +Domain Refine. g 1883 .. +35 Hierarchy 188.6 i 188.4 4 188.2 1» 188 1 1 2 a Run Figure 5.4.3. Plot of fitness versus run for comparison of migration approaches only three runs were done with each approach, no statistically valid conclusions can be drawn, even for this test problem. The greater fitness of the Superelement Hierarchy Approach could be attributed to the greater number of populations that it utilized. The Domain Refinement Approach, using only nine populations, may not have combed the search space as thoroughly. The last run, which was the Domain Refinement Approach’s best, may have been a sufficient path that was taken early enough to provide greater benefit at the end. The final calculation times of the genetic algorithm didn’t prove to be very promising overall. The overall run for either scheme required about 20 hours of wall clock time on 8 or 9 clustered processors, which is far greater than the five to six hours desired. The long search time is attributable to the very large search 113 space. Even though the search space (21024 =10“) has been reduced dramatically using exclusion of undesirable superelement materiaVvoid configurations it is still vast. A plot that shows the run times to the final resulting designs for each migration approach is shown in Figure 5.4.4. As can be seen, the Superelement Migration Approach Calculation Time Comparison 19.80 19.60 19.40 19.20 2' 5 g 19.00 +Domain Refine. 1 . . -,: 8 8° +35 Hierarchy 6 18.60 3 18.40 18.20 18.00 17.80 . 1 a 1 2 3 Run Figure 5.4.4. Plot of Run time versus run for comparison of migration approaches Hierarchy Approach required about a half hour to an hour more than the Domain Refinement Approach. This is actually somewhat surprising, given that the Superelement Hierarchy Approach used two populations per processor. The run time was originally thought to double that of the Domain Refinement Approach’s time, at the very least. If the Superelement Hierarchy Approach were run on 16 individual processors,‘the run time would likely have been approximately halved, thus allowing for an increase in the number of generations for the search or a shorter run time. On the other hand, if the number of populations per level of the Domain Refinement Approach was increased and each population had its own 114 processor, than the Domain Refinement Approach might also have provided better results. With the given information and the limited computational resources, a final determination on which migration approach is more beneficial cannot be made. Either migration approach appears to work fairly well, providing fairly acceptable results. The area that continues to require work is the overall run time. It required about 20 hours, which is still viewed as fairly large. Utilizing more processors may provide the best solution; this will ultimately provide a more efficient means of combing the search space quickly. In final conclusion, the resulting designs of either migration approach are fairly reasonable, which mainly illustrates that using only the desirable materiaVvoid configurations of superelements does not appear to have hurt the quality of the search. Limiting the superelement materiaVvoid configurations to just those that are desirable does not in any way limit the design as far as structure for placement of material. In fact, the resulting designs from both schemes were similar to the results found by Chapman et al. [6]. It is believed that much more benefit can result with using superelements after more research. Utilizing more processors will ultimately provide better results much quicker. 115 5.5 Future Work Utilizing superelement discretization has proven its value, but there is much room for improvement and further research. As mentioned earlier, more processors are a definite requirement. This is a key factor in reducing the run time of the search for this study. Another factor that could reduce the search time is the further reduction of the number of superelement configurations allowable, by applying additional restrictions. Other configurations could be created independently, based on prior experience, limiting the configurations to common geometrical shapes, for example. This would require a deeper analysis of the superelement material void configurations. The migration approaches could also be represented differently. The Domain Hierarchy Approach alone could be improved by adding another level of superelement resolution (16x16), which would provide an even finer element resolution for the design. Another improvement would have been to start with the 4x4 superelement mesh as the coarsest resolution. The Superelement Hierarchy Approach could have used different representations of materiaVvoid at each level. Instead of restricting each level to a resolution of a specified number of triangle elements, particular specified geometric shapes could have been applied at each level. The final resulting structures produced by the search should be more consistent between mns, to support the notion that a global optimal solution has been found. The current lack of consistency clearly indicates the need for longer 116 and perhaps more effective search, or that the objective function is sufficiently “flat” and “loose” that many optimal (lowest mass) or near-optimal solutions exist. One possible approach to provide consistent results is to combine the two approaches used in this study to utilize each approach’s structural advantages. The Domain Hierarchy Approach provided a smooth outer shape of the structure and the Superelement Hierarchy Approach provided configurations with pleasing internal structure. Another approach would be to add a penalty function that would penalize the design for having unconnected material elements in the domain or elements that join to form a point. This penalty would strive to keep material triangle elements connected at their sides within the domain. This penalty would aid to provide a more continuous structure as well as increasing manufacturability of the structure. Another possible improvement would be to develop a “smarter” problem-specific mutation operator, which would avoid and/or repair area with unconnected triangles sharing only a single point, for example. 117 REFERENCES References . Backlund J., lsby R., 1988, “Shape Optimization of Holes In Composite Shear Panels”, Structural Optimization, Proceedings of the lUTAM Symposium on Structural Optimization, pp. 9-16. . Belding B. E., May 1990, “On Truss Optimization By A Homogenization Method”, Masters Thesis, Michigan State University. . Bendsoe M., Diaz A.,Kikuchi N., 1993, "Topology and Generalized Layout Optimization of Elastic Structures”, Topology Design of Structures, Bendsoe M., Soares C., eds. NATO ASI Series, pp. 159-205 . Bendsae M., 1988, “Composite Materials as a Basis for Generating Optimal Topologies In Shape Design”, Structural Optimization, Proceedings of the lUTAM Symposium on Structural Optimization, pp. 31-56. . Chapman C.D., Jakiela M. J., 1996, “Genetic Algorithm-Based Structural Topology Design with Compliance and Topology Simplification Considerations”, Journal of Mechanical Design, Vol. 118, pp. 89-98 . Chapman C.D., Saitou K., Jakiela M. J., 1994, “Genetic Algorithms as an Approach to Configuration and Topology Design”, Journal of Mechanical Design, Vol. 116, pp. 1005-1012 . Derose G. C. A., November 1998, “Solving Topology Optimization Problems Using Wavelet - Galerkin Techniques”, Ph. D. thesis, Michigan State University. . Derose G. C. A., July 1996, “Hierarchical Topology Optimization Problems In Three - Dimensions”, Masters thesis, Michigan State University. . Eby D., October 1997, “Use of Injection Island Genetic Algorithms in the Optimization of Composite Flywheels”, Masters thesis, Michigan State University. 10. Eschenauer H., Koski J., Osyczka A., 1990, Multicriteria Design Optimization Procedures and Applications, Springer - Verlag, Berlin. 119 11. Goldberg D., 1985, Genetic Algorithms in Search Optimgation am Machine Learning, Addison Wesley Longman, lnc., Reading. 12. Goodman E.D., Averill R.C., Punch W.F., and Eby D. J., 1998, “Parallel Genetic Algorithms in Optimization of Composite Structures”, Soft Computing in Engineering Design and Manufacture, Springer-Verlag, pp. 199—208. 13. Goodman ED, 1996, GALOPPS, “The Genetic Algorithm Optimized for Portability and Parallelism”, Tech. Rept. #96-07-01, MSU GARAGe, Michigan State University, www.garage.cps.msu.edu 14. Hajela P., Jih J., 1988, “Boundary Element Methods in Optimal Shape Design - An Integrated Approach”, Structural Optimization, Proceedings of the lUTAM Symposium on Structural Optimization, pp. 109-124. 15. Haslinger J., Neittaanmaki P., 1988, Finite Element Approximation for Optimal Shape Design Theory and Applications, John Wiley & Sons LTD, New York. 16. Hyca M., 1988, “Shape Optimization of the Cross-Sections of Thinwalled Beams Subjected To Bending and Shear", Structural Optimization, Proceedings of the lUTAM Symposium on Structural Optimization, pp. 125- 1 34. 17. Jansen L. F., 1988, “Optimization of Structures Using the Finite Element Method”, Structural Optimization, Proceedings of the IUTAM Symposium on Structural Optimization, pp. 135-141. 18. Jenkin W. M., P., 1994, “A Genetic Algorithm for Structural Design Optimization”, Emergent Computing Methods in Engineering Design, NATO ASI Series, Series F: Computer and Systems Sciences, Vol. 149, pp.30—51. 19. Jenkins W. M., 1991, “Towards Structural Optimization via the Genetic Algorithm”, Computers and Structures, Vol. 40, No. 5, pp. 1321-1322 20. Jensen E., November 1992 “Topological Structural Design using Genetic Algorithms”, PhD thesis, Purdue University 120 21. Kane C., Schoenauer M.,1995, ”Genetic Operators for Two-Dimensional Shape Optimization”, Complexity lntemational 22. Lin S.C., Punch W.F., Goodman ED, 1994, “Coarse-Grain Parallel Genetic Algorithms: Categorization and New Approach”, IEEE Symposium on Parallel and Distributed Processing, pp. 50-55. 23. Logan D. L., 1992, A First Cogrse in the FitnitefiElement Methcg, PWS Publishing Company, Boston, pp. 270-290. 24. Malott B. A., July 1996, “Use of Genetic Algorithms For Optimal Design of Laminated Composite Sandwich Structures With Bending - Twisting Coupling”, Masters thesis, Michigan State University. 25. MARC Users Manual, Volume D, pp. D1-157 — D1-159, MARC Analysis Research Corporation 26. MARC Users Manual, Volume E, Part 1, MARC Analysis Research Corporation 27. Murotsu Y., Kishi M., Yonezawa M., “On Shape Optimization of Truss Structure Based On Reliability Concept”, Structural Optimization, Proceedings of the lUTAM Symposium on Structural Optimization, pp. 193- 200. 28. Nakanishi Y., Nakagiri S., 1996, “Optimization of Frame Topology Using Boundary Cycle and Genetic Algorithm”, JSME lntemational Journal, Series A, Vol. 39, No. 2, pp. 279-285 29. Picuga A., 1988, “Optimality Conditions For Multiple Loaded Structures - Integrating Control and Finite Element Method”, Structural Optimization, Proceedings of the lUTAM Symposium on Structural Optimization, pp. 233- 239. 30. Punch W.F., Averill R.C., Goodman E.D., Lin SC. and Ding Y., February 1995, “Design Using Genetic Algorithms — Some Results for Laminated Composite Structures”, IEEE Expert, Vol. 10(1), pp. 42-49. 121 31. Punch W.F., Goodman E.D., Pei M., Chai-Shun L., Hovaland P., and Enbody R., June 1993, “Further Research on Feature Selection and Classification Using Genetic Algorithms”, Proc. Fifth ICA, pp. 557-564. 32. Rajan S. D., 1995, “Sizing, Shape and Topology Design Optimization of Trusses Using Genetic Algorithms”, Journal of Structural Engineering, Oct. 1995. PP. 1480-1486 33. Reddy J. N., 1993, An lntrfliction to t_he Fi_nite Element Method, McGraw-Hill lnc., NewYork 34. Soto C. A., February 1994, “Shape Optimization Of Plate Structures Using Homogenization With Applications In Mechanical Design”, Masters thesis, Michigan State University. 122 IIIIIIIIIIIIIIIIIIIIIIIIIIIIIII IIII)ljljfljrijjlmjjiljjjjlll’II