Optimization apparatus and optimization apparatus control method

1. An optimization apparatus comprising:

a state holding section that holds values of a plurality of state variables included in an evaluation function indicative of an energy;

an energy calculation section that calculates an energy change of the energy for each of a plurality of state transitions in a case where each of the plurality of state transitions occurs according to a change in one of the values of the plurality of state variables;

a temperature control section that controls a temperature; and

a transition control section that adds, when stochastically determining based on the temperature, the energy change, and a random number whether to allow one of the plurality of state transitions according to a relative relationship between the energy change and a thermal excitation energy, an offset to the energy change and that exercises control so as to set the offset at a local minimum, at which the energy is locally minimized, to be larger than an offset at the time of the energy not being minimized.

2. The optimization apparatus according to claim 1 , wherein:

the transition control section includes an offset control circuit; and

the offset control circuit sets, when allowing one of the plurality of state transitions, the offset to zero, and monotonically increases, when allowing none of the plurality of state transitions, the offset with respect to a length of a stay in a current state represented by the values of the plurality of state variables by increasing the offset every iteration.

3. The optimization apparatus according to claim 2 , wherein:

the offset control circuit includes an accumulator having a reset terminal; and

the accumulator sets, upon receipt of a first signal that is indicative that one of the plurality of state transitions is allowed, the offset to zero, and adds, upon receipt of a second signal that is indicative that none of the plurality of state transitions is allowed, an offset increment value to the offset.

4. The optimization apparatus according to claim 3 , wherein:

the accumulator further has a clock terminal; and

each time a pulse signal is inputted from a state machine to the clock terminal, the accumulator adds the offset increment value to the offset.

5. The optimization apparatus according to claim 1 , wherein the transition control section includes:

a selector that selects, according to the random number, one of energy changes calculated for the plurality of state transitions;

a storage unit that outputs, according to the random number, a value of an inverse function of a function indicative of an allowance probability of a state transition represented by a Metropolis method or a Gibbs method;

a multiplier that outputs a threshold of the thermal excitation energy represented by a product of the value of the inverse function and the temperature; and

a comparator that outputs a determination result that indicates whether to allow the state transition corresponding to the energy change selected by the selector and that is represented by a value corresponding to a result of a comparison between a sum of the energy change selected by the selector and the offset and the threshold of the thermal excitation energy.

6. The optimization apparatus according to claim 1 , wherein the transition control section includes:

a storage unit that outputs, according to random numbers independent of one another for the plurality of state transitions, a plurality of values of an inverse function of a function indicative of allowance probabilities of the plurality of state transitions represented by a Metropolis method or a Gibbs method;

a multiplier that outputs thresholds of the thermal excitation energy represented by a plurality of products of the plurality of values and the temperature;

a comparator that outputs a plurality of determination results that indicate whether to allow the plurality of state transitions and that are represented by a plurality of values corresponding to results of comparisons between a plurality of sums of energy changes calculated for the plurality of state transitions and the offset and the plurality of products; and

a selector that selects, when there are a plurality of allowed state transitions among the plurality of state transitions based on the plurality of determination results, one of the plurality of allowed state transitions.

7. The optimization apparatus according to claim 1 , wherein the transition control section includes:

a storage unit that outputs, according to the random number common to all of the plurality of state transitions, a value of an inverse function of a function indicative of allowance probabilities of the plurality of state transitions represented by a Metropolis method or a Gibbs method;

a multiplier that outputs a threshold of the thermal excitation energy represented by a product of the value of the inverse function and the temperature;

a comparator that outputs a plurality of determination results that indicate whether to allow the plurality of state transitions and that are represented by a plurality of values corresponding to results of comparisons between a plurality of sums of energy changes calculated for the plurality of state transitions and the offset and the product; and

a selector that receives the plurality of determination results and that selects, when there are a plurality of allowed state transitions among the plurality of state transitions, one of the plurality of allowed state transitions.

8. The optimization apparatus according to claim 1 , wherein the transition control section includes:

a storage unit that outputs, according to a random number common to every two or more state transitions of the plurality of state transitions, a plurality of values of an inverse function of a function indicative of allowance probabilities of the plurality of state transitions represented by a Metropolis method or a Gibbs method;

a multiplier that outputs thresholds of the thermal excitation energy represented by a plurality of products of the plurality of values and the temperature;

a comparator that outputs a plurality of determination results that indicate whether to allow the plurality of state transitions and that are represented by a plurality of values corresponding to results of comparisons between a plurality of sums of energy changes calculated for the plurality of state transitions and the offset and the plurality of products; and

a selector that receives the plurality of determination results and that selects, when there are a plurality of allowed state transitions among the plurality of state transitions, one of the plurality of allowed state transitions.

9. A method for controlling an optimization apparatus, the method comprising:

holding, by a state holding section included in the optimization apparatus, values of a plurality of state variables included in an evaluation function indicative of an energy;

calculating, by an energy calculation section included in the optimization apparatus, an energy change of the energy for each of a plurality of state transitions in a case where each of the plurality of state transitions occurs according to a change in one of the values of the plurality of state variables;

controlling, by a temperature control section included in the optimization apparatus, a temperature; and

adding, by a transition control section included in the optimization apparatus, when stochastically determining based on the temperature, the energy change, and a random number whether to allow one of the plurality of state transitions according to a relative relationship between the energy change and a thermal excitation energy, an offset to the energy change, and exercising control so as to set the offset at a local minimum, at which the energy is locally minimized, to be larger than an offset at the time of the energy not being minimized.