Optimization apparatus and control method for optimization apparatus using ising models

Patent metadata

Field	Value
Publication number	US-11599073-B2
Application number	US-201916284101-A
Country	US
Kind code	B2
Filing date	Feb 25, 2019
Priority date	Mar 16, 2018
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

Abstract

A problem is inputted into an operation unit. A computation unit searches for a ground state of an Ising model. A management unit converts the problem inputted from the operation unit to the Ising model, inputs the Ising model produced by conversion and initial operating conditions into the computation unit, and has the computation unit search for the ground state using overall operating conditions produced by changing the initial operating conditions based on a result of the computation unit searching for the ground state using the initial operating conditions.

First claim

What is claimed is:

1. An optimization apparatus comprising: a computation circuit that searches for a ground state of an Ising model by using a simulated annealing or an exchange Monte Carlo method; and
a processor that converts a problem inputted from an input device to the Ising model, inputs the Ising model and initial operating conditions which include values of parameters of the simulated annealing or the exchange Monte Carlo method into the computation circuit, and causes the computation circuit to search for the ground state using the initial operating conditions, produces overall operating conditions by changing at least one of the values of the parameters included in the initial operating conditions when a result of the computation circuit searching for the ground state using the initial operating conditions changes while search for the ground state is executed a predetermined number of times, and causes the computation circuit to search for the ground state using the overall operating conditions.

2. The optimization apparatus according to claim 1 , wherein
the computation circuit includes a plurality of first computation circuits, and
the processor inputs respectively different initial operating conditions into each of the plurality of first computation circuits and exchanges the initial operating conditions inputted into a second computation circuit and a third computation circuit, out of the plurality of first computation circuits, in accordance with an exchange probability based on results of searches for the ground state by the plurality of first computation circuits.

3. The optimization apparatus according to claim 1 , wherein
the computation circuit includes a plurality of first computation circuits, and
the processor inputs respectively different initial operating conditions into each of the plurality of first computation circuits and inputs respectively different overall operating conditions, which have been produced by changing the initial operating conditions, into each of the plurality of first computation circuits based on results of searches for the ground state by the plurality of first computation circuits.

4. The optimization apparatus according claim 1 , wherein the processor includes:
a first management unit that converts the problem to the Ising model; and
a second management unit that is implemented in a computation apparatus in which the computation circuit is provided and that converts the initial operating conditions to the overall operating conditions.

5. The optimization apparatus according to claim 1 , wherein the processor holds the result of the computation circuit searching for the ground state.

6. The optimization apparatus according to claim 1 , wherein the parameters are first parameters used for the simulated annealing or second parameters used for the exchange Monte Carlo method,
the first parameters including at least one of an initial temperature, a final temperature and a cooling rate,
the second parameters including at least one of a highest temperature, a lowest temperature, a temperature interval and a number of replicas.

7. The optimization apparatus according to claim 1 , wherein the processor produces the overall operating conditions when an energy of the Ising model or a variation in the energy is larger than a predetermine value after the search for the ground state is executed the predetermined number of times.

8. A control method for an optimization apparatus, the method comprising:
converting, by a processor of an optimization apparatus, a problem that has been inputted from an input device into an Ising model;
inputting, by the processor, the Ising model and initial operating conditions which include values of parameters of a simulated annealing or an exchange Monte Carlo method into a computation circuit of the optimization apparatus, the computation circuit searching for a ground state of the Ising model by using the simulated annealing or the exchange Monte Carlo method;
causing, by the processor, the computation circuit to search for the ground state using the initial operating conditions;
producing, by the processor, overall operating conditions by changing at least one of the values of the parameters included in the initial operating conditions when a result of the computation circuit searching for the ground state using the initial operating conditions changes while search for the ground state is executed a predetermined number of times; and
causing, by the processor, the computation circuit to search for the ground state using the overall operating conditions.

9. The control method for the optimization apparatus according to claim 8 , wherein the processor holds the result of the computation circuit searching for the ground state.

10. The control method for the optimization apparatus according to claim 8 , wherein the parameters are first parameters used for the simulated annealing or second parameters used for the exchange Monte Carlo method,
the first parameters including at least one of an initial temperature, a final temperature and a cooling rate,
the second parameters including at least one of a highest temperature, a lowest temperature, a temperature interval and a number of replicas.

11. The control method for the optimization apparatus according to claim 8 , wherein the processor produces the overall operating conditions when an energy of the Ising model or a variation in the energy is larger than a predetermine value after the search for the ground state is executed the predetermined number of times.

12. A non-transitory computer-readable recording medium storing therein a computer program that causes a processor of an optimization apparatus to execute a process comprising:
converting a problem that has been inputted from an input device into an Ising model;
inputting the Ising model and initial operating conditions which include values of parameters of a simulated annealing or an exchange Monte Carlo method into a computation circuit of the optimization apparatus, the computation circuit searching for a ground state of the Ising model by using the simulated annealing or the exchange Monte Carlo method;
causing the computation circuit to search for the ground state using the initial operating conditions;
producing overall operating conditions by changing at least one of the values of the parameters included in the initial operating conditions when a result of the computation circuit searching for the ground state using the initial operating conditions changes while search for the ground state is executed a predetermined number of times; and
causing the computation circuit to search for the ground state using the overall operating conditions.

13. The non-transitory computer-readable recording medium according to claim 12 , wherein the process further includes holding the result of the computation circuit searching for the ground state.

14. The non-transitory computer-readable recording medium according to claim 12 , wherein the parameters are first parameters used for the simulated annealing or second parameters used for the exchange Monte Carlo method,
the first parameters including at least one of an initial temperature, a final temperature and a cooling rate,
the second parameters including at least one of a highest temperature, a lowest temperature, a temperature interval and a number of replicas.

15. The non-transitory computer-readable recording medium according to claim 12 , wherein the process further includes:
producing the overall operating conditions when an energy of the Ising model or a variation in the e

Assignees

• Fujitsu Ltd

Inventors

• Koyama Jumpei
• Takemoto Kazuya
• Takatsu Motomu
• Matsubara Satoshi
• Shibasaki Takayuki
• Yoneoka Noboru
• Miyazawa Toshiyuki
• Ohwada Akihiko
• Tsukamoto Sanroku

Classifications

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06N3/08

  Learning methods · CPC title

• G06F7/588

  Random number generators, i.e. based on natural stochastic processes · CPC title

• G06N5/01

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

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title