JP2005285090A - Multiobjective optimization apparatus, method, and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a multiobjective optimization apparatus, method, and program for making it possible to obtain a diversified Pareto-optimum individual in a short time even if an optimization target has uncertainty. <P>SOLUTION: A multiobjective evolutionary algorithm unit 2 feeds a set of parameters of an individual to a search history storage device 31 in a fitness estimating unit 3 and to an optimization target 6. The optimization target 6 outputs a set of sampled values of fitnesses on the basis of the set of parameters of the individual. The search history storage device 31 stores the set of parameters of the individual and a set of sampled values as a search history. A fitness estimating module 30 computes a set of estimated values of true fitnesses on the basis of the search history stored in the search history storage device for output to the multiobjective evolutionary algorithm unit 2. The multiobjective evolutionary algorithm unit 2 determines a Pareto-optimal population in accordance with a genetic algorithm on the basis of a plurality of sets of estimated values. <P>COPYRIGHT: (C)2006,JPO&NCIPI

Description

  The present invention relates to a multi-objective optimization device, a multi-objective optimization method, and a multi-objective optimization program that optimize parameters to be optimized.

  Conventionally, there is a problem class called a multi-objective optimization problem. For example, when considering the problem of minimizing the cost of a product and maximizing performance, this becomes a multi-objective optimization problem of two objective functions. In this case, cost and performance are two objective functions. Generally, there is not a single solution for the multi-objective optimization problem because there is a trade-off relationship that lowering the cost degrades the performance and increasing the performance increases the cost.

FIG. 36 is a diagram showing an example in which the multi-objective optimization problem is applied to engine optimization. When the multi-objective optimization problem is applied to engine fuel efficiency and torque optimization, the fuel efficiency and torque are two objective functions f ₁ and f ₂ . In this case, the values of the objective functions f ₁ and f ₂ are optimized by adjusting parameters such as the fuel injection amount and the ignition timing.

  The solution A has better fuel efficiency than the solution B, but the torque is inferior to the solution B. As described above, since the engine fuel efficiency and the engine torque have a trade-off relationship, there are a plurality of optimum solutions. The user can select a solution suitable for the purpose from a plurality of optimum solutions. For example, the solution A is selected for an engine used for a motorcycle suitable for sports driving, and the solution B is selected for an engine used for a motorcycle suitable for long touring.

  In general, the multi-objective optimization problem is defined as a problem of minimizing the values of M objective functions for N parameters within the range of the constraint condition of each parameter. When maximizing the value of the objective function, a negative sign is added to the objective function to convert it into a problem that minimizes the value of the objective function.

  Such a multi-objective optimization problem generally does not have a single optimal solution, but has an optimal solution set defined by a concept called a Pareto optimal solution. Here, the Pareto optimal solution is a solution in which the value of at least one other objective function must be altered in order to improve the value of a certain objective function, and is defined as follows: (For example, refer nonpatent literature 1).

[Definition 1] For two solutions x1, x2εF of p objective functions f _k (k = 1,..., P), f _k (x1) ≦ f _k (x2) (∀k = 1 ,..., P) ∧f _k (x1) <f _k (x2) (∃k = 1,..., P), x1 is said to dominate x2. Here, F is a set of solutions.

  [Definition 2] When a solution x0 dominates all other solutions xεF, x0 is an optimal solution.

  [Definition 3] When there is no solution xεF superior to a solution x0, x0 is a Pareto optimal solution (or non-inferior solution).

  Obtaining the Pareto optimal solution set results in obtaining an optimal solution set with respect to the objective function trade-off.

FIG. 37 is a diagram for explaining the Pareto optimal solution. FIG. 37 shows an example of _two objective functions f ₁ and f ₂ . The value f ₁ of the objective function f ₁ for solution a (a) the value f ₁ of the objective function f ₁ for solutions b (b) less than, the value f ₂ of the objective function f ₂ for Solution a (a) Is smaller than the value f ₂ (b) of the objective function f ₂ for the solution b. Therefore, the solution a is superior to the solution b.

  Similarly, the solution a dominates the solutions c and d. There is no solution superior to solution a. Similarly, there is no solution superior to the solutions e and f. Accordingly, the solutions a, e, and f are Pareto optimal solutions.

  The solution g is a weak Pareto optimal solution. The weak Pareto optimal solution is a Pareto solution that is not superior to the Pareto optimal solution only for a certain objective function. The weak Pareto optimal solution is not a rational solution and is a solution that does not need to be originally obtained.

  Many solutions for multi-objective optimization problems have been proposed. Recently, there has been a multiple objective evolutionary algorithm (MOEAs). The biggest feature of this method is that the Pareto optimal solution set is obtained at a time using the multi-point search of the evolutionary algorithm. The obtained Pareto optimal solution set is used for decision making to find a solution that matches the purpose from among them, or for obtaining knowledge from the shape of the Pareto optimal solution set (Pareto boundary).

  There have been many studies on applying genetic algorithms (GA) as multi-objective optimization problems as evolutionary algorithms. Genetic algorithms are computational methods that mimic the adaptive evolution of organisms. In a genetic algorithm, a solution candidate is called an individual. The objective function is called an adaptive function, and the value of the fitness function is called fitness.

  This genetic algorithm is based on the process of natural evolution (chromosome selection, crossover and mutation) as a hint. This is an algorithm proposed by Holland. The design variable is regarded as a gene, an initial design individual set is randomly generated, and the fitness of each individual is evaluated. Parents are selected so that individuals with better fitness are more likely to be selected as parents. And offspring are created by crossover (gene replacement) and mutation (random change of gene). Furthermore, generations are repeated through evaluation, selection, crossover, and mutation to search for an optimal solution.

  Specifically, Fonseca et al. MOGA (Multiple Objective Genetic Algorithm: see, for example, Non-Patent Document 1), Deb et al. NSGA-II (Non-Dominated Sorting Genetic Algorithm-II: see, for example, Non-Patent Document 2), Zitzler SPEA2 (Strength Pareto Evolutionary Algorithm 2: see, for example, Non-Patent Document 3) has been proposed. In particular, NSGA-II and SPEA2 are known as excellent multi-objective evolutionary algorithms.

  The multi-objective evolutionary algorithm is used as a practical application for the problem of obtaining the wing shape of a supersonic passenger aircraft, optimizing parameters of a vehicle body or an engine, and the like.

In addition, for optimization of the fitness function with uncertainty, MFEGA (Memory-based Fitness Estimation Genetic Algorithm) for estimating the true fitness using the search history has been proposed by Sano, Kita et al. ( For example, refer nonpatent literature 4). Here, in MFEGA, a sample value of the fitness of an individual obtained in the past is stored as a search history, and the true fitness is estimated with reference to the search history. MFEGA has been reported to have an excellent search performance in comparison with a method of sampling the fitness of the same individual multiple times and a normal genetic algorithm regarding a problem with uncertainty.
CMfonseca, pJFlemimg: genetic algorithms for multiobjective optimization: formation, discussion and generalization, of the 5th international conference on genetic algorithms, pp.416-423 (1993) K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan: A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II, KanGAL report 20001, Indian Institute of Technology, Kanpur, India (20OO ) E.Zitzler, M. Laumanns, L. Thiele: SPEA2: Improving the Performance of the Strength Pareto Evolutionary A1gorithm, Technical Report 103, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich (2001) Sano, Kita: Optimization of uncertain function by genetic algorithm using search history, Electrology C, Vol. 122, No. 6, PP-1001-1008 (2002) K.Ikeda, H.Kita, and S.Kobayashi: Failuer of Pareto-Based MOEAs, Does Non-Dominated Really Mean Near to Optimal? Congress on Evolutionary Computation, pp.957-962 (2001) MDBerg, et.al .: Computational Geometry: Algorithms and Applications, Springer-Verlag (1997) Hiroshi Imai, Keiko Imai, Computational Geometry, Information Mathematics Course 12, Kyoritsu Shuppan (1994) E.Zitzler, K.Deb, L, Thiele: Comparison of Mu1tiobjective Evo1utionary Algorithms: Empirical Results, Evolutionary Computation 8 (2), pp.173-195 (2000)

  However, the genetic algorithms proposed in Non-Patent Document 1 to Non-Patent Document 3 can obtain the same solution regardless of how many times they are executed, such as an ideal model that does not include a benchmark problem or a probability element. Applied to simulation. There has not been reported an example in which the above genetic algorithm is applied to a problem in which the fitness of an individual involves noise, that is, a problem with uncertainties, such as a simulation including a real system or a probability element. There are two reasons for this.

  First, since the optimization target is accompanied by noise, the fitness of the individual obtained from the optimization target changes for each individual evaluation, and the evolution does not proceed well. In other words, when the fitness deteriorates due to noise, an individual who should originally be able to obtain a good fitness is deceived. Alternatively, by improving the fitness level due to noise, an individual who would originally be able to obtain a poor fitness level survives. When such a phenomenon occurs, the individual cannot normally evolve.

  Secondly, the shape of the Pareto optimal solution set obtained is unclear. That is, since the obtained fitness is accompanied by noise, a Pareto boundary is not formed when the fitness is plotted on the plane of the fitness function space in the two-objective optimization problem, for example. Therefore, it is difficult to use conventional genetic algorithms for decision making or knowledge acquisition.

  Examples of simulations including real systems and random elements that require multi-objective optimization include optimization of signal switching rules using a traffic flow simulator and optimization of motor control parameters. The purpose of the optimization of the signal switching rule is to successfully switch signals at the intersection of two main roads and the vicinity thereof so that neither road causes traffic jams. The purpose of optimizing motor control parameters is to achieve both improvement of motor responsiveness and reduction of overshoot.

  However, in the case of a traffic flow simulator, the speed and number of vehicles to be passed are randomly given. In the case of a motor, the measurement error of the sensor occurs, so the same individual (that is, the rule and the control parameter) Even if the fitness is calculated by using the same, a different fitness is obtained each time. Therefore, the above two problems occur.

Such a problem with uncertainty is a very difficult problem not only for multi-objective optimization but also for single-objective optimization. In the evolutionary calculation method, several methods for statistically processing noise have been proposed. The most common method is to sample an individual multiple times. In this method, if the number of samplings is n, the noise variance can be reduced to n ^−0.5 . However, this method is not preferable because the evaluation time is n times in the optimization of a time-consuming real system or large-scale simulation.

  Further, MFEGA proposed in Non-Patent Document 4 exhibits excellent search performance for a single-objective optimization problem, but its application to a multi-objective optimization problem has not been sufficiently studied.

  An object of the present invention is to provide a multi-objective optimization apparatus, a multi-objective optimization method, and a multi-objective optimization program capable of obtaining appropriate Pareto optimal individuals having diversity in a short time even when the optimization target is accompanied by uncertainty. Is to provide.

  (1) The multi-objective optimization apparatus according to the first invention provides a set of individual parameters to the optimization target, and optimizes a set of fitness sample values for a plurality of fitness functions corresponding to a plurality of objectives. A multi-objective optimization device received from a target, which stores a set of individual parameters and a set of fitness sample values output from the optimization target, and corresponds to a plurality of individuals stored in the storage unit An estimation unit that obtains a set of true fitness estimation values corresponding to the target individual based on a plurality of sets of sample values, a new individual is generated based on the estimation value obtained by the estimation unit, and the generated individual Pareto parameters are given to the optimization target and storage unit, and the evaluation individual set is evaluated according to the multi-objective evolutionary algorithm based on the multiple sets of estimation values obtained by the estimation unit. A calculation unit for obtaining an individual set, the estimation unit weights a set of sample values corresponding to each individual stored in the storage unit, and obtains a linear sum of a plurality of sets of weighted sample values, A set of fitness estimates corresponding to the individual of interest is obtained, and the weight of each individual is a function including the distance between the individual of interest and the individual on the parameter space. Comparing the superiority or inferiority of the estimated values corresponding to multiple individuals of the evaluation individual set, weighting the comparison results for each of the multiple fitness functions, and comparing the multiple comparison results weighted for the multiple fitness functions Ranks multiple individuals in the evaluation individual set based on the linear sum, and creates a new one based on the distribution index that represents the degree of sparseness in the distribution of the highest rank individual in the evaluation individual set on the fitness function space And generates an individual.

  In the multi-objective optimization apparatus, a set of individual parameters and a set of fitness sample values output from the optimization target are stored in the storage unit. Based on a plurality of sets of sample values corresponding to a plurality of individuals stored in the storage unit, a set of true fitness estimation values corresponding to the target individual is obtained by the estimation unit. A new individual is generated by the calculation unit based on the estimated value, and a set of parameters of the generated individual is given to the optimization target and the storage unit. In addition, the evaluation individual set is evaluated by the calculation unit according to the multi-objective evolution type algorithm based on the obtained plural sets of estimated values. Thereby, the Pareto optimal individual set is obtained.

  In this case, a set of sample values corresponding to each individual stored in the storage unit is weighted, and a linear sum of a plurality of sets of weighted sample values is obtained to estimate fitness corresponding to the target individual. A set of values is determined.

  Since the weight of each individual is a function including the distance between the target individual and the individual in the parameter space, an estimated value with a sufficiently small error from the true fitness can be obtained. Therefore, even when the sample value output from the optimization target has uncertainty, an appropriate Pareto optimal individual set can be obtained.

  In addition, for each of the plurality of fitness functions, the superiority and inferiority of the estimated values corresponding to the plurality of individuals in the evaluation individual set are compared, and the comparison result for each of the plurality of fitness functions is weighted. The plurality of individuals in the evaluation individual set are ranked based on the linear sum of the plurality of comparison results weighted for the plurality of fitness functions.

  Thereby, a weak Pareto optimal individual can be deceived. Further, when the fitness sample value includes noise due to the uncertainty of the optimization target, it is prevented that the weak Pareto optimal individual is determined as the Pareto optimal individual. Therefore, even when the optimization target has uncertainty, it is possible to obtain a rational Pareto optimal individual considering the relationship between a plurality of fitness levels.

  Furthermore, in the distribution of individuals of the highest rank in the fitness function space, new individuals are generated based on the distribution index representing the degree of sparseness. As a result, individuals can be easily generated without a bias in a wide range on the fitness function space. Therefore, Pareto optimal individuals having diversity can be obtained in a short time.

(2) The estimation unit sets a plurality of individuals stored in the storage unit as h _l , sets a set of sample values corresponding to the target individual x as F (x), and is separated from the target individual by a distance d _l in the parameter space When a set of sample values corresponding to an individual is F (h _l ), k ′ is a coefficient, l = 1,..., H, and n is a natural number,

  A set f ′ (x) of estimated values of true fitness corresponding to the target individual x may be calculated using the estimation formula represented by:

  In this case, an estimated value with a smaller error from the true fitness can be obtained in consideration of the distance between the target individual and other individuals on the parameter space.

  (3) n may be 1. In this case, in calculating the estimated value, the influence of other individuals far away from the target individual in the parameter space is reduced. Thereby, an estimated value with a sufficiently small error from the true fitness can be obtained.

  (4) n may be 3. In this case, in the calculation of the estimated value, the influence of other individuals far away from the target individual in the parameter space is greatly reduced. Thereby, it is possible to obtain an estimated value with a sufficiently small error from the true fitness.

(5) The computing unit calculates fitness estimates corresponding to the individuals x1 and x2 for one fitness function among the p fitness functions corresponding to the p objectives, f _k (x1) and f _k. (X2), the estimated fitness values corresponding to individuals x1 and x2 for the other fitness functions among the p fitness functions are f _j (x1) and f _j (x2), and k and j are ,..., P, k is different from j, α _kj is a weight, and g _k (x1, x2) expressed by the following equation is g _k for all k = 1 _,. It is determined that the individual x1 is superior to the individual x2 when (x1, x2) ≦ 0 is satisfied and g _k (x1, x2) <0 is satisfied with respect to at least one of k = 1,. May be.

  (6) When a plurality of objectives are two or more m objectives, the distribution index is a single size formed by m individuals adjacent to the individual of interest on the fitness function space corresponding to the m objectives. The calculation unit may select an individual having the highest degree of sparseness based on the size of a single unit, and generate a new individual using the selected individual.

  In this case, in the distribution of individuals with the highest rank in the fitness function space, it becomes possible to easily generate new individuals in a region where the individuals are sparse based on the distribution index. Thereby, a highly diverse Pareto optimal individual can be easily obtained.

  (7) When a plurality of objectives are two objectives, the size of a single object is represented by the length of a straight line connecting two individuals adjacent to the target individual in the fitness function space, and the plurality of objectives are three objectives. In this case, the size of a single unit is represented by the area of a triangle having apexes of three individuals adjacent to the target individual in the fitness function space. It may be represented by the volume of a triangular pyramid having four individuals adjacent to the target individual on the function space.

  In this case, an area where individuals are sparse in the distribution of individuals of the highest rank can be easily determined according to the target number.

  (8) When a plurality of objectives are 4 or more m objectives, the size of a single is the bottom (m−1) dimensional area of a single formed by m individuals adjacent to the target individual in the fitness function space X It may be expressed by height / m.

  In this case, an area where individuals are sparse in the distribution of individuals of the highest rank can be easily determined according to the target number.

  (9) When a plurality of purposes are three or more purposes, the simple substance may be formed by Delaunay triangulation. In this case, the size of a single unit that is a distribution index can be easily calculated.

  (10) When the generated new individual is different from the individual in the evaluation individual set, the calculation unit may replace the new individual with a lower rank individual in the evaluation individual set.

  In this case, in the initial stage of searching for the Pareto optimal individual, bad individuals can be gradually decreased, and in the latter stage of searching for the Pareto optimal individual, diversity of the Pareto optimal individual can be maintained.

  (11) The arithmetic unit may give the lowest rank to the new individual when the generated new individual overlaps with the individual in the evaluation individual set.

  In this case, in the initial stage of searching for the Pareto optimal individual, bad individuals can be gradually decreased, and in the latter stage of searching for the Pareto optimal individual, diversity of the Pareto optimal individual can be maintained.

  (12) The calculation unit may evaluate each individual of the evaluation individual set once. In this case, since the individual is not re-evaluated, the optimization time can be shortened even when it takes time to evaluate one individual as in an actual system or a large-scale simulation.

  (13) The estimation unit may end the storage of the set of sample values output from the optimization target when the amount of the set of sample values stored in the storage unit reaches a predetermined storage capacity.

  In this case, a set of fitness estimation values is obtained using a set of sample values of a predetermined amount stored in the storage unit. Thereby, the optimization time can be shortened.

  (14) The computing unit may display the Pareto optimal individual based on the set of estimated values obtained by the estimating unit.

  In this case, since the user can visually recognize the Pareto optimal individual, various decision making can be easily performed.

  (15) The calculation unit may evaluate individuals in the evaluation individual set using a genetic algorithm as a multi-purpose evolutionary algorithm.

  In this case, an optimal Pareto optimal individual can be easily obtained by performing generation change based on a genetic algorithm.

  (16) The optimization target includes an evaluation system for evaluating a plurality of performances of the device, the set of parameters includes a set of control parameters for the evaluation system, and the plurality of fitness functions are included in the evaluation system. It is a plurality of performances obtained by evaluation, and the fitness set may be a plurality of performance values.

  In this case, a set of control parameters is given to the evaluation system. The evaluation system evaluates the performance of the device based on the set of control parameters, and outputs a set of sample values corresponding to a plurality of performances. According to this multi-objective optimization device, even when the evaluation system involves uncertainty, a set of appropriate control parameter sets having diversity can be obtained as Pareto optimal individuals in a short time.

  (17) The device may be an engine. In this case, a set of engine control parameters is given to the evaluation system. The evaluation system evaluates engine performance based on a set of engine control parameters, and outputs a set of sample values corresponding to a plurality of performances. According to this multi-objective optimization apparatus, even when the evaluation system involves uncertainty, a set of appropriate engine control parameter sets having diversity can be obtained in a short time as Pareto optimal individuals.

  (18) The device may be a motor. In this case, a set of motor control parameters is given to the evaluation system. The evaluation system evaluates the performance of the motor based on the set of motor control parameters, and outputs a set of sample values corresponding to a plurality of performances. According to this multi-objective optimization apparatus, even when the evaluation system involves uncertainty, a set of appropriate motor control parameter sets having diversity can be obtained in a short time as Pareto optimal individuals.

  (19) The evaluation system may be a device evaluation device that controls a device based on a set of parameters and outputs a plurality of performance values generated by the operation of the device as sample values.

  In this case, a set of control parameters is given to the device evaluation apparatus. The device evaluation apparatus evaluates the performance of the device based on the control parameter set, and outputs a set of sample values corresponding to a plurality of performances. According to this multi-objective optimization apparatus, a set of appropriate control parameter sets having diversity can be obtained in a short time as a Pareto optimal individual even when the apparatus evaluation apparatus involves uncertainty.

  (20) The evaluation system may be a device simulator that evaluates a plurality of performances by simulating the operation of the device based on a set of parameters and outputs the evaluated values of the plurality of performances as a set of sample values. Good.

  In this case, a set of control parameters is given to the equipment simulator. A plurality of performances are evaluated by simulating the operation of the device based on the control parameter set by the device simulator, and a set of sample values corresponding to the evaluated plurality of performances is output. According to this multi-objective optimization apparatus, a set of appropriate control parameter sets having diversity can be obtained in a short time as a Pareto optimal individual even when the equipment simulator involves uncertainty.

  (21) In the multi-objective optimization method according to the second invention, a set of individual parameters is given to an optimization target, and the fitness of a plurality of fitness functions corresponding to a plurality of objectives output from the optimization target is determined. A multi-objective optimization method for optimizing a parameter based on a set of sample values, the step of storing a set of individual parameters and a set of fitness sample values output from an optimization target in a storage unit; Obtaining a set of true fitness estimates corresponding to the individual of interest based on a plurality of sets of sample values corresponding to the plurality of individuals stored in the section; and a new individual based on the obtained estimate Generates and sets the generated individual parameter set to the optimization target and storage unit, and evaluates the evaluation individual set according to the multi-objective evolutionary algorithm based on the obtained multiple sets of estimated values A step of obtaining a Pareto optimal individual set, wherein the step of obtaining a set of estimated values weights a set of sample values corresponding to each individual stored in the storage unit, and sets a plurality of weighted sets of samples A step of obtaining a set of fitness estimates corresponding to the individual of interest by obtaining a linear sum of values, and the weight of each individual is a function including the distance between the individual of interest and the individual in the parameter space The step of obtaining the Pareto optimal individual compares the superiority or inferiority of the estimated values corresponding to the plurality of individuals of the evaluation individual set for each of the plurality of fitness functions, and weights the comparison result for each of the plurality of fitness functions. Performing a ranking of a plurality of individuals in an evaluation individual set based on a linear sum of a plurality of comparison results weighted for a plurality of fitness functions; It is intended to include a step of generating a new individual based on distribution index representing the degree of sparse in the individual distribution of the highest ranking of the evaluation population of individuals over the function space.

  In the multi-objective optimization method, a set of individual parameters and a set of fitness sample values output from the optimization target are stored in the storage unit. Based on a plurality of sets of sample values corresponding to a plurality of individuals stored in the storage unit, a set of true fitness estimation values corresponding to the target individual is obtained. A new individual is generated based on the estimated value, and a set of parameters of the generated individual is given to the optimization target and the storage unit. Further, the evaluation individual set is evaluated according to the multi-objective evolutionary algorithm based on the obtained plural sets of estimated values. Thereby, the Pareto optimal individual set is obtained.

  In this case, a set of sample values corresponding to each individual stored in the storage unit is weighted, and a linear sum of a plurality of sets of weighted sample values is obtained to estimate fitness corresponding to the target individual. A set of values is determined.

  Since the weight of each individual is a function including the distance between the target individual and the individual in the parameter space, an estimated value with a sufficiently small error from the true fitness can be obtained. Therefore, even when the sample value output from the optimization target has uncertainty, an appropriate Pareto optimal individual set can be obtained.

  In addition, for each of the plurality of fitness functions, the superiority and inferiority of the estimated values corresponding to the plurality of individuals in the evaluation individual set are compared, and the comparison result for each of the plurality of fitness functions is weighted. The plurality of individuals in the evaluation individual set are ranked based on the linear sum of the plurality of comparison results weighted for the plurality of fitness functions.

  Thereby, a weak Pareto optimal individual can be deceived. Further, when the fitness sample value includes noise due to the uncertainty of the optimization target, it is prevented that the weak Pareto optimal individual is determined as the Pareto optimal individual. Therefore, even when the optimization target has uncertainty, it is possible to obtain a rational Pareto optimal individual considering the relationship between a plurality of fitness levels.

  Furthermore, in the distribution of individuals of the highest rank in the fitness function space, new individuals are generated based on the distribution index representing the degree of sparseness. As a result, individuals can be easily generated without a bias in a wide range on the fitness function space. Therefore, Pareto optimal individuals having diversity can be obtained in a short time.

  (22) A multi-objective optimization program according to a third aspect of the present invention provides a set of individual parameters to an optimization target, and the fitness of a plurality of fitness functions corresponding to the plurality of objectives output from the optimization target A computer-executable multi-objective optimization program that optimizes parameters based on a set of sample values. The storage unit stores a set of individual parameters and a set of fitness sample values output from the optimization target. A process for storing, a process for obtaining a set of estimated values of true fitness corresponding to the target individual based on a plurality of sample values corresponding to the plurality of individuals stored in the storage unit, and A new individual is generated on the basis of this, and a set of parameters of the generated individual is given to the optimization target and the storage unit. The Pareto optimal individual set by performing an evaluation according to a genetic evolution algorithm, and the process of obtaining a set of estimated values weights a set of sample values corresponding to each individual stored in the storage unit. And calculating a set of fitness estimates corresponding to the individual of interest by calculating a linear sum of weighted sample values, and the weight of each individual A function that includes the distance to the individual, and the process of obtaining the Pareto optimal individual compares the superiority or inferiority of the estimated values corresponding to the plurality of individuals of the evaluation individual set for each of the plurality of fitness functions, and the plurality of fitness functions Weighting the comparison results for each of the plurality of individual individuals in the evaluation individual set based on a linear sum of the plurality of comparison results weighted for the plurality of fitness functions. A process of performing a ranking, is intended to include a process of generating a new individual based on distribution index representing the degree of sparse in the individual distribution of the highest ranking of the evaluation population of individuals on the fitness function space.

  In the multi-objective optimization program, a set of individual parameters and a set of fitness sample values output from the optimization target are stored in the storage unit. Based on a plurality of sets of sample values corresponding to a plurality of individuals stored in the storage unit, a set of true fitness estimation values corresponding to the target individual is obtained. A new individual is generated based on the estimated value, and a set of parameters of the generated individual is given to the optimization target and the storage unit. Further, the evaluation individual set is evaluated according to the multi-objective evolutionary algorithm based on the obtained plural sets of estimated values. Thereby, the Pareto optimal individual set is obtained.

  In this case, a set of sample values corresponding to each individual stored in the storage unit is weighted, and a linear sum of a plurality of sets of weighted sample values is obtained to estimate fitness corresponding to the target individual. A set of values is determined.

  Since the weight of each individual is a function including the distance between the target individual and the individual in the parameter space, an estimated value with a sufficiently small error from the true fitness can be obtained. Therefore, even when the sample value output from the optimization target has uncertainty, an appropriate Pareto optimal individual set can be obtained.

  In addition, for each of the plurality of fitness functions, the superiority and inferiority of the estimated values corresponding to the plurality of individuals in the evaluation individual set are compared, and the comparison result for each of the plurality of fitness functions is weighted. The plurality of individuals in the evaluation individual set are ranked based on the linear sum of the plurality of comparison results weighted for the plurality of fitness functions.

  Thereby, a weak Pareto optimal individual can be deceived. Further, when the fitness sample value includes noise due to the uncertainty of the optimization target, it is prevented that the weak Pareto optimal individual is determined as the Pareto optimal individual. Therefore, even when the optimization target has uncertainty, it is possible to obtain a rational Pareto optimal individual considering the relationship between a plurality of fitness levels.

  Furthermore, in the distribution of individuals of the highest rank in the fitness function space, new individuals are generated based on the distribution index representing the degree of sparseness. As a result, individuals can be easily generated without a bias in a wide range on the fitness function space. Therefore, Pareto optimal individuals having diversity can be obtained in a short time.

  According to the present invention, it is possible to obtain an appropriate Pareto optimal individual having diversity in a short time even when the optimization target involves uncertainty.

(1) First Embodiment First, a multi-objective optimization apparatus according to a first embodiment of the present invention will be described with reference to FIG.

(A) Functional Configuration of Multi-Objective Optimization Device FIG. 1 is a block diagram showing a functional configuration of the multi-purpose optimization device according to the first embodiment of the present invention.

  The multi-objective optimization apparatus 1 in FIG. 1 calculates a Pareto optimal individual set of a multi-objective optimization problem using a multi-objective genetic algorithm (GA) as a multi-objective evolutionary algorithm. This multi-objective optimization apparatus 1 is connected to an optimization target 6.

  The optimization target 6 is an evaluation system that evaluates the performance of the device. The evaluation system is an evaluation device for evaluating an actual system or a simulator including a probability element. The actual system is, for example, an engine or a motor, and the evaluation device is, for example, an engine evaluation device or a motor evaluation device. The simulator is, for example, an engine simulator or a motor simulator. In the present embodiment, the optimization target 6 is an engine evaluation device.

  The multi-objective optimization apparatus 1 includes a multi-objective evolution type algorithm unit 2, a fitness estimation unit 3, an output interface 4 and an input interface 5. The fitness level estimation unit 3 includes a fitness level estimation module 30 and a search history storage device 31.

  The fitness estimation module 30 of the multi-objective evolution type algorithm unit 2 and the fitness estimation unit 3 is realized by a CPU 101 (FIG. 2) described later executing a multi-objective optimization program. The search history storage device 31 is configured by an external storage device 106 (FIG. 2) described later.

The user 10 sets a plurality of fitness functions (objective functions) in the multipurpose evolution type algorithm unit 2. In the present embodiment, the plurality of fitness functions include fuel consumption, torque, and concentrations of components such as CO (carbon monoxide), HC (hydrocarbon), and NO _x (nitrogen oxide) contained in engine exhaust gas. Etc. are set.

Here, the trade-off relationship includes torque and fuel consumption, torque and CO concentration, torque and HC concentration, fuel consumption and NO _x concentration, CO concentration and NO _x concentration, HC concentration and NO _x concentration, and the like.

  An individual of the multi-objective genetic algorithm is a candidate for a solution of the multi-objective optimization problem, and has a plurality of parameter sets and a plurality of fitness values. A parameter is an adjustable value and is called a gene in the genetic algorithm. The parameters include fuel injection amount, fuel injection timing, ignition timing, throttle opening, and the like. The fitness is a value of the fitness function. Hereinafter, an individual of a multipurpose genetic algorithm is simply referred to as an individual.

  The multi-objective evolution type algorithm unit 2 receives an estimate value of the true fitness calculated by the fitness estimation module 30 described later, and gives a set of individual parameters to the search history storage device 31 of the fitness estimation unit 3 and outputs it. This is given to the optimization object 6 via the interface 4.

  The optimization target 6 outputs a set of fitness sample values based on the set of individual parameters given from the multipurpose optimization apparatus 1. Each sample value output from the optimization target 6 includes a true fitness and a noise component, as will be described later. Details of the sample value will be described later.

  A set of sample values output from the optimization target 6 is input to the search history storage device 31 of the fitness estimation unit 3 via the input interface 5. The search history storage device 31 stores a set of individual parameters and a set of sample values as a search history. Hereinafter, each set of individual parameters and sample values included in the search history is referred to as history data.

  The fitness estimation module 30 calculates a set of true fitness estimates based on the history data of the search history stored in the search history storage device 31 and provides the set of estimates to the multi-objective evolution algorithm unit 2 . Hereinafter, the true fitness estimate is simply referred to as fitness estimate or estimate.

  The multi-objective evolution type algorithm unit 2 generates a plurality of individuals according to a genetic algorithm based on a plurality of sets of estimated values, performs a multipoint search, and evaluates the fitness function with the Pareto optimality, whereby the Pareto optimal individual Find a set at the same time. Further, the multi-objective evolution type algorithm unit 2 presents the obtained Pareto optimal individual set to the user 10.

  As described above, the multi-objective evolution type algorithm unit 2 and the fitness level estimation unit 3 optimize the parameters of the individual by working together.

  Detailed operations of the multi-objective evolution algorithm unit 2 and the fitness estimation unit 3 will be described later.

(B) Hardware configuration of multipurpose optimization apparatus FIG. 2 is a block diagram showing a hardware configuration of the multipurpose optimization apparatus 1 of FIG.

  The multi-objective optimization apparatus 1 includes a CPU (Central Processing Unit) 101, a ROM (Read Only Memory) 102, a RAM (Random Access Memory) 103, an input device 104, a display device 105, an external storage device 106, and a recording medium driving device 107. And an input / output interface 108.

  The input device 104 includes a keyboard, a mouse, and the like, and is used for inputting various commands and various data. The ROM 102 stores a system program. The recording medium driving device 107 includes a CD (compact disk) drive, a DVD (digital versatile disk) drive, a flexible disk drive, and the like, and reads / writes data from / to a recording medium 109 such as a CD, DVD, or flexible disk.

  A multipurpose optimization program is recorded on the recording medium 109. The external storage device 106 includes a hard disk device or the like, and stores a multipurpose optimization program and various data read from the recording medium 109 via the recording medium driving device 107. The CPU 101 executes the multipurpose optimization program stored in the external storage device 106 on the RAM 103.

  The display device 105 includes a liquid crystal display panel, a CRT (cathode ray tube), and the like, and displays various images such as a Pareto optimal individual set. The input / output interface 108 includes the output interface 4 and the input interface 5 of FIG. The optimization target 6 is connected to the input / output interface 108 by wireless communication or wired communication. The input / output interface 108 transfers a set of sample values output from the optimization target 6 to the external storage device 106 and provides the optimization target 6 with a set of individual parameters generated by the multi-objective optimization program.

  As the recording medium 109 for recording the multipurpose optimization program, various recording media such as a semiconductor memory such as a ROM and a hard disk can be used. Alternatively, the multipurpose optimization program may be downloaded to the external storage device 106 via a communication medium such as a communication line and executed on the RAM 103.

  Here, as long as the recording medium 109 is a computer-readable recording medium, the recording medium 109 includes an electronic reading method, a magnetic reading method, an optical reading method, or any other reading method. For example, in addition to the above-mentioned CD, DVD and flexible disk, optical reading type recording medium such as CDV (compact disk video), semiconductor recording medium such as RAM and ROM, magnetic recording type recording medium such as hard disk, MO (magneto-optical) A magnetic storage type / optical reading type recording medium such as a disk) can be used.

(C) Configuration of Optimization Target FIG. 3 is a block diagram showing an example of the configuration of the optimization target 6. The optimization target 6 in FIG. 3 is an engine evaluation device.

  The optimization target 6 includes an engine 61, an ECU (engine control unit) 62, an exhaust gas analyzer 63, a controller 64, a throttle unit 65, and a dynamo 66.

  The ECU 62 receives a set of parameters from the multipurpose optimization device 1 by serial communication. In this example, the set of parameters is an ignition timing and a fuel injection timing. The ECU 62 controls the ignition timing and fuel injection timing of the engine 61 based on the parameter set. Engine information such as the rotational speed and the air-fuel ratio is given from the engine 61 to the controller 64.

  The controller 64 controls the throttle unit 65 and the dynamo 66 based on the engine information. The throttle unit 65 controls the output torque of the engine 61 by adjusting the intake air amount of the engine 61. The dynamo 66 controls the load torque.

The exhaust gas analyzer 63 analyzes the components in the exhaust gas from the engine 61 and outputs the HC concentration and the NO _x concentration as a set of sample values to the multipurpose optimization apparatus 1 by serial communication.

FIG. 4 is a graph showing the relationship between the HC concentration, NO _x concentration, CO concentration and air-fuel ratio.

If the fuel burns completely, the exhaust gas contains carbon dioxide and water. However, when the operating state changes, the combustion state also changes, and the exhaust gas contains CO, HC, and NO _x .

As shown in FIG. 4, when the air-fuel ratio is small, the HC concentration and the NO _x concentration are lowered. Concentration of NO _x is becomes maximum when the air-fuel ratio is slightly smaller than the stoichiometric air-fuel ratio (14.7), it decreases in the other region. In the vicinity of the theoretical air-fuel ratio, the HC concentration and the NO _x concentration have a trade-off relationship, and the CO concentration and the NO _x concentration have a trade-off relationship.

The optimization target 6 in FIG. 3 receives the ignition timing and the fuel injection timing as a set of individual parameters from the multi-purpose optimization device 1, and outputs the HC concentration and the NO _x concentration as a set of sample values.

(D) Overall Processing of Multipurpose Optimization Device FIGS. 5 and 6 are flowcharts showing the overall processing of the multipurpose optimization device 1 of FIG.

  As shown in FIG. 5, when the optimization process is started, the multi-objective evolution type algorithm unit 2 generates a parent individual set P as an initial individual set within a range determined by each parameter at random. The set P is initialized, and a set of parameters of each individual of the generated parent individual set P is sequentially given to the optimization target 6 (step S1). Thereby, a set of fitness sample values is sequentially output from the optimization target 6.

  When there is a Pareto optimal individual known as prior knowledge, the Pareto optimal individual may be used as part of the initial individual set. Thereby, the convergence of the search for the Pareto optimal individual can be expected to be improved.

  The search history storage device 31 of the fitness estimator 3 acquires a set of sample values corresponding to each individual of the parent individual set P from the optimization target 6, and sets a set of parameters and a sample value of the parent individual set P. The search history is stored (step S2).

  Next, the fitness estimation module 30 of the fitness estimator 3 estimates the fitness of each individual in the parent individual set P based on a set of sample values corresponding to a plurality of individuals stored in the search history storage device 31. A set of values is calculated (step S3). A method for calculating the fitness value will be described later.

  Next, the multi-objective evolution type algorithm unit 2 divides the parent individual set P into individual sets for each rank by superiority comparison and Pareto ranking based on the fitness value set (step S4). The Pareto ranking will be described later.

  Next, the multi-purpose evolution type algorithm unit 2 performs the congestion degree sort on the individual sets of each rank of the parent individual set P (step S5). Thereby, the individuals of each rank are arranged in descending order of the degree of congestion (congestion distance). The congestion degree sorting will be described later. Then, a predetermined number of individuals having a higher degree of congestion at a higher rank are selected, and other individuals are deleted.

  Further, the multi-purpose evolution type algorithm unit 2 selects three specific parent individuals from the individual set of the highest rank (rank 1) of the parent individual set P, and performs a crossover operation on the three parent individuals, thereby performing child operations. A set C is generated, and a set of parameters of each individual of the generated child individual set C is sequentially given to the optimization target 6 (step S6). Thereby, a set of fitness sample values is sequentially output from the optimization target 6.

  Here, the crossover operation means generating a new individual by multiplying the genes of the individual. A method for selecting a specific parent individual will be described later.

  The search history storage device 31 of the fitness estimation unit 3 acquires a set of fitness sample values corresponding to each individual of the child individual set C output from the optimization target 6, and sets a parameter corresponding to each individual. The set of sample values is stored as a search history (step S7).

  Next, the multipurpose evolution type algorithm unit 2 generates an individual set F from the child individual set C and the parent individual set P (step S8).

  The fitness estimation module 30 of the fitness estimation unit 3 calculates a set of fitness estimation values corresponding to each individual of the individual set F based on a plurality of sets of sample values stored in the search history storage device 31 ( Step S9).

  The multi-objective evolution type algorithm unit 2 divides the individual set F into individual sets for each rank by superiority or inferiority comparison based on a set of fitness estimates and Pareto ranking, and overlaps with individuals in the parent individual set P in the child individual set C The lowest rank is assigned to the individual (step S10).

  Next, the multi-purpose evolution type algorithm unit 2 generates a new parent individual set P by performing congestion degree sorting on the individual sets of each rank of the individual set F (step S11). Thereby, the individuals of each rank are arranged in descending order of the degree of congestion (congestion distance). The congestion degree sorting will be described later. Then, a predetermined number of individuals having a higher degree of congestion at a higher rank are selected, and other individuals are deleted.

  Thereafter, the multipurpose evolutionary algorithm unit 2 determines whether or not the number of generations has reached a predetermined end condition (step S12).

  Here, the generation includes a selection step for selecting a parent individual from an individual set, a crossover step for generating a new child individual by a crossover operation, and a generation change step for exchanging the parent individual and the child individual. If it is determined that the number of generations has not reached the predetermined end condition, the process proceeds to step S6. If it is determined that the number of generations has reached a predetermined end condition, the multi-objective evolution algorithm unit 2 presents the parent individual set P generated in step S11 to the user 10 as a Pareto optimal individual set, and performs processing. finish.

(E) Specific Example of Each Process of Multipurpose Optimization Device FIGS. 7 to 12 are schematic diagrams illustrating specific examples of each process of the multipurpose optimization device 1.

7 to 12 show examples of two parameters x ₁ and x ₂ and two fitness functions f ₁ and f ₂ . In the case of the optimization target 6 in FIG. 3, the parameters x ₁ and x ₂ are the ignition timing and the fuel injection timing, and the fitness functions f ₁ and f ₂ are the HC concentration and the NO _x concentration.

(E-1) Initialization of parent individual set FIG. 7 is a schematic diagram showing a parent individual set generated by initialization, (a) shows a parent individual set in the fitness function space, and (b) shows parameters. Indicates the parent individual set in the space. In initialization, as shown in FIG. 7, a plurality of individuals are randomly generated in the fitness function space and the parameter space.

(E-2) Individual Evaluation Method In the multi-objective optimization problem, since individuals have fitness values corresponding to a plurality of fitness functions, it is not possible to compare the superiority or inferiority of individuals with simple values. In the present embodiment, an individual is evaluated using superiority / inferiority comparison, Pareto ranking, and congestion degree sorting described below.

(E-2-1) Superiority comparison In FIG. 5, the superiority comparison in step S4 of FIG. 5 and step S10 of FIG. 6 is demonstrated. For this superiority / inferiority comparison, the following α-domination strategy is used. Details of the α superiority strategy are described in Non-Patent Document 5, for example.

  FIG. 8 is a schematic diagram for explaining the α superiority strategy. Here, in general, α superiority is defined as follows.

G _k (x1, x2) represented by the following equation (8) is obtained for two solutions x1, x2∈F of a certain number of p objective functions f _k (k = 1,..., P). The solution x1 is α superior to the solution x2.

g _k (x1, x2) ≦ 0 (∀k = 1,..., p) ∧g _k (x1, x2) <0 (∃k = 1,..., p)

In the above equation, f _k (x1) and f _j (x1) are the values of the objective functions f _k and f _j corresponding to the solution x1, respectively, and f _k (x2) and f _j (x2) are the solutions x2 respectively. _Are the values of the objective function f _k and f _j corresponding to. In the multi-objective genetic algorithm, the solutions x1 and x2 correspond to individuals, and the objective functions f _k and f _j correspond to fitness functions.

Here, attention is paid to the individual I3 in FIG. According to a general superiority comparison, a region where an individual I3 in a straight line L12 extending parallel from the line L11 and the individual I3 extending parallel to fitness functions f ₁ from the individual I3 in fitness function f ₂ is superior to other individuals Determined. That is, the individual I3 dominates the other individuals I6, I7, and I8 in the region above the straight line L11 and to the right of the straight line L12. Individuals I2 and I4 are not dominated by individual I3.

Individuals I2 is with respect to fitness functions f ₁ is slightly better than the two individual I3, are quite inferior individuals I3 respect fitness function f _2. Individuals I4 is with respect to fitness function f ₂ are slightly better than the two individual I3, are quite inferior individuals I3 respect fitness function f _1. When the fitness of such individuals I2 and I4 has uncertainty (for example, noise), the individuals I2 and I4 may be dominated by the individual I3.

On the other hand, according to the α superiority strategy, the straight line L1 inclined so as to approach the axis of the fitness function f ₁ from the individual I3 and the straight line L2 inclined so as to approach the axis of the fitness function f ₂ from the individual I3. A region where the individual I3 is superior to other individuals is determined. That is, the individual I3 dominates the individuals I2, I4, I6, I7, and I8 in the region above the straight line L1 and to the right of the straight line L2. According to the α superiority / inferiority strategy, the individuals I2 and I4 are excluded from the Pareto optimal individuals.

  In this embodiment, individual superiority or inferiority comparison is performed based on a weighted linear sum of a plurality of fitness estimation values by an α superiority strategy. According to the α superiority strategy, if one fitness level of a certain individual gets worse by 1, the other fitness level becomes α worse. That is, in the superiority / inferiority comparison, superiority or inferiority of one fitness affects the superiority or inferiority of other fitness. As a result, it is possible to obtain a rational solution in consideration of the relationship between a plurality of fitness levels as follows.

  The weak Pareto optimal individual is a solution in which at least one of the fitness values is not superior to other individuals (that is, equal to a Pareto optimal solution having at least one fitness value). Such weak Pareto optimal individuals have optimal solutions for certain fitness functions, but the remaining fitness functions are inferior to Pareto optimal individuals. Therefore, the weak Pareto optimal individual is not a reasonable solution, and is a solution that does not need to be obtained originally. Therefore, by introducing an α superiority strategy, weak Pareto optimal individuals can be deceived.

  Further, when the fitness is accompanied by uncertainty, a phenomenon occurs in which the weak Pareto optimal individual becomes a Pareto optimal individual due to the uncertainty. If a weak Pareto optimal individual is determined to be a Pareto optimal individual due to uncertainty, it will remain in the individual set without being deceived indefinitely, causing a search for the Pareto optimal individual to stagnate. Therefore, by introducing an α superiority strategy, it is possible to deceive such weak Pareto optimal individuals determined as Pareto optimal individuals.

  FIG. 9 is a schematic diagram for explaining individual superiority / inferiority comparison by the α superiority / inferiority strategy.

  In FIG. 9, the individual I3 dominates the individuals I2, I4, I5, I6, and I7, the individual I6 dominates the individual I8, and the individual I7 dominates the individual I8. There is no individual superior to individuals I1, I3, and I5. Therefore, the individuals I1, I3, and I5 are Pareto optimal individuals.

(E-2-2) Pareto Ranking Next, the Pareto ranking in step S4 in FIG. 5 and step S10 in FIG. 6 will be described. FIG. 10 is a diagram for explaining the Pareto ranking. In the Pareto ranking, a Pareto optimal individual set is obtained based on the ranking of each individual.

The rank r (x _i ) of the individual x _i that is superior to the p _i individuals is given by the following equation.

r (x _i ) = 1 + _pi
Here, rank 1 is the highest rank, and ranks of higher numerical values are lower ranks as the numerical values increase.

  In FIG. 10, individuals I1, I3, and I5 are not dominated by other individuals. Therefore, the rank of the individuals I1, I3, and I5 is 1. Individuals I2 and I4 are superior to one individual I3. Therefore, the ranks of the individuals I2 and I4 are 2. Similarly, the rank of the individual I6 is 6, the rank of the individual I7 is 5, and the rank of the individual I8 is 8.

(E-2-3) Congestion degree sort Next, the congestion degree sort in step S5 of FIG. 5 and step S11 of FIG. 6 will be described. FIG. 11 is a schematic diagram for explaining the congestion degree sorting.

  In the congestion degree sort, for each target individual of the same rank, a rectangle whose diagonal is a line connecting two adjacent individuals is assumed, and the total degree of the vertical and horizontal sides of the rectangle is the congestion degree (congestion distance) Represents. The smaller the value of the degree of congestion, the more focused the individual is in the crowded area. Individuals at both ends of the same rank are given maximum congestion.

  In FIG. 11, the degree of congestion of the individual I3 is represented by the sum of the vertical and horizontal sides of the rectangle s1 formed by the adjacent individuals I1 and I5. The degree of congestion of the individual I1 is represented by the sum of the vertical and horizontal sides of the rectangle s2 created by the adjacent individuals I9 and I3. The congestion degree of the individual I5 is represented by the sum of the vertical and horizontal sides of the rectangle s3 formed by the adjacent individuals I3 and I10.

  FIG. 12 is a flowchart showing the congestion degree sorting process by the multipurpose evolutionary algorithm unit 2.

  First, the multipurpose evolutionary algorithm unit 2 sorts the individual set for each fitness function, and examines two individuals adjacent to each target individual within the same rank for each fitness function (step S31).

  Next, the multi-objective evolution type algorithm unit 2 calculates a mathematical distance between two individuals adjacent to each target individual for each fitness function, and sums the mathematical distances in a plurality of fitness functions for each target individual. Is calculated as the degree of congestion (step S32). Here, the Euclidean distance is used as the mathematical distance.

  Thereafter, the multi-purpose evolutionary algorithm unit 2 sorts the individuals in the individual set of each rank in descending order of the value of the degree of congestion (step S33).

(E-3) Calculation of Estimated Value Based on Search History Next, calculation of the estimated value in step S3 in FIG. 5 and step S9 in FIG. 6 will be described.

  FIG. 13 is a schematic diagram for explaining calculation of an estimated value by the fitness estimation module 30 of the fitness estimation unit 3.

In the search history storage device 31 of FIG. 1, a set of individual parameters given from the multi-objective evolution type algorithm unit 2 and a set of fitness sample values output from the optimization target 6 are sequentially stored as a search history HS. . In FIG. 13, a set of parameters x ₁ and x _{2 and} a set of sample values F ₁ and F ₂ are stored as a search history HS for each individual.

  The fitness estimation module 30 calculates the true fitness corresponding to each individual as an estimated value based on the search history HS. A set of parameters and a set of estimated values corresponding to each individual are stored in the search history storage device 31 of FIG.

As shown in FIG. 13, the search history storage device 31 stores a set of parameters x ₁ and x _{2 and} a set of estimated values f ₁ ′ and f ₂ ′ as estimation results E for each individual.

  Further, the fitness estimation module 30 can display the fitness function space and the Pareto optimal individual set on the parameter space on the screen of the display device 105 in FIG. 2 based on the parameter set and the set of estimated values of each individual. it can.

In FIG. 13, the Pareto optimal individual set is displayed on the fitness function space including the fitness functions f ₁ and f ₂ and on the parameter space including the parameters x ₁ and x ₂ . A boundary formed by the Pareto optimal population is called a Pareto boundary.

  Thus, the method of estimating the fitness of an individual using the search history HS stored in the search history storage device 31 is called a memory-based fitness estimated method (MFEM) (non-patent literature). 5).

  When calculating the estimated value of the target individual, the target individual and the individual of the search history HS are generally different search points. In addition, in order to assume an uncertain environment, even if the same parameter set is given to the optimization target 6, a set of different sample values is output. Therefore, in order to calculate the set of estimated values of the individual of interest from the set of sample values of the search history HS, it is necessary to make some assumption on the nature of the fitness function. In MFEM, an uncertain environment is modeled on the assumption that the fitness function varies randomly according to the mathematical distance from the target individual.

  Let x be the target individual, and let f (x) be the true fitness of the target individual x. Consider the fitness f (h) of an individual h that is a distance d away from the target individual x in the parameter space. The expected value of the fitness f (h) is f (x), and a model that follows a normal distribution in which the variance of the fitness f (h) increases in proportion to the distance d is expressed by the following equation (1).

f (h) to N (f (x), kd) (1)
In the above equation (1), k is a positive constant that determines the weight based on distance, and N (f (x), kd) is a probability density function of a normal distribution with an average of f (x) and a variance of kd. Represents.

Here, it is assumed that noise δ according to a normal distribution having an average of 0 and a variance σ _E ² and independent of the position of the individual is added to the true fitness f (x). In this case, the sample value F (x) corresponding to the individual x is defined as follows:

F (x) = f (x) + δ (2)
FIG. 14 is a schematic diagram showing sample values with noise δ according to a normal distribution. Here, the sample value F (x) is a set of the sample value F ₁ (x) for the fitness function f ₁ and the sample value F ₂ (x) for the fitness function f ₂ , and the true fitness f ( x) is the set of true fitness f ₂ (x) of the true fitness f ₁ (x) and fitness function f ₂ for fitness functions f _1. Also, the noise [delta] is the noise [delta] ₂ of the set of the noise [delta] ₁ and a fitness function f ₂ for fitness functions f _1. Noise δ _i (i = 1, 2) is expressed by the following equation.

δ _{i to} N (0, σ _Ei ² ) (i = 1, 2)
In the above equation, N (0, σ _Ei ² ) represents a probability density function of a normal distribution with mean 0 and variance σ _E ² .

  The fitness estimating unit 3 obtains a Pareto optimal individual set that minimizes the expected value of the sample value F (x). At this time, the sample value F (h) corresponding to the individual h is modeled as the following equations (3.1) and (3.2).

F (h) to N (f (x), kd + σ _E ² ) (3.1)
d = | h−x | (3.2)
In the above equation (3.1), N (f (x), kd + σ _E ² ) represents a probability density function of a normal distribution having an average of f (x) and a variance of kd + σ _E ² .

  FIG. 15 is a schematic diagram showing a model of an uncertain fitness function. In this model, it is assumed that the sample value F (h) changes greatly and irregularly as the distance from the target individual x increases.

  Based on this model, an estimated value of the true fitness f (x) is calculated by the maximum likelihood method using the search history HS.

Individuals stored in the search history _{HS h l (l = 1,} ..., H), the distance d _{l (l} = 1 from the sample value F (h _l) and target individuals x individuals h _l to individuals h _l, ... , H), the probability of obtaining sample values F (h ₁ ),..., F (h _H ) can be expressed by the following equation.

Here, p (F (h _l ), d _l ) is a probability density function representing the probability that the sample value F (h _l ) is obtained, and can be represented by the following equation.

Here, k ′ = k / σ _E ² . In the present embodiment, the constant k ′ is obtained by a preliminary experiment. Non-Patent Document 4 proposes a method for estimating a constant k ′ during a search. The constant k ′ may be obtained by the proposed method.

The above equations (4) and (5) are considered as the likelihood of the true fitness f (x), and the maximum likelihood method is used. Thereby, the estimated value f ′ (x) of the true fitness f (x) can be expressed by a weighted average expression weighted by a function including the distance d _l as shown in the following expression (6). .

  FIG. 16 is a flowchart showing an estimated value calculation process by the fitness estimation module 30 of the fitness estimation unit 3.

  First, the fitness estimation module 30 confirms that the parent individual set P has been initialized in the multi-objective evolution type algorithm unit 2 (step S41). Next, the fitness estimation module 30 clears all the search histories HS in the search history storage device 31 (step S42).

  Thereafter, the fitness estimation module 30 stores the set of sample values output from the optimization target 6 in the search history storage device 31 as the search history HS (step S43). Next, the fitness estimation module 30 calculates a set of true fitness estimation values corresponding to each individual from the above equation (6) based on the search history HS of the search history storage device 31 (step S44).

  The fitness estimation module 30 determines whether or not the processing of the multi-objective evolution type algorithm unit 2 has been completed (step S45).

  If the process of the multipurpose evolutionary algorithm unit 2 has not ended, the process returns to step S43 and the processes of steps S43 to S45 are repeated. When the process of the multipurpose evolution type algorithm unit 2 is finished, the calculation process of the estimated value is finished.

(E-4) Method from selection of parent individual to generational change Next, a method from the selection of a specific parent individual in step S6 in FIG. 6 to the generational change in step S11 will be described. FIG. 17 is a schematic diagram for explaining a method from selection of a specific parent individual to generational change.

As shown in FIG. 17A, the parent individual set P is ranked by Pareto ranking. As shown in FIG. 17B, for the rank 1 individual set of the parent individual set P, the Euclidean distance between each two adjacent individuals in the fitness function space is calculated as a distribution index. In the present embodiment, the fitness function space includes two fitness functions f ₁ and f ₂ .

  One of the two individuals Ia and Ib having the maximum Euclidean distance is randomly selected as the first parent individual Ia with probability 1/2. Further, the second parent individual Ic and the third parent individual Id are selected from the parent individual set P by random selection.

  In the present embodiment, the Euclidean distance L of the distribution index is obtained by the following equation, assuming that two adjacent individuals are x and y, as shown in FIG.

L = [{f ₁ (x) −f ₁ (y)} ² + {f ₂ (x) −f ₂ (y)} ² ] ^1/2 (7)
Next, as shown in FIG. 17C, a child individual set C is generated from the first, second and third parent individuals Ia, Ic and Id. Further, as shown in FIG. 17 (d), an individual set F is generated from the child individual set C and the parent individual set P, and the Pareto ranking using the α superiority strategy is performed on the individual set F. At this time, if there is an individual that overlaps the individuals included in the parent individual set P in the child individual set C, the lowest rank is assigned to the individual.

  Thereafter, as shown in FIG. 17E, the degree of congestion is sorted into the individual set F, a predetermined number of individuals are selected based on the rank of the individuals and the degree of congestion within each rank, and the remaining individuals are deleted. Thereby, a new parent individual set P is generated. In this way, generational changes are made.

FIG. 18 is a schematic diagram for explaining the generation process of the child individual set C. FIG. 18A shows a parent individual set P in the parameter space, and FIG. 18B shows a child individual set C in the parameter space. When the parameters x ₁ and x ₂ of the individual I 21 of the child individual set C match the parameters x ₁ and x ₂ of the individual I 11 of the parent individual set P, the lowest rank is assigned to the individual I 21. Similarly, when the parameters x ₁ and x ₂ of the individual I 22 of the child individual set C match the parameters x ₁ and x ₂ of the individual I 12 of the parent individual set P, the lowest rank is assigned to the individual I 22. .

  Note that the method for selecting a specific parent individual is not limited to the present embodiment, and the two individuals having the maximum Euclidean distance L from the rank 1 individual set are selected as the first and second parent individuals. Three parent individuals may be selected from the parent individual set P by a method such as random selection, roulette selection, or tournament selection.

  FIG. 19 is a flowchart showing a process of selecting a specific parent individual by the multipurpose evolution type algorithm unit 2.

  First, the multi-purpose evolutionary algorithm unit 2 sorts the rank-1 individual set selected from the parent individual set P for each fitness function (step S51).

  Next, the multipurpose evolutionary algorithm unit 2 calculates the Euclidean distance between two adjacent individuals in the rank-1 individual set (step S52).

  Furthermore, the multi-objective evolution type algorithm unit 2 randomly selects one of the two individuals giving the maximum Euclidean distance as the first parent individual with a probability of 1/2, and the second parent individual and the third A parent individual is selected from the parent individual set P by random selection (step S53).

  In the present embodiment, a child individual is generated from the first, second, and third parent individuals by a crossover operation. For example, UNDX (Unimodal Normal Distribution Crossover) is used as the crossover operation.

  FIG. 20 is a schematic diagram showing child individual generation processing by UNDX. In UNDX, a child individual C1 is generated in accordance with a normal distribution random number determined based on a positional relationship among the first parent individual P1, the second parent individual P2, and the third parent individual P3. In this case, since the child individual C1 is generated according to the normal distribution around the axis AX connecting the first parent individual P1 and the second parent individual P2, the child individual C1 is the first to third parent individuals P1 to P1. It is not generated at a position far away from P3.

(F) Effects of the First Embodiment In the multi-objective optimization apparatus 1 according to this embodiment, the sample values corresponding to each individual stored in the search history storage device 31 according to the above equation (6) are used. Weighting is performed, and a set of fitness estimated values corresponding to the individual of interest is obtained using a linear sum of a plurality of sets of weighted sample values.

  Since the weight of each individual is a function including the distance between the target individual and the individual in the parameter space, an estimated value with a sufficiently small error from the true fitness can be obtained. Therefore, even when the sample value output from the optimization target has uncertainty, an appropriate Pareto optimal individual set can be obtained.

  Further, the superiority or inferiority of the estimated values corresponding to a plurality of individuals in the individual set is compared for each of the plurality of fitness functions by the α superiority strategy, and the comparison result for each of the plurality of fitness functions is weighted. A plurality of individuals in the individual set are ranked based on a linear sum of a plurality of comparison results weighted with respect to the plurality of fitness functions. Thereby, even when the optimization target has uncertainty, it is possible to obtain a rational Pareto optimal individual considering the relationship between a plurality of fitness levels.

  Further, in the distribution of individuals of the highest rank in the fitness function space, a new child individual can be easily generated in a sparse region by using the distance between adjacent individuals as a distribution index. As a result, individuals with the highest rank can be generated so as to be distributed evenly over a wide area in the fitness function space. Therefore, Pareto optimal individuals having diversity can be easily obtained.

  Furthermore, when the generated new child individual overlaps with an individual in the parent individual set, the lowest rank is assigned to the new child individual. Thereby, bad individuals can be gradually reduced in the initial stage of searching for the Pareto optimal individual, and diversity of the Pareto optimal individual can be maintained in the latter stage of searching for the Pareto optimal individual.

  Further, the Pareto optimal individual is displayed on the screen of the display device 105 based on the set of estimated values calculated by the fitness estimating unit 3. As a result, the user can visually recognize the Pareto optimal individual and can easily make various decisions.

(2) Second Embodiment Next, a multi-objective optimization apparatus according to a second embodiment of the present invention will be described. The multipurpose optimization apparatus according to the present embodiment has the configuration shown in FIGS. Further, the overall processing of the multi-objective optimization apparatus according to the present embodiment is the same as the processing shown in FIGS.

  The present embodiment differs from the first embodiment in the estimated value calculation method in step S3 in FIG. 5 and step S9 in FIG. 6 and the specific parent individual selection method in step S6 in FIG.

(A) Calculation of Estimated Value In the present embodiment, the estimated value f ′ (x) of the true fitness f (x) is calculated by an improved estimation formula.

As shown in the above equation (9), the estimated value f ′ (x) is represented by a weighted average equation weighted by a function including the cube of the distance d _{1 in} the parameter space.

  According to the above equation (9), the shorter the distance from the target individual to the individual in the search history HS, the greater the weight. On the other hand, when the distance from the individual of interest to the individual in the search history HS increases, the weight becomes extremely small. Therefore, an individual away from the target individual hardly contributes to the calculation of the estimated value f ′ (x).

  FIG. 21 is a schematic diagram showing an individual search based on the search history stored in the search history storage device 31. FIG. 21 (a) shows an initial set of individuals in single-objective optimization, FIG. 21 (b) shows an initial set of individuals in multi-objective optimization, and FIG. 21 (c) shows a late search in single-objective optimization. FIG. 21 (d) shows an individual set in the latter half of the search in the multi-objective optimization.

21A and 21C, the vertical axis represents the fitness function f, and the horizontal axis represents the parameter x. In FIGS. 21B and 21D, the vertical axis represents the fitness function f ₂ and the horizontal axis represents the fitness function f ₁ .

  At the beginning of the search, a plurality of individuals are dispersed as shown in FIGS. In the latter half of the search, in single-objective optimization, individuals are concentrated in the vicinity of a certain parameter value as shown in FIG. 21 (c), and in multi-objective optimization, a plurality of individuals are arranged as shown in FIG. 21 (d). Form a Pareto optimal population.

  In this way, in multi-objective optimization, individuals are dispersed over a wide range of the fitness function space. Therefore, the use of equation (9) reduces the contribution of individuals far away from the target individual, so that the accuracy of the estimated value can be reduced. Becomes higher.

(B) Method from Selection of Specific Parent Individual to Generation Change FIG. 22 is a schematic diagram for explaining a method from selection of a parent individual to generation change. In the present embodiment, examples of _three fitness functions f ₁ , f ₂ , and f ₃ are shown.

  As shown in FIG. 22A, the parent individual set P is ranked by Pareto ranking. As shown in FIG. 22B, the area of a triangle formed by each of the three adjacent individuals in the fitness function space is calculated as a distribution index for the rank 1 individual set of the parent individual set P.

  For the formation of the triangle, Delaunay Triangulation is used (see Non-Patent Document 6).

  Here, Delaunay triangulation will be briefly described. Delaunay triangulation is a dual figure of Voronoi Diagram, which is an important concept in computational geometry. Among the triangulation of a point set on a plane (space), it is known as an optimal triangulation in various meanings, and is also used for mesh generation in computer graphics or a finite element method. Delaunay triangulation is a division method for maximizing the minimum angle of a divided triangle, and examples include an algorithm using a sequential addition method, a division rule method, or a geometric transformation. The details of Delaunay triangulation are described in Non-Patent Document 7, for example.

  Any one of the three individuals IA, IB, and IC giving the maximum triangular area is selected at random with a probability of 1/3 as the first parent individual IA. Further, the second parent individual ID and the third parent individual IE are selected from the parent individual set P by random selection.

  Next, as shown in FIG. 22C, a child individual set C is generated from the first, second, and third parent individuals IA, ID, IE. Further, as shown in FIG. 22 (d), an individual set F is generated from the child individual set C and the parent individual set P, and the Pareto ranking using the α superiority strategy is performed on the individual set F. At this time, if there is an individual that overlaps the individuals included in the parent individual set P in the child individual set C, the lowest rank is assigned to the individual.

  Thereafter, as shown in FIG. 22E, the degree of congestion is sorted into the individual set F, a predetermined number of individuals are selected based on the rank of the individuals and the rank within each rank, and the remaining individuals are deleted. Thereby, a new parent individual set P is generated. In this way, generational changes are made.

  Note that the method for selecting a specific parent individual is not limited to the present embodiment, and three individuals giving the largest triangular area may be selected as the first, second and third parent individuals, or Two of the three individuals giving the largest triangular area are selected as the first and second parent individuals, and the third parent individual is selected from the parent individual set P by a method such as random selection, roulette selection or tournament selection. You may choose.

  In addition, when there are three or more parameters, a cross-parent extended crossover method such as UNDX-m may be used.

  FIG. 24 is a flowchart showing a process of selecting a specific parent individual by the multipurpose evolution type algorithm unit 2.

First, multi-objective evolutionary algorithm unit 2 orthogonal projection of an individual set of rank 1 selected from the parent population of individuals P to f _i -f _j plane (step S61). Here, f _i and f _j are fitness functions. i, j = 1, 2, 3 and i ≠ j, and the combination thereof is changed for each generation.

  Next, the multi-objective evolution type algorithm unit 2 performs Delaunay triangulation of the orthogonally projected individual set (step S62).

Further, the multi-objective evolution type algorithm unit 2 gives a component of the fitness function f _k as a height component to the Delaunay triangulated rank 1 individual set, and develops a plurality of triangles in a three-dimensional space (step S63). . Here, k ≠ i, j.

  Next, the multi-objective evolution type algorithm unit 2 calculates the areas of a plurality of triangles developed in the three-dimensional space (step S64).

  One of the three individuals forming the triangle with the largest area is randomly selected as the first parent individual with a probability of 1/3, and two individuals from the parent individual set P are selected as the second parent individual and the third A parent individual is selected by random selection (step S65).

(C) Effects of Second Embodiment In the multi-objective optimization apparatus 1 according to this embodiment, a set of sample values corresponding to each individual stored in the search history storage device 31 by the above equation (9) is used. Weighting is performed, and a set of fitness estimated values corresponding to the individual of interest is obtained using a linear sum of a plurality of sets of weighted sample values.

  Since the weight of each individual is a function including the cube of the distance between the target individual and the individual in the parameter space, the influence of other individuals far away from the target individual in the parameter space is sufficiently small. Thereby, an estimated value with a sufficiently small error from the true fitness can be obtained. Therefore, even when the sample value output from the optimization target has uncertainty, an appropriate Pareto optimal individual set can be obtained.

  In addition, in the distribution of individuals with the highest rank in the fitness function space, a new child individual can be easily generated in a sparse region by using the area of a triangle with three adjacent individuals as vertices as a distribution index. can do. As a result, individuals with the highest rank can be generated so as to be distributed evenly over a wide area in the fitness function space. Therefore, Pareto optimal individuals having diversity can be easily obtained.

(3) Other Embodiments (a) Extended Estimation Formula When the above estimation expressions (4) and (9) are generalized, the following expression is obtained.

  In the above formula (10), n is an arbitrary natural number. The estimation formula (4) of the first embodiment shows a case where n = 1, and the estimation formula (9) of the second embodiment shows a case where n = 3. Although n = 3 is preferable, n may be another natural number.

  Thus, the estimated value of the true fitness of the individual of interest is calculated by the weighted linear sum of the estimated values of other individuals in the search history HS without using the fitness sample value having a noise component. Thereby, even when the sample value has uncertainty, the Pareto optimal individual can be searched stably.

  In addition, since a weight including a function of the nth power of the distance between the target individual and another individual is used in the parameter space, the estimation value is prevented from being greatly influenced by other individuals spreading over a wide range. Therefore, the estimated value can be calculated with high accuracy.

(B) Selection of parent individuals As shown in the first embodiment, in the two-purpose optimization problem, the distance between individuals is used as a distribution index for selecting a specific parent individual. Further, as shown in the second embodiment, in the three-purpose optimization problem, a triangular area formed by three individuals is used as a distribution index for selecting a specific parent individual.

  When the distribution index for selecting a specific parent individual is expanded to an m-objective optimization problem, the distribution index is the size of a simplex formed by m individuals adjacent in the fitness function space. . m is a natural number of 2 or more. The simple substance can be formed by Delaunay triangulation.

  FIG. 24 is a diagram showing a distribution index extended to the m-object optimization problem. As shown in FIG. 24, in the case of two purposes, the distribution index is the length of a straight line connecting two adjacent individuals, and in the case of three purposes, the distribution index has three adjacent individuals as vertices. In the case of four purposes, the distribution index is the volume of a triangular pyramid having four adjacent individuals as vertices. The distribution index is a size of a four-dimensional simple substance, and is calculated by bottom volume × height ÷ 4. In the case of five purposes, the distribution index is the size of a five-dimensional simple substance, and is calculated by the following equation: bottom 4D area × height / 5. In the case of (m + 1) purpose, the distribution index is the size of a single m-dimension, and is calculated from the base (m−1) -dimensional area × height / m.

  In this way, by selecting a specific parent individual based on the distribution index, an active individual search is performed in a region where the distribution is sparse in the fitness function space. Thereby, since an individual is searched in a wide area, an estimated value can be calculated with high accuracy, and a Pareto optimal individual can be found equally in a wide area on the fitness function space.

(C) Application Example to Engine Simulator FIG. 25 is a block diagram showing an example in which the multi-objective optimization device is applied to an engine simulator.

  The optimization target 6a in FIG. 25 is an engine simulator. The engine simulator is composed of a personal computer, for example. The optimization target 6a simulates the operation of the engine based on a set of parameters given from the multipurpose optimization apparatus 1, and outputs a simulation result to the multipurpose optimization apparatus 1 as a set of fitness sample values.

In the present embodiment, the plurality of fitness functions include fuel consumption, torque, and concentrations of components such as CO (carbon monoxide), HC (hydrocarbon), and NO _x (nitrogen oxide) contained in engine exhaust gas. Etc. are set.

  The parameters include fuel injection amount, fuel injection timing, ignition timing, throttle opening, and the like.

  According to the multi-objective optimization apparatus 1 of FIG. 25, the Pareto optimal individual set can be efficiently obtained by setting the fitness function set and the parameter set.

(D) Application Example to Motor Evaluation Device FIG. 26 is a block diagram showing an example in which the multi-objective optimization device is applied to a motor evaluation device.

  The optimization target 6b in FIG. 26 is a motor evaluation device. The motor evaluation device includes a motor, a control circuit, and various detection circuits. The optimization target 6b controls the motor based on a set of individual parameters given from the multi-purpose optimization apparatus 1, measures a plurality of performance items of the motor, and uses the measurement results as a set of fitness sample values. Output to the optimization device 1.

  As the plurality of fitness functions, a plurality of functions such as rise time, settling time, overshoot amount, and current consumption are set.

  The parameters include PID (Proportional Integral Derivative) gain, drive current, and the like.

  Here, the trade-off relationship includes rise time and overshoot amount, rise time and current consumption, settling time and overshoot amount, and the like.

  According to the multi-objective optimization apparatus 1 of FIG. 26, the Pareto optimal individual set can be efficiently obtained by setting the fitness function set and the parameter set.

  It is also possible to perform real-time control of the motor in accordance with the actual environment by calculating the Pareto optimal population in real time.

(E) Application Example to Motor Simulator FIG. 27 is a block diagram showing an example in which the multipurpose optimization device is applied to a motor simulator.

  The optimization target 6c in FIG. 27 is a motor simulator. The motor simulator is composed of a personal computer, for example. The optimization target 6c performs a simulation of motor operation based on a set of parameters given from the multipurpose optimization apparatus 1, and outputs a simulation result to the multipurpose optimization apparatus 1 as a set of fitness sample values.

  As the plurality of fitness functions, a plurality of functions such as rise time, settling time, overshoot amount, and current consumption are set. The parameters include PID gain, drive current, and the like.

  According to the multi-objective optimization apparatus 1 of FIG. 27, the Pareto optimal individual set can be efficiently obtained by setting the fitness function set and the parameter set.

(F) Other examples of multi-objective evolutionary algorithm In the above embodiment, the genetic algorithm (GA) is used as the multi-objective evolutionary algorithm. However, the present invention is not limited to this, and instead of the genetic algorithm, an evolution strategy ( A calculation method based on a similar idea such as ES (Evolution Strategy) may be used.

  Note that calculation methods such as GA and ES are collectively referred to as evolutionary algorithms (EAs) or evolutionary computation (Evolutionary Computation).

(G) Application to four or more objectives In the above-described embodiment, the two-objective and three-objective optimizations have been described as examples. However, the present invention is similarly applied to optimization of four or more objectives. be able to. In this case, four or more fitness functions having a trade-off relationship are set.

(H) Generation change method In step S10 of FIG. 6 described above, a new parent individual set P is obtained by replacing an individual that does not overlap with an individual of the parent individual set P in the child individual set C with an individual lower in the parent individual set P. May be generated.

  In this case, in the initial stage of searching for the Pareto optimal individual, it is possible to reduce the number of bad individuals gradually and maintain the diversity of the Pareto optimal individual in the latter stage of searching for the Pareto optimal individual.

(I) Re-evaluation of parent individual In the above embodiment, the parent individual is re-evaluated. However, if there is a limit to the number of individual evaluations in a real system or large-scale simulation, only the child individual is re-evaluated. May be. Thereby, the number of evaluations can be reduced.

(J) Restriction on Acquisition of Sample Value When the amount of sample values stored in the search history storage device 31 reaches a predetermined storage capacity, the acquisition of sample values in the search history storage device 31 may be terminated. As a result, the estimated value is calculated based on the search history HS stored in the search history storage device 31 and the search for the Pareto optimal individual can proceed based on the calculated estimated value.

(K) Ranking In the above embodiment, a plurality of individuals are ranked by Pareto ranking. However, the present invention is not limited to this, and a plurality of individuals are ranked using other methods such as non-dominant sorting. May be.

(L) Realization Method of Each Part In the above embodiment, the multi-objective evolution algorithm part 2, the fitness estimation module 30 and the search history storage part 31 are realized by the CPU 101 and the program. Part or all of the estimation module 30 and the search history storage unit 31 may be realized by hardware such as an electronic circuit.

(4) Example 1 and Comparative Example 1
In Example 1 below, the benchmark problem was executed by the multi-objective optimization apparatus according to the first embodiment. In Comparative Example 1, the benchmark problem is executed by a multi-objective optimization device similar to the multi-objective optimization device according to the first embodiment except for the selection operator.

  FIG. 28 is a diagram showing conditions for multi-objective optimization in Comparative Example 1 and Example 1. FIG. 28 (a) shows the conditions for multi-objective optimization of Comparative Example 1, FIG. 28 (b) shows the conditions for multi-objective optimization of Example 1, and FIG. 28 (c) shows the results of Comparative Example 1 and Example 1. Indicates the benchmark problem to be performed.

  As shown in FIG. 28A, in Comparative Example 1, the individual set size is 100, the number of generations is 30, and the number of evaluations is 3000. However, the number of evaluations includes reevaluation of the parent individual. In Comparative Example 1, binary tournament selection is used as the selection operator, and UNDX is used as the crossover operator.

  As shown in FIG. 28B, in Example 1, the individual set size is 100, the number of generations is 300, and the number of evaluations is 3000. In Example 1, the selection method of the first embodiment (the method for selecting a specific parent individual shown in FIG. 17) is used as the selection operator, and UNDX is used as the crossover operator. Further, the generation change method shown in FIG. 17 was used.

In Comparative Example 1 and Example 1, the constant k ′ (= (k ₁ , k ₂ ) is determined by a preliminary experiment and is set to k ₁ = k ₂ = 1000, and α in the α superiority strategy of Example 1 (= (Α ₁₂ , α ₂₁ ) is assumed to be 0.1.

  Here, the number of evaluations is obtained by (number of generations × number of child individuals + number of individuals in the initial individual set).

  In Example 1 and Comparative Example 1, two problems ZDT1 and ZDT2 shown in FIG. 28C were used as benchmark problems (see Non-Patent Document 8).

  ZDT1 is a two-objective optimization problem in which the Pareto optimal solution set has a convex Pareto boundary. ZDT2 is a two-objective optimization problem in which the Pareto optimal solution set has a concave Pareto boundary. Here, ZDT1 and ZDT2 are the minimization problems of the two-variable dual objective function. Appropriate noise is added to each objective function. The ZDT1 and ZDT2 have weak Pareto optimal solutions.

  FIG. 29 is a diagram showing the Pareto optimal individual set obtained in the 50th generation in Comparative Example 1 and Example 1. FIG. FIG. 29A shows a Pareto optimal individual set obtained by the optimization of Comparative Example 1 in a state in which the sample value does not include noise, a circle indicates true fitness, and a solid line indicates a Pareto boundary. FIG. 29B shows a Pareto optimal solution set obtained by the optimization of Comparative Example 1 in a state where the sample value includes noise. The circles indicate true fitness without noise, and the diamonds indicate estimation. The solid line is the Pareto boundary. FIG. 29 (c) shows the Pareto optimal individual set obtained by the optimization of Example 1 in a state where the sample value includes noise, the circles indicate true fitness without noise, and the diamonds indicate estimations. The solid line is the Pareto boundary.

  When optimization is performed according to Comparative Example 1 in a state where the sample value does not include noise, as shown in FIG. 29A, the true fitness and the estimated value have shapes along the convex and concave Pareto boundaries. .

  However, when optimization is performed according to Comparative Example 1 in a state where the sample value includes noise, as shown in FIG. 29 (b), the true fitness and the estimated values are scattered together and the individual that does not reach the Pareto boundary. It can be seen that there are many and that the weak Pareto optimal individuals are Pareto optimal individuals.

  On the other hand, when the optimization is performed according to the first embodiment in a state in which the sample value includes noise, as shown in FIG. It can be seen that the concave Pareto boundary has been reached, and that weak Pareto optimal individuals have been excluded.

  As described above, according to the multi-objective optimization apparatus according to the first embodiment, by using the α superiority strategy, the weak Pareto optimal individual is excluded even in the bi-objective optimization problem having the weak Pareto optimal solution. The estimated value in the Pareto optimal individual set can be calculated with high accuracy. Thereby, the true fitness and the estimated value can be reached at the Pareto boundary.

(5) Example 2 and Comparative Example 2
In Example 2 below, the benchmark problem was executed by the multi-objective optimization apparatus according to the second embodiment. In Comparative Example 2, the benchmark problem was executed by a multi-objective optimization device similar to the multi-objective optimization device according to the second embodiment except for the selection operator.

  FIG. 30 is a diagram showing conditions for multi-objective optimization in Comparative Example 2 and Example 2. 30 (a) shows the conditions for multi-objective optimization of Comparative Example 2, FIG. 30 (b) shows the conditions for multi-objective optimization of Example 2, and FIG. 30 (c) shows the results of Comparative Example 2 and Example 2. Indicates the benchmark problem to be performed.

  As shown in FIG. 30A, in Comparative Example 2, the individual set size is 100, the number of generations is 30, and the number of evaluations is 3000. However, the number of evaluations includes reevaluation of the parent individual. In Comparative Example 2, binary tournament selection is used as the selection operator, and UNDX is used as the crossover operator.

  As shown in FIG. 30B, in Example 2, the individual set size is 100, the number of generations is 300, and the number of evaluations is 3000. In Example 2, the selection method of the second embodiment (the method for selecting a specific parent individual shown in FIG. 22) is used as the selection operator, and UNDX is used as the crossover operator. Furthermore, the generation change method shown in FIG. 22 was used.

In Comparative Example 2 and Example 2, the constant k ′ (= k ₁ , k ₂ , k ₃ ) is determined in a preliminary experiment, and k ₁ = k ₂ = k ₃ = 100000. Further, α (= α ₁₂ = α ₂₃ = α ₃₁ ) in the α superiority strategy of the second embodiment is set to 0.1.

  In Example 2 and Comparative Example 2, two-problem DTLZ2 shown in FIG. 30C was used as a benchmark problem.

  DTLZ2 is a 3-objective optimization problem in which the Pareto optimal solution set has a concave Pareto boundary. Here, DTLZ2 is set as a three-variable 3-objective minimization problem. Appropriate noise is added to each objective function.

  FIG. 31 is a diagram showing the Pareto optimal population obtained in Comparative Example 2 and Example 2. FIG. 31A shows the Pareto optimal individual set obtained by the optimization of Comparative Example 2 in a state where the sample value does not include noise, the circle is the true fitness, and the solid line is the Pareto boundary. FIG. 31 (b) shows the Pareto optimal solution set obtained by the optimization of Comparative Example 2 in a state where the sample value includes noise, the circles indicate the true fitness without noise, and the diamonds indicate the estimation. The solid line is the Pareto boundary. FIG. 31 (c) shows a Pareto optimal individual set obtained by the optimization of Example 2 in a state where the sample value includes noise, the circles indicate true fitness without noise, and the diamonds indicate estimations. The solid line is the Pareto boundary.

  When optimization is performed according to the comparative example 2 in a state where the sample value does not include noise, as shown in FIG. 31A, the true fitness and the estimated value have a shape along the concave Pareto boundary.

  However, when optimization is performed according to Comparative Example 2 in a state where the sample value includes noise, as shown in FIG. 31 (b), the true fitness and estimated values are scattered together and the individual that does not reach the Pareto boundary There are many.

  On the other hand, when the optimization is performed according to the second embodiment in a state in which the sample value includes noise, as shown in FIG. 31 (c), a concave Pareto with a distribution in which both the true fitness and the estimated value are hardly biased. The boundary has been reached.

  As described above, according to the multi-objective optimization apparatus according to the second embodiment, the Pareto optimal individual set can be obtained even in the 3-objective optimization problem by using the above-described specific parent individual selection method and generation change method. Can be calculated with high accuracy. Thereby, the true fitness and the estimated value can be reached at the Pareto boundary.

(6) Example 3
In Example 3 below, the multi-objective optimization of the optimization target 6 in FIG. 3 was executed by the multi-objective optimization apparatus 1 in FIG.

The multi-purpose optimizing device 1 gives the ignition timing and the fuel injection timing as parameters to the ECU 62 to be optimized. The vehicle speed and air-fuel ratio are controlled to be constant by the controller 64 to be optimized 6, the ignition timing and the fuel injection timing are changed by the ECU 62 based on the parameters given from the multi-purpose optimization device 1, and the HC concentration by the exhaust gas analyzer 63 and analyzing the concentration of NO _x. The analyzed HC concentration and NO _x concentration are output to the multipurpose optimization apparatus 1 as sample values.

FIG. 32 is a diagram illustrating conditions for multi-objective optimization according to the third embodiment. As shown in FIG. 32, in Example 3, the individual set size is 50, the child individual set size is 10, the number of generations is 23, and the number of evaluations is 280. In Example 3, the selection method of the first embodiment (the method for selecting a specific parent individual shown in FIG. 17) is used as the selection operator, and UNDX is used as the crossover operator. The constant k ′ (= k ₁ = k ₂ ) is 100,000, and the method of the first embodiment (generation change method shown in FIG. 17) is used as the generation change method.

FIG. 33 is a diagram showing sample values and estimated values obtained in Example 3. The vertical axis in FIG. 33 is the NO _x concentration, and the horizontal axis is the HC concentration. The values on the vertical axis and the horizontal axis are normalized values. Circle marks indicate sample values of 23 generations (280 individuals), and diamond marks indicate estimated values of the final generation.

FIG. 34 is a diagram showing on the fitness function space the estimated values of the Pareto optimal individuals of the final generation obtained in the third embodiment. The vertical axis in FIG. 34 is the NO _x concentration, and the horizontal axis is the HC concentration. The values on the vertical axis and the horizontal axis are normalized values.

  FIG. 35 is a diagram showing the parameters of the Pareto optimal individual of the final generation obtained in Example 3 on the parameter space. The vertical axis in FIG. 35 is the fuel injection timing, and the horizontal axis is the ignition timing. The values on the vertical axis and the horizontal axis are normalized values.

  34 and 35, a plurality of Pareto optimal individuals are classified into three series 1 to 3 so that the relationship between the estimated value and the parameter can be easily understood. A diamond mark indicates a Pareto optimal individual of series 1, a square mark indicates a Pareto optimal individual of series 2, and a triangle indicates a Pareto optimal individual of series 3.

Series 1 is a region well concentration of NO _x is HC concentration poor, sequence 2 is an area for equilibrium and HC concentration and concentration of NO _x, sequence 3 is poor concentration of NO _x is HC concentration is a good region. From FIG. 35, it can be seen that the HC concentration is improved if the ignition timing is decreased earlier and the ignition timing value is decreased, and the NO _x concentration is improved _if the injection timing is delayed later and the ignition timing value is increased.

(7) Correspondence between the constituent elements of the claims and each part of the embodiment In the above embodiment, the search history storage device 31 corresponds to the storage part, the fitness estimation module 30 corresponds to the estimation part, and the multi-objective evolution type The algorithm unit 2 corresponds to a calculation unit.

  The present invention can be used for optimizing a parameter to be optimized such as a real system or an uncertain simulation.

It is a block diagram which shows the functional structure of the multi-objective optimization apparatus which concerns on the 1st Embodiment of this invention. It is a block diagram which shows the hardware constitutions of the multi-objective optimization apparatus of FIG. It is a block diagram which shows an example of a structure of the optimization object. HC concentration, is a diagram showing a relationship between concentration of NO _x and CO concentration and the air-fuel ratio. It is a flowchart which shows the whole process of the multi-objective optimization apparatus of FIG. It is a flowchart which shows the whole process of the multi-objective optimization apparatus of FIG. It is a schematic diagram which shows the parent individual set produced | generated by initialization. It is a schematic diagram for demonstrating alpha superiority strategy. It is a schematic diagram for demonstrating the dominance comparison of the individual by alpha dominance strategy. It is a figure for demonstrating Pareto ranking. It is a schematic diagram for demonstrating congestion degree sorting. It is a flowchart which shows the process of the congestion degree sort by a multipurpose evolution type algorithm part. It is a schematic diagram for demonstrating calculation of the estimated value by the fitness estimation module of a fitness estimation part. It is a schematic diagram which shows the sample value with the noise according to normal distribution. It is a schematic diagram which shows the model of an uncertain fitness function. It is a flowchart which shows the calculation process of the estimated value by the fitness estimation module of a fitness estimation part. It is a schematic diagram for demonstrating the method from selection of a specific parent individual to generational change. It is a schematic diagram for demonstrating the production | generation process of a child individual set. It is a flowchart which shows the selection process of the specific parent individual by a multipurpose evolution type algorithm part. It is a schematic diagram which shows the production | generation process of the child individual by UNDX. It is a schematic diagram which shows the search of the individual based on the search history memorize | stored in the search history memory | storage device. It is a schematic diagram for demonstrating the method from selection of a parent individual to generational change. It is a flowchart which shows the selection process of the parent individual by a multipurpose evolution type algorithm part. It is a figure which shows the distribution parameter | index extended to the m objective optimization problem. It is a block diagram which shows the example which applied the multipurpose optimization apparatus to the engine simulator. It is a block diagram which shows the example which applied the multipurpose optimization apparatus to the motor evaluation apparatus. It is a block diagram which shows the example which applied the multipurpose optimization apparatus to the motor simulator. It is a figure which shows the conditions of the multipurpose optimization of the comparative example 1 and Example 1. FIG. It is a figure which shows the Pareto optimal individual set obtained in the 50th generation in the comparative example 1 and Example 1. FIG. It is a figure which shows the conditions of the multipurpose optimization of the comparative example 2 and Example 2. FIG. It is a figure which shows the Pareto optimal individual set obtained in the comparative example 2 and Example 2. FIG. It is a figure which shows the conditions of the multipurpose optimization of Example 3. It is a figure which shows the sample value and estimated value which were obtained in Example 3. It is a figure which shows the estimated value of the Pareto optimal individual of the last generation obtained in Example 3 on a fitness function space. It is a figure which shows the parameter of the Pareto optimal individual of the last generation obtained in Example 3 on parameter space. It is a figure which shows the example which applied the multi-objective optimization problem to engine optimization. It is a figure for demonstrating a Pareto optimal solution.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Multiobjective optimization apparatus 2 Multiobjective evolution type algorithm part 3 Fitness estimation part 4 Output interface 5 Input interface 6 Optimization object 10 User 30 Fitness estimation module 31 Search history storage device 61 Engine 62 ECU (engine control unit)
63 Exhaust gas analyzer 64 Controller 65 Throttle unit 66 Dynamo 101 CPU (Central processing unit)
102 ROM (read only memory)
103 RAM (Random Access Memory)
104 Input Device 105 Display Device 106 External Storage Device 107 Recording Medium Drive Device 108 Input / Output Interface 109 Recording Medium C Child Individual Set d _l Distance f ₁ , f ₂ Fitness Function F Individual Set HS Search History I1, I2, I3, I4 , I5, I6, I7, I8, I9, I10, I11, I12, I21, I22 Individual L1, L2, L11, L12 Straight line P Parent individual set P1 First parent individual P2 Second parent individual P3 Third parent Individual s1, s2, s3 rectangle x ₁ , x ₂ parameters

Claims (22)

A multi-objective optimization apparatus that gives a set of individual parameters to an optimization target and receives a set of fitness sample values for a plurality of fitness functions corresponding to a plurality of objectives from the optimization target,
A storage unit for storing a set of individual parameters and a set of fitness sample values output from the optimization target;
An estimation unit for obtaining a set of true fitness estimation values corresponding to an individual of interest based on a plurality of sets of sample values corresponding to a plurality of individuals stored in the storage unit;
A new individual is generated based on the estimated value obtained by the estimation unit, a set of parameters of the generated individual is given to the optimization target and the storage unit, and a plurality of sets obtained by the estimation unit A computing unit that obtains a Pareto optimal individual set by evaluating the evaluation individual set according to the multi-objective evolutionary algorithm based on the estimated value;
The estimation unit includes
By weighting a set of sample values corresponding to each individual stored in the storage unit and obtaining a linear sum of a plurality of sets of weighted sample values, a set of fitness estimated values corresponding to the individual of interest is obtained. And the weight of each individual is a function including the distance between the individual of interest and the individual on the parameter space,
The computing unit is
For each of the plurality of fitness functions, the superiority and inferiority of the estimated values corresponding to the plurality of individuals of the evaluation individual set are compared, the comparison result for each of the plurality of fitness functions is weighted, and the plurality of adaptation functions Ranking a plurality of individuals of the evaluation individual set based on a linear sum of a plurality of comparison results weighted for a degree function;
A multi-objective optimization device, characterized in that a new individual is generated based on a distribution index representing a degree of sparseness in a distribution of individuals of the highest rank of the evaluation individual set on a fitness function space. The estimation unit sets h _l as a plurality of individuals stored in the storage unit, sets F (x) as a set of sample values corresponding to the target individual x, and sets a distance d _l from the target individual in the parameter space. If the set of sample values corresponding to is F (h _l ), k ′ is a coefficient, l = 1,..., H, and n is a natural number,

The multi-objective optimization apparatus according to claim 1, wherein a set f ′ (x) of true fitness estimation values corresponding to the target individual x is calculated using the estimation formula represented by: 3. The multi-objective optimization apparatus according to claim 2, wherein n is 1. 3. The multi-objective optimization apparatus according to claim 2, wherein n is 3. The arithmetic unit calculates fitness estimates corresponding to individuals x1 and x2 for one fitness function among the p fitness functions corresponding to p objectives, f _k (x1) and f _k (x2). ), The fitness estimates corresponding to individuals x1 and x2 for the other fitness functions among the p fitness functions are f _j (x1) and f _j (x2), and k and j are 1, ..., and p, k is different from j, α _kj and weights, g _k (x1, x2) is k = 1, which is represented by the following formula, ···, g for all p _k (x1, x2 ) ≦ 0 is satisfied, and when at least one of k = 1,..., P has a relationship of g _k (x1, x2) <0, it is determined that the individual x1 is superior to the individual x2 The multi-objective optimization apparatus according to any one of claims 1 to 4.

When the plurality of objectives are two or more m objectives, the distribution index is a single size formed by m individuals adjacent to the target individual in the fitness function space corresponding to the m objectives. ,
The calculation unit selects an individual with the highest degree of sparseness based on the size of the unit, and generates a new individual using the selected individual. Multipurpose optimization device as described in 1. When the plurality of objectives are two objectives, the size of the single object is represented by a length of a straight line connecting two individuals adjacent to the target individual in the fitness function space, and the plurality of objectives is the three objectives. In this case, the size of the single unit is represented by an area of a triangle having apexes of three individuals adjacent to the medial individual in the fitness function space, and when the plurality of purposes is four purposes, the size of the single unit 7. The multi-objective optimization apparatus according to claim 6, wherein the multi-objective optimization apparatus is represented by a volume of a triangular pyramid having four individuals adjacent to the target individual in the fitness function space. In the case where the plurality of objectives are m objectives of 4 or more, the size of the simple substance is the bottom (m-1) dimensional area of the simple substance formed by m individuals adjacent to the target individual in the fitness function space × The multi-objective optimization apparatus according to claim 6, which is expressed by height / m. 7. The multi-objective optimization apparatus according to claim 6, wherein when the plurality of objectives are three or more objectives, the simple substance is formed by Delaunay triangulation. The arithmetic unit replaces the new individual with a lower-ranked individual in the evaluation individual set when the generated new individual is different from the individual in the evaluation individual set. The multipurpose optimization apparatus in any one of -9. 10. The calculation unit according to claim 1, wherein when the generated new individual overlaps with an individual of the evaluation individual set, the arithmetic unit assigns a lowest rank to the new individual. Multipurpose optimization device as described. The multipurpose optimization apparatus according to claim 1, wherein the calculation unit evaluates each individual of the evaluation individual set once. The estimation unit ends storage of the set of sample values output from the optimization target when the amount of the set of sample values stored in the storage unit reaches a predetermined storage capacity. The multi-objective optimization apparatus according to any one of claims 1 to 12. The multipurpose optimization apparatus according to any one of claims 1 to 13, wherein the calculation unit displays the Pareto optimal individual based on a set of estimated values obtained by the estimation unit. The multipurpose optimization apparatus according to any one of claims 1 to 14, wherein the arithmetic unit evaluates individuals of the evaluation individual set using a genetic algorithm as the multipurpose evolutionary algorithm. The optimization target includes an evaluation system for evaluating a plurality of performances of the device, the set of parameters includes a set of control parameters for the evaluation system, and the plurality of fitness functions are the evaluation functions The multi-objective optimization apparatus according to claim 1, wherein the plurality of performances are obtained by system evaluation, and the set of fitness is the value of the plurality of performances. The optimization device according to claim 16, wherein the device is an engine. The optimization device according to claim 16, wherein the device is a motor. 17. The apparatus according to claim 16, wherein the evaluation system is an apparatus evaluation apparatus that controls the apparatus based on the set of parameters and outputs a plurality of performance values generated by the operation of the apparatus as sample values. The equipment optimization device described. The evaluation system is a device simulator that evaluates a plurality of performances by simulating the operation of the device based on the set of parameters, and outputs a plurality of evaluated performance values as a set of sample values. The apparatus optimization device according to claim 16, wherein the apparatus optimization apparatus is a device. Multi-objective optimization that gives a set of individual parameters to an optimization target and optimizes parameters based on a set of fitness sample values for a plurality of fitness functions corresponding to the plurality of objectives output from the optimization target A method of
Storing a set of individual parameters and a set of fitness sample values output from the optimization target in a storage unit;
Obtaining a set of true fitness estimates corresponding to the individual of interest based on a plurality of sets of sample values corresponding to the plurality of individuals stored in the storage unit;
A new individual is generated based on the obtained estimated value, and a set of parameters of the generated individual is given to the optimization target and the storage unit, and for evaluation based on the obtained plural sets of estimated values Obtaining a Pareto optimal population by evaluating the population according to a multi-objective evolutionary algorithm,
The step of obtaining a set of estimated values comprises:
By weighting a set of sample values corresponding to each individual stored in the storage unit and obtaining a linear sum of a plurality of sets of weighted sample values, a set of fitness estimated values corresponding to the individual of interest is obtained. The weight of each individual is a function including the distance between the individual of interest and the individual on the parameter space;
The step of obtaining the Pareto optimal individual comprises:
For each of the plurality of fitness functions, the superiority and inferiority of the estimated values corresponding to the plurality of individuals of the evaluation individual set are compared, the comparison result for each of the plurality of fitness functions is weighted, and the plurality of adaptation functions Ranking a plurality of individuals of the evaluation individual set based on a linear sum of a plurality of comparison results weighted for a degree function;
Generating a new individual based on a distribution index representing the degree of sparseness in the distribution of individuals of the highest rank in the evaluation individual set on the fitness function space. A multipurpose that can be executed by a computer that provides a set of individual parameters to an optimization target and optimizes the parameters based on a set of fitness sample values for a plurality of corresponding fitness functions output from the optimization target An optimization program,
A process of storing a set of individual parameters and a set of fitness sample values output from the optimization target in a storage unit;
A process for obtaining a set of true fitness estimates corresponding to the individual of interest based on a plurality of sets of sample values corresponding to the plurality of individuals stored in the storage unit;
A new individual is generated based on the obtained estimated value, and a set of parameters of the generated individual is given to the optimization target and the storage unit, and for evaluation based on the obtained plural sets of estimated values Processing the computer to perform a process for obtaining the Pareto optimal population by evaluating the population according to a multi-objective evolutionary algorithm,
The process for obtaining a set of estimates is
By weighting a set of sample values corresponding to each individual stored in the storage unit and obtaining a linear sum of a plurality of sets of weighted sample values, a set of fitness estimated values corresponding to the individual of interest is obtained. The weight of each individual is a function including the distance between the individual of interest and the individual on the parameter space,
The process for obtaining the Pareto optimal individual is:
For each of the plurality of fitness functions, the superiority and inferiority of the estimated values corresponding to the plurality of individuals of the evaluation individual set are compared, the comparison result for each of the plurality of fitness functions is weighted, and the plurality of adaptation functions A process of ranking a plurality of individuals of the evaluation individual set based on a linear sum of a plurality of comparison results weighted for a degree function;
And a process for generating a new individual based on a distribution index representing the degree of sparseness in the distribution of individuals of the highest rank of the evaluation individual set on the fitness function space.

Images