World of Seven - Viz: SLS Engineering Suite

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)

Some observable Ro-TS behavior:

1. Ro-TS-I (vdf) on tai35a (QAPLIB)

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!

2. Ro-TS-A (vdf) on tai35a (QAPLIB)

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.

3. Ro-TS-I (vdf) on tai35b (QAPLIB)

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?

4. Ro-TS-B (vdf) on tai35b (QAPLIB)

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.

These results are reported in more details in our publications (download the local copy of those papers here):

Results on Quadratic Assignment Problem