Geoscience Reference
In-Depth Information
back to a site they were removed from in the last t iterations. The best solutions
found by Taillard (
1991
) were obtained considering the tabu tenure t randomly
generated in Œ0:9n;1:1n in every iteration.
Long Term Memory: Every iteration after x iterations (for example, x
D
3n
2
): if
there is an exchange between two facilities such that one facility moves to a site
it was never there in the last x iterations, such an exchange preempts any other
exchange and is executed. The long term memory serves as a diversification of
the tabu search.
The robust tabu search approach proposed by Taillard (
1991
) was improved by
Drezner (
2008a
) who suggested a small change of the tabu tenure by selecting it
randomly in the range Œ0:2n;1:8n (rather than Œ0:9n;1:1n) in each iteration.
The “reactive tabu search” was proposed by Battiti and Tecchiolli (
1994
). The
“concentric tabu search” was proposed in Drezner (
2002
) and extended in Drezner
(
2005b
). Various tabu searches approaches were proposed and computationally
tested in Misevicius and Blonskis (
2005
) and Misevicius et al. (
2006
). The iterated
tabu search was proposed by Misevicius (
2012
).
Many versions of genetic algorithms which are inspired by biological evolution
and survival of the fittest (Holland
1975
; Drezner and Drezner
2005
) have also been
proposed for the QAP. The first two papers are due to Fleurent and Ferland (
1994
)
and Tate and Smith (
1995
). Other works investigating this type of algorithm include
Misevicius (
2008
), Wu and Ji (
2008
), Ahuja et al. (
2000
).
The most successful heuristic algorithms seem to be the hybrid genetic algo-
rithms (Drezner
2003
,
2008a
;Misevicius
2004
,
2005
;Misevicius and Rubliauskas
2009
;Misevicius et al.
2009
;Misevicius and Guogis
2012
). For a review of the
application of such heuristic algorithms for the solution of the QAP see Drezner and
Misevicius (
2013
). Hybrid genetic algorithms apply a local search on the generated
offspring before considering its inclusion into the population. Two parameters are
given: the population size P and the number of generations G. A specific local
search, such as tabu search, is selected. The general framework of a simple hybrid
genetic algorithms is the following:
1. A starting population of size P is randomly selected, and the local search
heuristic is applied on each starting population member. The current generation
number is set to g
D
1.
2. Two population members are randomly selected and merged by a crossover
operator to produce an offspring.
3. The local search heuristic is applied to the merged solution, possibly improving
it.
4. If the value of the offspring's objective function is not better than the worst
population member's objective function, the offspring is ignored and go to Step 5.
Else,
(a) If the offspring is identical to an existing population member, it is ignored.
Go to Step 5.
