【笔记2021-11-19】NSGAII代码 MATLAB_max_range_of_decesion_variable

1. nsga_2.m

function nsga_2(pop,gen)
% 函数名字叫nsga_2，参数是pop=种群大小，gen遍历的代数

%% 检测输入的各种问题

if nargin < 2 % nargin是MATLAB中管参数数量的
% 要是参数数量小于2说明少输入了
    error('NSGA-II: Please enter the population size and number of generations as input arguments.');
end

% 两个输入参数都需要为整数数据类型
if isnumeric(pop) == 0 || isnumeric(gen) == 0
    error('Both input arguments pop and gen should be integer datatype');
end
% 最小人口数必须为20个人，最小代数为5
if pop < 20
    error('Minimum population for running this function is 20');
end
if gen < 5
    error('Minimum number of generations is 5');
end
% 确保pop和gen是整数
% round函数用于舍入到最接近的整数
pop = round(pop);
gen = round(gen);


%% 目标函数
%M是目标空间的维数，V是决策变量空间的维数。min_range和max_range是决策变量空间中变量的范围
%用户必须使用决策变量定义目标函数。确保编辑函数“ evaluate_objective”以适合您的需求。
[M, V, min_range, max_range] = objective_description_function();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

截止到这里，nsga_2.m文件没有完----1
objective_description_function()是另一个.m文件，在下边
1----接nsga_2.m文件

%% 初始化种群
%在特定范围内的随机值来进行种群的初始化，每个染色体都是由决策变量组成，同时目标函数，rank等级和拥挤距离信息的值也被添加到染色体向量中
%但是只有当中含有函数决策变量的向量元素才会进行遗传的操作，比如交叉变异（这一步不是全部都要执行的）

chromosome = initialize_variables(pop, M, V, min_range, max_range);


%% 初始化种群的排序
%使用非支配排序对总体进行排序。 会为每个个体返回两列，这两列的内容是所处位置对应的rank等级和拥挤度距离
%对每条染色体来说，添加rank等级和拥挤度距离到染色体向量中，以便于计算

chromosome = non_domination_sort_mod(chromosome, M, V);

%% 开始进化过程
% 在每一代中执行以下操作
% * 选择适合繁殖的父代
% * 对选定的父代执行交叉和变异的操作
% * 从父代和其后代中进行选择
% * 用适合的个体替换不适合的个体，以维持恒定的人口规模。

for i = 1 : gen
    % 选取父代，产生子代，原始的NSGA-II是基于拥挤度比较算子通过binary tournament selection二进制竞标赛选择
    % The arguments are 
    % pool - 交配池的大小，通常来说是种群数量的一半
    % tour - 竞标赛大小. 二级制竞标赛选择，但是要查看这个竞标赛大小的影响，这个是任意的，是由用户决定的
    pool = round(pop/2);
    tour = 2;
    % 选择过程
    %二进制随机数和它们的适应度进行比较，适应度高的个体被选为作为父代，比赛选择一直到交配池满为止，
    %一般来说池的大小就是被选择作为父代的个数
    %函数tournament_selection输入的参数是 染色体、交配池大小、竞标赛大小
    
    %该函数仅使用来自染色体向量中最后两个元素的信息。最后一个元素具有拥挤距离信息，而倒数第二个元素rank等级的信息。
    %选择基于rank等级，如果遇到具有相同等级的个人，则比较拥挤距离。 较低的等级和较高的拥挤距离是选择标准。
    
    
    parent_chromosome = tournament_selection(chromosome, pool, tour);

    % 进行交叉和变异操作
    %原始的NSGA-II算法使用模拟二进制交叉（SBX）和多项式变异。 交叉概率pc = 0.9，变异概率为pm = 1 / n，
    %其中n是决策变量的数量。 在原始算法中同时实现了实编码GA和二进制编码GA，而在此程序中，仅考虑了实编码GA。 
    %交叉算子和变异算子的分布指数分别为mu = 20和mum = 20。
    % The original NSGA-II algorithm uses Simulated Binary Crossover (SBX) and
    % Polynomial  mutation. Crossover probability pc = 0.9 and mutation
    % probability is pm = 1/n, where n is the number of decision variables.
    % Both real-coded GA and binary-coded GA are implemented in the original
    % algorithm, while in this program only the real-coded GA is considered.
    % The distribution indeices for crossover and mutation operators as mu = 20
    % and mum = 20 respectively.
    mu = 20;
    mum = 20;
    offspring_chromosome = ...
        genetic_operator(parent_chromosome, ...
        M, V, mu, mum, min_range, max_range);

    % Intermediate population（中间种群）
    %中间种群是当前这一代父母和后代的总人口。 人口规模是初始人口的两倍。
    
    [main_pop,temp] = size(chromosome);
    [offspring_pop,temp] = size(offspring_chromosome);
    % temp 是一个虚拟变量.
    clear temp
    % intermediate_chromosome 是当前种群和后代种群的串联（中间种群）
    intermediate_chromosome(1:main_pop,:) = chromosome;
    intermediate_chromosome(main_pop + 1 : main_pop + offspring_pop,1 : M+V) = ...
        offspring_chromosome;

    % 中间种群的非支配排序
    %在对中间种群进行替换操作之前，中间种群再一次进行排序，这次的排序是基于非支配排序的
    
    intermediate_chromosome = ...
        non_domination_sort_mod(intermediate_chromosome, M, V);
    % 执行选择
    %一旦对中间种群进行排序，根据rank等级和拥挤度距离来进行选优的
    %每个前沿都以升序填充，直到达到人口总数为止。
    
    
    %种群的最后一层，是根据拥挤度距离判断的
    %（这个注意，在填充最后一层的时候，一般都是在一个同一个大的等级中去选择，这时候比较的就是拥挤度距离了，这也是这个算法拥挤度距离的使用之处）
    
    
    % The last front is included in the population based on the individuals with
    % least crowding distance
    chromosome = replace_chromosome(intermediate_chromosome, M, V, pop);
    if ~mod(i,100)
        clc
        fprintf('%d generations completed\n',i);
    end
end

%% Result结果
% Save the result in ASCII text format.将结果保存为ASCII文本格式。
save solution.txt chromosome -ASCII

%% Visualize可视化
% 如果目标空间的尺寸是可视的，则以下内容用于可视化结果。
if M == 2
    plot(chromosome(:,V + 1),chromosome(:,V + 2),'*');
elseif M ==3
    plot3(chromosome(:,V + 1),chromosome(:,V + 2),chromosome(:,V + 3),'*');
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

2. objective_description_function.m

function [number_of_objectives, number_of_decision_variables, min_range_of_decesion_variable, max_range_of_decesion_variable] = objective_description_function()
% 四个返回的值是：目标函数个数、决策变量个数、决策变量最小范围、最大范围
%  %sprintf函数将数据格式化为字符串或字符向量。估计意思就是提醒用户输入目标函数维度
g = sprintf('Input the number of objective: ');
% 获得目标函数数
% Obtain the number of objective function
%  %input输入的东西当成数字或者矩阵；就是把字符串的g转化成数字
number_of_objectives = input(g);
if number_of_objectives < 2
   error('This is a multi-objective optimization function hence the minimum number of objectives is two');
end
g = sprintf('\nInput the number of decision variables: ');
% 获取决策变量的数量
% Obtain the number of decision variables
number_of_decision_variables = input(g);
clc
for i = 1 : number_of_decision_variables
   clc
   g = sprintf('\nInput the minimum value for decision variable %d : ', i);
   % 获得每个决策变量的最小可能值
   % Obtain the minimum possible value for each decision variable
   min_range_of_decesion_variable(i) = input(g);
   g = sprintf('\nInput the maximum value for decision variable %d : ', i);
   % 获得每个决策变量的最大可能值
   % Obtain the maximum possible value for each decision variable
   max_range_of_decesion_variable(i) = input(g);
   clc
end
g = sprintf('\n Now edit the function named "evaluate_objective" appropriately to match your needs.\n Make sure that the number of objective functions and decision variables match your numerical input. \n Make each objective function as a corresponding array element. \n After editing do not forget to save. \n Press "c" and enter to continue... ');
%提示用户编辑evaluate_objective函数，并等待直到按下“ c”。
% Prompt the user to edit the evaluate_objective function and wait until
% 'c' is pressed.
x = input(g, 's');%输入的东西当成字符串存起来；
if isempty(x)
   x = 'x';
end
while x ~= 'c'% ~=是不等于的意思
   clc
   x = input(g, 's');
   if isempty(x)
       x = 'x';
   end
end    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3. initialize_variables.m

function f = initialize_variables(N, M, V, min_range, max_range)

%% function f = initialize_variables(N, M, V, min_tange, max_range) 
%这个函数来初始化种群的，每个染色体都有着如下的步骤
% This function initializes the chromosomes. Each chromosome has the
% following at this stage
%       * set of decision variables 设定决策变量
%       * objective function values  目标函数值
% 
% where,
% N - Population size 种群的大小
% M - Number of objective functions 目标函数的数量
% V - Number of decision variables 决策变量的数量
% min_range - A vector of decimal values which indicate the minimum value
% for each decision variable.十进制值的向量，指示每个决策变量的最小值
% max_range - Vector of maximum possible values for decision
% variables.决策变量的最大值  


min = min_range;
max = max_range;
%K是数组元素的总数。为了便于计算，将决策变量和目标函数连接
%在一起以形成单个数组。 对于交叉和变异，仅使用决策变量，而对于选择，仅使用目标变量。
% K is the total number of array elements. For ease of computation decision
% variables and objective functions are concatenated to form a single
% array. For crossover and mutation only the decision variables are used
% while for selection, only the objective variable are utilized.

K = M + V;

%% Initialize each chromosome 初始化每条染色体
%每条染色体都会执行以下操作
% For each chromosome perform the following (N is the population size)
for i = 1 : N
    %根据最小值和最大值初始化决策变量可能的值。 
    %V是决策变量的数量。 在每个决策变量的最小和最大值之间选择一个随机数。
    % Initialize the decision variables based on the minimum and maximum
    % possible values. V is the number of decision variable. A random
    % number is picked between the minimum and maximum possible values for
    % the each decision variable.
    for j = 1 : V
        f(i,j) = min(j) + (max(j) - min(j))*rand(1);
    end
    %为了方便计算，染色体最后连接了目标函数的值，元素V + 1 到 K是具有目标函数值的
    % For ease of computation and handling data the chromosome also has the
    % vlaue of the objective function concatenated at the end. The elements
    % V + 1 to K has the objective function valued. 
    
    
    %函数evaluate_objective每次只获取一条染色体
    %实际上，只有决策变量与有关已处理目标函数数目的信息一起传递给函数，并返回目标函数的值。 这些
    %值现在存储在染色体本身的末尾。
    % The function evaluate_objective takes one chromosome at a time,
    % infact only the decision variables are passed to the function along
    % with information about the number of objective functions which are
    % processed and returns the value for the objective functions. These
    % values are now stored at the end of the chromosome itself.
    f(i,V + 1: K) = evaluate_objective(f(i,:), M, V);
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

4. non_domination_sort_mod.m

function f = non_domination_sort_mod(x, M, V)

%% function f = non_domination_sort_mod(x, M, V)
%这个函数进行非支配排序，所有个体在第一层的rank等级是1，在第二层的rank等级是2，以此类推
%等级分配完成后，计算每个前沿的拥挤度


[N, m] = size(x);
clear m

%初始化当前的层级号为1
% Initialize the front number to 1.
front = 1;

%此作业没有任何内容，仅用于轻松操作的MATLAB
% There is nothing to this assignment, used only to manipulate easily in
% MATLAB.
F(front).f = [];
individual = [];

%% Non-Dominated sort. 非支配排序
%初始化的种群基于非支配性进行排序。 快速排序算法[1]如下所述
% The initialized population is sorted based on non-domination. The fast
% sort algorithm [1] is described as below for each

%对于每个种群P当中的个体p都有着如下的操作
% ? for each individual p in main population P do the following
%  Sp是一个集合，代表着你在支配着谁，这个[]里面写的是种群的个体
%  该集合包含着所有由p支配的个体
%   ? Initialize Sp = []. This set would contain all the individuals that is
%     being dominated by p.
%  np是一个数，代表着有多少人支配着你
%  这就是支配p的个体数量。
%   ? Initialize np = 0. This would be the number of individuals that domi-
%     nate p.
%   对于P种群的个体q来说（种群的另一个个体）
%   ? for each individual q in P
%  如果p支配q，那么就把q放进Sp的集合中
%       * if p dominated q then
%           ? add q to the set Sp i.e. Sp = Sp ? {q}
%  如果q支配p，那么np的数量就加一了
%       * else if q dominates p then
%           ? increment the domination counter for p i.e. np = np + 1
% 如果np为0，说明没有个体支配p，那么p就是属于第一层级
%把个体p放入当rank=1的层级，更新层级


%   ? if np = 0 i.e. no individuals dominate p then p belongs to the first
%     front; Set rank of individual p to one i.e prank = 1. Update the first
%     front set by adding p to front one i.e F1 = F1 ? {p}
%  这是对种群P中所有个体进行执行的
%  初始化层级的计数为1

% ? This is carried out for all the individuals in main population P.
% ? Initialize the front counter to one. i = 1
% 接下来是当第i层Fi不等于空的时候执行的
%Q = []这个集合是用来储存在第i+1层的个体

%对于每个在Fi层的Sp（受p支配的个体的集合）集合的p中
%nq。。。减少个体的支配数
%nq=0 没有个体在随后接下来的前沿中支配q，因此设置q的等级为i+1，更新Q
%前沿计数加一，集合Q就是下一层，因此Fi=Q

% ? following is carried out while the ith front is nonempty i.e. Fi != []
%   ? Q = []. The set for storing the individuals for (i + 1)th front.
%   ? for each individual p in front Fi
%       * for each individual q in Sp (Sp is the set of individuals
%         dominated by p)
%           ? nq = nq?1, decrement the domination count for individual q.
%           ? if nq = 0 then none of the individuals in the subsequent
%             fronts would dominate q. Hence set qrank = i + 1. Update
%             the set Q with individual q i.e. Q = Q ? q.
%   ? Increment the front counter by one.
%   ? Now the set Q is the next front and hence Fi = Q.
%
% This algorithm is better than the original NSGA ([2]) since it utilize
% the informatoion about the set that an individual dominate (Sp) and
% number of individuals that dominate the individual (np).

%
for i = 1 : N
    %支配这个个体的个体数
    % Number of individuals that dominate this individual
    individual(i).n = 0;
    %站主导地位的个体（支配别人的个体）
    % Individuals which this individual dominate
    individual(i).p = [];
    for j = 1 : N
        dom_less = 0;
        dom_equal = 0;
        dom_more = 0;
        for k = 1 : M
            if (x(i,V + k) < x(j,V + k))
                dom_less = dom_less + 1;
            elseif (x(i,V + k) == x(j,V + k))
                dom_equal = dom_equal + 1;
            else
                dom_more = dom_more + 1;
            end
        end
        if dom_less == 0 && dom_equal ~= M
            individual(i).n = individual(i).n + 1;
        elseif dom_more == 0 && dom_equal ~= M
            individual(i).p = [individual(i).p j];
        end
    end   
    if individual(i).n == 0
        x(i,M + V + 1) = 1;
        F(front).f = [F(front).f i];
    end
end
%找到之后的前沿
% Find the subsequent fronts
while ~isempty(F(front).f)
   Q = [];
   for i = 1 : length(F(front).f)
       if ~isempty(individual(F(front).f(i)).p)
        	for j = 1 : length(individual(F(front).f(i)).p)
            	individual(individual(F(front).f(i)).p(j)).n = ...
                	individual(individual(F(front).f(i)).p(j)).n - 1;
        	   	if individual(individual(F(front).f(i)).p(j)).n == 0
               		x(individual(F(front).f(i)).p(j),M + V + 1) = ...
                        front + 1;
                    Q = [Q individual(F(front).f(i)).p(j)];
                end
            end
       end
   end
   front =  front + 1;
   F(front).f = Q;
end

[temp,index_of_fronts] = sort(x(:,M + V + 1));
for i = 1 : length(index_of_fronts)
    sorted_based_on_front(i,:) = x(index_of_fronts(i),:);
end
current_index = 0;

%% Crowding distance拥挤度距离
%The crowing distance is calculated as below计算方式如下
%对于每一个前沿Fi来说，n是个体的数量
% ? For each front Fi, n is the number of individuals.
%对于所有的个体来说，初始化距离是0
%j对应的是在前沿Fi上 的第j个个体
%   ? initialize the distance to be zero for all the individuals i.e. Fi(dj ) = 0,
%     where j corresponds to the jth individual in front Fi.
%对于每一个目标函数m来说
%   ? for each objective function m
%       是基于目标函数m来对Fi上的个体进行排序
%       * Sort the individuals in front Fi based on objective m i.e. I =
%         sort(Fi,m).
%       为每个个体的边界值分配无限距离（距离为无穷大）
%       * Assign infinite distance to boundary values for each individual
%         in Fi i.e. I(d1) = ? and I(dn) = ?
%       * for k = 2 to (n ? 1)
%           ? I(dk) = I(dk) + (I(k + 1).m ? I(k ? 1).m)/fmax(m) - fmin(m)
%           ? I(k).m is the value of the mth objective function of the kth
%             individual in I   第I前沿中，第k个个体的第m个目标函数值

%在每个前沿中为每个个体找出它的拥挤度距离
% Find the crowding distance for each individual in each front
for front = 1 : (length(F) - 1)
%    objective = [];
    distance = 0;
    y = [];
    previous_index = current_index + 1;
    for i = 1 : length(F(front).f)
        y(i,:) = sorted_based_on_front(current_index + i,:);
    end
    current_index = current_index + i;
    %对每个个体基于它的目标函数进行排序
    % Sort each individual based on the objective
    sorted_based_on_objective = [];
    for i = 1 : M
        [sorted_based_on_objective, index_of_objectives] = ...
            sort(y(:,V + i));
        sorted_based_on_objective = [];
        for j = 1 : length(index_of_objectives)
            sorted_based_on_objective(j,:) = y(index_of_objectives(j),:);
        end
        f_max = ...
            sorted_based_on_objective(length(index_of_objectives), V + i);
        f_min = sorted_based_on_objective(1, V + i);
        y(index_of_objectives(length(index_of_objectives)),M + V + 1 + i)...
            = Inf;
        y(index_of_objectives(1),M + V + 1 + i) = Inf;
         for j = 2 : length(index_of_objectives) - 1
            next_obj  = sorted_based_on_objective(j + 1,V + i);
            previous_obj  = sorted_based_on_objective(j - 1,V + i);
            if (f_max - f_min == 0)
                y(index_of_objectives(j),M + V + 1 + i) = Inf;
            else
                y(index_of_objectives(j),M + V + 1 + i) = ...
                     (next_obj - previous_obj)/(f_max - f_min);
            end
         end
    end
    distance = [];
    distance(:,1) = zeros(length(F(front).f),1);
    for i = 1 : M
        distance(:,1) = distance(:,1) + y(:,M + V + 1 + i);
    end
    y(:,M + V + 2) = distance;
    y = y(:,1 : M + V + 2);
    z(previous_index:current_index,:) = y;
end
f = z();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207