Comparison of approaches

Next: Conclusions and future Up: Case studies Previous: Simulated annealingexperiment

Comparison of approaches

The case studies lead to the following characterizations of each approach:

The heuristically guided and bounded search of VIPÊ is a rather good method, although it has its shortcomings. It is fast enough for the problem definition of the case studies: pagination of a newspaper delivered on fax. However, controlling or changing the heuristics proved rather difficult within the design of VIPÊ . The design of a system guided with heuristic rules that can be easily replaced or continuously adjusted is not a simple task, although it would be a useful feature for an automatic pagination application. If the search heuristics can be clearly separated from the implementation, this approach might be advantageous.

SA1.

In the first SA experiment, the definition of the state space resulted in awkwardly long annealing times for a fax newspaper. Still, considering the size of the state space, the annealing times were understandable. If the problem had been to paginate blocks of fixed size and shape, this approach would have been acceptable. After all, the produced layouts were quite good. In this experiment the selection of material and generation of layout were separated, which may be a desirable characteristic in some problem instances.

SA2.

In the second application of SA, the design of the state space and transitions was more suitable to the given problem, as described in 5.1. The transition replace if overlap achieved in reducing the local "raggedness" (discontinuity of ) of the search space, which enabled considerable improvements of state in the lower temperatures and even in a frozen state.

As compared with SA1, the state space was extended to cover a larger total colume of the solution space, but simultaneously decreased by cutting out a large amount of intermediate states that could not contain solutions---the states with overlapping articles. With a careful selection of the state transitions, a state space with suitable connectivity and shape of the cost function was created. Compared with SA1, the frequency of good solutions was also increased. Given this it is not surprising that the results of SA2 were most promising. The approach has the advantage of being fast (as had the VIPÊ experiment), and it enables continuous continuous control of the objectives of the search via the cost function.

Despite the considerable improvement in speed of the pagination, the SA2 implementation probably would not be quick enough for pagination to take place as part of a user interface of an electronic newspaper, which is generated and viewed interactively. However, since the speed of SA2 was comparable to that of VIPÊ , also SA2 can be used in a newspaper delivered on fax or some other application without dritical efficiency requirements paginating into fixed space from large storage.

It must be emphasized that both SA1 and SA2 were implemented to solve the general layout problem of type 3 (see section 4.1.3), for building the layout with a fixed area and varying material. VIPÊ , on the other hand, was a prototype specifically designed for pagination of editorial material.

Next: Conclusions and future Up: Case studies Previous: Simulated annealingexperiment

Krista Lagus