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.

 

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.

Fixed Step Size Random Search (FSSRS)

In the 1963 paper (Rastrigin, 1963) the author Rastrigin presents an improved version of Random Search.

  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. If f(x) < f(best), replace best with x.
  6. Continue (from step 4) until termination criteria is reached.

The user must choose the radius r.

Later authors propose was to dynamically adjust r. See ASSRS and ORSSRS.

Further Reading

References

  • Rastrigin, L.A (1963), “About Convergence of Random Search Method in Extremal Control of Multi-Parameter Systems” L.A. Rastrigin (mathnet.ru, includes PDF, russian language).

Drift Stall

[W]hen using mutation at a fairly high rate the lower salient genes do not fully converge since the selective pressure acting on these genes is counterbalanced by the disruptive effect of the mutation operator. – Thierens (1998)1

“Drift Stall” or “Convergence Stall” can result from overly high rates of mutation. Thierens (1998)1 credited Rudnick (1992)2 for the observation that where the mutation rate is very high, lower salient genes may be prevented from converging at all, due to the level of noise created by the mutation operator.

The key factor is to ensure that the diversity of the less salient building blocks is preserved long enough in order to buy time for the selection-recombination operators to reach this level of fitness scale. – Thierens (1998)1

 

References

  1. Domino Convergence, Drift, and the Temporal-Salience Structure of Problems – Dirk Thierens, David E. Goldberg, Angela Guimaraes Pereira, 1998
  2. Rudnick M. (1992). Genetic Algorithms and Fitness Variance with an Application to the Automated Design of Artificial Neural Networks. PhD thesis, Oregon Graduate Institute of Science and Technology.

Genetic Drift

[…] in a finite-sized population the proportion of alleles fluctuates due to stochastic sampling errors, so even in the absence of any selective pressure, the genes will eventually become fixated at one particular allele. – Thierens 19981

Genetic Drift (or just “drift”) is the phenomenon of the progressive loss of genetic information among less salient building blocks. While the algorithm is working hard to converge the salient building blocks, the less salient building blocks are also converging. But because they have lower marginal fitness contribution, they converge by chance (“drift”) alone.

Studies suggest that the expected time for a gene to converge due to genetic drift alone is, in very general terms, proportional to the population size.

According to the Domino Convergence model (Thierens 19981), time complexity to fully converge on the optimal solution is linear  to the encoding length l (i.e., O(l)) (only for an algorithm exhibiting constant selection intensity, read Domino Convergence).

In the absence of other factors, the conclusion might be that as the encoding length increases, we must increase the population size proportionately to ensure that genetic drift does not overtake domino convergence. In practical observation, we observe that the rule generally seems to hold, but that the required adjustment is somewhat less than strictly linear.

So, dilettante beware! We might expect to observe that as our encoding length increases, if our effective population size is not adjusted to compensate, we may find ourselves suffering from the effects of genetic drift.

References

  1. Domino Convergence, Drift, and the Temporal-Salience Structure of Problems – Dirk Thierens, David E. Goldberg, Angela Guimaraes Pereira, 1998

Domino Convergence

Building blocks with higher marginal fitness contribution – salient building blocks – converge before those with lower marginal fitness. Moreover, there comes a point in time – and fitness scale – when strong convergence runs out of steam, and low salience building blocks drift to substantial convergence at random with a resulting high probability of error. – Thierens 19981

Domino Convergence refers to the observation that elements (“building blocks”) in an encoding string that more significantly affect the measured objective value (“fitness”) converge earlier.

Thierens 19981 concludes, in the absence of other factors, that time complexity to converge in the case of constant selection intensity is linear (O(l)) to exponential (O(2l)) to the encoding length (l) of the encoding. On the other hand, where selection intensity is proportional to the fitness difference, time complexity to convergence is  exponential (O(2l)) to the encoding length (l).

Proportional selection intensity is exhibited, for example, in genetic algorithms that employ “roulette wheel” selection. Acting on Thierens’ conclusion above, we ought to be tempted to prefer the alternative “tournament” selection approach instead.

References

  1. Domino Convergence, Drift, and the Temporal-Salience Structure of Problems – Dirk Thierens, David E. Goldberg, Angela Guimaraes Pereira, 1998

How to use Windows Error Reporting

How do you use Windows Error Reporting?

Unfortunately, you can’t. It doesn’t work. The documentation is imprecise and convoluted. Try to log in to the various services you’re supposed to use, and you’ll see some error or another. Give up now, and use something else. Unfortunately, you won’t ever get Windows Error Reporting to work for you.

Full Enumeration

The idea of fully enumerating the solution space. In the case of a real-values solution space, full enumeration must be approximated by dividing each dimension into parcels. The size of such divisions must be chosen by the user.

We can generally think of “full enumeration” as being the worst case for performance. However there are a few exceptions. If the solution space is very small, it might make sense to simply fully enumerate the solution space.

A full enumeration search may be trivially performed in a “steady state” fashion, as the results from the search do not affect the search behaviour at all. Full enumeration may outperform some algorithms (such as Random Search) where the algorithm does not benefit from any form of search memory.

Magic Numbers in Microsoft Visual C++

Microsoft Visual C++, in Debug mode, uses some magic numbers to make our lives easier when we attempt to dereference invalid memory. Here’s a list of the ones I’ve found useful. I’ve included some from Google’s V8, since I ran into 0x1baddead0baddeaf this one time.

  • 0xabababab – Marks “no man’s land” guard bytes surrounding heap memory allocated by HeapAlloc().
  • 0xcccccccc – Uninitialized stack memory.
  • 0xcdcdcdcd – Uninitialized heap memory allocated by malloc().
  • 0xbaadf00d – Uninitialized heap memory.
  • 0xfdfdfdfd – Marks “no man’s land” guard bytes surrounding allocated heap memory.
  • 0xfeeefeee – Used by HeapFree() to mark freed heap memory
  • 0xdddddddd – Freed heap memory
  • 0xdeadbeedbeadbeef, 0x1baddead0baddeaf, 0x1baffed00baffedf, 0x1beefdad0beefdaf,0xbadbaddbbadbaddb, 0xbeefdeadbeefdeef, 0xfeed1eaffeed1eaf, 0xdeadbeef, 0xbaddeaf, 0xbaffedf,0xbeefdaf, 0xbeefdeef, 0xbadbaddb, 0xfeed1eaf, 0xbadc0de, 0xca11bac – Memory freed by Google’s V8 Javascript engine. (ref)

See Also