31-10-2016, 03:59 PM
Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems
1462601271-1.pdf (Size: 731.52 KB / Downloads: 14)
Abstract In this study, a new metaheuristic optimization
algorithm, called cuckoo search (CS), is introduced for
solving structural optimization tasks. The new CS algorithm
in combination with Le´vy flights is first verified using a
benchmark nonlinear constrained optimization problem. For
the validation against structural engineering optimization
problems, CS is subsequently applied to 13 design problems
reported in the specialized literature. The performance of the
CS algorithm is further compared with various algorithms
representative of the state of the art in the area. The optimal
solutions obtained by CS are mostly far better than the best
solutions obtained by the existing methods. The unique
search features used in CS and the implications for future
research are finally discussed in detail.
Introduction
Most design optimization problems in structural engineering
are highly nonlinear, involving many different design variables under complex constraints. These constraints can
be written either as simple bounds such as the ranges of
material properties or as nonlinear relationships including
maximum stress, maximum deflection, minimum load
capacity, and geometrical configuration. Such nonlinearity
often results in multimodal response landscape. Subsequently,
local search algorithms such as hill-climbing and
Nelder-Mead downhill simplex methods are not suitable;
only global algorithms should be used so as to obtain
optimal solutions [1].
Metaheuristic algorithms can be defined as upper level
general methodologies (templates) that can be used as
guiding strategies in designing underlying heuristics to
solve specific optimization problems [2]. Two important
characteristics of metaheuristics are intensification and
diversification [3]. Intensification intends to search around
the current best solutions and select the best candidates or
solutions. Diversification makes sure that the algorithm
can explore the search space more efficiently, often by
randomization.
Modern metaheuristic algorithms have been developed
with an aim to carry out global search with three main
purposes: solving problems faster, solving large problems,
and obtaining robust algorithms [2]. Genetic algorithms
(GA) and particle swarm optimization (PSO) are typical
examples of these algorithms. The efficiency of metaheuristic
algorithms can be attributed to the fact that they
imitate the best features in nature, especially the selection
of the fittest in biological systems which have evolved by
natural selection over millions of years. Timeline of main
metaheuristic algorithms is shown in Fig. 1.
As shown in Fig. 1, cuckoo search (CS) is a new
metaheuristic search algorithm. This algorithm is based on
the obligate brood parasitic behavior of some cuckoo
species in combination with the Le´vy flight behavior of some birds and fruit flies. It is developed by Yang and Deb
[4] and the preliminary studies show that it is very promising
and could outperform existing algorithms such as GA
and PSO [4]. In this paper, the CS algorithm is further
validated against various structural engineering optimization
problems including stochastic test functions. The
introduced search strategy is compared with other popular
optimization algorithms. Finally, the unique features of CS
are discussed and topics for further studies are proposed.
Cuckoo breeding behavior
Cuckoos are fascinating birds, not only because of the
beautiful sounds they can make, but also because of their
aggressive reproduction strategy. Some species such as the
ani and guira cuckoos lay their eggs in communal nests,
though they may remove others’ eggs to increase the
hatching probability of their own eggs [5]. Quite a number
of species engage the obligate brood parasitism by laying
their eggs in the nests of other host birds (often other
species). There are three basic types of brood parasitism:
intraspecific brood parasitism, cooperative breeding, and
nest takeover. Some host birds can engage direct conflict
with the intruding cuckoos. If a host bird discovers the eggs
are not its own, it will either throw these alien eggs away or
simply abandon its nest and build a new nest elsewhere.
Some cuckoo species such as the new world brood-parasitic
Tapera have evolved in such a way that female parasitic
cuckoos are often very specialized in the mimicry in
color and pattern of the eggs of a few chosen host species
[5]. This reduces the probability of their eggs being
abandoned and thus increases their reproductively.
Furthermore, the timing of egg-laying of some species is
also amazing. Parasitic cuckoos often choose a nest where
the host bird just laid its own eggs. In general, the cuckoo
eggs hatch slightly earlier than their host eggs. Once the
first cuckoo chick is hatched, the first instinctive action it
will take is to evict the host eggs by blindly propelling the eggs out of the nest, which increases the cuckoo chick’s
share of food provided by its host bird [5]. Studies also
show that a cuckoo chick can also mimic the call of host
chicks to gain access to more feeding opportunity.
2.2 Le´vy flights
In nature, animals search for food in a random or quasirandom
manner. In general, the foraging path of an animal
is effectively a random walk because the next move is
based on the current location/state and the transition
probability to the next location. Which direction it chooses
depends implicitly on a probability which can be modeled
mathematically. For example, various studies have shown
that the flight behavior of many animals and insects
has demonstrated the typical characteristics of Le´vy flights
[6, 7].
A recent study by Reynolds and Frye [8] shows that fruit
flies or Drosophila melanogaster explore their landscape
using a series of straight flight paths punctuated by a
sudden 90o turn, leading to a Le´vy-flight-style intermittent
scale-free search pattern. Studies on human behavior such
as the Ju/’hoansi hunter-gatherer foraging patterns also
show the typical feature of Le´vy flights. Even light can be
related to Le´vy flights [9]. Subsequently, such behavior
has been applied to optimization and optimal search, and
preliminary results show its promising capability
Cuckoo search
For simplicity in describing the new CS method [4], we
now use the following three idealized rules:
• Each cuckoo lays one egg at a time, and dumps it in a
randomly chosen nest.
• The best nests with high quality of eggs (solutions) will
carry over to the next generations.
• The number of available host nests is fixed, and a host
can discover an alien egg with a probability Pa [ [0, 1].
In this case, the host bird can either throw the egg away
or abandon the nest so as to build a completely new nest
in a new location.
For simplicity, this last assumption can be approximated
by a fraction Pa of the n nests being replaced by new nests
(with new random solutions at new locations). For a
maximization problem, the quality or fitness of a solution
can simply be proportional to the objective function. Other
forms of fitness can be defined in a similar way to the
fitness function in GA.
Based on these three rules, the basic steps of the CS can
be summarized as the pseudo code as follows:
When generating new solutions x(t?1) for, say cuckoo i,
a Le´vy flight is performed