Consider the set Sn of
permutations of {1,2,…,n} and two nxn matrices A=(a<i-j>),
B=(b<i-j>). The
Quadratic Assignment Problem with coefficient
matrices A and B, shortly denoted by QAP(A,B), can be stated as follows:
Find a permutation p of the set Sn which minimizes the
objective function Z(A,B,p), given by:
Permutation p which minimizes Z(A,B,p)
over Sn is called an optimal solution to QAP(A,B), its
corresponding value is called optimal value. The size n of the
coefficient matrices A and B is the size of QAP(A,B). If any of the
coefficient matrices A, B is symmetric, QAP(A,B) is called symmetric QAP, otherwise,
QAP(A,B) is said to be asymmetric. This formulation of QAP is called Koopmans-Beckmann QAP.
Observable characteristics of QAP
fitness landscape:
-. No "Big Valley": good solutions are scattered.
-. The distance of two good solutions can be as far as the diameter of
fitness landscape (most anchor points are quite different). When drawn
in FLST visualization, many points are almost touching the green border
and we know that the distance from left and right border is diameter of
the FL (and similarly for top and bottom border).
-. There are at least two types of QAP instances: Type "A": Uniformly generated instances, no
flow/distance dominance Type "B": Real-life like instances, strong flow/distance dominance,
many zeros
QAP
Type A,
anchor points are spread, landscape smooth. Most anchor points
are classified into one major data class only (green
triangles~>1% off best known solution)
QAP Type B,
anchor points are spread,
landscape very rugged. The anchor points are of different qualities,
very good (blue
circles~<1% off) to very bad (black
dots~>3% off)
The standard Ro-TS algorithm performs
reasonably good for type A instances. This may be because the fitness
landscape is smooth. So, most of the time, the search is traversing
areas with solution quality roughly 1%++ off from best known solution
value. The question is: can we do better?
Here, we do not see obvious solution
cycling issue (the search appears in one region at one time and another
region at another time). Note that since we do NOT record all the
points, only when the search trajectory is near some of these APs then
circles showing the search trajectory is drawn!
To attack type "A", stronger intensification is preferred,
avoid missing good solutions when the search are actually already near
the good solutions. We achieve this by lowering the tabu tenure range
used in Ro-TS. The result is a Ro-TS search that performs slightly
better than Ro-TS-I on this particular fitness landscape type.
Note that the best found solution is
always drawn in the middle of the screen, with other anchor points are
laid out w.r.t distance to this best found solution and to other APs.
Some layout errors are there but minimized using spring model layout
algorithm.
The standard Ro-TS algorithm performs very
poor on type B instances. This may be because the fitness landscape is
rugged. We observed that the search is stuck in a deep local optima most
of the time. How to fix it?
To attack type
"B", strong diversification is needed, avoid wasting time
escaping deep local optima. We perform strong diversification (but not
random restart) every time Ro-TS encountered a certain number of
iterations elapsed without improvement. The result is a Ro-TS search, a
'far' jump to another area in the fitness landscape, Ro-TS again, and
another jump, and so on. Every region is only visited briefly, but the
chance of visiting one of the good regions increased by a lot rather
than being stuck in a local optima region only.
References
These results are reported in more
details in our publications (download the local copy of those papers
here):
S. Halim, R. Yap, H.C. Lau. An Integrated White+Black Box Approach for
Designing and Tuning Stochastic Local Search.
In Principles and Practice of Constraint Programming (CP
2007, Providence, Rhode Island, USA, September 23-27, 2007):
332-347
S. Halim, R. Yap.
Designing and Tuning SLS through Animation and Graphics: an
Extended Walk-through.
In Engineering Stochastic Local Search Workshop (SLS
2007, Brussels, Belgium, September 6-8, 2007): 16-30
This document, results_qap.html, has been accessed 235 times since 25-Jun-24 11:57:13 +08.
This is the 2nd time it has been accessed today.
A total of 71 different hosts have accessed this document in the
last 151 days; your host, 3.22.249.229, has accessed it 1 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.