JP7024502B2 - Knee point selection program, knee point selection method and knee point selection device - Google Patents

Description

The present invention relates to a knee point selection program and the like.

In the multi-objective optimization problem, each objective function has a trade-off relationship, and one optimal solution is not determined. Therefore, a non-inferior solution set of each objective function is obtained. A non-inferior set is a set of non-inferior answers that cannot be given superiority or inferiority, and it can be said that when one of the objective function values is improved, the other objective function values are deteriorated. The surface formed by the non-inferior solution set is called the Pareto front.

FIG. 17 is a diagram showing an example of a Pareto front. In FIG. 17, the horizontal axis is the axis corresponding to the objective function value of the objective function f ₁ , and the more to the left, the better the objective function value for the objective function f ₁ . The vertical axis is the axis corresponding to the objective function value of the objective function f ₂ , and the lower the axis, the better the objective function value for the objective function f ₂ .

The decision maker will select one final non-inferior answer from the non-inferior sets contained in the Pareto Front. The preferred non-inferiority is the knee point P, which has a well-balanced trade-off ratio. In the vicinity of the knee point P, if the objective function f ₁ is improved a little, the objective function f ₂ is greatly deteriorated, and if the objective function f ₂ is improved, the objective function f ₁ is greatly deteriorated.

For example, as a conventional technique for detecting a knee point of a Pareto front, there is a technique using a normal boundary crossing method. In this conventional technique, the point farthest in the dominant normal direction from the boundary line C connecting the end points A and B of the Pareto front is detected as a knee point. In the example shown in FIG. 17, P is detected as a knee point.

I. Das. On characterizing the “knee” of the Pareto curve based on normal-boundary intersection. Structural Optimization, 18 (2): 107-115, 1999.

However, in the above-mentioned conventional technique, there is a problem that a robust knee point cannot be selected from a sample containing noise.

In one aspect, it is an object of the present invention to provide a knee point selection program, a knee point selection method, and a knee point selection device capable of selecting a robust knee point from a sample containing noise.

In the first plan, the computer is made to perform the following processing. The computer accepts multiple non-inferior inputs for an optimization problem with multiple objective functions. The computer repeatedly executes the process of giving height information based on a specific direction set on the multidimensional space with multiple objective functions as the coordinate axes for each of the multiple non-inferior answers while changing the weight for the non-inferior answers. By doing so, the number of times that the height information becomes the minimum is calculated for each non-inferior answer. The computer selects a non-inferior answer that is a knee point based on the calculated number of times.

You can select a robust knee point from a sample that contains noise.

FIG. 1 is a diagram showing an example of a data structure of non-inferior solution set information. FIG. 2 is a diagram for explaining the normalization process. FIG. 3 is a diagram showing an example of a data structure of undirected graph information. FIG. 4 is a diagram showing an example of a data structure of directed graph information. FIG. 5 is a diagram (1) for explaining a process in which the information processing apparatus detects a knee point. FIG. 6 is a diagram (2) for explaining the process of detecting the knee point by the information processing apparatus. FIG. 7 is a diagram for explaining a problem of the reference technique. FIG. 8 is a diagram for explaining the processing of the knee point selection device according to the present embodiment. FIG. 9 is a functional block diagram showing the configuration of the knee point selection device according to the present embodiment. FIG. 10 is a diagram showing an example of a data structure of non-inferior solution set information according to this embodiment. FIG. 11 is a diagram showing an example of a data structure of weight set information according to this embodiment. FIG. 12 is a diagram showing an example of the data structure of the minimum number of times table according to this embodiment. FIG. 13 is a diagram showing an example of the update process of the minimum number of times table. FIG. 14 is a diagram for explaining the processing of the selection unit according to the present embodiment. FIG. 15 is a flowchart showing a processing procedure of the knee point selection device according to the present embodiment. FIG. 16 is a diagram showing an example of a hardware configuration of a computer that realizes the same function as the knee point selection device. FIG. 17 is a diagram showing an example of a Pareto front.

Hereinafter, examples of the knee point selection program, the knee point selection method, and the knee point selection device disclosed in the present application will be described in detail with reference to the drawings. The present invention is not limited to this embodiment.

Before explaining the embodiment of the present invention, the reference technique devised by the inventor will be described. This reference technique is not a prior art. When the information processing apparatus according to the reference technique receives the non-inferior solution set information, it performs a process of normalizing the non-inferior solution set information.

Here, the non-inferior solution set information is the non-inferior answer information for a plurality of objective functions in the multi-objective optimization problem.

FIG. 1 is a diagram showing an example of a data structure of non-inferior solution set information. For example, the non-inferior solution to N objective functions is shown as a solution in N-dimensional space as shown in FIG. 1, and the non-inferior solution set information 20 includes the non-inferior answer ID and f ₁ , f ₂ , _Corresponds to f3. The non-inferior ID is information that uniquely identifies the non-inferior answer. f ₁ , f ₂ , and f ₃ are objective function values corresponding to the objective functions f ₁ , f ₂ , and f ₃ . For example, the non-inferior answer corresponding to the non-inferior ID "1" is "f ₁ = 1.4, f ₂ = -2.4, f ₃ = 7.7". In the example shown in FIG. 1, f ₁ to f ₃ are shown, but the non-inferior solution set information may include other objective function values.

The processing in which the information processing apparatus according to the reference technique normalizes the non-inferior solution set information will be described. FIG. 2 is a diagram for explaining the normalization process. The information processing apparatus reads out the non-inferior solution set information 20 and searches for the maximum value and the minimum value from the values in each column. For example, in the column of f ₁ , the maximum value is "4.4" and the minimum value is "1.4". _In the column of f2, the maximum value is "2.6" and the minimum value is "-2.4". _In the column of f3, the maximum value is "12.6" and the minimum value is "5.6".

The information processing device updates each objective function value by subtracting the minimum value from the value in each column of the non-inferior solution set information 20 and dividing by (maximum value-minimum value), respectively, and intermediate data 20a. To generate.

For example, the case of updating the objective function value f ₁ "1.4" of the non-inferior ID "1" of the non-inferior set information 20 will be described as follows: (1.4-1.4) / (4.4-). 1.4) = 0. Therefore, the objective function f ₁ of the non-inferior ID "1" of the intermediate data 20a is "0". Explaining the case of updating the objective function f ₁ "2.6" of the non-inferior ID "2" of the non-inferior set information 20, (2.6-1.4) / (4.4-1.4) ) = 0.4. Therefore, the objective function f1 of the non-inferior ID "2" of the intermediate data 20a is "0.4". The information processing device updates other objective function values in the same manner.

The information processing apparatus updates each value by multiplying the value of the intermediate data 20a by a weight corresponding to the type of the objective function, and generates the normalized information 20b. For example, the information processing apparatus multiplies the objective function value of the objective function f ₁ by w ₁ , multiplies the objective function value of the objective function f ₂ by w ₂ , and multiplies the objective function value of the objective function f ₃ by w ₃ . do. The weights w ₁ , w ₂ , and w ₃ are preset, and for example, w ₁ = "1", w ₂ = "2", and w ₃ = "3".

The information processing device gives "height information" that the value becomes larger as the non-inferior answer located in the non-dominant direction in the multidimensional space is given to the non-inferior solution arranged in the multidimensional space. From each non-inferior answer to which information is given, the non-inferior answer which is the minimum point is detected as a knee point.

For example, the information processing apparatus calculates the height information for each non-inferior ID based on the height function h _w . The height function h _w is represented by the equation (1). The height information given to the non-inferior ID calculated by the equation (1) corresponds to the sum of the normalization information 20b in the row direction.

The information processing apparatus executes clustering for classifying non-inferior answers having a short distance (Eugrid distance) into the same cluster for each non-inferior answer belonging to the same height information. For example, the information processing device classifies each non-inferior answer into clusters by performing clustering by Mapper. For example, the information processing device is called "G.Singh, F.Memoli, and G.Carlsson. Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition. In Proceedings of the Symposium on Point Based Graphics, The technique described in "Prague, Czech Republic, 2007." is used.

The information processing device generates undirected graph information based on the result of clustering by Mapper. The undirected graph information is information in which clusters clustered based on Mapper are connected to each other by overlapping clusters. Here, the fact that two clusters overlap means that there is a non-inferior solution belonging to both of the two clusters in the non-inferior solution set.

FIG. 3 is a diagram showing an example of a data structure of undirected graph information. In the example shown in FIG. 3, the height information is given to each cluster of the undirected graph information 25a, and the overlapping clusters are connected by edges. The height information of each cluster is given based on the height information of each non-inferior answer clustered based on Mapper.

That is, for non-inferior answers arranged in the multidimensional space, height information whose value becomes larger as the non-inferior answer located in the non-dominant direction in the multidimensional space is given, and each cluster c1 to c7 is given height information. Is given height information based on the non-inferior height information that constitutes the cluster. For example, for clusters existing in a multidimensional space, the value of height information becomes larger as the cluster is located in the non-dominant direction. In the example shown in FIG. 3, height information 1,3,2,1,2,3,2 is given to the clusters c1, c2, c3, c4, c5, c6, and c7.

Further, the cluster c2 and the cluster c3 are connected by the side h1. The cluster c3 and the cluster c4 are connected by the side h2. The cluster c4 and the cluster c5 are connected by the side h3. The cluster c5 and the cluster c6 are connected by the side h4. The cluster c6 and the cluster c7 are connected by the side h5.

The information processing apparatus converts the undirected graph information 25a into the directed graph information 25b based on the height information of each cluster. The directed graph is information in which orientation information is provided on each side shown in the undirected graph information 25a described with reference to FIG. For example, when the height information of the first cluster is larger than the height information of the second cluster, the information processing apparatus sets the direction of the side connecting the first cluster and the second cluster. Set in the direction from the second cluster to the first cluster. When the height information of the second cluster is larger than the height information of the first cluster, the information processing apparatus determines the direction of the side connecting the first cluster and the second cluster. Set in the direction from the cluster to the second cluster.

FIG. 4 is a diagram showing an example of a data structure of directed graph information. As shown in FIG. 4, in addition to the information described in FIG. 3, information on the orientation is given to each side h1 to h5. The side h2 is a directed side from the cluster c4 to the cluster c3. The side h1 is a directed side from the cluster c3 to the cluster c2. The side h3 is a directed side from the cluster c4 to the cluster c5. The side h4 is a directed side from the cluster c5 to the cluster c6. The side h5 is a directed side from the cluster c7 to the cluster c6.

The information processing apparatus detects a cluster containing a non-inferior answer corresponding to the knee point based on the directed graph information 25b. FIG. 5 is a diagram (1) for explaining a process in which the information processing apparatus detects a knee point. The information processing apparatus detects a very small cluster in which the input order is 0 and the output order is ≧ 1. In the example shown in FIG. 5, the clusters c4 and c7 are extremely small clusters in which the input order = 0 and the output order ≧ 1. A tiny cluster is one in which there are no other clusters around the tiny cluster that are lower than the tiny cluster. The information processing apparatus detects the non-inferior non-inferior ID included in the minimal cluster c4 and the non-inferior non-inferior ID included in the minimal cluster c7 as knee points.

For example, the non-inferior non-inferior ID included in the micro cluster c4 is "1,3", and the non-inferior non-inferior ID included in the micro cluster c7 is "2, 5". In this case, the information processing apparatus detects the non-inferior ID "1, 2, 3, 5" as a knee point.

By the way, even if the information processing apparatus is a non-inferior answer belonging to a very small cluster in which the input order is 0 and the output order is ≧ 1, if the following conditions are further satisfied, the corresponding non-inferior answer is given. Suppress detection as a knee point. Specifically, when the non-inferior answer belonging to the minimum cluster is also included in other maximal clusters, the information processing apparatus suppresses the detection of the corresponding non-inferior answer as a knee point. The condition of the cluster to be the maximum cluster is a cluster in which the input order = 1 and the output order = 0.

FIG. 6 is a diagram (2) for explaining the process of detecting the knee point by the information processing apparatus. In FIG. 6, graph 26 is a graph in which each non-inferior answer is plotted two-dimensionally. For example, the horizontal axis is the axis corresponding to the objective function value of the objective function f ₁ , and the more to the left, the better the objective function value for the objective function f ₁ . The vertical axis is the axis corresponding to the objective function value of the objective function f ₂ , and the lower the axis, the better the objective function value for the objective function f ₂ . In the graph 26, the direction from the upper right to the lower left is the dominant direction. Therefore, the height of each non-inferior answer in the graph 26 becomes larger as it is located in the upper right of the graph 26.

The information processing apparatus generates directed graph information 25c by performing clustering by Mapper for each non-inferior answer shown in graph 26 of FIG. For example, in the graph 26, each non-inferior answer contained in the regions 26a to 26h is classified into the minimum clusters 30a to 30h, respectively.

In the interval division based on the height of the non-inferior solution set by Mapper, the adjacent sections are overlapped and divided, and the non-inferior solutions belonging to each interval are clustered to generate undirected graph information 25a. do. Therefore, a non-inferior answer located in an area where sections overlap will belong to one cluster in each section, and therefore belong to two or more clusters throughout the entire section. Therefore, even if there is only a single non-inferior answer as in the region 26e, if the non-inferior answer is in the overlapping position of the interval, the corresponding non-inferior answer is minimized in the generated undirected graph 25a. Not only does it belong to the cluster 30e, but it also belongs to the cluster 41a having the next largest height, and further to the maximal cluster 42a. Similarly, the non-inferiority of the region 26f belongs not only to the minimum cluster 30f but also to the cluster 41b and the maximum cluster 42b.

In FIG. 6, the extremely small clusters 30a to 30d, 30g, and 30h are the extremely small clusters to be detected. However, the non-inferiority belonging to the minimal clusters 30e and 30f is an isolated point included in the regions 26e and 26f, which is not suitable as a knee point. Therefore, the information processing apparatus determines whether the non-inferior answer belonging to the minimum cluster also belongs to another maximum cluster. The information processing apparatus prevents the non-inferior answer included in the regions 26e and 26f from being detected by suppressing the detection of the non-inferior answer satisfying the said condition as a knee point.

As mentioned above, the reference technique detects the non-inferiority contained in the tiny cluster as a knee point. In the following description, the non-inferior answer included in the minimum cluster is appropriately referred to as "non-inferior answer corresponding to the minimum point".

Here, the problems of the reference technique will be described. There is a problem that the knee point detected by the reference technique is easily changed by the noise included in the non-inferior solution set information.

FIG. 7 is a diagram for explaining a problem of the reference technique. In FIG. 7, graph 50a is a graph in which an ideal non-inferior solution set containing no noise is plotted two-dimensionally. The graphs 50b and 50c are graphs in which the non-inferior solution set including noise is plotted two-dimensionally. _In the graphs 50a to 50c, the horizontal axis is the axis corresponding to the objective function value of the objective function f1. _The vertical axis is the axis corresponding to the objective function value of the objective function f2.

As shown in FIG. 7, when noise is included in the non-inferior solution set, the scale of the coordinate axes changes. When the scale of the axis changes, the height function changes, and when the height function changes, the detected knee point changes. The knee points detected by the reference technique include non-inferior answers that are no longer knee points with only a slight change in the height function. For example, in the graph 50a, even if the non-inferior answers 10A to 10F are detected as knee points, in the graphs 50b and 50c, some non-inferior answers may not be detected as knee points. As for the height function, as shown in the equation (1), the value of the height function changes when w changes. Changing the scale of the objective function f is equivalent to changing w. That is, it is required to select a robust knee point by excluding unstable non-inferior answers that are not knee points even if the height function changes a little.

Next, the processing of the knee point selection device according to this embodiment will be described. The knee point selection device generates a plurality of weight values used in the height function of the equation (1), and uses a plurality of height functions having different weights to perform a process of identifying a non-inferior answer corresponding to a minimum point. , For each non-inferior answer, count the number of times the minimum score was reached. The knee point selection device selects a high-ranking non-inferior answer having a large number of minimum points as a knee point.

FIG. 8 is a diagram for explaining the processing of the knee point selection device according to the present embodiment. The graphs 55a, 55b, 55c shown in FIG. 8 are graphs in which height information is added to the non-inferior solution set based on the height function. For example, the horizontal axis of _each graph 55a to 55c is the axis corresponding to the objective function value of the objective function f1. The vertical axis of _each graph 55a to 55c is the axis corresponding to the objective function value of the objective function f2.

Here, the weights of the height functions when generating the graphs 55a to 55c are different from each other. For example, the height function used when generating the graph 55a is "h ₁ = 0.2 × f ₁ + 0.8 × f ₂ ". The height function used when generating the graph 55b is "h ₂ = 0.5 × f ₁ + 0.5 × f ₂ ". The height function used when generating the graph 55c is "h ₃ = 0.8 × f ₁ + 0.2 × f ₂ ".

For example, in the graph 55a, the non-inferiority ID of the non-inferior answer (knee point) corresponding to the minimum point is set to "10B, 10C, 10D, 10F". In the graph 55b, the non-inferiority ID corresponding to the minimum point is defined as "10C, 10D, 10F". In the graph 55c, the non-inferiority ID corresponding to the minimum point is defined as "10A, 10C, 10D, 10F". Then, the number of times selected as the minimum score is "1 time" for the non-inferiority ID "10A", "1 time" for the non-inferiority ID "10B", and "1 time" for the non-inferiority ID "10B". The non-inferior answer of "10C" is "3 times". In addition, the non-inferiority ID "10D" is "3 times", the non-inferiority ID "10E" is "2 times", and the non-inferiority ID "10F" is "2". "Times".

The knee point selection device selects the non-inferior answer of the upper N as the knee point from the one selected as the minimum point most frequently. For example, when N = 4, the knee point selection device selects the non-inferiority ID “10C, 10D, 10E, 10F” as the knee point.

In this way, the knee point selection device uses a plurality of height functions having different weights to perform processing for identifying non-inferior answers corresponding to the minimum points, and for each non-inferior answer, the number of times that the minimum points are reached is large. Is selected as the knee point. A non-inferior answer with a large number of minimum points can be said to be a robust knee point because it is often a knee point even if the height function changes a little. Therefore, according to the knee point selection device according to the present embodiment, it is possible to select a robust knee point by excluding an unstable non-inferior answer that is no longer a knee point even if the height function is slightly changed. ..

Next, the configuration of the knee point selection device 100 according to this embodiment will be described. FIG. 9 is a functional block diagram showing the configuration of the knee point selection device according to the present embodiment. As shown in FIG. 9, the knee point selection device 100 includes a communication unit 110, an input unit 120, a display unit 130, a storage unit 140, and a control unit 150.

The communication unit 110 is a processing unit that connects to an external device or the like (not shown) via a network and executes data communication with the external device. The communication unit 110 corresponds to a communication device such as a NIC (Network Interface Card).

The input unit 120 is an input device for inputting various information to the knee point selection device 100. The input unit 120 corresponds to a keyboard, a mouse, a touch panel, and the like. For example, the user operates the input unit 120 to input the non-inferior solution set information 141 and the like, which will be described later.

The display unit 130 is a display device that displays information output from the control unit 150. The display unit 130 corresponds to a liquid crystal display, a touch panel, or the like.

The storage unit 140 has a non-inferior solution set information 141, a weight set information 142, a Mapper parameter 143, an undirected graph information 144, a directed graph information 145, and a minimum number of times table 146. The storage unit 140 corresponds to semiconductor memory elements such as RAM (Random Access Memory), ROM (Read Only Memory), and flash memory (Flash Memory), and storage devices such as HDD (Hard Disk Drive).

The non-inferior set information 141 is non-inferior information for a plurality of objective functions in a multi-objective optimization problem.

FIG. 10 is a diagram showing an example of a data structure of non-inferior solution set information according to this embodiment. For example, the non-inferior solution to N objective functions is shown as a solution in N-dimensional space as shown in FIG. 10, and the non-inferior solution set information 141 includes the non-inferior answer ID and f ₁ and f ₂ . To associate. The non-inferior ID is information that uniquely identifies the non-inferior answer. f ₁ and f ₂ are objective function values corresponding to the objective functions f ₁ and f ₂ . In the example shown in FIG. 10, f ₁ and f ₂ are shown, but the non-inferior solution set information 141 may include other objective function values.

The weight set information 142 holds information on the weights given to each objective function when calculating the height information. The weight set information 142 includes a plurality of types of weight sets.

FIG. 11 is a diagram showing an example of a data structure of weight set information according to this embodiment. As shown in FIG. 11, the weight set information 142 associates the weight set number with the weights (w ₁ , w ₂ ). The weight set number is a number that identifies a set of weights w ₁ and w ₂ given to the height function. For example, when the weight set number "W1001" is selected, w ₁ = "7" and w ₂ = "2" are given to the height function shown in the equation (1). Although FIG. 11 shows a set of weights w ₁ and w ₂ as an example, other weights (for example, w ₃ , w ₄ , ...) may be included.

Mapper parameter 143 contains information on parameters used when clustering non-inferior answers based on Mapper. For example, the Mapper parameter 143 includes the number of Mapper sections, the overlap rate of Mapper sections, and the number of bins in Mapper clustering.

The undirected graph information 144 is information in which clusters clustered based on Mapper are connected to each other by overlapping clusters. For example, the data structure of the undirected graph information 144 corresponds to the data structure of the undirected graph information 25a described with reference to FIG.

The directed graph information 145 is information in which orientation information is provided on each side shown in the undirected graph information 144. For example, the orientation of the side connecting the first cluster and the second cluster is from the second cluster to the first when the height information of the first cluster is larger than the height information of the second cluster. The direction is toward one cluster. The orientation of the side connecting the first cluster and the second cluster is from the first cluster to the second cluster when the height information of the second cluster is larger than the height information of the first cluster. It will be in the direction toward the cluster. For example, the data structure of the directed graph information 145 corresponds to the data structure of the directed graph information 25b described with reference to FIG.

The minimum number of times table 146 is a table that holds the number of non-inferior answers corresponding to the minimum points for each non-inferior answer. FIG. 12 is a diagram showing an example of the data structure of the minimum number of times table according to this embodiment. As shown in FIG. 12, the minimum number of times table 146 associates the non-inferior ID with the minimum number of times. The non-inferior ID is information that uniquely identifies the non-inferior answer. The minimum number of times indicates the number of non-inferior answers corresponding to the minimum points. The initial value of each minimum number of times is 0. The process using the minimum number table 146 will be described later.

Returning to the description of FIG. The control unit 150 includes a reception unit 151, a weight generation unit 152, a calculation unit 153, a selection unit 154, and an output unit 155. The control unit 150 can be realized by a CPU (Central Processing Unit), an MPU (Micro Processing Unit), or the like. It can also be realized by hard-wired logic such as ASIC (Application Specific Integrated Circuit) and FPGA (Field Programmable Gate Array).

The reception unit 151 is a processing unit that receives various information from the communication unit 110 or the input unit 120 and stores the received information in the storage unit 140. For example, the reception unit 151 receives the non-inferior solution set information 141 and the Mapper parameter 143 and stores them in the storage unit 140. Further, when the reception unit 151 receives the weight generation condition information, the reception unit 151 outputs the weight generation condition information to the weight generation unit 152. The weight generation condition information includes conditions (lattice points, distribution, etc.) for generating the weight set information 142.

The weight generation unit 152 is a processing unit that generates weight set information 142 based on the weight generation condition information. The weight generation unit 152 stores the weight set information 142 in the storage unit 140. For example, the weight generation unit 152 selects weights in a grid pattern from the range Δ in which the weights can be taken. The range Δ is defined as in Eq. (2). Alternatively, the weight generation unit 152 may select the weight with a uniform distribution on the range Δ, or may select the weight with a normal distribution centered on the specified value on the range Δ.

In this embodiment, the case where the weight generation unit 152 generates the weight set information 142 has been described as an example, but the knee point selection device 100 may receive the weight set information 142 from the communication unit 110 or the input unit 120. good.

The calculation unit 153 selects one weight set from the plurality of weight sets of the weight set information 142, and calculates height information for each of the non-inferior answers included in the non-inferior solution set information 141. The calculation unit 153 identifies the non-inferior answer corresponding to the minimum point based on the height information of each non-inferior answer. The calculation unit 153 refers to the minimum number of times table 146, and adds 1 to the minimum number of times corresponding to the non-inferior answer ID that is the minimum point. The calculation unit 153 repeatedly executes the above process while changing each weight set included in the weight set information 142.

An example of a process in which the calculation unit 153 calculates the height information of the non-inferior answer included in the non-inferior solution set information 141 will be described. The calculation unit 153 selects one weight set from the weight set information 142, sets the weights w ₁ and w ₂ of the selected weight set to the height function shown in the equation (1), and sets the height function. Based on this, the height information of the non-inferior answer is calculated. Regarding the process of calculating the height information of the non-inferior answer, it is the same as the information processing apparatus of the above-mentioned reference technique except that one weight set is selected from the weight set information 142 and used for the height function.

Subsequently, the calculation unit 153 will explain an example of the process of specifying the non-inferior answer corresponding to the minimum point based on the height information of the non-inferior answer. The calculation unit 153 executes clustering for classifying non-inferior answers having a short distance (Eugrid distance) into the same cluster for each non-inferior answer belonging to the same height information. The calculation unit 153 classifies each non-inferior answer into a cluster by executing clustering by Mapper using the Mapper parameter 143.

The calculation unit 153 generates undirected graph information 144 based on the result of clustering by Mapper. Further, the calculation unit 153 converts the undirected graph information 144 into the directed graph information 145 based on the height information of each cluster. The process in which the calculation unit 153 generates the undirected graph information 144 and the directed graph information 145 is the same as the information processing apparatus of the above-mentioned reference technique.

The calculation unit 153 detects a cluster (minimal cluster) including a non-inferior answer corresponding to the knee point based on the directed graph information 145. The calculation unit 153 detects the non-inferior answer included in the minimum cluster as a knee point (non-inferior answer corresponding to the minimum point). The process of detecting the knee point by the calculation unit 153 is the same as that of the information processing apparatus of the above-mentioned reference technique.

When the calculation unit 153 detects a non-inferior answer corresponding to the minimum point by executing the above process, the calculation unit 153 updates the minimum number of times table 146. FIG. 13 is a diagram showing an example of the update process of the minimum number of times table. The minimum number of times table 146a is the minimum number of times table 146 before the update. For example, the non-inferiority ID detected as a knee point by the above processing is set to "10A, 10C, 10D". In this case, the calculation unit 153 generates the updated minimum number table 146b by incrementing the non-defective ID by 1 to the minimum number corresponding to "10A, 10C, 10D".

The selection unit 154 is a processing unit that selects the non-inferior answer of the upper N having a large number of minimum times based on the minimum number of times table 146. N is a predetermined natural number and is set in advance by the user. The non-inferior answer selected by the selection unit 154 is the knee point. The selection unit 154 outputs the information of the knee point corresponding to the selected minimum point to the output unit 155.

FIG. 14 is a diagram for explaining the processing of the selection unit according to the present embodiment. For example, the minimum number table 146 obtained as a result of the calculation unit 153 repeatedly executing the above processing while changing each weight set included in the weight set information 142 is referred to as the minimum number table 146b. When the records included in the minimum number of times table 146b are sorted in descending order of the minimum number of times, the selection unit 154 sorts the records in the order of the non-inferiority IDs "10D, 10B, 10C, 10A, 10E" as shown in the minimum number of times table 146c. Become. When 3 is set as N, the selection unit 154 selects the non-inferior ID "10D, 10B, 10C" as the non-inferior answer (non-inferior ID) corresponding to the minimum point.

The output unit 155 is a processing unit that causes the display unit 130 to display the information of the knee point selected by the selection unit 154. Further, the output unit 155 may notify the external device of the detection result via the network. For example, the output unit 155 acquires the record of the non-inferior ID selected as the knee point from the non-inferior set information 141, and outputs the acquired record.

Next, an example of the processing procedure of the knee point selection device according to this embodiment will be described. FIG. 15 is a flowchart showing a processing procedure of the knee point selection device according to the present embodiment. As shown in FIG. 15, the reception unit 151 of the knee point selection device 100 receives the non-inferior solution set information 141, the Mapper parameter 143, and the weight generation condition information (step S101).

The weight generation unit 152 of the knee point selection device 100 generates the weight set information 142 based on the weight generation condition information (step S102). The calculation unit 153 of the knee point selection device 100 selects an unselected weight set included in the weight set information 142 (step S103).

The calculation unit 153 detects a non-inferior answer corresponding to the minimum point (step S104). The calculation unit 153 updates the minimum number of times table 146 based on the detection result of the non-inferior answer corresponding to the minimum point (step S105).

The calculation unit 153 determines whether or not all the weight sets included in the weight set information 142 have been selected (step S106). If all the weight sets have not been selected (steps S106, No), the calculation unit 153 proceeds to step S103. When all the weight sets are selected (steps S106, Yes), the calculation unit 153 shifts to step S107.

The selection unit 154 of the knee point selection device 100 sorts the records in the minimum number of times table 146 based on the minimum number of times (step S107). The selection unit 154 selects, as a knee point, the non-inferior answer corresponding to the top N records among the sorted records (step S108). The output unit 155 of the knee point selection device 100 outputs the knee point information to the display unit 130 and displays it (step S109).

Next, the effect of the knee point selection device 100 according to this embodiment will be described. The knee point selection device 100 uses a plurality of height functions having different weights to perform processing for identifying non-inferior answers corresponding to the minimum points, and for each non-inferior answer, the knee point is the one with the largest number of minimum points. Select as. A non-inferior answer with a large number of minimum points can be said to be a robust knee point because it is often a knee point even if the height function changes a little. Therefore, according to the knee point selection device 100 according to the present embodiment, it is possible to select a robust knee point by excluding an unstable non-inferior answer that is no longer a knee point even if the height function is slightly changed. can.

The knee point selection device 100 registers the minimum number of times for each non-inferior answer in the minimum number of times table 146, and sorts the non-inferior answers of the minimum number of times table 146 based on the minimum number of times. The knee point selection device 100 selects a non-inferior answer having the highest number of minimum times as a knee point. This allows you to select multiple robust knee points.

The knee point selection device 100 calculates the height information for the non-inferior answer by summing the values obtained by multiplying the values of the plurality of objective functions included in the non-inferior answer by the weight. This makes it possible to efficiently identify the non-inferior answer that corresponds to the minimum point.

Next, an example of a computer hardware configuration that realizes the same functions as the knee point selection device 100 shown in the above embodiment will be described. FIG. 16 is a diagram showing an example of a hardware configuration of a computer that realizes the same function as the knee point selection device.

As shown in FIG. 16, the computer 200 includes a CPU 201 that executes various arithmetic processes, an input device 202 that receives data input from a user, and a display 203. Further, the computer 200 has a reading device 204 for reading a program or the like from a storage medium, and an interface device 205 for exchanging data with a recording device or the like via a wired or wireless network. Further, the computer 200 has a RAM 206 for temporarily storing various information and a hard disk device 207. Then, each of the devices 201 to 207 is connected to the bus 208.

The hard disk device 207 has a reception program 207a, a weight generation program 207b, a calculation program 207c, a selection program 207d, and an output program 207e. The CPU 201 reads out the programs 207a to 207e and develops them in the RAM 206.

The reception program 207a functions as the reception process 206a. The weight generation program 207b functions as the weight generation process 206b. The calculation program 207c functions as the calculation process 206c. The selection program 207d functions as the selection process 206d. The output program 207e functions as an output process 206e.

The processing of the reception process 206a corresponds to the processing of the reception unit 151. The processing of the weight generation process 206b corresponds to the processing of the weight generation unit 152. The processing of the calculation process 206c corresponds to the processing of the calculation unit 153. The processing of the selection process 206d corresponds to the processing of the selection unit 154. The processing of the output process 206e corresponds to the processing of the output unit 155.

The programs 207a to 207e 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), a CD-ROM, a DVD, a magneto-optical disk, or an IC card inserted in the computer 200. Then, the computer 200 may read and execute each of the programs 207a to 207e.

The following additional notes will be further disclosed with respect to the embodiments including each of the above embodiments.

(Appendix 1) Accepting multiple non-inferior answers about optimization problems using multiple objective functions
For each of the plurality of non-inferior answers, the process of giving height information based on a specific direction set on the multidimensional space with the plurality of objective functions as coordinate axes is repeatedly executed while changing the weight for the non-inferior answers. By doing so, the number of times the height information becomes the minimum is calculated for each non-inferior answer.
A knee point selection program characterized by causing a computer to execute a process of selecting a non-inferior answer to be a knee point based on the calculated number of times.

(Appendix 2) In the process of selecting the non-inferior answer that is the knee point, a plurality of non-inferior answers are sorted based on the number of times that the height information becomes the minimum, and among the plurality of sorted non-inferior answers. , The knee point selection program according to Appendix 1, wherein a non-inferior answer having a higher minimum number of times is selected as the knee point.

(Appendix 3) The calculation process is characterized in that height information for the non-inferior answer is calculated by summing the values obtained by multiplying the values of a plurality of objective functions included in the non-inferior answer by a weight. The knee point selection program described in Appendix 1 or 2.

(Appendix 4) This is a knee point selection method performed by a computer.
Accepts multiple non-inferior inputs for optimization problems using multiple objective functions,
For each of the plurality of non-inferior answers, the process of giving height information based on a specific direction set on the multidimensional space with the plurality of objective functions as coordinate axes is repeatedly executed while changing the weight for the non-inferior answers. By doing so, the number of times the height information becomes the minimum is calculated for each non-inferior answer.
A knee point selection method characterized by executing a process of selecting a non-inferior answer to be a knee point based on the calculated number of times.

(Appendix 5) In the process of selecting the non-inferior answer that is the knee point, a plurality of non-inferior answers are sorted based on the number of times that the height information becomes the minimum, and among the plurality of sorted non-inferior answers. The knee point selection method according to Appendix 4, wherein a non-inferior answer having a higher number of minimum times is selected as the knee point.

(Appendix 6) The calculation process is characterized in that height information for the non-inferior answer is calculated by summing the values obtained by multiplying the values of a plurality of objective functions included in the non-inferior answer by a weight. The knee point selection method according to Appendix 4 or 5.

(Appendix 7) A reception unit that accepts input of multiple non-inferior answers about an optimization problem using multiple objective functions, and
For each of the plurality of non-inferior answers, the process of giving height information based on a specific direction set on the multidimensional space with the plurality of objective functions as coordinate axes is repeatedly executed while changing the weight for the non-inferior answers. By doing so, a calculation unit that calculates the number of times that the height information becomes the minimum for each non-inferior answer,
A knee point selection device comprising a selection unit for selecting a non-inferior answer to be a knee point based on the calculated number of times.

(Appendix 8) The calculation unit sorts a plurality of non-inferior answers based on the number of times the height information becomes the minimum, and among the sorted multiple non-inferior answers, the number of times the height information becomes the minimum is the highest non-inferior answer. The knee point selection device according to Appendix 7, wherein the inferior answer is selected as the knee point.

(Appendix 9) The calculation unit is characterized in that the height information for the non-inferior answer is calculated by summing the values obtained by multiplying the values of a plurality of objective functions included in the non-inferior answer by a weight. 7. The knee point selection device according to 7.

100 Knee point selection device 110 Communication unit 120 Input unit 130 Display unit 140 Storage unit 141 Non-inferior solution set information 142 Weight set information 143 Mapper parameter 144 Undirected graph information 145 Directed graph information 146 Minimal number of times table 150 Control unit 151 Reception unit 152 Weight Generation unit 153 Calculation unit 154 Selection unit 155 Output unit

Claims (4)

Accepts multiple non-inferior inputs for optimization problems using multiple objective functions,
For each of the plurality of non-inferior answers, height information based on a specific direction set in a multidimensional space having the plurality of objective functions as coordinate axes, and the values of the plurality of objective functions included in the non-inferior answers. By repeatedly executing the process of giving the height information, which is the sum of the values obtained by multiplying each of the different weights, while changing the weight for the non-inferior answer, the height information is minimized for each non-inferior answer. Calculate the number of times
A knee point selection program characterized by causing a computer to execute a process of selecting a non-inferior answer to be a knee point based on the calculated number of times. The process of selecting the non-inferior answer that is the knee point sorts a plurality of non-inferior answers based on the number of times that the height information becomes the minimum, and becomes the minimum among the sorted non-inferior answers. The knee point selection program according to claim 1, wherein a non-inferior answer having a higher number of times is selected as the knee point. This is a knee point selection method performed by a computer.
Accepts multiple non-inferior inputs for optimization problems using multiple objective functions,
For each of the plurality of non-inferior answers, height information based on a specific direction set in a multidimensional space having the plurality of objective functions as coordinate axes, and the values of the plurality of objective functions included in the non-inferior answers. By repeatedly executing the process of giving the height information, which is the sum of the values obtained by multiplying each of the different weights, while changing the weight for the non-inferior answer, the height information is minimized for each non-inferior answer. Calculate the number of times
A knee point selection method characterized by executing a process of selecting a non-inferior answer to be a knee point based on the calculated number of times. A reception unit that accepts multiple non-inferior answers about optimization problems using multiple objective functions,
For each of the plurality of non-inferior answers, height information based on a specific direction set in a multidimensional space having the plurality of objective functions as coordinate axes, and the values of the plurality of objective functions included in the non-inferior answers. By repeatedly executing the process of giving the height information, which is the sum of the values obtained by multiplying each of the different weights, while changing the weight for the non-inferior answer, the height information is minimized for each non-inferior answer. A calculation unit that calculates the number of times
A knee point selection device comprising a selection unit for selecting a non-inferior answer to be a knee point based on the calculated number of times.

Images