US 10,885,147 B2Granted

Optimization apparatus and control method thereof

AssigneeFujitsu Limited

InventorMotomu Takatsu

Life of this patent

Estimating the term…

Loading patent…

Abstract

A first evaluation function calculation unit and a second evaluation function calculation unit calculate a cost function term Ei and a penalty function term Pi in an evaluation function, respectively. A transition control unit stochastically determines whether to accept any of state transitions, based on a product of a ratio between an inverse temperature βi and a penalty factor αi and Pi and Ei. An exchange control unit supplies βi and αi to each annealing unit, βi and αi having been set such that each annealing unit has a different ratio between βi and αi, receives Ei and Pi from each annealing unit, and exchanges βi between first and second annealing units among the plurality of annealing units and αi between the first and second annealing units, in accordance with a probability based on βi, αi, Ei, and Pi of the first and second annealing units.

Claims7

Dependent claims

An optimization apparatus comprising:

a plurality of annealing circuits;
and
an exchange control circuit,
wherein each of the plurality of annealing circuits includes
a state storage circuit that holds values of a plurality of state variables included in an evaluation function that represents an energy,
a first calculation circuit that calculates, upon occurrence of at least one state transition in which any of the values of the plurality of state variables changes, a cost function term in the evaluation function for each of a plurality of state transitions,
a second calculation circuit that calculates, upon occurrence of the at least one state transition in which any of the values of the plurality of state variables changes, a penalty function term in the evaluation function for each of the plurality of state transitions, and
a transition control circuit that stochastically determines whether to accept any of the plurality of state transitions, based on a product of a ratio between an inverse temperature and a penalty factor and the penalty function term and the cost function term, and
wherein the exchange control circuit supplies temperature information that indicates the inverse temperature and the penalty factor to each of the plurality of annealing circuits, the temperature information and the penalty factors having been set such that each of the plurality of annealing circuits has a different ratio between the inverse temperature and the penalty factor, receives the cost function term and the penalty function term from each of the plurality of annealing circuits, and exchanges an inverse temperature indicated by a temperature information supplied to a first annealing circuit with an inverse temperature indicated by a temperature information supplied to a second annealing circuit among the plurality of annealing circuits and a penalty factor supplied to the first annealing circuit with a penalty factor supplied to the second annealing circuit, in accordance with a probability based on the inverse temperatures, the penalty factors, the cost function terms, and the penalty function terms of the first annealing circuit and the second annealing circuit.

6 more elements

A control method of an optimization apparatus, the control method comprising:

holding, by a state storage unit included in each of a plurality of annealing units, values of a plurality of state variables included in an evaluation function that represents an energy;
calculating, by a first calculation unit included in each of the plurality of annealing units, upon occurrence of at least one state transition in which any of the values of the plurality of state variables changes, a cost function term in the evaluation function for each of a plurality of state transitions;
calculating, by a second calculation unit included in each of the plurality of annealing units, upon occurrence of the at least one state transition in which any of the values of the plurality of state variables changes, a penalty function term in the evaluation function for each of the plurality of state transitions;
stochastically determining, by a transition control unit included in each of the plurality of annealing units, whether to accept any of the plurality of state transitions, based on a product of a ratio between an inverse temperature and a penalty factor and the penalty function term and the cost function term;
and
supplying, by an exchange control unit, temperature information that indicates the inverse temperature and the penalty factor to each of the plurality of annealing units, the temperature information and the penalty factors having been set such that each of the plurality of annealing units has a different ratio between the inverse temperature and the penalty factor, receiving the cost function term and the penalty function term from each of the plurality of annealing units, and exchanging an inverse temperature indicated by a temperature information supplied to a first annealing unit with an inverse temperature indicated by a temperature information supplied to a second annealing unit among the plurality of annealing units and a penalty factor supplied to the first annealing unit with a penalty factor supplied to the second annealing unit, in accordance with a probability based on the inverse temperatures, the penalty factors, the cost function terms, and the penalty function terms of the first annealing unit and the second annealing unit.

3 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/269,676Filed 7 Feb 2019
Priority: JP 2018-04389612 Mar 2018
Published: US 2019/0278829 A112 Sep 2019
Granted: 5 Jan 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 17/17
Complex mathematical operations: function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method
G06N 5/01
Computing arrangements using knowledge-based models: dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
G06N 3/047
Architecture, e.g. interconnection topology: probabilistic or stochastic networks
G06N 3/044
Architecture, e.g. interconnection topology: recurrent networks, e.g. Hopfield networks