Optimization apparatus and optimization method

Patent metadata

Field	Value
Publication number	US-11526740-B2
Application number	US-202016874735-A
Country	US
Kind code	B2
Filing date	May 15, 2020
Priority date	May 29, 2019
Publication date	Dec 13, 2022
Grant date	Dec 13, 2022

Abstract

An optimization method includes holding combining destination information indicating a combining destination neuron to be combined with a target neuron which is one of a plurality of neurons corresponding to a plurality of spins of an Ising model obtained by converting an optimization problem, the target neuron being different in a plurality of neuron circuits; holding a weighting coefficient indicating a strength of combining between the target neuron and the combining destination neuron, and outputting the weighting coefficient corresponding to the combining destination information; permitting an update of a value of the target neuron by using the weighting coefficient output and the value of the update target neuron, and outputting a determination result indicating whether or not the value of the target neuron is permitted to be updated; and determining the update target neuron based on the plurality of determination results respectively output and outputting the update target information.

First claim

What is claimed is:

1. An optimization apparatus comprising:
a plurality of neuron circuits respectively including:
a first memory that stores combining destination information indicating a combining destination neuron to be combined with a target neuron which is one of a plurality of neurons corresponding to a plurality of spins of an Ising model obtained by converting an optimization problem, receives update target information indicating an update target neuron for which a value is to be updated, and outputs a signal indicating the combining destination information which coincides with the update target information,
a second memory that stores a weighting coefficient indicating a strength of combining between the target neuron and the combining destination neuron, and outputs the weighting coefficient corresponding to the combining destination information indicated by the signal output from the first memory, and
a computing circuit that stochastically permits an update of a value of the target neuron by using the weighting coefficient output from the second memory and a change of the value by a spin of a bit of the update target neuron, and outputs a determination result indicating whether the value of the target neuron is permitted to be updated, and

respectively configured to output the determination result for the target neuron different from each other; and
an update control circuit configured to determine the update target neuron based on a plurality of determination results output from the plurality of neuron circuits, update the value of the update target neuron, and output the update target information.

2. The optimization apparatus according to claim 1 ,
wherein the first memory outputs coincidence determination information indicating whether the combining destination information which coincides with the update target information is held, and
when a neuron circuit of the plurality of neuron circuits which outputs the coincidence determination information indicating that the combining destination information which coincides with the update target information is not held outputs the determination result indicating that the value of the target neuron is permitted to be updated, the update control circuit determines the target neuron as one of the update target neurons.

3. The optimization apparatus according to claim 1 , wherein the first memory is a content-addressable memory.

4. An optimization method comprising:
storing, by a first memory included in each of the plurality of neuron circuits, combining destination information indicating a combining destination neuron to be combined with a target neuron which is one of a plurality of neurons corresponding to a plurality of spins of an Ising model obtained by converting an optimization problem, the target neuron being different in a plurality of neuron circuits, receiving update target information indicating an update target neuron for which a value is to be updated, and outputting a signal indicating the combining destination information which coincides with the update target information;
storing, by a second memory included in each of the plurality of neuron circuits, a weighting coefficient indicating a strength of combining between the target neuron and the combining destination neuron, and outputting the weighting coefficient corresponding to the combining destination information indicated by the signal output from the first memory;
stochastically permitting, by a computing circuit included in each of the plurality of neuron circuits, an update of a value of the target neuron by using the weighting coefficient output from the second memory and a change of the value by a spin of a bit of the update target neuron, and outputting a determination result indicating whether the value of the target neuron is permitted to be updated; and
determining, by an update control circuit, the update target neuron based on the plurality of determination results respectively output from the computing circuits of a plurality of the neuron circuits, updating the value of the update target neuron, and outputting the update target information.

Assignees

• Fujitsu Ltd

Inventors

• Tsukamoto Sanroku
• Tamura Hirotaka
• Matsubara Satoshi

Classifications

• G06N3/047 Primary

  Probabilistic or stochastic networks · CPC title

• G06N7/01

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

• G06N3/044

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

• G06N3/08

  Learning methods · CPC title

• G06N3/082

  modifying the architecture, e.g. adding, deleting or silencing nodes or connections · CPC title