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

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.

1. Three-bar Truss

A symmetric 3-bar truss is shown in [Fig. 2] Cross-sectional areas(x₁, x₂, x₃) 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;

2. Composite Breakwater

A composite breakwater consists of upright structure(A_u) and foundation or rubble mound which is again composed of core(A_c) and revetments(A_rl, A_rw). 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 (c_u, c_c, c_rw, c_rl);

[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(x₁), lower flange thickness(x₂), web thickness(x₃), projecting width of longitudinal compression stiffeners(x₄), thickness of longitudinal compression stiffeners(x₅), projecting width of longitudinal web stiffeners(x₆), and thickness of longitudinal web stiffeners(x₇). 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, f_c(x), is expressed as the thickness, T, itself. The cost function for the steel box girder, f_s(x), is formulated as the weight per unit length of the girder. Here, W_s is the unit weight of the steel and A_s is the area of the girder section.

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).

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.

<Table 1>

Input Data for Three-bar Truss

The results are presented in <Table 2>, where N_opt is the number of function evaluations to reach the optimum. As shown in the table, MGA yields the best solution with the minimal N_opt. 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(P_opt) are 100% in MGA, 91% in SGA, and 43% in μGA, respectively. This shows the global convergence property and reliability of MGA.

<Table 2>

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(x₁~x₆) 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 P_opt is the probability to obtain the best optima shown in the corresponding column.

<Table 3>

Results of Breakwater Example

The distribution of optima in 100 trials is shown in [Fig. 6]. The probability to obtain the best solution(P_opt) 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, x₀=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.

<Table 4>

Results of Box Girder Example