The Korean Society Fishries And Sciences Education
[ Article ]
The Journal of the Korean Society for Fisheries and Marine Sciences Education - Vol. 29, No. 2, pp.544-551
ISSN: 1229-8999 (Print) 2288-2049 (Online)
Print publication date Apr 2017
Received 06 Feb 2017 Revised 24 Feb 2017 Accepted 03 Mar 2017
DOI: https://doi.org/10.13000/JFMSE.2017.29.2.544

An Comparative Study of Metaheuristic Algorithms for the Optimum Design of Structures

Yeon-Sun RYU ; Hyun-Man CHO
Pukyong National University
구조물 최적설계를 위한 메타휴리스틱 알고리즘의 비교 연구
류연선 ; 조현만
부경대학교

Correspondence to: 051-629-7382, oldsea@nate.com

Abstract

Metaheuristic algorithms are efficient techniques for a class of mathematical optimization problems without having to deeply adapt to the inherent nature of each problem. They are very useful for structural design optimization in which the cost of gradient computation can be very expensive. Among them, the characteristics of simulated annealing and genetic algorithms are briefly discussed. In Metropolis genetic algorithm, favorable features of Metropolis criterion in simulated annealing are incorporated in the reproduction operations of simple genetic algorithm. Numerical examples of structural design optimization are presented. The example structures are truss, breakwater and steel box girder bridge. From the theoretical evaluation and numerical experience, performance and applicability of metaheuristic algorithms for structural design optimization are discussed.

Keywords:

Metaheuristic algorithm, Optimum design, Genetic algorithm, Simulated annealing

Ⅰ. Introduction

An optimization problem is the problem of finding the best solution from all feasible ones. To solve the optimization problem, optimization algorithms are needed. There are many optimization algorithms which can be classified in many ways, depending on the focus and characteristics.

If the gradient of a function is the focus, optimization can be classified into gradient-based algorithms and gradient-free algorithms. Gradient- based algorithms such as hill-climbing use derivative information. Gradient-free algorithms do not use any derivative information but the values of the function itself. Some functions may have discontinuities or it may be expensive to calculate derivatives accurately. And thus gradient-free algorithms become very useful in this case(Ryu et al., 2011).

Optimization algorithms can also be classified as deterministic or stochastic. If an algorithm works in a mechanical deterministic manner without any random nature, it is called deterministic. It will reach the same final solution if we start with the same initial point in the deterministic algorithms. Stochastic algorithms generate and use random variables. Stochastic algorithms will usually reach a different solution every time the algorithm is run, even though the same initial point is used. Conventional deterministic optimization algorithm assumes that the information of the function and derivative is available and that this information is used to determine the search direction in a deterministic manner at every step of the algorithm. In many practical problems, such information is not available(Boussaid et al., 2013).

Algorithms with stochastic components were often referred to as heuristic in the past, though the recent literature tends to refer to them as metaheuristics. A metaheuristic is a higher-level strategy that guides and modifies other heuristics to produce solutions to an wide range of hard optimization problems without having to deeply adapt to each problem. Many metaheuristics implement some form of stochastic optimization, so that the solution found is dependent on the set of random variables generated. Notable examples of metaheuristics include genetic algorithms, simulated annealing, tabu search, etc. In general, finite-dimensional constrained minimization problems are symbolically expressed as:

Find a design variable vector x∊Rn;
to minimize the cost function f(x),
subject to the m constraints gi(x)≤0.

Recently, a considerable amount of research effort has been made for the development and application of metaheuristic methods in various fields of engineering optimization. Among them, simulated annealing(SA) and genetic algorithms (GAs) have been advantageously applied for the structural design optimization. SA has a favorable advantage of possible convergence to a precise global optimum. However, its major drawback lies in the time-consuming computation to reach the neighborhood of global optimum, or slower convergence(Van Laarhoven and Aarts, 1987). GA has various versions such as simple GA(SGA), micro-GA(μGA), hybrid GA, Metropolis GA(MGA) and others(Woo and Park, 2003; Ryu et al., 2006). They have been successfully applied in various fields of optimization.

In the paper, characteristics and critical procedures of some metaheuristic algorithms such as SA and several GAs are reviewed. From the theoretical evaluation and numerical experience for optimum design problems of structures, performance and applicability of metaheuristic algorithms are discussed.


Ⅱ. Metaheuristic Algorithms

1. Simulated Annealing

Simulated annealing(SA) is a probabilistic method which simulates solid thermodynamic annealing process to obtain a well ordered solid state of minimal energy. This technique is often used for finding global optimum of a given function that may have local minima in a large search space. It was first proposed by Kirkpatrick et al.(1983). This method consists in carrying a solid at high temperature, then in lowering this temperature slowly.

In SA, there are usually two basic iterative loops, i.e., an inner loop of Metropolis criterion or reproduction operation and an outer loop of temperature reduction or new design iteration. Once the initial values and starting current design are chosen, a random search is used to generate a new design in the inner loop of Metropolis criterion. Metropolis criterion is a stochastic process to reach a thermal equilibrium status of a solid in heat bath (Metropolis et al., 1953). For a specified temperature, reproduction with Metropolis criterion will be continued until the maximum number of inner loop iteration is reached. In the high temperature, the acceptance probability becomes larger and most of new designs are accepted. In the outer loop iteration, the reduction of temperature is controlled by a cooling schedule until it becomes very small. If temperature becomes very small, acceptance probability also becomes smaller and the Metropolis criterion is hardly met. Thus, the global optimum will hardly be missed once it is found. The temperature is reduced according to the cooling schedule, i.e., the search domain is gradually reduced. Rapid reduction of the temperature may cause the convergence to an undesirable local optimum.

2. Genetic Algorithms

Genetic algorithm(GA) is based on evolutionary ideas of natural selection and survival of the fittest in the ecosystem. GA generates solutions to optimization problems using techniques inspired by natural evolution, such as mutation, selection, and crossover. Simple GA(SGA) is robust and still applied in the fields of structural design optimization (Holland, 1992; Jin, 2000). However, a critical drawback of SGA lies in the premature convergence to a local optimum if any relatively dominant individual appears in early generation. Original SGA was developed by Holland in the early 1970s. Since then many variants of GAs have been derived and applied to optimization problems. A micro GA(μGA) was proposed by Krishnakumar (1989), in which the population size and amount of computation were successfully reduced without loss of variety of potential genetic information. Like SGA, μGA also uses tournament selection and one-point crossover as reproduction and crossover operator, respectively. However, crossover probability is usually taken as 1.0 so as to surely exchange the genetic information between selected individuals. Mutation is no more necessary since μGA uses the wide variety of genetic information through a restarting option. The elitism is favorably used in μGA in order to keep the best individual in a generation.

A Metropolis GA(MGA) was developed Ryu et al.(2005; 2006), in which Metropolis criterion is combined to the reproduction operator of SGA in addition to a roulette wheel selection MGA. [Fig. 1] shows the flow chart of Metropolis GA.

[Fig. 1]

Flow Chart of Metropolis Genetic Algorithm

At early generations, Metropolis criterion in MGA enables an individual with low fitness to be possibly accepted so that the genetic varieties may be maintained in the population without losing the potential genetic information. It also prevents the convergence to a premature local optimum through the expansion of search space. Thus, a global optimum may not be missed and premature local optima can be avoided as well. At near-final generations, the Metropolis acceptance probability of low-fitness individual will be considerably reduced, and the reproduction operation like roulette wheel selection will be mainly used. Consequently, the precise convergence to a global optimum is assured within the minimal number of generations in MGA.


Ⅲ. Numerical Examples for Structural Design Optimization

1. Three-bar Truss

A symmetric 3-bar truss is shown in [Fig. 2] Cross-sectional areas(x1, x2, x3) of the members are the design variables. The constraints are based on member crushing, member buckling, failure by excessive deflection of node 4, and failure by resonance when the fundamental natural frequency of the structure is below a given threshold.

[Fig. 2]

Three-bar Truss

The cost function to be minimized is the total volume of the structure;

fx=l22x1+x2(1) 

2. Composite Breakwater

A composite breakwater consists of upright structure(Au) and foundation or rubble mound which is again composed of core(Ac) and revetments(Arl, Arw). In the [Fig. 3], design variables are defined as the dimension of structural components. The design constraints are based on sliding, overturning, stability, bearing capacity of structural components, etc.(Ryu et al., 2005). The cost function is the construction cost of unit length of the breakwater, which is expressed as weighted sum of structural components with the weighting factors or unit costs (cu, cc, crw, crl);

fx=cuAu+ccAc+crwArw+crl+Arl(2) 
[Fig. 3]

Design Variables for Composite Breakwater

3. Composite Steel Box Girder Bridge

The design of a composite steel box girder bridge consists of the design of concrete slab and steel box girder sections. A concrete slab is first designed and then it is considered as a loading for the design of steel box girder. For the concrete slab, the thickness of the slab is selected as a design variable. Only one variable is enough since the steel ratio per unit width of reinforced concrete slab can be expressed in terms of its thickness. The width of the slab is assumed to be pre-determined. Design variables for the steel box girder section are identified as shown in [Fig. 4]. They are upper flange thickness(x1), lower flange thickness(x2), web thickness(x3), projecting width of longitudinal compression stiffeners(x4), thickness of longitudinal compression stiffeners(x5), projecting width of longitudinal web stiffeners(x6), and thickness of longitudinal web stiffeners(x7). The single-cell box girder section is considered in the study and its depth and width are assumed to be pre-determined.

[Fig. 4]

Design Variables for Steel Box Girder

Weight of the structure is a design cost function to be minimized. Hence, the cost function for the concrete slab, fc(x), is expressed as the thickness, T, itself. The cost function for the steel box girder, fs(x), is formulated as the weight per unit length of the girder. Here, Ws is the unit weight of the steel and As is the area of the girder section.

fcx=T;fsx=WsAs(3) 

The design constraints for a concrete slab are formulated according to the Standard Specifications of Korean Highway Bridges, in which the ultimate strength design method is recommended for the reinforced concrete structures. The design constraints for a steel box girder section are formulated according to the Standard Specifications of Korean Highway Bridges, which is the load and resistance factor design. The design constraints are based on flexural strength, shear strength, web slenderness, properties of longitudinal compression flange and web stiffeners, and deflection(Ryu et al., 2002).


Ⅳ. Numerical Results

1. Three-bar Truss

Input data for design optimization of 3-bar truss are listed in <Table 1>. As the parameters, the population size is 10 for SGA and MGA, and 5 for μGA, and the maximum number of gnerations and the string length are commonly set to 200 and 15, respectively.

Input Data for Three-bar Truss

The results are presented in <Table 2>, where Nopt is the number of function evaluations to reach the optimum. As shown in the table, MGA yields the best solution with the minimal Nopt. MGA and SA give the exactly same optimum. However, the amount of computation in MGA is much less than that in SA, i.e., less than 20%. This shows the efficiency of MGA. The values of optima in table 1 are the best results obtained out of 100 trials. In general, GAs may yield a different optimum in each trial. Thus, the global optimum is assured from the results of 100 trials. The distribution of optima in 100 trials is shown in [Fig. 5]. As shown in the figure, the probabilities to obtain the true global optimum(Popt) are 100% in MGA, 91% in SGA, and 43% in μGA, respectively. This shows the global convergence property and reliability of MGA.

Results of Three-bar Truss Example

[Fig. 5]

Distribution of Obtained Optima for Three-bar Truss Problem

2. Composite Breakwater

Input data for design optimization of composite breakwater are wave height: 6.3m, wave period: 11.4sec, water depth: 10.1m, friction coefficients: 0.6 and 0.8, and angle of rubber mound: 0.46rad and 0.59rad. Lower and upper bound of design variables(x1~x6) are; (10,20), (1,15), (1,10), (0.1,5), and (1,15), respectively. Optimization parameters for GAs are the population size 60 for SGA and MGA, and 5 for μGA, and maximum number of generations 2000.

The best results of 100 trials are summarized in <Table 3>, where Popt is the probability to obtain the best optima shown in the corresponding column.

Results of Breakwater Example

The distribution of optima in 100 trials is shown in [Fig. 6]. The probability to obtain the best solution(Popt) is 62% in MGA, 9% in SGA, and only 1% in μGA, respectively. MGA needs less amount of computation than SA for the same quality of solutions. Comparing other GAs, MGA yields the best solution with the highest probability to obtain it.

[Fig. 6]

Distribution of Obtained Optima for Breakwater Problem

3. Composite Steel Box Girder

In the design of concrete slab, the vertical behavior of the slab is the only factor that is considered in design. So the same kind of problem is solved for all the design cases with the Carroll’s μGA. Since the optimization problem is a single-variable problem, the population size for the μGA is taken as N=1 as the Carroll’s GA Driver recommended(1998). The optimal solution is obtained in 13 generations and the results is the thickness of slab, x0=250mm

The results of design optimization for steel box of single-span bridge are summarized in <Table 4> As shown in the table, the μGA with N=5 gives the true optimum in minimum number of generations or it requires minimum number of function evaluations. It is also shown that the μGA is robust and more efficient than the SGA.

Results of Box Girder Example


Ⅴ. Conclusion

Metaheuristic algorithms for structural design optimization are reviewed. Metaheuristics algorithms such as simulated annealing, genetic algorithm, tabu search, etc. have the following common characteristics; they are nature-inspired; they use stochastic components; and they do not use the gradient of the cost function. Simulated annealing is a good approximation method for the global optimization problem. Its advantage is an ability to prevent trapped in local minima. But simulated annealing takes long time to find the optimum. Simple genetic algorithm is robust and applied wide range of optimization problems. However it cannot find a global optimum for some problems. Genetic algorithm has various versions such as micro genetic algorithm and Metropolis genetic algorithm. Metropolis genetic algorithm was developed by the combination of Metropolis criterion of simulated annealing and roulette wheel selection of simple genetic algorithm. The characteristics of simulated annealing and genetic algorithms are briefly discussed. Numerical examples of structural design optimization using metaheuristic algorithms are also presented. They are three bar truss, composite breakwater, and composite steel box girder. From the numerical results, performance and applicability of metaheuristic algorithms are evaluated.

Acknowledgments

※ This work was supported by a Research Grant of Pukyong National University(2016).

References

  • Boussaid, I., Lepagnot, J., & Siarry, P., (2013), A survey on optimization metaheuristics, Journal of Information Science, 237, p82-117.
  • Carroll, D. L., (1998), FORTRAN Genetic algorithms driver, Dept. of Aeronautical and Astronautical Engineering, University of Illinois at Urbana-Champaign.
  • Goldberg, D. E., (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, MA.
  • Holland, J. H., (1992), Adaptation in Natural and Artificial Systems. A Bradford book, The MIT press.
  • Jin, G. G., (2000), Genetic Algorithms and Their Applications (in Korean), Kyowoo-sa.
  • Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P., (1983), Optimization by simulated annealing, Science, 220(4598), p671-680.
  • Krishnakumar, K., (1989), Micro-genetic algorithms for stationary and non-stationary function optimization, Intelligent Control and Adaptive Systems, SPIE, 1196, p289-296.
  • Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E., (1953), Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, p1087-1092. [https://doi.org/10.1063/1.1699114]
  • Ryu, Y. S., Lim, O. K., Kim, M. K., & Lee, T. H., (2011), Introduction to Optimum Design (in Korean), Honreung Publishing co.
  • Ryu, Y. S., Kim, J. H., Cho, H. M., & Kim, J. T., (2002), LRFD-based design optimization of steel box girder sections using genetic algorithms, Journal of Civil Engineering, KSCE, 6(2), p127-134. [https://doi.org/10.1007/bf02829129]
  • Ryu, Y. S., Park, K. B., Kim, J. T., & Na, W. B., (2005), Optimum design of Composite breakwater with Metropolis GA, 6th World Congressof Structural Multidisciplinary Optimization, Rio de Janeiro, Brazil.
  • Ryu, Y. S., Park, K. B., Kim, J. T., & Na, W. B., (2006), Development and efficiency evaluation of Metropolis GA for the structural optimization, Journal of the Computational Structural Engineering Institute of Korea, 19(1), p27-37.
  • Van Laarhoven, P. J. M., & Aarts, E. H. L., (1987), Simulated Annealing - Theory and Applications, Kluwer Academic Publishers. [https://doi.org/10.1007/978-94-015-7744-1]
  • Woo, B. H., & Park, H. S., (2003), Distributed Hybrid Genetic Algorithms for Structural Optimization, Journal of Computational Structural Engineering Institute of Korea, 16(5), p407-417.

[Fig. 1]

[Fig. 1]
Flow Chart of Metropolis Genetic Algorithm

[Fig. 2]

[Fig. 2]
Three-bar Truss

[Fig. 3]

[Fig. 3]
Design Variables for Composite Breakwater

[Fig. 4]

[Fig. 4]
Design Variables for Steel Box Girder

[Fig. 5]

[Fig. 5]
Distribution of Obtained Optima for Three-bar Truss Problem

[Fig. 6]

[Fig. 6]
Distribution of Obtained Optima for Breakwater Problem

<Table 1>

Input Data for Three-bar Truss

Input data Value
Young’s modulus 6.89Í107 kN/m2
Unit weight 0.69 kN/m3
Load 17.8 kN
Allowable stresses 34450, 137800 kN/m2
Allowable displacements 0.127Í10-3,0.127Í10-3 m
Lower bound on design variables 64.52Í10-6, 64.52Í10-6 m2
Upper bound on design variables 64.52Í10-3,64.52Í10-3 m2
Lower limit on frequency 2500 Hz

<Table 2>

Results of Three-bar Truss Example

Output SGA μGA MGA SA
x1(m2) 4.17×10-3 3.96×10-3 4.10×10-3 4.10×10-3
x2(m2) 1.73×10-3 2.52×10-3 2.00×10-3 2.00×10-3
Violation 0.0 0.0 0.0 0.0
Cost(m3) 3.47×10-4 3.49×10-4 3.4×10-4 3.46×10-4
Nopt 950 860 650 3341

<Table 3>

Results of Breakwater Example

Output SGA μGA MGA SA
x1(m) 15.92 15.43 16.10 15.87
x2(m) 6.91 6.57 6.94 6.96
x3(m) 6.66 7.10 6.63 6.88
x4(m) 8.02 8.03 8.04 8.30
x5(m) 1.00 0.99 1.00 0.99
x6(m) 5.50 5.50 5.11 5.44
Violation 0.00 0.00 0.00 0.00
Cost(m2) 422.67 429.26 421.00 421.00
Nopt 117960 4722 117240 139427
Popt 9 1 62 -

<Table 4>

Results of Box Girder Example

Span GA N x1(mm) x2(mm) x3(mm) x4(mm) x5(mm) x6(mm) x7(mm) fs(x)(N/mm) F(x) Nopt
40m SGA 5 10 14 9 0 0 160 9 890.5 1109.5 308(1540)
40 10 14 9 0 0 80 8 878.2 1121.8 75(3000)
80 10 14 9 0 0 80 8 878.2 1121.8 187(14960)
120 10 14 9 0 0 80 8 878.2 1121.8 47(5640)
μGA 5 10 14 9 0 0 80 8 878.2 1121.8 83(415)
50m SGA 5 10 21 9 0 0 80 8 1050.6 949.4 271(1355)
40 10 21 9 0 0 80 8 1050.6 949.4 92(3680)
80 10 21 9 0 0 80 8 1050.6 949.4 155(12400)
120 10 22 9 0 0 50 30 1088.5 911.5 59(7080)
μGA 5 10 21 9 0 0 80 8 1050.6 949.4 96(480)
60m SGA 5 11 28 14 0 0 0 0 1391.8 608.2 390(1950)
40 11 29 9 0 0 80 8 1272.4 727.6 492(19680)
80 11 29 9 0 0 80 8 1272.4 727.6 147(11760)
120 11 29 9 0 0 80 8 1272.4 727.6 61(7320)
μGA 5 11 29 9 0 0 80 8 1272.4 727.6 134(670)