Computer-readable recording medium storing optimization program, optimization method, and information processing apparatus

An optimization method comprising:

• acquiring, by a computer, information on an evaluation function obtained by converting a problem;
• determining values of a plurality of temperature parameters that are different from each other and used for solution processing of an optimal solution by a replica exchange method;
• setting each of values of the plurality of temperature parameters to any one of a plurality of replicas;
• and
• executing the solution processing by performing, for each of the plurality of replicas independently of each other, update processing of repeating update of any value of a plurality of state variables included in the evaluation function in accordance with a first transition probability that is obtained based on an amount of change in a value of the evaluation function due to a change in any value of the plurality of state variables and any value of the plurality of temperature parameters, and in which a change in a value of the evaluation function relative to a change in a value of temperature parameter is gentler than that in a case of using a second transition probability based on the Boltzmann distribution, and repeating exchange processing of exchanging, between the plurality of replicas, any values of the plurality of temperature parameters set for each of the plurality of replicas or values of the plurality of state variables in each of the plurality of replicas, in accordance with an exchange probability that satisfies an invariant distribution condition of probability distribution obtained by the first transition probability.

An information processing apparatus comprising:

• a memory;
• and
• a processor coupled to the memory and configured to:
• acquire information on an evaluation function obtained by converting a problem;
• determine values of a plurality of temperature parameters that are different from each other and used for solution processing of an optimal solution by a replica exchange method;
• set each of values of the plurality of temperature parameters to any one of a plurality of replicas;
• and
• execute the solution processing by performing, for each of the plurality of replicas independently of each other, update processing of repeating update of any value of a plurality of state variables included in the evaluation function in accordance with a first transition probability that is obtained based on an amount of change in a value of the evaluation function due to a change in any value of the plurality of state variables and any value of the plurality of temperature parameters, and in which a change in a value of the evaluation function relative to a change in a value of temperature parameter is gentler than that in a case of using a second transition probability based on the Boltzmann distribution, and repeating exchange processing of exchanging, between the plurality of replicas, any values of the plurality of temperature parameters set for each of the plurality of replicas or values of the plurality of state variables in each of the plurality of replicas, in accordance with an exchange probability that satisfies an invariant distribution condition of probability distribution obtained by the first transition probability.