The Employment of Genetic Algorithms - Dissertation Example

?Table of Contents Table of Contents 1.Introduction 2 1. Background 2 2.Literature Review 3 3. Objective 4 2. Theory 4 2 Structural optimization 4 2.2. The GA Principle 6 2.3. Truss Structures 7 3. Structural Optimization Using Genetic Algorithms 8 4. An Example of 10 bar Truss 10 5. Conclusions 11 References 12 1. Introduction In the recent years, the employment of genetic algorithms (GA) to get the optimal design for the civil engineering structures has been studied (Leon, 1970; Bunday, 1984; Bell, 1974; Makowski, 1965; Collatz and Wetterling, 1975). Ghasemi et al. (1999) have revealed the appropriateness of the genetic algorithms to deal with the large trusses that have numerous indefinite variables. This study shows that how an algorithm of our design can be employed to match this previous study. The paper will hugely concentrate over the application of genetic algorithm to trusses developed under indefinite conditions (Ganzerli et al., 2003). 1.1. Background Galileo Galilei has been recognized as the first scientist by the Coello Coello et al. (1994), who studied optimization of structures over the bending of beams in his work. Over the period of time, this subject has developed and become an area of engineering, in itself, which is known as the structural optimization. For the last few decades, the rising interest towards this area has been because of the availability of powerful and cheap computers as well as due to the rapid progress in the analytic and optimization methods for the structures (Soh and Yang, 1998). The optimization of the weight of the structures is of great importance to many fields of engineering. It might be linked to cost optimization, in some aspects, as it clearly tends towards an optimal usage of the materials. The weight optimized structures, in civil engineering, are very convenient as the construction as well as the transportation work in, relation to the build-up, is simple. The engagement of the least possible share of the load capacity by the structure itself is another benefit of developing a structure with its weight being optimized. Also, in the aircraft and car industries, the structural optimization is highly important since a lighter structure leads to a better fuel efficiency. The use of genetic algorithms is an efficient optimization technique. GA is a form of evolutionary programming (Alander, 1999) and most likely known as the best optimization technique of the present time (Ashlock, 2006). It provokes the evolutionary principle of survival of the fittest through aggregating the optimum solutions to a problem in numerous generations in order to augment the outcome gradually. The elementary population of solutions is constructed on the random basis and then along with the evolution, the best solutions are aggregated in each generation until they converged in to an optimal solution (Gold Berg, 1989). 1.2. Literature Review Over the previous two decades, the genetic algorithms have been used in search for an optimal design solution for trusses that has been explained in numerous scientific reports. However the optimization in the majority of these studies does not relate to shape, size and topology simultaneously. In general, the topology of the truss is fixed that means the inner connectivity of the members is constant (Ravindran and Ragsdell, 2006). The most frequently used method to deal with the optimization of the truss topology is the ground structure method that has been used by Hajela & Lee (1995) and Deb & Gulati (2000) in their work. An extremely connected ground structure having numerous nodes and elements, in the ground structure method, is gradually minimized until just the basic required elements are left (Ohsaki, 2005). The emphasis has been over the development of a highly efficient genetic algorithm, in some of the recent studies on truss optimization with GA, which determines an optimal solution through the least possible number of calculations such as the adaptive approach given by Togan & Daloglu (2006) and the directed mutation given by Li & Ye (2006). Also the size, shape and topology have not been taken in to consideration simultaneously, in these studies. 1.3. Objective The objective of this study is to investigate the design of structures through employing the genetic algorithms. It aims to provide the design of a program that employs genetic algorithms in order to optimize a truss structure. It will also include an example of truss optimization. 2. Theory 2.1. Structural optimization There are different aspects in which a structure can be optimal, which are called objectives, and may, for example, include the cost, weight, stiffness of the structure. An objective function, f, can be used for the numerical evaluation of a particular objective in order to asses the goodness of the structure with respect to its weight, cost or stiffness (Christensen and Klarbring, 2008). Definitely, the structure has to be optimized under some constraints or else it is an issue that does not have a well defined solution (Christensen and Klarbring, 2008). At first, there are design constraints, such as the constraint of geometrical extension or the constraint of the availability of various structural parts. Then there are behavioral constraints (Christensen and Klarbring, 2008) on the structure, which signify the response of the structure under specific load conditions. This, as for example, includes constraints on displacements, forces, stresses, and dynamic responses. Moreover, there is one evident requirement that is valid for all structures that is the kinematical stability or else there are mechanisms (Tsai, 2001). This can be considered as a behavioral constraint. Structures lying under the constraints are known as the feasible solutions to the optimization problem. For example, a generalized optimization is represented below: Where ‘f’ refers to the objective function, ‘x’ refers to the vector or the function that denotes the design variables, and ‘y’ refers to the vector or the function that denotes the state variables representing the structural response (Christensen & Klarbring, 2008). Optimization can be performed in accordance to two or more distinct objective functions that represent the multi-objective optimization (Coello Coello and Christiansen, 2000), which is also known as the vector or the multi-criterion optimization (Christensen & Klarbring, 2008; Coello Coello and Christiansen, 2000). As for instance, Galante (1996) endeavored to determine a minimal weight of a truss that employed the least possible number of different profiles. Under multi-objective optimization, a single generalized objective function can be placed with the weighted parts of the constituting objective functions. Thus, different optima are obtained through changing the weights (Christensen & Klarbring, 2008). Other procedures to deal with the multi-objective optimization are also feasible. In case of the trusses, the optimization can be classified in to three categories, which are briefly described below: Sizing Optimization: This refers to determining the optimal cross-sectional area of every part of the structure. Shape Optimization: This refers to optimizing the external shape of the structure. Topology Optimization: This refers to the investigation for the best inner connectivity of the parts of the structure (Christensen & Klarbring, 2008). One method for the optimization of these three parameters is to take them in to account one by one, commencing from the topology optimization that is a so-called multi-level optimization technique and is also known as the layered optimization (Kawamura and Ohmori, 2002). However, it is evident that this approach does not necessarily give the ultimate global solution as the problems are not linearly dissociable (Deb and Gulati, 2000). Among the benefits of a genetic algorithm, one is that a simultaneous optimization of all the three parameters can be achieved 2.2. The GA Principle There are three characteristic operators of Genetic Algorithms, which are selection, crossover and mutation. Under each generation or iteration, the three operators are exercised over a population of potential solutions or individuals so as to enhance their fitness. A string is used to represent each individual, which resembles very much to the natural chromosomes due to which they are termed as genetic algorithms (Deb, 1997). Firstly, the population is randomly constructed, and the breeding goes on until a criterion for inhibition is attained, for instance, the surpassing of a particular number of generations, or the lack of further development within the individuals. There are numerous benefits of the GA technique, among which the prime benefits are its simplicity and broad applicability. Also, GA technique can be conveniently altered or updated to work on a broad range of problems (Sivanandam and Deepa, 2008), as opposed to the conventional search methods that are specified on a particular sort of problem (Deb, 1997). The technique of the genetic algorithm is relatively strong as well. Moreover, it does not seem to get stuck in local optimums in contrary to other techniques that may do (Deb, 1997; Sivanandam and Deepa, 2008). Moreover, the GA technique can handle discrete variables and has the potential to work in highly intricate search spaces since it employs the function evaluations instead of derivatives (Sivanandam and Deepa, 2008). On the contrary, it may need numerous function evaluations, and it often experiences the preterm convergence. The individuals become quite similar to each other, initially in the process (Sivanandam and Deepa, 2008). Moreover, there are various alternatives and options in Genetic Algorithms and it may be difficult to determine the suitable settings to attain high efficiency. 2.3. Truss Structures A truss, present in the roof supports and bridges, is a structure composed of members joined at their end points as shown in the Figure 1 given below. A prime engineering exercise is to reduce the cross-sectional area of the members whilst assuring that the truss holds up a specified load. This is an optimization problem, for sure. The objective is to reduce the overall volume of the truss members along with conforming to specified constraints such as the anticipated stresses over the truss members and the permissible displacements at the connecting points. It is computationally expensive to employ the conventional calculus-based optimization techniques. However, further drawbacks are associated with these conventional techniques as they demand that the function employed in the modeling of the truss be differentiable, and hence, continuous. Nevertheless the members are generally off-the-shelf components that are found in a range of discrete sizes. The genetic algorithm enables us to designate the truss populations with the members taken from this available range. The Figure 1 given below shows the 10-bar truss whose solution will be illustrated further in this paper. The connecting points of the truss move only in the horizontal and the vertical directions. Xi denotes the positive displacements whereas the Pi denotes the loads. The triangles at the connecting points A and F signify that they are externally constrained and thus, unable to move. The response of the structure to the external load comprises of the following three items. The internal forces of each component or member of the truss, The internal stresses that are estimated by dividing the internal forces by the cross-sectional areas of the truss members, and The displacements. We are able to derive the responses of the structure for a specified load condition with the help of the well-understood matrix relationships (Wang, 1986). Figure 1: Truss (10 bars). (Source: Burton, n.d.) 3. Structural Optimization Using Genetic Algorithms Genetic algorithm is coded in C++ with the help of object-oriented programming techniques. It will include a generic GA class as well as a parameter class form the base. Other classes are derived from these classes, which can employ different pairing and mating algorithms. There is a class at the next level that estimated the volume of the truss and investigates that if its constraints have been violated or not. The objective is to reduce the volume of the truss, which is equal to the aggregate of the cross-sectional areas times the lengths of the truss-members, under the fixed load conditions and geometry. The design process specifies constraints or limitations over the optimum displacements and stresses, so that the safety and the serviceability of the truss-structure do not get lower than a given minimum value. The mathematical statement for the optimal design problem can be like this: minimize f (A, P), when gj(A, P) is at most 0. (Source: Burton, n.d.). where j = 1...n, f is the volume as a function of the cross-sectional areas (A) and the external loads (P), gj(A,P) represents the constraints, and n denotes the number of constraints that should be met through the optimal design (Burton, n.d.). In case the values of gj(A, P) gets above zero for any constraint then the specific configuration in view becomes unfit. Genetic algorithm, in trusses, functions through a population of trusses in which the members vary in their cross-sectional area. In the population, each chromosome is denoted as a series of randomly generated cross-sectional areas of the truss-members. The cost-function depends upon the structural responses for a specific load condition, as stated previously. A cost penalty is assigned to those trusses that do not satisfy the constraints. The genetic algorithm sorts the population and let the upper half of it to mate. The parents are coupled through a tournament algorithm having a subset size equal to twenty. The following three mating algorithms are employed: (1) single point crossover, (2) greedy crossover, and (3) static random crossover (Haupt and Haupt, 1997). One of these three mating algorithms is randomly selected at each generation. We commence with a 5 percent mutation rate and gradually reduce it to 1 percent. When the optimal truss in the population does not augment after 10 generations then the convergence is reached. 4. An Example of 10 bar Truss The truss of 10 bars as shown in the Figure 1 is a frequently employed benchmark in the literature. The limitation is that the stress of every member may not transcend 25 ksi for tension as well as for compression, in which a kip is 1000 pounds. The exception is the 9th member whose stress may not get above 75 ksi. The member cross-sectional areas are between 0.1 square inches and 10 square inches. The material used in the truss is aluminum and the Young’s Modulus of the truss is 1.0 ? 105 psi, in which the Young’s Modulus is a parameter that depicts the material’s stiffness. Ghasemi et al. (1999) presents a precise solution to the problem that is solved through the sequential quadratic programming (SQP), along with a genetic-algorithm-solution. The results of the Genetic Algorithm Truss are favorably compared with the results that are presented in the work of Ghasemi et al. (1999). Table 1: Results of the 10-bar Truss (Source: Burton, n.d.) The table 1 above shows the comparison between the published results to those obtained with the GA-Truss. The overall volume of the truss, which is the solution of GA-Truss, is under 2 percent of the SQP solution. The 4th column of the table presents the situation in which the design variables are rounded to the integer values, which decreases the convergence time and offers an optimal solution. The 5th column of the table shows the continuous design variables of the GA-Truss whereas the 6th column shows the continuous design variables of the GA-Truss through rebirthing that is a method of limiting the range of permissible values for the design variables depending upon their values after the GA’s partial run. The convergence will be faster since the new population holds stronger bounds on the variables. The new ranges are estimated after the partial run as more or less a percentage of the values of each variable. A population may be re-generated many times since each rebirth provides a tighter bound for the design variables, which successfully reduce the search space. 5. Conclusions The conclusions are: It is not necessary that two runs converge on to the same solution; A larger elementary population converges to reach an improved truss; Passing on good genes gets tougher if the rate of mutation is set too high; The algorithm may stick in the local minima if the rate of mutation rate is set too low; A population converges faster if it is represented with less precision; A population converges on an augmented truss if it is represented with more precision. The precision could be sequenced so as to permit only integers for the widths of the truss members, which is effective for a preliminary design. For the existing population, the bit depth may be modified during the run time; The level of uncertainty is directly related to the structural cost. References Alander Jarmo T. (1999). An Indexed Bibliography of Genetic Algorithm Implementations. Bibliography. University of Vaasa. Department of Information Technology and Production Economics. Ashlock, Daniel. (2006). Evolutionary Computation for Modeling and Optimization. New York: Springer. Bell, Brian J. (1974). Advanced theory of structures (frame analysis). London : Macdonald and Evans. Bunday, B. D. (1984). Basic Optimisation methods. London : Edward Arnold. Burton, A. (n.d.). Truss Optimization Using Genetic Algorithms. Mathematics and Computer Science, Gonzaga University Christensen, Peter W and Klarbring, Anders (2008). An Introduction to Structural Optimization. Springer Netherlands. Coello Coello, Carlos A. Christiansen, Alan D. (2000). Multiobjective optimization of trusses using genetic algorithms. Computers and Structures. Volume 75, issue 6. Pages 647- 660. Coello Coello, Carlos A. Rudnik, Michael. Christiansen, Alan D. (1994). Using genetic algorithms for optimal design of trusses. Proceedings of the Sixth International Conference on Tools with Artificial Intelligence. Pages 88-94. Collatz, L., and Wetterling, W. (1975). Optimization problems translated [from the German] by P. Wadsack. New York : Springer-Verlag. Deb, Kalyanmoy. (1997). Genetic Algorithm in Search and Optimization: The Technique and Applications. Proceedings of the International Workshop on Soft Computing and Intelligent Systems. Pages 58-87. Deb, Kalyanmoy and Gulati, Surendra. (2000). Design of Truss-Structures for Minimum Weight using Genetic Algorithms. Finite Elements in Analysis and Design. Volume 37, issue 5. Pages 447-465. Ghasemi, M., et al.. 1999. Optimization of Trusses Using Genetic Algorithms for Discrete and Continuous Variables. Engineering Computations. MCB Univ. Press Ltd., Bradford, Engl. Vol. 16 (No. 3): 272-301. Ganzerli, S., De Palma, P., Smith, J., Burkhart, M. 2003. Efficiency of genetic algorithms for optimal structural design considering convex models of uncertainty. Proceedings of The Ninth International Conference on Applications of Statistics and Probability in Civil Engineering, San Francisco, July 6-9, 2003. Ganzerli S. and Burkhart M.F. 2002. Genetic algorithms for optimal structural design using convex models of uncertainties. Fourth International Conference on Computational Stochastic Mechanics (CSM4), Kerkyra (Corfu), Greece. June 9-12, 2002. Galante, Miguel. (1996). GENETIC ALGORITHMS AS AN APPROACH TO OPTIMIZE REAL-WORLD TRUSSES. International Journal for Numerical Methods in Engineering. Volume 39, issue 3. Pages 361-382. Goldberg, David Edward. (1989). Genetic algorithms in search, optimization and machine learning. New York: Addison-Wesley. Hajela, P. Lee, E. (1995). GENETIC ALGORITHMS IN TRUSS TOPOLOGICAL OPTIMIZATION. International Journal of Solids and Structures. Volume 32, issue 22. Pages 3341-3357. Haupt, R., Haupt, S., 1997. Practical Genetic Algorithms. Wiley-Interscience. Hoboken, NJ. Kawamura, H. and Ohmori, H. Kito N. (2002). Truss topology optimization by a modified genetic algorithm. Structural and Multidisciplinary Optimization. Volume 23, issue 6. Pages 467-473. Leon, C. (1970). Introduction to methods of optimization. Philadelphia; London : Saunders. Li, Na. Ye, Feng. (2006). Optimal Design of Discrete Dtructure with Directed Mutation Genetic Algorithms. 2006 6th World Congress on Intelligent Control and Automation. Volume 1. Pages 3663-3667. Makowski, Z. S. (1965). Steel space structures. London : Joseph Ohsaki, M. Katoh N. (2005) Topology optimization of trusses with stress and local constraints on nodal stability and member intersection. Structural and Multidisciplinary Optimization. Volume 29, issue 3. Pages 190-197. Ravindran, A., Ragsdell, M.K., and Reklaitis, V.G. (2006). Engineering optimization : methods and applications. Chichester : Wiley. Sivanandam S. N. Deepa S. N. (2008). Introduction to Genetic Algorithms. Berlin: Springer. Soh, Che-Kiong. Yang, Jiaping. (1998). Optimal Layout of Bridge Trusses by Genetic Algorithms. Computer-Aided Civil and Infrastructure Engineering. Volume 13, issue 4. Pages 247-254. Togan, Vedat. Daloglu, Ayse T. (2006). Optimization of 3d trusses with adaptive approach in genetic algorithms. Engineering Structures. Volume 28, issue 7. Pages 1019-1027. Tsai, Lung-Wen (2001). Mechanism design: enumeration of kinematic structures according to function. New York: CRC Press. Wang, C.K. (1986). Structural Analysis on Microcomputers. New York, NY: Macmillan. Read More