COMPUTER-READABLE RECORDING MEDIUM STORING OPTIMIZATION PROGRAM, OPTIMIZATION METHOD, AND OPTIMIZATION APPARATUS

Abstract

An optimization apparatus of: performing a search for an optimal solution through iteration of processing configured to determine, by using a difference between a first energy value of an evaluation function in a first state and a second energy value of the evaluation function in a second state, whether to accept a state transition from the first state to the second state, and perform the state transition; and in the performing of the search for the state, storing the difference between the first and second energy values, and the respective values of the evaluation function in the second state, in a case where negation of the state transition is consecutively iterated a specific number of times, selecting one state from among the stored second states, based on the differences, and making the state transition from the first state to the selected one state.

Claims

1. A non-transitory computer-readable recording medium storing an optimization program for causing a computer to execute optimization processing comprising: performing a search for a state that serves as a solution through iteration of processing, the processing being configured to determine, by using a difference between a first energy value of an evaluation function based on respective values of a plurality of variables that indicate a first state and a second energy value of the evaluation function based on respective values of the plurality of variables that indicate a second state in which a value of at least one variable among the plurality of variables is changed, whether to accept a state transition from the first state to the second state, and perform the state transition based on a result of the determining; and in the performing of the search for the state, storing the difference between the first energy value in the first state and the second energy value in the second state, and the respective values of the plurality of variables that indicate the second state, in a case where negation of the state transition is consecutively iterated a specific number of times, selecting one state from among the stored second states, based on the differences, and making the state transition from the first state to the selected one state.

2. The non-transitory computer-readable recording medium according to claim 1, wherein the selecting is configured to select the one state from among a top specific number of the second states obtained in a case where the respective differences are sorted in ascending order.

3. The non-transitory computer-readable recording medium according to claim 1, wherein the storing is configured to store, as a candidate state, the difference and the respective values of the plurality of variables that indicate the second state in a case where the difference is smaller than a specific value, and the selecting is configured to select the one state from among the stored candidate states.

4. The non-transitory computer-readable recording medium according to claim 3, wherein the storing is configured to update one of a stored specific number of the candidate states with a new candidate state.

5. The non-transitory computer-readable recording medium according to claim 1, the optimization processing further comprising: calculating a third energy value in the one state to which the state transition is made; and in a case where the calculated third energy value satisfies a specific condition, setting the one state to which the state transition is made, as the state that serves as the solution.

6. A computer-implemented method of an optimization processing, the method comprising: performing a search for a state that serves as a solution through iteration of processing, the processing being configured to determine, by using a difference between a first energy value of an evaluation function based on respective values of a plurality of variables that indicate a first state and a second energy value of the evaluation function based on respective values of the plurality of variables that indicate a second state in which a value of at least one variable among the plurality of variables is changed, whether to accept a state transition from the first state to the second state, and perform the state transition based on a result of the determining; and in the performing of the search for the state, storing the difference between the first energy value in the first state and the second energy value in the second state, and the respective values of the plurality of variables that indicate the second state, in a case where negation of the state transition is consecutively iterated a specific number of times, selecting one state from among the stored second states, based on the differences, and making the state transition from the first state to the selected one state.

7. An optimization apparatus comprising: a memory; and a processor coupled to the memory, the processor being configured to perform optimization processing including: performing a search for a state that serves as a solution through iteration of processing, the processing being configured to determine, by using a difference between a first energy value of an evaluation function based on respective values of a plurality of variables that indicate a first state and a second energy value of the evaluation function based on respective values of the plurality of variables that indicate a second state in which a value of at least one variable among the plurality of variables is changed, whether to accept a state transition from the first state to the second state, and perform the state transition based on a result of the determining; and in the performing of the search for the state, storing the difference between the first energy value in the first state and the second energy value in the second state, and the respective values of the plurality of variables that indicate the second state, in a case where negation of the state transition is consecutively iterated a specific number of times, selecting one state from among the stored second states, based on the differences, and making the state transition from the first state to the selected one state.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0024] FIG. 1 is a block diagram illustrating an example of a functional configuration of an optimization apparatus according to an embodiment;

[0025] FIG. 2 is a flowchart illustrating an example of an operation of the optimization apparatus according to the embodiment;

[0026] FIG. 3 is a flowchart illustrating an example of setting processing;

[0027] FIG. 4 is an explanatory diagram for describing selection of a state that serves as a transition destination;

[0028] FIG. 5 is an explanatory diagram for describing selection of a state that serves as the transition destination;

[0029] FIG. 6 is an explanatory diagram for describing selection of a state that serves as the transition destination;

[0030] FIG. 7 is an explanatory diagram illustrating an example of a configuration of a computer;

[0031] FIG. 8 is a diagram for describing MCMC;

[0032] FIG. 9 is a diagram for describing simulated annealing; and

[0033] FIG. 10 is a flowchart for describing simulated annealing processing of the related art.

DESCRIPTION OF EMBODIMENTS

[0034] However, in the related art described above, when the state transition is consecutively rejected in the determination as to whether to accept the state transition at the time of the search for the optimum solution, the state change does not occur, so that the time in which the search stays at the local solution increases. Consequently, the processing time for obtaining the optimum solution increases. For example, in a case of local optimization or low thermal noise, a state change does not occur and the search stays at a local solution for a long time. This causes an issue in that the efficiency for the search for the optimum solution decreases.

[0035] In one aspect, an object is to provide a computer-readable recording medium storing an optimization program, an optimization method, and an optimization apparatus capable of efficiently performing a search for a solution.

[0036] An optimization program, an optimization method, and an optimization apparatus according to embodiments will be described below with reference to the drawings. In the embodiments, components having the same functions are denoted by the same reference sign, and redundant description thereof is omitted. The optimization program, the optimization method, and the optimization apparatus described in the embodiments below are merely illustrative and do not intend to limit the embodiments. The individual embodiments below may be appropriately combined with each other within a scope without any contradiction.

[0037] FIG. 1 is a block diagram illustrating an example of a functional configuration of an optimization apparatus according to an embodiment. As illustrated in FIG. 1, an optimization apparatus 1 includes a communication unit 10, an input unit 20, a display unit 30, a storage unit 40, and a control unit 50. As the optimization apparatus 1, for example, a personal computer (PC) or the like may be used.

[0038] The communication unit 10 receives various kinds of data from an external apparatus via a network. The communication unit 10 is an example of a communication device. For example, the communication unit 10 may receive, from the external apparatus, information that is part or entirety of initial setting information 41 (described later).

[0039] The input unit 20 is an input device that inputs various kinds of information to the control unit 50 of the optimization apparatus 1. The input unit 20 corresponds to a keyboard, a mouse, a touch panel, or the like. For example, the input unit 20 receives the information that is the part or entirety of the initial setting information 41 (described later) through an input operation performed by a user.

[0040] The display unit 30 is a display device that displays information output from the control unit 50. For example, the display unit 30 displays a processing result or the like obtained in the optimization apparatus 1.

[0041] The storage unit 40 stores the initial setting information 41, state information 42, and transition candidate information 43. The storage unit 40 corresponds to a semiconductor memory element such as a random-access memory (RAM) or a flash memory, or a storage device such as a hard disk drive (HDD).

[0042] The initial setting information 41 is information on initial settings used when an optimum solution of an Ising-type energy function corresponding to an optimization problem is obtained through simulated annealing processing. For example, the initial setting information 41 includes information (such as constants W.sub.ij and b.sub.i determined in accordance with a problem to be solved) of a model equation of the Ising-type energy function (evaluation function) corresponding to the optimization problem.

[0043] The initial setting information 41 also includes an initial temperature of thermal noise, the number of iterations (N), a threshold (M) of the number of consecutive rejections, an initial value (j=0) of a counter (j) for counting the number of consecutive rejections, and the number of candidate states (K) that are used in the simulated annealing processing. The number of consecutive rejections indicates the number of consecutive iterations in which a state transition is not accepted but is rejected in the simulated annealing processing. The initial setting information 41 includes a threshold (TH) for determining a candidate state that serves a candidate for a transition destination.

[0044] The state information 42 is information indicating a state (value of each variable (spin)) or the like of the Ising-type energy function used when the optimum solution of the energy function is obtained through the simulated annealing processing. For example, the state information 42 includes information on (value of each variable (spin) of) each of a predetermined number of (for example, M) states (S.sub.i) that are set as candidates for the transition destination in the simulated annealing processing, and an energy increase (ΔE.sub.i) from an energy before the transition to an energy in each state.

[0045] The transition candidate information 43 is information on candidate states that are set as candidates for the next transition destination when rejection of the state transition is iterated without being accepted in the simulated annealing processing. For example, the transition candidate information 43 includes the value of each variable (spin) indicating the candidate state and the energy increase from the energy before the transition to the energy in that candidate state.

[0046] The control unit 50 includes an initial state setting unit 51, an energy calculation unit 52, a state holding unit 53, and a calculation control unit 54. The control unit 50 is implemented by a central processing unit (CPU), a graphics processing unit (GPU), or a hard wired logic such as application-specific integrated circuit (ASIC) or a field-programmable gate array (FPGA).

[0047] The initial state setting unit 51 is a processing unit that sets an initial state used when the optimum solution of the Ising-type energy function corresponding to the optimization problem is obtained through the simulated annealing processing.

[0048] For example, the initial state setting unit 51 receives information on the initial state via the communication unit 10 or the input unit 20. For example, the information on the initial state includes the information on the model equation of the Ising-type energy function (evaluation function) corresponding to the optimization problem, the initial temperature of thermal noise, the number of iterations (N), the threshold (M) of the number of consecutive rejections, and the initial value of the counter (j) for counting the number of consecutive rejections. The information on the initial state also includes the number of candidate states (K) that are set as candidates for the transition destination, and the threshold (TH) for determining the candidate state. The initial state setting unit 51 stores the received information on the initial state in the storage unit 40 as the initial setting information 41.

[0049] The energy calculation unit 52 is a processing unit that performs a calculation related to an energy value of the Ising-type energy function (evaluation function) in the simulated annealing processing. For example, based on Equation (1) described above, the energy calculation unit 52 calculates the energy value related to the energy E(x) of the entire system. Based on Equation (2) described above, the energy calculation unit 52 calculates the energy increase (ΔE.sub.i) from an energy in the current state to an energy in a state (S.sub.i) in which a value of at least one variable among the variables (bits) is changed.

[0050] The state holding unit 53 is a processing unit that stores, in the storage unit 40, information on each state in which a value of each variable (each bit) is changed in the simulated annealing processing. For example, the state holding unit 53 stores, in the storage unit 40 as the state information 42, the energy increase (ΔE.sub.i) from the energy in the current state to the energy in the state (S.sub.i) in which a value of at least one variable among the variables (bits) is changed, which is calculated by the energy calculation unit 52 in the simulated annealing processing, and the value of each variable indicating that state (S.sub.i).

[0051] If the energy difference (ΔE.sub.i) is smaller than a specific value (threshold (TH)), the state holding unit 53 stores the energy difference and the value of each variable indicating the corresponding state (candidate state) in the storage unit 40 as the transition candidate information 43.

[0052] The calculation control unit 54 is a processing unit that controls calculation processing (simulated annealing processing) for obtaining the optimum solution. For example, in the simulated annealing processing, the calculation control unit 54 determines whether to accept the state transition, based on the difference (ΔE.sub.i) between the energy value of the current state (value of each variable) and the energy value of the state (S.sub.i) changed from the current state by bit inversion, calculated by the energy calculation unit 52. By iterating this processing, the calculation control unit 54 searches for a state that serves as the solution.

[0053] In a case where negation of the state transition is consecutively iterated a specific number of times when the search for the solution is iteratively performed in such a manner, the calculation control unit 54 selects one state based on the energy difference from among the states included in the stored state information 42. Then, the calculation control unit 54 causes the state to transition from the current state to the selected one state. Thus, the optimization apparatus 1 may avoid a circumstance in which a state change does not occur and the search stays at a local solution for a long time because of consecutive negation of the state transition.

[0054] FIG. 2 is a flowchart illustrating an example of an operation of the optimization apparatus 1 according to the embodiment. As illustrated in FIG. 2, in response to the start of processing, the initial state setting unit 51 initializes a condition used when the optimum solution of the Ising-type energy function corresponding to the optimization problem is obtained through the simulated annealing processing (S1).

[0055] For example, the initial state setting unit 51 receives the information on the initial state via the communication unit 10 or the input unit 20, and sets the initial state of the simulated annealing processing. The setting of the initial state includes, in addition to initial setting of the Ising-type energy function and each variable (bit) in that function, setting of the initial temperature of thermal noise, setting of the number of iterations (N), setting of the threshold (M) of the number of consecutive rejections, and initialization (j=0) of the counter (j) for counting the number of consecutive rejections. The setting of the initial state also includes setting of the number of candidate states (K) that serve as candidates for the transition destination, setting of the threshold (TH) for determining the candidate state, and so on.

[0056] Then, the calculation control unit 54 sets a counter (i) of the number of iterations to i=1 (S2), and starts the simulated annealing processing (S3 to S14).

[0057] For example, the energy calculation unit 52 randomly or sequentially selects a variable (bit) from the current state (S.sub.min), and calculates the energy increase (ΔE.sub.i) caused when the value of the selected variable is changed (when the bit is inverted) in accordance with Equation (2) (S3). In a case where the iteration counter is i=1, the current state (S.sub.min) is the state of the initial setting made in the S1.

[0058] Then, the state holding unit 53 causes the storage unit 40 to hold, as the state information 42, the energy increase (ΔE.sub.i) calculated by the energy calculation unit 52 and the state (S.sub.i) in which the value of the variable is changed (S4).

[0059] Then, based on the energy increase (ΔE.sub.i) calculated by the energy calculation unit 52, the calculation control unit 54 determines whether to accept, as the transition destination, the state (S.sub.i) in which the value of the variable is changed (S5).

[0060] For example, the calculation control unit 54 calculates an acceptance probability (A(ΔE.sub.i)) of the state transition, based on the energy increase (ΔE.sub.i), and determines acceptance or rejection in accordance with whether that probability is equal to or greater than a predetermined value. The calculation control unit 54 may determine acceptance or rejection by using a difference between a uniform random number u[i] and the acceptance probability (A(ΔE.sub.i)) of the state transition.

[0061] If the state (S.sub.i) is accepted as the transition destination (S5: Yes), the calculation control unit 54 updates the current state (S.sub.min) and the energy increase (ΔE.sub.min) corresponding to that state (S6). The processing then proceeds to S10. For example, the calculation control unit 54 replaces ΔE.sub.min with the energy increase (ΔE.sub.i) calculated by the energy calculation unit 52. The calculation control unit 54 also sets the state (S.sub.i) in which the value of the variable is changed, as the new current state (S.sub.min).

[0062] If the state (S.sub.i) is not accepted as the transition destination (S5: No), the calculation control unit 54 increments the counter (j) for counting the number of consecutive rejections (j=j+1) (S7).

[0063] Then, the calculation control unit 54 determines whether the counter (j) for counting the number of consecutive rejections is equal to the threshold (M) of the number of consecutive rejections (j=M?) (S8). If the counter (j) for counting the number of consecutive rejections is not equal to the threshold (M) of the number of consecutive rejections (S8: No), the calculation control unit 54 causes the processing to proceed to S13.

[0064] If the counter (j) for counting the number of consecutive rejections is equal to the threshold (M) for the number of consecutive rejections (S8: Yes), the calculation control unit 54 performs setting processing for setting the state (S.sub.min) that serves as the transition destination and the energy increase (ΔE.sub.min) corresponding to that state (S9). The processing then proceeds to S10.

[0065] FIG. 3 is a flowchart illustrating an example of the setting processing. As illustrated in FIG. 3, in response to the start of the setting processing (for setting ΔE.sub.min and S.sub.min), the calculation control unit 54 sorts the states (S.sub.i) included in the state information 42 in ascending order of the corresponding energy increases (ΔE.sub.i) (S20). For example, in a case where acceptance of M state transitions has not occurred even once, the states corresponding to the respective energy increases ΔE.sub.(i-M) to ΔE.sub.i in the state information 42 are sorted in ascending order.

[0066] FIG. 4 is an explanatory diagram for describing selection of a state that serves as the transition destination. FIG. 4 illustrates the state information 42 in a case where acceptance of M state transitions has not occurred even once. As illustrated in FIG. 4, the state information 42 includes M energy increases ΔE.sub.i and states S.sub.i corresponding those energy increases ΔE.sub.i. The calculation control unit 54 sorts this state information 42 in ascending order based on the energy increases (ΔE.sub.i) (see the right side in FIG. 4).

[0067] Then, the calculation control unit 54 selects, as candidate states, K states respectively corresponding to top K energy increases ΔE after the sorting (S21). Then, the calculation control unit 54 randomly selects one of the K selected candidate states and sets the selected candidate state as a new state (S.sub.min) that serves as the transition destination (S22). Then, the calculation control unit 54 sets the energy increase ΔE corresponding to the selected state as ΔE.sub.min (S23).

[0068] For example, in the example illustrated in FIG. 4, the calculation control unit 54 selects the top seven states from among the M states, and sets one state (S.sub.1) among those top seven states as the new state (S.sub.min) that serves as the transition destination. The calculation control unit 54 sets an energy increase ΔE′.sub.i corresponding to the selected state (S.sub.1) as ΔE.sub.min.

[0069] Referring back to FIG. 2, after the processing of S6 or S9, the calculation control unit 54 resets the counter (j) for counting the number of consecutive rejections (j=0) (S10). Then, based on Equation (1) described above, the energy calculation unit 52 calculates the current energy E.sub.min of the entire system by using ΔE.sub.min (S11).

[0070] Then, the calculation control unit 54 determines whether the energy E.sub.min of the entire system calculated by the energy calculation unit 52 satisfies a predetermined condition (E.sub.min<known energy) (S12). The known energy is a known energy value that is the minimum in the evaluation function (energy function), and is set together with the energy function at the time of initial setting or the like, for example.

[0071] If the condition is satisfied (S12: Yes), the calculation control unit 54 sets the current state (S.sub.i) obtained through the simulated annealing processing (S3 to S14), as the state that serves as the solution. The processing then ends.

[0072] If the condition is not satisfied (S12: No), the calculation control unit 54 determines whether the counter (i) of the number of iterations is equal to the number of iterations (N) set as the initial condition (i=N?) (S13). If the counter (i) is equal to the number of iterations (N) (S13: Yes), the calculation control unit 54 sets the current state (S.sub.i) as the state that serves as the solution. The processing then ends.

[0073] If the counter (i) is not equal to the number of iterations (N) (S13: No), the calculation control unit 54 increments the counter (i) for counting the number of iterations (i=i+1) (S14). The processing then returns to S3.

[0074] In the setting processing for setting the state (S.sub.min) that serves as the transition destination and the energy increase (ΔE.sub.min) corresponding to that state in S9, the calculation control unit 54 may select and set one state from among the candidate states included in the transition candidate information 43.

[0075] For example, in the S4, the state holding unit 53 stores each energy difference and the value of each variable indicating the corresponding state (candidate state) in the case where the energy difference (ΔE.sub.i) is smaller than the specific value (threshold (TH)), in the storage unit 40 as the transition candidate information 43. The calculation control unit 54 randomly selects one of the candidate states included in this transition candidate information 43 and sets the selected candidate state as the new state (S.sub.min) that serves as the transition destination (S22). Then, the calculation control unit 54 sets the energy increase ΔE corresponding to the selected state as ΔE.sub.min (S23).

[0076] FIG. 5 is an explanatory diagram for describing selection of a state that serves as the transition destination. On the left side in FIG. 5, the state information 42 in a case where acceptance of M state transitions has not occurred even once is illustrated. As illustrated in FIG. 5, when the threshold (TH) is set to 10, states (S.sub.1, S.sub.2, S.sub.5, and S.sub.6 in the illustrated example) in which the energy increase ΔE.sub.i is less than 10 are held in the transition candidate information 43 as the candidate states. The calculation control unit 54 randomly selects one state (S.sub.6 in the illustrated example) from among these candidate states (S.sub.1, S.sub.2, S.sub.5, and S.sub.6), and sets the selected state as the new state (S.sub.min) that serves as the transition destination.

[0077] In S4, the state holding unit 53 may store information on a specific number of candidate states in the storage unit 40 as the transition candidate information 43. For example, in a case where three candidate states are held as the transition candidate information 43, the state holding unit 53 stores the energy difference and the value of each variable indicating the corresponding state (candidate state) in the case where the energy difference is smaller than the specific value (threshold (TH)) up to the third candidate state, in the storage unit 40 as the transition candidate information 43. Then, in a case where three candidate states are held, the state holding unit 53 updates one of the three candidate states with the latest information (the energy difference and the value of each variable indicating that state (candidate state)). For example, the state holding unit 53 updates the oldest information among the three candidate states, with the latest information.

[0078] FIG. 6 is an explanatory diagram for describing selection of a state that serves as the transition destination. As illustrated in FIG. 6, the state holding unit 53 stores information on X (three in the illustrated example) candidate states (S.sub.1, S.sub.2, and S.sub.5, and the corresponding energy increases ΔE′.sub.i thereof) in the storage unit 40 as the transition candidate information 43. The calculation control unit 54 randomly selects one state (S.sub.2 in the illustrated example) from among these candidate states (S.sub.1, S.sub.2, and S.sub.5) and sets the selected state as the new state (S.sub.min) that serves as the transition destination.

[0079] As described above, the optimization apparatus 1 searches for a state that serves as a solution through iteration of processing in which, based on a difference (ΔE.sub.i) between an energy value of an evaluation function based on values of respective variables that indicate a current state and an energy value of the evaluation function based on values of the variables that indicate a state (S.sub.i) in which a value of at least one variable among the variables is changed, whether to accept a state transition is determined and the state transition is made. In this search, the optimization apparatus 1 stores, as the state information 42, the difference (ΔE.sub.i) between the energy in the current state and the energy in the changed state and the values of the respective variables that indicate the changed state (S.sub.i). The optimization apparatus 1 selects, based on the energy difference, one state from among the states included in the stored state information 42 in a case where negation of the state transition is consecutively iterated a specific number of times. Then, the optimization apparatus 1 makes the state transition from the current state to the selected one state.

[0080] Thus, the optimization apparatus 1 may avoid a circumstance in which, when a search for a state that serves as the solution is performed, a state change does not occur and the search stays at a local solution for a long time. Because this leads to a reduction in processing time for obtaining the optimum solution, the search for the solution may be performed efficiently.

[0081] The optimization apparatus 1 selects the one state from a top specific number of the states obtained in a case where the respective energy differences (ΔE.sub.i) are sorted in ascending order. For the state (S.sub.i) changed from the current state, as the energy difference (ΔE.sub.i) becomes smaller, the acceptance probability of the state transition becomes higher. Thus, it may be said that the state is appropriate as the transition destination. Thus, the optimization apparatus 1 may select a state that is more appropriate as the transition destination by sorting the states in ascending order of the energy differences (ΔE.sub.i) and selecting one state from among the top specific number of states.

[0082] The optimization apparatus 1 stores, as the transition candidate information 43, the energy difference (ΔE.sub.i) and values of the respective variables that indicate the corresponding state (candidate state) in a case where the energy difference is smaller than a specific value (threshold (TH)). The optimization apparatus 1 selects one state from among the candidate states included in stored transition candidate information 43. Thus, the optimization apparatus 1 may select one state from among states that are narrowed down in advance and of which the energy difference (ΔE.sub.i) is smaller than the specific value.

[0083] The optimization apparatus 1 updates one of the specific number of candidate states in the stored transition candidate information 43, with a new candidate state. Thus, the optimization apparatus 1 may avoid an increase in memory usage by making the number of candidate states in the transition candidate information 43 not exceed the specific number.

[0084] The optimization apparatus 1 calculates an energy value in the state to which the state transition is made. The optimization apparatus 1 sets the state to which the state transition is made, as the state that serves as the solution in a case where the calculated energy value satisfies a specific condition. Thus, the optimization apparatus 1 may obtain, as the solution, the state of which the energy value of the evaluation function satisfies the specific condition. For example, in a case where a maximum or minimum energy value is known for the energy value of the evaluation function, the optimization apparatus 1 may obtain, as the solution, a state having that energy value.

[0085] Note that each component of each apparatus illustrated in the drawings is not necessarily configured physically as illustrated in the drawings. For example, specific forms of distribution and integration in each apparatus are not limited to those illustrated in the drawings. The entirety or part of the apparatus may be configured by being functionally or physically distributed or integrated in arbitrary units in accordance with various loads, usage situations, and the like.

[0086] All or arbitrary some of various processing functions of the initial state setting unit 51, the energy calculation unit 52, the state holding unit 53, and the calculation control unit 54 carried out in the control unit 50 of the optimization apparatus 1 may be executed with a CPU (or a microcomputer such as a micro-processor unit (MPU) or a micro-controller unit (MCU)). Needless to say, all of or arbitrary some of the various processing functions may be executed with a program analyzed and executed by the CPU (or a microcomputer such as an MPU or an MCU) or with hardware of wired logic. The various processing functions carried out in the optimization apparatus 1 may be executed in such a manner that a plurality of computers cooperate with each other via cloud computing.

[0087] The various kinds of processing described in the embodiment described above may be implemented by execution of a program prepared in advance by a computer. Accordingly, an example of a (hardware) configuration of the computer that executes the program having substantially the same functions as those of the embodiment described above will be described below. FIG. 7 is an explanatory diagram for describing an example of the configuration of the computer.

[0088] As illustrated in FIG. 7, a computer 200 includes a CPU 201 that executes various kinds of arithmetic processing, an input device 202 that receives an input of data from a user, and a display 203. The computer 200 also includes a communication device 204 that receives data from an external apparatus, and an interface device 205 that is coupled to various apparatuses. The computer 200 includes a RAM 206 that temporarily stores various kinds of information, and a hard disk device 207. Each of the CPU 201 to the hard disk device 207 is coupled to a bus 208.

[0089] The hard disk device 207 includes an initial state setting program 207a, an energy calculation program 207b, a state holding program 207c, and a calculation control program 207d. The CPU 201 reads the initial state setting program 207a, the energy calculation program 207b, the state holding program 207c, and the calculation control program 207d and loads the initial state setting program 207a, the energy calculation program 207b, the state holding program 207c, and the calculation control program 207d to the RAM 206.

[0090] The initial state setting program 207a functions as an initial state setting process 206a. The energy calculation program 207b functions as an energy calculation process 206b. The state holding program 207c functions as a state holding process 206c. The calculation control program 207d functions as a calculation control process 206d.

[0091] Processing of the initial state setting process 206a corresponds to the processing of the initial state setting unit 51. Processing of the energy calculation process 206b corresponds to the processing of the energy calculation unit 52. Processing of the state holding process 206c corresponds to the processing of the state holding unit 53. Processing of the calculation control process 206d corresponds to the processing of the calculation control unit 54.

[0092] Each program among the initial state setting program 207a, the energy calculation program 207b, the state holding program 207c, and the calculation control program 207d is not necessarily stored in the hard disk device 207 initially. For example, each program may be stored on a “portable physical medium” such as a flexible disk (FD), a compact disc read-only memory (CD-ROM), a digital versatile disc (DVD), a magneto-optical disk, or an integrated circuit (IC) card to be inserted into the computer 200. The computer 200 may then read and execute each program. Alternatively, each program may be stored in an apparatus coupled to a public network, the Internet, a LAN, or the like, and the computer 200 may read each program from the apparatus and execute the program.

[0093] In relation to the embodiment above, the following appendices are further disclosed.

[0094] All examples and conditional language provided herein are intended for the pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.