Tabu search for maximal constraint satisfaction problems(11)

Abstract. This paper presents a Tabu Search (TS) algorithm for solving maximal constraint satisfaction problems. The algorithm was tested on a wide range of random instances (up to 500 variables and 30 values). Comparisons were carried out with a min-confl

300/30, 500/30). For each size, we choose one or several values for the couple (p1;p2) in such a way that the instances of the class are not easily satis able and have a cost value smaller than 30.

4.3 Parameter tuni

ng for TS and MCRWThe performance of TS and MCRW is greatly in uenced by some parameters: the size of tabu list tl and the random walk probability p. We use the following procedure to determine the appropriate values for these parameters for each class of instances. First, a preliminary study determined the following ranges of parameter values: 10 tl 35 and 0:02 p 0:1. Then, di erent discrete values between these ranges were further tested as follows. For TS (respectively MCRW) each of the values f10, 15, 20, 25, 30, 35, 40, 45g (f0.02, 0.03, 0.04, 0.05, 0.07, 0.1, 0.2, 0.3, 0.4g for MCRW) was used to run 50 times on the class (10 instances, 5 runs per instance, each run being limited to 50,000 moves) and the best value identi ed for the class.

4.4 ResultsProblem

tl cost value f

Tabu

50.10.10.60.0 15 50.10.10.70.0 15 50.10.30.30.0 15 50.10.30.35.0 15 50.10.50.20.0 15 100.15.10.40.0 15 100.15.10.45.0 25 100.15.10.50.0 30 100.15.30.15.0 10 100.15.30.20.0 20 250.25.03.55.0 40 250.25.07.30.0 30 250.25.10.21.0 25 250.25.10.22.0 30 250.25.10.23.0 35 300.30.03.50.0 45 300.30.05.35.0 35 300.30.07.25.0 25 500.30.04.25.0 30Table 1.

min avg max 4 4 4 0.05 14 14 14 0.05 5 5.08 6 0.05 15 15 15 0.05 8 8 8 0.05 0 1.2 2 0.03 8 9.72 12 0.03 20 21.62 24 0.03 0 0 0 0.03 19 20.78 23 0.03 6 8.42 12 0.02 7 11.68 14 0.03 3 4.88 7 0.03 8 10.86 14 0.03 15 19.18 22 0.02 5 10.1 15 0.03 9 13.96 17 0.02 1 3.48 6 0.02 0 1.56 3 0.02

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