Information Technology Reference
In-Depth Information
strategy for the EMBOSS domain and the example workflow composition
problem that drastically constrains the solution space by excluding clearly
inadequate solutions and explicitly including adequate solutions.
3.3.4
Solution Refinement
Similar to the scenario that has been described in [180], this section de-
scribes a possible solution refinement strategy for the synthesis results that
are returned by PROPHETS. It is of course only one highly specific example,
tailored to a particular workflow composition scenario. A different use case
will also require a different refinement strategy and finally a different set of
domain-specific and problem-specific constraints. However, starting the so-
lution refinement in a small search depth with constraints that exclude the
most dispensable constructs, and then proceeding to greater search depths
with constraints that include desired constructs explicitly, as it is done here,
has turned out to be a common and expedient constraint development ap-
proach. Thus, the incremental development of the constraints is discussed
at this level of detail only for this example, while for the other application
scenarios simply the finally defined constraints are presented.
Tabl e 3.2
Solution refinement for the exemplary workflow composition problem,
considering solutions up to length 4
Refinements
Number of solutions
depth 1 depth 2 depth 3
depth 4
none
2
427 46,992 ¿ 1,000,000
1
2
193 10,130
385,518
1, 2a
2
169
7,933
274,664
1, 2a, 2b
0
1
132
8,801
1, 2a, 2b, 3a
0
0
2
271
1, 2a, 2b, 3a, 3b
0
0
1
134
1, 2a, 2b, 3a, 3b, 4
0
0
1
34
Table 3.2 surveys the numbers of solutions for the different search depths
and refinements steps, clearly showing the impact of the individual con-
straints on the solution sets. The first row of the table shows that when
no constraints are applied, the synthesis algorithm finds two one-step solu-
tions that solve the workflow composition problem, 427 solutions in depth 2,
almost 47,000 solutions in depth 3 and exceeds the default limit of 1,000,000
solutions in depth 4. The remaining rows document how the incremental re-
finements that are described in the following successively narrow the search
to the actually intended solutions.
In addition to the numbers given in Table 3.2, Figure 3.13 illustrates the
impact of the constraints on the solution space graphically: It shows the
Search WWH ::
Custom Search