Shulou(Shulou.com)06/01 Report--

NSGA2 genetic algorithm how to solve multi-objective optimization, I believe that many inexperienced people do not know what to do, so this paper summarizes the causes of the problem and solutions, through this article I hope you can solve this problem.

NSGA-II

When carrying out multi-objective optimization, we are usually faced with the situation that multiple objective functions can not be optimized at the same time. In order to solve this contradiction, the concept of Pareto-Optimality is introduced.

Pareto-Optimality

In general, the general form of multi-objective optimization is:

After processing, it can be transformed into the following forms:

Among them

F1 (x), f2 (x),..., fn (x)

Is the objective function, all of which are in the form of finding the minimum.

The following discusses the two objective functions:

Several objective functions are multidimensional space, and there are two objective functions Time (F1 (x)) and Cost (f2 (x)).

You can draw an image:

Then several concepts are introduced:

Non-dominant solution: assuming that any two solutions S1 and S2 are better than S2 for all objectives, then we say S1 dominates S2. If the solution of S1 is not dominated by other solutions, S1 is called non-dominant solution (undominated solution), also known as Pareto solution.

Dominant solution: if all the goals of solving S2 are worse than S1, then S1 is said to be superior to S2, also known as S1 dominates S2.

, S2 is the dominated solution.

So the first task now is to find all the Pareto solutions in the solution space. after finding all the Pareto solutions, the plane formed by these solutions is called the Pareto frontier surface (Non-dominated front). When there are many objective functions, the front surface is usually hypersurface.

Non-dominant solution sorting (Non-dominated Sorting)

1. Let the set of all solutions be S, and now find out the set of non-dominant solutions, which is marked as F1.

two。 Let S=S-F1 find the set of non-dominant solutions from S, and write it down as F2.

3. Repeat step 2 until S is an empty set

The non-dominant solutions found each time are sorted as follows:

{F1 and F2, … , Fn}

On the way, draw the corresponding points in the Fi set, and connect the lines, then form n pareto surfaces, numbered as Non-dominated Front 1 and Nonlinearity Front 2.

Take the data in the above table as an example: F1 = {A ~ ~ B ~ D ~ D}, F _ 2 = {C ~ E ~ D}, F _ 3 = {H ~ I}.

Draw the corresponding figure:

The solution on the first front has the maximum fitness, and the larger the ordinal number is, the smaller the fitness is. The solution on the front surface with small sequence number can dominate the solution on the front surface with large sequence number.

Ranking of solutions on the same frontier surface-congestion degree (Crowding Distances)

For the first frontier surface, it contains four solutions of A _ MagneB _ D _ D _ F, how to judge the fitness of these four solutions? As a result, the concept of congestion is introduced.

Calculation of congestion:

1. Only the solution on the same front surface is considered, and the congestion degree at the boundary points at both ends of the front surface is set to ∞.

two。 For the points not at both ends, the degree of congestion is mainly related to the two adjacent points.

The smaller the degree of congestion, the more important it is to solve the problem.

A more popular understanding: the smaller the congestion degree, the lower the similarity between the solution and other solutions, and keeping the points with less congestion is equivalent to preserving the diversity of the solution.

Therefore, to determine the fitness order of the solution, we should first determine which frontier the solution is on, and then calculate the congestion degree if it is on the same frontier.

Combined with genetic algorithm

The steps are about the same as those of ordinary genetic algorithms, initializing random solutions for coding, cross-swapping, and mutation

Generate offspring

However, after the generation of offspring, it needs to be mixed with the parent to select the solution with high fitness to re-form the offspring, and then carry on a new round of iteration.

Examples are as follows:

1. In order to solve a two-objective optimization problem, 10 solutions are randomly selected as F in initialization, and it is calculated that the offspring is P.

At this time, PBG F is mixed to form a new solution set S

two。 For S, sort the non-dominant solutions introduced above, calculate the congestion degree, and finally get the fitness order of the 12 solutions, from which 10 points with high fitness are selected to generate new children (maintain the same number as the parent generation). Bring the algorithm for a new round of iteration

Mixed screening of offspring and parents to produce new offspring, which seems to be called elite strategy.

Any heuristic algorithm consists of two aspects: the operation of accelerating convergence and the operation of maintaining the diversity of solutions in the process of convergence, which interact with each other so as to find an appropriate convergence speed and reduce computing time. At the same time, avoid falling into local optimization.

For NSGA, its rules still meet these two guidelines:

1. The purpose of this algorithm is not to take only the optimal frontier surface, but to take all the frontier surfaces into consideration, in order to reflect the diversity of solutions and prevent falling into local optimization.

two。 The purpose of calculating the congestion degree is to preserve the solutions with low similarity and to maintain the diversity of the solution space.

3. The elite strategy is used to accelerate convergence and get rid of bad solutions more quickly.

After reading the above, have you mastered how NSGA2 genetic algorithm can solve multi-objective optimization? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.