Optimization device and control method of optimization device

Patent metadata

Field	Value
Publication number	US-11150615-B2
Application number	US-201916675278-A
Country	US
Kind code	B2
Filing date	Nov 6, 2019
Priority date	Dec 26, 2018
Publication date	Oct 19, 2021
Grant date	Oct 19, 2021

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.

First claim

What is claimed is:

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.

Assignees

• Fujitsu Ltd

Inventors

• Matsubara Satoshi
• Takatsu Motomu

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G05B17/02 Primary

  electric · CPC title

• G05B13/041 Primary

  in which a variable is automatically adjusted to optimise the performance · CPC title

• G05B13/024 Primary

  in which a parameter or coefficient is automatically adjusted to optimise the performance · CPC title