Adaptive Step Size Random Search (ASSRS)

Adaptive Step Size Random Search (ASSRS) is proposed by Schumer 1968 as an attempt to improve upon FSSRS by dynamically adapting the radius of the hypersphere to be sampled.

The approach is described as follows. Note that this is slightly simplified relative to the source paper.

  1. Given fitness function “f”
  2. Select a starting point x at random within the solution space.
  3. Let best = x.
  4. Sample a new position x within a given hypersphere of a specified radius r around best. That is, randomly select x to be a new point within a specified distance r of best.
  5. Sample a new position y within a given hypersphere of a specified radius r+δr around best. That is, y is chosen from a slightly larger hypersphere than x.
  6. If f(y) < f(x), replace r with r+δr (that is, we slightly increase the step size r).
  7. If the predicate at step 6 fails several times, replace r with r-δr (that is, we slightly reduce the step size r).
  8. If f(x) < f(best), replace best with x.
  9. If f(y) < f(best), replace best with y.
  10. Continue (from step 4) until termination criteria is reached.

The user must choose the initial radius r, as well as δr.

Schrack and Choit later propose a further enhancement, ORSSRS.

References

  • Schumer, M.A.; Steiglitz, K. (1968). “Adaptive step size random search”. IEEE Transactions on Automatic Control13 (3): 270–276. doi:10.1109/tac.1968.1098903.