Biology Reference
In-Depth Information
Table 1.
Time and performance comparison between LST and
hsearch
for
(a) 500 leaves and (b) 1000 leaves.
(a) 500 leaves
Trials
=
1
Trials
=
50
+
RBFS
l
max
Time [s]
Equal
Better
Time [s]
Equal
Better
20
9.30 ± 0.31
20
0
610 ± 24
20
0
100
9.63 ± 0.32
3
0
661 ± 25
14
2
150
9.34 ± 0.34
0
5
729 ± 35
3
17
(b) 1000 leaves
Trials
=
1
Trials
=
50
+
RBFS
l
max
Time [s]
Equal
Better
Time [s]
Equal
Better
20
79.9 ± 3.3
2
16
5601 ± 177
1
17
50
80.5 ± 3.1
0
20
5699 ± 185
0
20
75
79.3 ± 3.1
0
14
5958 ± 242
0
20
100
80.4 ± 3.1
0
11
6564 ± 229
0
19
For each maximum branch length
l
max
, LST and hsearch were run on 20 problems.
Trials = 1 is LST's lowest optimization level, and Trials = 50 + RBFS constitutes a
high one.
hsearch
was always run for 50 hours. Time is the average running time of
LST over the 20 problems. The column Equal shows how often the two programs
found a tree with the same score, and the column Better shows how often LST found
a tree with a better score.
and how often LST found a tree with a higher score. The timings for
hsearch
are not shown. It ran for 50 hours on each problem.
We first look at the problems with 500 leaves. In all cases, it took
LST around 10 seconds to come up with a solution with Trials
=
1 and
around 10 minutes with Trials
=
50
+
RBFS. For the easiest problems
20), the two programs constructed the same tree in all 20 prob-
lems and for both of LST's optimization levels. For
l
max
(
l
max
=
=
100 and
1 was not enough for LST to be able to compete with
hsearch
. Using Trials
l
max
=
150, Trials
=
100 led to a comparable per-
formance of the two programs; and for
l
max
=
=
50
+
RBFS for
l
max
=
150,
hsearch
never returned
a better scoring tree than LST. In 17 out of 20 cases, LST found a
better tree in around 10 minutes, than
hsearch
did in 50 hours.
