Patent Publication Number: US-11645496-B2

Title: Optimization apparatus and optimization apparatus control method

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2018-161212, filed on Aug. 30, 2018, the entire contents of which are incorporated herein by reference. 
     FIELD 
     The embodiments discussed herein are related to an optimization apparatus and an optimization apparatus control method. 
     BACKGROUND 
     Formerly the use of an optimization apparatus (which may also be referred to as an Ising machine or a Boltzmann machine) using an Ising-type energy function was known as a method for calculating multivariable optimization problems at which Neumann type computers are poor. The optimization apparatus performs a calculation by replacing a problem to be calculated with an Ising model indicative of the behavior of the spin of a magnetic material. 
     For example, the optimization apparatus also performs modeling of a problem by the use of a neural network. In that case, each of a plurality of bits corresponding to a plurality of spins included in the Ising model functions as a neuron which outputs “0” or “1” according to the value of another bit and a weighting value (which is also referred to as a coupling coefficient) indicative of the magnitude of the interaction between another bit and each bit itself. The optimization apparatus finds, by a stochastic search method such as simulated annealing, as a solution a combination of the state of each neuron by which the minimum value of a value of the energy function of the Ising model (hereinafter referred to as an energy) is obtained. 
     Formerly the following optimization apparatus was known. A combination of the state of each neuron which minimizes an energy is calculated by performing simulated annealing by the use of digital circuits. 
     See, for example, the following documents: 
     Japanese Laid-open Patent Publication No. 2018-041351; 
     Japanese Laid-open Patent Publication No. 2016-051314; and 
     Japanese Laid-open Patent Publication No. 2006-072691. 
     By the way, there are many optimization problems including an integer programming problem in which a variable has three or more values and not two values, that is to say, 0 and 1. 
     However, if the state of a neuron is represented by conventional optimization apparatus by the use of variables having three or more values, one variable is represented by the use of a plurality of bits. This increases the scale of circuits used for calculating a change in energy of the Ising model on the basis of which whether to update the state of a neuron is determined. 
     SUMMARY 
     According to an aspect, there is provided an optimization apparatus including a plurality of Ising units each including: a calculation circuit configured to calculate, among a plurality of neurons which correspond to a plurality of spins included in an Ising model obtained by converting a problem to be calculated and whose states are represented by using variables each having m values (m is a positive integer greater than or equal to 3), two changes in energy of the Ising model caused by a change in a state of a second neuron by 2 n  (n is an integer greater than or equal to 0) in both of positive and negative directions, based on a state change direction of a first neuron whose state has been updated and a weighting coefficient indicative of a magnitude of an interaction between the first neuron and the second neuron; and a state transition determination circuit configured to determine, based on magnitude relationships among a thermal excitation energy determined based on a random number and a temperature parameter and the two changes in energy, whether to allow updates of the state of the second neuron that cause the two changes in energy, to output determination results obtained by determining whether to allow the updates, and to limit an update by which the state of the second neuron exceeds an upper limit value or falls below a lower limit value, wherein the plurality of Ising units each output the determination results regarding different second neurons; an update neuron selection circuit configured to select, based on the determination results outputted by each of the plurality of Ising units, one second neuron whose update is allowed and to select the state change direction; and a state update circuit configured to update the state of the one second neuron selected by the update neuron selection circuit, based on the state change direction. 
     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. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG.  1    illustrates an example of an optimization apparatus according to a first embodiment; 
         FIG.  2    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the first embodiment; 
         FIG.  3    illustrates an example of an optimization apparatus according to a second embodiment; 
         FIG.  4    illustrates an example of a first ΔE change section; 
         FIG.  5    illustrates an example of a second ΔE change section; 
         FIG.  6    illustrates an example of a transition propriety determination section; 
         FIG.  7    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the second embodiment; 
         FIG.  8    illustrates an example of an optimization apparatus according to a third embodiment; 
         FIG.  9    illustrates an example of a first domain confirmation section; 
         FIG.  10    illustrates an example of a second domain confirmation section; 
         FIG.  11    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the third embodiment; 
         FIG.  12    illustrates an example of an optimization apparatus according to a fourth embodiment; 
         FIG.  13    illustrates an example of a portion of a local field update section in which a shift operation is performed; 
         FIG.  14    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the fourth embodiment; 
         FIG.  15    illustrates an example of the hardware of a control apparatus; and 
         FIG.  16    is a flow chart illustrative of the flow of an example of a method for controlling an optimization apparatus by the control apparatus. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     Embodiments will now be described with reference to the accompanying drawings. 
     There are combinations of states of a plurality of neurons corresponding to a plurality of spins included in an Ising model obtained by converting a problem to be calculated. The following optimization apparatus search for a combination of states of the plurality of neurons, of the combinations of states of the plurality of neurons, which minimizes an energy function. The state of each neuron is represented by the use of a variable having m values (m is an integer greater than or equal to 3). Furthermore, it is assumed that the variable has a determined bit width and that the variable changes in a positive or negative direction by 2 n  (n is an integer greater than or equal to 0). 
     For example, the Ising-type energy function E(x) is defined as 
     
       
         
           
             
               
                 
                   
                     E 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       - 
                       
                         
                           ∑ 
                           
                             〈 
                             
                               i 
                               , 
                               j 
                             
                             〉 
                           
                         
                         ⁢ 
                         
                           
                             W 
                             ij 
                           
                           ⁢ 
                           
                             x 
                             i 
                           
                           ⁢ 
                           
                             x 
                             j 
                           
                         
                       
                     
                     - 
                     
                       
                         ∑ 
                         i 
                       
                       ⁢ 
                       
                         
                           b 
                           i 
                         
                         ⁢ 
                         
                           x 
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     The first term of the right side means that the products of states and a coupling coefficient of two neurons are added up without omission or duplication for all possible combinations of two neurons selected from among all neurons. x i  is a variable (which is also referred to as a state variable) indicative of a state of an ith neuron. x j  is a variable indicative of a state of a jth neuron. W ij  is a weighting coefficient indicative of the magnitude of an interaction between the ith neuron and the jth neuron. W ii =0. In many cases, W ij =W ji  (that is to say, in many cases, a weighting coefficient matrix is a symmetric matrix). Furthermore, the weighting coefficient W ij  has a determined bit width (16 bits, 32 bits, 64 bits, or 128 bits, for example). 
     The second term of the right side means that the product of a bias coefficient and a variable indicative of a state of each of all the neurons is added up. b i  is a bias coefficient of the ith neuron. 
     In addition, if the variable x i  has m values and does not reach the upper limit or the lower limit, a change portion Δx i  of the variable x i  is ±2 n . 
     An energy change ΔE i±  caused by changes in the variable x i  in the positive and negative directions is given by 
     
       
         
           
             
               
                 
                   
                     Δ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       E 
                       
                         i 
                         ± 
                       
                     
                   
                   = 
                   
                     
                       E 
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     ⁢ 
                     
                       
                          
                         
                           
                             x 
                             i 
                           
                           -&gt; 
                           
                             
                               x 
                               i 
                             
                             ± 
                             
                               2 
                               n 
                             
                           
                         
                       
                       ⁢ 
                       
                         
                           - 
                           
                             E 
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                         
                         = 
                         
                           
                             
                               ∓ 
                               
                                 2 
                                 n 
                               
                             
                             ⁢ 
                             
                               ( 
                               
                                 
                                   
                                     ∑ 
                                     j 
                                   
                                   ⁢ 
                                   
                                     
                                       W 
                                       ij 
                                     
                                     ⁢ 
                                     
                                       x 
                                       j 
                                     
                                   
                                 
                                 + 
                                 
                                   b 
                                   i 
                                 
                               
                               ) 
                             
                           
                           = 
                           
                             
                               ∓ 
                               
                                 2 
                                 n 
                               
                             
                             ⁢ 
                             
                               h 
                               i 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     As given by expression (2), the energy change ΔE i±  has two values according to (positive and negative) state change directions of the ith neuron. 
     In expression (2), h i  is referred to as a local field. 
     First Embodiment 
       FIG.  1    illustrates an example of an optimization apparatus according to a first embodiment. 
     An optimization apparatus  10  according to a first embodiment includes N Ising units  11   a   1 ,  11   a   2 , . . . , and  11   a N which perform calculations regarding N neurons, an update neuron selection circuit  12 , a state update circuit  13 , and a controller  14 . Each of the Ising units  11   a   1  through  11   a N may be one-chip semiconductor integrated circuit. Alternatively, the Ising units  11   a   1  through  11   a N may be included in a one-chip semiconductor integrated circuit. 
     The Ising unit  11   a   1  performs calculations regarding a first neuron (neuron whose identification information ID is 1) of the N neurons. The Ising unit  11   a   1  includes a calculation circuit  11   b   1  and a state transition determination circuit  11   c   1 . 
     The calculation circuit  11   b   1  receives from the update neuron selection circuit  12  a state change direction DR of a neuron, of the N neurons, whose state is updated and identification information ID of the neuron. Furthermore, the calculation circuit  11   b   1  calculates energy changes ΔE 1+  and ΔE 1−  on the basis of a weighting coefficient indicative of the magnitude of an interaction between the neuron identified by the identification information ID and the first neuron and the state change direction DR. The state of the first neuron changes by 2 n  in the positive and negative directions. The energy changes ΔE 1+  and ΔE 1  are two energy changes of the Ising model caused by these changes in the state of the first neuron. 
     In the example of  FIG.  1   , the calculation circuit  11   b   1  includes a register  11   b   11 , a local field update section  11   b   12 , and an energy change calculation section  11   b   13 . 
     The register  11   b   11  stores N weighting coefficients W 11 , W 12 , . . . , and W 1N . The weighting coefficients W 11 , W 12 , . . . , and W 1N  may be stored in a memory such as static random access memory (SRAM). All weighting coefficients W 11  through W NN  may be stored in one memory. 
     On the basis of the identification information ID of the neuron whose state is updated, the local field update section  11   b   12  selects a weighting coefficient indicative of the magnitude of an interaction between the neuron and the first neuron. Furthermore, the local field update section  11   b   12  updates a local field h 1  on the basis of the selected weighting coefficient and the state change direction DR of the neuron whose state is updated. An initial value of the local field h 1  is, for example, a bias coefficient b 1 . 
     When the state of a neuron (jth neuron) changes by 2 n  in the positive direction, a change portion of the local field h 1  is expressed as +2 n W 1j . When the state of the neuron (jth neuron) changes by 2 n  in the negative direction, a change portion of the local field h 1  is expressed as −2 n W 1j . 
     Therefore, the local field update section  11   b   12  updates the local field h 1  by adding to or subtracting from the current local field h 1  according to the state change direction DR a value obtained by left-shifting the weighting coefficient W ij  by n bits. This local field update section  11   b   12  is realized by the use of, for example, a selector, an adder (or a subtractor), and a shift operation circuit. If n=0, then the shift operation circuit is not needed. 
     The energy change calculation section  11   b   13  calculates the energy changes ΔE 1+  and ΔE 1−  on the basis of expression (2). The energy change calculation section  11   b   13  is realized by the use of, for example, a shift operation circuit and a sign inversion circuit. If n=0, then the shift operation circuit is not needed. 
     On the basis of the magnitude relationships among a thermal excitation energy and the energy changes ΔE 1+  and ΔE 1− , the state transition determination circuit  11   c   1  determines whether to allow updates of the state of the first neuron that cause the energy changes ΔE 1+  and ΔE 1− . Furthermore, the state transition determination circuit  11   c   1  outputs determination results obtained by determining whether to allow the updates. In addition, the state transition determination circuit  11   c   1  limits an update by which the state of the first neuron exceeds an upper limit value or falls below a lower limit value. That is to say, the state transition determination circuit  11   c   1  prevents an update by which the state of the first neuron goes beyond a domain. For example, a domain of a variable indicative of the state of each neuron is determined according to the type of a problem and restrictions on the hardware of the optimization apparatus  10 . 
     For example, the thermal excitation energy is determined on the basis of a random number generated by a random number generation circuit described later and a temperature parameter T inputted from the controller  14 . 
     Furthermore, limit information LMT including the upper limit value and the lower limit value is supplied from the controller  14 . If the state of the first neuron changes by 2 n  in the positive or negative direction and exceeds the upper limit value or falls below the lower limit value, then the state transition determination circuit  11   c   1  changes the energy change ΔE 1+  or the energy change ΔE 1  to, for example, a sufficiently large determined positive value so that an update of the state of the first neuron will not be allowed. For example, this determined positive value may be determined on the basis of a value indicative of a result obtained by determining, at the time of the energy change being changed to the determined positive value, whether to allow an update of the state of the first neuron. 
     Furthermore, If the state of the first neuron changes by 2 n  in the positive or negative direction and exceeds the upper limit value or falls below the lower limit value, then the state transition determination circuit  11   c   1  may change a result obtained by determining whether to allow an update of the state of the first neuron to a value which is indicative that the update is not allowed. 
     An example of the above state transition determination circuit  11   c   1  will be described in second and later embodiments. 
     The other Ising units  11   a   2  through  11   a N perform processes regarding second through Nth neurons respectively. This is the same with the Ising unit  11   a   1 . 
     For example, a calculation circuit  11   b   2  of the Ising unit  11   a   2  includes a register  11   b   21 , a local field update section  11   b   22 , and an energy change calculation section  11   b   23 . The register  11   b   21  stores N weighting coefficients W 21 , W 22 , . . . , and W 2N . On the basis of identification information ID of a neuron whose state is updated, the local field update section  11   b   22  selects a weighting coefficient indicative of the magnitude of an interaction between the neuron and the second neuron. Furthermore, the local field update section  11   b   22  updates a local field h 2  on the basis of the selected weighting coefficient and a state change direction DR of the neuron whose state is updated. The energy change calculation section  11   b   23  calculates energy changes ΔE 2+  and ΔE 2−  on the basis of expression (2). Furthermore, on the basis of the magnitude relationships among a thermal excitation energy and the energy changes ΔE 2+  and ΔE 2− , a state transition determination circuit  11   c   2  of the Ising unit  11   a   2  determines whether to allow updates of the state of the second neuron that cause the energy changes ΔE 2+  and ΔE 2− . In addition, the state transition determination circuit  11   c   2  outputs determination results obtained by determining whether to allow the updates. Moreover, the state transition determination circuit  11   c   2  limits an update by which the state of the second neuron exceeds an upper limit value or falls below a lower limit value. 
     A calculation circuit  11   b N of the Ising unit  11   a N includes a register  11   b N 1 , a local field update section  11   b N 2 , and an energy change calculation section  11   b N 3 . The register  11   b N 1  stores N weighting coefficients W N1 , W N2 , . . . , and W NN . On the basis of identification information ID of a neuron whose state is updated, the local field update section  11   b N 2  selects a weighting coefficient indicative of the magnitude of an interaction between the neuron and the Nth neuron. Furthermore, the local field update section  11   b N 2  updates a local field h N  on the basis of the selected weighting coefficient and a state change direction DR of the neuron whose state is updated. The energy change calculation section  11   b N 3  calculates energy changes ΔE N+  and ΔE N−  on the basis of expression (2). Furthermore, on the basis of the magnitude relationships among a thermal excitation energy and the energy changes ΔE N+  and ΔE N , a state transition determination circuit  11   c N of the Ising unit  11   a N determines whether to allow updates of the state of the Nth neuron that cause the energy changes ΔE N+  and ΔE N− . In addition, the state transition determination circuit  11   c N outputs determination results obtained by determining whether to allow the updates. Moreover, the state transition determination circuit  11   c N limits an update by which the state of the Nth neuron exceeds an upper limit value or falls below a lower limit value. 
     On the basis of determination results outputted by the Ising units  11   a   1  through  11   a N, the update neuron selection circuit  12  selects one neuron whose state is allowed to be updated and selects a state change direction DR. The update neuron selection circuit  12  outputs identification information ID of the selected neuron whose state is allowed to be updated and the state change direction DR. 
     On the basis of the state change direction DR, the state update circuit  13  changes (updates) the state of the neuron selected by the update neuron selection circuit  12  by 2 n  in the positive or negative direction. The state update circuit  13  has a storage section (such as a register) and holds states of the N neurons. 
     The controller  14  transmits information to and receives information from a control apparatus  15  such as a personal computer (PC). For example, the controller  14  receives from the control apparatus  15  weighting coefficients W ij  which represent the Ising model and sets the weighting coefficients W ij  in the Ising units  11   a   1  through  11   a N (stores the weighting coefficients W ij  in the registers  11   b   11  through  11   b N 1 ). In addition, the controller  14  may receive from the control apparatus  15  initial values of local fields h i  (bias coefficients b i , for example) and set them in the Ising units  11   a   1  through  11   a N. 
     Furthermore, the controller  14  receives annealing conditions (such as the maximum value and minimum value of the temperature parameter T and information regarding how to lower the value of the temperature parameter T) from the control apparatus  15  and sets the temperature parameter T in the Ising units  11   a   1  through  11   a N on the basis of the annealing conditions. The controller  14  gradually lowers the value of the temperature parameter T on the basis of the annealing conditions. In addition, the controller  14  receives the above limit information LMT from the control apparatus  15  and sets the limit information LMT including the upper limit value and lower limit value of the state of each neuron in the Ising units  11   a   1  through  11   a N. Moreover, the controller  14  transmits as a solution to the control apparatus  15  the state of each neuron held in the state update circuit  13 , for example, at the time of lowering the value of the temperature parameter T determined times (or at the time of the temperature parameter T reaching the minimum value). 
     The controller  14  is realized by an application specific electronic circuit such as an application specific integrated circuit (ASIC) or a field programmable gate array (FPGA). The controller  14  may be a processor such as a central processing unit (CPU) or a digital signal processor (DSP). In that case, the processor executes a program stored in a memory (not illustrated). By doing so, the above processes by the controller  14  are performed. The functions of the controller  14  may be included in the control apparatus  15 . 
     An example of the operation of the optimization apparatus  10  according to the first embodiment will now be described. 
       FIG.  2    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the first embodiment. 
     First the controller  14  sets in the Ising units  11   a   1  through  11   a N weighting coefficients W ij , initial values of local fields h i , initial values of the temperature parameter T, and the limit information LMT received from the control apparatus  15  (step S 1 ). 
     The local field update sections  11   b   12  through  11   b N 2  update the local fields h i  in the second and later update processes by performing the above process (step S 2 ). 
     Each of the energy change calculation section  11   b   13  through  11   b N 3  calculates two energy changes ΔE i+  and ΔE i−  on the basis of expression (2) (step S 3 ). 
     Each of the state transition determination circuits  11   c   1  through  11   c N performs the above process in order to determine whether to allow updates of the state of each neuron that cause the energy changes ΔE i+  and ΔE i−  (step S 4 ). Furthermore, each of the state transition determination circuits  11   c   1  through  11   c N performs the above process in step S 4  in order to limit an update by which the state of each neuron goes beyond a domain. 
     On the basis of determination results outputted by the Ising units  11   a   1  through  11   a N, the update neuron selection circuit  12  selects one neuron whose state is allowed to be updated and selects a state change direction DR (step S 5 ). 
     The state update circuit  13  updates the state of the neuron selected by the update neuron selection circuit  12  on the basis of the state change direction DR (step S 6 ). 
     The controller  14  determines whether or not the update process from step S 2  to step S 6  is repeated determined N 1  times (step S 7 ). If the update process from step S 2  to step S 6  is not repeated the determined N 1  times, then the update process from step S 2  to step S 6  is repeated. 
     If the update process from step S 2  to step S 6  is repeated the determined N 1  times, then the controller  14  determines whether or not the number of times the temperature parameter T is changed (number of times temperature is changed) has reached determined N 2  times (step S 8 ). 
     If the number of times temperature is changed has not reached the determined N 2  times, then the controller  14  changes the temperature parameter T (lowers temperature) (step S 9 ). The determined N 1  times, the determined N 2  times, and how to change the value of the temperature parameter T (how much the value of the temperature parameter T is decreased at a time, for example) are determined on the basis of annealing conditions. After step S 9  is performed, the process is repeated from step S 2 . 
     If the number of times temperature is changed has reached the determined N 2  times, then the controller  14  transmits (outputs) as a solution (calculation result) to the control apparatus  15  the state of each neuron held at that time in the state update circuit  13  (step S 10 ). 
     With the above optimization apparatus  10  according to the first embodiment an allowed change in the state of each neuron having three or more values is set to ±2 n  (n is an integer greater than or equal to 0). By doing so, the structure of circuits used for calculating an energy change of the Ising model is simplified and an increase in circuit scale is suppressed. Furthermore, the state of a neuron having three or more values is treated on a small circuit scale. This widens the scope of problems that the optimization apparatus  10  is able to solve. 
     The values of n may differ among different neurons. 
     Second Embodiment 
       FIG.  3    illustrates an example of an optimization apparatus according to a second embodiment. Components in  FIG.  3    which are the same as those of the optimization apparatus  10  according to the first embodiment illustrated in  FIG.  1    are marked with the same numerals. 
     With an optimization apparatus  20  according to a second embodiment a state transition determination circuit  21   b   1  of an Ising unit  21   a   1  includes ΔE change sections  21   b   11  and  21   b   12  and transition propriety determination sections  21   b   13  and  21   b   14 . 
     If a variable x 1  changes by +2 n  and exceeds an upper limit value, then the ΔE change section  21   b   11  changes an energy change ΔE 1+  to a determined positive value ΔE max . 
     If the variable x 1  changes by −2 n  and falls below a lower limit value, then the ΔE change section  21   b   12  changes an energy change ΔE 1−  to the determined positive value ΔE max . 
     A sufficiently large value is used as the positive value ΔE max  so that if the positive value ΔE max  is supplied to the transition propriety determination sections  21   b   13  and  21   b   14 , the probability that update of the variable x 1  will be allowed will become approximately zero. 
       FIG.  4    illustrates an example of a first ΔE change section.  FIG.  4    illustrates an example of the ΔE change section  21   b   11 . 
     The ΔE change section  21   b   11  includes a 2 n  adder  30 , a comparator circuit  31 , and a selector  32 . 
     The 2 n  adder  30  adds 2 n  to the current variable x l  supplied from a state update circuit  13 . 
     The comparator circuit  31  compares an upper limit value x 1max  of the variable x 1  included in limit information LMT and an addition result obtained by the 2 n  adder  30 . Furthermore, if the addition result is greater than the upper limit value x 1max , then the comparator circuit  31  outputs 1. In the other cases, the comparator circuit  31  outputs 0. 
     The selector  32  inputs the energy change ΔE 1+  and the positive value ΔE max  included in the limit information LMT. If an output of the comparator circuit  31  is 1, then the selector  32  outputs the positive value ΔE max . If an output of the comparator circuit  31  is 0, then the selector  32  outputs the energy change ΔE 1+ . 
       FIG.  5    illustrates an example of a second ΔE change section.  FIG.  5    illustrates an example of the ΔE change section  21   b   12 . 
     The ΔE change section  21   b   12  includes a 2 n  subtractor  33 , a comparator circuit  34 , and a selector  35 . 
     The 2 n  subtractor  33  subtracts 2 n  from the current variable x 1  supplied from the state update circuit  13 . 
     The comparator circuit  34  compares a lower limit value x 1min  of the variable x 1  included in the limit information LMT and a subtraction result obtained by the 2 n  subtractor  33 . Furthermore, if the subtraction result is smaller than the lower limit value x 1min , then the comparator circuit  34  outputs 1. In the other cases, the comparator circuit  34  outputs 0. 
     The selector  35  inputs the energy change ΔE 1=  and the determined positive value ΔE max  included in the limit information LMT. If an output of the comparator circuit  34  is 1, then the selector  35  outputs the positive value ΔE max . If an output of the comparator circuit  34  is 0, then the selector  35  outputs the energy change ΔE 1 . 
     On the basis of the magnitude relationship between the energy change ΔE 1−  or the positive value ΔE max  and a thermal excitation energy, the transition propriety determination section  21   b   13  illustrated in  FIG.  3    determines whether to allow update of the state of a first neuron that causes the energy change ΔE 1+ . 
     On the basis of the magnitude relationship between the energy change ΔE 1−  or the positive value ΔE max  and the thermal excitation energy, the transition propriety determination section  21   b   14  determines whether to allow an update of the state of the first neuron that causes the energy change ΔE 1− . 
       FIG.  6    illustrates an example of a transition propriety determination section. 
     The transition propriety determination section  21   b   13  includes a sign inverter  40 , an adder  41 , a random number generation circuit  42 , a selection rule applier  43 , a multiplier  44  and a comparator circuit  45 . 
     The sign inverter  40  multiplies the energy change ΔE 1+  or the positive value ΔE max  outputted by the ΔE change section  21   b   11  by −1 to perform a sign inversion. 
     The adder  41  adds an offset value off generated by an offset generation circuit  23  described later to an output value of the sign inverter  40 . 
     The random number generation circuit  42  generates a uniform random number r greater than or equal to 0 and smaller than or equal to 1. 
     The selection rule applier  43  outputs a value based on a selection rule (Metropolis method or the Gibbs method) adopted for performing simulated annealing. 
     If simulated annealing is performed, an allowance probability A(ΔE, T) of a state transition which causes an energy change ΔE is determined by the following expression (3). By doing so, it is proved that a state reaches an optimum solution at the limit at which time (number of repetition times) is infinite. 
     
       
         
           
             
               
                 
                   
                     
                       A 
                       ⁡ 
                       
                         ( 
                         
                           
                             Δ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             E 
                           
                           , 
                           T 
                         
                         ) 
                       
                     
                     = 
                     
                       f 
                       ⁡ 
                       
                         ( 
                         
                           
                             - 
                             Δ 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             E 
                             / 
                             T 
                           
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       f 
                       ⁡ 
                       
                         ( 
                         
                           
                             - 
                             Δ 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             E 
                             / 
                             T 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               min 
                               ⁡ 
                               
                                 [ 
                                 
                                   1 
                                   , 
                                   
                                     exp 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           - 
                                           Δ 
                                         
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           E 
                                           / 
                                           T 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ] 
                               
                             
                           
                           
                             
                               Metropolis 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               method 
                             
                           
                         
                         
                           
                             
                               1 
                               / 
                               
                                 [ 
                                 
                                   1 
                                   + 
                                   
                                     exp 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         Δ 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           E 
                                           / 
                                           T 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ] 
                               
                             
                           
                           
                             
                               Gibbs 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               method 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     In expression (3), T indicates the above temperature parameter T. 
     It is assumed that an allowance probability A(ΔE, T) given by expression (3) is used and that a steady state is reached after a sufficient number of repetition times. Then an occupation probability of each state follows Boltzmann distribution in a thermal equilibrium state in the thermodynamics. When temperature is gradually lowered from a high value, an occupation probability of a low energy state increases. Therefore, when temperature is sufficiently lowered, a low energy state will be obtained. This is very similar to a change in state which occurs at the time of annealing a material. Accordingly, this method is referred to as simulated annealing. At this time a state transition by which energy increases occurs stochastically. This corresponds to thermal excitation in the physics. 
     A circuit for outputting flag information (=1) which is indicative that a state transition which causes the energy change ΔE is allowed with the allowance probability A(ΔE, T) is realized by a comparator which outputs a value based on a result obtained by comparing f(−ΔE/T) in expression (3) and the uniform random number r. 
     However, the same function is also realized by making the following change. Even if the same monotone increasing function is made to operate on two numbers, the magnitude relationship between them does not change. Therefore, even if the same monotone increasing function is made to operate on two inputs of a comparator, its output does not change. For example, f −1 (−ΔE/T) which is an inverse function of f(−ΔE/T) is used as a monotone increasing function made to operate on f(−ΔE/T) and f −1 (r) which is obtained by substituting r for −ΔE/T of f −1 (−ΔE/T) is used as a monotone increasing function made to operate on the uniform random number r. In that case, a circuit which outputs 1 when −ΔE/T is greater than f −1 (r) may be used as a circuit having the same function as the above comparator has. Furthermore, the temperature parameter T is positive. Therefore, a circuit which outputs 1 when −ΔE is greater than T·f −1 (r) may be used as a circuit having the same function as the above comparator has. 
     The selection rule applier  43  illustrated in  FIG.  6    uses a conversion table for converting the uniform random number r inputted to a value of the above f −1 (r). By doing so, the selection rule applier  43  outputs a value of f −1 (r). If the Metropolis method is applied, then f 1 (r) is log(r). For example, the conversion table is stored in a memory such as a random access memory (RAM) or a flash memory. 
     The multiplier  44  outputs the product (T·f −1 (r)) of the temperature parameter T supplied from a controller  14  and f −1 (r). T·f −1 (r) corresponds to a thermal excitation energy. 
     The comparator circuit  45  compares an addition result by the adder  41  and T·f −1 (r). If the addition result is greater than T·f −1 (r), then the comparator circuit  45  outputs 1 as flag information FLG 1+ . If the addition result is smaller than T·f −1 (r), then the comparator circuit  45  outputs 0 as flag information FLG 1+ . 
     The circuit structure of the transition propriety determination section  21   b   14  is the same as that of the transition propriety determination section  21   b   13 . 
     Ising units  21   a   2  through  21   a N have the same structure as the Ising unit  21   a   1  has and perform the same processes on second through Nth neurons respectively. 
     For example, a state transition determination circuit  21   b N of the Ising unit  21   a N includes ΔE change sections  21   b N 1  and  21   b N 2  and transition propriety determination sections  21   b N 3  and  21   b N 4 . 
     If a variable x N  changes by +2 n  and exceeds an upper limit value, then the ΔE change section  21   b N 1  changes an energy change ΔE N−  to the determined positive value ΔE max . 
     If the variable x N  changes by −2 n  and falls below a lower limit value, then the ΔE change section  21   b N 2  changes an energy change ΔE N−  to the determined positive value ΔE max . 
     On the basis of the magnitude relationship between the energy change ΔE N−  or the positive value ΔE max  and a thermal excitation energy, the transition propriety determination section  21   b N 3  determines whether to allow update of the state of the Nth neuron that causes the energy change ΔE N− . 
     On the basis of the magnitude relationship between the energy change ΔE N−  or the positive value ΔE max  and the thermal excitation energy, the transition propriety determination section  21   b N 4  determines whether to allow update of the state of the Nth neuron that causes the energy change ΔE N− . 
     On the basis of determination results (flag information) outputted by the Ising units  21   a   1  through  21   a N, an update neuron selection circuit  22  selects one neuron whose state is allowed to be updated and selects a state change direction DR. This is the same with the update neuron selection circuit  12  illustrated in  FIG.  1   . Furthermore, the update neuron selection circuit  22  outputs identification information ID of the selected neuron whose state is allowed to be updated and the state change direction DR. With the optimization apparatus  20  according to the second embodiment the update neuron selection circuit  22  also outputs flag information FLG regarding the selected neuron whose state is allowed to be updated. 
     The optimization apparatus  20  according to the second embodiment includes the offset generation circuit which generates an offset value off. When the flag information FLG supplied from the update neuron selection circuit  22  indicates that a state transition is not allowed (that is to say, when a state transition does not occur), the offset generation circuit  23  increments the offset value off. On the other hand, when the flag information FLG supplied from the update neuron selection circuit  22  indicates that a state transition is allowed (that is to say, when a state transition occurs), the offset generation circuit  23  resets the offset value off to 0. When the offset value off becomes larger, a state transition is more apt to be allowed. If the current state is a local solution, then an escape from the local solution is promoted. 
     An example of the operation of the optimization apparatus  20  according to the second embodiment will now be described. 
       FIG.  7    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the second embodiment. 
     First the controller  14  sets in the Ising units  21   a   1  through  21   a N weighting coefficients W ij , initial values of local fields h i , initial values of the temperature parameter T, and the limit information LMT received from a control apparatus  15  (step S 20 ). With the optimization apparatus  20  according to the second embodiment the limit information LMT includes the positive value ΔE raax  and a domain (upper limit value and the lower limit value) of each variable x i . 
     Steps S 21  and S 22  are the same as steps S 2  and S 3 , respectively, illustrated in  FIG.  2   . 
     After step S 22  is performed, each of the state transition determination circuits  21   b   1  through  21   b N changes the energy change ΔE i+  or the energy change ΔE i−  for the variable x i  to the positive value ΔE max  if the variable x i  goes beyond the domain by an update (step S 23 ). 
     Furthermore, each of the state transition determination circuits  21   b   1  through  21   b N determines whether to allow updates of the state of each neuron that cause the energy changes ΔE i+  and ΔE i−  (step S 24 ). For example, step S 24  includes adding the above offset value off. 
     The subsequent steps S 25  through S 30  are the same as steps S 5  through S 10 , respectively, illustrated in  FIG.  2   . 
     The same effect that is obtained by the optimization apparatus  10  according to the first embodiment is achieved by the above optimization apparatus  20  according to the second embodiment. Furthermore, with the optimization apparatus  20 , the energy change ΔE i+  or the energy change ΔE i−  for the variable x i  is changed to the positive value ΔE max  if the variable x i  goes beyond the domain by the update. This suppresses an update by which the variable x i  goes beyond the domain. 
     Third Embodiment 
       FIG.  8    illustrates an example of an optimization apparatus according to a third embodiment. Components in  FIG.  8    which are the same as those of the optimization apparatus  10  or  20  illustrated in  FIG.  1  or  3    are marked with the same numerals. 
     With an optimization apparatus  50  according to a third embodiment a state transition determination circuit  51   b   1  of an Ising unit  51   a   1  includes transition propriety determination sections  51   b   11  and  51   b   12  and domain confirmation sections  51   b   13  and  51   b   14 . 
     On the basis of the magnitude relationship between an energy change ΔE 1+  and a thermal excitation energy, the transition propriety determination section  51   b   11  determines whether to allow an update of the state of a first neuron that causes the energy change ΔE 1+ . 
     On the basis of the magnitude relationship between an energy change ΔE 1−  and the thermal excitation energy, the transition propriety determination section  51   b   12  determines whether to allow an update of the state of the first neuron that causes the energy change ΔE 1− . 
     The circuit structure of the transition propriety determination sections  51   b   11  and  51   b   12  is the same as that of the transition propriety determination section  21   b   13  illustrated in  FIG.  6   . 
     If a variable x 1  changes by +2 n  and exceeds an upper limit value, then the domain confirmation section  51   b   13  sets flag information indicative of a result obtained by determining whether to allow the update to 0 (which is indicative that the update is not allowed). 
     If the variable x 1  changes by −2 n  and falls below a lower limit value, then the domain confirmation section  51   b   14  sets flag information indicative of a result obtained by determining whether to allow the update to 0. 
       FIG.  9    illustrates an example of a first domain confirmation section.  FIG.  9    illustrates an example of the domain confirmation section  51   b   13 . 
     The domain confirmation section  51   b   13  includes a 2 n  adder  60 , a comparator circuit  61 , and an AND (logical product) circuit  62 . 
     The 2 n  adder  60  adds 2 n  to the current variable x 1  supplied from a state update circuit  13 . 
     The comparator circuit  61  compares an upper limit value x 1max  of the variable x 1  included in limit information LMT and an addition result obtained by the 2 n  adder  60 . Furthermore, if the addition result is greater than the upper limit value x 1max , then the comparator circuit  61  outputs 0. In the other cases, the comparator circuit  61  outputs 1. 
     Flag information FLG 1a  outputted by the transition propriety determination section  51   b   11  is inputted to one input terminal of the AND circuit  62  and an output of the comparator circuit  61  is inputted to the other input terminal of the AND circuit  62 . Furthermore, if the output of the comparator circuit  61  is 1, then the AND circuit  62  outputs a value (0 or 1) of the flag information FLG 1a . If the output of the comparator circuit  61  is 0, then the AND circuit  62  outputs 0 regardless of the value of the flag information FLG 1a . 
       FIG.  10    illustrates an example of a second domain confirmation section.  FIG.  10    illustrates an example of the domain confirmation section  51   b   14 . 
     The domain confirmation section  51   b   14  includes a 2 n  subtractor  63 , a comparator circuit  64 , and an AND circuit  65 . 
     The 2 n  subtractor  63  subtracts 2 n  from the current variable x 1  supplied from the state update circuit  13 . 
     The comparator circuit  64  compares a lower limit value x 1min  of the variable x 1  included in the limit information LMT and a subtraction result obtained by the 2 n  subtractor  63 . Furthermore, if the subtraction result is smaller than the lower limit value x 1min , then the comparator circuit  64  outputs 0. In the other cases, the comparator circuit  64  outputs 1. 
     Flag information FLG 1b , outputted by the transition propriety determination section  51   b   12  is inputted to one input terminal of the AND circuit  65  and an output of the comparator circuit  64  is inputted to the other input terminal of the AND circuit  65 . Furthermore, if the output of the comparator circuit  64  is 1, then the AND circuit  65  outputs a value (0 or 1) of the flag information FLG 1b . If the output of the comparator circuit  64  is 0, then the AND circuit  65  outputs 0 regardless of the value of the flag information FLG 1b . 
     Ising units  51   a   2  through  51   a N have the same structure as the Ising unit  51   a   1  has and perform the same processes on second through Nth neurons respectively. 
     For example, a state transition determination circuit  51   b N of the Ising unit  51   a N includes transition propriety determination sections  51   b N 1  and  51   b N 2  and domain confirmation sections  51   b N 3  and  51   b N 4 . 
     On the basis of the magnitude relationship between an energy change ΔE N+  and a thermal excitation energy, the transition propriety determination section  51   b N 1  determines whether to allow an update of the state of the Nth neuron that causes the energy change ΔE N+ . 
     On the basis of the magnitude relationship between an energy change ΔE N−  and the thermal excitation energy, the transition propriety determination section  51   b N 2  determines whether to allow an update of the state of the Nth neuron that causes the energy change ΔE N− . 
     If a variable x N  changes by +2 n  and exceeds an upper limit value, then the domain confirmation section  51   b N 3  sets flag information indicative of a result obtained by determining whether to allow the update to 0. 
     If the variable x N  changes by −2 n  and falls below a lower limit value, then the domain confirmation section  51   b N 4  sets flag information indicative of a result obtained by determining whether to allow the update to 0. 
     An example of the operation of the optimization apparatus  50  according to the third embodiment will now be described. 
       FIG.  11    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the third embodiment. 
     First a controller  14  sets in the Ising units  51   a   1  through  51   a N weighting coefficients W ij , initial values of local fields h i , initial values of a temperature parameter T, and the limit information LMT received from a control apparatus  15  (step S 40 ). With the optimization apparatus  50  according to the third embodiment the limit information LMT includes a domain (upper limit value and the lower limit value) of each variable x i . 
     Steps S 41  and S 42  are the same as steps S 2  and S 3 , respectively, illustrated in  FIG.  2   . 
     After step S 42  is performed, each of the state transition determination circuits  51   b   1  through  51   b N determines whether to allow updates of the state of each neuron that cause the energy changes ΔE i+  and ΔE i−  (step S 43 ). For example, step S 43  includes adding the above offset value off. 
     After that, each of the state transition determination circuits  51   b   1  through  51   b N makes flag information regarding a variable x i  0 if the variable x i  goes beyond the domain by an update (step S 44 ). 
     The subsequent steps S 45  through S 50  are the same as steps S 5  through S 10 , respectively, illustrated in  FIG.  2   . 
     The same effect that is obtained by the optimization apparatus  10  according to the first embodiment is achieved by the above optimization apparatus  50  according to the third embodiment. Furthermore, with the optimization apparatus  50 , flag information regarding the variable x i  is made 0 if the variable x i  goes beyond the domain by an update. This reliably suppresses an update by which the variable x i  goes beyond the domain. 
     Fourth Embodiment 
       FIG.  12    illustrates an example of an optimization apparatus according to a fourth embodiment. Components in  FIG.  12    which are the same as those of the optimization apparatus  10 ,  20 , or  50  illustrated in  FIG.  1 ,  3   , or  8  are marked with the same numerals. 
     The optimization apparatus  70  according to the fourth embodiment includes shift amount holders  73   a   1  through  73   a N which hold shift amounts n 1  through nN to be supplied to calculation circuits  71   b   1  through  71   b N, respectively, and a state update circuit  72 . The shift amounts n 1  through nN are values which determine the widths of changes in the states of N neurons, respectively, and are greater than or equal to 0. For example, the width of a change in the state of a first neuron is expressed as ±2 n1  and the width of a change in the state of an Nth neuron is expressed as ±2 nN . The shift amounts n 1  through nN may be different from one another. 
     The shift amount holders  73   a   1  through  73   a N are, for example, registers or SRAMs. 
     The shift amounts n 1  through nN are supplied to local field update sections  71   b   11  through  71   b N 1  included in the calculation circuits  71   b   1  through  71   b N of Ising units  71   a   1  through  71   a N respectively. Furthermore, each of the local field update sections  71   b   11  through  71   b N 1  uses a shift amount for a neuron whose state is updated for updating a local field. 
       FIG.  13    illustrates an example of a portion of a local field update section in which a shift operation is performed.  FIG.  13    illustrates a portion of the local field update section  71   bi   1 , of the local field update sections  71   b   11  through  71   b N 1 , in which a local field for an ith neuron is updated. 
     The local field update section  71   bi   1  includes an anticoincidence circuit  80 , a selection circuit  81 , and a shift operation circuit  82 . 
     If identification information ID (=i) of the ith neuron and identification information ID (=j) of a neuron whose state is updated do not match, then the anticoincidence circuit  80  outputs 1. If they match, then the anticoincidence circuit  80  outputs 0. 
     For example, the anticoincidence circuit  80  compares the identification information ID of the ith neuron and the identification information ID of the jth neuron bit by bit. If all bits of the identification information ID of the ith neuron and all bits of the identification information ID of the jth neuron match, then the anticoincidence circuit  80  outputs 0. In the other cases, the anticoincidence circuit  80  outputs 1. 
       FIG.  13    illustrates an example of the anticoincidence circuit  80 . The anticoincidence circuit  80  includes k exclusive-OR (ExOR) circuits  80   a   1 ,  80   a   2 , . . . , and  80   ak  and a plurality of logical sum (OR) circuits (OR circuits  80   b   1  through  80   bm  and  80   c , for example). 
     The identification information ID of the ith neuron is made up of k bits and the identification information ID of the jth neuron is made up of k bits. Each of the ExOR circuits  80   a   1  through  80   ak  compares 1 bit of the identification information ID of the ith neuron and bit of the identification information ID of the jth neuron. If they match, then each of the ExOR circuits  80   a   1  through  80   ak  outputs 0. If they do not match, then each of the ExOR circuits  80   a   1  through  80   ak  outputs 1. For example, the ExOR circuit  80   a   1  compares the least significant bit (i 1 ) of the identification information ID of the ith neuron and the least significant bit (j 1 ) of the identification information ID of the jth neuron. If they match, then the ExOR circuit  80   a   1  outputs 0. If they do not match, then the ExOR circuit  80   a   1  outputs 1. The ExOR circuit  80   ak  compares the most significant bit (i k ) of the identification information ID of the ith neuron and the most significant bit (j k ) of the identification information ID of the jth neuron. If they match, then the ExOR circuit  80   ak  outputs 0. If they do not match, then the ExOR circuit  80   ak  outputs 1. 
     Each of the OR circuits  80   b   1  through  80   bm  receives two outputs among k outputs from the ExOR circuits  80   a   1  through  80   ak  and outputs the logical sum of the two outputs. For example, the OR circuit  80   b   1  receives the outputs of the ExOR circuits  80   a   1  and  80   a   2  and outputs the logical sum of them. 
     Outputs of the OR circuits  80   b   1  through  80   bm  are inputted by twos to a plurality of OR circuits (not illustrated) at the next stage. Furthermore, outputs of the plurality of OR circuits at that stage are inputted by twos to a plurality of OR circuits at the next stage. This process is repeated according to the value of k. In addition, an output of the OR circuit  80   c  at the last stage is an output of the anticoincidence circuit  80 . 
     If the output of the anticoincidence circuit  80  is 1, then the selection circuit  81  selects and outputs a weighting coefficient W ij . If the output of the anticoincidence circuit  80  is 0, then the selection circuit  81  selects and outputs 0. 
     If an output of the selection circuit  81  is 0, then the shift operation circuit  82  outputs 0. If an output of the selection circuit  81  is the weighting coefficient W ij , then the shift operation circuit  82  outputs a value obtained by left-shifting the weighting coefficient W ij  by nj bits (W ij *(1&lt;&lt;nj)=2 nj W ij ). A change portion of a local field h i  is obtained by multiplying 2 nj W ij  by 1 or −1 according to a state change direction DR. 
     In  FIG.  12   , one of the shift amounts n 1  through nN is supplied to each of energy change calculation sections  71   b   12  through  71   b N 2  included in the calculation circuits  71   b   1  through  71   b N of the Ising units  71   a   1  through  71   a N respectively. For example, the energy change calculation section  71   b   12  receives the shift amount n 1  and calculates ΔE 1+ =−2 n1 h 1  and ΔE 1− =2 n1 h 1  on the basis of expression (2). The energy change calculation section  71   b N 2  receives the shift amount nN and calculates ΔE N+ =−2 nN h N  and ΔE N− =2 nN h N  on the basis of expression (2). 
     State transition determination circuit  71   c   1  through  71   c N are almost the same as the state transition determination circuits  21   b   1  through  21   b N, respectively, included in the optimization apparatus  20  according to the second embodiment or the state transition determination circuits  51   b   1  through  51   b N, respectively, included in the optimization apparatus  50  according to the third embodiment. As stated above, however, with the ΔE change sections  21   b   11  through  21   b N 1  and  21   b   12  through  21   b N 2  or the domain confirmation sections  51   b   13  through  51   b N 3  and  51   b   14  through  51   b N 4  2 n  is added to or subtracted from the state of the current neuron (see  FIG.  4 ,  5 ,  9   , or  10 ). Therefore, one of the shift amounts n 1  through nN is supplied to each of the state transition determination circuit  71   c   1  through  71   c N as a shift amount n. 
     The shift amounts n 1  through nN are supplied to the state update circuit  72 . The state update circuit  72  selects one shift amount corresponding to identification information ID outputted by an update neuron selection circuit  22 . Furthermore, on the basis of the selected shift amount (hereinafter indicated by ns) and a state change direction DR, the state update circuit  72  changes the state of a neuron indicated by the identification information ID by 2 ns  in the positive or negative direction. 
     A controller  74  has the same function as the controller  14  has and sets the shift amounts n 1  through nN in the shift amount holders  73   a   1  through  73   a N respectively. When the state of a neuron is updated, the controller  74  may change the shift amounts n 1  through nN. By doing so, the speed of convergence to an optimum solution is controlled. For example, if the states of all neurons do not change even by performing an update process determined times (current state is a local solution), then the controller  74  increases the shift amounts n 1  through nN. This increases the absolute value of an energy change and promotes an escape from the local solution. As a result, the speed of convergence is accelerated. 
     An example of the operation of the optimization apparatus  70  according to the fourth embodiment will now be described. 
       FIG.  14    is a flow chart illustrative of the flow of an example of the operation of the optimization apparatus according to the fourth embodiment. 
     First the controller  74  sets in the Ising units  71   a   1  through  71   a N weighting coefficients W ij , initial values of local fields h i , initial values of a temperature parameter T, and the limit information LMT received from a control apparatus  15 . Furthermore, the controller  74  sets the shift amounts n 1  through nN received from the control apparatus  15  in the shift amount holders  73   a   1  through  73   a N respectively (step S 60 ). The subsequent steps S 61  through S 69  are the same as steps S 2  through S 10 , respectively, illustrated in  FIG.  2   . However, steps S 61  through S 69  differ from steps S 2  through S 10 , respectively, only in that the shift amounts n 1  through nN set are used. The controller  74  may change the magnitude of the shift amounts n 1  through nN, for example, after step S 68 . 
     The same effect that is obtained by the optimization apparatus  10  according to the first embodiment is achieved by the above optimization apparatus  70  according to the fourth embodiment. Furthermore, with the optimization apparatus  70  the controller  74  individually sets the shift amounts n 1  through nN for the N neurons. Therefore, the width of a change in the state of each neuron is variable. In addition, when the state of a neuron is updated, the controller  74  is able to change the shift amounts n 1  through nN. As a result, the speed of convergence to an optimum solution is controlled. 
     By the way, for example, a processor included in a control apparatus, such as a PC, may execute a control program. By doing so, the function of the controller  14  included in the above optimization apparatus  10  according to the first embodiment, the above optimization apparatus according to the second embodiment, or the above optimization apparatus  50  according to the third embodiment or the function of the controller  74  included in the above optimization apparatus  70  according to the fourth embodiment is realized. 
       FIG.  15    illustrates an example of the hardware of a control apparatus. 
     A control apparatus  90  includes a CPU  91 , a RAM  92 , a hard disk drive (HDD)  93 , an image signal processing unit  94 , an input signal processing unit  95 , a medium reader  96 , a communication interface  97 , and an interface  98 . These units are connected to a bus. 
     The CPU  91  is a processor including an operational circuit which executes an instruction of a program. The CPU  91  loads at least part of a program or data stored in the HDD  93  into the RAM  92  and executes it. The CPU  91  may include a plurality of processor cores. The control apparatus  90  may include a plurality of processors. Control of an optimization apparatus  98   a  may be exercised in parallel by the use of the plurality of processors or processor cores. 
     The RAM  92  is a volatile semiconductor memory which temporarily stores a program to be executed by the CPU  91  or data to be used by the CPU  91  for performing an operation. The control apparatus  90  may include a type of memory other than a RAM or include a plurality of memories. 
     The HDD  93  is a nonvolatile storage unit which stores programs for software, such as an operating system (OS), middleware, and application software, and data. For example, the programs include a control program which makes the control apparatus  90  perform the function of setting weighting coefficients, limit information LMT, and the like and controlling a temperature parameter T. The control apparatus  90  may include another type of storage unit, such as a flash memory or a solid state drive (SSD), and include a plurality of nonvolatile storage units. 
     The image signal processing unit  94  outputs an image (image indicative of the calculation result of an optimization problem, for example) to a display  94   a  connected to the control apparatus  90  in accordance with an instruction from the CPU  91 . A cathode ray tube (CRT) display, a liquid crystal display (LCD), a plasma display panel (PDP), an organic electro-luminescence (OEL) display, or the like is used as the display  94   a.    
     The input signal processing unit  95  acquires an input signal from an input device  95   a  connected to the control apparatus  90  and outputs it to the CPU  91 . A pointing device such as a mouse, a touch panel, a touch pad, or a track ball, a keyboard, a remote controller, a button switch, or the like is used as the input device  95   a . Two or more types of input devices may be connected to the control apparatus  90 . 
     The medium reader  96  is a reader which reads a program or data recorded on a record medium  96   a . A magnetic disk, an optical disk, a magneto-optical disk (MO), a semiconductor memory, or the like is used as the record medium  96   a . The magnetic disk may be a flexible disk (FD) or an HDD. The optical disk may be a compact disc (CD) or a digital versatile disc (DVD). 
     The medium reader  96  copies a program or data read from, for example, the record medium  96   a  to another record medium such as the RAM  92  or the HDD  93 . The program read is executed by, for example, the CPU  91 . The record medium  96   a  may be a portable record medium and be used for distributing a program or data. Furthermore, the record medium  96   a  and the HDD  93  may be referred to as computer readable record media. 
     The communication interface  97  is connected to a network  97   a  and communicates with other information processing apparatus via the network  97   a . The communication interface  97  may be a wired communication interface connected to a communication device, such as a switch, by a cable or a radio communication interface connected to a base station by a radio link. 
     The interface  98  communicates with the optimization apparatus  98   a . For example, the optimization apparatus  98   a  is the optimization apparatus  10  according to the first embodiment except the controller  14 , the optimization apparatus  20  according to the second embodiment except the controller  14 , the optimization apparatus  50  according to the third embodiment except the controller  14 , or the optimization apparatus  70  according to the fourth embodiment except the controller  74 . 
       FIG.  16    is a flow chart illustrative of the flow of an example of a method for controlling the optimization apparatus by the control apparatus. 
     The control apparatus  90  sets weighting coefficients W ij , initial values of local fields h i , initial values of a temperature parameter T, and limit information LMT in the optimization apparatus  98   a . Furthermore, if the optimization apparatus  98   a  includes the shift amount holders  73   a   1  through  73   a N illustrated in  FIG.  12   , then the control apparatus  90  sets the shift amounts n 1  through nN (step S 70 ). 
     After that, the control apparatus  90  receives, for example, a signal which the optimization apparatus  98   a  transmits each time it performs the above update process. The control apparatus  90  determines whether or not the update process is repeated determined N 1  times (step S 71 ). If the update process is not repeated the determined N 1  times, then step S 71  is repeated. 
     If the update process is repeated the determined N 1  times, then the control apparatus  90  determines whether or not the number of times the temperature parameter T is changed (number of times temperature is changed) has reached determined N 2  times (step S 72 ). 
     If the number of times temperature is changed has not reached the determined N 2  times, then the control apparatus  90  changes the temperature parameter T (lowers temperature) (step S 73 ). In step S 73 , the control apparatus  90  transmits to the optimization apparatus  98   a  a value of the temperature parameter T smaller than a value transmitted the last time. The determined N 1  times, the determined N 2  times, and how to change the value of the temperature parameter T (how much the value of the temperature parameter T is decreased at a time, for example) are determined on the basis of annealing conditions. After step S 73  is performed, the process is repeated from step S 71 . The control apparatus  90  may change the magnitude of the shift amounts n 1  through nN, for example, after step S 73 . 
     If the number of times temperature is changed has reached the determined N 2  times, then the control apparatus  90  acquires the state of each neuron (variable x i  (i=1 to N)) at that time as the calculation result of an optimization problem from, for example, the storage section in the state update circuit  13  illustrated in  FIG.  1    (step S 74 ). 
     After that, the control apparatus  90  displays the received calculation result on, for example, the display  94   a  illustrated in  FIG.  15    (step S 75 ) and ends the control of the optimization apparatus  98   a.    
     As stated above, the contents of the process performed by the above control apparatus  90  are realized by making a computer execute a program. 
     The program may be recorded on a computer readable record medium (record medium  96   a , for example). A magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory, or the like may be used as a computer readable record medium. The magnetic disk may be an FD or an HDD. The optical disk may be a CD, a CD-recordable(R)/rewritable(RW), a DVD, or a DVD-R/RW. The program may be recorded on a portable record medium and be distributed. In that case, the program may be copied from a portable record medium to another record medium (HDD  93 , for example) and be executed. 
     One aspect of the optimization apparatus, the optimization apparatus control method, and the optimization apparatus control program has been described on the basis of the embodiments. However, these embodiments are simple examples and are not limited to the above description. 
     According to one aspect, an increase in the circuit scale of an optimization apparatus which treats a variable having three or more values is suppressed. 
     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 various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.