WO2018166270A2

WO2018166270A2 - Index and direction vector combination-based multi-objective optimisation method and system

Info

Publication number: WO2018166270A2
Application number: PCT/CN2017/119311
Authority: WO
Inventors: 骆剑平; 杨芸
Original assignee: 深圳大学
Priority date: 2017-03-15
Filing date: 2017-12-28
Publication date: 2018-09-20
Also published as: CN107122844A

Description

Multi-objective optimization method and system based on combination of index and direction vector

Technical field

The invention relates to the field of multi-objective optimization, in particular to a multi-objective optimization method and system based on combining indicators and direction vectors.

Background technique

When solving optimization problems in engineering practice and scientific research, if only one objective function is considered, it is called single-objective optimization problem; if more than one objective function is considered, and each objective function will be mutually restricted by decision variables, Independence, that is, when an objective function is improved, the performance of other objective functions is reduced to a certain extent. Such a situation is called a multi-objective superior problem. The optimal solution of the single-objective optimization problem is usually a uniquely determined optimal solution, and the solution of the multi-objective optimization problem is irreconcilable between the objective functions. Its optimal solution is usually a set, which is usually called Pareto. Optimal solution or non-dominated solution.

In life, we often face multi-objective optimization problems. For example, when we need to depart from A to B, we hope to spend the least time, the shortest distance and the lowest cost, but the reality is often the shortest path. On the top, the time spent is not necessarily the least, and the cost is not necessarily the lowest; however, when choosing the shortest time, the travel time and cost of travel are not necessarily the lowest; at the same time, the time and distance are not necessarily the shortest. These three elements seem to be unified, but they are mutually constrained. This is a typical multi-objective optimization problem. Solving such problems leads to a series of optimal solutions, and the choice of which method ultimately depends on the needs of the decision maker. Therefore, the multi-objective optimization problem will solve as many Pareto optimal solutions as possible, so that decision makers have more choices, and choose the most needed way in the comparison of more best methods.

At present, multi-objective optimization problems can be widely applied in many fields such as vehicle path planning, power system, workshop management scheduling, cloud computing, data mining, radar detection systems, etc. Therefore, it is valuable to study multi-objective optimization problems.

There are two main methods for traditional multi-objective optimization algorithms: weighting method and constraint method. The weighting method assigns each objective function a weight, and then adds all the objective functions to which the weights are assigned, that is, converts to a single-objective optimization problem. The algorithm can only find one optimal solution at a time (a weight) There is only one optimal solution for the allocation method). The constraint method is based on one of the objectives as the optimization object, and the other objective functions are the constraints, which translates into a single-objective optimization problem with constraints, but only one partial Pareto solution can be obtained once, and the efficiency is low and the corresponding parameters are not Very good setting.

Evolutionary Algorithm (EAs) is a group search algorithm that simulates the evolutionary process of nature in nature. Without any prior knowledge, it searches and compares the optimal solution by iteratively, thus obtaining the whole. Pareto optimal set. Firstly, the excellent individuals in the t-th generation are selected in a certain selection way to form the Pareto optimal set of the t-th generation, and then the Pareto optimal set is cross-mutated to produce the t+1th new population, t The +1 generation population replaces the t-th generation population, and the previous steps are repeated. When the pre-set termination condition is evolved, the Pareto optimal set is taken as the output, which is the multi-objective optimization problem solved by the algorithm. Excellent solution set. The emergence of evolutionary algorithms has brought new ideas and directions to solving multi-objective optimization problems.

The multi-objective evolutionary algorithm can efficiently solve multi-objective optimization problems mainly because: 1) running once can produce a Pareto optimal solution set, and in each iteration process, the entire solution set will be optimized instead of only optimizing the optimal solution. The consumption of computing resources is relatively low; 2) there is no requirement for the nature of the objective function, and the objective function does not need to be micro, steerable or continuous, that is, there is no specific requirement for the type of problem that needs to be optimized, and it is suitable for optimization of all black box problems. 3) easy to understand and use, do not need to invest too much human resources; 4) suitable for parallel computing environment, you can use computer to run multiple algorithms at the same time, multiple processes will not affect each other, so that you can solve more efficiently Multiple multi-objective optimization issues.

The selection methods of multi-objective evolutionary algorithms can be mainly divided into three categories: based on Pareto dominance, based on decomposition and based on indicators.

(1) Based on Pareto dominance

Pareto dominated multi-objective evolutionary algorithms, mainly: non-dominated sorting genetic algorithm II (NSGAII), Pareto enhanced evolutionary algorithm 2 (SPEA2), based on the surface Pareto selection algorithm II (PESA-II). The Pareto-dominated approach prioritizes convergence and then considers distribution. Although they perform very well when dealing with 2-3 targets, they are less than ideal in the face of increasing number of targets. The main reasons are as follows: 1) As the number of targets increases, the number of individuals who become non-dominated in the population increases rapidly, resulting in a severe reduction in the selection pressure based on the Pareto dominance relationship, and the quality between individuals is difficult to distinguish. It weakens the search ability of the algorithm; 2) Because the Pareto dominance relationship is not effective in the high-dimensional case, the dominant factor of the algorithm update individual becomes the distributed retention mechanism, which may have a negative impact on the convergence of the algorithm. In response to such characteristics, Deb and Jain proposed an improved NSGA-II algorithm, NSGA-III, which replaces the clustering operand of NSGA-II with a uniformly distributed reference point--crowding distance operator to solve high-dimensional multi-targets. Performance is better when optimizing problems.

(2) based on decomposition

The main idea based on the decomposition method is to decompose the multi-objective optimization algorithm into multiple single-objective optimization algorithms, which are realized by linear or nonlinear aggregation functions. This method uses the domain ideas and plays a vital role. . Its main representative algorithm is MOEA/D. The decomposition-based approach, like Pareto dominance, prioritizes convergence and then considers distribution. The MOEA/D algorithm, in the high-dimensional target space, generally closes the Pareto front by selecting the aggregate function, and maintains the diversity of the population through different weight vectors. However, in a high-dimensional target space, an individual with a good aggregate function value is likely to be far away from the corresponding weight vector, so this superior individual is likely to be replaced, which in turn leads to serious diversity of the MOEA/D algorithm. reduce. Therefore, for the MOEA/D algorithm, if the priority of the corresponding weight vector of the aggregate function is too high, there is a great possibility that some important search areas will be lost. The EAG-MOEA/D algorithm separates and coordinates each other based on the idea of decomposition and Pareto dominance and congestion distance using evolutionary documents. It has a good effect on low-dimensional discrete multi-objective optimization problems and high-dimensional multi-objective optimization problems. The solution is not very ideal. The proposed MOEA/DD algorithm: combined with the dominant idea, and MOEA/D_DU can better solve the shortcomings of the MOEA/D algorithm in the high-dimensional case.

(3) Based on indicators

In order to compare the performance of different multi-objective evolutionary algorithms, researchers have proposed that it can evaluate the quality indicators of a large number of individuals in the solution set, such as the IGD index, the ε index, the R2 index, the distribution index, and the convergence. Sexual and distributed super-volume indicators. In 2004, Zitzler et al. proposed the IBEA algorithm to apply the quality index to the multi-objective evolutionary algorithm, which is an indicator-based adaptive value allocation strategy for pairing selection and environment selection, and constructed a multi-indicator based Target evolutionary algorithm framework. The basic idea of this algorithm is to use the quality indicators to guide the evolution process, and to transform the multi-objective optimization problem into a single-objective optimization problem for a given index. Since it does not use the objective function as the optimization object, it avoids the increase of the target number. To choose the problem of small pressure becomes one of the most important methods to solve high-dimensional multi-objective optimization problems. IBEA has attracted a lot of scholars' attention. Some new multi-objective evolutionary algorithms based on indicators have been proposed, such as: MOMBI, combining indicators and hybrid leapfrog intelligent algorithms to solve multi-objective optimization problems [5] and Two-Arc2 will Pareto dominance and indicators are combined from two files, and the solution to high-dimensional multi-objective optimization problems is better.

Despite the recent achievements in this field, there is still plenty of room to explore for multi-objective optimization evolution.

One difficulty in the high-dimensional multi-objective optimization problem is that it maintains high diversity while converging to the real frontier of Pareto; the proposed multi-objective evolutionary algorithm suitable for high-dimensional, such as NSGA-III through uniformly distributed reference points To replace the crowded distance, so as to improve the convergence and distribution of the population, although the high-dimensional multi-objective optimization problem has achieved good results, but because of the Pareto dominance relationship in the case of more and more targets, non-dominated solutions The number is increasing sharply, the selection pressure is getting smaller and smaller, and the Pareto optimal solution is difficult to approach Pareto's true preface. This essential attribute is difficult to completely eliminate.

Therefore, the prior art has yet to be improved and developed.

Summary of the invention

In view of the above deficiencies of the prior art, the object of the present invention is to provide a multi-objective optimization method and system based on combining indicators and direction vectors, aiming at solving the problem that the existing multi-objective optimization algorithm cannot achieve and improve the convergence of the calculation results. The issue of diversity.

The technical solution of the present invention is as follows:

A multi-objective optimization method based on combining indicators and direction vectors, including steps:

A. Initialize the direction vector, the evolutionary population, and the ideal point vector;

B. Generating a new individual based on the initialized evolutionary population;

C. Combine the new individual with the initialized evolutionary population, obtain all the non-dominated solutions in the merged evolutionary population, and iterate the merged evolutionary population until the number of non-dominated solutions in the merged population and the size of the initialized evolutionary population Equal, and output the solution corresponding to the evolved population after iteration.

The multi-objective optimization method based on the combination of the indicator and the direction vector, wherein the step A specifically includes:

A1, the initialization direction vector λ = (λ ₁ , λ ₂ , ..., λ _m ) ^T , wherein

H is a preset parameter that takes a natural number, m is the target number, and the total number of initialization direction vectors λ

A2: Obtain an angle between the i-th direction vector and the remaining N-1 direction vectors in the initialization direction vector λ, and obtain a minimum value a _i between the direction vectors;

A3, the evolving population randomly generated initialization ^{EP = (x 1, ...,} x N); where x ⁱ

individual fitness value

^{F (x i), i∈ {} 1,2, ..., N}, EP The size is N;

A4, setting the current iteration number gen=0;

A5. Initialize the ideal point vector z ^* = (z ₁ ^* , ..., z _m ^* ), where z _k ^* =min(f _k (x ⁱ )), i ∈ {1,...,N}, K∈{1,...,m}.

The multi-objective optimization method based on combining an indicator and a direction vector, wherein the evolved population initialized in the step B generates a new individual according to a simulated binary crossover operator or a backpack operator.

The multi-objective optimization method based on the combination of the indicator and the direction vector, wherein the step B specifically includes:

B1, randomly selecting the i-th sub-problem, the value of i is between 1 and N, and the i-th problem can only be selected once;

B2, randomly selecting two individuals k and l as replicas from the initialized evolutionary population EP, and generating the new individual y by the individual x ^k corresponding to the kth sub-question and the individual x ^l corresponding to the lth sub-problem, when the new individual y exceeds Step B3 is performed in the range of the preset decision space Ω, and step B4 is performed when the new individual y does not exceed the range of the preset decision space Ω;

B3, re-randomly generating a new solution and replacing the new individual y;

B4, calculating a new individual objective function value vector y _{F (y) = (f 1} (y), ..., f m (y));

B5. The updated ideal point vector is z' ^* = (z ₁ ' ^* , ..., z' _m ^* ), where z' _k ^* =min(z' _k ^* , f _k (y)), k∈{ 1,...,m};

B6. Place the new individual y in the new individual set Y, where Y=Y+{y}, where the initial value of the new individual set φ is φ.

The multi-objective optimization method based on the combination of the indicator and the direction vector, wherein the step C specifically includes:

C1, the new individual set Y is merged with the initialized evolutionary population EP, and the combined evolutionary population EP' is obtained, wherein EP'=Y∪EP, wherein the size of the combined evolutionary population EP' is recorded as _Np , where _Np = sizeof( EP);

C2, obtain all non-dominated solutions in the merged evolutionary population EP', and place them in the non-dominated solution set S, where the initial value of the non-dominated solution set S is φ, and the size of the non-dominated solution set S is denoted as N ', where N'=sizeof(S);

C3, emptying the merged evolutionary population EP';

C4. When N'≤2N, the cleared EP' is set equal to the non-dominated solution set S, and when N'>2N, it is obtained according to ag _i =min(angle(F(x _j ), λ ⁱ )) The non-dominant solution set S is the individual x _k from the minimum angle of the i-th direction vector, where k ∈ [1, N'], j = {1, ..., N'}, x ∈ S;

C5. Determine whether the ag _i corresponding to the individual x _{k of} the minimum angle of the i-th direction vector is smaller than the minimum value a _i between the direction vectors, and if the ag _{i is} smaller than a _i , the EP'=EP'+{x _k} x ⁱ ∈S and _{S = S / {x k}} ;

C6. Calculating the fitness value of x ⁱ individuals in the non-dominated solution set S

I∈{1,2,...,sizeof(S)}, and obtain the fitness value of the individual x ⁱ

Take the value x for the individual x ^d , where

The value of i ranges from 1 to N'-2N;

C7, if

Then iterate to obtain EP"=EP"+{x ⁱ }x ⁱ ∈S, and the size of the evolved population EP" after iteration is M=N.

A multi-objective optimization system based on combination of indicators and direction vectors, including:

An initialization module for initializing a direction vector, an evolutionary population, and an ideal point vector;

a new individual generation module for generating a new individual based on the initialized evolved population;

An iterative output module for combining the new individual with the initialized evolutionary population, obtaining all non-dominated solutions in the merged evolved population, and iterating the merged evolved population until the number of non-dominated solutions in the merged population is initialized The evolutionary populations are equal in size and output the solution corresponding to the evolved population after iteration.

The multi-objective optimization system based on the combination of the indicator and the direction vector, wherein the initialization module specifically includes:

a direction vector initializing unit for initializing a direction vector λ=(λ ₁ , λ ₂ , . . . , λ _m ) ^T , wherein

a first angle acquiring unit, configured to acquire an angle between the i-th direction vector and the remaining N-1 direction vectors in the initialization direction vector λ, and obtain a minimum value a _i between the direction vectors;

An evolutionary population initialization unit for randomly generating an initial evolutionary population EP=(x ¹ ,...,x ^N ); wherein the fitness value of the individual ⁱ is F(x ⁱ ), i∈{1, 2,... , N}, the size of the EP is N;

Setting unit for setting the current iteration number gen=0;

An ideal point vector initialization unit for initializing an ideal point vector z ^* = (z ₁ ^* , ..., z _m ^* ), where z _k ^* =min(f _k (x ⁱ )), i ∈ {1,. ..,N},k∈{1,...,m}.

The multi-objective optimization system based on combining an indicator and a direction vector, wherein the evolved population initialized in the new individual generation module generates a new individual according to a simulated binary crossover operator or a backpack operator.

The multi-objective optimization system based on the combination of the indicator and the direction vector, wherein the new individual generation module specifically includes:

a sub-question selection unit for randomly selecting the i-th sub-problem, the value of i is between 1 and N, and the i-th problem can only be selected once;

a new individual generation and judgment unit for randomly selecting two individuals k and l as a copy from the initialized evolutionary population EP, and generating a new individual for the individual x ^k corresponding to the kth sub-question and the individual x ^l corresponding to the l-th sub-question y, when the new individual y exceeds the range of the preset decision space Ω, the new solution replacement unit is started, and when the new individual y does not exceed the range of the preset decision space Ω, the target function value vector calculation unit is started;

A new solution replaces the unit for re-randomly generating a new solution and replacing the new individual y;

An objective function value vector calculation unit for calculating an objective function value vector F(y)=(f ₁ (y), . . . , f _m (y)) of the new individual y;

An update unit for updating the ideal point vector as z' ^* = (z ₁ ' ^* , ..., z' _m ^* ), where z' _k ^* =min(z' _k ^* , f _k (y)), K∈{1,...,m};

A new individual set acquisition unit for placing a new individual y in a new individual set Y, where Y=Y+{y}, wherein the initial value of the new individual set φ is φ.

The multi-objective optimization system based on the combination of the indicator and the direction vector, wherein the iterative output module specifically includes:

a merging unit for combining the new individual set Y with the initialized evolutionary population EP to obtain a combined evolutionary population EP', wherein EP'=Y∪EP, wherein the size of the combined evolutionary population EP' is denoted as _Np , where _Np =sizeof(EP);

The non-dominated solution acquisition unit is used to obtain all non-dominated solutions in the merged evolutionary population EP', and is placed in the non-dominated solution set S, wherein the initial value of the non-dominated solution set S is φ, and the non-dominated solution set The size of S is denoted by N', where N'=sizeof(S);

Emptying the unit for emptying the merged evolved population EP';

The individual acquisition unit is configured to set the cleared EP′ to be equal to the non-dominated solution set S when N′≤2N, and to ag _i =min(angle(F(x _j ),λ when N′>2N) ⁱ⁾⁾ set of non-dominated solutions acquires a minimum angle of the vector S in a direction from the i-th individual x _k, wherein k∈ [1, N '], j = {1, ..., N'}, x∈S;

a second angle acquiring unit, configured to determine whether the ag _i corresponding to the individual x _{k of} the minimum angle of the i-th direction vector is smaller than the minimum value a _i between the direction vectors, and if the ag _{i is} less than a _i '=EP'+{x _k }x ⁱ ∈S and S=S/{x _k };

The fitness value calculation unit is configured to calculate the fitness value of the x ⁱ individual in the non-dominated solution set S

And obtain the fitness value of the individual x ⁱ

Take the value x for the individual x ^d , where

The value of i ranges from 1 to N'-2N;

Iterative unit for use in

Advantageous Effects: The multi-objective optimization method and system based on the combination of indicators and direction vectors provided by the present invention can be used to replace the Pareto dominant relationship, and effectively alleviate the selection pressure caused by the excessive proportion of non-dominated individuals. The problem. Moreover, the binary ε index strictly satisfies the Pareto dominant consistency, the computational complexity is lower than the index, and no additional parameter setting is required, and the calculation is simple.

DRAWINGS

1 is a flow chart of a preferred embodiment of a multi-objective optimization method based on combining indicators and direction vectors according to the present invention.

Figure 2a is a first schematic view of the use angle of the DTLZ7_M3.

Figure 2b is a second schematic view of the use angle of the DTLZ7_M3.

Figure 2c is a third schematic view of the use angle of the DTLZ7_M3.

Figure 3a is a first schematic diagram of the deletion of a non-inferior solution.

Figure 3b is a second schematic diagram of the deletion non-inferior solution.

Figure 3c is a third schematic diagram of the deletion non-inferior solution.

4 is a schematic diagram of the angle θ between the X individual and the λ direction vector.

FIG. 5 is a structural block diagram of a preferred embodiment of a multi-objective optimization system based on combining indicators and direction vectors according to the present invention.

detailed description

The present invention provides a multi-objective optimization method and system based on a combination of indicators and direction vectors. In order to make the objects, technical solutions and effects of the present invention more clear and clear, the present invention will be further described in detail below. It is understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention.

Referring to FIG. 1 , FIG. 1 is a flowchart of a preferred embodiment of a multi-objective optimization method based on combining indicators and direction vectors according to the present invention. As shown in FIG. 1 , the method includes the following steps:

Step S100, initializing a direction vector, an evolutionary population, and an ideal point vector;

Step S200: Generate a new individual according to the initialized evolved population;

Step S300, combining the new individual with the initialized evolutionary population, obtaining all non-dominated solutions in the merged evolved population, and iterating the merged evolved population until the number of non-dominated solutions in the merged evolved population and the initialized evolved population Equal in size and output the solution corresponding to the evolved population after iteration.

In the embodiment of the present invention, an ε index is proposed, and the ε index is combined with the direction vector to effectively improve the edge effect of the ε index. For the choice of direction vector, from the perspective of population diversity, a uniformly distributed direction vector can be used. Thus, when the Pareto optimal frontier is consistent with the direction vector, the introduced direction vector can alleviate the index edge effect, and when the Pareto optimal frontier and the direction vector are inconsistent, the indicator will play a leading role in the evolution process. The edge effect of the indicator is not obvious because some individuals are selected by the direction vector. From the experimental results, the combination of binary-based addition index and direction vector can improve the convergence and diversity of the algorithm at the same time, and can deal with multi-objective optimization problems in various situations.

The indicator-based approach, when distinguishing between individual strengths and weaknesses, does not compare individual objective function values, but converts all objective functions into a single value that measures individual contribution. Therefore, the indicator-based approach is not limited by the number of targets, and can effectively replace the problem that Pareto dominance is difficult to converge in high-dimensional cases.

The index and direction vector will be combined, called EDV, and the index uses ε binary addition index, because of its simple calculation and low computational complexity, compared with the super-volume indicator (when the number of targets increases) The computational complexity increases exponentially, which is more suitable for high-dimensional multi-objective optimization problems. Combining the ε index with the direction vector can effectively improve the edge effect of the ε index. When the Pareto optimal frontier is consistent with the direction vector, the introduction of the direction vector can alleviate the edge effect of the indicator. When the Pareto optimal frontier and the direction vector are inconsistent, the indicator will play a leading role in the evolution process. The edge effect is not obvious because some of the individuals are selected by the direction vector.

In order to more clearly understand the technical solution of the present invention, some basic concepts of a mathematical model for a multi-objective optimization problem are described below.

Definition 1.1 Multi-objective optimization problems (MOPs)

A multi-objective optimization problem consisting of n-dimensional decision variables, m objective functions, J inequality constraints and K equality constraints is defined as follows:

Minimized: F(x)=(f ₁ (x),...,f _m (x)) ^T

_{Constraints: g j (x) ≥0,} j = 1, ..., J (1-1)

h _k (x)=0,k=1,...,K

X∈Ω

Where in formula (1-1),

a _i and b _i represent different constants, thus constituting the range of values of the decision variable x in the i dimension, then Ω is called the decision (variable) space, then x = (x ₁ , ..., x _n ) ^T ∈ Ω is a candidate solution. F: Ω→R ^{m is} composed of m conflicting objective functions, R ^m is the target space, and the obtained target set can be expressed as: Θ={F(x)|x∈Ω, g _j (x)≥0, _{h k (x) = 0}} , where. When the number of targets is m>3, it is called high-dimensional multi-objective optimization problem. When the number of targets is 2 or 3, it is called low-dimensional multi-objective optimization problem.

For the single-objective optimization problem, the fitness value is compared to compare the merits of the individual. Then the goals of the multi-objective optimization problem are conflicting with each other, so there is no way to compare the individual merits and demerits through a fitness function like the single-objective optimization problem. Therefore, the comparison of the advantages and disadvantages of multi-objective individuals requires a different method. It is called a preference relation. Pareto dominant relationship is the most common preference relationship for multi-objective optimization problems, which is defined as follows:

Definition 1.2Pareto dominant

Given two feasible solutions a, b ∈ Ω, if a and b satisfy the relation (1-2),

Referred to as

Also known as b dominates a, a is dominated by b.

Definition 1.3 non-dominated solution

Given two feasible solutions a, b ∈ Ω, a does not dominate b, and b does not dominate a, then a and b are said to be non-dominated. For x∈A, if x'∈A is not found to dominate x, then x is called the non-dominated solution in set A.

Define the 1.4Pareto optimal solution set

Cannot find a b∈Ω in the feasible solution, satisfying

Where a ∈ Ω, then a is the Pareto optimal solution, and the set of all Pareto optimal solutions is called the Pareto optimal solution set, and the corresponding target vector is called Pareto optimal preface.

After understanding some basic concepts of the mathematical model of multi-objective optimization problems, the following is a further introduction to the fitness evaluation process based on binary quality indicators.

In general, a quality indicator refers to a function that maps a Pareto collection containing N individuals to a specific number. For example, a super-volume indicator based on the super-volume concept can be used to evaluate the quality of a set, but the super-volume The computational complexity is very high, because the calculation of a set of supervolumes is a NP-hard problem. Therefore, the binary addition ε index I _ε+ can be used to compare the quality of the two Pareto sets as a whole to understand the relationship between them, thus guiding the algorithm to evolve in a better direction. For the two sets A and B, I _ε+ (A, B) is defined as follows:

The binary addition indicator I _ε+ gives the minimum distance that the Pareto set needs to translate for the entire target space for each target dimension, thus approximate a weakly dominant relationship. I _ε+ can be regarded as an extension of the Pareto dominance relationship. It is similar to the ordinary Pareto-based fitness value distribution method, so it can be used to directly calculate the individual fitness value. It is worth noting that the I _ε+ indicator strictly satisfies the Pareto dominance relationship.

Suppose the population P is a sample of the decision space Ω, and the fitness value evaluation function F ₁ (x) of the individual x in the population P is defined as follows:

Where c=max _{x, y} ∈ _P |I(x,y)|, then v>0 is the scale factor, generally taking a smaller value, and the experimental result of 0.01 is better. The greater the fitness value F ₁ (x), the greater the contribution of the individual to the overall solution quality index. If the individual is deleted, the greater the quality loss of the solution set, the more it should be retained to the offspring. That is, if

Then there is F _I (x)>F _I (y); if F _I (a)>F _I (b), then a is considered to be better than b.

Preferably, in the multi-objective optimization method based on the combination of the indicator and the direction vector, the step S100 specifically includes:

Step S101, initializing the direction vector λ=(λ ₁ , λ ₂ , . . . , λ _m ) ^T , wherein

Step S102: Obtain an angle between the i-th direction vector and the remaining N-1 direction vectors in the initialization direction vector λ, and obtain a minimum value a _i between the direction vectors;

Step S103, randomly generating an initial evolutionary population EP=(x ¹ , . . . , x ^N ); wherein the fitness value of the individual ⁱ is F(x ⁱ ), i∈{1, 2, . . . , N}, The size of the EP is N;

Step S104, setting the current iteration number gen=0;

Step S105, initializing an ideal point vector z ^* = (z ₁ ^* , ..., z _m ^* ), where z _k ^* =min(f _k (x ⁱ )), i∈{1,...,N} ,k∈{1,...,m}.

Preferably, in the multi-objective optimization method based on the combination of the indicator and the direction vector, the step S200 specifically includes:

Step S201, randomly selecting the i-th sub-problem, the value of i is between 1 and N, and the i-th sub-question can only be selected once;

Step S202: randomly selecting two individuals k and l as replicas from the initialized evolutionary population EP, and generating the new individual y by the individual x ^k corresponding to the kth sub-question and the individual x ^l corresponding to the lth sub-problem, when the new individual y Step S203 is performed when the range of the decision space Ω exceeds the preset, and step S204 is performed when the new individual y does not exceed the range of the decision space Ω set in advance;

Step S203, re-randomly generating a new solution and replacing the new individual y;

Step S204, calculating an objective function value vector F(y)=(f ₁ (y), . . . , f _m (y)) of the new individual y;

Step S205, updating the ideal point vector to be z' ^* = (z ₁ ' ^* , ..., z' _m ^* ), where z' _k ^* =min(z' _k ^* , f _k (y)), k∈ {1,...,m};

Step S206, placing the new individual y in the new individual set Y, where Y=Y+{y}, wherein the initial value of the new individual set φ is φ.

In step S201, the problem corresponding to the i-th direction vector in the initialization direction vector λ=(λ ₁ , λ ₂ , . . . , λ _m ) ^T is the i-th sub-problem, and the sub-problem here is not to convert the multi-objective For a single target, here is just the solution corresponding to the i-th direction vector is called the solution of the i-th sub-problem. The subproblem is just a name, only related to the direction vector. The role of the sub-problem is to associate the solution with a uniformly distributed direction vector.

When randomly selecting the i-th sub-problem, the computer randomly generates a random number from 1 to N, that is, each integer from 1 to N is selected with the same probability, but here it is set to if this number appears Once, it will not be selected again next time.

After the execution of step S203 is completed, step S205 is performed, and after the execution of step S204 is completed, step S205 is also directly performed.

The simulated binary crossover operator (SBX) is used for the evolutionary population initialized for continuous optimization problems. At the time of the first evolution, the new individual produced N new individuals from the EP of size N, at which point the solutions in the EP were not all non-inferior solutions. But from the second evolution, the EP left a non-inferior solution, which may be smaller than N or larger than N, but not more than 2N. Because only a maximum of 2N non-inferior solutions are retained in the EP.

When the non-inferior solution of the evolutionary document exceeds twice the initial population size, the direction vector and the index are used respectively to determine the retention of the non-inferior solution. The design idea is to assign N nearest non-inferior solutions to the direction vector, leaving The non-inferior solution is sorted by the binary quality indicator, retaining the best N non-inferior solutions, so the size of the evolution document here is set to twice the working population. Part of it is determined by the direction vector, and part is determined by the index fitness value. Priority is given to the direction vector, and the non-inferior solution with the smallest angle of all direction vectors is selected. Here, not every direction vector can really participate in the evolution, for example, when all non-inferior solutions to the direction vector have the smallest angle ratio When the minimum angle between the direction vectors is large, the direction vector does not participate in the selection of non-inferior solutions, and then an individual is selected by the indicator-based selection method. After the non-inferior solution with the smallest angle of the direction vector is selected, the I _{ε +} index technique is used to guide the document selection, and each time the individual with the lowest fitness value is deleted until the individual selected by the direction vector and the individual selected by the indicator When the sum is 2N, the total number of non-inferior solutions of the evolutionary document is always no more than 2N.

Specifically, the step S300 specifically includes:

Step S301, combining the new individual set Y with the initialized evolutionary population EP to obtain the combined evolutionary population EP', wherein EP'=Y∪EP, wherein the size of the combined evolutionary population EP' is recorded as _Np , where _Np =sizeof (EP);

Step S302: Obtain all non-dominated solutions in the merged evolved population EP', and place them in the non-dominated solution set S, wherein the initial value of the non-dominated solution set S is φ, and the size of the non-dominated solution set S is recorded as N', where N'=sizeof(S);

Step S303, emptying the merged evolved population EP';

Step S304, when N'≤2N, the cleared EP' is set equal to the non-dominated solution set S, and when N'>2N, according to ag _i =min(angle(F(x _j ), λ ⁱ )) Obtaining an individual x _k from the minimum angle of the i-th direction vector in the non-dominated solution set S, where k ∈ [1, N'], j = {1, ..., N'}, x ∈ S;

Step S305, determining whether the agi corresponding to the individual x _{k of} the minimum angle of the i-th direction vector is smaller than the minimum value a _i between the direction vectors, and if the ag _{i is} smaller than a _i , the EP'=EP'+{x _k }x ⁱ ∈S and S=S/{x _k };

Step S306, calculating the fitness value of the individual x ⁱ in the non-dominated solution set S

And obtain the fitness value of the individual x ⁱ

Take the value x for the individual x ^d , where

The value of i ranges from 1 to N'-2N;

Step S307, if

Here, the distance between the direction vectors is determined by the angle of the angle. The distance from the individual to the direction vector is also determined by the angle, because the length of the direction vector is generally about 1, so the distance between the direction vectors is also about 1. When the target vector of a solution is very large, the distance between the distance to the direction vector and the direction vector is not comparable, so that it is impossible to judge whether the direction vector has a role in the solution space. But no matter how large the target vector of the solution is, the angle between the angle between the solution and the vector will never change, and for all non-inferior solutions, the individual to the shortest distance of the vector, and this vector The angle must also be the smallest. By means of the angle, it can be used not only to determine the individual closest to the direction vector distance, but also to determine whether this direction vector plays a role in this evolution.

As shown in Fig. 2a - Fig. 2c, the top four points in Fig. 2a represent the Pareto optimal solution of DTLZ7 at three targets, and the straight line indicates the direction of uniform distribution; in Fig. 2b, the Pareto is the most DTLZ7 at three targets. Excellent solution. If there is an individual with the smallest angle in each direction, the individuals with the smallest angle to the vector in each direction may be concentrated in one area, while other Pareto optimal areas may not have individuals, as shown in Figure 2c. Shown. Therefore, many direction vectors do not play a role in improving the diversity of the population. Instead, the optimal individuals obtained by a large number of direction vectors are basically concentrated in a certain block area. Therefore, all the direction vectors should not be assigned the same individual resources. When the individual with the smallest angle from the direction vector is smaller than the minimum angle of the direction vector to the other direction vector, the direction vector individual resource is allocated to retain the individual; and when the angle is smaller than the direction vector When the direction vector is larger than the other direction vector, the minimum angle is not allocated, and the individual resources are not allocated. The optimal individual is not selected in this direction vector, and the individual resources are left to be selected based on the indicator.

The angle θ between the X individual and the λ direction vector does not need to be calculated at the time of calculation, because the magnitude of θ is always between 0 and π/2, so θ is positively correlated with sin θ, and θ can be replaced by the value of sin θ. The value of this will not affect the result of the comparison.

and so

A schematic diagram of the angle θ between the X individual and the λ direction vector is shown in FIG. 4 .

For the evolutionary document EP, the best non-dominated solution is always stored. The maximum size of the EP is 2N, that is, the maximum non-dominated solution is stored after the evolution of the EP. In the evolution process, the solutions in the newly generated individual set Y and EP are first merged into the EP, and then the non-inferior solution in the EP is saved to the memory S, and the size of the S is N', and the EP is also The non-inferior solution in the empty. If the total number of individuals in S is less than 2N at this time, S is directly saved to the EP.

If the total number of individuals in S is greater than 2N, the non-inferior solution closest to each direction vector is first selected, and this non-inferior solution is retained in the EP, and this non-inferior solution is removed from S. In this way, up to N non-inferior solutions closest to the direction vector can be selected in the EP, but at least one non-inferior solution can not be selected, because it is possible that these non-inferior solutions are not very close to all the direction vectors ( Relative to the direction vector with the smallest angle to the direction vector). Because the EP retains up to 2N non-inferior solutions, no matter how many non-inferior solutions are selected from the direction vector, S also deletes N'-2N non-non-distributed non-inferior Inferior solution. Because the non-inferior solutions that were previously removed from S are not actually deleted, but are preferentially entered into the EP, and S is originally to delete N'-2N non-inferior solutions. Once these non-inferior solutions are deleted, they will not be Retained in the EP is a non-inferior solution that is abandoned in the evolution of the population. Therefore, if the non-inferior solution selected by the direction vector is less, the non-inferior solution retained by the indicator mode will be more, thus ensuring that 2N non-inferior solutions can always be retained after evolution in the EP.

Use the index to select the better non-inferior solution. Firstly, each non-dominated solution in S after removing the non-inferior solution set that is closer to the direction vector needs to calculate the I _ε+ index fitness by formula (3-3). Value, and then find the individual d with the smallest fitness value in S. The fitness values of the remaining non-dominated solutions need to be recalculated. According to the fitness index fitness value calculation definition (3-3), each non-inferior solution new fitness The value is equal to the individual fitness value minus the ε indicator addition term between the individual and the individual. As a result, the computational complexity of the algorithm is not very high. If the size of S is still greater than 2N-sizeof (EP), then continue to discard the non-inferior solution with the smallest fitness value in the remaining S, and recalculate the fitness values of other non-inferior solutions. Until the number of non-inferior solutions in S is equal to 2N-sizeof(EP), the non-inferior solution is no longer discarded, and finally the optimal non-dominated solutions in S are all added to the EP.

When the number of non-dominated solutions in the memory S is too large, it is necessary to delete the worst non-inferior solution in one S at a time, instead of deleting the worst N'-2N non-inferior solutions in S at one time. Because if you delete multiple individuals with the least fitness at one time, you may delete several consecutive non-inferior solutions, which will lose some information with higher information, which is not conducive to the evolution of the population. Assume that there are at most 6 individuals in this collection, and the extra individuals need to be deleted. The individuals a to i in Fig. 3a are non-dominated solutions, while the three individuals c, d and e in the A region are closely close together, so the fitness values of the three individuals c, d and e are relatively high. Individuals will be smaller. If three individuals are deleted at a time, the three individuals will be deleted together, as shown in Figure 3b, so that one individual in the A region is not retained, which will result in insufficient distribution of the solution. Uniform, and the diversity is huge. If only one individual is deleted at a time, the d individual with the smallest fitness value will be deleted first, and then the fitness value of the other individual will be recalculated, and the individual with the smallest fitness value will be changed from the e individual to the f individual, because at this time, the f individual The e individuals after the deletion of d are more dense, so that a more uniform non-inferior solution is obtained, and the diversity loss of the solution set is relatively less, as shown in Fig. 3c.

Based on the above method, the present invention also provides a multi-objective optimization system based on combining indicators and direction vectors. As shown in FIG. 5, the multi-objective optimization system based on combining indicators and direction vectors includes:

An initialization module 100, configured to initialize a direction vector, an evolutionary population, and an ideal point vector;

a new individual generation module 200, configured to generate a new individual according to the initialized evolved population;

The iterative output module 300 is configured to merge the new individual with the initialized evolutionary population, obtain all non-dominated solutions in the merged evolved population, and iterate the merged evolved population until the number and initialization of the non-dominated solutions in the merged evolved population The evolutionary populations are equal in size and output the solution corresponding to the evolved population after iteration.

Preferably, in the multi-objective optimization system based on the combination of the indicator and the direction vector, the initialization module 100 specifically includes:

Setting unit for setting the current iteration number gen=0;

Preferably, in the multi-objective optimization system based on the combination of the indicator and the direction vector, the evolved population initialized in the new individual generation module 200 generates a new individual according to the simulated binary crossover operator or the backpack operator.

Preferably, in the multi-objective optimization system based on the combination of the indicator and the direction vector, the new individual generation module 200 specifically includes:

And generating a new individual determining unit configured to initialize the evolving population from EP two randomly selected individuals k and l as a copy, and issue corresponding to the k-th individual x ^k and l corresponding to the individual sub-problems generated new individual X ^l y, when the new individual y exceeds the range of the preset decision space Ω, the new solution replacement unit is started, and when the new individual y does not exceed the range of the preset decision space Ω, the target function value vector calculation unit is started;

Preferably, in the multi-objective optimization system based on the combination of the indicator and the direction vector, the iterative output module 300 specifically includes:

Emptying the unit for emptying the merged evolved population EP';

The individual acquisition unit is configured to set the cleared EP′ to be equal to the non-dominated solution set S when N′≤2N, and to ag _i =min(angle(F(x _j ),λ when N′>2N) ⁱ )) obtaining the individual x _k from the minimum angle of the i-th direction vector in the non-dominated solution set S, where k ∈ [1, N'], j = {1, ..., N'}, x ∈ S;

a second angle acquiring unit, configured to determine whether the ag _i corresponding to the individual x _{k of} the minimum angle of the i-th direction vector is smaller than the minimum value a _i between the direction vectors, and if the ag _{i is} less than a _i '=EP'+{x _k },x ⁱ ∈S and S=S/{x _k };

And obtain the fitness value of the individual x ⁱ

Take the value x for the individual x ^d , where

The value of i ranges from 1 to N'-2N;

Iterative unit for use in

In summary, the present invention provides a multi-objective optimization method and system based on combining indicators and direction vectors, including: initializing a direction vector, an evolutionary population, and an ideal point vector; and generating a new individual according to the initialized evolved population; The new individual is merged with the initialized evolutionary population to obtain all the non-dominated solutions in the merged evolutionary population, and the merged evolutionary population is iterated until the number of non-dominated solutions in the merged population is equal to the size of the initialized evolutionary population. And output the solution corresponding to the evolved population after iteration. The invention can be used to replace the Pareto dominant relationship, and effectively alleviate the problem that the selection pressure caused by the excessive proportion of non-dominated individuals becomes small. Moreover, the binary ε index strictly satisfies the Pareto dominant consistency, the computational complexity is lower than the index, and no additional parameter setting is required, and the calculation is simple.

It is to be understood that the application of the present invention is not limited to the above-described examples, and those skilled in the art can make modifications and changes in accordance with the above description, all of which are within the scope of the appended claims.

Claims

A multi-objective optimization method based on combining indicators and direction vectors, comprising the steps of:

A. Initialize the direction vector, the evolutionary population, and the ideal point vector;

B. Generating a new individual based on the initialized evolutionary population;

C. Combine the new individual with the initialized evolutionary population, obtain all the non-dominated solutions in the merged evolutionary population, and iterate the merged evolutionary population until the number of non-dominated solutions in the merged population and the size of the initialized evolutionary population Equal, and output the solution corresponding to the evolved population after iteration.
The multi-objective optimization method based on the combination of the indicator and the direction vector according to claim 1, wherein the step A specifically includes:

A1, the initialization direction vector λ = (λ 1 , λ 2 , ..., λ m ) T , wherein
H is a preset parameter that takes a natural number, m is the target number, and the total number of initialization direction vectors λ

A2: Obtain an angle between the i-th direction vector and the remaining N-1 direction vectors in the initialization direction vector λ, and obtain a minimum value a i between the direction vectors;

A3, the evolving population randomly generated initialization EP = (x 1, ..., x N); where x i individual fitness value F (x i), i∈ { 1,2, ..., N}, EP The size is N;

A4, setting the current iteration number gen=0;

A5. Initialize the ideal point vector z * = (z 1 * , ..., z m * ), where z k * =min(f k (x i )), i ∈ {1,...,N}, K∈{1,...,m}.
The multi-objective optimization method based on combining the indicator and the direction vector according to claim 1, wherein the evolved population initialized in the step B generates a new individual according to the simulated binary crossover operator or the backpack operator.
The multi-objective optimization method based on the combination of the indicator and the direction vector according to claim 3, wherein the step B specifically includes:

B1, randomly selecting the i-th sub-problem, the value of i is between 1 and N, and the i-th problem can only be selected once;

B2, from the evolving population initialization EP two randomly selected individuals k and l as a copy, and issue a corresponding individual k-th and l x k corresponding to the individual sub-problems a new individual X l y, when y exceeds new individual Step B3 is performed in the range of the preset decision space Ω, and step B4 is performed when the new individual y does not exceed the range of the preset decision space Ω;

B3, re-randomly generating a new solution and replacing the new individual y;

B4, calculating a new individual objective function value vector y F (y) = (f 1 (y), ..., f m (y));

B5, update the ideal point vector to
among them

B6. Place the new individual y in the new individual set Y, where Y=Y+{y}, where the initial value of the new individual set φ is φ.
The multi-objective optimization method based on the combination of the indicator and the direction vector according to claim 1, wherein the step C specifically includes:

C1, the new individual set Y is merged with the initialized evolutionary population EP, and the combined evolutionary population EP' is obtained, wherein EP'=Y∪EP, wherein the size of the combined evolutionary population EP' is recorded as Np , where Np = sizeof( EP);

C2, obtain all non-dominated solutions in the merged evolutionary population EP', and place them in the non-dominated solution set S, where the initial value of the non-dominated solution set S is φ, and the size of the non-dominated solution set S is denoted as N ', where N'=sizeof(S);

C3, emptying the merged evolutionary population EP';

C4. When N'≤2N, the cleared EP' is set equal to the non-dominated solution set S, and when N'>2N, it is obtained according to ag i =min(angle(F(x j ), λ i )) The non-dominant solution set S is the individual x k from the minimum angle of the i-th direction vector, where k ∈ [1, N'], j = {1, ..., N'}, x ∈ S;

C5, is determined from the i-th vector of the individual directions x k corresponding to the minimum angle is smaller than the minimum value a i agi angle between the direction of the vector, the EP '= EP' + {x k} is less than if a i agi x i ∈S and S=S/{x k };

C6. Calculating the fitness value of x i individuals in the non-dominated solution set S
And obtaining a value x i so that the fitness of individuals
Take the value x for the individual x d , where
The value of i ranges from 1 to N'-2N;

C7, if
Then iteratively is performed to obtain EP"=EP"+{x i }x i ∈S, and the size of the evolved population EP" after iteration is M=N.
A multi-objective optimization system based on combining indicators and direction vectors, comprising:

An initialization module for initializing a direction vector, an evolutionary population, and an ideal point vector;

a new individual generation module for generating a new individual based on the initialized evolved population;

An iterative output module for combining the new individual with the initialized evolutionary population, obtaining all non-dominated solutions in the merged evolved population, and iterating the merged evolved population until the number of non-dominated solutions in the merged population is initialized The evolutionary populations are equal in size and output the solution corresponding to the evolved population after iteration.
The multi-objective optimization system based on the combination of the indicator and the direction vector according to claim 6, wherein the initialization module specifically comprises:

a direction vector initializing unit for initializing a direction vector λ=(λ 1 , λ 2 , . . . , λ m ) T , wherein
H is a preset parameter that takes a natural number, m is the target number, and the total number of initialization direction vectors λ

a first angle acquiring unit, configured to acquire an angle between the i-th direction vector and the remaining N-1 direction vectors in the initialization direction vector λ, and obtain a minimum value a i between the direction vectors;

An evolutionary population initialization unit for randomly generating an initial evolutionary population EP=(x 1 ,...,x N ); wherein the fitness value of the individual i is F(x i ), i∈{1, 2,... , N}, the size of the EP is N;

Setting unit for setting the current iteration number gen=0;

An ideal point vector initialization unit for initializing an ideal point vector z * = (z 1 * , ..., z m * ), where z k * =min(f k (x i )), i ∈ {1,. ..,N},k∈{1,...,m}.
The multi-objective optimization system based on combining indicator and direction vector according to claim 6, wherein the evolved population initialized in the new individual generation module generates a new individual according to a simulated binary crossover operator or a backpack operator.
The multi-objective optimization system based on the combination of the indicator and the direction vector according to claim 8, wherein the new individual generation module specifically comprises:

a sub-question selection unit for randomly selecting the i-th sub-problem, the value of i is between 1 and N, and the i-th problem can only be selected once;

a new individual generation and judgment unit for randomly selecting two individuals k and l as a copy from the initialized evolutionary population EP, and generating a new individual for the individual x k corresponding to the kth sub-question and the individual x l corresponding to the l-th sub-question y, when the new individual y exceeds the range of the preset decision space Ω, the new solution replacement unit is started, and when the new individual y does not exceed the range of the preset decision space Ω, the target function value vector calculation unit is started;

A new solution replaces the unit for re-randomly generating a new solution and replacing the new individual y;

An objective function value vector calculation unit for calculating an objective function value vector F(y)=(f 1 (y), . . . , f m (y)) of the new individual y;

Update unit for updating the ideal point vector to
among them

A new individual set acquisition unit for placing a new individual y in a new individual set Y, where Y=Y+{y}, wherein the initial value of the new individual set φ is φ.
The multi-objective optimization system based on the combination of the indicator and the direction vector according to claim 6, wherein the iterative output module comprises:

a merging unit for combining the new individual set Y with the initialized evolutionary population EP to obtain a combined evolutionary population EP', wherein EP'=Y∪EP, wherein the size of the combined evolutionary population EP' is denoted as Np , where Np =sizeof(EP);

The non-dominated solution acquisition unit is used to obtain all non-dominated solutions in the merged evolutionary population EP', and is placed in the non-dominated solution set S, wherein the initial value of the non-dominated solution set S is φ, and the non-dominated solution set The size of S is denoted by N', where N'=sizeof(S);

Emptying the unit for emptying the merged evolved population EP';

The individual acquisition unit is configured to set the cleared EP′ to be equal to the non-dominated solution set S when N′≤2N, and to ag i =min(angle(F(x j ),λ when N′>2N) i )) obtaining the individual x k from the minimum angle of the i-th direction vector in the non-dominated solution set S, where k ∈ [1, N'], j = {1, ..., N'}, x ∈ S;

a second angle acquiring unit, configured to determine whether the ag i corresponding to the individual x k of the minimum angle of the i-th direction vector is smaller than the minimum value a i between the direction vectors, and if the ag i is less than a i '=EP'+{x k }x i ∈S and S=S/{x k };

The fitness value calculation unit is configured to calculate the fitness value of the x i individual in the non-dominated solution set S
And obtain the fitness value of the individual x i
Take the value x for the individual x d , where
The value of i ranges from 1 to N'-2N; iterative units are used for
Then iteratively is performed to obtain EP"=EP"+{x i }x i ∈S, and the size of the evolved population EP" after iteration is M=N.