Tabu search for maximal constraint satisfaction problems(15)

TS is on average 3 to 5 times faster (in terms of number of moves) than MCRW to reach a given cost value and this factor remains stable across all instances and for di erent cost values of a given instance.Problem f succ. 50 50 50 50 50 50 49 40 26 10 1 0 300.30.07.25.0 11 10 9 8 7 6 5 4 3 2 1 0 Tabu MCRW MCRW/Tabu#moves succ.#moves#moves min avg max min avg max avg 3326 8545 24332 50 11739 28242 77551 3.3 4513 10039.8 25924 50 11789 39613.3 104638 3.94 4738 12156.1 26545 50 15019 48761 107704 4.01 6293 15773.7 39941 50 15027 63067.7 132980 3.99 6306 22562.5 59051 50 15308 86265.8 227572 3.82 10722 31382.2 70505 50 16239 133856 355128 4.26 12764 43022.3 93673 47 33298 178486 415849 18585 52437.2 99010 35 85267 236837 461983 20799 64812.5 96686 25 106969 304038 493080 57146 79492.5 97850 12 132130 339752 484847 94525 94525 94525 1 425855 425855 425855 0 -

Table 3. More detailed comparative results of TS and MCRW, maximum moves= 100,000 for TS, 500,000 for MCRW

From Table 3, we observe that MCRW (with a maximum of 500,000 moves) obtains solutions comparable to those of TS (with a maximum of 100,000 iterations) in terms of quality. In terms of moves required by MCRW and TS, the ratio remains the same as before, i.e. around 3.5 to 4. Other experiments have been carried out where the two algorithms were run 5 times each with a much larger number of moves (2,000,000) on these instances. Similar results have been observed. Recall that there are two big di erences between the TS and MCRW algorithms. The rst one is that TS uses a tabu list while MCRW performs random walks. The second one is that the two algorithms examine the neighborhood according to two di erent strategies: TS looks at all the con icting variables while MCRW looks only at a single variable. In other words, MCRW examines much fewer neighbor solutions than TS does at each iteration. Therefore, one may ask if this second factor is responsible for the di erence of performance between these two algorithms. In order to see if this is the case, we tested a third algorithm which examines at each iteration all the con icting variables like in TS.

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究Tabu search for maximal constraint satisfaction problems(15)全文阅读和word下载服务。