Geoscience Reference
In-Depth Information
(b) If the offspring is different from all population members, the offspring
replaces the worst population member.
5. Set g D g C 1.Ifg G go to Step 2.
6. Otherwise (g D G C 1), stop with the best population member as the final
solution.
Many modifications for such a simple framework have been proposed. For example,
Schaffer et al. ( 1989 ), Drezner and Marcoulides ( 2003 ), Fox and McMahon ( 1991 ),
Wu and Ji ( 2008 ), Drezner and Drezner ( 2006 ), Misevicius ( 2008 ), Drezner ( 2005a ),
and CantĂș-Paz ( 2001 ).
An important component for the success of genetic algorithms is the crossover
operator. The following crossover operator, suggested by Drezner ( 2003 ), exploits
the structure of the problem and works well when distances are life-like distances
such as Manhattan or Euclidean distances. When problems are randomly generated
like the Taia instances (Taillard 1991 ) it may not work well. Two parents are to be
merged to produce an offspring. In Drezner ( 2003 ) the following crossover operator
is repeated for all n facilities considered separately as pivot sites. The best merged
offspring is selected for the local search heuristic. The merge of the two selected
parents for one pivot site is as follows:
1. The median distance from the pivot site to all sites is calculated.
2. A site that is closer than the median to the pivot site is assigned the facility located
there in the first parent.
3. All other sites are assigned a facility from the second parent.
4. It is possible that some facilities are assigned twice. The same number of facilities
are not assigned at all. Therefore,
(a) Go over all the facilities from left to right and create a list of unassigned
facilities.
(b) Find all facilities that are assigned twice, and replace the site that is farther
than the median (i.e., from the second parent) with a facility that is not
assigned at all.
Drezner ( 2003 ) applied the concentric tabu search (Drezner 2002 ) as the local
search heuristic. Drezner ( 2008a ) found that the modified robust tabu (applying only
the short term memory) performed better as a local search heuristic.
13.7
Test Problem Instances
There are many test problems instances listed in the web-site QAPLIB. Commonly
used sets of test problem instances for evaluating the effectiveness of algorithms are
listed in Table 13.1 .
Note that if at least one of the sets of weights or distances is symmetric, the
problem can be formulated as a symmetric problem. Suppose that d ij D d ji .Define
Search WWH ::




Custom Search