we have several factors at play here:

- even for quite simple problems their cost-function's hyper-surfaces are rather complex, ridden with very many local minima;

- for the sake of efficiency, the solutions are usually sought in finite time, and all or most unpromising runs are being terminated or pruned;

- and the termination criterion is usually more often than not based on each particular researcher's intuition & art, than hard science - both hard to quantify analytically in a robust and mathematically convincing a manner;

- all the above can be of course hard-coded in a form of some algorithm, but the not-so-rational-part will be still present there in a for of parameters - the deterministic element, and model's weights (like e.g. in ANN) - the random element;

- however, the balance between the to is again a matter of skills and art

- and so is by the way our interpretation of what constitutes: a "more efficient" for each particular solution sought?

- as in any multifaceted approximation many more factors are glided over, and excluded from the model, than those implicitly or even explicitly defined as the ones "responsible" for the studied phenomena;

- the actual choice of the particular random number generator used (assuming that a quality MC methods were assured = a truly bad random generator would be a rather trivial case to rule against it) plays relatively insignificant role IMO, unless the phenomenon studied might be of a truly chaotic nature.

Well to take further on from Jan's point is that it depends on what your doing. If you want the probability to be biased versus unbiased, it will drastically determine what type of generator you use whether pseudo-random or some other class of randomness in the algorithmic sense. For example, if I had put together a "random" algorithm that guarantees an approximation within say 5/2 of the optimal, the assumptions must hold for what is going on. Infact many randomized results can be derandomized to avoid this question by transforming it into some greedy algorithm. Great example is the randomized MAX SAT approximation algorithm, and how if you include a bit of bias, you can actually improve the result. If the sequences are not reflecting the conditions, it will fail to meet the guarantee.

"This answer is taken from chapter 16 in D. Levine, V. R. Brown and V. T. Shirey (eds), Oscillations in Neural Networks, Lawerence Erlbaum and Associates, Publishers."

"Many animal species are faced with the problem of finding sparsely distributed resources that occur (and disappear) dynamically in a huge space. Furthermore the dynamics of these resources are stochastic and probably chaotic in terms of both spatial and temporal distribution. But they are not completely random. The search strategy is called foraging. It involves two interrelated phases which dominate the behavior of the animal based on the amount of knowledge it has regarding the location and timing of the resource. In the absence of knowledge or cues foraging animals adopt a stochastic search pattern that will have a reasonably high likelihood of bringing them into encounters with the resource. With knowledge or cues, the animal switches to a more directed search behavior.

Autonomous agents such as mobile robots may need to have these capabilities in order to find mission-critical objects yet no current algorithmic or heuristic search method adequately addresses this problem. The serendipitous discovery of a quasi-chaotic oscillating neural circuit used to generate motor signals in a mobile robot has led to the development of an autonomous agent search method that resembles foraging search in a number of details.Constraining search to potentially fruitful paths before any useful heuristics are available to the searcher is a problem of general interest in artificial intelligence. Foraging search based on chaotic oscillators may prove useful in a more general way."

Thus I think choosing an appropriate chaotic number generator is the most proper way to make the given meta-heuristic efficient because the chaotic sets have a balanced combination of randomness and determinism . Also according to ergodic property of chaotic systems the quality of solutions may be improved.

@R. - beautifully rounded argument indeed, however... the "appropriate chaotic number generator" might not suffice alone!

Pls. note that e.g. in ANN much of the success depends on sufficiently small learning rates being used, thus the temporal range (in terms of the algorithm steps) of even the very best new random direction, or... even [pretty unlikely, as the very randomness should take care that a gross majority of steps will be sub-optimal indeed] series of such perfectly optimal new directions, will have rather limited final effect.

Much better chance of well utilized "appropriate chaotic number generator" lie in a domain of e.g. genetic/evolutionary algorithms IMO. But even better success rates might stem from a parallel processing of a multitude of ANN-type circuits, all doing exactly the same search independently, together with yet another cascade of a II-nd layer of a bit higher order units supervising and voting on the results of the I-st layer, etc, etc in a truly cognitivistic tradition :) !!