Optimized Relative Step Size Random Search (ORSSRS)

Here we’re looking at the 1976 paper “Optimized relative step size random searches” (ORSSRS). The authors build on the earlier FSSRS and ASSRS. FSSRS used a step size of fixed distance to define the hypersphere within which samples would be taken. ASSRS adapts the step size based on the successful and failed samples.  ORSSRS proposes a more advanced method for selecting the step size as the optimization progresses.

  1. Given fitness function “f”
  2. Select a starting point x at random within the solution space.
  3. Let best = x.
  4. Generate vector d, a random vector of length r (within the dimensions of the solution space).
  5. Calculate a new position x from x = best + d.
  6. If f(x) < f(best), replace best with x, replace r with r-δr (reduce the step size), and continue (from step 4) until termination criteria is reached.
  7. Otherwise, reverse the direction of the search by calculating a new position x from x = best – d.
  8. If f(x) < f(best), replace best with x, replace r with r-δr (reduce the step size), and continue (from step 4) until termination criteria is reached.

The user must provide the initial value of r (σ⁰ is used in the paper).

δr r is used in the paper) is given by a complex derivation provided in the paper. I must confess that I did not fully understand the derivation, so I won’t foster any further confusion on your part by attempting a poor explanation here.

References

  • Schrack 1976 – Optimized relative step size random searches – Schrack, G. & Choit, M. Mathematical Programming (1976) 10: 230. Link.