Optimization device and control method of optimization device

Abstract

An optimization device includes: a state hold circuit that holds values of state variables included in an evaluation function that represents energy; an objective function calculation circuit that calculates an energy change value in an objective function included in the evaluation function for each of state transitions when a state transition occurs in response to a change in any of the values of the state variables; a constraint term calculation circuit that calculates a constraint term evaluation value, which is an evaluation value of a constraint term included in the evaluation function, for each of the state transitions; a temperature control circuit that controls a temperature value that indicates a temperature; and a transition control circuit that determines stochastically whether to accept any of the state transitions based on the temperature value, a random number value, and a sum of the change value and the constraint term evaluation value.

Claims

1. An optimization device comprising: a state hold circuit configured to hold values of a plurality of state variables included in an evaluation function that represents energy; an objective function calculation circuit configured to calculate an energy change value in an objective function included in the evaluation function for each of a plurality of state transitions when a state transition occurs in response to a change in any of the values of the plurality of state variables; a constraint term calculation circuit configured to calculate a constraint term evaluation value, which is an evaluation value of a constraint term included in the evaluation function, for each of the plurality of state transitions; a temperature control circuit configured to control a temperature value that indicates a temperature; and a transition control circuit configured to determine stochastically whether to accept any of the plurality of state transitions based on the temperature value, a random number value, and a sum of the change value and the constraint term evaluation value.

2. The optimization device according to claim 1, wherein the constraint term calculation circuit is further configured to: calculate, for each of the plurality of state transitions, a first nonlinear constraint term by performing a nonlinear processing on the constraint term before any of the plurality of state variables changes and a second nonlinear constraint term by performing the nonlinear processing on the constraint term after the any of the plurality of state variables changes, the nonlinear processing limiting an amount of energy of the constraint term; and calculate, for each of the plurality of state transitions, the constraint term evaluation value, which is a difference between the first nonlinear constraint term and the second nonlinear constraint term.

3. The optimization device according to claim 2, wherein each of the first nonlinear constraint term and the second nonlinear constraint term increases in a stepped shape or a curved shape according to the energy of the constraint term and has a predetermined upper limit value.

4. The optimization device according to claim 1, wherein the constraint term calculation circuit is further configured to: calculate the energy of the constraint term based on the values of the plurality of state variables, and a weighting factor and a bias factor related to the constraint term; and output the energy of the constraint term.

5. The optimization device according to claim 1, wherein the constraint term calculation circuit is further configured to: select whether to supply the constraint term evaluation value or whether to supply 0 instead of the constraint term evaluation value to the transition control circuit based on an input enable signal.

6. A control method of an optimization device, the control method comprising: holding, by a state hold circuit included in the optimization device, values of a plurality of state variables included in an evaluation function that represents energy; calculating, by an objective function calculation circuit included in the optimization device, an energy change value in an objective function included in the evaluation function for each of a plurality of state transitions when a state transition occurs in response to a change in any of the values of the plurality of state variables; calculating, by a constraint term calculation circuit included in the optimization device, a constraint term evaluation value, which is an evaluation value of a constraint term included in the evaluation function, for each of the plurality of state transitions; controlling, by a temperature control circuit included in the optimization device, a temperature value that indicates a temperature; and determining, by a transition control circuit included in the optimization device, stochastically whether to accept any of the plurality of state transitions based on the temperature value, a random number value, and a sum of the change value and the constraint term evaluation value.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a view illustrating an example of an optimization device according to a first embodiment;

(2) FIG. 2 is a flowchart illustrating a flow of an example of the operation of the optimization device;

(3) FIG. 3 is a view illustrating an example of a nonlinear function;

(4) FIG. 4 is a view illustrating an example of an optimization device according to a second embodiment;

(5) FIG. 5 is a flowchart illustrating a flow of an example of the operation performed by an optimization device including a processing of separating a weighting factor and a bias factor;

(6) FIG. 6 is a view illustrating an example of separation of an objective function component and a constraint term component; and

(7) FIG. 7 is a view illustrating a conceptual configuration of an optimization device by a simulated annealing method.

DESCRIPTION OF EMBODIMENTS

(8) The simulated annealing method will be described below.

(9) The simulated annealing method is a kind of Monte Carlo method, and is a method of stochastically obtaining a solution using a random number value. In the following, a problem of minimizing the value of an evaluation function to be optimized will be described as an example, and the value of the evaluation function will be called energy. In the case of maximization, the sign of the evaluation function may be changed.

(10) Starting from the initial state in which one of discrete values is substituted for each variable, a state close to the state (e.g., a state in which only one variable is changed) is selected from the current state (a combination of variable values) and a state transition thereof is considered. The energy change for the state transition is calculated, and the state transition is adopted according to the value to stochastically determine whether to change the state or to keep the original state without adopting the state transition. When the adoption probability of a case where energy falls is selected to be larger than a case where energy rises, a state change occurs in the direction of energy decrease on average, and it may be expected that a state transition to a more appropriate state occurs with the passage of time. Finally, it may be possible to obtain an optimal solution or an approximate solution giving energy close to the optimal value. When such a solution is adopted for a case where energy falls deterministically or when such a solution is not adopted for a case where energy rises, the energy change becomes a broad monotonous decrease over time, but no more changes occur once the energy change reaches a local solution. As described above, since the discrete optimization problem has a large number of local solutions, a state is mostly caught by local solutions that are not close to the optimal value. Therefore, it is important to determine stochastically whether to adopt the state.

(11) In the simulated annealing method, it has been proved that the state reaches the optimum solution at the limit of time (number of iterations) infinity when the adoption (acceptance) probability of the state transition is determined as follows.

(12) For the energy change value (ΔE) accompanying the state transition, the acceptance probability p of the state transition is determined by the following function f(x) represented by an equation (1). An equation (2) is the Metropolis method. An equation (3) is the Gibbs method.

(13) $\begin{array}{cc}\left[\mathrm{Equation}1\right]& \\ p\left(\Delta E,T\right)=f\left(-\frac{\Delta E}{T}\right)& \left(1\right)\\ \left[\mathrm{Equation}2\right]& \\ f_{\mathrm{metro}}\left(x\right)=\min \left(1,e^x\right)& \left(2\right)\\ \left[\mathrm{Equation}3\right]& \\ f_{\mathrm{Gibbs}}\left(x\right)=\frac{1}{1+e^{-x}}& \left(3\right)\end{array}$

(14) Here, the sign “T” is a parameter called a temperature value and is changed as follows. That is, the temperature value T is reduced logarithmically to the number of iterations t as expressed by the following equation.

(15) $\left[\mathrm{Equation}4\right]$$\begin{array}{cc}T=\frac{T_0\log \left(c\right)}{\log \left(t+c\right)}& \left(4\right)\end{array}$

(16) Here, the sign “T.sub.0” is an initial temperature, which needs to be large enough according to a problem.

(17) When using the acceptance probability represented by the equations (1) to (3), assuming that the state reaches the steady state after sufficient repetition, the occupancy probability of each state follows the Boltzmann distribution with respect to the thermal equilibrium state in thermodynamics. In addition, since the occupancy probability of a low energy state increases when the temperature is gradually lowered from the high temperature, the low energy state may be obtained when the temperature is sufficiently lowered. This method is called a simulated annealing method because the method is very similar to a state change when a material is annealed. At this time, the stochastic occurrence of a state transition in which energy rises corresponds to thermal excitation in physics.

(18) In the above-mentioned simulated annealing method, an optimum solution may be obtained when the number of iterations is taken infinitely, but in reality, since it is necessary to obtain a solution with a limited number of iterations, the optimum solution may not be determined reliably. In the above equations, since the temperature drops very slowly, the temperature does not drop sufficiently in a finite time. Therefore, in the actual simulated annealing method, the temperature is often lowered faster rather than the logarithmic temperature change.

(19) FIG. 7 illustrates a conceptual configuration of an optimization device by a simulated annealing method. A case where a plurality of state transition candidates is generated will be described in the following description, but the original basic simulated annealing method is to generate transition candidates one by one.

(20) An optimization device 10 includes a state holding unit 11 that holds the current state S (values of a plurality of state variables). The optimization device 10 further includes an evaluation function calculation unit 12 that calculates an energy change value {−ΔE.sub.i} of each state transition when a state transition from the current state S occurs due to a change in one of the values of the plurality of state variables. The optimization device 10 further includes a temperature controller 13 that controls a temperature value T, and a transition controller 14 that controls a state change. Based on the temperature value T, the energy change value {−ΔE.sub.i}, and a random number value, the transition controller 14 determines stochastically whether to accept any of a plurality of state transitions according to a relative relationship between the energy change value {−ΔE.sub.i} and the thermal excitation energy. The optimization device 10 further includes an energy comparison unit 15 that specifies the minimum energy state S among the states generated by the state transitions.

(21) The operation in one time iteration is as follows. First, the transition controller 14 generates one or more candidates (candidate number {N.sub.i}) for state transition from the current state s held in the state holding unit 11 to the next state. The evaluation function calculation unit 12 calculates the energy change value {−ΔE.sub.i} for each state transition listed as a candidate using the current state S and the state transition candidates. The transition controller 14 uses the temperature value T generated by the temperature controller 13 and a random variable (random number value) generated by a random number generator unit in the transition controller 14 to permit the state transition with the acceptance probability of the above equations (1) to (3) in response to the energy change value {−ΔE.sub.i} of each state transition. Then, the transition controller 14 calculates transition propriety {fi} indicating whether to accept each state transition (hereinafter, also referred to as propriety of state transition). When there are plural permitted state transitions, the transition controller 14 randomly selects one of the permitted state transitions using a random number value. Then, the transition controller 14 outputs the transition number N and transition propriety F of the selected state transition. When there are plural permitted state transitions, the value of the state variable stored in the state holding unit 11 is updated according to a selected state transition.

(22) Starting from the initial state, the temperature controller 13 repeats the above repetition while lowering the temperature value, and the operation is ended when the number of repetitions reaches a certain number or when an end determination condition such as a condition that energy reaches a certain value is satisfied. An answer output by the optimization device 10 is the state at the end. However, in reality, since the temperature T does not become 0 with a finite number of iterations, the occupancy probability of the state has a distribution represented by the Boltzmann distribution even at the end, which is not necessarily an optimal value or a good solution. Therefore, it is a realistic solution to hold the state of the minimum energy obtained so far during the iteration and finally output such a state.

(23) Here, supplementary descriptions will be made on a mechanism that has not been described so far and permits the state transition with the acceptance probability represented by the equations (1) to (3) by the transition controller 14.

(24) A circuit that outputs 1 with an acceptance probability “p” and outputs 0 with an acceptance probability (1−p) may be implemented by a comparator that has two inputs “a” and “b”, outputs 1 when a>b, and outputs 0 when a<b, in which the acceptance probability “p” is input into the input “a” and a uniform random number taking a value of an interval [0, 1) is input into the input “b”. Therefore, the above function may be implemented by inputting, into the input “a” of the comparator, the value of the acceptance probability “p” which is calculated using the equation of (1) from the energy change value and the temperature T.

(25) That is, when “f” is a function used in the equation of (1) and “u” is a uniform random number taking a value of the interval [0, 1), the above function may be implemented in a circuit that outputs 1 as the transition propriety F when f(ΔE/T) is larger than “u”.

(26) This may be left as it is, but the same function may be implemented even when the following modification is made. Even when the same monotonically increasing function is applied to two numbers, the magnitude relationship does not change. Therefore, the output of the comparator does not change even when the same monotonically increasing function is applied to the two inputs of the comparator. When the inverse function f.sup.−1 of f is adopted as the monotonically increasing function, a circuit that outputs 1 when −ΔE/T is larger than f.sup.−1(u) or a circuit that outputs 1 when ΔE/T is equal to or less than f.sup.−1(u) is sufficient. Further, since the temperature T is positive, a circuit that outputs 1 when −ΔE is larger than Tf.sup.−1(u) or a circuit that outputs 1 when ΔE is equal to or less than Tf.sup.−1(u) is sufficient. The transition controller 14 generates the uniform random number “u” and outputs a value of f.sup.−1(u) using a conversion table that converts the uniform random number “u” into a value of f.sup.−1(u). When the Metropolis method is applied, f.sup.−1(u) is given by the following equation (5). Further, when the Gibbs method is applied, f.sup.−1(u) is given by the following equation (6).

(27) $\begin{array}{cc}\left[\mathrm{Equation}5\right]& \\ f_{\mathrm{metro}}^{-1}\left(u\right)=\log \left(u\right)& \left(5\right)\\ \left[\mathrm{Equation}6\right]& \\ f_{\mathrm{Gibbs}}^{-1}\left(u\right)=\log \left(\frac{u}{1-u}\right)& \left(6\right)\end{array}$

(28) When solving the optimization problem by the simulated annealing method as described above, the evaluation function to be minimized often includes an objective function representing a numerical value to be minimized and a constraint term for limiting violation of the constraint condition that the solution needs to satisfy. In the evaluation function of an Ising model, the constraint term is expressed in a quadratic form.

(29) Hereinafter, embodiments of the present disclosure will be described with reference to the drawings.

First Embodiment

(30) FIG. 1 is a view illustrating an example of an optimization device according to a first embodiment.

(31) An optimization device 20 includes a state holding unit 21, an objective function calculation unit 22, a constraint term calculation unit 23, a temperature controller 24, a transition controller 25, and an energy comparison unit 26.

(32) The state holding unit 21 holds a state “s” (values of a plurality of state variables) included in an evaluation function representing energy. Further, the state holding unit 21 updates the values of the state variables based on a transition propriety F and a transition number N output by the transition controller 25. The state holding unit 21 may be implemented using, for example, a register or a memory (e.g., RAM (Random Access Memory)) that holds the values of the plurality of state variables, and a logic circuit that inverts the value of a state variable from 1 to 0 or from 0 to 1 based on the transition propriety F and the transition number N. When the transition propriety F is a value (e.g., 1) that permits the state transition of the transition number N, the value of the state variable corresponding to the transition number N is inverted.

(33) When the state transition occurs in response to a change in any of the values of the plurality of state variables, the objective function calculation unit 22 calculates an energy change value in an objective function included in the evaluation function for each of the plurality of state transitions. Hereinafter, the energy change value in the objective function calculated for each of the plurality of state transitions is denoted as an energy change {−ΔE.sub.oi}.

(34) The energy E.sub.o of the objective function is expressed by the following equation (7) based on the values of the plurality of state variables, a weighting factor (also called a coupling coefficient) related to the objective function, and a bias factor.

(35) $\left[\mathrm{Equation}7\right]$$\begin{array}{cc}{E}_o=-\frac{1}{2}\underset{i,j}{.Math.}{W}_{o\_\mathrm{ij}}{x}_i{x}_j-\underset{i}{.Math.}{\beta }_{o\_i}{x}_i& \left(7\right)\end{array}$

(36) In the equation (7), x.sub.i and x.sub.j are state variables, W.sub.o_ij is a weighting factor between the state variables x.sub.i and x.sub.j in the objective function, and βo_i is a bias factor between the state variables x.sub.i and x.sub.j in the objective function.

(37) The objective function calculation unit 22 calculates the energy of the current objective function and the energy of an objective function when each of a plurality of state transitions (state transitions designated by candidate numbers {N.sub.i} to be described later) occurs. Then, the objective function calculation unit 22 calculates an energy change {−ΔE.sub.oi} that is a difference between the energy of the current objective function and the energy of the objective functions when each of the plurality of state transitions occurs. For example, the energy change ΔE.sub.oi of the objective function when the value of x.sub.i is inverted is expressed by the following equation (8).
[Equation 8]
ΔE.sub.oi=E.sub.o_i−E.sub.o_current  (8)

(38) In the equation (8), E.sub.o_i is the energy of the objective function after the inversion of the value of x.sub.i, and E.sub.o_current is the energy of the current objective function (before the change of x.sub.i). The objective function calculation unit 22 is implemented using, for example, a logic circuit such as a product-sum operation circuit, a register or a memory (e.g., a RAM) that holds a weighting factor and a bias factor, and the like. The register or memory that holds the weighting factor and the bias factor may be outside the objective function calculation unit 22.

(39) When a state transition occurs in response to a change in any of the plurality of state variable values, the constraint term calculation unit 23 calculates a constraint term evaluation value that is an evaluation value of a constraint term in the evaluation function for each of the plurality of state transitions. The constraint term evaluation value is calculated, for example, as follows. In the following, the constraint term evaluation value calculated for each of the plurality of state transitions may be expressed as an energy change {−ΔE.sub.pi_nl}.

(40) The energy E.sub.p of the constraint term is expressed by the following equation (9) based on the values of the plurality of state variables, and a weighting factor and a bias factor related to the constraint term.

(41) $\left[\mathrm{Equation}9\right]$$\begin{array}{cc}{E}_p=-\frac{1}{2}\underset{i,j}{.Math.}{W}_{p\_\mathrm{ij}}{x}_i{x}_j-\underset{i}{.Math.}{\beta }_{p\_i}{x}_i& \left(9\right)\end{array}$

(42) In the equation (9), W.sub.p_ij is a weighting factor between the state variables x.sub.i and x.sub.j in the constraint term, and β.sub.p_i is a bias factor for the state variable x.sub.i in the constraint term.

(43) The constraint term calculation unit 23 calculates the energy of the constraint term before and after any of the plurality of state variables changes. That is, the constraint term calculation unit 23 calculates the energy of the current constraint term and the energy of the constraint term when each of the plurality of state transitions (state transitions designated by the candidate numbers {N.sub.i} to be described later) occurs.

(44) Further, the constraint term calculation unit 23 calculates, for each of the plurality of state transitions, a first nonlinear constraint term by performing a nonlinear processing, which limits the amount of the energy of the constraint term, on the constraint term before any of the plurality of state variables changes and a second nonlinear constraint term by performing the nonlinear processing on the constraint term after the any of the plurality of state variables changes. Thereafter, the constraint term calculation unit 23 calculates, for each of the plurality of state transitions, an energy change {−ΔE.sub.pi_nl} that is a difference between the first nonlinear constraint term and the second nonlinear constraint term. For example, an energy change Δ.sub.Epi_nl, which is a constraint term evaluation value when the value of x.sub.i changes, is expressed by the following equation (10).
[Equation 10]
ΔE.sub.pi_nl=f(E.sub.p_i)−fE.sub.p_current)  (10)

(45) In the equation (10), f(E.sub.p_i) is a nonlinear constraint term calculated by performing nonlinear processing on the energy E.sub.p_i of the constraint term after the change of the value of x.sub.i. f(E.sub.p_current) is a nonlinear constraint term calculated by performing nonlinear processing on the energy E.sub.p_current of the current constraint term (before the change of x.sub.i).

(46) Further, the constraint term calculation unit 23 may output the energy E.sub.p (e.g., the energy E.sub.p_current) of the calculated constraint term.

(47) The constraint term calculation unit 23 is implemented using, for example, a logic circuit such as a product-sum operation circuit, a register or a memory that holds a weighting factor and a bias factor, a circuit that performs nonlinear processing (e.g., a selection circuit that selects and outputs a value corresponding to the energy of the constraint term), and the like. The register or the memory that holds the weighting factor and the bias factor may be outside the constraint term calculation unit 23.

(48) The temperature controller 24 controls a temperature T. In order to implement the simulated annealing method, the temperature controller 24 performs, for example, a control of decreasing the temperature T according to a predetermined schedule.

(49) The temperature controller 24 may be implemented by an electronic circuit for a specific application, such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array). The temperature controller 24 may be a processor such as a CPU (Central Processing Unit) or a DSP (Digital Signal Processor). In that case, the processor controls the temperature T by executing a program stored in a memory (not illustrated).

(50) The transition controller 25 determines stochastically whether to accept any of the plurality of state transitions based on an evaluation value that is the sum of the energy change {−ΔE.sub.oi} and the energy change {−ΔE.sub.pi_nl}, the temperature T, and a random number value. For example, the transition controller 25 uses the random number value to generate and output a candidate number {N.sub.i}. In addition, the transition controller 25 calculates the evaluation value {−ΔE.sub.i}={−ΔE.sub.oi}+{−ΔE.sub.pi_nl} for each of the plurality of state transitions designated by the candidate number {N.sub.i}. Further, the transition controller 25 calculates a product Tf.sup.−1(u) of the temperature T and the random number value (corresponding to thermal excitation energy). Then, the transition controller 25 determines stochastically whether to accept any of the plurality of state transitions based on a result of comparison between Tf.sup.−1(u) and {−ΔE.sub.i}. In a case where the transition controller 25 is a circuit that outputs a transition propriety F indicating that a state transition is accepted when {−ΔE.sub.i}<Tf.sup.−1(u), the state transition acceptance probability becomes smaller as {−ΔE.sub.i} becomes positively larger. When there is a plurality of permitted state transitions, the transition controller 25 randomly selects one of the permitted state transitions using a random number value. Then, the transition controller 25 outputs a transition number N of the selected state transition, and a transition propriety F.

(51) When there is no permitted state transition, the transition controller 25 may add or subtract an offset value to or from one of the energy change {−ΔE.sub.oi} and Tf.sup.−1(u) so that the state transition acceptance probability increases (see, e.g., Japanese Laid-Open Patent Publication No. 2018-063626).

(52) The transition controller 25 as described above may be implemented using, for example, an adder circuit, a multiplier circuit, a selector, a comparator, a random number generation circuit, a memory (e.g., a RAM) that stores f.sup.−1(u) corresponding to a random number value, and the like.

(53) The energy comparison unit 26 receives the current state “s” and uses a weighting factor and a bias factor regarding the objective function and the constraint term to calculate the energy for the current state “s”. In addition, the energy comparison unit 26 holds the minimum energy and a state when the minimum energy is obtained (minimum energy state S). When the energy obtained from the current state “s” is lower than the minimum energy obtained so far, the energy comparison unit 26 updates the minimum energy and stores the state “s” as the minimum energy state S. Further, the energy comparison unit 26 outputs the minimum energy state S.

(54) Such an energy comparison unit 26 may be implemented using, for example, a comparator, a register, or a memory (e.g., a RAM).

(55) Hereinafter, an operation example of the optimization device 20 will be described.

(56) FIG. 2 is a flowchart illustrating a flow of an example of the operation performed by the optimization device.

(57) First, in the optimization device 20, the number of iterations is initialized by a controller (controller) (not illustrated) that manages the number of iterations (step S1). Thereafter, an energy change {−ΔE.sub.oi} and an energy change {−ΔE.sub.pi_nl} (a constraint term evaluation value) are calculated by the above-described processing of the objective function calculation unit 22 and the constraint term calculation unit 23 (step S2).

(58) Then, the transition controller 25 calculates the evaluation value {−ΔE.sub.i}={−ΔE.sub.oi}+{−ΔE.sub.pi_nl} that is the sum of the change value {−ΔE.sub.oi} and the constraint term evaluation value {−ΔE.sub.pi_nl} (step S3), and performs a stochastic search (step S4). The stochastic search includes the above-described processing of the transition controller 25 determining stochastically whether to accept any of the plurality of state transitions based on {−ΔE.sub.i}, the temperature T, and the random number value, and the above-described processing of the state holding unit 21 updating the state variable based on the transition propriety F and the transition number N.

(59) Thereafter, the number of iterations is incremented by the controller (step S5), and it is determined whether the number of iterations has reached a predetermined number (step S6). When it is determined that the number of iterations has not reached the predetermined number, the process from step S2 is repeated. When it is determined that the number of iterations has reached the predetermined number, the controller causes the energy comparison unit 26 to output the minimum energy state S (step S7) and ends the process. Although not illustrated in FIG. 2, in order to implement the simulated annealing method, the temperature controller 24 performs a control to lower the temperature T, for example, every time the number of iterations reaches a certain number (smaller than the predetermined number). Therefore, the temperature controller 24 may perform processing of the controller (controller) that manages the number of repetitions.

(60) The optimization device 20 as described above does not use an energy difference between the constraint terms before and after a change in any of the plurality of state variables to determine a transition propriety, but calculates the constraint term evaluation value, which is the evaluation value of the constraint term, for each of the plurality of state transitions, to use the constraint term evaluation value for determining the transition propriety. For example, when the energy of the constraint term in a constraint violation state that violates a plurality of constraint conditions becomes larger and an energy difference between the constraint terms is used to determine the transition propriety, the difference also becomes larger and the acceptance probability of transition to the constraint violation state becomes smaller.

(61) In contrast, by using the constraint term evaluation value as described above, the optimization device 20 may limit the increase of {−ΔE.sub.i} even when the energy of the constraint term is large, and the acceptance probability of transition to the constraint violation state may be increased. This may accelerate a transition (transition that goes beyond the potential peak) from a certain energy state to a lower energy state via a constraint violation state, thereby speeding up the search for the ground state. That is, the time to reach optimization may be shortened.

(62) Further, the constraint term calculation unit 23 may easily check whether the current state includes a constraint violation by outputting the calculated constraint term energy E.sub.p. This is because the presence or absence of a constraint violation may be determined based on whether the energy E.sub.p is 0. The constraint term energy E.sub.p when the minimum energy state S is obtained may be stored in a register or a memory. Thereby, it may be easily checked whether the minimum energy state S includes a constraint violation.

Nonlinear Processing Example

(63) Hereinafter, an example of nonlinear processing performed at the time of calculation of the energy change {−ΔE.sub.pi_nl} in the constraint term evaluation value will be described.

(64) The nonlinear processing is performed using, for example, one of the following three nonlinear functions.

(65) FIG. 3 is a view illustrating examples of a nonlinear function.

(66) An example of a first nonlinear function (nonlinear function 1) is a function that may limit the upper limit of the constraint term energy E.sub.p most simply.

(67) The nonlinear function 1 flattens (in a stepped form with one stage) f(E.sub.p_i) and f(E.sub.p_current) (hereinafter collectively referred to as f(E.sub.p)), which are the above-described nonlinear constraint terms. For example, as illustrated in FIG. 3, when the constraint term energy E.sub.p is larger than 0 (i.e., in the constraint violation state) or when f(E.sub.p)=p.sub.a, that is, when the energy E.sub.p is 0 (i.e., not in the constraint violation state), the nonlinear function 1 is a function of f(E.sub.p)=0.

(68) The sign P.sub.a, which is a penalty coefficient parameter, is a constant value greater than zero. The penalty coefficient parameter p.sub.a is smaller than the maximum value of the energy of the constraint term and is appropriately set so that the minimum energy state S does not violate any constraint condition.

(69) In a case where such a nonlinear function 1 is used, even when any condition violates certain constraint conditions, f(E.sub.p), which is a nonlinear constraint term of the energy E.sub.p of the constraint term in that state, becomes a constant upper limit value (=p.sub.a).

(70) A second nonlinear function example (nonlinear function 2) is to step f(E.sub.p) according to the energy E.sub.p (in a stepped form with multiple stages). For example, as illustrated in FIG. 3, the nonlinear function 2 is a function that sets f(E.sub.p) to 0 when the constraint term energy E.sub.p is 0, f(E.sub.p) to p.sub.A when 0<E.sub.p≤a, f(E.sub.p) to p.sub.B when a<E.sub.p≤b, and f(E.sub.p) to p.sub.C when b<E.sub.p.

(71) The signs p.sub.A, p.sub.B, and p.sub.C, which are penalty coefficient parameters, have a relationship of 0<p.sub.A<p.sub.B<p.sub.C. The penalty coefficient parameter p.sub.C, which is the largest of the penalty coefficient parameters p.sub.A, p.sub.B, and p.sub.C, is smaller than the maximum value of the energy of the constraint term and is appropriately set within a range in which the state transition acceptance probability is maintained to a certain extent.

(72) When such a nonlinear function 2 is used, since a plurality of f(E.sub.p)s corresponding to the constraint term energy E.sub.p may be obtained, the state transition acceptance probability may be changed in a plurality of stages according to the number of state constraint violations. Further, in a case where the nonlinear function 2 is used, even when a certain state violates certain constraint conditions, f(E.sub.p), which is a nonlinear constraint term of the constraint term energy E.sub.p in that state, does not increase over the penalty coefficient parameter p.sub.C (upper limit value).

(73) In the example of the nonlinear function 2 in FIG. 3, f(E.sub.p) is changed in four steps according to the energy E.sub.p. However, f(E.sub.p) may be changed in three steps or five or more steps.

(74) A third nonlinear function example (nonlinear function 3) is to change f(E.sub.p) into a curved shape according to the energy E.sub.p. The nonlinear function 3 is a function that converges f(E.sub.p) to a predetermined upper limit value as the energy E.sub.p increases, for example, as illustrated in FIG. 3. Such a nonlinear function 3 may be implemented by information (table information) indicating a correspondence relationship between the energy E.sub.p and the energy function f(E.sub.p), which is stored in advance in a memory that may be referred to by the constraint term calculation unit 23. The nonlinear function 3 may also be implemented by the constraint term calculation unit 23 performing a monotonically increasing function calculation.

(75) When such a nonlinear function 3 is used, since f(E.sub.p) may be expressed more finely according to the constraint term energy E.sub.p, the constraint term may be optimized efficiently.

Second Embodiment

(76) FIG. 4 is a view illustrating an example of an optimization device according to a second embodiment. In FIG. 4, the same elements as those in the optimization device 20 illustrated in FIG. 1 are denoted by the same reference numerals.

(77) In the optimization device 30 according to the second embodiment, a constraint term calculation unit 23a has the same function as the constraint term calculation unit 23 according to the optimization device 20, and further has a function of validating or invalidating the function of calculating the energy {−ΔE.sub.pi_nl} according to an enable signal EN.

(78) For example, the constraint term calculation unit 23a validates the function of calculating the energy change {−ΔE.sub.pi_nl} when the enable signal EN is 1, and invalidates the function of calculating the energy change {−ΔE.sub.pi_nl} when the enable signal EN is 0. Such a function may be implemented by a circuit such as a selector that selects whether to supply the calculated energy change {−ΔE.sub.pi_nl} or whether to supply 0 instead of the energy change {−ΔE.sub.pi_nl} to the transition controller 25, for example, based on the enable signal EN. The constraint term calculation unit 23a supplies 0 to the transition controller 25 when the enable signal EN is 0, and supplies the calculated energy change {−ΔE.sub.pi_nl} to the transition controller 25 when the enable signal EN is 1.

(79) The enable signal EN is input from, for example, a mode switching controller 31 as illustrated in FIG. 4. The mode switching controller 31 and the temperature controller 24 may be the same controller (controller).

(80) In a combinatorial optimization problem in which a state often passes through a constraint violation state that violates a plurality of constraint conditions during stochastic search, processing performed by the constraint term calculation unit 23 of the optimization device 20 according to the first embodiment is effective. However, a problem in which a state rarely passes through a constraint violation state that violates a plurality of constraint conditions may be sufficiently solved by the optimization device 10 as illustrated in FIG. 7. When solving such a problem, the constraint term calculation unit 23a invalidates the function of calculating the energy change {−ΔE.sub.pi_nl} as described above. Then, when the objective function calculation unit 22 outputs the energy change {−ΔE.sub.i} for the evaluation function including the constraint term as the energy change {−ΔE.sub.oi}, the optimization device 30 may be used as the optimization device 10 illustrated in FIG. 7.

Example of Processing of Separating Weighting Factor and Bias Factor

(81) In the above description, the weighting factor and the bias factor related to the objective function, and the weighting factor and the bias factor related to the constraint term are separated from each other. However, this separation processing may be performed by the optimization devices 20 and 30.

(82) FIG. 5 is a flowchart illustrating a flow of an example of the operation by an optimization device including the processing of separating the weighting factor and the bias factor.

(83) First, a weighting factor and a bias factor externally supplied from the optimization devices 20 and 30 are separated into an objective function component and a constraint term component by a controller (not illustrated) in the optimization devices 20 and 30 (step S10).

(84) FIG. 6 is a view illustrating an example of separation of an objective function component and a constraint term component.

(85) For example, as illustrated in FIG. 6, the controller separates lower bits in the weighting factor and the bias factor into an objective function component, and upper bits therein into a constraint term component. Then, the controller stores the weighting factor and the bias factor of the objective function component in a register or a memory of the objective function calculation unit 22, and stores the weighting factor and the bias factor of the constraint term component in a register or a memory of the constraint term calculation unit 23 or 23a.

(86) In FIG. 5, the processes of steps S11 to S17 are the same as those of steps S1 to S7 illustrated in FIG. 2.

(87) By performing the separation processing as described above in the optimization devices 20 and 30, the objective function component and the constraint term component of the weighting factor and the bias factor may not separately be received from memories outside the optimization devices 20 and 30.

(88) According to an aspect of the embodiments, the search for the ground state may be speeded up.

(89) All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to an illustrating of the superiority and inferiority of the invention. Although the embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.