JP2022165027A - Optimization program, optimization method and optimization device - Google Patents

Abstract

An object of the present invention is to reduce the amount of permutation energy computation.
An optimization device (100) selects one permutation number of a permutation of a LOP (Linear Ordering Problem) matrix, moves the selected permutation number forward or backward, A first difference value between the energy of the first state and the energy of the second state of the permutation after being moved is calculated. The optimization device 100 stores the first difference value in the storage unit. The optimization device 100 selects one permutation number of the permutation, moves the selected permutation number forward or backward, and calculates the energy of the second state of the permutation before the movement and the energy of the third state of the permutation after the movement. When calculating the second difference value with the energy of the state, the first difference value is reused to calculate the second difference value.
[Selection drawing] Fig. 1

Description

The present invention relates to optimization programs and the like.

Combinatorial optimization problems are used in fields such as manufacturing, finance, and logistics. A combinatorial optimization problem is an optimization problem whose solution has combinatorial structures such as ordering and assignments.

For example, there is a linear ordering problem (LOP) as an application target for combinatorial optimization problems. The LOP is a matter of ranking all the candidates to suit the will of as many voters as possible given multiple factors, eg the ranking of multiple candidates. LOP also finds a permutation for rearranging the square matrix corresponding to the order of the candidates so that the sum of the elements of the upper triangular matrix is maximized. In LOP, for dimensionality n of the problem, n! The higher the dimension, the more difficult it is to solve, because there are a number of possible combinations.

LOP will be described under the following conditions 1-3.
(Condition 1): There are n candidates.
(Condition 2): The elements of the matrix (voting matrix) specify the number of people who voted for each of the candidate pairs.
(Condition 3): Vote for all pair candidates.

The objective function is shown in Equation (1), and the permutation π is shown in Equation (2). Also, it is assumed that the constraint condition is "arrange the rows and columns of the matrix in the same permutation".

A vote number matrix A is shown in Equation (3). The elements (components) “a _ij ” of vote count matrix A indicate the number of people who voted that candidate i is better than candidate j.

A permutation (order of candidates) can be represented by a plurality of binary values (bits) and can be represented by a matrix X. In the matrix X, each row and column of elements sum to all ones. Matrix X is a binary representation of the desired permutation and is used for bit update and inversion. For example, for the initial permutation 1234 (the ordering of Candidate 1, Candidate 2, Candidate 3, and Candidate 4), the matrix X is as shown in Equation (4). For permutation 3421, matrix X is as shown in equation (5).

FIG. 12 is a diagram for explaining rearrangement of LOPs. As shown in FIG. 12, if permutation 1234 is permuted into permutation 3421, then ^t XAX is computed. In the matrix ^t XAX, the rows and columns are arranged in 3421 order. X shown in FIG. 12 is the matrix X corresponding to equation (5) above.

FIG. 13 is a diagram for explaining LOP energy. The energy of the LOP is the sum of the elements of the upper triangular matrix (the sum of the elements contained in region 10). For example, the energy E of the matrix ^t XAX shown in FIG. 13 is given by Equation (6).

Energy E is used when placing candidates 1, 2, 3, 4 in descending order of votes. A larger energy E means that a candidate with a larger number of votes is located in the front. For example, when the energy of the permutation 3421 is higher than the energy of the permutation 1234, the candidates with the higher number of votes are positioned ahead of the candidate arrangement order 3421 of the candidate arrangement order 1234. ing.

For example, Markov Chain Monte Carlo methods (MCMC) are known as conventional techniques for searching for the minimum value (or maximum value) of the energy E. FIG. 14 is a diagram for explaining MCMC. The vertical axis in FIG. 14 corresponds to the energy value, and the horizontal axis corresponds to a certain state.

In MCMC, the energy change amount ΔE when moving from the current state to the neighboring state is calculated, and if the condition is satisfied, the state is shifted to the next state. ΔE is calculated by subtracting the energy E′ after the transition from the energy E before the transition. In MCMC, searching is performed by stochastically inverting states (bits). Also, by adding thermal noise, it is possible to avoid staying at a local optimum.

A conventional technique relating to LOP will be described. In this prior art, Steps 1-4 are executed.

"Step 1" performed by the conventional technique will be described. In the prior art, permutation number j (j=1, 2, . . . n−1) is inserted at insertion position i (i=j+1) for an n×n matrix, and energy is calculated. (Pj, i) indicates that the permutation number j is inserted at the insertion position i.

From the original permutation 1234, the prior art generates the following permutations.
(P1, 2) → permutation 2134
(P2, 3) → permutation 1324
(P3, 4) → permutation 1243

"Step 2" performed by the conventional technique will be described. In the prior art, the permutation number j (j=1, 2, . , . . . m) and calculate the energy for the generated permutation.

For example, among the permutations in Step 1, if permutation 1324 has the largest energy, the following permutations are generated.
(P1, 2) → permutation 3124
(P1, 3) → permutation 3214
(P1, 4) → permutation 3241
(P2, 1) → permutation 3124
(P2, 3) → permutation 1234
(P2, 4) → permutation 1243
(P3, 1) → permutation 2134
(P3, 2) → permutation 1234
(P3, 4) → permutation 1342

"Step 3" performed by the conventional technique will be described. In the prior art, the permutation that maximizes the energy calculated in Step 2 is obtained.

"Step 4" executed by the conventional technique will be described. In the prior art, Steps 1-3 are repeatedly executed until the optimum solution is found.

Here, a conventional energy calculation method will be described. FIG. 15 is a diagram for explaining a conventional energy calculation method.

The energy E of the original permutation 1234 is the sum of the elements in region 10 and is given by equation (7).

When the generated permutation is the permutation 2134, the energy E1 is calculated by Equation ( ₈ ). That is, instead of calculating the sum of the elements of the upper triangular matrix of the matrix _A ', the energy E1 is calculated based on the already calculated energy E of the permutation 1234 and matrix elements a21 and a12.

When the generated permutation is the permutation 3214, the energy E2 is calculated by Equation ( ₈ ). That is, instead of calculating the sum of the elements of the upper triangular matrix of the matrix _A '', the energy E2 is calculated based _on the energy E1, elements a21, a12, a21, and a31 of the permutation 2134 already calculated.

Manuel Laguna, "Intensification and diversification with elite tabu search solutions for the linear ordering problem," Computers & Operations Research 26 (1999) 1217-1230.

However, the conventional technique described above has a problem that the amount of calculation of the energy of the generated permutation is large.

For example, when the difference between the permutation number j and the insertion position i increases in the target matrix, the number of additions and subtractions increases and the amount of calculation increases. In addition, in the conventional technology, only the energy of the generated permutation is used to determine whether or not to update. Therefore, if you get stuck in a local solution, it is difficult to escape, it takes time to reach the optimum solution, and the amount of calculation increases.

In one aspect, an object of the present invention is to provide an optimization program, an optimization method, and an optimization device capable of reducing the amount of permutation energy calculations.

The first option is to have the computer perform the following processing. The computer selects one permutation number of the permutation of the LOP (Linear Ordering Problem) matrix, moves the selected permutation number forward or backward, and moves the energy of the first state of the permutation before moving A first difference value from the energy of the second state of the permutation after the permutation is calculated. The computer stores the first difference value in a storage device. The computer selects one permutation number of the permutation, moves the selected permutation number forward or backward, and the energy of the second state of the permutation before the movement and the energy of the third state of the permutation after the movement When calculating the second difference value from , the first difference value is reused to calculate the second difference value.

The amount of permutation energy computation can be reduced.

FIG. 1 is a functional block diagram showing the configuration of the optimization device according to this embodiment. FIG. 2 is a diagram illustrating an example of the data structure of a calculation table according to the embodiment; FIG. 3 is a diagram (1) for explaining the processing of the calculation unit according to the embodiment. FIG. 4 is a diagram (2) for explaining the processing of the calculation unit according to the embodiment. FIG. 5 is a diagram (3) for explaining the processing of the calculation unit according to the embodiment. FIG. 6 is a diagram (4) for explaining the processing of the calculation unit according to the embodiment. FIG. 7 is a flow chart showing the processing procedure of the optimization device according to this embodiment. FIG. 8 is a flowchart showing a processing procedure of forward insertion processing. FIG. 9 is a flowchart showing a processing procedure of backward insertion processing. FIG. 10 is a diagram for explaining other processing of the optimization device. FIG. 11 is a diagram showing an example of the hardware configuration of a computer that implements functions similar to those of the optimization device. FIG. 12 is a diagram for explaining rearrangement of LOPs. FIG. 13 is a diagram for explaining LOP energy. FIG. 14 is a diagram for explaining MCMC. FIG. 15 is a diagram for explaining a conventional energy calculation method.

Embodiments of the optimization program, optimization method, and optimization apparatus disclosed in the present application will be described in detail below with reference to the drawings. In addition, this invention is not limited by this Example.

FIG. 1 is a functional block diagram showing the configuration of the optimization device according to the first embodiment. As shown in FIG. 1 , this optimization device 100 has a communication section 110 , an input section 120 , a display section 130 , a storage section 140 and a control section 150 .

Communication unit 110 receives various data from an external device via a network. Communication unit 110 is an example of a communication device. For example, the communication unit 110 may receive vote matrix information 141, which will be described later, from an external device.

The input unit 120 is an input device that inputs various kinds of information to the control unit 150 of the optimization device 100 . The input unit 120 corresponds to a keyboard, mouse, touch panel, or the like.

The display unit 130 is a display device that displays information output from the control unit 150 . For example, the display unit 130 displays information on the optimal permutation solution.

The storage unit 140 has vote matrix information 141 , difference value information 142 and a calculation table 143 . The storage unit 140 corresponds to semiconductor memory devices such as RAM (Random Access Memory) and flash memory, and storage devices such as HDD (Hard Disk Drive).

The vote matrix information 141 is information of the vote matrix A having a _ij as elements (components) of the matrix. For example, let i=1 to n and j=1 to n (square matrix). The element “a _ij ” is set to the number of people who voted that candidate i is better than candidate j. The vote count matrix A is shown by equation (3).

The difference value information 142 indicates the difference value between the energy of the state of the permutation before the movement and the energy of the state of the permutation after the movement when the permutation number of the selected permutation is moved forward or backward. This is the information shown. As will be described later, the difference value of the difference value information 142 is updated by the new difference value calculated by the calculator 152 .

The calculation table 143 is a table that defines the relationship between the number of forward or backward shifts of the permutation number of the permutation of the n×n matrix and the difference value. For example, when the permutation number 3 of the original permutation 1234 is moved forward by one, the permutation becomes the permutation 1324, and the number of movements is "1". When the permutation number 3 of the original permutation 1234 is moved forward by two, the permutation becomes the permutation 3124, and the number of moves is "2".

When the permutation number 1 of the original permutation 1234 is moved backward by one, the permutation becomes the permutation 2134, and the number of moves is "1". When the permutation number 1 of the original permutation 1234 is moved backward by two, the permutation becomes the permutation 2314, and the number of movements is "2".

FIG. 2 is a diagram illustrating an example of the data structure of a calculation table according to the first embodiment; As shown in FIG. 2, the calculation table 143 has a front table 143a and a rear table 143b. Note that the original permutation 123, . . . i .

The forward table 143a associates the number of forward movements with the calculation of ΔE. The forward movement count indicates how many permutations of the permutation number i are selected and the permutation number i is moved forward. If the order number i is moved forward by one, the number of items moved forward is "1". ΔE is the difference value between the energy of the state of the permutation before movement and the energy of the state of the permutation after movement.

The backward table 143b associates the number of backward movements with the calculation of ΔE. The number of backward shifts indicates how many times the permutation number i of the permutation is selected and the permutation number i is moved backward. When the sequence number i is moved backward by one, the backward movement number becomes "1". ΔE is a difference value between the energy of the state of the permutation before movement and the energy of the state of the permutation after movement.

Returning to the description of FIG. The control unit 150 has an acquisition unit 151 and a calculation unit 152 . The control unit 150 is implemented by hardwired logic such as a CPU (Central Processing Unit), a GPU (Graphics Processing Unit), an ASIC (Application Specific Integrated Circuit), and an FPGA (Field Programmable Gate Array).

The obtaining unit 151 obtains the vote matrix information 141 from an external device or the like via a network. Acquisition unit 151 registers vote matrix information 141 in storage unit 140 . The acquisition unit 151 may acquire the vote matrix information 141 via the input unit 120 .

The calculation unit 152 selects one permutation number of the permutation of the vote matrix A, moves the selected permutation number forward or backward, and calculates the energy in the state before the movement and the state after the movement. Calculate the difference value with the energy of When calculating the difference value, the calculator 152 uses the previous difference value recorded in the difference value information 142 according to the calculation of ΔE defined in the calculation table 143 . The calculator 152 updates the difference value of the difference value information 142 with the newly calculated difference value.

3 to 6 are diagrams for explaining the processing of the calculation unit according to this embodiment. FIG. 3 will be described. Let the original permutation be permutation 1234 . The energy E of the original permutation 1234 is the sum of the upper triangular matrices of matrix A and is calculated by equation (7). The calculation unit 152 calculates the energy E of the original permutation based on Equation (7).

In FIG. 3 , the permutation number “3” of the original permutation 1234 is moved forward by one to become permutation 1324 . Let the matrix of the permutation ₁₃₂₄ be the matrix A1 shown in FIG. The energy E ₁ of permutation 1324 is the sum of the upper triangular matrices of matrix A ₁ and is given by equation (10). Here, the difference value _ΔE1 between the energy E and the energy E1 is given by equation ( ₁₁ ).

That is, the calculation unit 152 calculates the difference value ΔE ₁ between the energy E and the energy E ₁ using the elements a ₂₃ and a ₃₂ of the matrix A ₁ as shown in Equation (11). Note that the calculation unit 152 calculates the energy _E1 by subtracting the difference value _ΔE1 from the energy E. The calculator 152 sets the difference value ΔE ₁ in the difference value information 142 .

FIG. 4 will be described. In FIG. 4 , the permutation number “3” of the original permutation 1234 is moved forward by two to become a permutation 3214 . Let the matrix of the permutation 3214 be the matrix A2 shown in _FIG . The energy E ₂ of permutation 3214 is the sum of the upper triangular matrices of matrix A ₂ and is given by equation (12). Here, the difference value _ΔE2 between the energy E and the energy E2 is given by equation ₍ 13).

It should be noted that the calculation unit 152 can calculate the difference value _ΔE2 by the equation (14) when the difference value _ΔE1 has already been calculated as described in FIG. That is, as shown in Equation (14), the calculation unit 152 uses the difference value ΔE ₁ (ΔE of reuse) and the values of the elements a ₁₃ and a ₃₁ of the matrix A ₂ to calculate the energy E and the energy E ₂ and the difference value ΔE ₂ is calculated.

The calculation unit 152 identifies the elements a ₁₃ and a ₃₁ of the matrix A ₂ for calculating the difference value ΔE ₂ based on the forward table 143a described with reference to FIG. For example, Equation (14) corresponds to the calculation of ΔE for a forward movement number of "2" of the front table 142a.

_The calculation unit 152 calculates the energy E2 by subtracting the difference value _ΔE2 from the energy E. The calculator 152 updates the difference value information 142 with the difference value _ΔE2 .

FIG. 5 will be described. In FIG. 5 , the permutation number “1” of the original permutation 1234 is moved backward by one to become permutation 2134 . Let the matrix of the permutation ₂₁₃₄ be the matrix A3 shown in FIG. The energy E3 of permutation 2134 is the sum of the upper triangular _matrices of matrix A3 and is given by equation ₍ 15). Here _, the difference value ΔE3 between energy E and energy E3 is given by equation ₍ 16).

That is _, the calculation unit 152 calculates the difference value ΔE3 between the energy E and the energy E3 using the elements _a12 and _a21 of the matrix A3 _, as shown in Equation ₍ 16). Note that the calculation unit 152 calculates the energy _E3 by subtracting the difference value _ΔE3 from the energy E. The calculator 152 sets the difference value ΔE ₃ in the difference value information 142 .

FIG. 6 will be described. In FIG. 6 , the permutation number “1” of the original permutation 1234 is moved backward by two to become a permutation 2314 . Let the matrix of the permutation ₂₃₁₄ be the matrix A4 shown in FIG. The energy E ₄ of permutation 2314 is the sum of the upper triangular matrices of matrix A ₄ and is given by equation (17). Here, the difference value _ΔE4 between the energy E and the energy E4 is given by equation ₍ 18).

It should be noted that the calculation unit 152 can calculate the difference value ΔE ₄ according to equation (19) when the difference value ΔE ₃ has already been calculated as described with reference to FIG. 5 . That is, the calculation unit 152 calculates the difference value ΔE ₄ between the energy E and the energy E ₄ using the difference value ΔE ₃ and the elements a ₁₃ and a ₃₁ of the matrix A ₄ as shown in equation (19). do.

The calculation unit 152 identifies the elements a ₁₃ and a ₃₁ of the matrix A ₄ for calculating the difference value ΔE ₄ based on the backward table 143b described with reference to FIG. For example, equation (19) corresponds to the calculation of ΔE for a rearward movement number “2” of the rear table 142b.

The calculation unit 152 calculates the energy _E4 by subtracting the difference value _ΔE4 from the energy E. The calculator 152 updates the difference value information 142 with the difference value _ΔE4 .

As described above, the calculation unit 152 selects one permutation number of the permutation, moves the selected permutation number forward or backward, and calculates the energy of the state before the movement and the energy of the state after the movement. Calculate the difference value of In addition, the calculation unit 152 holds the maximum value of energy in the process of calculating each energy.

The calculation unit 152 repeats the above process until the maximum value of energy does not change even if the energy is calculated a plurality of times. The calculation unit 152 takes the permutation with the maximum energy as the optimum solution. The calculation unit 152 outputs information on the optimum solution to the display unit 130 for display. Alternatively, the calculation unit 152 may notify the external device of information on the optimum solution. For example, if the energy E ₄ shown in FIG.

Next, an example of the processing procedure of the optimization device 100 according to the first embodiment will be explained. FIG. 7 is a flow chart showing the processing procedure of the optimization device according to this embodiment. As shown in FIG. 7, the calculation unit 152 of the optimization device 100 sets states (initial values of permutations) (step S101). The calculation unit 152 sets the permutation number i to 1 (step S102).

When the value set to the permutation number i is 1 (step S103, Yes), the calculation unit 152 proceeds to step S106. On the other hand, when the value set for the permutation number i is not 1 (step S103, No), the calculation unit 152 proceeds to step S104.

The calculation unit 152 executes forward insertion processing (step S104). If the value set for the permutation number i matches the number of dimensions N (step S105, Yes), the calculation unit 152 proceeds to step S101. On the other hand, when the value set for the permutation number i does not match the number of dimensions N (step S105, No), the calculation unit 152 proceeds to step S106.

The calculation unit 152 executes backward insertion processing (step S106). The calculation unit 152 updates the permutation number i by adding 1 to the permutation number i (step S107), and proceeds to step S102.

Next, an example of forward insertion processing shown in step 104 of FIG. 7 will be described. FIG. 8 is a flowchart showing a processing procedure of forward insertion processing. As shown in FIG. 8, the calculator 152 sets 1 to the front insertion position j (step S201). The calculation unit 152 selects matrix elements a _ij and a _ji (step S202).

The calculation unit 152 calculates ΔE _j using the stored ΔE _(i−1) (step S203). In step S203, the calculator 152 calculates ΔE shown in the forward table 143a. The calculation unit 152 stores ΔE _j in the storage unit 140 (step S204).

The calculation unit 152 determines whether to execute MCMC bit inversion (step S205). For example, if ΔE _j is positive, the calculation unit 152 determines to execute MCMC bit inversion (step S205, Yes), and proceeds to step S206. On the other hand, when ΔE _j is 0 or less, the calculation unit 152 determines not to execute the MCMC bit inversion (step S205, No), and proceeds to step S210.

The calculator 152 performs MCMC bit inversion to update the permutation (step S206). The calculator 152 calculates the energy E (step S207). In step S207, the calculation unit 152 calculates energy E by subtracting ΔE from the energy of the original matrix set in step S101.

The calculation unit 152 determines whether the energy E is greater than E_MAX (the maximum value of the energy E so far) (step S208). If the energy E is not greater than E_MAX (step S208, No), the calculator 152 proceeds to step S210.

On the other hand, if the energy E is greater than E_MAX (step S208, Yes), the calculator 152 updates E_MAX with the energy E calculated in step S207 (step S209).

If the condition j<(i−1) is satisfied (step S210, Yes), the calculator 152 updates the forward insertion position by adding 1 to the forward insertion position j (step S211). Move to S203.

On the other hand, if the condition j<(i−1) is not satisfied (step S210, No), the calculation unit 152 terminates the forward insertion processing.

Next, an example of the backward insertion processing shown in step S106 of FIG. 7 will be described. FIG. 9 is a flowchart showing a processing procedure of backward insertion processing. As shown in FIG. 9, the calculator 152 sets the front insertion position t to 1 (step S301). The calculator 152 selects matrix elements a _it and a _ti (step S302).

The calculation unit 152 calculates ΔE _t using the stored ΔE _(t−1) (step S303). In step S303, the calculator 152 calculates ΔE shown in the rear table 143b. The calculation unit 152 stores ΔE _t in the storage unit 140 (step S304).

The calculation unit 152 determines whether to execute MCMC bit inversion (step S305). For example, if ΔE _t is positive, the calculator 152 determines to execute MCMC bit inversion (step S305, Yes), and proceeds to step S306. On the other hand, when ΔE _t is 0 or less, the calculation unit 152 determines not to execute the MCMC bit inversion (step S305, No), and proceeds to step S310.

The calculator 152 performs MCMC bit inversion to update the permutation (step S306). The calculator 152 calculates the energy E (step S307). In step S307, the calculation unit 152 calculates energy E by subtracting ΔE from the energy of the original matrix set in step S101.

The calculation unit 152 determines whether the energy E is greater than E_MAX (the maximum value of the energy E so far) (step S308). If the energy E is not greater than E_MAX (step S308, No), the calculator 152 proceeds to step S310.

On the other hand, if the energy E is greater than E_MAX (step S308, Yes), the calculator 152 updates E_MAX with the energy E calculated in step S307 (step S309).

If the condition t≧(number of dimensions N−1) is satisfied (step S310, Yes), the calculation unit 152 ends the backward insertion processing.

On the other hand, if the condition t≧(the number of dimensions N−1) is not satisfied (step S310, No), the calculation unit 152 updates the backward insertion position by adding 1 to the backward insertion position t ( Step S311), and the process proceeds to step S303.

Next, the effects of the optimization device 100 according to this embodiment will be described. The optimization device 100 selects one permutation number of the permutation, moves the selected permutation number forward or backward, and calculates the difference value between the energy of the state before the movement and the energy of the state after the movement. calculate. When calculating the difference value, the optimization device 100 uses the previous difference value stored in the storage unit 140 according to the calculation of ΔE defined in the calculation table 143 . The optimization device 100 updates the difference value in the storage unit 140 with the newly calculated difference value. This makes it possible to reduce the amount of permutation energy calculations.

For example, the processing of the optimization device 100 eliminates redundant operations, selects some elements of the vote count matrix A, and calculates ΔE, thereby reducing the number of additions and subtractions by 99% compared to the conventional technology. becomes possible.

In the prior art, when inserting the first permutation number in the 100th dimension at the end, the difference ΔE _j of the energy E is calculated by equation (20). The number of additions and subtractions according to the conventional technology is 199, which is the total of 99 additions and 100 subtractions.

On the other hand, according to the optimization apparatus 100 according to the present embodiment, the number of additions and subtractions becomes two by reusing ΔE and accumulating in order regardless of the number of dimensions of the LOP. For example, when the permutation number j is moved forward by t, the difference value ΔE _j of the energy E is calculated by equation (21), and the number of additions and subtractions is two.

By the way, the content of the processing of the optimization device 100 described above is an example, and the optimization device 100 may perform other processing. The optimization device 100 selects one permutation number of the permutation, moves the selected permutation number forward or backward, and calculates the difference value between the energy of the state before the movement and the energy of the state after the movement. Although calculated, it is not limited to this. The optimization device 100 changes the state of the matrix by inserting a group of permutation numbers consisting of a plurality of adjacent permutation numbers into the forward or backward permutation, and the energy before the state change and the energy after the state change. may be calculated.

The optimization device 100 registers in the calculation table 143 the calculation of ΔE when moving the selected group backward and the calculation of ΔE when moving the selected group forward. FIG. 10 is a diagram for explaining other processing of the optimization device.

For example, if the original permutation is 12345, the original permutation matrix A is as shown in FIG. Description will be given using the calculation table 143c. The example of the permutation shown in the calculation table 143c is an example, and the description of the relationship between other permutations and the calculation method of ΔE will be omitted.

If the optimization device 100 selects the permutation number 12 from the original permutation number 12345 and inserts the permutation number 12 between the permutation numbers 3 and 4, the permutation becomes 31245. In this case, the optimization device 100 calculates the difference value ΔE between the energy of the permutation 12345 and the energy of the permutation 31245 by the calculation method defined by one matrix of the calculation table 143c.

If the optimization device 100 selects the permutation number 12 from the original permutation number 12345 and inserts the permutation number 12 between the permutation numbers 4 and 5, the permutation becomes 34125. In this case, the optimization device 100 calculates the difference value ΔE between the energy of the permutation 12345 and the energy of the permutation 34125 by the calculation method defined by the two matrices of the calculation table 143c.

If the optimization device 100 selects the permutation number 12 from the original permutation number 12345 and inserts the permutation number 12 after the permutation number 5, the permutation becomes 34512. In this case, the optimization device 100 calculates the difference value ΔE between the energy of the permutation 12345 and the energy of the permutation 34125 by the calculation method defined by the three matrices of the calculation table 143c.

If the optimization device 100 selects the permutation number 45 from the original permutation number 12345 and inserts the permutation number 45 between the permutation numbers 2 and 3, the permutation becomes 12453. In this case, the optimization device 100 calculates the difference value ΔE between the energy of the permutation 12345 and the energy of the permutation 12453 by the calculation method defined by the four matrices of the calculation table 143c.

If the optimization device 100 selects the permutation number 45 from the original permutation number 12345 and inserts the permutation number 45 between the permutation numbers 1 and 2, the permutation becomes 14523. In this case, the optimization device 100 calculates the difference value ΔE between the energy of the permutation 12345 and the energy of the permutation 14523 by the calculation method defined by the five matrices of the calculation table 143c.

If the optimization device 100 selects the permutation number 45 from the original permutation number 12345 and inserts the permutation number 45 before the permutation number 1, the permutation becomes 45123. In this case, the optimization device 100 calculates the difference value ΔE between the energy of the permutation 12345 and the energy of the permutation 45123 by the calculation method defined by the six matrices of the calculation table 143c.

Next, a supplementary explanation regarding MCMC inversion will be given. Simulated Annealing (SA), which applies MCMC, is a general-purpose technique for solving high-dimensional optimal problems. SA is an operation that stochastically searches the neighborhood of the current state, accepts the new state with a high probability (for example, probability 1) if the objective function increases from the current state, and accepts the state with a small probability if it decreases. repeat. SA is not limited to combinatorial optimization problems, but is also used for optimizing objective functions of continuous variables, for example.

Let ΔE be the increment of the objective function (energy) when the current state transitions to the new state. The operation of stochastically accepting a new state even when the objective function increases (ΔE<0) can be understood by a physical analogy of receiving thermal energy from the environment to compensate for the decrease in the objective function. In SA, optimization can be performed while avoiding a local maximum by gradually lowering the parameter corresponding to temperature from a high value. The metallurgical term "annealing" is used because the temperature is lowered. Here, consider the case where the relationship between the probability of taking a state and the energy of that state is the Boltzmann distribution in the equilibrium state. In this case, in the MCMC algorithm, the probability A(ΔE) of accepting a transition to a neighboring state is given by equation (22).

In Equation (22), T indicates temperature. The transition acceptance probability of Equation (22) satisfies the detailed equilibrium termed in statistical physics, and the state distribution is the Boltzmann distribution in the equilibrium state. It should be noted that the transition acceptance probability that satisfies the detailed equilibrium can be created other than the formula (22).

Although the optimization apparatus 100 described above has determined to execute MCMC bit inversion when ΔE is positive, using uniform random number u[i] (0<u[i]<1), A (ΔE _i ) may be compared to determine whether to perform MCMC bit reversal. The optimization device 100 performs MCMC bit inversion when u[i]<A(ΔE _i ), and otherwise does not perform MCMC bit inversion.

Next, an example of the hardware configuration of a computer that realizes the same functions as those of the optimization device 100 shown in the above embodiment will be described. FIG. 11 is a diagram showing an example of the hardware configuration of a computer that implements functions similar to those of the optimization device.

As shown in FIG. 11, a computer 200 has a CPU 201 that executes various arithmetic processes, an input device 202 that receives data input from a user, and a display 203 . The computer 200 also has a communication device 204 that receives data from an external device, and an interface device 205 that connects with various devices. The computer 200 has a RAM 206 that temporarily stores various information and a hard disk device 207 . Each device 201 - 207 is then connected to a bus 208 .

The hard disk device 207 has an acquisition program 207a and a calculation program 207b. The CPU 201 reads out the acquisition program 207 a and the calculation program 207 b and develops them in the RAM 206 .

Acquisition program 207a functions as acquisition process 206a. The calculation program 207b functions as a calculation process 306b.

The processing of the acquisition process 206 a corresponds to the processing of the acquisition unit 151 . Processing of the calculation process 206 b corresponds to processing of the calculation unit 152 .

Note that the programs 207a and 207b do not necessarily have to be stored in the hard disk device 207 from the beginning. For example, each program is stored in a “portable physical medium” such as a flexible disk (FD), CD-ROM, DVD disk, magneto-optical disk, IC card, etc. inserted into the computer 200 . Then, the computer 200 may read and execute the programs 207a and 207b.

The following additional remarks are disclosed regarding the embodiments including the above examples.

(Appendix 1) For the permutation of the matrix corresponding to the permutation of multiple elements in the linear ordering problem, select one permutation number of the permutation, move the selected permutation number forward or backward, and calculating a first difference value between the energy of the first state and the energy of the second state of the permutation after the movement;
storing the first difference value in a storage device;
Select one permutation number of the permutation, move the selected permutation number forward or backward, and combine the energy of the second state of the permutation before the movement with the energy of the third state of the permutation after the movement. 2. An optimization program that causes a computer to execute a process of reading the first difference value stored in the storage device and calculating the second difference value when calculating the second difference value.

(Supplementary note 2) The process of calculating the second difference value includes the number of forward or backward movement of the selected permutation number, the first difference value, a part of the elements of the first state, and the 2. The optimization program according to appendix 1, causing the computer to execute a process of calculating the second difference value using information indicating the relationship between the two difference values.

(Appendix 3) updating the first difference value stored in the storage device with the second difference value, selecting one permutation number of the permutation,
storing the calculated second difference value in the storage device;
When moving the selected permutation number forward or backward and calculating the third difference value between the energy of the third state of the permutation before the movement and the energy of the fourth state of the permutation after the movement, 3. The optimization program according to appendix 1 or 2, further causing a computer to execute a process of reading out the second difference value stored in a storage device and calculating the third difference value.

(Appendix 4) In the selection process, the computer selects a plurality of adjacent permutation numbers in the permutation numbers of the permutation, and changes the permutation state by moving the selected permutation numbers forward or backward. The optimization program according to appendix 1, characterized by:

(Appendix 5) A computer-implemented optimization method comprising:
For the permutation of the matrix corresponding to the permutation of multiple elements in the linear ordering problem, select one permutation number of the permutation, move the selected permutation number forward or backward, and the energy of the first state of the permutation before moving and the energy of the second state of the permutation after being moved, calculating the first difference value,
storing the first difference value in a storage device;
Select one permutation number of the permutation, move the selected permutation number forward or backward, and combine the energy of the second state of the permutation before the movement with the energy of the third state of the permutation after the movement. 2. An optimization method, comprising: reading out the first difference value stored in the storage device and calculating the second difference value when calculating the second difference value.

(Supplementary note 6) The process of calculating the second difference value includes the number of forward or backward shifts of the selected permutation number, the first difference value, a part of the elements of the first state, and the 6. The optimization method according to appendix 5, wherein the computer further executes a process of calculating the second difference value using information indicating the relationship between the two difference values.

(Appendix 7) Update the first difference value stored in the storage device with the second difference value, select one permutation number of the permutation, and store the calculated second difference value in the storage device. and moving the selected permutation number forward or backward, and calculating the third difference value between the energy of the third state of the permutation before the movement and the energy of the fourth state of the permutation after the movement 7. The optimization method according to appendix 5 or 6, wherein the computer further executes a process of reading out the second difference value stored in the storage device and calculating the third difference value.

(Appendix 8) In the selection process, the computer selects a plurality of adjacent permutation numbers in the permutation numbers of the permutation, and moves the selected permutation numbers forward or backward to change the permutation state. The optimization method according to appendix 5, characterized in that:

(Appendix 9) an acquisition unit that acquires a matrix corresponding to a permutation of a plurality of elements in a linear ordering problem;
Select one permutation number of the permutation, move the selected permutation number forward or backward, and compare the energy of the first state of the permutation before the move and the energy of the second state of the permutation after the move. calculating one difference value, storing said first difference value in a storage device, selecting one permutation number of the permutation, moving the selected permutation number forward or backward, and the second state of the permutation before moving. and the energy of the third state of the permutation after being moved, the first difference value stored in the storage device is read, and the second difference value is calculated as a calculating unit that calculates;
An optimization device characterized by comprising:

(Supplementary Note 10) The calculation unit determines the relationship between the number of forward or backward shifts of the selected permutation number, the first difference value, the partial element of the first state, and the second difference value. 10. The optimization device according to appendix 9, wherein the process of calculating the second difference value is executed using information indicating .

(Additional Note 11) The calculation unit updates the first difference value stored in the storage device with the second difference value, selects one permutation number of the permutation, and calculates the calculated second difference value. Stored in the storage device, moving the selected permutation number forward or backward, and a third difference value between the energy of the third state of the permutation before the movement and the energy of the fourth state of the permutation after the movement. 11. The optimization apparatus according to Supplementary note 9 or 10, further comprising reading the second difference value stored in the storage device to calculate the third difference value .

(Appendix 12) The calculation unit selects a plurality of adjacent permutation numbers in the permutation numbers and moves the selected permutation numbers forward or backward to change the permutation state. 9. The optimization device according to clause 9.

100 optimization device 110 communication unit 120 input unit 130 display unit 140 storage unit 141 vote matrix information 142 difference value information 143 calculation table 150 control unit 151 acquisition unit 152 calculation unit

Claims (6)

For the permutation of the matrix corresponding to the permutation of multiple elements in the linear ordering problem, select one permutation number of the permutation, move the selected permutation number forward or backward, and the energy of the first state of the permutation before moving and the energy of the second state of the permutation after being moved, calculating the first difference value,
storing the first difference value in a storage device;
Select one permutation number of the permutation, move the selected permutation number forward or backward, and combine the energy of the second state of the permutation before the movement with the energy of the third state of the permutation after the movement. 2. An optimization program that causes a computer to execute a process of reading the first difference value stored in the storage device and calculating the second difference value when calculating the second difference value. The process of calculating the second difference value includes the number of forward or backward shifts of the selected permutation number, the first difference value, a partial element of the first state, and the second difference value. 2. The optimization program according to claim 1, causing the computer to execute a process of calculating the second difference value using information indicating the relationship of . updating the first difference value stored in the storage device with the second difference value, selecting a permutation number of permutations;
storing the calculated second difference value in the storage device;
When moving the selected permutation number forward or backward and calculating the third difference value between the energy of the third state of the permutation before the movement and the energy of the fourth state of the permutation after the movement, 3. The optimization program according to claim 1, further causing a computer to execute a process of reading out the second difference value stored in a storage device and calculating the third difference value. In the selection process, the computer selects a plurality of adjacent permutation numbers in the permutation numbers of the permutation, and moves the selected permutation numbers forward or backward to change the permutation state. The optimization program according to claim 1. A computer implemented optimization method comprising:
For the permutation of the matrix corresponding to the permutation of multiple elements in the linear ordering problem, select one permutation number of the permutation, move the selected permutation number forward or backward, and the energy of the first state of the permutation before moving and the energy of the second state of the permutation after being moved, calculating the first difference value,
storing the first difference value in a storage device;
Select one permutation number of the permutation, move the selected permutation number forward or backward, and combine the energy of the second state of the permutation before the movement with the energy of the third state of the permutation after the movement. 2. An optimization method, comprising: reading out the first difference value stored in the storage device and calculating the second difference value when calculating the second difference value. an obtaining unit for obtaining a matrix corresponding to permutations of multiple elements in a linear ordering problem;
Select one permutation number of the permutation, move the selected permutation number forward or backward, and compare the energy of the first state of the permutation before the move and the energy of the second state of the permutation after the move. calculating one difference value, storing said first difference value in a storage device, selecting one permutation number of the permutation, moving the selected permutation number forward or backward, and the second state of the permutation before moving. and the energy of the third state of the permutation after being moved, the first difference value stored in the storage device is read, and the second difference value is calculated as a calculating unit that calculates;
An optimization device characterized by comprising:

Images