Optimization system, optimization apparatus, and optimization system control method for solving optimization problems by a stochastic search

Patent metadata

Field	Value
Publication number	US-11715003-B2
Application number	US-201916266165-A
Country	US
Kind code	B2
Filing date	Feb 4, 2019
Priority date	Feb 6, 2018
Publication date	Aug 1, 2023
Grant date	Aug 1, 2023

Abstract

An optimization apparatus calculates a first portion, among energy change caused by change in value of a neuron of a neuron group, caused by influence of another neuron of the neuron group, determines whether to allow updating the value, based on a sum of the first and second portions of the energy change, and repeats a process of updating or maintaining the value according to the determination. An arithmetic processing apparatus calculates the second portion caused by influence of a neuron not belonging to the neuron group and an initial value of the sum. A control apparatus transmits data for calculating the second portion and the initial value to the arithmetic processing apparatus, and the initial value and data for calculating the first portion to the optimization apparatus, and receives the initial value from the arithmetic processing apparatus, and a value of the neuron group from the optimization apparatus.

First claim

What is claimed is:

1. An optimization system comprising:
an optimization apparatus;
an arithmetic processing apparatus; and
a control apparatus,
the optimization apparatus is configured to repeat an update process including a first process, a second process and a third process, the optimization apparatus calculates, in the first process, a first change portion of an energy change caused by a change in a value of a first neuron that belongs to a neuron group selected from all neurons corresponding to all state variables of an evaluation function indicative of an energy, the first change portion is caused by an influence of another neuron that belongs to the neuron group, the optimization apparatus determines, in the second process, by a stochastic search whether to allow an update of the value of the first neuron, based on a first sum of the first change portion which is calculated by the optimization apparatus and a second change portion of the energy change, the second change portion is caused by an influence of a second neuron that is included in all the neurons but does not belong to the neuron group and is calculated by the arithmetic processing apparatus, and the optimization apparatus updates or maintains, in the third process, the value of the first neuron according to a result of determining whether to allow the update;
the arithmetic processing apparatus is configured to calculate the second change portion and calculate a first initial value of a second sum by adding a second initial value of the first change portion to the second change portion;
the control apparatus is configured to select the neuron group from all the neurons, transmit to the arithmetic processing apparatus first data for calculating the second change portion and the second initial value, receive the first initial value from the arithmetic processing apparatus, transmit to the optimization apparatus the first initial value and second data which includes a first weighting coefficient group whose values are set so that the first neuron is coupled to all other neurons of the neuron group, and receive a value of the neuron group from the optimization apparatus;
the optimization system further includes a plurality of optimization apparatuses including the optimization apparatus; and
the plurality of optimization apparatuses perform the update process for different neuron groups,
the optimization apparatus includes a memory and a plurality of integrators, the memory stores the first initial value received from the control apparatus, and a first integrator among the plurality of integrators acquires the first initial value from the memory, calculates the first change portion by accumulating a product of a value of a neuron included in the all other neurons and a weighting coefficient between the neuron and the first neuron and calculates the first sum by adding the first change portion to the first initial value, the weighting coefficient being included in the first weighting coefficient group.

2. The optimization system according to claim 1 , wherein the first data includes a second weighting coefficient group whose values are set so that the first neuron is coupled to some of all the neurons, the some of the all the neurons including the second neuron.

3. The optimization system according to claim 1 , wherein the control apparatus transmits, upon selection of a first neuron group, the first sum updated based on a value of a previously selected second neuron group received from a first optimization apparatus that has performed the update process for the second neuron group to a second optimization apparatus that performs the update process for the first neuron group.

4. The optimization system according to claim 2 , wherein:
the control apparatus transmits the second weighting coefficient group to the optimization apparatus, detects an updated neuron by the value of the neuron group received from the optimization apparatus, and transmits information regarding the updated neuron to the optimization apparatus; and
the optimization apparatus updates the first sum, based on the second weighting coefficient group and the information received.

5. The optimization system according to claim 2 , wherein the control apparatus transmits the second weighting coefficient group to the plurality of optimization apparatuses, detects an updated neuron by the value of the neuron group received from a first optimization apparatus that has performed the update process for the neuron group, and transmits information regarding the updated neuron to a second optimization apparatus different from the first optimization apparatus among the plurality of optimization apparatuses; and
the second optimization apparatus updates the first sum, based on the second weighting coefficient group and the information received.

6. An optimization apparatus comprising:
a storage section configured to store data for calculating a first change portion of an energy change caused by a change in a value of a first neuron that belongs to a neuron group selected from all neurons corresponding to all state variables of an evaluation function indicative of an energy, and the first change portion being caused by an influence of another neuron that belongs to the neuron group, the data including a first weighting coefficient group whose values are set so that the first neuron is coupled to all other neurons of the neuron group; and
a stochastic search circuit configured to repeat an update process including a first process, a second process and a third process,
the stochastic search circuit calculates, in the first process, the first change portion, based on the data,
the stochastic search circuit determines, in the second process, by a stochastic search whether to allow an update of the value of the first neuron, based on a first sum of the first change portion and a second change portion of the energy change, the second change portion being caused by an influence of a second neuron that is included in all the neurons but does not belong to the neuron group and being calculated by an arithmetic processing apparatus, and
the stochastic search circuit updates or maintains, in the third process, the value of the first neuron according to a result of determining whether to allow the update,
the optimization apparatus further comprising:
a memory configured to store a first initial value of a second sum calculated by adding a second initial value of the first change portion to the second change portion, and
a plurality of integrators configured to include a first integrator which acquires the first initial value from the memory, calculates the first change portion by accumulating a product of a value of a neuron included in the all other neurons and a weighting coefficient between the neuron and the first neuron and calculates the first sum by adding the first change portion to the first initial value, the weighting coefficient being included in the first weighting coefficient group.

7. An optimization system control method comprising:
repeating, by an optimization apparatus included in an optimization system, an update process including a first process, a second process and a third process;
calculating by the optimization apparatus, in the first process, a first change portion of an energy change caused by a change in a value of a first neuron that belongs to a neuron group selected from all neurons corresponding to all state variables of an evaluation function indicative of an energy, the first change portion being caused by an influence of another neuron that belongs to the neuron group;
determining by the optimization apparatus, in the second process, by a stochastic search whether to allow an update of the value of the first neuron, based o

Assignees

• Fujitsu Ltd

Inventors

• Tsukamoto Sanroku
• Matsubara Satoshi
• Tamura Hirotaka

Classifications

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06N3/08 Primary

  Learning methods · CPC title

• G06N3/0495

  Quantised networks; Sparse networks; Compressed networks · CPC title

• G06N3/063 Primary

  using electronic means · CPC title

• G06N5/01

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