An optimization apparatus comprising: a plurality of annealing circuits to which respective states and respective, different temperatures are assigned, and which are configured to calculate respective evaluation function values responsive to the respective states, each of the plurality of annealing circuits causing a transition from a current state assigned thereto to a next state with a probability responsive to a temperature assigned thereto and a difference in evaluation function values between the current state and the next state; an exchange circuit configured to exchange the temperatures or the states between the plurality of annealing circuits with predetermined probabilities based on the temperatures and the evaluation function values, the annealing circuits being arranged in descending order of thermodynamic betas, a probability of exchange between an n-th annealing circuit and n+1-th annealing circuit being min[1, exp{(β n -β n+1)(E n -E n+1)}], β n and E n respectively being a thermodynamic beta and an evaluation function value of the n-th annealing circuits β n+1 and E n+1 respectively being a thermodynamic beta and an evaluation function value of the n+1-th annealing circuits, and min[1, x] assuming a value of 1 or a value of x, whichever is smaller; and a temperature adjustment circuit configured to change temperatures of the plurality of annealing circuits, such that, for the n-th annealing circuit, no adjustment is made for β n when either (aveE n-1 -aveE n) or (aveE n -aveE n+1)is positive, β n is brought closer to β n-1 when | (β n-1 -β n)(aveE n-1 -aveE n)| > |(β n -β n+1)(aveE n -aveE n+1)|, and β n is brought closer to β n+1 when |(β n-1 -β n)(aveE n-1 -aveE n)| < |(β n -β n+1) (aveE n -aveE n+1)|, β n-1 and E n-1 respectively being a thermodynamic beta and an evaluation function value of the n-1-th annealing circuits, aveE n-1, aveE n, and aveE n+1 respectively being averages of evaluation function values of the n-1-th, n-th, and n+1-th annealing circuits, respectively, over a plurality of state transitions. a plurality of annealing circuits to which respective states and respective, different temperatures are assigned, and which are configured to calculate respective evaluation function values responsive to the respective states, each of the plurality of annealing circuits causing a transition from a current state assigned thereto to a next state with a probability responsive to a temperature assigned thereto and a difference in evaluation function values between the current state and the next state; an exchange circuit configured to exchange the temperatures or the states between the plurality of annealing circuits with predetermined probabilities based on the temperatures and the evaluation function values, the annealing circuits being arranged in descending order of thermodynamic betas, a probability of exchange between an n-th annealing circuit and n+1-th annealing circuit being min[1, exp{(β n -β n+1)(E n -E n+1)}], β n and E n respectively being a thermodynamic beta and an evaluation function value of the n-th annealing circuits β n+1 and E n+1 respectively being a thermodynamic beta and an evaluation function value of the n+1-th annealing circuits, and min[1, x] assuming a value of 1 or a value of x, whichever is smaller; and a temperature adjustment circuit configured to change temperatures of the plurality of annealing circuits, such that, for the n-th annealing circuit, no adjustment is made for β n when either (aveE n-1 -aveE n) or (aveE n -aveE n+1)is positive, β n is brought closer to β n-1 when | (β n-1 -β n)(aveE n-1 -aveE n)| > |(β n -β n+1)(aveE n -aveE n+1)|, and β n is brought closer to β n+1 when |(β n-1 -β n)(aveE n-1 -aveE n)| < |(β n -β n+1) (aveE n -aveE n+1)|, β n-1 and E n-1 respectively being a thermodynamic beta and an evaluation function value of the n-1-th annealing circuits, aveE n-1, aveE n, and aveE n+1 respectively being averages of evaluation function values of the n-1-th, n-th, and n+1-th annealing circuits, respectively, over a plurality of state transitions.