Memetic Algorithms

Memetic algorithms are hybrid algorithms in which EAs are integrated with a local search. In these algorithms, EAs are usually used for global exploration of the search space while fine-tuning of solutions is conducted by the local search. MAs have largely emerged in the late 1980s and early 1990s (Moscato, 1989) with the progress in the field of evolutionary computation and improved understanding of the dynamics of evolutionary algorithms. Some earlier studies on hybrid optimization methods utilizing EAs were also reported in the literature, e. g., a hybrid of evolution strategies (Rechenberg, 1973) and linear programming for topology optimization of trusses (Hoeffler et al., 1973).

The overall structure of a canonical MA is presented in Figure 1. It is a slightly modified version of a simple MA presented in (Hart et al., 2005a). Figure 1 shows that the differences between EAs and MAs occur at point 6. In the case of a MA, additional local search is conducted to improve (fine- tune) new individuals generated by an EA in steps 3-5.

This canonical algorithm structure can be instantiated in many different ways. Depending on the type of EA used (e. g., a genetic algorithm (GA) (Holland, 1975), evolution strategies (ES) (Rechenberg, 1973), etc.) and the type of local search (e. g., steepest ascent/descent, greedy search, etc.) different hybrids can be created. In this way, each component of the MA can be adjusted to a specific problem, or a class of problems. Current state-of-the-art review in this field can be found in (Hart et al., 2005b).

MAs have also been applied to solve several structural design problems. Hoeffler et al. (1973) combined linear programming and ES to optimize topologies of truss systems. Linear programming methods were applied to identify initial truss layout and ES were subsequently used to determine optimal positions of joints. This hybrid strategy resulted in reduced total weight of trusses when compared to results obtained using sole linear programming methods. Sakamoto and Oda (1993)

1. Initialize the population

2. Evaluate all members of the population

While the termination condition is not satisfied

{

3. Select individual(s) in the population to be parent(s)

4. Create new individuals by applying the variation operators to the copies of parent(s)

5. Evaluate new individuals

6. Improve individuals using local search

7. Replace some/all of the individuals in the current population with the new individuals

}

Figure 1: Structure of a canonical memetic algorithm

applied a MA composed of a GA and the generalized optimality criterion method to optimize topologies and cross-sections of members in trusses. As before, minimum weight truss systems were sought subject to displacement constraints. At about the same time, Adeli and Cheng (1993) proposed a hybrid algorithm for the optimization of space truss structures. In this case, a GA combined with penalty-function method produced optimal solutions faster than a standard GA.

In the experiments reported in this paper, evolutionary algorithms were combined with a continuous/discrete optimization algorithm implemented in SODA (Grierson, 1989) to optimize topologies and cross-sections of members in steel structural systems of tall buildings. Extensive sensitivity analyses of evolutionary computation parameters were also conducted to determine their optimal settings for structural design experiments.