In the modern society, information processing is performed in most fields. The information processing is performed by using a computing device such as a computer. A variety of data is computed and processed to obtain a meaningful result for performing prediction, determination, control, or the like. Optimization processing is one of the important fields of the information processing. For example, the optimization processing is used for a problem to which a solution is to be found for minimizing resources or cost in a certain process, or for maximizing the effect produced by the process. Such a problem is clearly important.
A typical example of the optimization problem is the linear programming. In the linear programming, a solution is to be found to maximize or minimize an evaluation function under a certain constraint. The evaluation function is expressed with a linear sum of a plurality of continuous variables, and the constraint is also expressed with a linear sum. The linear programming is used in a variety of fields, such as production planning of products. In the linear programming, simplex method and interior point method are known as excellent algorithms, and are able to efficiently solve problems even though the problems have more than hundreds of thousands of variables.
On the other hand, many optimization problems involve variables whose values are not continuous but discrete. Examples of the above-described optimization problems include the traveling salesman problem and the knapsack problem. In the traveling salesman problem, there is found a shortest route to travel a plurality of cities sequentially and return to a start point. In the knapsack problem, when different articles are packed in a knapsack, a combination of articles is determined so that a total price of the combination becomes a maximum price. Such problems are called discrete optimization problems or combinational optimization problems, and known as problems difficult to obtain an optimum solution.
A main reason why the discrete optimization problems are difficult to solve is that each variable takes only a discrete value. As a result, any method that continuously changes a variable so that a current state is improved on an evaluation function and reaches an optimum solution does not work. Moreover, another reason is that, in addition to an original optimum value (optimum solution, global solution, global minimum) of the variable, there are many values (local minimum or local maximum, local solutions) which are local extremal values of the evaluation function. For this reason, an exhaustive method is used to reliably obtain an optimum solution, taking a longer calculation time. In many of the discrete optimization problems, the calculation time for determining an optimum solution is expected to exponentially increase with the size of a problem (that is, the number of variables). Such problems are called non-deterministic polynomial (NP) difficult problems in complexity theory. The above-described traveling salesman problem and the knapsack problem are also included in the NP difficult problems.
As described above, reliably determining an optimum solution of the discrete optimization problems is difficult. However, for dealing with practically important discrete optimization problems, some algorithms have been devised which use intrinsic properties of the problems. In many of the discrete optimization problems, since the calculation time for determining an exact solution is expected to exponentially increase as described above, many of the practical solution methods are approximation algorithms. Thus, in those methods, even though an optimum solution is not obtained, an obtained solution of the evaluation function becomes close to the optimum solution.
On the other hand, there are known other approximation algorithms which do not use the properties of problems to solve the problems. Thus, these algorithms deal with a variety of problems. These algorithms are called metaheuristics, and include simulated annealing (SA), genetic algorithm, and neural network. Even though these metaheuristics may be less efficient than the algorithms that ingeniously use the properties of problems, the metaheuristics are expected to obtain a solution faster than the solution algorithms used to obtain an exact solution.
Hereinafter, the simulated annealing will be described.
The simulated annealing is one type of Monte Carlo method, and uses random numbers to stochastically determine a solution. In the following description, there will be described, as an example, a problem to minimize the value of an evaluation function, which is called energy. If the problem was to maximize the value of an evaluation function, the sign of the evaluation function would be changed.
In an initial state, one of discrete values is put into each variable. Here, a current state is represented by a combination of values of variables. Then another state close to the current state is selected. For example, the other state is a state in which only one of the variables is changed. Then it is determined whether the current state will transition to the other state. Specifically, change in energy for the state transition is calculated, and it is stochastically determined based on the calculated energy change, whether the current state will be changed by accepting the state transition, or kept by rejecting the state transition. Here, if an acceptance probability for energy decrease is larger than that for energy increase, the state will change so as to lower its energy on average. In addition, it is expected that the state will transition to a more desirable state as the time elapses. It is also expected that an approximate solution, which gives energy close to the energy given by an optimum solution or an optimum value, may finally be obtained. However, if the state transition was accepted when the energy is to decrease, and if the state transition was rejected when the energy is to increase, the energy would monotonously decrease in general with time, but would not change any more after reaching a local minimum. Since the discrete optimization problems involve many local minimums as described above, the state is often captured by a local minimum which is not close to an optimum value. For this reason, it is important that the acceptance is stochastically determined.
In the simulated annealing, it has been proved that if the acceptance probability for state transition is determined as follows, the state will reach an optimum solution in a limit where the time (the number of iterations) is infinite.
(1) An acceptance probability p for a state transition having a value of energy change (energy decrease) −ΔE is determined by using one of the following functions f ( ).
                              p          ⁡                      (                                          Δ                ⁢                                                                  ⁢                E                            ,              T                        )                          =                  f          ⁡                      (                                          -                Δ                            ⁢                                                          ⁢                              E                /                T                                      )                                              (                  1          ⁢                      -                    ⁢          1                )                                                      f            metro                    ⁡                      (            x            )                          =                              min            ⁡                          (                              1                ,                                  e                  x                                            )                                ⁢                                          ⁢                      (                          Metropolis              ⁢                                                          ⁢              Method                        )                                              (                  1          ⁢                      -                    ⁢          2                )                                                      f            Gibbs                    ⁡                      (            x            )                          =                              1                          1              +                              e                                  -                  x                                                              ⁢                                          ⁢                      (                          Gibbs              ⁢                                                          ⁢              Method                        )                                              (                  1          ⁢                      -                    ⁢          3                )            
Here, T is a parameter called a temperature, and is changed as follows.
(2) As expressed by the following expression, the temperature T is decreased logarithmically with respect to the number t of iterations.
                    T        =                                            T              0                        ⁢                          log              ⁡                              (                c                )                                                          log            ⁡                          (                              t                +                c                            )                                                          (        2        )            
Here, T0 is an initial temperature, and desirably has a sufficiently large value in accordance with a problem to be solved.
When the acceptance probability expressed by the expressions indicated in the above (1) is used, and when the state reaches a stationary state after sufficient iteration, occupation probabilities of states depend on Boltzmann distribution used for expressing a thermal equilibrium state in thermodynamics. In addition, when the temperature is gradually decreased from a high temperature, the occupation probability of a state having a low energy increases. Thus, at a sufficiently low temperature, a low-energy state will be obtained. Since this change is similar to the change obtained when a material is annealed, this method is called simulated annealing. Here, since a state transition which increases energy also occurs stochastically, the state transition corresponds to thermal excitation in physics.
In the simulated annealing, an optimum solution is obtained if the number of iterations is infinite, as described above. In practice, however, since an optimum solution is to be obtained with the finite number of iterations, the optimum solution is not reliably determined. In addition, since the temperature expressed by the expression (2) decreases slowly, the temperature does not decrease sufficiently in a finite time. For this reason, in a practical simulated annealing, the temperature is decreased faster, not logarithmically.
FIG. 13 illustrates a conceptual configuration of an optimization apparatus based on the simulated annealing. Here, although the original simulated annealing generates transition candidates one by one, the following description covers a case where the simulated annealing generates a plurality of transition candidates. This technique can be easily applied to parallel tempering case also.
An optimization apparatus 10 includes a state holding unit 11 which holds a current state S (values of a plurality of state variables). The optimization apparatus also includes an energy calculation unit 12 which calculates energy changes −ΔEi of state transitions from the current state S. The state transitions will occur when the values of the plurality of state variables of the current state S are changed. The optimization apparatus 10 also includes a temperature control unit 13 which controls the temperature T, and a transition control unit 14 which controls the state transition.
The transition control unit 14 uses the temperature T, the energy changes −ΔEi, and random numbers; and stochastically determines which one of the state transitions is accepted, depending on the relative relationship between the energy changes −ΔEi and thermal excitation energy.
The transition control unit 14 includes a candidate generation unit 14a and a transition assessor 14b. The candidate generation unit 14a generates candidates of state transition. The transition assessor 14b stochastically determines whether the candidates of state transition are accepted or not, by using the energy changes −ΔEi of the candidates and the temperature T. The transition control unit 14 also includes a transition determination unit 14c and a random-number generation unit 14d. The transition determination unit 14c determines a candidate to be used, from the accepted candidates. The random-number generation unit 14d generates probability values.
The operation in one iteration is performed as follows. The candidate generation unit 14a generates one or more candidates of state transition (candidate numbers: Ni) from the current state S stored in the state holding unit 11, to next states. The energy calculation unit 12 uses the current state S and the state transition candidates, and calculates energy changes −ΔEi for the state transitions of the candidates. The transition assessor 14b uses the temperature T generated by the temperature control unit 13 and probability values (random numbers) generated by the random-number generation unit 14d; and accepts state transitions with acceptance probabilities expressed by the expressions described in the above (1), depending on the energy changes −ΔEi for the state transitions. The transition assessor 14b then outputs transition acceptances fi, which indicate whether each state transition is accepted or not (hereinafter, whether each state transition is accepted or not may be referred to also as acceptance or rejection on state transition). When a plurality of state transitions is accepted, the transition determination unit 14c randomly selects one of the plurality of state transitions, by using a random number. The transition determination unit 14c then outputs a transition number N of the selected state transition, and a transition acceptance f. When the one state transition is selected, the values of the state variables stored in the state holding unit 11 are updated in accordance with the selected state transition.
The optimization apparatus 10 starts its operation from the initial state, repeats the above-described iteration processes while causing the temperature control unit 13 to lower the temperature, and ends its operation when an end determination condition is satisfied. In the end determination condition, it may be determined whether the predetermined number of iterations is reached, or whether the energy becomes lower than a predetermined value. The optimization apparatus 10 outputs a state obtained when the optimization apparatus 10 ends its operation. In practice, however, since the temperature does not become zero when the finite number of iterations is reached, the occupation probabilities of state depend on Boltzmann distribution even when the optimization apparatus 10 ends its operation. Thus, a solution obtained when the optimization apparatus 10 ends its operation is not necessarily an optimum value or a good solution. For this reason, in a practical method, a state which minimizes the energy at a point in the iteration processes is stored, and outputted at the end of the operation.
FIG. 14 is a block diagram, including a circuit diagram, of the transition control unit based on a typical simulated annealing which generates candidates one by one, that is, a block diagram of a configuration of computation units used for the transition assessor.
The transition control unit 14 includes a random-number generation circuit 14b1, a selector 14b2, a noise table 14b3, a multiplier 14b4, and a comparator 14b5.
The selector 14b2 selects one of the energy changes −ΔEi, calculated for state transition candidates, in accordance with the transition number N which is a random number generated by the random-number generation circuit 14b1; and outputs the selected energy change.
The function of the noise table 14b3 will be described later. The noise table 14b3 may be created in a memory, such as a random access memory (RAM) or a flash memory.
The multiplier 14b4 multiplies a value outputted from the noise table 14b3, with the temperature T; and outputs the product (which corresponds to the above-described thermal excitation energy) of the value and the temperature.
The comparator 14b5 compares the multiplication result outputted by the multiplier 14b4, with the energy change −ΔE selected by the selector 14b2; and outputs a comparison result, as the transition acceptance f.
The transition control unit 14 illustrated in FIG. 14 basically includes the above-described functions, and thus the mechanism to accept a state transition with the acceptance probability, expressed by the expressions of the above (1), will be described.
A circuit which outputs 1 when receiving the acceptance probability p, and outputs 0 when receiving 1-p may be a comparator. The comparator has two input terminals a and b. The comparator outputs 1 when a signal at the input terminal a is larger than a signal at the input terminal b, and outputs 0 when a signal at the input terminal a is smaller than a signal at the input terminal b. Here, the input terminal a receives the acceptance probability p, and the input terminal b receives a uniform random number obtained in an interval of [0,1). Thus, if the acceptance probability p, calculated by using the expressions of the above (1) and depending on the energy change and the temperature T, is received by the input terminal a of the comparator, the above-described function is achieved.
That is, where a symbol f represents the function used by the expressions of the above (1) and a symbol u represents a uniform random number obtained in the interval of [0,1), the above-described function is achieved by a circuit which outputs 1 when f(−ΔE/T) is larger than u.
Alternatively, the same function may be achieved by the following modification. Here, when an identical monotone increasing function is applied to two numbers, the magnitude relationship between the two numbers does not change. Thus, when an identical monotone increasing function is applied to signals at the two input terminals of the comparator, the comparator outputs an identical signal. So, if the inverse function f−1 of the function f is used as the monotone increasing function, the comparator outputs 1 when −ΔE/T is larger than f−1(u). Furthermore, since the temperature T is a positive value, the comparator outputs 1 when −ΔE is larger than Tf−1(u). The noise table 14b3 of FIG. 14 is a conversion table to produce the inverse function f−1(u). The conversion table receives a discrete input value obtained in the interval of [0,1), and outputs a value of one of the following functions.
                                          f            metro                          -              1                                ⁡                      (            u            )                          =                  log          ⁡                      (            u            )                                              (                  3          ⁢                      -                    ⁢          1                )                                                      f            Gibbs                          -              1                                ⁡                      (            u            )                          =                  log          ⁡                      (                          u                              1                -                u                                      )                                              (                  3          ⁢                      -                    ⁢          2                )            
The transition control unit 14 also includes a latch circuit to latch a determination result, and a state machine to generate a timing signal used for the latch circuit; but these components are omitted in FIG. 14 for simplification.
FIG. 15 illustrates a flow of operations of the conventional transition control unit. In the operation flow, one state transition is selected as a candidate (S1); an energy change for the state transition is compared with a product of the temperature and a random number, and thereby the acceptance or rejection on state transition is determined (S2); and the state transition is used if the state transition is accepted, and not used if the state transition is rejected (S3).
As can be seen in the above description, although the simulated annealing is used for general purpose, it has a drawback of taking a long calculation time because the temperature is gradually decreased. In addition, the simulated annealing has another drawback in which decreasing the temperature is difficult to adjust in accordance with a problem to be solved. The latter drawback will be described below with reference to FIG. 16.
In a path of state transition from an initial value to an optimum solution or an approximate solution, there are many local minimums having not good degrees of approximation. To quickly escape from these local minimums, a high temperature will be used to cause a sufficient thermal excitation. At the high temperature, however, since the energy is widely distributed in Boltzmann distribution, there is only a small difference in occupation probability between an optimum solution or an approximate solution at which the energy becomes lower (hereinafter, referred to as a good solution), and a local minimum which has a bad degree of approximation (hereinafter, referred to as a bad solution), and at which the energy becomes higher. As a result, even though one solution quickly escapes from a local minimum, the solution will merely reach one of many bad solutions, thus having less probability to reach a good solution. To increase the occupation probability of a good solution, a low temperature will be used to decrease the thermal excitation energy with respect to an energy difference in occupation probability between a good solution and a bad solution. In this case, however, the decreased thermal excitation energy disadvantageously decreases the possibility to cross a peak of energy in a path, causing almost no change in the state. As countermeasures, an intermediate temperature would be used to cross the peak of energy and slightly increase the difference between the good solution and the bad solution. The intermediate temperature would be changed gradually to gradually increase the occupation probability of the good solution. If the temperature is decreased too slowly, the temperature is not sufficiently decreased in a finite time, and thus fails to increase the occupation probability of the good solution. In contrast, if the temperature is decreased rapidly, the temperature is significantly decreased before the current solution escapes from the local minimum, and thus leaves the solution captured by the bad solution. For this reason, as the temperature is decreased, the original simulated annealing would decrease the rate of change in the temperature, and wait at each temperature until the distribution of energy at each temperature becomes close to Boltzmann distribution.
Thus, in the original simulated annealing, it is desirable that the temperature be slowly decreased, and the decreasing of the temperature be appropriately adjusted in accordance with a problem to be solved, to escape a current solution from a local minimum by using only the thermal excitation caused by the temperature.
Here, one conventional method randomly causes a state transition to escape a current solution from a local minimum.
See, for example, Japanese Laid-open Patent Publication No. 2016-66378.
As described above, when an optimization problem is solved by using the simulated annealing, the calculation time becomes longer because the escape from a local minimum takes a long time. In addition, there are many bad local minimums, as also described above. Thus, even though a state having a local minimum randomly transitions to another state, the state will be captured by one of near bad local minimums again, which fails to shorten the calculation time.
USPTO Backgrounds
USPTO Backgrounds