PPS算法分析

avatar 2024年07月01日10:37:58 0 116 views
博主分享免费Java教学视频,B站账号:Java刘哥 ,长期提供技术问题解决、项目定制:本站商品点此

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)
      • 在这个阶段,ε值逐渐减小,变得更严格。这个阶段用于精细优化,通过减少约束违反度,逐步找到最优解。
    • 双阶段策略确保了既有广泛搜索的能力,又有精细优化的能力。
  • 改进的约束处理机制

    • 在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,中文注释由博主添加

 

 
 

 

 

  • 微信
  • 交流学习,服务定制
  • weinxin
  • 个人淘宝
  • 店铺名:言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

avatar 登录者:匿名
匿名评论,评论回复后会有邮件通知

  

已通过评论:0   待审核评论数:0