ارتباط متقابل سودمند در بهینه سازی بین هموارسازی فضای جستجو و جستجوی تصادفی

The effectiveness of the Metropolis algorithm (MA) (constant-temperature simulated annealing) in optimization by the method of search-space smoothing (SSS) (potential smoothing) is studied on two types of random traveling salesman problems. The optimization mechanism of this hybrid approach (MASSS) is investigated by analyzing the exploration dynamics observed in the rugged landscape of the cost function (energy surface). The results show that the MA can be successfully utilized as a local search algorithm in the SSS approach. It is also clarified that the optimization characteristics of these two constituent methods are improved in a mutually beneficial manner in the MASSS run. Specifically, the relaxation dynamics generated by employing the MA work effectively even in a smoothed landscape and more advantage is taken of the guiding function proposed in the idea of SSS; this mechanism operates in an adaptive manner in the de-smoothing process and therefore the MASSS method maintains its optimization function over a wider temperature range than does the MA.

Optimization is a ubiquitous task in various fields of science and engineering and a wide variety of examples can be cited, ranging from finding the lowest-energy configurations of various molecular systems [1] to solving operations-research problems arising from real-life situations [2]. Mathematically, each task is formulated as a problem to find a feasible solution that minimizes a given cost function. Despite such a simple description of the problem, the construction of the solution algorithm with a reasonable computational load is considered to be difficult for many of the important problems. This situation has prompted researchers to develop innovative tools and methodologies, and in this line of work heuristic algorithms to find a good solution whose optimality is not guaranteed have been developed in every research field. In these studies, the fundamental difficulty in the solution of hard optimization problems is considered to come from the complex rugged landscape of the cost function. This is because, in such a mountainous terrain, the approach of iterative improvement like the familiar steepest descent method can only find a locally optimal solution in its basin of attraction in the solution space. Although there have been many attempts to overcome this difficulty, we reconsider here the following two basic strategies among those consisting of the repetition of the neighborhood move in the solution space. The first strategy is that, by allowing a deteriorating move in the neighborhood, one enables the system to escape from a poor basin and to move into a more promising region in the search space. As a typical example of this strategy, we can take a stochastic search approach [3] like simulated annealing (SA) [4], [5], [6] and [7]. The approach of SA is originally based on the idea of equilibrium statistical mechanics and the Metropolis algorithm (MA) [8] for equilibrium sampling is employed as a search method. There, deteriorating moves are allowed probabilistically, and by decreasing the operating temperature, the search range in the cost space is lowered to sample an optimal (or suboptimal) solution. The second strategy is that, by smoothing the terrain of the cost (energy) function, one enables the system to surmount the barriers present in the unsmoothed terrain and to be guided into a low-lying basin in the original landscape. This strategy has been known as the method of search-space smoothing (SSS) [9], [10] and [11] and a similar idea has also been used in the method of potential smoothing (PS) (or the diffusion equation method) [12], [13] and [14]. In the approach of SSS, a smoothed terrain is deformed into the original unsmoothed one in a stepwise manner and a locally optimal solution obtained in one stage is used as an initial solution of the iterative improvement in the next stage. There, the locally optimal solution is expected to be included in a promising basin in the next terrain so that the system settles down to a low-lying state in the original landscape. In other words, one believes that the global structure of the landscape is roughly maintained during smoothing and that the effective size of the productive basin becomes larger with increasing smoothness. (A schematic view of this scenario can be seen in most of the literature on SSS and PS, e.g., Refs. [9], [10], [12] and [14].) These two strategies are in stark contrast in where the improvement is made. It is made to the search rule in the former and to the landscape structure in the latter, and indeed each strategy has been treated separately in the optimization research field. On another front, it is empirically known that such a heuristic strategy can improve its performance in the right combination with other techniques. Then, what about the combination of the present two strategies? In the approach of SSS, as mentioned above, the system is assumed to be guided into a low-lying basin in the repetition of iterative improvement in the de-smoothing process. It is therefore quite natural to have concerns that the randomization caused by the stochastic search rule of SA undermines the advantage of this guiding function [10]. However, if the above assumption is correct, it is desirable for the system to explore lower-lying basins in every smoothed terrain [10]. In this respect, we can expect a positive effect even in a stochastic approach like SA. This is because, in the SA-like approach, the relaxation dynamics observed as downward interbasin transitions play a primary role as an optimizer [15], [16] and [17]. It is, therefore, anticipated that the SA-like approach can enhance the optimizing ability of the SSS method. If this combination actually outperforms its constituents, the elucidation of its optimization mechanism is useful for a fruitful design and implementation of its algorithm and for a good understanding of this hybrid strategy. On this point, one might question the significance of the problem on SA because its method has already been improved in various sophisticated ways. Simulated [18] and parallel [19] and [20] tempering methods, which emulate (randomized) tempering-like process(es), are examples of such improved versions of SA and their upgrade scenario is plausible. However, even such modern approaches are not panaceas within the limited computational resources, and in fact a case showing the superiority of the conventional SA is reported in the relatively recent literature [21]. Moreover, the actual working mechanism of SA and SA-related algorithms can be different from the envisioned optimization scenario [16], [17] and [22]. It is, therefore, reasonable to believe that we are still lacking in the necessary understanding of the function of these algorithms in their finite-time optimization process. With this background in mind, we introduce an SSS algorithm combined with the MA (constant-temperature SA) instead of the iterative improvement method and discuss the effectiveness of this hybrid approach by focusing on the mutual influence between the two strategies. The algorithm is designed for the solution of the traveling salesman problem (TSP) [23] and [24] and coined the MASSS method. The reason for this choice of test bed is that the optimization characteristics of both the SSS and SA methods have been well investigated on this problem. (See, e.g., Refs. [3], [9], [10] and [11] for SSS and Refs. [3], [16] and [24] for SA.) As in the previous studies [16], [17] and [22], the search trajectory is observed as an interbasin transition process by applying the mapping-onto-minima approach used in studies on liquid and glass [25], [26] and [27]. Though time-consuming, this investigation is helpful to directly assess the guiding function, namely, by which the system is guided into a low-lying basin. As shown in Section 3, the relaxation dynamics work effectively also in a smoothed terrain, and this makes it possible to utilize more of the guiding function of the SSS method and to improve its optimization performance. Furthermore, this improvement can be adaptively achieved in the de-smoothing process and therefore the performance is maintained over a wide range of operating temperature for the MA. We thus find a mutually beneficial relationship between the present two basic strategies in the implementation of the MASSS method. Originally, this work is intended neither to improve the existing solution methods nor to propose a novel algorithm. Our aim is to assess the effectiveness of the present hybrid approach and elucidate how it works in its optimization process; therefore, all the algorithms used in our experiment are constructed in the standard way. The remainder of this paper is organized as follows: In Section 2, we give the definition of the test-bed problems and explain the method of our experimental analysis in detail. In Section 3, we show the results of this analysis and discuss the mutual effect between the two strategies. In Section 4, we conclude our study.

Focusing on the mutual influence between smoothing heuristics and stochastic search, we investigated the optimization characteristics of the MASSS method, the combination of the SSS method and the MA, and obtained a clear picture of how this hybrid approach works in its optimization process. Both the SSS method and the MA have a function that makes the system explore lower-lying basins in the solution space, and the mutual enhancement of their respective functions offers better optimization characteristics to an the MASSS method. Specifically, the relaxation dynamics generated by employing the MA work effectively also in a smoothed landscape and take more advantage of the guiding function of the SSS method. Furthermore, this mechanism functions in the smoothed landscape matched with the operating temperature and therefore the MASSS method maintains its performance over a wider temperature range than the MA. The former is the benefit of applying the MA to the SSS method and the latter the benefit in the opposite direction. Although the experimental analysis was performed only for the solution of the TSPs, and for the limited search rule and smoothing function, it is hoped that the present baseline study in the landscape paradigm will be informative to the study and implementation of possible variants.