\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A parallel water flow algorithm with local search for solving the quadratic assignment problem

  • * Corresponding author: Trung Hieu Tran

    * Corresponding author: Trung Hieu Tran
Abstract Full Text(HTML) Figure(4) / Table(9) Related Papers Cited by
  • In this paper, we adapt a nature-inspired optimization approach, the water flow algorithm, for solving the quadratic assignment problem. The algorithm imitates the hydrological cycle in meteorology and the erosion phenomenon in nature. In this algorithm, a systematic precipitation generating scheme is included to increase the spread of the raindrop positions on the ground to increase the solution exploration capability of the algorithm. Efficient local search methods are also used to enhance the solution exploitation capability of the algorithm. In addition, a parallel computing strategy is integrated into the algorithm to speed up the computation time. The performance of the algorithm is tested with the benchmark instances of the quadratic assignment problem taken from the QAPLIB. The computational results and comparisons show that our algorithm is able to obtain good quality or optimal solutions to the benchmark instances within reasonable computation time.

    Mathematics Subject Classification: Primary: 90C27, 90B80; Secondary: 68W10.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  An example of solution representation in the WFA for the QAP.

    Figure 2.  The erosion process in exploitation phase of the WFA.

    Figure 3.  Flow chart of the WFA for the QAP.

    Figure 4.  Comparison of the WFA with other algorithms on (a). Average percentage difference; and (b). The number of the best known solutions obtained.

    Table 1.  A summary of state-of-the-art metaheuristic algorithms for solving the QAP.

    Metaheuristic algorithms No. of best known solutions found / No. of tested instances Average difference Maximum difference Maximum size of instance Drawbacks
    Simulated annealing [37] 26 / 40 0.99% 11.51%
    (chrxxx instance)
    30 Solving QAP relaxation to construct initial solution for simulated annealing depends on the capability of solvers used [37]. Thus, the algorithm may not solve instances of size $n>30$ effectively or extensive computation time may be required.
    Ant system [24] 33 / 44 0.28% 2.79%
    (chrxxx instance)
    40 Computation time of local search is rather onerous [24], and thus does not solve instances of size $n>40$ efficiently.
    Population based hybrid ant system [28] 80 / 110 0.41% 14.25%
    (chrxxx instance)
    100 Population size increases significantly according to instance size [28], leading to difficulty for solving large instances.
    Greedy genetic algorithm [2] 58 / 87 0.17% 5.13%
    (chrxxx instance)
    100 Although greedy approach improves the quality of individuals, this may affect the overall performance of the genetic algorithm [2]. In addition, using 2-exchange local search could limit the capability for searching better solutions.
    Greedy randomized adaptive search procedure [22] 27 / 44 0.69% 4.64%
    (chrxxx instance)
    128 The algorithm can be applied only to symmetric QAP instances [2].
    Iterated fast local search [29] 72 / 130 0.87% 20.33%
    (lipaxxx instance)
    256 2-opt local search of the algorithm could not solve lipaxxx instances of the QAPLIB effectively [29] due to limit in search space.
    Hybrid genetic algorithm [23] 84 / 130 0.51% 16.56%
    (lipaxxx instance)
    256 2-gene exchange local search could not solve lipaxxx instances of the QAPLIB effectively [23] due to limit in search space.
     | Show Table
    DownLoad: CSV

    Table 2.  The parameter sets of the WFA for the QAP benchmark instances.

    Benchmarks $n$ Parameter values
    MaxCloud MaxPop MaxUIE MinEro
    Burkard 26 5 16 10 2
    Christofides 12 - 20 10 16 10 2
    22 15 16 10 2
    25 20 16 10 2
    Elshafei 19 10 16 10 2
    Eschermann 16, 64 2 8 5 2
    32 (a, b) 5 16 10 2
    32 (c, e, g) 2 8 5 2
    32 (d, h) 2 16 10 2
    128 5 16 5 3
    Hadley 12 - 20 10 16 10 2
    Krarup 30, 32 20 16 10 2
    Li & Pardalos 20, 30 10 16 10 2
    40, 50, 60 10 24 10 2
    70 10 24 15 2
    80, 90 20 24 10 2
    Nugent 12 - 28 10 16 5 2
    30 20 16 10 2
    Roucairol 12, 15 5 16 10 2
    20 10 24 10 2
    Scriabin 12, 15, 20 5 16 10 2
    Skorin-Kapov 42 - 64 15 16 10 2
    72, 81, 90 10 24 15 2
    100 10 16 10 2
    Steinberg 36 20 16 10 2
    Taillard
     (Taixxxa) 12 5 16 10 2
    15, 17 5 24 10 2
    20 - 35 20 24 10 2
    40, 50 20 24 15 2
    60, 80,100 10 24 10 2
     (Taixxxb) 12 - 20 5 8 10 2
    25 10 16 10 2
    30, 35, 40 20 16 10 2
    50, 60, 80 10 16 15 2
    100 5 24 10 2
    150 5 16 5 2
     (Taixxxc) 64 10 24 10 2
    256 2 8 5 2
    Thonemann 30 10 24 10 2
    40 20 16 10 2
    150 5 16 10 2
    Wilhelm 50 15 24 10 2
    100 10 16 10 2
     | Show Table
    DownLoad: CSV

    Table 3.  Comparison results of the WFA with other algorithms for Burkard's and Christofides' instances

    Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
    Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
    Bur26a 5426670 5426670 30.0 0 30.0 0 11.38 0 21.07 0 235 0 125 0 61.27 - - 0
    Bur26b 3817852 3817852 23.0 0 23.0 0 59.45 0 35.03 0 225 0 9.5 0 60.27 - - 0
    Bur26c 5426795 5426795 16.0 0 16.0 0 5.16 0 19.09 0 227 0 7.42 0 57.78 - - 0
    Bur26d 3821225 3821225 29.0 0 29.0 0 15.12 0 19.40 0 213 0 8.42 0 61.27 - - 0
    Bur26e 5386879 5386879 32.0 0 32.0 0 17.63 0 20.53 0 218 0 10.03 0 57.83 - - 0
    Bur26f 3782044 3782044 44.0 0 44.0 0 5.05 0 11.23 0 104 0 6.68 0 59.19 - - 0
    Bur26g 10117172 10117172 26.0 0 26.0 0 22.58 0 18.67 0 194 0 9.99 0 57.72 - - 0
    Bur26h 7098658 7098658 20.0 0 20.0 0 37.58 0 5.67 0 204 0 6.82 0 57.47 - - 0
    Chr12a 9552 9552 0.6 0 0.6 - - - - 0 19.6 0 0.54 0 1.09 0 40 0
    Chr12b 9742 9742 0.5 0 0.5 - - - - 0 18.4 0 0.42 0 1.11 0 41 0
    Chr12c 11156 11156 0.6 0 0.6 - - - - 0 20.2 0 1.29 0 1.02 0.26 38 0.27
    Chr15a 9896 9896 3.2 0 3.2 - - - - 0.4 40.6 0 1.50 0 2.97 0 69 0
    Chr15b 7990 7990 4.1 0 4.1 - - - - 0 41.8 0 1.31 0 3.08 2.7 72 0
    Chr15c 9504 9504 4.0 0 4.0 - - - - 0 44 0 1.30 0 2.64 11.5 69 6.36
    Chr18a 11098 11098 9.3 0 9.3 - - - - 0.4 79 0 2.11 5.14 7.23 1.71 103 14.25
    Chr18b 1534 1534 10.2 0 10.2 - - - - 0 78.8 0 2.62 0 5.30 0 105 0
    Chr20a 2192 2192 32.0 0 32.0 1.82 509 0 331 0 94.6 0.18 3.61 4.38 10.95 0 131 1.82
    Chr20b 2298 2298 27.0 0 27.0 5.92 195 2.79 375 5.13 96.4 3.12 3.32 5.40 8.61 0 127 4.96
    Chr20c 14142 14142 15.0 0 15.0 0.00 9.23 0 29.49 0 97.8 4.51 1.77 0 13.55 0 140 0
    Chr22a 6156 6156 60.0 0 60.0 2.31 201 0 315 0.75 146 0 4.52 0.88 19.11 5.7 164 0.32
    Chr22b 6194 6194 58.0 0 58.0 2.58 213 0.97 162 0 152 1.46 5.26 1.68 17.00 8.5 163 0
    Chr25a 3796 3796 95.0 0 95.0 2.32 115 0 236 0 194 2.27 5.97 11.17 33.59 0 591 0
     | Show Table
    DownLoad: CSV

    Table 4.  Comparison results of the WFA with other algorithms for Elshafei's, Eschermann's, Hadley's, and Krarup's instances.

    Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
    Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
    Els19 17212548 17212548 15 0 15 - - - - 0 80.6 0 44.46 - - - - 0
    Esc16a 68 68 0.1 0 0.1 - - - - 0 47.4 0 5.13 0 3.17 0 61 0
    Esc16b 292 292 0.1 0 0.1 - - - - 0 48.2 0 0.19 0 2.75 0 60 0
    Esc16c 160 160 0.1 0 0.1 - - - - 0 53.4 0 0.44 0 4.03 0 68 0
    Esc16d 16 16 0.1 0 0.1 - - - - 0 53.2 0 0.50 0 3.98 - - 0
    Esc16e 28 28 0.1 0 0.1 - - - - 0 46.8 0 0.32 0 2.28 - - 0
    Esc16f 0 0 0.1 0 0.1 - - - - 0 46.0 - - 0 1.11 - - 0
    Esc16g 26 26 0.1 0 0.1 - - - - 0 49.8 0 0.29 0 2.77 - - 0
    Esc16h 996 996 0.1 0 0.1 - - - - 0 48.0 0 0.22 0 2.13 0 65 0
    Esc16i 14 14 0.1 0 0.1 - - - - 0 51.6 0 0.16 0 2.05 - - 0
    Esc16j 8 8 0.1 0 0.1 - - - - 0 402 0 0.32 0 2.91 - - 0
    Esc32a 130 130 190 0 190 1.54 7.03 0 226 0 382 1.52 97.04 0 137 - - 0
    Esc32b 168 168 53 0 53 0 2.80 0 40.59 0 400 0 33.61 0 110 - - 0
    Esc32c 642 642 1.2 0 1.2 0 0 0 0.08 0 389 0 2.01 0 54.7 - - 0
    Esc32d 200 200 11 0 11 0 1.92 0 2.13 0 353 0 2.76 0 74.3 - - 0
    Esc32e 2 2 0.8 0 0.8 0 0 0 0.05 0 370 0 0.66 0 46.09 - - 0
    Esc32g 6 6 0.9 0 0.9 0 0 0 0.07 0 371 0 1.27 0 28.41 - - 0
    Esc32h 438 438 31 0 31 0 3.41 0 2.64 0 349 0 6.54 0 85.75 - - 0
    Esc64a 116 116 9.6 0 9.6 - - - - 0 2631 0 194 0 1522 - - 0
    Esc128 64 64 1395 0 1395 - - - - - - 0 1631 - - - - 0
    Had12 1652 1652 0.7 0 0.7 - - - - - - 0 4.27 0 0.97 0 41 0
    Had14 2724 2724 1.5 0 1.5 - - - - - - 0 10.25 0 1.97 0 64 0
    Had16 3720 3720 2.2 0 2.2 - - - - - - 0 5.38 0.05 3.64 0 88 0
    Had18 5358 5358 4.9 0 4.9 - - - - - - 0 18.54 0 6.52 0 118 0
    Had20 6922 6922 11.2 0 11.2 0 2.8 0 159 - - 0 15.26 0 10.58 0 148 0
    Kra30a 88900 88900 430 0 430 0 292 0 199 0 301 0.89 71 1.34 106 - - 0
    Kra30b 91420 91420 441 0 441 0.32 268 0 140 0 331 0 123 0.13 102 - - 0.08
    Kra32 88700 88700 432 0 432 - - - - - - - - 0 172 - - 0
     | Show Table
    DownLoad: CSV

    Table 5.  Comparison results of the WFA with other algorithms for Li & Pardalos' and Skorin-Kapov's instances.

    Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
    Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
    Lipa20a 3683 3683 14 0 14 0 0.99 0 107 0 74.8 0 0.59 0 16.11 - - 0
    Lipa20b 27076 27076 16 0 16 0 0.66 0 0 0 74.4 0 0.39 0 16.78 - - 0
    Lipa30a 13178 13178 75 0 75 0 46.43 0 54.85 0 345 0 5.66 0 120 - - 0.99
    Lipa30b 151426 151426 73 0 73 0 7.31 0 0 0 337 0 2.78 0 122 - - 0
    Lipa40a 31538 31538 655 0 655 1.13 306 1.02 281 0.96 1022 0 19.46 0 490 - - -
    Lipa40b 476581 476581 430 0 430 0 6.21 0 0 0 1026 0 9.52 0 486 - - -
    Lipa50a 62093 62619 872 0.80 971 - - - - 0.95 1486 0.82 57.32 1.02 1556 - - 0
    Lipa50b 1210244 1210244 777 0 777 - - - - 0 1509 0 39.96 0 1462 - - 0
    Lipa60a 107218 108103 1337 0.79 2754 - - - - 0.77 3057 0.64 137 0.84 3668 - - 0.81
    Lipa60b 2520135 2520135 893 0 893 - - - - 0 3047 0 86.13 0 3724 - - 0
    Lipa70a 169755 170956 1714 0.71 1744 - - - - 0.71 6148 0.62 233 0.77 8067 - - -
    Lipa70b 4603200 4603200 1771 0 1771 - - - - 0 6123 15.9 196 0 7762 - - -
    Lipa80a 253195 254853 2254 0.63 3467 - - - - 0.61 9519 0.61 373 0.67 15220 - - -
    Lipa80b 7763962 7763962 2511 0 2511 - - - - 0 9499 16.56 332 20.33 15965 - - -
    Lipa90a 360630 362854 2562 0.57 5678 - - - - 0.58 12358 0.54 592 0.63 27909 - - -
    Lipa90b 12490441 12490441 5034 0 5034 - - - - 0 12319 0 503 0 27788 - - -
    Sko42 15812 15836 1042 0.03 1547 - - - - 0.25 1006 0.35 365 0.30 614 - - 0
    Sko49 23386 23510 1098 0.32 1772 - - - - 0.21 1252 0.19 714 0.45 1318 - - 0.05
    Sko56 34458 34568 1064 0.20 1742 - - - - 0.02 2976 0.06 907 0.47 2613 - - 0.12
    Sko64 48498 48796 1178 0.31 2770 - - - - 0.22 3788 0.09 1399 0.25 4936 - - 0
    Sko72 66256 66660 1620 0.47 4096 - - - - 0.29 5078 0.21 1987 0.73 8663 - - 0.03
    Sko81 90998 91452 1520 0.50 1655 - - - - 0.20 10964 0.12 2680 0.43 16960 - - 0.05
    Sko90 115534 116922 1625 0.91 4053 - - - - 0.27 12698 0.43 3822 0.45 28787 - - 0.02
    Sko100a 152002 153426 1905 0.94 1907 - - - - 0.21 16608 0.22 1486 1.30 309 - - 0.19
    Sko100b 153890 155288 1494 0.85 1577 - - - - 0.14 14729 0.30 1405 2.34 274 - - -
    Sko100c 147862 149628 1525 1.15 1786 - - - - 0.20 20314 0.06 873 1.50 284 - - -
    Sko100d 149576 151196 1666 0.97 3978 - - - - 0.17 20302 0.27 863 1.03 293 - - -
    Sko100e 149150 151056 2423 0.90 5415 - - - - 0.24 21127 0.33 745 1.55 301 - - -
    Sko100f 149036 150510 2038 0.91 2125 - - - - 0.29 21479 0.41 781 0.73 285 - - -
     | Show Table
    DownLoad: CSV

    Table 6.  Comparison results of the WFA with other algorithms for Nugent's, Roucairol's, Scriabin's, Steinberg's, Thonemann's, and Wilhelm's instances.

    Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
    Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
    Nug12 578 578 0.5 0 0.5 - - - - 0 19 0 6.84 0 1.41 0 36 0
    Nug14 1014 1014 0.8 0 0.8 - - - - - - 0 7.71 0.39 3.11 - - 0.2
    Nug15 1150 1150 5.8 0 5.8 - - - - 0 41.4 0 8.3 0 4.02 0 73 0
    Nug16a 1610 1610 4.1 0 4.1 - - - - - - 0 11.24 0 5.59 - - 0
    Nug16b 1240 1240 4.7 0 4.7 - - - - - - 0 11.02 0 5.59 - - 0
    Nug17 1732 1732 5.7 0 5.7 - - - - - - 0 11.95 0 7.31 - - 0
    Nug18 1930 1930 7.9 0 7.9 - - - - - - 0.31 13.56 0 9.55 - - 0
    Nug20 2570 2570 15.7 0 15.7 0 2.53 0 119 0 97.8 0 20.73 0 16.06 0 132 0
    Nug21 2438 2438 27.5 0 27.5 - - - - - - 0 29.80 0 20.63 - - 0
    Nug22 3596 3596 26.5 0 26.5 - - - - - - 0 43.82 0 25.84 - - 0
    Nug24 3488 3488 39.7 0 39.7 - - - - - - 0 33.83 0 39.75 - - 0.06
    Nug25 3744 3744 38.5 0 38.5 - - - - - - 0 42.10 0 47.66 - - 0
    Nug27 5234 5234 51.8 0 51.8 - - - - - - - - 0 80.56 - - 0
    Nug28 5166 5166 57.5 0 57.5 - - - - - - - - 0.12 98.33 - - 0
    Nug30 6124 6124 136.1 0 136.1 0.42 523 0 181 0.07 354 0.42 109 2.12 117 0.06 887 0.07
    Rou12 235528 235528 0.5 0 0.5 - - - - 0 19.6 0 0.30 0 1.06 0 35 0
    Rou15 354210 354210 1.1 0 1.1 - - - - 0 34.6 0 0.56 0 2.95 0.71 71 0
    Rou20 725522 725522 12.2 0 12.2 0 165 0 245 0.16 75.2 0 1.43 0.02 11.73 0.06 127 0
    Scr12 31410 31410 0.7 0 0.7 - - - - 0 18.8 0 0.44 0 1.11 0 38 0
    Scr15 51140 51140 1.0 0 1.0 - - - - 0 35.2 0 0.42 0 3.09 0 78 0
    Scr20 110030 110030 5.4 0 5.4 0 157 0 46.1 0 79.6 0 1.57 0 12.69 2.13 137 0
    Ste36a 9526 9526 623.5 0 623.5 1.81 276 0.76 295 0.27 710 0 221 0 204 - - -
    Ste36b 15852 15852 763.2 0 763.2 0.92 180 0.25 213 - - 0 235 3.43 222 - - -
    Ste36c 8239110 8239110 800.4 0 800.4 0.89 142 0.33 321 - - 0 24.07 - - - - -
    Tho30 149936 149936 306.2 0 306.2 0 216 0 288 0 396 0 132 0.29 119 - - -
    Tho40 240516 240620 823.1 0.04 823.1 1.17 184 0.66 312 0.32 958 0.05 344 0.53 502 - - -
    Tho150 8133398 8238058 4590.3 1.29 4590.3 - - - - - - 0.41 729 - - - - -
    Wil50 48816 48916 829.8 0.06 2522.3 - - - - 0.07 2115 0 695 0.28 1499 - - -
    Wil100 273038 274446 3330.7 0.34 5272.6 - - - - 0.2 20544 0.15 1252 0.27 51121 - - -
     | Show Table
    DownLoad: CSV

    Table 7.  Comparison results of the WFA with other algorithms for Taillard's instances.

    Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
    Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
    Tai12a 224416 224416 0.3 0 0.3 - - - - - - 0 0.18 0 1.05 0 35 0
    Tai12b 39464925 39464925 0.2 0 0.2 - - - - - - 0 0.62 0 1.03 0.03 53 0
    Tai15a 388214 388214 2.0 0 2.0 - - - - - - 0 0.69 0 2.99 0.39 73 0.01
    Tai15b 51765268 51765268 0.8 0 0.8 - - - - - - 0 0.70 0 3.05 0.47 77 0
    Tai17a 491812 491812 4.0 0 4.0 - - - - - - 0.55 0.96 0.38 5.55 0 86 0.56
    Tai20a 703482 703482 175.5 0 175.5 0 484 0 160 - - 0.84 1.38 0.47 11.42 0.21 124 0.8
    Tai20b 122455319 122455319 4.8 0 4.8 - - - - - - 0 2.70 0 12.52 5.6 167 0
    Tai25a 1167256 1169030 236.4 0 1514.3 1.43 355 0.55 206 - - 0.77 3.27 2.00 33.03 - - 1.57
    Tai25b 344355646 344355646 70.6 0 70.6 - - - - - - 0 3.77 5.59 35 - - 0
    Tai30a 1818146 1832590 437.2 0.57 546.7 1.58 265 1.46 332 - - 1.34 6.72 1.11 83.06 - - 1.37
    Tai30b 637117113 637117113 633.8 0 633.8 - - - - - - 0 14.11 2.22 81 - - 0
    Tai35a 2422002 2436540 550.9 0.59 1288.4 1.90 531 1.64 232 - - 1.29 12.09 1.24 177 - - 1.3
    Tai35b 283315445 283315445 1032.5 0 1032.5 - - - - - - 0 23.90 3.54 186 - - 0.19
    Tai40a 3139370 3160484 886.1 0.67 886.1 2.20 325 2.05 253 - - 1.08 18.37 1.85 354 - - 1.7
    Tai40b 637250948 637250948 1217 0 1217 - - - - - - 0 36.95 5.60 328 - - 0
    Tai50a 4938796 5031472 1113 1.46 2323 - - - - - - 1.31 58.21 2.25 1104 - - 2.48
    Tai50b 458821517 458926056 1592 0.02 1592 - - - - - - 0 64.77 0.42 1032 - - 0
    Tai60a 7205962 7342990 2165 1.55 3142 - - - - - - 1.79 104 2.75 2740 - - 2.37
    Tai60b 608215054 612153786 1866 0.65 1866 - - - - - - 0 148 0.47 2621 - - 0.02
    Tai64c 1855928 1855928 1325 0 1325 - - - - - - 0 28.96 0.03 237 - - 0
    Tai80a 13511780 13821180 2100 1.87 5707 - - - - - - 1.41 360 2.46 11333 - - 2.37
    Tai80b 818415043 827982667 3434 1.17 3434 - - - - - - 0.03 424 2.79 10533 - - 0
    Tai100a 21052466 21538854 2450 1.76 8120 - - - - - - 1.29 785 2.33 35781 - - -
    Tai100b 1185996137 1198498100 4406 1.05 4406 - - - - - - 0.32 855 0.52 34336 - - -
    Tai150b 498896643 508566248 9117 1.94 9117 - - - - - - 0.20 3414 0.38 290186 - - -
    Tai256c 44759294 44896638 7539 0.27 12126 - - - - - - 0.16 1956 0.27 73180 - - -
     | Show Table
    DownLoad: CSV

    Table 8.  Improved results of the WFA variants for the QAP instances that have not been optimally solved by 2-opt WFA.

    Instances Best known value Random 2-opt WFA Systematic generator 2-opt WFA Random 2-opt mirror WFA WFA-3-opt
    Best solution Time (s) Best solution Time (s) Best solution Time (s) Best solution Time (s)
    Lipa50a 62093 62619 872 62703 1158 62666 1507 62593 971
    Lipa60a 107218 108103 1337 108172 2508 108070 2754 108070 2529
    Lipa80a 253195 254853 2254 254840 3965 254800 3467 254800 3930
    Lipa90a 360630 362854 2562 362906 4423 362673 5678 362673 5680
    Sko42 15812 15836 1042 15816 1547 15830 1071 15816 1618
    Sko49 23386 23510 1098 23460 1772 23474 1868 23460 1897
    Sko56 34458 34568 1064 34528 1742 34558 2454 34528 2134
    Sko64 48498 48796 1178 48648 2770 48758 2954 48648 3429
    Sko72 66256 66660 1620 66570 4096 66820 3425 66570 3702
    Sko90 115534 116922 1625 116968 4385 116632 4491 116590 4053
    Sko100b 153890 155288 1494 155728 4388 155398 4942 155204 1577
    Sko100c 147862 149628 1525 149862 3972 149990 4830 149564 1786
    Sko100d 149576 151196 1666 151186 4230 151022 3978 151022 3897
    Sko100e 149150 151056 2423 151140 4162 150588 5515 150498 5415
    Sko100f 149036 150510 2038 151032 4060 150794 4893 150390 2125
    Tai25a 1167256 1169030 236 1169030 570 1167256 1514 1167256 1817
    Tai30a 1818146 1832590 437 1828576 547 1830918 2571 1828576 640
    Tai35a 2422002 2436540 551 2436458 1288 2443826 2147 2436458 1508
    Tai50a 4938796 5031472 1113 5010798 2323 5026322 3595 5010798 2520
    Tai60a 7205962 7342990 2165 7317694 3142 7353798 3910 7317694 3074
    Tai80a 13511780 13821180 2100 13790286 2647 13764720 5707 13764720 4123
    Tai100a 21052466 21538854 2450 21577638 3897 21422344 8120 21422344 6220
    Tai256c 44759294 44896638 7539 44879868 12126 44881948 13280 44879868 15916
    Wil50 48816 48916 830 48856 3365 48846 2522 48846 2892
    Wil100 273038 274446 3331 274244 4278 274608 4234 273980 5273
     | Show Table
    DownLoad: CSV

    Table 9.  The average-value-based comparison results of the WFA and the PGA for all the QAP instances.

    Instances WFA PGA
    $\bar{\triangle}$ Time (s) $\bar{\triangle}$ Time (s)
    Burkard 0.000 28.14 0.006 22.97
    Christofides 0.000 23.65 3.834 2.54
    Elshafei 0.000 15.20 2.150 44.46
    Eschermann 0.042 91.23 0.586 104.06
    Hadley 0.000 4.16 0.002 10.80
    Krarup 0.000 441.83 1.190 96.97
    Li & Pardalos 1.336 1539.66 5.104 161.72
    Skorin-Kapov 0.865 2573.38 0.590 1386.65
    Nugent 0.000 29.82 0.259 26.94
    Roucairol 0.000 4.78 0.523 0.762
    Scriabin 0.000 2.40 0.627 0.808
    Steinberg 0.000 745.02 2.090 160.15
    Thonemann 0.559 1926.51 0.650 401.51
    Wilhelm 0.222 3972.06 0.225 973.44
    Taillard 0.890 2514.07 0.920 320.17
    Average 0.261 927.46 1.250 247.60
     | Show Table
    DownLoad: CSV
  •   R. Abbiw-Jackson , B. Golden , S. Raghavan  and  E. Wasil , A divide-and-conquer local search heuristic for data visualization, Computers & Operations Research, 33 (2006) , 3070-3087.  doi: 10.1016/j.cor.2005.01.020.
      R. K. Ahuja , J. B. Orlin  and  A. Tiwari , A greedy genetic algorithm for the quadratic assignment problem, Computers & Operations Research, 27 (2000) , 917-934.  doi: 10.1016/S0305-0548(99)00067-2.
      E. M. Arkin , R. Hassin  and  M. Sviridenko , Approximating the maximum quadratic assignment problem, Information Processing Letters, 77 (2001) , 13-16.  doi: 10.1016/S0020-0190(00)00151-4.
      A. Blanchard , S. Elloumi , A. Faye  and  N. Wicker , A cutting algorithm for the quadratic assignment problem, INFOR, 41 (2003) , 35-49. 
      S. H. Bokhari, Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, Boston, MA, 1987.
      E. S. Buffa , G. C. Armour  and  T. E. Vollmann , Allocating facilities with CRAFT, Harvard Business Review, 42 (1964) , 136-158. 
      R. E. Burkard , S. E. Karisch  and  F. Rendl , QAPLIB -A quadratic assignment problem library, Journal of Global Optimization, 10 (1997) , 391-403.  doi: 10.1023/A:1008293323270.
      R. E. Burkard, E. Cela, G. Rote and G. J. Woeginger, The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases, in: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, Vancouver, British Columbia, Canada, (1996), 204-218.
      E. Cela, The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization (eds. D. Z. Du and P. Pardalos), Kluwer Academic Publishers, London, 1998.
      V. M. Demidenko , G. Finke  and  V. S. Gordon , Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices, Journal of Mathematical Modeling and Algorithms, 5 (2006) , 167-187.  doi: 10.1007/s10852-005-9013-2.
      M. Dorigo, Optimization, Learning and Natural Algorithms, Ph. D thesis, Politecnico di Milano, Italie, 1992.
      E. Duman  and  I. Or , The quadratic assignment problem in the context of the printed circuit board assembly process, Computers & Operations Research, 34 (2007) , 163-179.  doi: 10.1016/j.cor.2005.05.004.
      B. Eschermann and H. J. Wunderlich, Optimized synthesis of self-testable finite state machines, in: Proceedings of the 20th International Symposium Fault-Tolerant Computing (FTCS 20), Newcastle Upon Tyne, UK, (1990), 390-397. doi: 10.1109/FTCS.1990.89393.
      H. Eskandar , A. Sadollah , A. Bahreininejad  and  M. Hamdi , Water cycle algorithm-A novel metaheuristic optimization method for solving constrained engineering optimization problems, Computers & Structures, 110/111 (2012) , 151-166. 
      R. N. Gasimov  and  O. Ustun , Solving the quadratic assignment problem using F-MSG algorithm, Journal of Industrial and Management Optimization, 3 (2007) , 173-191.  doi: 10.3934/jimo.2007.3.173.
      G. Gutin  and  A. Yeo , Polynomial approximation algorithms for TSP and QAP with a factorial domination number, Discrete Applied Mathematics, 119 (2002) , 107-116.  doi: 10.1016/S0166-218X(01)00267-0.
      P. M. Hahn , W. L. Hightower , T. A. Johnson , M. Guignard-Spielberg  and  C. Roucairol , Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem, Yugoslavian Journal of Operational Research, 11 (2001) , 41-60. 
      J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
      L. J. Hubert, Assignment Methods in Combinatorial Data Analysis, Marcel Dekker Inc., New York, 1987.
      J. Kennedy and R. C. Eberhart, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, (1995), 1942-1948. doi: 10.1109/ICNN.1995.488968.
      I. K. Kim , D. W. Jung  and  R. H. Park , Document image binarization based on topographic analysis using a water flow model, Pattern Recognition, 35 (2002) , 265-277.  doi: 10.1016/S0031-3203(01)00027-9.
      Y. Li, P. M. Pardalos and M. G. C. Resende, A greedy randomized adaptive search procedure for the quadratic assignment problem, in Quadratic Assignment and Related Problems(eds. P. M. Pardalos and H. Wolkowicz), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16 (1994), 237-261.
      M. Lim , Y. Yuan  and  S. Omatu , Extensive testing of a hybrid genetic algorithm for solving quadratic assignment problems, Computational Optimization and Applications, 23 (2002) , 47-64.  doi: 10.1023/A:1019972523847.
      V. Maniezzo  and  A. Colorni , The ant system applied to the quadratic assignment problem, IEEE Transactions on Knowledge and Data Engineering, 11 (1999) , 769-778.  doi: 10.1109/69.806935.
      P. Merz  and  B. Freisleben , Fitness landscape analysis and memetic algorithms for the quadratic assignment problem, IEEE Transactions on Evolutionary Computation, 4 (2000) , 337-352. 
      S. Nakrani  and  C. Tovey , On honey bees and dynamic server allocation in internet hosting centers, Adaptive Behaviors, 12 (2004) , 223-240.  doi: 10.1177/105971230401200308.
      H. H. Oh , K. T. Lim  and  S. I. Chien , An improved binarization algorithm based on a water flow model for document image with inhomogeneous backgrounds, Pattern Recognition, 38 (2005) , 2612-2625.  doi: 10.1016/j.patcog.2004.11.025.
      A. S. Ramkumar , S. G. Ponnambalam  and  N. Jawahar , A population-based hybrid ant system for quadratic assignment formulations in facility layout design, International Journal of Advanced Manufacturing Technology, 44 (2009) , 548-558.  doi: 10.1007/s00170-008-1849-y.
      A. S. Ramkumar , S. G. Ponnambalam  and  N. Jawahar , Iterated fast local search algorithm for solving quadratic assignment problems, Robotics and Computer-Integrated Manufacturing, 24 (2008) , 392-401.  doi: 10.1016/j.rcim.2007.01.004.
      D. F. Rossin , M. C. Springer  and  B. D. Klein , New complexity measures for the facility layout problem: An empirical study using traditional and neural network analysis, Computers & Industrial Engineering, 36 (1999) , 585-602.  doi: 10.1016/S0360-8352(99)00153-9.
      S. Sahni  and  T. Gonzalez , P-complete approximation problems, Journal of the ACM, 23 (1976) , 555-565.  doi: 10.1145/321958.321975.
      H. Q. Saremi , B. Abedin  and  A. M. Kermani , Website structure improvement: Quadratic assignment problem approach and ant colony metaheuristic technique, Applied Mathematics and Computation, 195 (2008) , 285-298.  doi: 10.1016/j.amc.2007.04.095.
      A. Shukla, A modified bat algorithm for the quadratic assignment problem, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 15), Sendai, Japan, (2015), 486-490. doi: 10.1109/CEC.2015.7256929.
      H. Shah-Hosseini, Problem solving by intelligent water drops, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 07), Singapore, (2007), 3226-3231.
      H. Shah-Hosseini , Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem, International Journal of Intelligent Computing and Cybernetics, 1 (2008) , 193-212.  doi: 10.1108/17563780810874717.
      H. Shah-Hosseini , The intelligent water drops algorithm: A nature-inspired swarm-based optimization algorithm, International Journal of Bio-Inspired Computation, 1 (2009) , 71-79. 
      S. P. Singh  and  R. R. K. Sharma , Two-level modified simulated annealing based approach for solving facility layout problem, International Journal of Production Research, 46 (2008) , 3563-3582. 
      E. Taillard , Comparison of iterative searches for the quadratic assignment problem, Location Science, 3 (1995) , 87-105.  doi: 10.1016/0966-8349(95)00008-6.
      T. H. Tran  and  K. M. Ng , A water flow algorithm for flexible flow shop scheduling with intermediate buffers, Journal of Scheduling, 14 (2011) , 483-500.  doi: 10.1007/s10951-010-0205-x.
      T. H. Tran  and  K. M. Ng , A hybrid water flow algorithm for multi-objective flexible flow shop scheduling problems, Engineering Optimization, 45 (2013) , 483-502.  doi: 10.1080/0305215X.2012.685072.
      K. Y. Wong  and  P. C. See , A hybrid ant colony optimization algorithm for solving facility layout problems formulated as quadratic assignment problems, Engineering Computations: International Journal for Computer-Aided Engineering and Software, 27 (2010) , 117-128. 
      T. H. Wu , S. H. Chung  and  C. C. Chang , A water flow-like algorithm for manufacturing cell formation problems, European Journal of Operational Research, 205 (2010) , 346-360.  doi: 10.1016/j.ejor.2010.01.020.
      X. Yang , Q. Lu , C. Li  and  X. Liao , Biological computation of the solution to the quadratic assignment problem, Applied Mathematics and Computation, 200 (2008) , 369-377.  doi: 10.1016/j.amc.2007.11.016.
      F. C. Yang  and  Y. P. Wang , Water flow-like algorithm for object grouping problems, Journal of the Chinese Institute of Industrial Engineers, 24 (2007) , 475-488. 
      Y. J. Zheng , Water wave optimization: A new nature-inspired metaheuristic, Computers & Operations Research, 55 (2015) , 1-11.  doi: 10.1016/j.cor.2014.10.008.
  • 加载中

Figures(4)

Tables(9)

SHARE

Article Metrics

HTML views(2455) PDF downloads(482) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return