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

Tabu search guided by reinforcement learning for the max-mean dispersion problem

  • * Corresponding author: Moses Olabhele Esangbedo

    * Corresponding author: Moses Olabhele Esangbedo 
Abstract Full Text(HTML) Figure(4) / Table(6) Related Papers Cited by
  • We present an effective hybrid metaheuristic of integrating reinforcement learning with a tabu-search (RLTS) algorithm for solving the max–mean dispersion problem. The innovative element is to design using a knowledge strategy from the $ Q $-learning mechanism to locate promising regions when the tabu search is stuck in a local optimum. Computational experiments on extensive benchmarks show that the RLTS performs much better than state-of-the-art algorithms in the literature. From a total of 100 benchmark instances, in 60 of them, which ranged from 500 to 1, 000, our proposed algorithm matched the currently best lower bounds for all instances. For the remaining 40 instances, the algorithm matched or outperformed. Furthermore, additional support was applied to present the effectiveness of the combined RL technique. The analysis sheds light on the effectiveness of the proposed RLTS algorithm.

    Mathematics Subject Classification: Primary: 65K05; Secondary: 90-08.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Box diagrams of debugging data for greedy factor $\epsilon$

    Figure 2.  Box diagrams of debugging data for learning factor $\alpha$

    Figure 3.  Box diagrams of debugging data for discount factor rate $\gamma{}$

    Figure 4.  Effectiveness of the incorporated RLTS component in the proposed algorithm

    Table 1.  Computational results of reinforcement-learning tabu-search (RLTS) algorithm on 60 benchmark instances

    Instance($ n $) GRASP-PR[18] HH[8] HHP[9] TP-TS[6] MAMMDP[15] EDA[16] RLTS
    $ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $
    MDPI1(500) 78.61 81.25 81.28 81.28 81.2770 81.2770 81.2770 81.2770 81.2770 81.2770
    MDPI2(500) 76.87 77.45 77.79 77.60 78.6102 78.6102 78.6102 78.6102 78.6102 78.6102
    MDPI3(500) 75.69 75.31 76.30 75.65 76.3008 76.3008 76.3008 76.3008 76.3008 76.3008
    MDPI4(500) 81.81 82.28 82.33 81.47 82.3321 82.3321 82.3321 82.3321 82.3321 82.3321
    MDPI5(500) 78.57 80.01 80.08 79.92 80.3540 80.3540 80.3540 80.3540 80.3540 80.3540
    MDPI6(500) 79.64 81.12 81.25 79.93 81.2486 81.2486 81.2486 81.2486 81.2486 81.2486
    MDPI7(500) 75.50 78.09 78.16 77.71 78.1645 78.1645 78.1645 78.1645 78.1645 78.1645
    MDPI8(500) 76.98 79.01 79.06 78.70 79.1399 79.1399 79.1399 79.1399 79.1399 79.1399
    MDPI9(500) 75.72 76.98 77.36 77.15 77.4210 77.4210 77.4210 77.4210 77.4210 77.4210
    MDPI10(500) 80.38 81.24 81.25 81.02 81.3099 81.3099 81.3099 81.3099 81.3099 81.3099
    MDPII1(500) 108.15 109.16 109.38 109.33 109.6101 109.6101 109.6101 109.6101 109.6101 109.6101
    MDPII2(500) 103.29 105.06 105.33 104.81 105.7175 105.7175 105.7175 105.7175 105.7175 105.7175
    MDPII3(500) 106.30 107.64 107.79 107.18 107.8217 107.8217 107.8217 107.8217 107.8217 107.8217
    MDPII4(500) 104.62 105.37 106.10 105.69 106.1001 106.1001 106.1001 106.1001 106.1001 106.1001
    MDPII5(500) 103.61 106.37 106.55 106.59 106.8572 106.8572 106.8572 106.8572 106.8572 106.8572
    MDPII6(500) 104.81 105.52 105.77 106.17 106.2980 106.2980 106.2980 106.2980 106.2980 106.2980
    MDPII7(500) 104.50 106.61 107.06 106.92 107.1494 107.1494 107.1494 107.1494 107.1494 107.1494
    MDPII8(500) 100.02 103.41 103.78 103.49 103.7792 103.7792 103.7792 103.7792 103.7792 103.7792
    MDPII9(500) 104.93 106.20 106.24 105.97 106.6198 106.6198 106.6198 106.6198 106.6198 106.6198
    MDPII10(500) 103.50 103.79 104.15 103.56 104.6515 104.6515 104.6515 104.6515 104.6515 104.6515
    MDPI1(750) 95.86 96.6507 96.6507 96.6507 96.6507 96.6507 96.6507
    MDPI2(750) 97.42 97.5649 97.5649 97.5649 97.5649 97.5649 97.5649
    MDPI3(750) 96.97 97.7989 97.7989 97.7989 97.7989 97.7989 97.7989
    MDPI4(750) 95.21 96.0414 96.0414 96.0414 96.0414 96.0414 96.0414
    MDPI5(750) 96.65 96.7619 96.7619 96.7619 96.7619 96.7619 96.7619
    MDPI6(750) 99.25 99.8613 99.8613 99.8613 99.8613 99.8613 99.8613
    MDPI7(750) 96.26 96.5454 96.5454 96.5454 96.5454 96.5454 96.5454
    MDPI8(750) 96.46 96.7270 96.7270 96.7270 96.7270 96.7270 96.7270
    MDPI9(750) 96.78 98.0584 98.0584 98.0584 98.0584 98.0584 98.0584
    MDPI10(750) 99.85 100.0642 100.0642 100.0642 100.0642 100.0642 100.0642
    MDPII1(750) 127.69 128.8637 128.8637 128.8637 128.8637 128.8637 128.8637
    MDPII2(750) 130.79 130.9544 130.9544 130.9544 130.9544 130.9544 130.9544
    MDPII3(750) 129.40 129.7825 129.7825 129.7825 129.7825 129.7825 129.7825
    MDPII4(750) 125.68 126.5823 126.5823 126.5823 126.5823 126.5823 126.5823
    MDPII5(750) 128.13 129.1229 129.1229 129.1229 129.1229 129.1229 129.1229
    MDPII6(750) 128.55 129.0252 129.0252 129.0252 129.0252 129.0252 129.0252
    MDPII7(750) 124.91 125.6467 125.6467 125.6467 125.6467 125.6467 125.6467
    MDPII8(750) 130.66 130.9405 130.9405 130.9405 130.9405 130.9405 130.9405
    MDPII9(750) 128.89 128.8899 128.8899 128.8899 128.8899 128.8899 128.8899
    MDPII10(750) 132.99 133.2653 133.2653 133.2653 133.2653 133.2653 133.2653
    MDPI1(1, 000) 118.76 119.1741 119.1741 119.1741 119.1741 119.1741 119.1741
    MDPI2(1, 000) 113.22 113.5248 113.5248 113.5248 113.5248 113.5248 113.5248
    MDPI3(1, 000) 114.51 115.1386 115.1386 115.1386 115.1386 115.1386 115.1386
    MDPI4(1, 000) 110.53 111.1504 111.1504 111.1504 111.1504 111.1504 111.1504
    MDPI5(1, 000) 111.24 112.7232 112.7232 112.7232 112.7232 112.7232 112.7232
    MDPI6(1, 000) 112.08 113.1987 113.1987 113.1987 113.1987 113.1987 113.1987
    MDPI7(1, 000) 110.94 111.5555 111.5555 111.5555 111.5555 111.5555 111.5555
    MDPI8(1, 000) 110.29 111.2632 111.2632 111.2632 111.2632 111.2632 111.2632
    MDPI9(1, 000) 115.78 115.9588 115.9588 115.9588 115.9588 115.9588 115.9588
    MDPI10(1, 000) 114.29 114.7316 114.7316 114.7316 114.7316 114.7316 114.7316
    MDPII1(1, 000) 145.46 147.9362 147.9362 147.9362 147.9362 147.9362 147.9362
    MDPII2(1, 000) 150.49 151.3800 151.3800 151.3800 151.3800 151.3800 151.3800
    MDPII3(1, 000) 149.36 150.7882 150.7882 150.7882 150.7882 150.7882 150.7882
    MDPII4(1, 000) 147.91 149.1780 149.1780 149.1780 149.1780 149.1780 149.1780
    MDPII5(1, 000) 150.23 151.5208 151.5208 151.5208 151.5208 151.5208 151.5208
    MDPII6(1, 000) 147.29 148.3434 148.3434 148.3434 148.3434 148.3434 148.3434
    MDPII7(1, 000) 148.41 148.7424 148.7424 148.7424 148.7424 148.7424 148.7424
    MDPII8(1, 000) 145.87 147.8268 147.8268 147.8268 147.8268 147.8268 147.8268
    MDPII9(1, 000) 145.67 147.0839 147.0839 147.0839 147.0839 147.0839 147.0839
    MDPII10(1, 000) 148.40 150.0461 150.0461 150.0461 150.0461 150.0461 150.0461
     | Show Table
    DownLoad: CSV

    Table 2.  Computational results of RLTS algorithm on the 40 benchmark large instances with $n = 3, 000, 5, 000$. Each instance was independently solved 20 times, and results were compared to the TP-TS, MAMMDP, and EDA algorithms

    Instance $ (n) $ TP-TS MAMMDP EDA RLTS
    $ f_{best} $ $ f_{avg} $ $ time $ $ f_{best} $ $ f_{avg} $ time $f_{best} $ $ f_{avg} $ $ time $
    MDPI1(3, 000) 188.0953 189.049 189.049 88.36 189.049 189.049 69.35 189.049 189.049 47.45
    MDPI2(3, 000) 186.4730 187.3873 187.3873 60.71 187.3873 187.3873 53.64 187.3873 187.3873 66.65
    MDPI3(3, 000) 184.3414 185.6668 185.6551 352.85 185.6668 185.6453 399.44 185.6668 185.6622 426.7
    MDPI4(3, 000) 185.5882 186.1637 186.1536 300.37 186.1637 186.1637 240.45 186.1637 186.1637 137.8
    MDPI5(3, 000) 186.2349 187.5455 187.5455 61.29 187.5455 187.5455 94.16 187.5455 187.5455 54.23
    MDPI6(3, 000) 189.0935 189.4313 189.4313 51.99 189.4313 189.4313 48.21 189.4313 189.4313 23.15
    MDPI7(3, 000) 187.4512 188.2426 188.2426 86.57 188.2426 188.2426 120.95 188.2426 188.2426 65.45
    MDPI8(3, 000) 185.7358 186.7968 186.7968 48.04 186.7968 186.7968 38.7 186.7968 186.7968 31.2
    MDPI9(3, 000) 187.1076 188.2313 188.2313 151.78 188.2313 188.2313 82.66 188.2313 188.2313 47.25
    MDPI10(3, 000) 184.6866 185.6825 185.6238 228.72 185.6825 185.6719 510.41 185.6825 185.6822 467.1
    MDPII1(3, 000) 252.1818 252.3204 252.3204 59.7 252.3204 252.3204 42.42 252.3204 252.3204 51.2
    MDPII2(3, 000) 248.6972 250.0621 250.0621 220.1 250.0621 250.0617 248.1 250.0621 250.0576 514.4
    MDPII3(3, 000) 250.5303 251.9063 251.9063 146.32 251.9063 251.9063 139.36 251.9063 251.9063 78.1
    MDPII4(3, 000) 253.0963 253.941 253.9406 370.76 253.941 253.9406 352.17 253.941 253.941 184.05
    MDPII5(3, 000) 252.5621 253.2604 253.2604 374 253.2604 253.2603 308.8 253.2604 253.2608 344.15
    MDPII6(3, 000) 249.7160 250.6778 250.6778 55.35 250.6778 250.6778 55.9 250.6778 250.6778 37.25
    MDPII7(3, 000) 249.5939 251.1344 251.1344 74.72 251.1344 251.1344 88.61 251.1344 251.1344 59.85
    MDPII8(3, 000) 252.0565 252.9996 252.9996 79.82 252.9996 252.9996 123.56 252.9996 252.9996 61.72
    MDPII9(3, 000) 251.3625 252.4258 252.4258 90.27 252.4258 252.4258 58.5 252.4258 252.4258 94.4
    MDPII10(3, 000) 251.1169 252.3966 252.3966 13.18 252.3966 252.3966 8.73 252.3966 252.3966 12.02
    MDPI1(5, 000) 236.3332 4395.321 4395.24 2914.9 4395.321 4395.288 3084.12 4395.321 4395.312 2804.12
    MDPI2(5, 000) 239.0143 219.7661 219.762 145.745 219.7661 219.7644 154.206 219.7661 219.7656 140.206
    MDPI3(5, 000) 238.4742 240.1625 240.1029 312.13 240.1625 240.0434 905.58 240.1625 240.0519 1061.45
    MDPI4(5, 000) 237.3972 241.8274 241.793 1244.36 241.8274 241.768 958.6 241.8274 241.7649 1046.76
    MDPI5(5, 000) 240.0439 240.8908 240.8882 810.48 240.8908 240.8494 992.57 240.8908 240.8518 1040.85
    MDPI6(5, 000) 238.0015 240.9972 240.9768 653.64 240.9972 240.9281 1240.33 240.9925 240.9129 910.6
    MDPI7(5, 000) 239.7444 242.4801 242.4759 735.16 242.4801 242.4419 1104.64 242.4801 242.4593 895.02
    MDPI8(5, 000) 237.9150 240.3229 240.3063 976.02 240.376 240.2726 992.36 240.376 240.2698 1072.8
    MDPI9(5, 000) 235.9103 242.8149 242.775 259.5 242.8201 242.7624 965.79 242.8201 242.7778 1036.81
    MDPI10(5, 000) 241.8043 241.195 241.1618 1148.6 241.195 241.1291 909.39 241.195 241.134 1036.05
    MDPII1(5, 000) 316.7478 239.7606 239.6676 1219.71 239.7606 239.5363 1001.4 239.7606 239.6131 1441.87
    MDPII2(5, 000) 323.6829 243.4737 243.373 457.28 243.4737 243.3442 981.99 243.4737 243.3673 758.61
    MDPII3(5, 000) 321.9291 322.2359 322.1813 1519.05 322.2359 322.1594 1114.21 322.2359 322.1691 1089.2
    MDPII4(5, 000) 317.6767 327.3019 327.0063 1103.13 327.3019 327.1024 731.65 327.3019 327.2153 858.95
    MDPII5(5, 000) 317.7479 324.8135 324.8016 955.81 324.8135 324.777 1043.24 324.8135 324.7917 1039.47
    MDPII6(5, 000) 319.3890 322.2376 322.1973 664.1 322.2277 322.1171 1059.47 322.2376 322.1448 1106.05
    MDPII7(5, 000) 319.9806 322.4912 322.3807 1014.9 322.5012 322.3717 971.06 322.5012 322.3647 1151.2
    MDPII8(5, 000) 318.8545 322.9505 322.7039 352.88 322.9505 322.6878 1405.72 322.9505 322.7466 937.45
    MDPII9(5, 000) 320.4376 322.8504 322.7931 714.31 322.8504 322.7615 1164.19 322.8504 322.8136 1052.93
    MDPII10(5, 000) 320.8530 323.1121 323.0533 879.48 323.1121 322.8815 1168.86 323.1121 322.8943 1015.75
     | Show Table
    DownLoad: CSV

    Table 3.  Parameters of $\epsilon$, $\alpha$, and $\gamma$

    Names Range Debugging Intervals Final values
    Greedy factor [0.5, 1) 0.05 0.7
    Learning factor (0, 1) 0.1 0.5
    Discount factor [0, 1) 0.1 0.5
     | Show Table
    DownLoad: CSV

    Table 4.  Debugging results for factor $\epsilon$

    Instances ($ n $) / $ \epsilon $ 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95
    MDPI1(5, 000) -0.122851 -0.081087 -0.130172 -0.128802 -0.056058 -0.129919 -0.041805 -0.155847 -0.044694 -0.105110
    MDPI2(5, 000) -0.041683 -0.044909 -0.042706 -0.031403 -0.032596 -0.058119 -0.012692 -0.060083 -0.056580 -0.054879
    MDPI3(5, 000) -0.067597 -0.050908 -0.053767 -0.106229 -0.068687 -0.076957 -0.105697 -0.085361 -0.115044 -0.051265
    MDPI4(5, 000) -0.133373 -0.042282 -0.115774 -0.091527 -0.064438 -0.134837 -0.063109 -0.100193 -0.061781 -0.071073
    MDPI5(5, 000) -0.042153 -0.058244 -0.073869 -0.027768 -0.041856 -0.064060 -0.072030 -0.051006 -0.032583 -0.059985
    MDPI6(5, 000) -0.040458 -0.030610 -0.054468 -0.079938 -0.042002 -0.093500 -0.018872 -0.071949 -0.053420 -0.030553
    MDPI7(5, 000) -0.007039 -0.040785 -0.022835 -0.025523 -0.011432 -0.022520 -0.000364 -0.015116 0.004182 -0.010404
    MDPI8(5, 000) -0.048888 -0.064965 -0.040440 -0.050873 -0.058277 -0.058174 -0.040082 -0.054745 -0.050569 -0.078426
    MDPI9(5, 000) -0.129854 -0.078371 -0.117872 -0.097018 -0.076916 -0.176947 -0.060925 -0.175825 -0.084588 -0.097384
    MDPI10(5, 000) -0.033717 -0.043167 -0.010259 -0.039291 -0.035665 -0.062412 -0.042826 -0.063820 -0.018992 -0.030091
    MDPII1(5, 000) -0.005740 -0.033777 -0.059031 -0.047182 -0.044300 -0.066763 -0.060716 -0.031978 -0.014357 -0.039396
    MDPII2(5, 000) 0.147624 0.167856 0.178805 0.132264 0.164916 0.118441 0.083772 0.211362 0.147558 0.088298
    MDPII3(5, 000) -0.023621 -0.023856 -0.045420 -0.022302 -0.009195 -0.030358 -0.013416 -0.023812 -0.027812 -0.027001
    MDPII4(5, 000) -0.166333 -0.094202 -0.120204 -0.096423 -0.085864 -0.121264 -0.120666 -0.188106 -0.240823 -0.147536
    MDPII5(5, 000) -0.075976 -0.096680 -0.044135 -0.004540 -0.033960 -0.043347 -0.077273 -0.032238 -0.036416 -0.031091
    MDPII6(5, 000) -0.017563 0.058637 0.005761 -0.098428 -0.080234 0.015629 -0.008452 0.021738 0.033528 -0.012549
    MDPII7(5, 000) -0.015845 -0.074944 -0.060637 -0.081458 -0.021804 -0.056874 -0.053205 -0.017029 -0.017963 -0.067988
    MDPII8(5, 000) -0.178216 -0.143775 -0.177740 -0.229257 -0.176900 -0.163983 -0.205498 -0.172191 -0.244947 -0.188872
    MDPII9(5, 000) 0.014833 -0.094614 -0.111384 -0.118775 0.068232 -0.047735 -0.119738 -0.069007 -0.124918 -0.130199
    MDPII10(5, 000) 0.017633 -0.048853 -0.107008 -0.162074 0.012272 -0.128291 0.050908 0.021277 0.044312 -0.082684
    Debugging results for factors $ \alpha $ and $ \gamma $ were omitted.
     | Show Table
    DownLoad: CSV

    Table 5.  Friedman test results for three parameters

    $\epsilon~$ Mean Rank $\alpha~$ Mean Rank $\gamma~$ Mean Rank
    $\epsilon~$0.5 6.2 $\alpha~$0.1 3.8 $\gamma~$0 4.2
    $\epsilon~$0.55 6.1 $\alpha~$0.2 5.05 $\gamma~$0.1 4.15
    $\epsilon~$0.6 4.9 $\alpha~$0.3 4.6 $\gamma~$0.2 4.7
    $\epsilon~$0.65 4.7 $\alpha~$0.4 4.25 $\gamma~$0.3 5.6
    $\epsilon~$0.7 6.9 $\alpha~$0.5 6.45 $\gamma~$0.4 5.4
    $\epsilon~$0.75 3.65 $\alpha~$0.6 4.95 $\gamma~$0.5 7.15
    $\epsilon~$0.8 6.15 $\alpha~$0.7 4.85 $\gamma~$0.6 5.75
    $\epsilon~$0.85 5.3 $\alpha~$0.8 5.95 $\gamma~$0.7 5.85
    $\epsilon~$0.9 6.1 $\alpha~$0.9 5.1 $\gamma~$0.8 6.3
    $\epsilon~$0.95 5 $\gamma~$0.9 5.9
    $ N $ 20 $ N $ 20 $ N $ 20
    Chi-Square 18.12 Chi-Square 13.88 Chi-Square 17.193
    $ df $ 9 $ df $ 8 $ df $ 9
    Asymp. Sig 0.034 Asymp. Sig. 0.085 Asymp. Sig. 0.46
     | Show Table
    DownLoad: CSV

    Table 6.  Comparison between multistart tabu-search (MTS) method and the proposed RLTS algorithm on the set of 40 large instances within ≥ 3, 000. Each instance was independently solved 20 times by the two algorithms

    Instance $ (n) $ MTS RLTS
    $ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $
    MDPI1(3, 000) 189.04897 189.04897 189.04897 189.04897
    MDPI2(3, 000) 187.38729 187.38729 187.38729 187.38729
    MDPI3(3, 000) 185.66681 185.65159 185.66681 185.6594
    MDPI4(3, 000) 186.16373 186.16373 186.16373 186.16373
    MDPI5(3, 000) 187.54552 187.54552 187.54552 187.54552
    MDPI6(3, 000) 189.43126 189.43126 189.43126 189.43126
    MDPI7(3, 000) 188.24258 188.24258 188.24258 188.24258
    MDPI8(3, 000) 186.79681 186.79681 186.79681 186.79681
    MDPI9(3, 000) 188.23126 188.23126 188.23126 188.23126
    MDPI10(3, 000) 185.68251 185.67237 185.68251 185.6747
    MDPII1(3, 000) 252.32043 252.32043 252.32043 252.32043
    MDPII2(3, 000) 250.06214 250.05474 250.06214 250.0569
    MDPII3(3, 000) 251.90627 251.90627 251.90627 251.90627
    MDPII4(3, 000) 253.94101 253.93968 253.94101 253.941
    MDPII5(3, 000) 253.26042 253.26016 253.26042 253.2604
    MDPII6(3, 000) 250.67775 250.67775 250.67775 250.67775
    MDPII7(3, 000) 251.13441 251.13441 251.13441 251.13441
    MDPII8(3, 000) 252.99965 252.99965 252.99965 252.99965
    MDPII9(3, 000) 252.42577 252.42577 252.42577 252.42577
    MDPII10(3, 000) 252.39659 252.39659 252.39659 252.39659
    MDPI1(5, 000) 240.14121 240.0212 240.1594 240.01588
    MDPI2(5, 000) 241.81754 241.75355 241.8274 241.7716
    MDPI3(5, 000) 240.89082 240.82517 240.89082 240.8443
    MDPI4(5, 000) 240.97349 240.91546 240.9972 240.9249
    MDPI5(5, 000) 242.48013 242.43047 242.48013 242.4512
    MDPI6(5, 000) 240.32868 240.2663 240.32868 240.26432
    MDPI7(5, 000) 242.82014 242.7599 242.82014 242.7793
    MDPI8(5, 000) 241.14478 241.11345 241.195 241.1323
    MDPI9(5, 000) 239.76056 239.51496 239.76056 239.5929
    MDPI10(5, 000) 243.38549 243.34815 243.4737 243.3598
    MDPII1(5, 000) 322.22322 322.1312 322.2359 322.1659
    MDPII2(5, 000) 327.30191 327.07525 327.30191 327.2223
    MDPII3(5, 000) 324.81083 324.79022 324.8135 324.7931
    MDPII4(5, 000) 322.21229 322.1266 322.2376 322.08809
    MDPII5(5, 000) 322.42081 322.30125 322.5012 322.3782
    MDPII6(5, 000) 322.95049 322.61523 322.95049 322.7672
    MDPII7(5, 000) 322.85044 322.7784 322.85044 322.7757
    MDPII8(5, 000) 323.03384 322.87316 323.1121 322.8885
    MDPII9(5, 000) 323.52271 323.27856 323.5438 323.4081
    MDPII10(5, 000) 324.51991 324.29479 324.51991 324.5191
     | Show Table
    DownLoad: CSV
  • [1] R. AringhieriR. Cordone and A. Grosso, Construction and improvement algorithms for dispersion problems, European J. Oper. Res., 242 (2015), 21-33.  doi: 10.1016/j.ejor.2014.09.058.
    [2] R. Aringhieri and R. Cordone, Comparing local search metaheuristics for the maximum diversity problem, J. Oper. Res. Soc., 62 (2011), 266-280.  doi: 10.1057/jors.2010.104.
    [3] J. Boyan and A. W. Moore, Learning evaluation functions to improve optimization by local search, J. Machine Learning Research, 1 (2000), 77-112.  doi: 10.1162/15324430152733124.
    [4] J. BrimbergN. MladenovićR. Todosijević and D. Urošević, Less is more: Solving the max-mean diversity problem with variable neighborhood search, Information Sciences, 382 (2017), 179-200.  doi: 10.1016/j.ins.2016.12.021.
    [5] E. K. BurkeG. Kendall and E. Soubeiga, A tabu-search hyperheuristic for timetabling and rostering, J. Heuristics, 9 (2003), 451-470.  doi: 10.1023/B:HEUR.0000012446.94732.b6.
    [6] R. CarrascoA. PhamM. GallegoF. GortázarR. Martí and A. Duarte, Tabu search for the Max–Mean Dispersion Problem, Knowledge-Based Systems, 85 (2015), 256-264.  doi: 10.1016/j.knosys.2015.05.011.
    [7] F. C. De Lima Júnior, A. D. D. Neto and J. D. De Melo, Hybrid metaheuristics using reinforcement learning applied to salesman traveling problem, in Traveling Salesman Problem, Theory and Applications, IntechOpen, 2010. doi: 10.5772/13343.
    [8] F. Della Croce, M. Garraffa and F. Salassa, A hybrid heuristic approach based on a quadratic knapsack formulation for the max-mean dispersion problem, in Combinatorial Optimization, Lecture Notes in Comput. Sci., 8596, Springer, Cham, 2014,186–194. doi: 10.1007/978-3-319-09174-7_16.
    [9] F. Della CroceM. Garraffa and F. Salassa, A hybrid three-phase approach for the max-mean dispersion problem, Comput. Oper. Res., 71 (2016), 16-22.  doi: 10.1016/j.cor.2016.01.003.
    [10] F. Della CroceA. Grosso and M. Locatelli, A heuristic approach for the max-min diversity problem based on max-clique, Comput. Oper. Res., 36 (2009), 2429-2433.  doi: 10.1016/j.cor.2008.09.007.
    [11] P. GalinierZ. Boujbel and M. Coutinho Fernandes, An efficient memetic algorithm for the graph partitioning problem, Ann. Oper. Res., 191 (2011), 1-22.  doi: 10.1007/s10479-011-0983-3.
    [12] M. GarraffaF. Della Croce and F. Salassa, An exact semidefinite programming approach for the max-mean dispersion problem, J. Comb. Optim., 34 (2017), 71-93.  doi: 10.1007/s10878-016-0065-1.
    [13] A. Gosavi, Reinforcement learning: A tutorial survey and recent advances, INFORMS J. Comput., 21 (2009), 178-192.  doi: 10.1287/ijoc.1080.0305.
    [14] X. LaiD. YueJ.-K. Hao and F. Glover, Solution-based tabu search for the maximum min-sum dispersion problem, Inform. Sci., 441 (2018), 79-94.  doi: 10.1016/j.ins.2018.02.006.
    [15] X. Lai and J. K. Hao, A tabu search based memetic algorithm for the max-mean dispersion problem, Comput. Oper. Res., 72 (2016), 118-127.  doi: 10.1016/j.cor.2016.02.016.
    [16] P. Larranaga, A review on estimation of distribution algorithms, in Estimation of Distribution Algorithmn, Genetic Algorithms and Evolutionary Computation, 2, Springer, Boston, 2002, 57–100. doi: 10.1007/978-1-4615-1539-5_3.
    [17] Z. Lu, F. Glover and J.-K. Hao, Neighborhood combination for unconstrained binary quadratic programming, MIC 2009: The VIII Metaheuristics International Conference, Hamburg, Germany, 2009.
    [18] R. Martí and F. Sandoya, GRASP and path relinking for the equitable dispersion problem, Comput. Oper. Res., 40 (2013), 3091-3099.  doi: 10.1016/j.cor.2012.04.005.
    [19] V. V. Miagkikh and W. F. Punch, Global search in combinatorial optimization using reinforcement learning algorithms, Proceedings of the 1999 Congress on Evolutionary Computation-CEC99, Washington, DC, 1999. doi: 10.1109/CEC.1999.781925.
    [20] D. Nijimbere, S. Zhao, H. Liu, B. Peng and A. Zhang, A hybrid metaheuristic of integrating estimation of distribution algorithm with tabu search for the max-mean dispersion problem, Math. Probl. Eng., 2019 (2019), 16pp. doi: 10.1155/2019/7104702.
    [21] D. C. PorumbelJ.-K. Hao and F. Glover, A simple and effective algorithm for the MaxMin diversity problem, Ann. Oper. Res., 186 (2011), 275-293.  doi: 10.1007/s10479-011-0898-z.
    [22] O. A. ProkopyevN. Kong and and D. L. Martinez-Torres, The equitable dispersion problem, European J. Oper. Res., 197 (2009), 59-67.  doi: 10.1016/j.ejor.2008.06.005.
    [23] A. P. PunnenS. TaghipourD. Karapetyan and B. Bhattacharyya, The quadratic balanced optimization problem, Discrete Optim., 12 (2014), 47-60.  doi: 10.1016/j.disopt.2014.01.001.
    [24] I. SghirJ. K. HaoI. B. Jaafar and K. Ghédira, A multi-agent based optimization method applied to the quadratic assignment problem, Expert Systems Appl., 42 (2015), 9252-9262.  doi: 10.1016/j.eswa.2015.07.070.
    [25] J. A. Torkestani and M. R. Meybodi, A cellular learning automata-based algorithm for solving the vertex coloring problem, Expert Systems Appl., 38 (2011), 9237-9247.  doi: 10.1016/j.eswa.2011.01.098.
    [26] Y. WangQ. Wu and F. Glover, Effective metaheuristic algorithms for the minimum differential dispersion problem, European J. Oper. Res., 258 (2017), 829-843.  doi: 10.1016/j.ejor.2016.10.035.
    [27] Y. WangJ.-K. HaoF. Glover and Z. Lü, A tabu search based memetic algorithm for the maximum diversity problem, Engineering Appl. Artificial Intell., 27 (2014), 103-114.  doi: 10.1016/j.engappai.2013.09.005.
    [28] Y. Xu, D. Stern and H. Samulowitz, Learning adaptation to solve constraint satisfaction problems. Available from: https://www.microsoft.com/en-us/research/wp-content/uploads/2009/01/lion2009.pdf.
    [29] T. Yu and W.-G. Zhen, A multi-step $ Q(\lambda)$ learning approach to power system stabilizer, IFAC Proceedings Volumes, 43 (2010), 220-224.  doi: 10.3182/20100826-3-tr-4015.00042.
    [30] Y. ZhouJ.-K. Hao and and B. Duval, Reinforcement learning based local search for grouping problems: A case study on graph coloring, Expert Systems Appl., 64 (2016), 412-422.  doi: 10.1016/j.eswa.2016.07.047.
  • 加载中
Open Access Under a Creative Commons license

Figures(4)

Tables(6)

SHARE

Article Metrics

HTML views(1332) PDF downloads(773) Cited by(0)

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return