Introduction
  

DEAS is a recently developed non-gradient optimization algorithm by Jong-Wook Kim in 2002. The principle of DEAS is based on the distinct properties of binary strings. If a binary digit, 0 or 1, is appended to any binary string as a least significant bit (LSB), the decoded real number of a new binary string decreases for 0, and increases for 1 compared with that of the original binary string. This property is applied to the perturbation of a current local minimum for discovering an optimal direction vector, and the name ¡®bisectional search (BSS)¡¯ comes from this aspect of dichotomous search.

Like the branch and bound method, BSS alone has the serious drawback of regional limitation. However, simple operations of increment addition (INC) and decrement subtraction (DEC) for a binary string can readily remove the problem, and raise search efficiency. In unidirectional search (UDS) of DEAS, the operations of INC and DEC are iterated while a better optimum is sought in a guided search direction obtained by the previous BSS.

Fig. 1 demonstrates the above principle along with basic terms for a one-dimensional problem whose cost function is unimodal and has a local minimum at 1110b (about 0.33). The blue arrows represent selected transitions in BSS, and the purple arrows stand for consecutive transitions in UDS. Every session consists of single BSS and multiple UDS, and the sessions are iterated as the length of binary strings monotonically increases.
 
Fig. 1 Search aspect of DEAS in a one-dimensional unimodal problem
 
exhaustive DEAS

In multi-dimensional problems, binary strings are heaped up as a binary matrix, while they are concatenated into a string (individual) in the genetic algorithm. Exhaustive DEAS (eDEAS) is classified as a kind of greedy search in that all the members in each neighborhood are evaluated in BSS and UDS. Fig. 2 depicts a session in a two-dimensional problem, whose local minimum exists in a lower right part, with binary matrices. For an optimal direction to be discovered, BSS evaluates the cost function four, or 2, times, and [1 0] is determined as an optimal direction vector (DV) of this session, which is handed over to UDS for further exploration. Then UDS continues to search in three, or 2 - 1 fixed directions per transition by extension vectors (EV) while better solutions are sought. For notational convenience, a binary digit 0 of each EV means that an extension is not occurred in a given direction, and vice versa. Since a current best solution is obtained by moving along the direction of x.an optimal EV after the first transition in UDS is described as [0 1]
 
Fig. 2 Local search aspect of eDEAS in a two-dimensional problem
(solid: basic extension, thick and solid: selected extension, dash-dotted: redundant extension)
Note that, among the second neighborhood in UDS, the matrix A is included again, and is thus evaluated redundantly. This situation also recurs at the fourth neighborhood, related with previous optimal EV¡¯s depicted with thick solid lines in Fig. 2. A common feature of these revisited matrices is that all the digits of the current EVs, whose corresponding digits of the previous optimal DVs equal 1, are simultaneously zero. This redundancy can be removed by a simple redundant check by referring to a masking technique in microprocessors as
If all the bits represented as ¡®X¡¯ (don¡¯t-care term) in the masked result are simultaneously zero, the corresponding EV is regarded as a redundant search direction. Therefore, for example, revisiting EV¡¯s in UDS for [100] are ,[001],[010] and [011] except , [000] as shown in Fig. 3 with red arrows.
 
Fig. 3 Search aspect of eDEAS in a three-dimensional problem
 
univariate DEAS

The eDEAS generates and evaluates almost 2 points in every transition, thus it suffers from a heavy amount of computation, which is quite burdensome in case of n>10. To overcome this problem, researches are being carried out on the univariate DEAS which consumes only 2 function evaluations for further exploration.
 
Global search strategy as a multistart

In searching with DEAS, the whole search space of interest is dynamically divided by a fixed number of grids. It implies that search paths of each binary string are automatically determined according to the cost function landscape unless it is time-variant. That is, if DEAS is applied to any two identical strings, the subsequent search process of DEAS will yield exactly the same search paths. Since this revisit leads to unnecessary computation, it should be detected and intercepted at every instance of starting new sessions. Regarding that DEAS enables UDS to search horizontally as in Fig. 4, search paths of different initial strings or matrices can encounter at some strings or matrices. As soon as a current search path is detected as revisited by a history check function in DEAS, search process is stopped and restarted from an unexplored string or matrix.
 
Fig. 4 Example of revisited search
The simplest way to design the history check function is to save current binary matrix in a lookup table and compare with past data just before starting BSS. This bit-by-bit comparison, however, can cause the problems of storage and computational time. As a solution to this problem, an integer- or real-valued representative for a string concatenated from a matrix is saved in the lookup table as:
Then, every newly assigned value is compared with those of previous optimal matrices whose corresponding row lengths are identical. If the history table is constructed in the fashion of Table 1, which is attained for the Branin function, a new member is horizontally compared with old ones and enrolled in case of no identical values. Note that a revisit has occurred at the fourth restart with the row length of 2, and subsequent values are identical to those of the third restart. Therefore, revisit is efficiently detected and prohibited by the aid of a history table in DEAS.
 
Table 1 History table of the Branin function
Restart no.
1
2
3
4
row

length
1
0
2
1
3
2
10
12
11
11
3
33
44
39
39
4
65
52
71
71
5
657
612
143
143
6
1297
3268
1295
1295
:
:
:
:
:
An additional important feature for global optimization is an escaping scheme. As optimal binary matrices are lengthened, their step lengths decrease exponentially, which means that search points continuously converge to one of local minima. Thus, it can be inferred that a current point falls inside a region of attraction (ROA) of an unacceptable local minimum, when successive cost values do not drop below a predefined acceptable value. For this situation, DEAS commands to escape from a current point and restart, which is similar to the multistart method.

However, it is difficult to theoretically determine the optimal indexes of escaping, which is common to all global optimization methods. DEAS resorts to a kind of heuristic, i.e. surveying the landscape of the cost function by a finite number of trials as a preliminary search. In Fig. 5 are shown the sketch of the preliminary search over the Goldstein-price function, where the row lengths of initial matrices range from 1 to 3 with the maximal added row length of 9, and random restarts are conducted three times for each initial row length.
This brief survey provides many beneficial information; optInitRowLen, rowIndRestart, and costIndRestart. The optInitRowLen means an optimal initial row length by which a global minimum can be discovered. Since step lengths are larger with a smaller row length, a small optInitRowLen means ROA's of global minima spread wide over whole search space. The rowIndRestart and costIndRestart represent optimal indices of a row length and a cost value for restarts by which it is determined to restart or to continue. The rowIndRestart is selected as the minimal row length from which global minima and local minima can be seemingly discriminated, and costIndRestart is an approximately intermediate value between the best and the second-best local minima. These values are closely related to the smoothness, ratios of ROA, and slopes of the cost function currently handled. Therefore, the preliminary search of DEAS additionally provides approximate information of the cost function.
 
Fig. 5 Escaping indexes of DEAS at a preliminary search with the Goldstein-price function
See [J1] for more detail
 
DEAS group
DEAS will be released as one of the following categories
- exhaustive DEAS (eDEAS)
- univariate DEAS (uDEAS)
- modular DEAS (mDEAS)
- randomized DEAS (rDEAS)
 
Copyright ¨Ï2003 by DEAS. All rights reserved......