An Evolutionary Local Search Method for Incremental Satisfiability - Artificial Intelligence and Symbolic Computation - page 153

variables). If the series contains problems at the phase transition (values of ratio near
the threshold), it is generally difficult to find a satisfying assignment to such prob-
lems and hence, more frequent local search repairs are performed (step 1.c. of the
algorithm). It seems that this approach may not be suitable for stochastic local search
algorithms, whereas the incremental systematic algorithm proposed by Hooker [14]
was substantially faster than DPL [10], [17]. However, more complete tests are re-
quired to further investigate this hypothesis.

Table 2. Results of τ -EO-ISAT on ISAT2 instances

n m

Problem id Success

rate/ 20

CPU time # Flips

Mean Std Mean Std

ais6
ais8
ais10
ais12
ii8a1
ii8a2
ii8a3
ii8a4
ii8b1
ii8b2
ii8b3
ii8b4
ii8c1
ii8c2
ii8d1
ii8d2
ii8e1
ii8e2
par8-1-c
par8-2-c
par8-3-c
par8-4-c
par8-5-c
flat100-239
(100 inst.)
uf125-538
(100 inst.)
g125-17
g125-18
g250-15
g250-20

61
113
181
265
66
180
264
396
336
576
816
1068
510
950
530
930
520
870
64
68
75
67
75
300

581
1520
3151
5666
186
800
1552
2798
2068
4088
6108
8214
3065
6689
3207
6547
3136
6121
254
270
298
266
298
1117

20
20
8
8
20
20
20
20
20
20
19
20
20
20
20
20
20
20
20
20
20
20
15
5.30

0.0540
2.2310
3.0270
4.1985
0.0008
0.0045
0.0455
0.2480
0.0457
2.6800
3.2670
4.3428
0.0542
3.6502
1.3720
4.2365
0.0350
1.0395
0.0825
0.0945
0.0250
0.1278
0.9540
5.2050

0.0115
1.1543
2.5230
1.7620
0.0005
0.0012
0.0125
0.0165
0.0054
0.2754
2.2850
2.2490
0.0012
1.2760
0.0086
0.0450
0.0014
0.0745
0.0150
0.0172
0.0120
0.0850
0.6535
0.1442

1080.0
15403.5
6045.9
18458.1
38.0
67.2
205.4
223.2
104.7
3216.4
20255.4
1208.5
137.9
2702.2
823.9
959.4
123.1
310.5
2321.6
2551.6
550.6
3195.0
21465.0
42435.7

320.1
1356.8
1582.2
2351.0
0.0
0.1
54.2
22.5
24.1
412.5
654.1
2543.9
65.4
25.3
85.2
21.3
8.4
12.6
54.8
545.6
185.4
1255.6
11520.1
1280.8

125 538 19.55 0.4382 0.0321 4359.6 458.0

2125
2250
3750
7250

66276
70163
233965
454622

18
20
20
19

64.5205
1.2651
0.9510
134.8600

8.3510
0.2090
0.0650
12.2945

626452.0
11245.8
9756.1
1295286.5

95734.0
1562.6
455.3
981005.0

As an initial result, τ-EO-ISAT2 solved all the problems in less computation time
and provided better solution quality than τ-EO-ISAT1, but it did not dominate R-
Novelty on all the problems. However, it should be noted that the mean times re-