Optimization apparatus and control method thereof

Abstract

A transition control unit detects, when stochastically determining based on a temperature, energy changes, and a random number whether to accept any of a plurality of state transitions according to a relative relationship between the energy changes and thermal excitation energy, a minimum value among the energy changes. The transition control unit then subtracts, when the minimum value is positive, an offset obtained by multiplying the minimum value by a value M that is greater than 0 and less than or equal to 1 from each of the energy changes corresponding to the plurality of state transitions.

Claims

1. An optimization apparatus for solving an optimization problem by using simulated annealing, the optimization apparatus comprising: a state storage circuit configured to hold values of a plurality of state variables included in an evaluation function that represents energy; a calculation circuit configured to calculate each amount of change in energy for a plurality of state transitions that occur in response to change of the values of the plurality of state variables respectively, and configured to output the each amount of change in energy; a transition controller configured to receive the each amount of change in energy, determine a minimum value among the each amount of change in energy for the plurality of state transitions, calculate first values by subtracting an offset from the each amount of change in energy, and when the minimum value is positive, stochastically determine based on a temperature, the first values, and a random number whether to accept any of the plurality of state transitions and when the minimum value is 0 or less, stochastically determine based on the temperature, the each amount of change in energy, and the random number whether to accept any of the plurality of state transitions, the offset being obtained by multiplying the minimum value by a second value that is greater than 0 and less than or equal to 1; and a temperature controller configured to gradually drop the temperature used by the transition controller, the transition controller causes the state storage circuit to update any of the values of the plurality of state variables based on a state transition among the plurality of state transitions when the state transition is accepted.

2. The optimization apparatus according to claim 1, wherein the transition controller controls the offset such that an acceptance probability of a state transition corresponding to the minimum value indicates 1.

3. The optimization apparatus according to claim 1, wherein the transition controller includes: a minimum value detection circuit configured to detect the minimum value; a first arithmetic circuit configured to calculate the offset; a second arithmetic circuit configured to calculate the first values by subtracting the offset from the each amount of change in energy corresponding to the plurality of state transitions; a first selector configured to output, based on a selection signal, the each amount of change in energy or the first values calculated by the second arithmetic circuit; and a selection signal generation circuit configured to generate the selection signal, which causes the first selector to select the each amount of change in energy when the minimum value is 0 or less and to select the first values calculated by the second arithmetic circuit when the minimum value is a positive value.

4. The optimization apparatus according to claim 3, wherein the transition controller further includes: a second selector configured to select, based on the random number, a first output value about a first state transition from output values of the first selector about the plurality of state transitions; a storage circuit configured to output a value of an inverse function of a function that represents acceptance probabilities of the plurality of state transitions, each of the acceptance probabilities being represented by a Metropolis method or a Gibbs method based on the random number; a multiplier configured to output the thermal excitation energy represented by a product of the value of the inverse function and the temperature; and a comparator configured to output a determination result indicating whether to accept the first state transition, the determination result being represented by a value corresponding to a comparison result between the first output value selected by the second selector and the thermal excitation energy.

5. The optimization apparatus according to claim 3, wherein the transition controller further includes: a storage circuit configured to output a value of an inverse function of a function that represents acceptance probabilities of the plurality of state transitions, each of the acceptance probabilities being represented by a Metropolis method or a Gibbs method based on the random number; a multiplier configured to output the thermal excitation energy represented by a product of the value of the inverse function and the temperature; a comparator configured to output determination results respectively indicating whether to accept the plurality of state transitions, each of the determination results being represented by a value corresponding to a comparison result between an output value of the first selector about a corresponding one of the plurality of state transitions and the thermal excitation energy; and a transition number determination circuit configured to preferentially select a first state transition accepted among the plurality of state transitions based on the determination results and the random number and output a number of the first state transition and a determination result corresponding to the first state transition.

6. A control method of an optimization apparatus for solving an optimization problem by using simulated annealing, the control method comprising: holding, by a state storage circuit of the optimization apparatus, values of a plurality of state variables included in an evaluation function that represents energy; calculating, by a calculation circuit of the optimization apparatus, each amount of change in energy for each of a plurality of state transitions that occur in response to change of the values of the plurality of state variables respectively, outputting, by the calculation circuit, the each amount of change in energy; receiving, by a transition controller of the optimization apparatus, the each amount of change in energy, determining, by the transition controller, a minimum value among the each amount of change in energy for the plurality of state transitions, calculating, by the transition controller, first values by subtracting an offset from the each amount of change in energy, and when the minimum value is positive, stochastically determining, by the transition controller, based on a temperature, the first values, and a random number whether to accept any of the plurality of state transitions and when the minimum value is 0 or less, stochastically determining, by the transition controller, based on the temperature, the each amount of change in energy, and the random number whether to accept any of the plurality of state transitions, the offset being obtained by multiplying the minimum value by a second value that is greater than 0 and less than or equal to 1; and gradually dropping, by a temperature controller of the optimization apparatus, the temperature used by the transition controller, the transition controller causes the state storage circuit to update any of the values of the plurality of state variables based on a state transition among the plurality of state transitions when the state transition is accepted.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 illustrates an example of a transition control unit of an optimization apparatus according to a first embodiment;

(2) FIG. 2 illustrates an example of a minimum value detection circuit;

(3) FIG. 3 illustrates an example of an energy distribution with respect to states;

(4) FIG. 4 illustrates an example of the probability of acceptance of an individual state transition with Hamming distance 1 at a local solution;

(5) FIG. 5 illustrates an example of application of offsets to energy changes by a transition control unit of an optimization apparatus according to a second embodiment;

(6) FIG. 6 illustrates an example of the transition control unit of the optimization apparatus according to the second embodiment;

(7) FIG. 7 illustrates an example of a transition number determination circuit;

(8) FIG. 8 illustrates an example of a selection circuit unit;

(9) FIG. 9 illustrates an example of a selection circuit;

(10) FIG. 10 illustrates examples of indexes to be generated;

(11) FIG. 11 illustrates an example of a transition control unit that increases a transition acceptance probability by a certain offset increment;

(12) FIG. 12 illustrates a first example of change of a state transition acceptance probability when a transition control unit according to a comparative example is used;

(13) FIG. 13 illustrates a second example of change of the state transition acceptance probability when the transition control unit according to the comparative example is used;

(14) FIG. 14 illustrates examples of software simulation results based on simulated annealing performed by using the transition control units illustrated in FIGS. 6 and 11;

(15) FIG. 15 illustrates a conceptual configuration of an optimization apparatus based on simulated annealing;

(16) FIG. 16 is a circuit-level block diagram illustrating a configuration example of a transition control unit according to a conventional example, focusing on an arithmetic portion needed for a transition acceptance determination unit;

(17) FIG. 17 is a flowchart illustrating an operation of the transition control unit according to the conventional example; and

(18) FIG. 18 illustrates a concept of state occupation probabilities based on simulated annealing.

DESCRIPTION OF EMBODIMENTS

(19) Embodiments will be described below with reference to the accompanying drawings, wherein like reference characters refer to like elements throughout.

First Embodiment

(20) FIG. 1 illustrates an example of a transition control unit in an optimization apparatus according to a first embodiment. The same elements as those in the transition control unit 14 illustrated in FIGS. 15 and 16 are denoted by the same reference characters, and descriptions thereof will be omitted as appropriate.

(21) As illustrated in FIG. 1, the transition control unit 20 includes a minimum value detection circuit 21, a multiplication circuit 22, an addition circuit 23, a selection signal generation circuit 24, and a selector 25 added to the circuit portion that realizes the functions of the transition acceptance determination unit 14b illustrated in FIG. 15. The other portions of the transition control unit 20 are the same as the transition control unit 14 illustrated in FIG. 16.

(22) When at least one of the values of a plurality of state variables has changed and at least one state transition from the current state has occurred, the minimum value detection circuit 21 receives an energy change {ΔE.sub.i} of an individual state transition. Next, the minimum value detection circuit 21 detects a minimum value ΔE.sub.min of the energy changes {ΔE.sub.i} of the state transitions.

(23) The multiplication circuit 22 is an arithmetic circuit that outputs values (MΔE.sub.min) each of which is obtained by multiplying the minimum value ΔE.sub.min by a value M (0<M≤1).

(24) The addition circuit 23 is an arithmetic circuit that subtracts an individual value MΔE.sub.min as an offset from the energy changes {ΔE.sub.i} of the state transitions (adds −MΔE.sub.min to {ΔE.sub.i}). A subtraction circuit may be used instead of the addition circuit 23.

(25) The selection signal generation circuit 24 generates a selection signal sign. When the minimum value ΔE.sub.min is 0 or less, the selection signal generation circuit 24 generates a selection signal sign (for example, 0) that causes the selector 25 to select the energy changes {ΔE.sub.i} of the state transitions. When the minimum value ΔE.sub.min is greater than 0, the selection signal generation circuit 24 generates a selection signal sign (for example, 1) that causes the selector 25 to select the values calculated by the addition circuit 23.

(26) Based on the selection signal sign, the selector 25 selects and outputs the energy changes {ΔE.sub.i} of the state transitions or the values calculated by the addition circuit 23, namely, {ΔE.sub.i}−MΔE.sub.min. The values outputted by the selector 25 are supplied to the selector 14b2. When the selector 25 selects and supplies the energy changes {ΔE.sub.i} to the selector 14b2, the selector 14b2 selects an energy change ΔE corresponding to a transition number N from the energy changes {ΔE.sub.i}, inverts the sign of the selected energy change ΔE, and outputs −ΔE. When the selector 25 selects and supplies the energy changes ({ΔE.sub.i}−MΔE.sub.min) obtained by subtracting the offset MΔE.sub.min from the energy changes {ΔE.sub.i} to the selector 14b2, the selector 14b2 selects an energy change ΔE−MΔE.sub.min corresponding to the transition number N. Next, the selector 14b2 inverts the sign of the energy change ΔE−MΔE.sub.min and outputs −ΔE+MΔE.sub.min.

(27) When the comparator 14b5 is configured to output 1 when the energy change ≥Tf.sup.−1(u), the selector 14b2 does not need to invert the sign as described above.

(28) FIG. 2 illustrates an example of the minimum value detection circuit.

(29) For example, the minimum value detection circuit 21 is formed by a plurality of stages of two-input minimum value detection circuits arranged in the form of a tournament. Each of the two-input minimum value detection circuits 21a1, 21a2, . . . , 21am in the first stage is supplied with energy changes corresponding to state transitions of two state variables among the energy changes {ΔE.sub.i} of the state transitions. For example, among the n state variables, energy changes (ΔE.sub.1 and ΔE.sub.2) corresponding to the state transitions of the first and second state variables are supplied to the two-input minimum value detection circuit 21a1. The two-input minimum value detection circuit 21a1 outputs the smaller one of the two energy changes (ΔE.sub.1 and ΔE.sub.2).

(30) Each of the two-input minimum value detection circuits is realized by, for example, a comparison circuit and a selector. FIG. 2 illustrates a circuit example of the two-input minimum value detection circuit 21am. The two-input minimum value detection circuit 21am includes a comparison circuit 21am1 and a selector 21am2. The comparison circuit 21am1 compares the two energy changes (ΔE.sub.n−1 and ΔE.sub.n) supplied thereto and outputs 0 when ΔE.sub.n−1<ΔE.sub.n and outputs 1 when ΔE.sub.n<ΔE.sub.n−1. The selector 21am2 outputs ΔE.sub.n−1 when 0 is outputted by the comparison circuit 21am and outputs ΔE.sub.n when 1 is outputted by the comparison circuit 21am.

(31) Each of the two-input minimum value detection circuits in the second and subsequent stages outputs the smaller one of the energy changes outputted by the two two-input minimum value detection circuits in the previous stage. For example, the two-input minimum value detection circuit 21b in the second stage selects and outputs the smaller one of the energy changes outputted by the two-input minimum value detection circuits 21a1 and 21a2 in the previous stage.

(32) In the case of this minimum value detection circuit 21, the energy change outputted by the two-input minimum value detection circuit 21c in the last stage is the minimum value ΔE.sub.min.

(33) By using the transition control unit 20 as described above, the acceptance probability of the state transition at a local solution is increased, and escaping from the local solution is accelerated. The reason will hereinafter be described.

(34) FIG. 3 illustrates an example of an energy distribution with respect to states. In FIG. 3, the horizontal axis represents states (combinations of values of state variables), and the vertical axis represents the energy.

(35) FIG. 3 illustrates a state (an optimal solution) in which the energy represents the minimum value and a state (a local solution) in which the energy represents a locally minimum value, which is not the minimum value.

(36) As expressed by the above formulas 1-1 to 1-3, as the temperature decreases or as the energy change increases (positively), the state transition acceptance probability decreases.

(37) FIG. 4 illustrates an example of the probability of acceptance of an individual state transition with Hamming distance 1 at a local solution. In FIG. 4, the horizontal axis represents state variables s.sub.i as state transition candidates, and the vertical axis represents the acceptance probabilities of the individual state transitions. A waveform 30a indicates the acceptance probabilities that the individual state transitions with Hamming distance 1 at a local solution are accepted (an individual state transition in which one of the values of the state variables s.sub.1 to s.sub.n changes). In the case of the waveform 30a, the acceptance probabilities are much smaller than 1. Thus, a state transition is not likely to occur, and it takes time to escape from the local solution.

(38) As illustrated in FIG. 4, by adding a value (MΔA) obtained by multiplying a difference ΔA between the maximum value of the acceptance probability of the waveform 30a and 1 by M (0<M≤1) to the individual state transition acceptance probabilities, the acceptance probabilities are appropriately increased without excessively increasing the state transition acceptance probabilities. A waveform 30b indicates the acceptance probabilities when ΔA is added to the acceptance probabilities indicated by the waveform 30a (namely, when M=1), and a waveform 30c indicates the acceptance probabilities when 0.5ΔA is added to the acceptance probabilities indicated by the waveform 30a (namely, when M=0.5).

(39) As expressed by formulas 1-1 to 1-3, as the smaller the energy change is, the greater the state transition acceptance probability will be. When the energy change is 0 or less, the acceptance probability reaches the maximum value (=1). Thus, among the energy changes {ΔE.sub.i} of the state transitions, when the minimum value ΔE.sub.min is positive, by subtracting a value (MΔE.sub.min) obtained by multiplying the minimum value ΔE.sub.min by M from the individual state transition energy changes {ΔE.sub.i}, the acceptance probabilities are increased, as illustrated in FIG. 4.

(40) FIG. 5 illustrates an example of application of offsets to energy changes by a transition control unit of an optimization apparatus according to a second embodiment. In FIG. 5, the horizontal axis represents state variables s.sub.i as state transition candidates, and the vertical axis represents ΔE.

(41) A waveform 31a indicates an example of the energy changes {ΔE.sub.i} of state transitions at a local solution. In the case of the waveform 31a, by subtracting as an offset a value (MΔE.sub.min) obtained by multiplying the minimum value ΔE.sub.min by M from the energy changes {ΔE.sub.i} of individual state transitions, the acceptance probabilities are increased as described above. A waveform 31b indicates energy changes when the minimum value ΔE.sub.min is subtracted from the energy changes {ΔE.sub.i} indicated by the waveform 31a (namely, when M=1). When M=1, the minimum value of the energy changes ΔE indicated by the waveform 31b reaches 0, and the acceptance probability of the state transition corresponding to the minimum value reaches 1. In addition, a waveform 31c indicates energy changes when 0.5ΔE.sub.min is subtracted from the energy changes {ΔE.sub.i} indicated by the waveform 31a (namely, M=0.5).

(42) The convergence theorem of simulated annealing indicates that a good result is obtained if whether to accept an individual state transition is determined in accordance with the state transition probability of a Metropolis method or a Gibbs method. Since the probabilities of state transitions are very small at local solutions, selection of a transition candidate is performed many times, and the branch ratio of the subsequent state transitions is proportional to the transition probability of a Metropolis method or Gibbs method. Thus, if the transition control unit increases the absolute values of the acceptance probabilities of the individual state transitions while maintaining the relative ratio of these acceptance probabilities, the branch ratio of the individual state transitions is maintained. Thus, the transition control unit is able to shorten the time for which the state is stuck at a local solution, without negatively affecting the convergence. As a result, the calculation time is shortened.

(43) As described above, by subtracting MΔE.sub.min as an offset from the energy changes {ΔE.sub.i} of the individual state transitions, the transition control unit is able to increase the absolute values of the acceptance probabilities while maintaining the relative ratio of the acceptance probabilities of the individual state transitions as illustrated in FIG. 4. Thus, the transition control unit is able to shorten the time for which the state is stuck at a local solution, without negatively affecting the convergence. As a result, the calculation time is shortened.

(44) In simulated annealing in which the energy to be optimized is expressed by an ising model and in optimization based on a Boltzmann machine almost equivalent to the simulated annealing, a method for generating transition candidates and calculating the energy changes associated with state transitions will briefly be described.

(45) An ising model is a model that represents a system formed by N spins that interact with each other. An individual spin s.sub.i (corresponding to an individual state variable described above) is represented by a binary value of ±1. The energy in the system is expressed by the following formula 4.

(46) $\begin{array}{cc}E=\frac{1}{2}\underset{i,j}{\overset{}{.Math.}}{J}_{i,j}{s}_i{s}_j+\underset{i}{\overset{}{.Math.}}{h}_i{s}_i& \left(4\right)\end{array}$

(47) In formula 4, J.sub.i,j represents an interaction coefficient between spins s.sub.i and s.sub.j, and h.sub.i represents an external magnetic field coefficient, which is a bias value in the system.

(48) A state transition candidate from the current state to the next state is a single spin flip, and there are N candidates. Thus, as the transition candidates, the number of a single spin that is flipping or a group of the numbers of a plurality of spins that are flipping may be generated.

(49) Change of the energy associated with a flip of the i-th spin is expressed by the following formula 5.

(50) $\begin{array}{cc}\Delta E_i=-2s_i\frac{\partial E}{\partial s_i}=-2s_i\left(\underset{j}{\overset{}{.Math.}}{J}_{i,j}{s}_j+h_i\right)& \left(5\right)\end{array}$

(51) In the following formula 6, F.sub.i referred to as a local field value represents the rate of change of the energy associated with a flip of an individual spin.

(52) $\begin{array}{cc}{F}_i=\underset{j}{\overset{}{.Math.}}{J}_{i,j}{s}_j+h_i& \left(6\right)\end{array}$

(53) Since whether to accept the state transition is determined based on change of the energy, basically, change of the energy is calculated from the local field value, instead of calculating the energy itself. When the state corresponding to the lowest energy obtained as the output is used, the energy is obtained by calculating change of the energy from the local field value and accumulating the results.

(54) In addition, the following mathematical formula is obtained.

(55) $\begin{array}{cc}\frac{\partial }{\partial s_j}{F}_i=J_{i,j}& \left(7\right)\end{array}$

(56) Thus, there is no need to recalculate the local field value from a matrix operation every time. Only the amount of change due to a flip of a spin associated with a state transition is added. Thus, the state storage unit 11 and the energy calculation unit 12 illustrated in FIG. 15 are realized by relatively simple arithmetic circuits such as an N-bit register that holds the values of the N spins, an adder, and an exclusive or.

(57) In addition, an optimization method based on a Boltzmann machine used in a neural network is the same as the simulated annealing using an ising model with the exception that an individual state variable corresponding to an individual spin is indicated by a binary value (0, 1). The energy, the energy change, and the local field value in a Boltzmann machine are expressed by the following formulas 8 to 10.

(58) $\begin{array}{cc}E=\frac{1}{2}\underset{i,j}{\overset{}{.Math.}}{J}_{i,j}{s}_i{s}_j+\underset{i}{\overset{}{.Math.}}{h}_i{s}_i& \left(8\right)\\ \Delta E_i=\left(1-2s_i\right)\frac{\partial E}{\partial s_i}=\left(1-2s_i\right)\left(\underset{j}{.Math.}{J}_{i,j}{s}_j+h_i\right)& \left(9\right)\\ F_i=\underset{j}{\overset{}{.Math.}}{J}_{i,j}{s}_j+h_i& \left(10\right)\end{array}$

(59) In many cases, a neuron in a Boltzmann machine corresponds to a spin in an ising model.

(60) As described above, simulated annealing using an ising model is equivalent to simulated annealing using a Boltzmann machine. Thus, these simulated annealings are mutually convertible.

(61) In simulated annealing using a Boltzmann machine (and simulated annealing using an ising model), only one state variable changes in association with a state transition, the energy change corresponding to this change is previously calculable by using a local field value. Thus, in FIG. 1, an implementation example in which previously calculated energy changes are selected based on generation of transition candidates is illustrated. However, in a non-Boltzmann machine, there are cases where transitions in which a plurality of state variables change need to be considered. In these cases, an implementation in which needed energy changes after generation of transition candidates are calculated could be more advantageous.

Second Embodiment

(62) FIG. 6 illustrates an example of the transition control unit of the optimization apparatus according to the second embodiment. The same elements as those in the transition control unit 20 illustrated in FIG. 1 are denoted by the same reference characters, and descriptions thereof will be omitted.

(63) The transition control unit 40 illustrated in FIG. 6 does not include the selector 14b2, and the output from a selector 25a is supplied to a non-inverting input terminal of a comparator 14b5. In addition, an output terminal of the comparator 14b5 is connected to a transition number determination circuit 41.

(64) As in the selector 25, the selector 25a selects, based on a selection signal sign, the energy changes {ΔE.sub.i} of the respective state transitions or the values calculated by an addition circuit 23, namely, the energy changes {ΔE.sub.i}−MΔE.sub.min obtained by subtracting an offset from energy changes {ΔE.sub.i}. Next, the selector 25a inverts the signs of the selected energy changes and outputs the energy changes.

(65) The comparator 14b5 outputs comparison results, each of which is a comparison result between an individual −{ΔE.sub.i} or −{ΔE.sub.i}+MΔE.sub.min and a product (corresponding to thermal excitation energy) outputted by the multiplier 14b4, as transition determination results {f.sub.i}. For example, assuming that the energy change associated with a state transition of the k-th state variable s.sub.k is denoted by ΔE.sub.k, when −ΔE.sub.k or −ΔE.sub.k+MΔE.sub.min is greater than the product outputted by the multiplier 14b4, the transition determination result f of the state variable s.sub.k indicates 1. When −ΔE.sub.k or −ΔE.sub.k+MΔE.sub.min is less than the product outputted by the multiplier 14b4, the transition determination result f of the state variable s.sub.k indicates 0.

(66) When the comparator 14b5 is configured to output 1 when the energy change ≤Tf.sup.−1(u), the selector 25a does not need to invert the sign as described above.

(67) The transition number determination circuit 41 preferentially selects, based on the transition determination results {f.sub.i} of the individual state transitions outputted by the comparator 14b5, a state transition determined to be accepted by the comparator 14b5 and outputs the transition number N and the transition determination result f of the selected state transition.

(68) Hereinafter, a circuit example of the transition number determination circuit 41 when the number of state variables is 1,024 will be described. The following description assumes that the comparator 14b5 outputs 1 as a transition determination result {f.sub.i} when the comparator 14b5 determines to accept a state transition and outputs 0 otherwise.

(69) FIG. 7 illustrates an example of the transition number determination circuit.

(70) The transition number determination circuit 41 includes a noise generation circuit 50 and selection circuit units 51a1, 51a2, . . . , 51a32, and 52.

(71) The noise generation circuit 50 generates and outputs 5-bit random numbers rd1 and rd2 as noise values. Different seeds (initial values) are used for the random numbers rd1 and rd2. For example, a linear feedback shift register (LFSR) or the like may be used as the noise generation circuit 50.

(72) Each of the selection circuit units 51a1 to 51a32 receives 32 state transition determination results {f.sub.i} of the 1,024 transition determination results {f.sub.i}. Each of the selection circuit units 51a1 to 51a32 selects and outputs one of the 32 transition determination results based on the 5-bit random number rd1. In addition, each of the selection circuit units 51a1 to 51a32 generates and outputs a 5-bit index that indicates the one transition determination result selected from the respective 32 state transition determination results.

(73) The selection circuit unit 52 receives the transition determination results and the 5-bit indexes outputted from the selection circuit units 51a1 to 51a32. Next, based on the transition determination results, the indexes, and the 5-bit random number rd2, the selection circuit unit 52 selects and outputs one transition determination result f of the 32 transition determination results and generates and outputs a 10-bit transition number N.

(74) FIG. 8 illustrates an example of a selection circuit unit.

(75) In FIG. 8, an example of the selection circuit unit 51a1 is illustrated. Each of the selection circuit units 51a2 to 51a32 is also realized by the same circuit as that of the selection circuit unit 51a1.

(76) The selection circuit unit 51a1 includes selection circuits 60a to 60e. The selection circuit unit 51a1 also includes selection circuits 61a1 to 61a16, 61b1 to 61b8, 61c1 to 61c4, 61d1 and 61d2, and 61e. These selection circuits 61a1 to 61a16, 61b1 to 61b8, 61c1 to 61c4, 61d1 and 61d2, and 61e are connected in a tree shape in five stages.

(77) The selection circuit 60a supplies 0 or 1 to the selection circuits 61a1 to 61a16 in the first stage based on the value of the first bit of the 5-bit random number rd1. The selection circuit 60b supplies 0 or 1 to the selection circuits 61b1 to 61b8 in the second stage based on the value of the second bit of the 5-bit random number rd1. The selection circuit 60c supplies 0 or 1 to the selection circuits 61c1 to 61c4 in the third stage based on the value of the third bit of the 5-bit random number rd1. The selection circuit 60d supplies 0 or 1 to the selection circuits 61d1 and 61d2 in the fourth stage based on the value of the fourth bit of the 5-bit random number rd1. The selection circuit 60e supplies 0 or 1 to the selection circuit 61e in the fifth stage based on the value of the fifth bit of the 5-bit random number rd1.

(78) Each of the selection circuits 61a1 to 61a16 in the first stage receives two of the 1,024 state transition determination results {fi}. Next, based on the values of the corresponding transition determination results and 0 or 1 outputted by the selection circuit 60a, each of the selection circuits 61a1 to 61a16 selects and outputs one of the two transition determination results and generates and outputs a 1-bit index that indicates the determination result that it has selected.

(79) Each of the selection circuits 61b1 to 61b8 in the second stage receives two of the 16 transition determination results and two of the 16 indexes outputted by the selection circuits 61a1 to 61a16. Next, based on the values of the corresponding transition determination results and 0 or 1 outputted by the selection circuit 60b, each of the selection circuits 61b1 to 61b8 selects and outputs one of the two transition determination results and generates and outputs a 2-bit index that indicates the determination result that it has selected.

(80) Each of the selection circuits 61c1 to 61c4 in the third stage receives two of the eight transition determination results and two of the eight indexes outputted by the selection circuits 61b1 to 61b8. Next, based on the values of the corresponding transition determination results and 0 or 1 outputted by the selection circuit 60c, each of the selection circuits 61c1 to 61c4 selects and outputs one of the two transition determination results and generates and outputs a 3-bit index that indicates the determination result that it has selected.

(81) Each of the selection circuits 61d1 and 61d2 in the fourth stage receives two of the four transition determination results and two of the four indexes outputted by the selection circuits 61c1 to 61c4. Next, based on the values of the corresponding transition determination results and 0 or 1 outputted by the selection circuit 60d, each of the selection circuits 61d1 and 61d2 selects and outputs one of the two transition determination results and generates and outputs a 4-bit index that indicates the determination result that it has selected.

(82) The selection circuit 61e in the fifth stage receives the two transition determination results and the two indexes outputted by the selection circuits 61d1 and 61d2. Next, based on the values of the transition determination results and 0 or 1 outputted by the selection circuit 60e, the selection circuit 61e selects and outputs one of the two transition determination results and generates and outputs a 5-bit index that indicates the determination signal that it has selected.

(83) The selection circuit unit 52 illustrated in FIG. 7 is realized by almost the same circuit configuration as that of the selection circuit unit 51a1. Specifically, in the case of the selection circuit unit 52, each of the selection circuits 61a1 to 61a16 in the first stage receives two of the 32 transition determination results and two of the 32 5-bit indexes outputted by the selection circuit units 51a1 to 51a32. Next, after selection of the transition determination results and addition of the index bits in an individual stage, a 10-bit transition number N and a finally selected transition determination result f are outputted.

(84) FIG. 9 illustrates an example of a selection circuit.

(85) In FIG. 9, an example of the selection circuit 61b1 in FIG. 8 is illustrated. Each of the selection circuits 61b2 to 61b8, 61c1 to 61c4, 61d1 and 61d2, and 61e is also realized by a similar circuit configuration.

(86) The selection circuit 61b1 includes an exclusive OR (XOR) circuit 70, an OR circuit 71, and selection circuit 72 and 73.

(87) the XOR circuit 70 receives the transition determination results outputted by the selection circuits 61a1 and 61a2 in the first stage. In FIG. 9, fg1 denotes the transition determination result outputted by the selection circuit 61a1, and fg2 denotes the transition determination result outputted by the selection circuit 61a2. The XOR circuit 70 outputs 0 when fg1 and fg2 represent the same value and outputs 1 otherwise.

(88) The OR circuit 71 receives fg1 and fg2. When at least one of fg1 and fg2 represents 1, the OR circuit 71 outputs 1 as the transition determination result (denoted by fg3). When both fg1 and fg2 represent 0, the OR circuit 71 outputs 0 as fg3.

(89) The selection circuit 72 receives fg1 and 0 or outputted by the selection circuit 60b. When the XOR circuit 70 outputs 1, the selection circuit 72 selects and outputs the value of fg1. When the XOR circuit 70 outputs 0, the selection circuit 72 selects and outputs the value outputted by the selection circuit 60b.

(90) The selection circuit 73 receives the indexes outputted by the selection circuits 61a1 and 61a2 in the first stage. In FIG. 9, the index outputted by the selection circuit 61a1 is denoted by id1, and the index outputted by the selection circuit 61a2 is denoted by id2. When the selection circuit 72 outputs 1, the selection circuit 73 selects and outputs the value of id1. When the selection circuit 72 outputs 0, the selection circuit 73 selects and outputs the value of id2.

(91) A value obtained by adding the 1-bit value outputted by the selection circuit 72 to the value of id1 or id2 outputted by the selection circuit 73 (added to an upper bit) is the index (denoted by id3 in FIG. 9) outputted by the selection circuit 61b1.

(92) Each of the selection circuits 61a1 to 61a16 in the first stage illustrated in FIG. 8 is also realized by almost the same circuit configuration as that illustrated in FIG. 9. Specifically, each of the selection circuits 61a1 to 61a16 does not include the selection circuit 73.

(93) FIG. 10 illustrates examples of indexes to be generated.

(94) When the selection circuit 60b outputs 1 and when the two transition determination results (fg1 and fg2) supplied to the selection circuit 61b1 illustrated in FIG. 9 represent the same value, the selection circuit 61b1 outputs, as id3, a value obtained by adding a new bit 1 to an upper bit of id1. In addition, when the selection circuit 60b outputs 1 and when fg1 and fg2 represent 1 and 0, respectively, the selection circuit 61b1 also outputs the value, as id3, the value obtained by adding the new bit 1 to the upper bit of id1. However, when the selection circuit 60b outputs 1 and when fg1 and fg2 represent 0 and 1, respectively, the selection circuit 61b1 outputs, as id3, a value obtained by adding a new bit 011 to an upper bit of id2.

(95) When the selection circuit 60b outputs 0 and when fg1 and fg2 represent the same value, the selection circuit 61b1 outputs, as id3, a value obtained by adding a new bit 0 to the upper bit of id2. In addition, when the selection circuit 60b outputs 0 and when fg1 and fg2 represent 1 and 0, respectively, the selection circuit 61b1 also outputs, as id3, the value obtained by adding the new bit 1 to the upper bit of id1. In addition, when the selection circuit 60b outputs 0 and when fg1 and fg2 represent 0 and 1, respectively, the selection circuit 61b1 outputs, as id3, the value obtained by adding the new bit 0 to the upper bit of id2.

(96) In addition, when at least one of fg1 and fg2 represents 1, fg3 represents 1. When both fg1 and fg2 represent 0, fg3 represents 0.

(97) By using the transition number determination circuit 41 as described above, a state transition to be accepted is selected preferentially. Thus, since the state transition frequency is increased, the calculation time is expected to shorten further.

COMPARATIVE EXAMPLE

(98) FIG. 11 illustrates an example of a transition control unit that increases the transition acceptance probability by a certain offset increment.

(99) A transition control unit 80 includes an offset addition circuit 81 and an offset control circuit 82 added to the circuit portion that realizes the functions of the transition acceptance determination unit 14b illustrated in FIG. 15. The other portions of the transition control unit 80 are the same as the transition control unit 14 illustrated in FIGS. 15 and 16.

(100) The offset addition circuit 81 adds an offset y to −ΔE. In the circuit example in FIG. 11, the offset addition circuit 81 is a subtractor 81a. Thus, in the example in FIG. 11, instead of adding the offset y to −ΔE, the offset y is subtracted from the comparison target product Tf−1(u) (corresponding to thermal excitation energy) of a temperature T and a random number. However, either the addition or subtraction is applicable.

(101) The offset control circuit 82 performs a control operation such that the offset y at a local solution (a solution where the energy indicates a locally minimum value) is greater than that of a non-local solution. In the example in FIG. 11, the offset control circuit 82 includes an accumulator 82a having a reset terminal R. The accumulator 82a outputs 0 as the offset y when the transition determination result f inputted to the reset terminal R indicates acceptance of the state transition (namely, when the state transition occurs). The accumulator 82a also has an input terminal and a clock terminal. When the transition determination result f indicates that the state transition is not accepted (namely, when the state transition will not occur), each time the clock terminal is supplied with a pulse signal (not illustrated), the accumulator 82a adds an offset increment Δy inputted to the input terminal to the offset y. For example, the pulse signal (not illustrated) is supplied by a state machine. The offset increment Δy is stored in a register (not illustrated), for example.

(102) When −ΔE+y, which is the sum of the −ΔE outputted by selector 14b2 and the offset y stored in the accumulator 82a, is greater than the product Tf.sup.−1(u) of the temperature T and the random number, the transition control unit 80 as described above accepts the corresponding state transition.

(103) In addition, the accumulator 82a changes the offset y as follows. If a state transition has been accepted and has occurred, the accumulator 82a resets the offset y to 0. If no state transition has been accepted and has occurred, the accumulator 82a increments the offset y by the offset increment Δy.

(104) FIG. 12 illustrates a first example of change of the probability of acceptance of an individual state transition when the transition control unit according to the comparative example is used. In FIG. 12, the horizontal axis represents state variables s.sub.i as candidates of state transitions, and the vertical axis represents the acceptance probability of the individual state transitions.

(105) As illustrated in FIG. 12, when the offset increment Δy is small, since the acceptance probability is slightly increased, escaping from a local solution could take much time.

(106) FIG. 13 illustrates a second example of change of the probability of acceptance of an individual state transition when the transition control unit according to the comparative example is used. In FIG. 13, the horizontal axis represents state variables s.sub.i as candidates of state transitions, and the vertical axis represents the acceptance probabilities of the individual state transitions.

(107) As illustrated in FIG. 13, when the offset increment Δy is large, since the individual acceptance probability is significantly increased, state transitions occur excessively frequently. Thus, the solution could not converge into an optimal solution.

(108) In contrast, in the case of the transition control units 20 and 40 illustrated in FIGS. 1 and 6, respectively, as M is brought closer to 1, the acceptance probability is increased, and escaping from a local solution is accelerated. In addition, since 0<M≤1, even when M=1, the number of state transitions whose acceptance probability is 1 is small (1 in the example in FIG. 4). Thus, state transitions do not occur excessively frequently.

(109) FIG. 14 illustrates examples of software simulation results based on simulated annealing performed by using the transition control units illustrated in FIGS. 6 and 11. The problem to be optimized is a traveling salesman problem formulated by an ising model (a Boltzmann machine). In FIG. 14, the horizontal axis represents the number of iterations (the number of repetitions of processing for updating the state and energy in simulated annealing), and the vertical axis represents the energy.

(110) Results 90a to 90e indicate simulation results of change of the energy with respect to the number of iterations when the transition control unit 80 in FIG. 11 changes the offset increment Δy. The result 90a indicates a simulation result when the offset increment Δy is 0 (namely, when no offset is not used). The results 90b to 90e indicate simulation results when the offset increments Δy are 0.05, 0.1, 0.15, and 0.2, respectively.

(111) In contrast, results 91a to 91d indicate simulation results of change of the energy with respect to the number of iterations when the transition control unit 40 in FIG. 6 changes M. The results 91a to 91d indicate simulation results when M=0.25, 0.5, 0.75, and 1, respectively.

(112) When the minimum energy value (the energy at an optimal solution) is about 6,000, in the case of the transition control unit 80, the smallest number of iterations it2 to reach an energy Ex, which is larger than the minimum value by about 10%, is about 65,000, which is more than triple the smallest number of iterations it1 in the case of the transition control unit 40.

(113) Namely, the example in FIG. 14 indicates that the transition control unit 40 calculates a value close to an optimal solution at least three times faster than the transition control unit 80.

(114) The example in FIG. 14 indicates that use of the transition control unit 40 and M=0.25 achieve the lowest energy (about 6,300). In contrast, when the transition control unit 80 is used, the lowest energy is about 6,800. Thus, the transition control unit 40 achieves a solution closer to an optimal solution than the transition control unit 80.

(115) The degree of the above effect differs depending on the optimization problem to be calculated. For example, the value of M is selected based on the individual optimization problem and the software simulation results as described above such that the calculation time is further shortened.

(116) While an aspect of the optimization apparatuses and control methods thereof based on embodiments has been described, the above description is only an example. The embodiments are not limited to the above description.

(117) In an aspect, the embodiments shorten the calculation time of an individual optimization problem.

(118) All examples and conditional language provided herein are intended for the pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.