ALGORITHM AND PROGRAM OF THE RANDOM SEARCH METHOD WITH AN ADAPTIVE STEP

N. F. Filipenko

(Presented by the scientific seminar of the Laboratory of Computer Engineering and Automation, Research Institute of Nuclear Physics, Electronics, and Automation)

The problem of finding the minimum of a function \(F(X)\) is formulated as follows: find the vector \(X^*=(x_1^*, x_2^*, \ldots, x_n^*)\) that delivers

\[ \min_{X \in D} F(X) = F(X^*), \]

where \(D\) is the domain of constraints on the variables in the form

\[ f_i(X) \ge 0, \quad \overline{i=1,m}. \]

The case of searching for the maximum of \(F(X)\) is reduced, by replacing \(R(X)=-F(X)\), to the problem of searching for the minimum of \(R(X)\).

Algorithm of the Method

The random search method was first proposed and developed by L. A. Rastrigin [1]. The algorithm of the method can be written in the form of the following recurrent expression:

\[ X^{k+1} = X^k + \Delta X^{k+1}; \quad \Delta X^{k+1} = \begin{cases} S \cdot \xi, & \text{if } F(X^k) < F(X^{k-1});\\ S \cdot \xi - \Delta X^k, & \text{if } F(X^k) \ge F(X^{k-1}). \end{cases} \]

Here \(S\) is the length of the working step in the space of variables; \(\xi\) is the next realization of a random vector uniformly distributed over a hypercube with unit edge and center at the origin of the coordinates.

The stepwise random search method for the minimum of a function was programmed according to the scheme with an adaptive step from [3]. Briefly, the essence of the modification proposed in [3] is as follows.

Trial steps from the base point are carried out in pairs (steps of length \(S\) and \(S \cdot (1+a)\), \(a>0\), are taken). If after \(M_1\) steps no decrease in the objective function \(F(X)\) occurs, then the search step is reduced by a factor of \(K_1\). If, for some step size, the value of the function decreases, then this step size is stored as the nominal one. After \(M_2\) evaluations of the function, a “long step” is carried out, \(K_2\) times greater than the nominal one. If this attempt is successful, then a new, larger value of the nominal step is chosen; if not, the step remains the same.

More details on the algorithm of the method and the results of comparing this method with others can be found in [2].

Program Description

The program was written for the M-20, BESM-4, and M-220 computers. The program uses the IS-2 constants; it does not use drums or tapes. Working cells 0001–0003; the length of the SP and of the working fields is equal to \(\max\{0256,0242+2n\}\). Thus, for \(n>6\) the length of the SP together with the working fields is \(0242+2n\) cells. For \(n \le 6\) the length of the SP is 0256.

The SPAD program is adjusted to any location in the MOZU. This means that the SP may first be recorded starting from any cell \(\alpha\) of the MOZU, for example by the command: \(C\ 010\alpha,\ C+1,0000|\), stored in cell \(C\). Adjustment to the location (from cell \(\alpha\)) is performed automatically after the first call to the SP.

A call to the program is made by the following two lines:

\[ \begin{array}{c|c|c|c|c} x+0 & 0 & 16 & x+1 & \alpha\quad 7610 \,|\\ x+1 & \pi_1\pi_2\pi_3 & n & X^0 & F\quad <\varepsilon> \,| \end{array} \]

Here \(\alpha\) is the cell from which the program is located in the MOZU, and \(\alpha+1\) is the cell into which the programmer must send the computed value \(F(X)\).

Before computing the value \(F(X)\), it is necessary to check the validity of the inequalities \(f_j(X)\ge 0,\ j=\overline{1,m}\). If at least one of the inequalities is not satisfied, then control should be transferred to cell \((F-1)\), sending any nonzero code to cell \((\alpha+2)\). (It should be remembered that before calling the program nothing may be sent to cells \(\alpha+1\) and \(\alpha+2\).) \(F\) is the entry cell into the program for computing \(F(X)\); \(F-1\) is the exit cell from the program for computing \(F(X)\) (it must be free). Thus, after computing the value \(F(X)\) and checking the constraints \(f_j(X)\), the programmer must send the value \(F(X)\) to cell \((\alpha+1)\) and transfer control to cell \((F-1)\); \(n\) is the dimension of the vector of variables \(X\) (specified in octal form); \(X^0\) is the cell starting from which the components of the vector (the initial search point) are located. Moreover, the vector \(X\) must satisfy the conditions \(f_j(X)\ge 0;\ j=\overline{1,m}\); \(<\varepsilon>\) is the cell containing the required error tolerance for checking the termination condition of the minimization process \(F(X)\). The components of \(X^0\) and \(\alpha\) are normalized octal numbers.

The following modes of using signs are provided for various criteria for terminating the minimization process:

a) if \(\pi_2=1\), then the criterion is \(\varepsilon-F(X^k)>0\);

b) if \(\pi_3=1\), then the criterion is \(\varepsilon-\|X^k-X^{k-1}\|>0\);

c) if \(\pi_1=\pi_2=\pi_3=0\), then the criterion is \(\varepsilon-|F(X^k)-F(X^{k-1})|>0\);

d) if \(\pi_1=1\), then the stopping criterion is specified by the programmer (for example, by the number of computations of \(F(X)\)).

In case d), the cell \(<\varepsilon>\) is the entry cell into the block for checking whether the criterion is satisfied in the programmer’s main program (OP). If the criterion is not satisfied and minimization is to be continued, the programmer must transfer control to cell \((\varepsilon-1)\) (which must be free). If the criterion is satisfied, then, if desired, the programmer may transfer control to cell \((\alpha+0153)\) of the SPAD program, where the following final actions are carried out: transfer of the vector \(X_{\min}\) (some approximation to the point \(X^*\)) to the field \(X^0\), \(F(X_{\min}) => \alpha+1\), restoration of \(RA\) of the main program, and return to cell \((x+2)\) of the OP.

When criteria a)–c) are satisfied, the concluding actions are performed automatically.

Working Fields of the Program

$\alpha+0242 \div \alpha+0241+n$—components of the vector $X_{\min}$ (the minimum point at the given search stage); $\alpha+0242+n \div \alpha+0241+2n$—components of the vector $X_{\min}$ (the minimum obtained as a result of one iteration); $X^0 \div X^0+n-1$—components of the vector of the current point.

Method Parameters

Table 1

The purpose of the method parameters (except for $\Delta S$) is described in the method algorithm. All parameters are specified as normalized octal numbers.

Depending on the value of $\Delta S$, the SPAD program operates in two modes: if $\Delta S>S$, then the step in the method is made with normalization by the variables (i.e., the step length for each variable depends on the absolute value of that variable—the larger the value of the variable, the larger the step for it); if $\Delta S>S$, then no normalization is performed. Thus, for large $\Delta S$ there will be no normalization, while for $\Delta S=0$ step normalization will always be performed.

In order to change a certain parameter, it is sufficient, after entering the SPAD program, to place it in the corresponding cell in normalized octal form (before the first call to SPAD from the OP).

Possible Aborts, Cycling, and Some Recommendations

The random-search program may cycle if a minimum of $F(X)$ is found, but the minimization termination criterion is not satisfied (a local minimum has been found, or $\varepsilon$ has been specified incorrectly). It should also be noted that the minimization termination criterion is checked only after a decrease of the objective function. Cycling may occur at the value $\Delta S=0$ if any of the variables is equal to zero, since in this case the step for this variable will be equal to zero.

Cycling can be monitored by cell $(\alpha+0232)$, where the method step is located. In cycling, the step becomes zero.

An abort is possible in cell $(\alpha+0074)$ on command 04 if all components of the vector $X$ are equal to zero.

The minimization process can be monitored by cell $(\alpha+0231)$, where the current $F(X_{\min})$ is located; cell $(\alpha+0230)$ contains the value $F(X^0)$; cell $(\alpha+0233)$ contains the number of computations of $F(X)$.

As can be seen from the call to the SPAD program, the number of variables \(n\) cannot be greater than 63. In principle, however, the dimension of the vector \(X\) may be greater than 63. For this it is sufficient to enter into cell \((a+0007)\) the command \((00;\ <n>,\ldots,2223)\), where \(<n>\) is the number of the cell in which, at the second address, the number of variables must be stored in octal form.

Random-search program

2000   4  72  0000  7610  7521        2056   0  02  2222  2235  0000
2001   2  72  0000  7777  0000        2057   0  36  0000  2061  2073
2002   7  16  0003  0224  0000        2060   0  16  2076  2065  2073
2003   4  72  0000  7610  2157        2061   0  72  0000  2223  0002
2004   4  55  0000  7740  2223        2062   4  03  2241  0000  0001
2005   4  55  0000  7732  2224
2006   4  55  0000  7731  2225        2063   0  01  0001  0002  0002
2007   0  67  2223  0000  2223        2064   1  32  0002  2062  7777
2010   0  14  0114  2225  2225        2065   0  72  0000  2223  2236
2011   4  55  0000  7734  2226        2066   0  13  2212  2213  2212
2012   0  67  2226  0000  0003        2067   0  15  2212  2213  2213
2013   0  14  0114  2223  0001        2070   0  06  0101  2212  0001
2014   0  67  0001  0000  0002        2071   0  02  7761  0001  0001
2015   0  13  2042  2225  2151        2072   0  05  2235  0001  0001
2016   4  55  0000  7712  2241        2073   0  00  0000  0000  0000
2017   0  76  2201  2025  2150
2020   4  55  0000  7711  0000        2074   4  04  2241  0002  0003
2021   0  76  2203  2025  2150        2075   0  05  0001  0003  0001
2022   4  55  0000  7714  0030        2076   0  00  0000  0000  0000
                                             2077   1  32  0002  2066  7777
2023   0  36  2202  2025  2150        2100   0  72  0000  2224  0000
2024   0  00  2204  0000  2150        2101   3  16  2102  0000  7777
2025   4  16  0001  2026  2160        2102   0  01  2233  7761  2233
2026   0  53  0001  7750  2237        2103   0  00  0000  0000  0000
2027   0  01  2237  0000  2237        2104   0  15  0000  2002  0000
2030   0  13  2205  2226  2045        2105   0  76  0000  2116  2002
2031   0  13  2206  0002  2046        2106   0  02  2001  2231  0000
2032   0  13  2207  0003  2076        2107   0  76  0000  2116  0000
2034   0  00  2045  0000  2141        2110   0  72  0000  2223  2241
2035   0  13  2210  0001  2154        2111   0  00  0000  0000  0000
2033   0  13  2045  0002  2111        2112   1  32  0002  2111  7777
2036   0  13  2154  0003  2154        2113   0  00  2235  0000  2232
2037   0  13  2206  0001  2162        2114   0  00  0000  0000  2226
2040   0  13  2211  2223  2171        2115   0  00  2001  0000  2231
2041   0  00  0000  0000  2226        2116   0  05  2232  2214  2235
2042   0  02  0001  0000  0000        2117   0  02  0000  2240  2240
2043   0  00  2215  0000  2232        2120   0  36  0000  2056  0000
2044   0  72  0000  2223  2233        2121   0  55  2241  7740  0000
2045   0  00  0000  0000  0000        2122   0  76  0000  2150  2241
2046   0  00  0000  0000  0000
2047   1  32  0002  2045  7777        2123   0  01  2226  7761  2226
2050   0  72  0000  2224  2234        2124   0  02  2226  2217  0000
2051   3  16  2052  0000  7777        2125   0  36  0000  2130  0000
                                             2126   0  05  2232  2216  2232
2052   0  00  2001  0000  2230        2127   0  00  0000  0000  2226
2053   0  00  2001  0000  2231        2130   0  02  2227  2221  0000

REFERENCES

1. L. A. Rastrigin. Statistical Search Methods. Moscow, “Nauka,” 1968.

2. V. V. Zakharov, N. M. Filipenko. Comparison of random search with a descent scheme on test functions. Avtomatika i vychislitel’naya tekhnika, 1972, No. 1.

3. M. Schumer, K. Steiglitz. Adaptive step size random search. IEEE Trans. Automat. Control, v. 13, No. 3, 1968.