Information processing apparatus, information processing method, and computer-readable recording medium storing program of searching for parameter

Abstract

An apparatus of searching for a parameter used in an energy function of an Ising model that corresponds to a problem, the apparatus being configured to obtain information that indicates the energy function; performing a first processing a plurality of times, the first processing including obtaining a first candidate value from a first range, the first range being a candidate value range of the parameter to be used for a search for a solution of the problem based on the energy function, and evaluating the first candidate value according to a result of the search in a case where the first candidate value is used as a value of the parameter; changing the candidate value range from the first range to a second range narrower than the first range; performing a second processing a plurality of times, the second processing including obtaining a second candidate value from the second range.

What is claimed is: 
     
         1 . An information processing apparatus of searching for a parameter, the information processing apparatus comprising:
 a memory configured to store information that indicates an energy function of an Ising model that corresponds to a problem; and   a processor configured to perform processing including:   obtaining the information stored in the memory;   performing a first processing a plurality of times, the first processing including,
 obtaining a first candidate value from a first range, the first range being a candidate value range of the parameter to be used for a search for a solution of the problem based on the energy function, and 
 evaluating the first candidate value according to a result of the search in a case where the first candidate value is used as a value of the parameter; 
   changing the candidate value range from the first range to a second range narrower than the first range;   performing a second processing a plurality of times, the second processing including
 obtaining a second candidate value from the second range, and 
 evaluating the second candidate value according to a result of the search in a case where the second candidate value is used as a value of the parameter; and 
   determining, based on at least any one of a first difference or an index, a timing at which the candidate value range is changed from the first range to the second range and a second difference between the first range and the second range, the first difference being a difference between a best evaluation value and another evaluation value, the best evaluation value being any one of a plurality of first evaluation values calculated by the performing of the first processing the plurality of times, the another evaluation value being an evaluation value obtained by the first processing performed before the first processing of the best evaluation value, the index indicating a nature of the problem according to the energy function.   
     
     
         2 . The information processing apparatus according to  claim 1 , wherein
 the determining of the timing is configured to delay the timing as the first difference increases,   the determining of the second difference is configured to decrease the second difference as the first difference increases.   
     
     
         3 . The information processing apparatus according to  claim 1 , wherein
 the determining of the timing is configured to advance, as compared with a case where the first difference is more than the threshold value, the timing in a case where the first difference is equal to or less than a threshold value, and   the determining of the second difference is configured to increase, as compared with a case where the first difference is more than the threshold value, the second difference in a case where the first difference is equal to or less than a threshold value.   
     
     
         4 . The information processing apparatus according to  claim 1 , wherein
 the index that indicates the nature of the problem indicates a difficulty level of the problem,   the determining of the timing is configured to delay the timing as the difficulty level increases, and   the determining of the second difference is configured to decrease the second difference as the difficulty level increases.   
     
     
         5 . The information processing apparatus according to  claim 1 , wherein
 the index that indicates the nature of the problem is an index that indicates at least any one of: the number of state variables in the energy function, a type of a constraint in the energy function, or the number of constraints in the energy function.   
     
     
         6 . The information processing apparatus according to  claim 5 , wherein
 the determining of the timing is configured to delay the timing as at least any one of the number of state variables or the number of constraints increases, and   the determining of the second difference is configured to decrease the second difference as at least any one of the number of state variables or the number of constraints increases.   
     
     
         7 . The information processing apparatus according to  claim 1 , wherein
 the changing of the candidate value is configured to set, as a center value of the second range, the first candidate value that corresponds to the best evaluation value among the first candidate values obtained from the first range.   
     
     
         8 . The information processing apparatus according to  claim 1 , the processing further including
 calculating the best evaluation value that corresponds to the first candidate value based on a best value of the energy function and a period of time taken to reach the best value, the best value being any one of values obtained by the search for a certain period of time in a case where the first candidate value is used.   
     
     
         9 . The information processing apparatus according to  claim 1 , the processing further including:
 determining, as a value of the parameter, the second candidate value that corresponds to a best evaluation value among a plurality of second evaluation values obtained for a plurality of the second candidate values obtained from the second range, and   obtaining a result of the search for a solution to the problem, by executing the search for a solution to the problem by using the determined value of the parameter, or by inputting the determined value of the parameter to a search processing circuit configured to perform the search to cause the search processing circuit to execute the search.   
     
     
         10 . The information processing apparatus according to  claim 1 , wherein
 there are a plurality of parameters to be used as the parameter,   the first processing is configured to
 obtain a first set of candidate values by obtaining, for each of the plurality of parameters, the candidate value from the first range, and 
 evaluate the first set of the candidate values according to a result of the search in a case where the first set of the candidate values is used, 
   the changing of the candidate value range is configured to
 change, for each candidate value in the first set of candidate values, the candidate value range from the first range to the second range, 
   the second processing is configured to
 obtain a second set of candidate values by obtaining, for each of the plurality of parameters, the candidate value from the second range, and 
 evaluate the second set of the candidate values according to a result of the search in a case where the second set of the candidate values is used, and 
   the determining is configured to
 determine the timing and the second difference based on at least any one of the first difference or the index, the first difference being a difference between a best evaluation and another evaluation value, the best value being any one of a plurality of evaluation values calculated by the performing of the first processing the plurality of times, the another evaluation value being an evaluation value obtained by the first processing performed before the first processing of the best evaluation value, the index indicating the nature of the problem according to the energy function. 
   
     
     
         11 . The information processing apparatus according to  claim 10 , wherein
 the search for a solution to the problem is executed by a simulated annealing method or a replica-exchange method, and   a plurality of the parameters include at least one of a maximum temperature value and a minimum temperature value to be used in the simulated annealing method or the replica-exchange method.   
     
     
         12 . An information processing method implemented by a computer of searching for a parameter, the method comprising:
 obtaining information that indicates an energy function of an Ising model that corresponds to a problem;   performing a first processing a plurality of times, the first processing including,
 obtaining a first candidate value from a first range, the first range being a candidate value range of a parameter to be used for a search for a solution of the problem based on the energy function, and 
 evaluating the first candidate value according to a result of the search in a case where the first candidate value is used as a value of the parameter; 
   changing the candidate value range from the first range to a second range narrower than the first range;   performing a second processing a plurality of times, the second processing including
 obtaining a second candidate value from the second range, and 
 evaluating the second candidate value according to a result of the search in a case where the second candidate value is used as a value of the parameter; and 
   determining, based on at least any one of a first difference or an index, a timing at which the candidate value range is changed from the first range to the second range and a second difference between the first range and the second range, the first difference being a difference between a best evaluation value and another evaluation value, the best evaluation value being any one of a plurality of first evaluation values calculated by the performing of the first processing the plurality of times, the another evaluation value being an evaluation value obtained by the first processing performed before the first processing of the best evaluation value, the index indicating a nature of the problem according to the energy function.   
     
     
         13 . A non-transitory computer-readable storage medium storing a program of searching for a parameter, the program causing a computer to perform processing comprising:
 obtaining information that indicates an energy function of an Ising model that corresponds to a problem;   performing a first processing a plurality of times, the first processing including
 obtaining a first candidate value from a first range, the first range being a candidate value range of a parameter to be used for a search for a solution of the problem based on the energy function, and 
 evaluating the first candidate value according to a result of the search in a case where the first candidate value is used as a value of the parameter; 
   changing the candidate value range from the first range to a second range narrower than the first range;   performing a second processing a plurality of times, the second processing including,
 obtaining a second candidate value from the second range, and 
 evaluating the second candidate value according to a result of the search in a case where the second candidate value is used as a value of the parameter; and 
   determining, based on at least any one of a first difference or an index, a timing at which the candidate value range is changed from the first range to the second range and a second difference between the first range and the second range, the first difference being a difference between a best evaluation value and another evaluation value, the best evaluation value being any one of a plurality of first evaluation values calculated by the performing of the first processing the plurality of times, the another evaluation value being an evaluation value obtained by the first processing performed before the first processing of the best evaluation value, the index indicating a nature of the problem according to the energy function.   
     
     
         14 . An information processing apparatus of searching for a parameter, the information processing apparatus comprising:
 a memory configured to store information that indicates an energy function of an Ising model that corresponds to a problem; and   a processing circuit configured to perform processing including:   obtaining the information stored in the memory; and   determining, based on an index that indicates a nature of the problem according to the energy function, a timing of changing a candidate value range from a first range to a second range and a difference between the first range and the second range, each of the first range and the second range being a range to be used in processing, the processing including
 performing first processing a plurality of times, the first processing including obtaining a first candidate value from the first range that is a candidate value range of a parameter to be used for a search for a solution of the problem based on the energy function and evaluating the first candidate value according to a result of the search in a case where the first candidate value is used as a value of the parameter, 
 performing second processing of changing the candidate value range from the first range to the second range narrower than the first range, and 
 performing third processing a plurality of times, the third processing including obtaining a second candidate value from the second range and evaluating the second candidate value according to a result of the search in a case where the second candidate value is used as a value of the parameter. 
   
     
     
         15 . An information processing method implemented by a computer of searching for a parameter, the method comprising:
 obtaining information that indicates an energy function of an Ising model that corresponds to a problem; and   determining, based on an index that indicates a nature of the problem according to the energy function, a timing of changing a candidate value range from a first range to a second range and a difference between the first range and the second range, each of the first range and the second range being a range to be used in processing, the processing including
 performing first processing a plurality of times, the first processing including obtaining a first candidate value from the first range that is a candidate value range of a parameter to be used for a search for a solution of the problem based on the energy function and evaluating the first candidate value according to a result of the search in a case where the first candidate value is used as a value of the parameter, 
 performing second processing of changing the candidate value range from the first range to the second range narrower than the first range, and 
 performing third processing a plurality of times, the third processing including obtaining a second candidate value from the second range and evaluating the second candidate value according to a result of the search in a case where the second candidate value is used as a value of the parameter. 
   
     
     
         16 . A non-transitory computer-readable storage medium storing a program of searching for a parameter, the program causing a computer to perform processing comprising:
 obtaining information that indicates an energy function of an Ising model that corresponds to a problem; and   determining, based on an index that indicates a nature of the problem according to the energy function, a timing of changing a candidate value range from a first range to a second range and a difference between the first range and the second range, each of the first range and the second range being a range to be used in processing, the processing including
 performing first processing a plurality of times, the first processing including obtaining a first candidate value from the first range that is a candidate value range of a parameter to be used for a search for a solution of the problem based on the energy function and evaluating the first candidate value according to a result of the search in a case where the first candidate value is used as a value of the parameter, 
 performing second processing of changing the candidate value range from the first range to the second range narrower than the first range, and 
 performing third processing a plurality of times, the third processing including obtaining a second candidate value from the second range and evaluating the second candidate value according to a result of the search in a case where the second candidate value is used as a value of the parameter.