Procedure: Exchange Algorithm

Description and Background

The exchange algorithm has been used and modified by several authors to construct a \(D\)-optimal and other types of design. Fedorov (1972), Mitchell and Miller (1970), Wynn (1970) , Mitchell (1974) and Atkinson and Donev (1989) study versions of this algorithm. The main idea of all versions is start with an initial feasible design and then greedily modify the design by exchange until a satisfactory design is obtained. The following steps are the general steps for an exchange algorithm.

Inputs

  1. A large candidate set, such as a full factorial design (scaled integer grid) or a spacefilling design.
  2. A initial design chosen, at random, or preferably, a space filling design.
  3. An objective function \(M\), which is based on an optimal design criterion.

Outputs

  1. The optimal or near optimal design \(D=\{x_1,x_2, \cdots, x_n\}\).
  2. The value of the target function at the obtained design

Procedure

  1. Start with the initial \(n\) point design.
  2. Compute the target function \(M\).
  3. General step. Find a set of points of size \(k\) from the current design and replace with another set of \(k\) points chosen from the candidate set. If the value of \(M\), after this exchange, is improved, keep the new design and update \(M\). The set of points removed from the current design can be put back in the candidate set.
  4. Repeat till the stopping rule applies. It may be that after many attempts at a good exchange there is no improvement or only a small improvement in the design. As for global optimisation algorithms it is usual to plot the value of the objective function against the number of improving exchanges, or simply the number of exchanges.