1
Necessary Risk

Il arrive souvent de ne rien obtenir parce que l'on ne tente rien (Often, nothing is gained because nothing is attempted)

Jacques Deval

In using chance to solve a problem, there is always a risk of failure, unless an unlimited number of attempts are permitted: this is rarely possible. The basic idea involved in stochastic optimization is that this risk is necessary, for the simple reason that no other solution is available; however, it may be reduced by carefully controlling the use of random elements. This is generally true, in that a correctly-defined optimizer will produce better results than a purely random search for most test cases. However, this is not always the case, and the ability to identify these "anomalous" situations is valuable.

1.1. No better than random search

Let us take a set of permutation tests. A precise definition is given in the Appendices (section 7.1). Here, note simply that based on one discrete finite function, all of the other functions can be generated by permutations of possible values at each point.

The definition space is E = (0, 1, 2, 3) and the value space is V = (1, 2, 3). A function is therefore defined by its values at the points of E, for example f1 = (1, 3, 2, 2). One possible permutation of this function is f2 = (1, 2, 3, 2); there are 12 such functions in total, each of which is a permutation of the others, shown in the first column of Table 1.1. Each function has a minimum value of 1 (to simplify our discussion, optimization in this case will always be taken to mean minimization). Now, let us consider three iterative algorithms, and calculate the probability that they will find the minimum of each function. These algorithms are all without repetition, and conserve the best position obtained along with the associated value (the ratchet effect). A brief, informal description of these algorithms is given below. For each, the result is given as a pair (x*, f (x* )), where x* is the proposed solution.

1.1.1. Uniform random search

This algorithm, like those which follow, includes an initialization phase, followed by an iteration phase (see section 1.1.). Let us calculate the probability p (t) of finding the solution after t position draws. As there is only one solution, p (1) = 1/4, the probability of not obtaining the solution on the first try is therefore 1 - p (1). In this case, as three nonsampled permutations remain, the probability of obtaining the solution on the second try is 1/3. Thus, the probability of obtaining the solution on the first or second try is p (2) = p (1) + (1 - p (1)) 13 = 1/4 + 3/ 4 1/ 3 = 1/2. Similarly, the probability of obtaining the solution on the first, second or third try is p (3) = p (2) + (1 - p (2) 1/2) = 3/4. Evidently, as the algorithm is without repetition, the probability of having found the solution on the fourth try is 1, as an exhaustive search will have been carried out.

Algorithm 1.1. Random search without repetition

Initialization

1. - Draw a position x* at random, following a uniform distribution (each position has the same selection probability).

Iterations

As long as the STOP criterion (for example a maximum number of iterations) has not been reached:

1. - draw a position x at random from the unsampled population;
2. - if f (x) < f (x* ), then replace x* by x.

1.1.2. Sequential search

This method consists of drawing positions one by one, not at random (without repetition), but in a predefined order, for example position 1, position 2, etc. To calculate p (t), each function must be considered individually. For f4 = (3, 1, 2, 2), for example, a solution will definitely be found after two tries, compared to a probability of 1/2 using the previous method.

However, the opposite situation also occurs, for example for f6 = (3, 2, 2, 1). After two tries, the solution can not be found, as the random method may find it, with a probability of 1/2. Overall, this method is therefore equivalent to the previous method in terms of probabilities p (t). Improvements are thus required.

1.1.3. Partial gradient

Using this method, the first two positions are drawn sequentially. Next, if the two values obtained are decreasing, the sequential approach is retained, as the "direction" of the search appears to be correct. Otherwise, positions are drawn at random from the remaining population. This means that differences from the previous method will only emerge at draw p (3). Once again, each function must be examined individually for calculation purposes. Take, for example, a function such as f6 = (3, 2, 2, 1). The first two draws give results of 3 and 2. As the direction appears promising, the third position is drawn: the value is 2. This is not the minimum, as p (3) = 0. With a function such as f9 = (2, 2, 1, 3), there is no clear preferred direction, and so the third point is drawn at random from the two remaining points, giving a probability of success of 1/2.

The probabilities of success for these three methods, p (t) for t = 1, 2, 3, using the 12 function test case defined above, are given in Table 1.1. Naturally, all of these algorithms obtain the solution with the same probability, 1 (certainty), after four attempts, as they are repetition-free. However, their average performance will not be necessarily identical after one, two or three attempts. The partial gradient algorithm, which is slightly more sophisticated, might be expected to be somewhat more efficient; it is the only method which has a chance of finding a solution to f10 or f11 after three attempts. However, success is not guaranteed for f9 and f12. Finally, as demonstrated in the final line of the table, the three algorithms give the same average performance over the set of test cases.

Table 1.1. Permutation test cases. Probability of success after one, two and three attempts. The three algorithms are repetition-free and present the same average performance, as the conditions of the No Free Lunch Theorem (NFLT) are fulfilled

One attempt Two attempts Three attempts Random Seq. Rand. Seq. Rand. Seq. Grad. f1 = (1, 3, 2, 2) 1/4 1 1/2 1 3/4 1 1 f2 = (1, 2, 3, 2) 1/4 1 1/2 1 3/4 1 1 f3 = (1, 2, 2, 3) 1/4 1 1/2 1 3/4 1 1 f4 = (3, 1, 2, 2) 1/4 0 1/2 1 3/4 1 1 f5 = (3, 2, 1, 2) 1/4 0 1/2 0 3/4 1 1 f6 = (3, 2, 2, 1) 1/4 0 1/2 0 3/4 0 0 f7 = (2, 1, 3, 2) 1/4 0 1/2 1 3/4 1 1 f8 = (2, 1, 2, 3) 1/4 0 1/2 1 3/4 1 1 f9 = (2, 2, 1, 3) 1/4 0 1/2 0 3/4 1 1/2 f10 = (2, 2, 3, 1) 1/4 0 1/2 0 3/4 0 1/2 f11 = (2, 3, 2, 1) 1/4 0 1/2 0 3/4 0 1/2 f12 = (2, 3, 1, 2) 1/4 0 1/2 0 3/4 1 1/2 Average 1/4 1/4 1/2 1/2 3/4 3/4 3/4

This is due to the fact that the conditions of the NFLT [WOL 97, IGE 03] are met. Without going into the mathematical formalization, these conditions are:

1. - finite discrete definition space;
2. - finite discrete value space;
3. - set of test cases closed under permutations (c.u.p.).

Under these conditions, any repetition-free algorithm, no matter how sophisticated, will present the same average performance in terms of random search, however performance is measured. Note that the first two conditions are necessarily fulfilled if calculations are carried out digitally, as a computer always has a limited number of bytes, and thus the numbers which may be represented are limited. This means that an algorithm can only out-perform random search methods in a...