C-TAEA算法分析

avatar 2024年06月29日16:59:38 0 128 views
博主分享免费Java教学视频,B站账号:Java刘哥 ,长期提供技术问题解决、项目定制:本站商品点此

C-TAEA 总结:

1)C-TAEA借鉴了 MOEA/D 的分解策略和权重向量思想,双种群算法

2)C-TAEA包含2个存档,分别是CA和DA

CA:收敛性存档,主要存储高质量的可行解

DA:多样性存档,主要解决CA在一些邻域中解比较少的情况,为那些邻域存储补充优质解

优质解的判断:先进行非支配排序,优先取靠前前沿的个体;如果需要在同一个前沿里取有限个,逐个挑选拥挤度最小的个体。


最近几天把CCMO和C-TAEA算法很详细地看了下,其中C-TAEA感觉比较复杂,这里记录下。

主要针对其论文里的几个算法步骤顺序来写

一、关联过程

代码如下

[~,Region_Hd] = max(1-pdist2(real(Hd.objs),W,'cosine'),[],2);
[~,Region_CA] = max(1-pdist2(CA.objs,W,'cosine'),[],2);

 

二、更新CA

图片中错别字,“吵了” -> “超了”

代码见附录,UpdateCA.m

 

三、算法3、更新DA

代码见附录,UpdateDA.m

 

四、算法4、选择配对池

代码见附录 C-TAEA.m

 

五、算法5、二元锦标赛选择

代码见附录 MatingSelection.m

 

六、附录

UpdateCA.m

function UpdatedCA=UpdateCA(CA,Q,W)
% 更新收敛存档(CA)
% CA 是未更新的存档
% Q 是后代集合
% W 是权重向量

%------------------------------- 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".
%--------------------------------------------------------------------------
    
    % 【更新CA,从Hc中获取优质可行解,如果可行解不足,则获取优质不可行解】

    S=[];        % 初始化用于输出的解集合
    Sc=[];       % 初始化用于收集满足约束的可行解集合
    Hc=[CA,Q];   % 将当前存档和后代合并,用于接下来的操作
    N=size(W,1); % 权重向量的数量,通常等同于需要维持的解的数量
    CV=sum(max(0,Hc.cons),2);   % 计算所有解的约束违反总和                                  
    Sc=[Sc,Hc(CV==0)]; % 筛选出没有约束违反的解,即可行解

    if length(Sc)==N 
        UpdatedCA=Sc; % 如果可行解数量正好等于N,直接使用这些解作为新的CA

    elseif length(Sc)>N  % 可行解过多,需要裁剪
        % 1. 对可行解进行非支配排序
        [FrontNO,MaxNO]=NDSort(Sc.objs,inf);  

        % 2. 对可行解分层
        for i=1:MaxNO
            S=cat(2,S,Sc(FrontNO==i)); % 按层收集解,每层都是非支配的
            if length(S)>=N
                break; % 一旦收集到足够数量的解,就停止
            end
        end

        % 3. 筛选或裁剪 
        while length(S)>N 
            % 3.1 标准化目标函数值以进行距离计算
            % 额外说明:S是1x93的数组,里面元素是SOLUTION,每个SOLUTION又有 dec、obj、con、add属性,S.objs 是 93x3
            Zmax=max(S.objs,[],1);  % 每列中取最大值,返回1x3
            Zmin=min(S.objs,[],1);  % 每列中取最小值,返回1x3
            % 标准化,将值限定在[0,1], (目标值-最小值)/(最大值-最小值)
            SPopObj=(S.objs-repmat(Zmin,size(S.objs,1),1))./(repmat(Zmax,size(S.objs,1),1)-repmat(Zmin,size(S.objs,1),1));

             % 3.2 将解关联到最近的权重向量
             % 使用pdist2函数计算标准化后的解与权重向量集W之间的余弦距离,找出每个解最接近的权重向量。
             % 计算两个矩阵之间的距离:pdist2(SPopObj,W,'cosine')
             % 1-pdist2(...) 距离越小相似度越大
             % max(xxx, [], 2) 找到每行最大余弦相似度的值和索引,即找到每个个体最近的权重向量的索引
             % 此处 SPopObj是95x3,W是91x3,每个个体找到最相似的w
            [~,Region] = max(1-pdist2(SPopObj,W,'cosine'),[],2);% associate each solution in S with their corresponding subregion
            [value,~]=sort(Region,'ascend');
            flag=max(value);
            counter=histc(value,1:flag);  % 计算每个子区域的解数量,统计每个权重对应有几个个体(只统计上面个体最相似的权重)

            % 3.3 最拥挤区域的识别
            [~,most_crowded]=max(counter); % 找出最拥挤的子区域
            S_crowdest=S(Region==most_crowded);  % 选出该子区域中的所有解
            dist=pdist2(S_crowdest.objs,S_crowdest.objs); % 计算解之间的距离,欧式距离                    
            dist(dist==0)=inf; % 将距离矩阵中的对角线元素(自身与自身的距离)设置为无穷大,以避免后续操作中将自己与自己视为最近的解。
            [row,~]=find(min(min(dist))==dist); % 找到最近的解对(最近的2个解)
            St=S_crowdest(row);  % 选择距离最近的解,2个解

            % 3.4 计算切比雪夫距离
            [~,Region_St] = max(1-pdist2(St.objs,W,'cosine'),[],2);
            Z = min(St.objs,[],1);
            g_tch=max(abs(St.objs-repmat(Z,length(St),1))./W(Region_St,:),[],2);
            [~,order]=max(g_tch);  % 找出具有最大切比雪夫距离的解

            % 3.5 选择并移除最差的解 【最差的解,就是拥挤距离最大的2个解,距离他们权重向量距离最远的解】
            % 筛选拥挤距离最大的解,目的是减少拥挤度,增加解的多样性
            % 筛选离权重向量远的解,目的是期望解朝着权重向量方向移动
            x_wrost=St(order);     % 选择最差的解以移除
            S=setdiff(S,x_wrost);  % 从集合中移除最差的解
        end
        UpdatedCA=S;

    elseif length(Sc)<N
        % 【可行解数量不足,补充不可行解中帕累托支配前沿靠前的解,最后一个前沿中超出的,】

        SI=setdiff(Hc,Sc);	% 找出不满足约束的解集
        f1=sum(max(0,SI.cons),2);  % 计算不满足约束的程度
        [~,Region_SI] = max(1-pdist2(SI.objs,W,'cosine'),[],2); % 将不满足约束的解关联到权重向量
        Z = min(SI.objs,[],1) ;
        f2=max(abs(SI.objs-repmat(Z,length(SI),1))./W(Region_SI,:),[],2);  % 计算标准化后的目标函数值
        PopObj=[f1,f2];           
        [FrontNO,MaxNO]=NDSort(PopObj,inf);  % 对不满足约束的解进行非支配排序               
        S=[S,Sc]; % S是输出结果,Sc是可行解
        for i=1:MaxNO
            S=cat(2,S,SI(FrontNO==i));  % 加入新解直到达到N个
            if length(S)>=N 
                last=i;
                break;
            end
        end
        F_last=SI(FrontNO==last);	 % 找到最后加入的前沿
        delete_n=size(S,2)-N;  % 需要删除的解的数量
        CV=sum(max(0,F_last.cons),2); % 计算约束违反程度
        [~,index]=sort(CV,'descend');  % 根据约束违反程度排序
        x_wrost=F_last(index(1:delete_n)); % 选择最差的解以移除
        S=setdiff(S,x_wrost); % % 从集合中移除最差的解
        UpdatedCA=S; % 返回更新后的CA
    end
end

 

UpdateDA.m

function UpdatedDA=UpdateDA(CA,DA,Q,W)
% Update DA
% CA is the Archive that has  been updated.
% DA is the Archive that has not been updated
% Q  is the set of offspring
% W  is the set of weight vectors

%------------------------------- 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".
%--------------------------------------------------------------------------


    % 【更新DA,遍历所有权重向量对应的区域,如果某个区域的CA个数较少,优先从Hd的对应区域中获取最优个体,加入到S中,同时从Hd中剔除最优个体。】
    S=[];           % 初始化输出集合 S
    Hd=[DA,Q];      % 将多样性存档和后代合并为一个新的集合 Hd
    N=size(W,1);    % 获取权重向量的数量,定义所需的存档大小
    [~,Region_Hd] = max(1-pdist2(real(Hd.objs),W,'cosine'),[],2);  % 计算 Hd 中每个个体与权重向量的关联
    [~,Region_CA] = max(1-pdist2(CA.objs,W,'cosine'),[],2);      % 计算 CA 中每个个体与权重向量的关联
    itr=1;
    while length(S)<N
        for i=1:N      % 遍历每个子区域                                       
            current_c=find(Region_CA==i); % 找出 CA 中属于第 i 个子区域的个体
            if length(current_c)<itr   % 如果该子区域的个体数量少于迭代次数
                for j=1:itr-length(current_c)   % 需要从 Hd 中补充个体到这个子区域   
                    current_d=find(Region_Hd==i);  % 找出 Hd 中属于第 i 个子区域的个体  
                    if isempty(current_d)~=1   % 如果找到了对应的个体
                        [FrontNO,~]=NDSort(Hd(current_d).objs,inf);  % 对这些个体进行非支配排序
                        O=Hd(current_d(FrontNO==1));             % 选择非支配层级最高的个体
                        [~,Region_O] = max(1-pdist2(real(O.objs),W,'cosine'),[],2);  % 再次计算这些个体与权重向量的关联
                        Z = min(O.objs,[],1);  % 计算这些个体的目标函数值的最小值
                        g_tch=max(abs(O.objs-repmat(Z,length(O),1))./W(Region_O,:),[],2);  % 计算切比雪夫距离
                        [~,order]=min(g_tch);   % 找出切比雪夫距离最小的个体
                        x_best=O(order);   % 选择最优的个体

                        Hd(current_d(Hd(current_d)==x_best))=[]; % 从 Hd 中移除已被选择的最优个体
                        if isempty(Hd)==1   % 如果 Hd 为空
                            Region_Hd=[];  % 清空 Region_Hd
                        else   % 否则重新计算 Hd 中个体的区域
                            [~,Region_Hd] = max(1-pdist2(real(Hd.objs),W,'cosine'),[],2);
                        end    
                        if length(S)<N      % 如果 S 的长度仍小于 N
                            S=cat(2,S,x_best);   % 将最优个体加入到 S
                        end
                    else
                        break;   % 如果没有找到合适的个体,跳出循环
                    end
               end
            end
            if length(S)==N   % 如果 S 的长度达到 N,跳出外层循环
                break;
            end
        end
        itr=itr+1;  % 迭代次数增加
    end
    UpdatedDA=S;
end

 

C-TAEA.m

classdef CTAEA < ALGORITHM
% <multi/many> <real/integer/label/binary/permutation> <constrained>
% Two-archive evolutionary algorithm for constrained MOPs

%------------------------------- Reference --------------------------------
% K. Li, R. Chen, G. Fu, and X. Yao, Two-archive evolutionary algorithm for
% constrained multi-objective optimization, IEEE Transactions on
% Evolutionary Computation, 2018, 23(2): 303-315.
%------------------------------- 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".
%--------------------------------------------------------------------------

    methods
        function main(Algorithm,Problem)
            %% 生成权重向量
            [W,Problem.N] = UniformPoint(Problem.N,Problem.M); % 生成均匀分布的权重向量

            %% 生成随机种群
            Population = Problem.Initialization();  % 初始化种群
            CA = UpdateCA([],Population,W);  % 更新收敛存档
            DA = UpdateDA(CA,[],Population,W); % 更新多样性存档

            %% Optimization
            while Algorithm.NotTerminated(CA)
                %% 选择配对池
                % 计算CA和DA在Hm中的非支配解比例
                Hm = [CA,DA];   % Hm是合并了收敛归档和多样性归档的种群                      
                [FrontNo,~] = NDSort(Hm.objs,inf); % 非支配排序

                FrontNo_C   = FrontNo(1:ceil(length(Hm)/2)); % CA部分
                Nc = size(find(FrontNo_C==1),2);  % 第一层,即帕累托非支配解的数量,如8  
                Pc = Nc/length(Hm); % CA的非支配解数量占整个Hm的比例,如8/200=0.04

                FrontNo_D = FrontNo(ceil(length(Hm)/2)+1:length(Hm)); % DA部分
                Nd = size(find(FrontNo_D==1),2);  % 第一层,即帕累托非支配解的数量,如6
                Pd = Nd/length(Hm); % D的非支配解数量占整个Hm的比例,如6/200=0.03

                 % 计算CA中非支配解的比例
                [FrontNo,~] = NDSort(CA.objs,inf); % 对收敛文档再排序一下
                NC = size(find(FrontNo==1),2);     % 找到帕累托前沿个体数量,如8
                PC = NC/length(CA); % 非支配解数占CA数量,如8/100=0.08                

                % 繁殖
                Q = [];
                for i = 1 : size(W,1)
                    % 选P1,Pc大概率大于Pd,更倾向于从CA选
                    if Pc > Pd % 如果CA中的非支配解比DA中非支配解多,选择CA作为配对
                        P1 = MatingSelection(CA); 
                    else
                        P1 = MatingSelection(DA);
                    end

                    % 选P2,PC为0.08,更倾向于从DA中选
                    pf = rand();
                    if pf < PC % 判断随机数是否小于CA中的非支配解比例
                        P2 = MatingSelection(CA); % 如果是,从收敛存档CA中选择配偶
                    else
                        P2 = MatingSelection(DA);  % 否则,从多样性存档DA中选择配偶
                    end
                    MatingPool = [P1,P2];  % 将选择的两个个体P1和P2组成配对池
                    Offspring  = OperatorGAhalf(Problem,MatingPool);  % 使用遗传算子生成后代
                    Q = [Q,Offspring]; % 将新生成的后代添加到种群Q中
                end

               %% update CA and DA
                CA = UpdateCA(CA,Q,W);
                DA = UpdateDA(CA,DA,Q,W);
            end
        end
    end
end

 

 

MatingSelection.m

function P = MatingSelection(S)
% Mating selection of C-TAEA

%------------------------------- 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".
%--------------------------------------------------------------------------
  
    number=length(S);
    rnd=randi(number,1,2);
    x_1=rnd(1);
    x_2=rnd(2);
    CV1 = sum(max(0,S(x_1).con),2);
    CV2 = sum(max(0,S(x_2).con),2);
    if CV1>0 && CV2>0
        x=randi(number,1);
        P=S(x);
    elseif CV1<=0 && CV2>0
        P=S(x_1);
    elseif CV1>0  && CV2<=0
        P=S(x_2);
    elseif CV1==0 && CV2==0
          [FrontNo,~] = NDSort(S(rnd).objs,inf);
          if FrontNo(1)<=FrontNo(2)
              P=S(x_1);
          else
              P=S(x_2);
          end
     end
end

 

以上代码来自 PlatEMO,中文注释由博主添加

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

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

发表评论

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

  

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