Optimization apparatus, optimization method, and non-transitory computer-readable storage medium
An optimization apparatus includes a processor. The processor configured to calculate a change amount of energy represented by an evaluation function of a case of changing a state of any one of a plurality of state variables so as to increase or decrease a value by 1 in a case of a state variable taking multiple values, the evaluation function representing the energy including the plurality of state variables, determine whether to set a state change in the state variable as a candidate according to a correlation between a threshold and a total change amount, stochastically determine whether to adopt the state change set as the candidate, calculate post-transition energy after executing a state transition of the state variable according to the state change, and obtain minimum energy by setting the post-transition energy as the minimum energy when the post-transition energy is less than the minimum energy.
1 . An optimization apparatus comprising:
a temperature control circuit to control a temperature value indicating a temperature,
annealing circuits configured to:
calculate a change amount of energy represented by an evaluation function the evaluation function including a plurality of binary state variables and at least one multi-valued auxiliary spin which represents a range constraint for a sum related to the plurality of binary state variables, and
a processor coupled to the temperature control circuit and the annealing circuits and configured to:
determine whether to set a state change in any of the binary state variables or the multi-valued auxiliary spin as a candidate according to a correlation between a threshold and a total change amount, the threshold being calculated based on the temperature value and a random number value, the total change amount being obtained by the calculated change amount of energy, the state change for the multi-valued auxiliary spin comprises incrementing or decrementing its value by 1 to traverse a continuous integer range of the range constraint,
stochastically determine whether to adopt the state change set as the candidate,
calculate post-transition energy after executing a state transition of the state variable according to the state change, and
obtain minimum energy by setting the post-transition energy as the minimum energy when the post-transition energy is less than the minimum energy.
2 . The optimization apparatus according to claim 1 , wherein the annealing circuits do not set the state change in the state variable as the candidate when the state of the state variable taking the at least three values in the case of changing the state does not fall within a range of an upper limit value or a lower limit value determined in advance.
3 . The optimization apparatus according to claim 2 , wherein the annealing circuits perform an addition state change of adding a value of 1 and a subtraction state change of subtracting a value of 1 when the state variable taking the at least three values, and select and set either the addition state change or the subtraction state change as the candidate when both the addition state change and the subtraction state change fall within the range.
4 . The optimization apparatus according to claim 3 , wherein the annealing circuits give priority for selection to the addition state change and the subtraction state change and select the addition state change or the subtraction state change based on the priority.
5 . The optimization apparatus according to claim 2 , wherein the annealing circuits set the upper limit value or the lower limit value for an initial value of the state variable taking multiple values.