Optimization method, information processing apparatus, and system using the same
Provided is an optimization method including executing a ground state search for an interaction model by a ground state search in a surrogate interaction model including D (D is a natural number of three or more) variable groups each having N continuous variables by using an information processing apparatus, the interaction model having a third-order or higher-order energy function including N (N is a natural number) continuous variables and discrete variables. The ground state search is executed based on simulated annealing. An interaction relation of the surrogate interaction model has a complete D-part graph structure. A coupling is set between i-th variable pairs in the respective variable groups of the surrogate interaction model. The information processing apparatus is operated to simultaneously update all variables of one variable group from among the D variable groups when performing a state transition in the surrogate interaction model.
1. An optimization method comprising
executing a ground state search for an interaction model by a ground state search in a surrogate interaction model including D (D is a natural number of three or more) variable groups each having N continuous variables by using an information processing apparatus, the interaction model having a third-order or higher-order energy function including N (N is a natural number) continuous variables and discrete variables,
wherein the ground state search is executed based on simulated annealing,
an interaction relation of the surrogate interaction model has a complete D-part graph structure,
a coupling is set between i-th variable pairs in the respective variable groups of the surrogate interaction model, and
the information processing apparatus is operated to simultaneously update all variables of one variable group from among the D variable groups when performing a state transition in the surrogate interaction model,
wherein the information processing apparatus includes:
D memory groups each of which includes N variable memories that store values of the N continuous variables;
a supply line which supplies a selection signal SW for selecting one of the variable groups and selecting the memory group and an update method when a value is updated;
a value of the selected memory group is updated by the selection signal SW according to the selected update method; and
an interaction coefficient memory that stores an interaction coefficient J that defines the interaction relation of the surrogate interaction model and coupling strength λ between the i-th variable pairs in the respective variable groups, and
wherein the information processing apparatus calculates a next state of the value of the memory group from the interaction coefficient J, the coupling strength λ, the variable memory, a temperature signal ST, and a random number signal SR, and
wherein the following equation is satisfied:
H
(
x
,
y
,
z
)
=
-
1
6
∑
i
,
j
,
k
J
ijk
x
i
y
j
z
k
+
λ
2
∑
i
{
(
x
i
-
y
i
)
2
+
(
y
i
-
z
i
)
2
+
(
z
i
-
x
i
)
2
}
,
where x is a first variable group, y is a second variable group, and z is a third variable group and an interaction with a magnitude J ijk acts on x i of the first variable group, y j of the second variable group, and z k of the third variable group.
2. The optimization method according to claim 1 , wherein
the coupling strength λ affects a magnitude of a penalty in a case where the i-th variable pairs of the respective variable groups have different values with respect to the energy function.
3. The optimization method according to claim 1 , wherein
the interaction coefficient J is a symmetric tensor, and
the coupling strength λ is determined from a numerical evaluation based on J.
4. The optimization method according to claim 1 , wherein
an acceptance probability P of a state transition to the next state is obtained based on a heat bath method in an algorithm of the simulated annealing.