Optimization apparatus and optimization method

Patent metadata

Field	Value
Publication number	US-12039233-B2
Application number	US-202117183408-A
Country	US
Kind code	B2
Filing date	Feb 24, 2021
Priority date	Mar 26, 2020
Publication date	Jul 16, 2024
Grant date	Jul 16, 2024

Abstract

A method includes: accessing first storage configured to store a first weight coefficient group which is at least some of a plurality of weight coefficients indicating a magnitude of interaction between a plurality of state variables in an evaluation function representing energy of an Ising model; accessing a plurality of second storages each of the plurality of second storage being configured to store a second weight coefficient group related to a state variable having a value of 1 in any of a plurality of state variable groups respectively including the plurality of state variables among the plurality of weight coefficients; outputting, for each of the plurality of state variable groups, a search result obtained by performing searching processing configured to perform processing of searching for an optimum solution by repeatedly performing a first update process with a first constraint or a second update process with a second constraint.

First claim

What is claimed is:

1. An optimization apparatus comprising:
a first storage unit to store a first weight coefficient group which is at least some of a plurality of weight coefficients indicative of a magnitude of interaction between a plurality of state variables included in an evaluation function that represents energy of an Ising model;
a plurality of second storage units, the each of the plurality of second storage units to store a second weight coefficient group related to a state variable having a value of 1 in any of a plurality of state variable groups respectively including the plurality of state variables among the plurality of weight coefficients;
a searching unit to output, for each of the plurality of state variable groups, a search result obtained by performing searching processing on a respective state variable group, the searching processing being configured to perform processing of searching for an optimum solution that minimizes the energy by repeatedly performing a first update process or a second update process; and
a control unit to designate two columns, two rows, or group common to the plurality of state variable groups,
wherein the first update process includes:
obtaining a first determination result by determining, based on an amount of change in the energy of the Ising model calculated using the first weight coefficient group and the second weight coefficient group, whether to replace values of first state variables included in designated two columns or two rows between two columns or between two rows in a matrix that the N 2 (N is an integer 2 or more) first state variables among the plurality of state variables are arranged in N rows and N columns; and
in accordance with the first determination result, performing updating by replacing the first state variables included in the designated two columns or two rows while satisfying a first constraint that a sum of values of first state variables included in each column and each row of the matrix is 1,
wherein the second update process includes:
obtaining a second determination result by determining, based on the amount of change in the energy, whether to perform update any two values among values of a plurality of second state variables included in a designated group among the plurality of state variables while satisfying a second constraint that a sum of values of the second state variables included in the designated group is 1; and
in accordance with the second determination result, performing updating of two values while satisfying a second constraint that a sum of the plurality of second state variables included in the designated group is 1.

2. The optimization apparatus according to claim 1 , wherein the control unit replaces a target to be read as the first weight coefficient group and stored in the first storage unit among the plurality of weight coefficients stored in a storage apparatus for every predetermined number of the update processing.

3. The optimization apparatus according to claim 2 , wherein the control unit performs reading of the first weight coefficient group from the storage apparatus by combining a plurality of reading methods.

4. The optimization apparatus according to claim 2 , wherein the first storage unit includes a third storage unit and a fourth storage unit, and
the control unit reads a second target stored in the first storage unit as the first weight coefficient group from the storage apparatus and causes the second target to be stored in the fourth storage unit when a first target stored in the first storage unit as the first weight coefficient group is stored in the third storage unit and the update processing is performed using the first target.

5. The optimization apparatus according to claim 1 , wherein the plurality of state variables include the N square first state variable subjected to the first constraint, the plurality of second state variables subjected to the second constraint, and a third state variable not subjected to the first constraint and the second constraint, and
the searching unit performs any of update by the replacement, update of two values, or update of a value of one third state variable based on the first weight coefficient group or the second weight coefficient group.

6. The optimization apparatus according to claim 1 , wherein the searching unit updates the second weight coefficient group using the first weight coefficient group based on a result of the update processing.

7. An optimization method implemented by an optimization apparatus, the method comprising:
accessing first storage to store a first weight coefficient group which is at least some of a plurality of weight coefficients indicative of a magnitude of interaction between a plurality of state variables included in an evaluation function that represents energy of an Ising model;
accessing a plurality of second storages, the each of the plurality of second storages to store a second weight coefficient group related to a state variable having a value of 1 in any of a plurality of state variable groups respectively including the plurality of state variables among the plurality of weight coefficients;
outputting, for each of the plurality of state variable groups, a search result obtained by performing searching processing on a respective state variable group, the searching processing to perform processing of searching for an optimum solution that minimizes the energy by repeatedly performing a first update process or a second update process; and
designating two columns, two rows, or group common to the plurality of state variable groups,
wherein the first update process includes:
obtaining a first determination result by determining, based on an amount of change in the energy of the Ising model calculated using the first weight coefficient group and the second weight coefficient group, whether to replace values of first state variables included in designated two columns or two rows between two columns or between two rows in a matrix that the N 2 (N is an integer 2 or more) first state variables among the plurality of state variables are arranged in N rows and N columns; and
in accordance with the first determination result, performing updating by replacing the first state variables included in the designated two columns or two rows while satisfying a first constraint that a sum of values of first state variables included in each column and each row of the matrix is 1,
wherein the second update process includes:
obtaining a second determination result by determining, based on the amount of change in the energy, whether to perform update any two values among values of a plurality of second state variables included in a designated group among the plurality of state variables while satisfying a second constraint that a sum of values of the second state variables included in the designated group is 1; and
in accordance with the second determination result, performing updating of the two values while satisfying a second constraint that a sum of the plurality of second state variables included in the designated group is 1.

Assignees

• Fujitsu Ltd

Inventors

• Kanda Kouichi
• Tamura Hirotaka

Classifications

• G06N10/00

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title

• G06F2111/06

  Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA] · CPC title

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title

• G06N7/01

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

• G06N3/047

  Probabilistic or stochastic networks · CPC title