OPTIMIZATION APPARATUS, METHOD IMPLEMENTED BY OPTIMIZATION APPARATUS, AND NONTRANSITORY COMPUTERREADABLE STORAGE MEDIUM FOR STORING PROGRAM

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. An optimization apparatus comprising:
 a memory; and
a processor coupled to the memory, the processor being configured to execute transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “
Legendre transformation,”
“
Lagrange function,” and
“
Wolfe'"'"'s duality theorem,”
execute binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function,execute Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, andexecute reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.
1 Assignment
0 Petitions
Accused Products
Abstract
An optimization apparatus includes: a memory; and a processor coupled to the memory, the processor being configured to (a): execute transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “Legendre transformation,” “Lagrange function,” and “Wolfe'"'"'s duality theorem,” (b): execute binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function, (c): execute Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and (d): execute reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.
0 Citations
No References
No References
6 Claims
 1. An optimization apparatus comprising:
a memory; and a processor coupled to the memory, the processor being configured to execute transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “
Legendre transformation,”
“
Lagrange function,” and
“
Wolfe'"'"'s duality theorem,”execute binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function, execute Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and execute reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.  View Dependent Claims (2)
 3. A method implemented by an optimization apparatus, the method comprising:
executing transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “
Legendre transformation,”
“
Lagrange function,” and
“
Wolfe'"'"'s duality theorem,”executing binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function, executing Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and executing reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.  View Dependent Claims (4)
 5. A nontransitory computerreadable storage medium for storing a program which causes a processor to perform processing, the processing comprising:
executing transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “
Legendre transformation,”
“
Lagrange function,” and
“
Wolfe'"'"'s duality theorem,”executing binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function, executing Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and executing reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.  View Dependent Claims (6)
1 Specification
This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2018199994, filed on Oct. 24, 2018, the entire contents of which are incorporated herein by reference.
The embodiments discussed herein are related to an optimization apparatus, a method implemented by an optimization apparatus, and a nontransitory computerreadable storage medium storing a program.
As a method for solving a multivariable optimization problem, at which the von Neumann computer is not good, the Ising machine (referred to as Boltzmann machine in some cases) using the Ising energy function (referred to also as cost function or objective function) exists. In the Ising machine, a problem of a calculation target is replaced by an Ising model that is a model representing the behavior of spins of a magnetic body and calculation is carried out. For example, the Ising machine finds, as a solution, the combination of the states of the respective bits with which the minimum value of the abovedescribed energy function is obtained (ground state) by simulated annealing (referred to also as SA).
Regarding the replacement of the problem of the calculation target into the Ising model, a related art is known in which the problem is replaced by the Ising model through an approximation by the qloss function because transformation to the Ising model is difficult if a term of a discontinuous function exists in a cost function deemed as the problem.
Examples of the related art include Japanese Laidopen Patent Publication, No. 10149445, Japanese National Publication of International Patent Application No. 2002522128, and V. S. Denchev, N. Ding, S. V. N. Vishwanathan, and H. Neven, “Robust classification with adiabatic quantum optimization,” in Proc. ICML'"'"'12, pp. 10031010 (2012).
According to an aspect of the embodiment, an optimization apparatus includes: a memory; and a processor coupled to the memory, the processor being configured to (a): execute transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “Legendre transformation,” “Lagrange function,” and “Wolfe'"'"'s duality theorem,” (b): execute binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function, (c): execute Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and (d): execute reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.
The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention.
However, in the abovedescribed related art, the discontinuous function is replaced by another function obtained through the approximation by the qloss function. Therefore, there is a problem that a difference arises between the solution found by the Ising machine and the value desired to be found originally and a solution with high accuracy is not obtained in some cases.
A cost function (F(W)) relating to this radiation irradiation plan is as follows. Here, the irradiation target (tumor 301 or normal tissue 302) in
First, the irradiation target is discretized (segmentation by squares in the illustrated example) and is turned to pixels lined up on one row. Here, the number of pixels is defined as I. Furthermore, suppose that N beams of the radiation exist, and the intensity thereof is represented by a vector W=(w1, w2, . . . , wN).
When the irradiation amount of the radiation at the ith pixel is defined as di(W, Mi), di(W, Mi) is represented by the following expression (1).
di(W, Mi)=Σ_{n=1}^{N}wnMin (1)
In expression (1), Min is the influence given to the ith pixel by the nth beam and may be calculated in advance. Furthermore, Mi=(Mi1, Mi2, . . . , MiN) is defined.
If a target irradiation amount (pi) is given for each pixel, the cost function F(W) relating thereto is represented by the following expression (2), with the target irradiation amount defined as M=(M1, M2, . . . , Mi). The purpose of squaring in expression (2) is to transform the function to an Ising model and ignore the sign of the difference in finding the minimum W when pi and di(W, Mi) become the closest values.
F(W)=Σ_{i}(pi−di(W, Mi))^{2} (2)
However, there is a limit to the irradiation amount depending on the organ. When the limit is put as Ci, the cost function F(W) is represented by the following expression (3).
F(W)=Σ_{i}(pi−di(W, Mi))^{2}+Σ_{i}β_{i}max(0, di(W)−Ci) (3)
The vector W of the intensity of the beams that minimizes the cost function F(W) represented in the expression (3) is the solution found as the optimization problem. Here, pi, Mi, βi, and Ci are constants set by a user. Furthermore, the first term in the cost function F(W) represented in expression (3) is a term (C(W)) that is a continuous function. The second term is a constraint term (F1(W)) and βi represents the intensity of the constraint term about each pixel. When di(W) becomes larger beyond Ci, F(W) also becomes larger. Furthermore, the second term is a discontinuous step function and therefore it is difficult to express F(W) in the Ising form without change.
Thus, in the processing (201) of transforming the cost function F(W) to the expression of the Ising model (F′(W)), F1(W) included in F(W) is squared to be replaced by a qloss function and F′(W) expressed in the twobody Ising format is output.
In the cost function F(W), F1(W) that is a discontinuous function is included. Furthermore, the number of pixels (I), the number of beams (N), the target irradiation amount (pi), the degree of influence given by the beam (Mi), the strength of the constraint (βi), and the limit amount of irradiation (Ci) are included in the cost function F(W) as constants. These constants are specified by a user.
Subsequently, for processing with the qloss function, the optimization apparatus 200 squares the discontinuous function (F1(W)) included in the cost function F(W) (S202).
Next, the optimization apparatus 200 transforms the cost function F(W) in which the discontinuous function (F1(W)) is squared to the Ising format by using the qloss function (S203). Subsequently, the optimization apparatus 200 outputs the transformed F′(W) (S204).
The qloss function may be first written as represented in the following expression (4) with use of a parameter (qϵ[−∞, 0]).
L_{q}(m)=min[(1−q)^{2}, (max[0,1−m])^{2}] (4)
Here, when a variable (tϵR) is added and the qloss function is rewritten into the Ising format, the qloss function is represented by the following expression (5).
Here, assuming q<<0, expression (4) becomes L_{q}(m)=(max[0, 1−m])^{2}. Therefore, F1 included in F is represented by the following expression (6) by using L_{q}.
Furthermore, in the Ising format, when q<<0 and a condition of ti≥1 that is the minimal condition are added, the following expression (7) is obtained.
In the expression (7), t is set to a constant 1 (canceled out with the constant term 1) and F′(W) of the following expression (8) is obtained. In the F′(W), the constraint term is represented in the square form. The optimization apparatus 200 outputs the obtained F′(W).
F′(w)=(p_{i}−Σ_{n=1}^{N}w_{n}M_{in})^{2}+Σ_{i}β_{i}(C_{i}−Σ_{n=1}^{N}w_{n}M_{in})^{2} (8)
Referring back to
Subsequently, the optimization apparatus 200 calculates the weight (δ) of each bit obtained as the result of the binary expansion and sets δ_{w}(k)=2^{k−1}/(2^{k−1}−1) (S302). In this expression, k=1 to dw is satisfied.
For example, when binary expansion is carried out with bit precision (dd) for what is obtained by turning the numerical values W to binary numbers, a string wd in which the MSB is set on the left side and numerical values are turned to binary numbers to the dd bits is defined as wnd=[wd1, wd2, . . . , wddd]. The weight δ_{w }corresponding thereto is represented by the following expression (9) through multiplication of the expanded bits and the weights.
δ_{w}=[2^{dd−1}, 2^{dd−2}, . . . , 2^{1}, 2^{0}]/(2^{dd}−1) (9)
Subsequently, when the optimization apparatus 200 sets the section of Wn to αw to βw and simultaneously limits the range in the binary expansion, Wn is represented by the following expression (10).
Wn≈(αw−βw)(δ_{w}[1]*wd[1]+δ_{w}[2]*wd[2]+ . . . +δ_{w}[dd]*wd[dd])+βw (10)
For example, the optimization apparatus 200 sets n=1 to N and sets W_{n}=α_{w}Σ_{k=1}^{dw}W_{n,k}δ_{w}(k)+β_{w }(S303). W_{n,k }is what is obtained by turning Wn to binary values and is numerical values of 0 or 1 and corresponding to the Ising spins.
Subsequently, the optimization apparatus 200 outputs, as the coupling coefficients, the coefficients of the quadratic term and the linear term of Wn of the expression (Z) obtained by substituting the abovedescribed expression into F(w, t) (S304). At this time, the optimization apparatus 200 also outputs Z=[αw, βw, δw].
For example, all terms of F′ are subjected to summation regarding i and therefore are added to each other finally. First, a consideration will be made about the terms inside the total sum. Here, when A=Σ_{k=1}^{N}WnMn is defined, the inside of F′ is represented by the following expression (11).
(p−A)^{2}+β(C−A)^{2}=(1+β)A^{2}−2(P+BC)A+p^{2}+βC^{2} (11).
Here, Sr=[W_{1}, W_{2}, . . . , W_{N}] and M=[M_{1}, M_{2}, . . . , M_{N}] are defined.
In expression (11), (1+β)A^{2 }is the quadratic term and corresponds to the following coupling coefficient (Jr). Furthermore, −2(P+βC)A is the linear term and corresponds to the following coupling coefficient hr. Moreover, p^{2}+βC^{2 }is a constant term and has no relation to W and therefore will be ignored in the following.
The expression of the Ising model before the binary expansion (S is the Ising spin and is a real number) and the coupling coefficients Jr and hr are represented by the following expression (12).
Σ_{KL=1}^{N}Jr_{KL}Sr_{K}Sr_{L}+Σ_{K=1}^{N}hr_{K}Sr_{K} (12)
Thus, the coupling coefficients Jr and hr are represented by the following expressions (13) and (14).
Sr is a real number and therefore binary expansion is carried out. What results from the binary expansion is what is obtained by lining up elements resulting from binary expansion of each element of Sr in the row direction. Here, what results from the binary expansion of Sr is defined as S=[W_{1,1}, W_{1,2}, . . . , W_{N,d}]. When each element of Jr is multiplied by the weight δ_{w }and the matrix of Jr is expanded by a factor of N in the row direction and the column direction, what results from the binary expansion of Jr is represented by the following expression (15).
Similarly, also regarding hr, each element of hr is multiplied by the weight δ_{w }and the vector is expanded by a factor of N in the row direction. When the resulting vector is defined as h′, h′ is represented by the following expression (16).
h′=[−2(P+βC)M_{1}δ_{1}, . . . , −2(P+βC)M_{1}δ_{d}, . . . , −2(P+βC)M_{N}δ_{d}] (16)
Regarding the pixel (i), W as the basis of S is invariable. Regarding J′ and h′, what are finally obtained are what result from addition of i elements to each other with respect to each element and are represented by the following expressions (17) and (18). The number of bits of S is N*d in total.
In S304, the optimization apparatus 200 employs J and h of the expressions (17) and (18) as the coupling coefficients (Q) and outputs them with Z=[αw, βw, δw]. Actually, numerical values are substituted into all places of symbols.
Referring back to
Subsequently, the optimization apparatus 200 carries out reverse binary expansion for the numerical values of W′ obtained by the simulated annealing of the Ising machine (204). Thereby, the optimization apparatus 200 finds W that correspond to the numerical values of W′ and are continuous values. For example, the optimization apparatus 200 obtains Wn (continuous values) from the Ising spins (numerical values of W′) based on the following expression (19) by using the coefficients Z=[αw, βw, δw] of the binary expansion.
Wn≈(αw−βw)(δ_{w}[1]*wd[1]+δ_{w}[2]*wd[2]+ . . . +δ_{w}[dd]*wd[dd])+βw (19)
Here, the values of W′, which are the result obtained from F′(W), are correct. However, because the term that is a discontinuous max function (F1(W)) is squared to be replaced by the qloss function, W′ are approximate values from the viewpoint of F(W) and are not correct values.
For example, in formulation of a radiation irradiation plan, it is important to impose correct constraint corresponding to the linearity represented in the graph G201 on the beams with which irradiation is carried out. However, if the linearity is hot retained after the transformation as in the graph G202, it becomes difficult to impose the correct constraint and the constraint on the beams becomes less or becomes excessive in some cases.
In one aspect, the embodiments discussed herein intend to provide an optimization apparatus, an optimization method, and an optimization program that enable finding of the optimum solution with higher accuracy.
The optimization apparatus, the optimization method, and the optimization program according to the embodiments will be described below with reference to the drawings. Configurations having the same function in the embodiments are given the same numeral and overlapping description is omitted. The optimization apparatus, the optimization method, and the optimization program described in the following embodiments merely represent one example and do not limit the embodiments. Furthermore, the following respective embodiments may be combined as appropriate in a range in which contradiction is not caused.
The transforming unit 11 is a processing unit that accepts input of a cost function F(W) relating to an optimization problem and carries out transformation to an expression of an Ising model (F′(W)) by using the Legendre transformation, the Lagrange function, and the Wolfe'"'"'s duality theorem. Suppose that, in the present embodiment, the cost function F(W) input to the transforming unit 11 relates to the radiation irradiation plan exemplified in
The binary expansion unit 12 is a processing unit that subjects W to binary expansion into 0 and 1 for processing by an Ising machine because the transformed F′(W) remains continuous values. For example, similarly to the existing binary expansion (202), the binary expansion unit 12 turns values relating to coefficients of the cost function (F′(W)) transformed by the transforming unit 11 to the Ising format with binary spins through carrying out binary expansion.
The Ising machine processing unit 13 is a processing unit that executes processing based on simulated annealing (SA) by the Ising machine based on coupling coefficients (Q) and seeks values that represent the ground state.
The reverse binary expansion unit 14 carries out reverse binary expansion for the values that have been sought by the Ising machine processing unit 13 and represent the ground state, i.e. numerical values of W′ obtained by the simulated annealing of the Ising machine. For example, the reverse binary expansion unit 14 executes the processing similar to that of the existing reverse binary expansion (204) and obtains continuous values (W) corresponding to the numerical values of W′. Thereby, the reverse binary expansion unit 14 obtains the values that minimize the input cost function F(W).
Here, the processing of the respective units of the optimization apparatus 1 will be described in detail.
As illustrated in
Here, the discontinuous term (F1(W)) is a second term (Σ_{i}β_{i}max(0, di(w)−Ci)) in the cost function F(W) represented in expression (3). This discontinuous term may be specified by a user at the time of input of the cost function F(W) or may be detected from the cost function F(W) by a publiclyknown expression processing system.
Subsequently, the transforming unit 11 carries out transformation to the Ising format by using the Legendre transformation, the Lagrange function, and the Wolfe'"'"'s duality theorem regarding the term (F1(W)) that is the discontinuous term of the cost function F(W) (S2).
Here, the transformation processing of S2 will be described in detail.
As illustrated in
When the Legendre transformation is carried out regarding the discontinuous function, the nature does not change although the transformation is carried out because the resulting function is equivalently expressed by a set of tangents specified by the values of the slope and the intercept. For example, f*(p) resulting from the Legendre transformation of a function f is represented by the following expression (20).
The transforming unit 11 carries out the Legendre transformation twice for β_{i}max(0, di(w)−Ci) of the discontinuous function F1(W). This is equivalent to operation of returning the function to the original because forward transformation and inverse transformation of the Legendre transformation are the same.
For example, f1(w)=max(0, di(w)−Ci)=−min(0, Ci−di(w)) is defined. When the Legendre transformation is carried out twice for the f1, setting m=di(w)−Ci and putting f1(m)=−min(0, m) yield the following expression (21).
When the function (f1) after the Legendre transformation remains as it is, − (minus) sign exists in front of min of the function f1 and it is difficult to treat the function f1 as a minimization problem of m and t.
Therefore, the transforming unit 11 finds a dual problem based on the Wolfe'"'"'s duality theorem regarding the function (f1) after the Legendre transformation (S13). For example, property that the original problem may also be solved if the dual problem may be solved is used.
For example, the following expression (22) is obtained when the dual problem is found regarding the function (f1). Here, z_{1 }and z_{2 }are Lagrange multipliers. m is m=di(w)−Ci.
max_{t,z}{−mt−z_{1}(t+1)+z_{2}t}−m−z_{1}−z_{2}=0, z_{1}≥0, z_{2}≥0, −1≤t≤0, (22)
Furthermore, when the signs are reversed regarding expression (22), expression (23) is obtained.
−min_{t,z}{mt+z_{1}(t+1)−z_{2}t} (23)
As illustrated in
Referring back to
f1(w,t,z_{1},z_{2})=(di(w)−Ci)t+z_{1}(t+1)−z_{2}t +M(−(di(w)−Ci)−z_{1}+z_{2})^{2} (24)
Subsequently, regarding the cost function (F(W)), the transforming unit 11 outputs the whole of the function (F′(W)) in which the penalty term expressed in the twobody Ising format is incorporated instead of the discontinuous function (F1(W)) and the ranges of values.
For example, the output F′(W) is represented by the following expression (25). Furthermore, the output ranges of the values of z_{1}, z_{2}, and t are z_{1}≥0, z_{2}≥0, and −1≤t≤0.
Referring back to
Subsequently, the Ising machine processing unit 13 executes processing by an Ising machine by using the Ising format (S4). For example, the Ising machine processing unit 13 executes processing based on simulated annealing (SA) by the Ising machine based on the coupling coefficients (Q) and finds the values of the respective spins that represent the ground state.
Subsequently, the reverse binary expansion unit 14 finds the values of coefficients before the binary expansion by using the values of the spins of the processing result by the Ising machine (values of the respective spins that represent the ground state) (S5). For example, the reverse binary expansion unit 14 executes the processing similar to that of the existing reverse binary expansion (204) to carry out reverse binary expansion for the numerical values of W′ obtained by the Ising machine. Thereby, the optimization apparatus 1 obtains the values (real number values) that minimize the input cost function F(W).
As described above, the optimization apparatus 1 includes the transforming unit 11, the binary expansion unit 12, the Ising machine processing unit 13, and the reverse binary expansion unit 14. The transforming unit 11 transforms an input first cost function (F(W)) to a second cost function (F′(W)) by using the Lagrange function and the Wolfe'"'"'s duality theorem. The binary expansion unit 12 finds the coupling coefficients (Q) to turn values relating to the coefficients of the second cost function to the Ising format with binary spins through carrying out binary expansion. The Ising machine processing unit 13 seeks the values that represent the ground state regarding the coupling coefficients relating to the second cost function (F′(W)). The reverse binary expansion unit 14 carries out reverse binary expansion regarding the sought values that represent the ground state and finds the values that minimize the first cost function (F(W)).
Due to this, when describing the absolute value constraint included in the first cost function (F(W)) by an Ising model, the optimization apparatus 1 may treat the absolute value constraint as it is without changing the shape of the function (graph shape). Therefore, the optimization apparatus 1 may find the optimum solution with higher accuracy.
As illustrated in
In
Furthermore, the transforming unit 11 carries out the Legendre transformation regarding the discontinuous function (F1(W)) included in the first cost function (F(W)). Then, the transforming unit 11 carries out transformation to the second cost function (F′(W)) by incorporating a function obtained through finding a dual problem based on the Wolfe'"'"'s duality theorem based on the expression after the Legendre transformation to the first cost function instead of the discontinuous function. This allows the optimization apparatus 1 to carry out the transformation from the first cost function (F(W)) to the second cost function (F′(W)) without changing the shape of the discontinuous function (graph shape) included in the first cost function (F(W)).
The respective constituent elements of the respective apparatuses that are diagrammatically represented do not necessarily be configured as diagrammatically represented physically. For example, specific forms of distribution and integration of the respective apparatuses are not limited to the diagrammaticallyrepresented forms, and all or part of the respective apparatuses may be configured to be distributed or integrated functionally or physically in an arbitrary unit according to various loads, the status of use, and so forth.
All or an arbitrary part of various processing functions executed in the optimization apparatus 1 may be executed on a central processing unit (CPU) (or microcomputer such as microprocessing unit (MPU) or micro controller unit (MCU)). Furthermore, it goes without saying that all or an arbitrary part of various processing functions may be executed on a program analyzed and executed by the CPU (or microcomputer such as MPU or MCU) or hardware based on wired logic. Moreover, the various processing functions executed in the optimization apparatus 1 may be executed through cooperation of plural computers based on cloud computing.
Incidentally, various kinds of processing explained in the abovedescribed embodiment may be implemented by executing a program prepared in advance by a computer. Thus, one example of a computer (hardware) that executes a program having the functions similar to that of the abovedescribed embodiment will be described below.
As illustrated in
The inputoutput apparatus 100 is an input apparatus such as keyboard and mouse that accept input operation from a user and an output apparatus such as a display that outputs various processing results. The storing apparatus 101 is a hard disk apparatus or the like, for example, and a program 101a for executing various kinds of processing explained in the abovedescribed embodiment is stored therein. Furthermore, various kinds of data to which the program 101a refers are stored in the storing apparatus 101. The RAM 102 is used when the CPU 104 reads out the program 101a and executes various kinds of processing, and temporarily stores various kinds of information. The ROM 103 is a nonvolatile memory that stores a boot program executed at the time of activation of the optimization apparatus 1, and so forth, for example.
The CPU 104 executes various kinds of processing relating to the transforming unit 11, the binary expansion unit 12, the Ising machine processing unit 13, and the reverse binary expansion unit 14 by reading out the program 101a stored in the storing apparatus 101 and loading the program 101a into the RAM 102 to execute it. The program 101a does not have to be stored in the storing apparatus 101. For example, the optimization apparatus 1 may read out and execute the program 101a stored in a storage medium that may be read by the optimization apparatus 1. The storage medium that may be read by the optimization apparatus 1 is compact disc (CD)ROM, digital versatile disc (DVD) disc, portable recording medium such as universal serial bus (USB) memory, semiconductor memory such as flash memory, hard disk drive, and so forth, for example. Furthermore, the program 101a may be stored in an apparatus coupled to a public line, the Internet, a local area network (LAN), or the like and the optimization apparatus 1 may read out the program 101a from any of them and execute it.
The Ising machine 105 is an apparatus that executes processing based on simulated annealing (SA) and seeks the combination of the states of the respective bits with which the minimum value of a cost function transformed to the Ising format is obtained (ground state) under control by the Ising machine processing unit 13.
The controller 110 passes weights W_{ij }relating to coupling coefficients to the hardware optimization engine 111 and causes the hardware optimization engine 111 to execute simulated annealing (SA) processing to obtain the state of each bit. The hardware optimization engine 111 sets the weights W_{ij }from the controller 110 in each of the neurons 112 and obtains output after the SA processing from each of the neurons 112. Subsequently, the hardware optimization engine 111 outputs, to the controller 110, the output obtained from each of the neurons 112.
The plural neurons 112 are what are obtained by modeling an Ising model by using a neural network. For example, each of the plural neurons 112 functions as a neuron that outputs 0 or 1 according to the states of the other bits and the weights W_{ij }(coupling coefficients) that represent the strength of coupling between another bit and the selfbit.
For example, each of the neurons 112 includes multipliers 113, adders 114, and a comparator 116. Each of the multipliers 113 multiplies the states (x_{1}, x_{2}, . . . , x_{n}) of n neurons 112 output from the hardware optimization engine 111 and the weights W_{i1}, . . . , and W_{i,n}. The adders 114 integrate the values output from the multipliers 113 and adds noise 115. The comparator 116 outputs a comparison result between the value resulting from the integration by the adders 114 and the addition of the noise 115 and a threshold. The neuron 112 seeks the ground state by sequentially updating the parameters of the neuron 112 based on the output value obtained from the comparator 116 and repeating the processing.
All examples and conditional language provided herein are intended for the pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.