最新补充文章：
|
PPS 总结： 1）PPS，双阶段算法，Push 阶段忽略约束，Pull 阶段考虑约束 2）借鉴 NSGA-II 算法，引入非支配排序、拥挤度计算进行更新种群 3）借鉴 MOEA/D 算法，引入分解策略和邻域矩阵 4）提出增强版 ε 约束方法，自适应动态调节 ε 值 |
一、Push阶段子问题
判断后代个体是否应该替代父代个体。
分别计算每个父代个体的切比雪夫距离，以及每个子代个体的切比雪夫距离。
找出子代更优的(更小的)，从中再按顺序挑选nr个
代码如下
% 计算旧解和新解的目标值和约束违反
% 切比雪夫距离，max(w * |目标值fx - 目标理想值Z|)
g_old = max(abs(Population(P).objs-repmat(Z,length(P),1)).*W(P,:),[],2);
g_new = max(repmat(abs(Offspring.obj-Z),length(P),1).*W(P,:),[],2);
cv_old = overall_cv(Population(P).cons);
cv_new = overall_cv(Offspring.con) * ones(length(P),1);
if search_stage == 1 % 推阶段
% 推阶段，如果后代比父代更好，则替换nr个
Population(P(find(g_old>=g_new,nr))) = Offspring;
...
二、Pull阶段子问题
相比push阶段的子代替代父代，情况要复杂一些。
主要有三种情况
代码如下
% 情况1：新解目标值减少了，新解和旧解约束违反值 <= ε
% 情况2：新解目标值减少了，新旧解约束不变
% 情况3：新解约束违反值减少了，可以不考虑目标值的变化
Population(P(find(((g_old >= g_new) & (((cv_old <= epsilon_k) & (cv_new <= epsilon_k)) | (cv_old == cv_new)) | (cv_new < cv_old) ), nr))) = Offspring;这里括号有点多，梳理一下，本质上这样的
情况一、g_old >= g_new && cv_old <= epsilon_k && cv_new <= epsilon_k
情况二、g_old >= g_new && cv_old == cv_new
情况三、cv_new < cv_old
三、PPS-MOEA/D
1、简单回顾一下MOEA/D
MOEA/D本质是多目标优化算法，将多目标转为多个子问题，不涉及约束处理技术。
1）为种群初始化一个权重向量W，即每个个体解x关联一个权重w
2）对所有的权重w计算它们之间的距离，求得每个权重最近的10个权重
即得到每个解的最近10个解，作为它的邻居
3）在选择父代的时候，从邻居里选2个父代，进行遗传算法的交叉变异和产生后代
4）在选择更新时，可采用比较切比雪夫距离的方式判断子代是否替代父代，即更新种群或环境选择
总之，引入N个权重向量可以在空间中划分N/10个邻域，N个个体在自己的邻域内局部搜索和更新，邻域之间没有交互。
2、PPS中增强的 ε 约束方法
相对传统的ε约束方法，PPS中做了一些增强
-
动态调整ε值：
- 在PPS中，ε值不是固定的，而是动态调整的。这种调整基于优化过程中的反馈，例如约束违反的程度和目标函数的变化率。
- 动态调整ε值使得算法能够更灵活地应对不同的约束和目标变化，提高优化效果。
-
双阶段优化策略：
- 推阶段（Push Stage）：
- 在这个阶段，不考虑约束
- 拉阶段（Pull Stage）：
- 在这个阶段，ε值逐渐减小，变得更严格。这个阶段用于精细优化，通过减少约束违反度，逐步找到最优解。
- 双阶段策略确保了既有广泛搜索的能力，又有精细优化的能力。
- 推阶段（Push Stage）：
-
改进的约束处理机制：
- 在PPS中，除了传统的ε约束方法外，还引入了改进的约束处理技术。例如，通过基于ε的优先级来处理约束，确保在优化过程中更有效地处理约束条件。
- 这种改进的机制可以更好地平衡目标优化和约束满足，提高算法的整体性能。
3、PPS算法循环
代码如下
classdef PPS < ALGORITHM
% <multi/many> <real/integer> <constrained>
% Push and pull search algorithm
% delta --- 0.9 --- The probability of choosing parents locally
% nr --- 2 --- Maximum number of solutions replaced by each offspring
%------------------------------- Reference --------------------------------
% Z. Fan, W. Li, X. Cai, H. Li, C. Wei, Q. Zhang, K. Deb, and E. Goodman,
% Push and pull search for solving constrained multi-objective optimization
% problems, Swarm and Evolutionary Computation, 2019, 44(2): 665-679.
%------------------------------- Copyright --------------------------------
% Copyright (c) 2024 BIMK Group. You are free to use the PlatEMO for
% research purposes. All publications which use this platform or any code
% in the platform should acknowledge the use of "PlatEMO" and reference "Ye
% Tian, Ran Cheng, Xingyi Zhang, and Yaochu Jin, PlatEMO: A MATLAB platform
% for evolutionary multi-objective optimization [educational forum], IEEE
% Computational Intelligence Magazine, 2017, 12(4): 73-87".
%--------------------------------------------------------------------------
% This function is written by Wenji Li
methods
function main(Algorithm,Problem)
%% Parameter setting
% 设置参数 delta 和 nr，delta 是局部选择父代的概率，nr 是每个后代最多替换的解数量
[delta,nr] = Algorithm.ParameterSet(0.9,2);
%% Generate the weight vectors
[W,Problem.N] = UniformPoint(Problem.N,Problem.M); % 生成权重向量 W，并设置种群规模 Problem.N
T = ceil(Problem.N/10); % 设置每个解的邻居数量 T,即每个子区域解的数量
%% Detect the neighbours of each solution
B = pdist2(W,W); % 计算权重向量之间的距离
[~,B] = sort(B,2); % 对距离进行排序，找到每个解的 T 个最近邻居
B = B(:,1:T); % 提取最近的 T 个邻居
%% Generate random population
Population = Problem.Initialization(); % 初始化种群 Population
Z = min(Population.objs,[],1); % 设置理想点 Z 为种群目标值的最小值
%% Evaluate the Population
Tc = 0.9 * ceil(Problem.maxFE/Problem.N); % 最大评估次数的 90%，此处等于90
last_gen = 20; % 最后几代
change_threshold = 1e-1; % 变化阈值
search_stage = 1; % 1是推阶段，其他是拉阶段
max_change = 1; % 最大变化率
epsilon_k = 0; % 初始 epsilon_k
epsilon_0 = 0; % 初始 epsilon_0
cp = 2; % 拉阶段的控制参数
alpha = 0.95; % 控制切换拉阶段的阈值
tao = 0.05; % epsilon的衰减因子
ideal_points = zeros(ceil(Problem.maxFE/Problem.N),Problem.M); % 初始化理想点
nadir_points = zeros(ceil(Problem.maxFE/Problem.N),Problem.M); % 初始化对立点
arch = archive(Population,Problem.N); % 初始化存档
%% Optimization
while Algorithm.NotTerminated(Population)
gen = ceil(Problem.FE/Problem.N); % 计算当前代数, maxFE=10000，N=100，则gen最大为100
fprintf("gen:%d\n", gen);
pop_cons = Population.cons; % 获取种群的约束值
cv = overall_cv(pop_cons); % 计算总体约束违反
population = [Population.decs,Population.objs,cv]; % 将种群的决策变量、目标值和约束值组合
rf = sum(cv <= 1e-6) / Problem.N; % 计算可行解的比例
ideal_points(gen,:) = Z; % 更新理想点
nadir_points(gen,:) = max(population(:,Problem.D + 1 : Problem.D + Problem.M),[],1); % 更新对立点
% 计算理想点和对立点的最大变化率
if gen >= last_gen
% 变化率体现种群收敛情况
max_change = calc_maxchange(ideal_points,nadir_points,gen,last_gen);
end
% 设置 e(k) 的值和搜索策略
if gen < Tc
% 理想点或者对立点最大变化率小于0.1时，开始从推阶段转到拉阶段
if max_change <= change_threshold && search_stage == 1
% 如果最大变化率小于阈值且在推阶段，切换到拉阶段。可能gen=37就从推阶段转为拉阶段了
search_stage = -1;
% population(:,end)指的是population最后一列，即cv列。max(cv,[], 1) 计算cv中每列最大值
epsilon_0 = max(population(:,end),[],1); % 更新 epsilon_0，初始值为最大约束违法程度
epsilon_k = epsilon_0; % 更新 epsilon_k
end
if search_stage == -1
% 在拉阶段，更新 epsilon_k。只有拉阶段才考虑约束，才需ε约束处理技术
epsilon_k = update_epsilon(tao,epsilon_k,epsilon_0,rf,alpha,gen,Tc,cp);
end
else
epsilon_k = 0; % 超过 Tc 后 epsilon_k 设为 0
end
% 对于每个解
for i = 1 : Problem.N
% 选择父代
if rand < delta
P = B(i,randperm(size(B,2))); % 局部选择邻居作为父代
else
P = randperm(Problem.N); % 全局随机选择父代
end
% 生成一个后代
Offspring = OperatorDE(Problem,Population(i),Population(P(1)),Population(P(2)));
% 更新理想点
Z = min(Z,Offspring.obj);
% 计算旧解和新解的目标值和约束违反
% 切比雪夫距离，max(w * |目标值fx - 目标理想值Z|)
g_old = max(abs(Population(P).objs-repmat(Z,length(P),1)).*W(P,:),[],2);
g_new = max(repmat(abs(Offspring.obj-Z),length(P),1).*W(P,:),[],2);
cv_old = overall_cv(Population(P).cons);
cv_new = overall_cv(Offspring.con) * ones(length(P),1);
if search_stage == 1 % 推阶段
% 推阶段，如果后代比父代更好，则替换nr个
Population(P(find(g_old>=g_new,nr))) = Offspring;
else % 拉阶段 && 使用改进的epsilon约束处理
% 情况1：新解目标值减少了，新解和旧解约束违反值 <= ε
% 情况2：新解目标值减少了，新旧解约束不变
% 情况3：新解约束违反值减少了，可以不考虑目标值的变化
Population(P(find(((g_old >= g_new) & (((cv_old <= epsilon_k) & (cv_new <= epsilon_k)) | (cv_old == cv_new)) | (cv_new < cv_old) ), nr))) = Offspring;
end
end
% 输出非支配和可行解
arch = archive([arch,Population],Problem.N);
if Problem.FE >= Problem.maxFE
Population = arch;
end
end
end
end
end
% 总约束违反
function result = overall_cv(cv)
% 对约束值进行处理，计算总的约束违反程度
cv(cv <= 0) = 0;cv = abs(cv);
result = sum(cv,2);
end
% 计算最大变化率
% 变化率 = |当前理想点 - 20代之前的理想点| ÷ max(20代之前的理想点，0.000001)
function max_change = calc_maxchange(ideal_points,nadir_points,gen,last_gen)
% 设置一个很小的 delta 值，避免除零错误
delta_value = 1e-6 * ones(1,size(ideal_points,2));
% 计算理想点的变化率
rz = abs((ideal_points(gen,:) - ideal_points(gen - last_gen + 1,:)) ./ max(ideal_points(gen - last_gen + 1,:),delta_value));
% 计算对立点的变化率
nrz = abs((nadir_points(gen,:) - nadir_points(gen - last_gen + 1,:)) ./ max(nadir_points(gen - last_gen + 1,:),delta_value));
% 返回最大变化率
max_change = max([rz, nrz]);
end
% 更新 epsilon，在拉阶段前期(可行解少于95%时，匀速慢慢减少)，中后期将先慢后快地减少
% 参数
% tao=0.05
% epsilon_k=0.9958
% epsilon_0=0.9958
% rf=0.02
% alpha=0.95
% gen=37
% Tc=90
% cp=2
function result = update_epsilon(tao,epsilon_k,epsilon_0,rf,alpha,gen,Tc,cp)
% 根据 rf 值和 alpha 更新 epsilon_k 的值
if rf < alpha % 当可行解比例小于95%时，以5%速度减少
result = (1 - tao) * epsilon_k;
else
% 随着gen的增加，epsilon减少的速度逐渐增快
result = epsilon_0 * ((1 - (gen / Tc)) ^ cp);
end
end
以上代码来自 PlatEMO，中文注释由博主添加
- 微信
- 交流学习，资料分享
-
- 个人淘宝
- 店铺名：言曌博客咨询部
-
(部分商品未及时上架淘宝)
您可以选择一种方式赞助本站
支付宝扫一扫赞助
微信钱包扫描赞助
赏