NSGAII algorithm
The basic idea of NSGA-i II algorithm is as follows: Firstly, an initial population of N size is randomly generated, and the first generation of offspring population is obtained through the three basic operations of selection, crossover and mutation of genetic algorithm after non-dominated sorting. Secondly, starting from the second generation, the parent population was combined with the offspring population to carry out a rapid non-dominated sorting, and the crowding degree of individuals in each non-dominated layer was calculated. Suitable individuals were selected to form the new parent population according to the non-dominant relationship and the crowding degree of individuals. Finally, a new population of offspring is generated by the basic operation of the genetic algorithm: and so on until the end-of-program condition is met. The corresponding program flow chart is shown in the figure below.
3.1 Fast non-dominated sorting algorithm
3.2 Crowding and crowding comparison operator
Crowding refers to the density of individuals around a given individual in a population, which can be expressed intuitively as individuals. There are only individuals around. The length of the largest rectangle itself, denoted by nd,
The algorithm of congestion is as follows:
3.3 Crowding comparison operator
3.3 Comparison of the two algorithms and improvement of generation II:
Non-dominated sorting genetic algorithm (NSGA) has been applied in many problems, but NSGA still has some problems:) A has high computational complexity, O(mN3)(m is the number of objective functions,N is the population size), so when the population is large, the calculation is time-consuming. B) There is no elite strategy; The elitist strategy can accelerate the execution speed of the algorithm, and to some extent, it can ensure that the satisfactory solutions found will not be lost. C The share radius needs to be specified.
NSGA I II has made improvements in the following three aspects to address the above defects:
) A proposed a fast non-dominated sorting method, which reduced the computational complexity of the algorithm. From the original O(mN3) to O(mN2), where m is the number of objective functions and N is the population size. B) Crowding and crowding comparison operators are proposed to replace fitness sharing strategies that need to specify sharing radius, and are used as the winning criteria in peer comparison after quicksort, so that individuals in the quasi-paroet domain can extend to the whole Pareto domain and evenly distribute, maintaining the diversity of the population.) C Introduce elite strategy to expand sampling space. Combining the parent population with its offspring population and competing to produce the next generation population is beneficial to keep the excellent individuals in the parent generation into the next generation, and through the layered storage of all individuals in the population, the best individuals will not be lost and the population level will be rapidly improved.
References:
1, Research and Application of Non-dominated Sorting Genetic Algorithm with Elite Strategy
clc; clear all; close all; rand('seed',1e5); % data_all=xlsread('data.xlsx'); data_ori=xlsread('data_ori.xlsx'); % Global omg1; % weight 1 Time cost global OMg2; % weight 2 Freight cost global Po; % position global need; % demand global c; % freight global gd_c; % fixed freight global w; % Vehicle load vector form global car_num; % Number of cars global ORI; %0 coordinates %global color; % Route color global w_HOME; %global kehu_num; % Number of affected spots global Cij; % road capacity global yij; % Actual traffic volume global ck_num; % Number of warehouses global r; global m; global v; global dis_max; % Maximum distance global YunfeixISHU; Omg1 = 0.7; Omg2 = 0.3; po=data_all(:,1:2); need=data_all(:,3); c=15; gd_c=200; W = 30,30,30 []; W_home = [1, 2, 3]; %color=['k','k','m','m','g','g','b','b','r','r']; car_num=length(w); ORI=data_ori; [kehu_num,~]=size(data_all); Cij=1000; ck_num=size(ORI,1); yij=unidrnd(600,[kehu_num+ck_num,kehu_num+ck_num]); R = 0.15; m=4; v=50; dis_max=100; yunfeixishu=1e-3; tic; f_num=1; x_num=kehu_num; X_min =zeros(1,x_num); % decision variable minimum array initialization x_max=zeros(1,x_num); % decision variable maximum array initialization x_min(:)=1+0.001; X_max (:) = car_num + 0.999; pop=5e3; % population size gen=50; % evolution algebra PC =0.90; % cross probability PM =0.9; % mutation probability yITA1 =20; % analog binary cross parameter yITa2 =20; % polynomial variation parameter pf1=zeros(1,gen); px=1:1:gen; % chromo=initialize(POP, f_NUM,x_num,x_min,x_max); For II =1:gen % binary race select (K took POP /2, so choose twice) chromo_parent_1 = Tournament_selection (Chromo,x_num); chromo_parent_2 = tournament_selection(chromo,x_num); chromo_parent=[chromo_parent_1;chromo_parent_2]; Simulated binary crossover and polynomial variation chromo_offspring=cross_mutation(chromo_parent, F_NUM, X_NUM, X_min, X_max, PC, PM, YITA1, YITA2); [pop_parent,~]=size(chromo); [pop_offspring,~]=size(chromo_offspring); combine_chromo(1:pop_parent,1:(f_num+x_num))=chromo(:,1:(f_num+x_num)); combine_chromo((pop_parent+1):(pop_parent+pop_offspring),1:(f_num+x_num))=chromo_offspring(:,1:(f_num+x_num)); % elite retention produces next generation population chromo=elitism(POP,combine_chromo, F_NUM,x_num); If mod(ii,1) == 0 fprintf('%d generation completed.\n',ii); end pf1(ii)=mean(chromo(:,x_num+1)); end toc; time=toc; figure(1); plot(px,pf1); Xlabel (' number of iterations '); Ylabel (' average value of objective function within population '); grid on; uncode(chromo(1,:),f_num,x_num);Copy the code
