CCMO算法分析

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

CCMO 总结:

1)CCMO,双种群算法,一个处理原问题种群,一个处理辅助问题(如无约束)种群

2)借鉴 NSGA-II 算法,引入非支配排序(未使用拥挤度计算)

3)借鉴 SPEA2 算法,计算适应度(支配数量),截断策略(非支配解过多,只需要选N个,故删除拥挤度高的)

4)弱协同,2个种群只在更新种群时才协作,各自独立交叉变异

CCMO是采用双种群协作的方式,使用NSGAII框架;另外,为了提高多样性,替代NSGAII的拥挤度距离(选择最不拥挤),采用SPEA2的裁剪策略(删除最拥挤的)。

一、CCMO算法流程

代码见附录 CCMO.md

 

二、为什么CCMO是弱协同

在CCMO算法中,之所以说是"弱协同"而不是"强协同",是因为该算法中两个种群在交配选择时并不直接合作。
具体来说,每个种群独立进行父本的选择,各自生成后代,而没有交互作用或协同策略来共同优化或选择交配父本。
这种独立操作确保了种群间的多样性,但相较于那些采用种群间直接交互以加强解的质量和搜索效率的算法(即强协同),它在种群间的协调上显得较弱。
 
比如在多样性方面,弱协同的好处
  • 多样性维护:弱协同通过减少个体之间的协作,可以更好地维护种群的多样性。每个子群体独立进化,有助于避免种群过早收敛到局部最优解。
  • 避免过度协作:强协同虽然可以通过紧密的协作提高优化性能,但也可能导致个体之间的过度协作,进而损害种群的多样性。弱协同通过适度的协作,平衡了优化性能和多样性维护的需求。

 

三、NSGAII和SPEA2对比

SPEA2的环境选择机制

1、适应度计算:

    • 强度值计算(Strength Value):计算每个解支配的其他解的数量。
    • 适应度值计算(Fitness Value):计算每个解的适应度值,适应度值等于所有被当前解支配的解的强度值之和,再加上一个微小的常数来处理未被任何解支配的情况。

2、选择非支配解:

    • 选择适应度小于1的解,这些解通常是非支配解。

3、裁剪多余解:

    • 如果选择的非支配解数量超过种群大小,通过截断算法删除多余的解。截断算法根据解的拥挤度(即距离)来选择删除哪些解,以保持种群的多样性。

 

NSGA-II的非支配排序机制

1、非支配排序:

    • 将种群中的个体根据支配关系分成不同的等级(Front)。第一个等级(Front 1)包含所有非支配解,第二个等级(Front 2)包含被Front 1支配的解,以此类推。

2、拥挤距离计算:

    • 对每个前沿(Front)的个体计算拥挤距离,拥挤距离用于衡量个体在目标空间的稀疏程度。

3、环境选择:

    • 优先选择低等级(高优先级)的前沿个体。如果某个前沿的个体数量超过剩余的种群大小,根据拥挤距离选择个体,以保持种群的多样性。

 

四、附录

CCMO.m

classdef CCMO < ALGORITHM
% <multi> <real/integer/label/binary/permutation> <constrained>
% Coevolutionary constrained multi-objective optimization framework
% type --- 1 --- Type of operator (1. GA 2. DE)

%------------------------------- Reference --------------------------------
% Y. Tian, T. Zhang, J. Xiao, X. Zhang, and Y. Jin, A coevolutionary
% framework for constrained multi-objective optimization problems, IEEE
% Transactions on Evolutionary Computation, 2021, 25(1): 102-116.
%------------------------------- 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)
            %% Parameter setting
            type = Algorithm.ParameterSet(1); % 默认采用GA算法

            %% 初始化两个种群(解和目标值)
            Population1 = Problem.Initialization(); % 主种群,带约束
            Population2 = Problem.Initialization(); % 辅助种群,无约束

            %% 分别评价两个种群,求适应度(被支配的数量)
            Fitness1    = CalFitness(Population1.objs,Population1.cons);
            Fitness2    = CalFitness(Population2.objs);

            %% Optimization
            while Algorithm.NotTerminated(Population1)
                if type == 1 % 采用GA算法
                    %% 分别选择父代(二元锦标赛:从N个个体里挑选2个个体,比较适应度,选择好的那个。重复N次,可重复选择)
                    MatingPool1 = TournamentSelection(2,Problem.N,Fitness1);
                    MatingPool2 = TournamentSelection(2,Problem.N,Fitness2);

                    %% 分别生成子代(采用GA算法,对上面的种群进行模拟二进制交叉、二项式变异)
                    Offspring1  = OperatorGAhalf(Problem,Population1(MatingPool1));
                    Offspring2  = OperatorGAhalf(Problem,Population2(MatingPool2));

                elseif type == 2
                    MatingPool1 = TournamentSelection(2,2*Problem.N,Fitness1);
                    MatingPool2 = TournamentSelection(2,2*Problem.N,Fitness2);
                    Offspring1  = OperatorDE(Problem,Population1,Population1(MatingPool1(1:end/2)),Population1(MatingPool1(end/2+1:end)));
                    Offspring2  = OperatorDE(Problem,Population2,Population2(MatingPool2(1:end/2)),Population2(MatingPool2(end/2+1:end)));
                end

                %% 选择更新(优先选择非支配解;如果非支配太多了,采用SPEA2的截断策略,循环删除最拥挤的个体)
                [Population1,Fitness1] = EnvironmentalSelection([Population1,Offspring1,Offspring2],Problem.N,true);
                [Population2,Fitness2] = EnvironmentalSelection([Population2,Offspring1,Offspring2],Problem.N,false);
            end
        end
    end
end

 

CalFitness.m

function Fitness = CalFitness(PopObj,PopCon)
% Calculate the fitness of each solution
% 求适应度,这里不是求目标值,而是求每个解被支配的数量

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

    N = size(PopObj,1);
    if nargin == 1 % 如果只有一个输入参数
        CV = zeros(N,1);
    else
        CV = sum(max(0,PopCon),2); % 计算约束违约度CV,每个个体的约束违约度为其所有约束违约量的和
    end

    %% Detect the dominance relation between each two solutions
    Dominate = false(N); % 初始化支配关系矩阵,大小为N x N,全为false
    for i = 1 : N-1
        for j = i+1 : N
            if CV(i) < CV(j)
                Dominate(i,j) = true; % 如果个体i的约束违约度小于个体j,则个体i支配个体j
            elseif CV(i) > CV(j)
                Dominate(j,i) = true; % 如果个体i的约束违约度大于个体j,则个体j支配个体i
            else
                k = any(PopObj(i,:)<PopObj(j,:)) - any(PopObj(i,:)>PopObj(j,:));
                if k == 1
                    Dominate(i,j) = true; % i个体至少一个目标优于j,并且没有任何目标劣于j
                elseif k == -1
                    Dominate(j,i) = true; % j个体至少一个目标优于i,并且没有任何目标劣于i
                end
            end
        end
    end
    
    %% 每个解支配其他解的数量
    S = sum(Dominate,2); % 2表示行,即求所有行之和,返回一个列向量,代表每个个体直接别人的数量
    
    %% 每个解被多少个解支配
    R = zeros(1,N); 
    for i = 1 : N
        R(i) = sum(S(Dominate(:,i)));
    end
    
    %% Calculate D(i) 每个解的拥挤度距离
    Distance = pdist2(PopObj,PopObj);  % 计算种群中每两个个体之间的距离矩阵
    Distance(logical(eye(length(Distance)))) = inf; % 将距离矩阵的对角线元素设为无穷大,以避免自身比较
    Distance = sort(Distance,2);  % 对距离矩阵的每一行进行排序
    D = 1./(Distance(:,floor(sqrt(N)))+2); % 计算拥挤距离 D,Nx1
    
    %% Calculate the fitnesses 适应度为被支配程度和拥挤距离之和
    % R是1xN,D是Nx1,D'是1xN
    Fitness = R + D';  % 这里的 D' 是 D 的转置操作,将列向量 D 转换为行向量,以便与 R 进行逐元素相加
end

 

EnvironmentalSelection.m

function [Population,Fitness] = EnvironmentalSelection(Population,N,isOrigin)
% The environmental selection of SPEA2
%%  SPEA2的选择和NSGAII的选择显著不同

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

    % Population = [Population1,Offspring1,Offspring2],故大小大于N

    %% Calculate the fitness of each solution
    if isOrigin
        Fitness = CalFitness(Population.objs,Population.cons);
    else
        Fitness = CalFitness(Population.objs);
    end

    %% Environmental selection
    % 选择适应度小于1的解(这些解通常是非支配解)。
    Next = Fitness < 1;
    if sum(Next) < N % 如果选择的解数量小于所需的种群大小 N
        [~,Rank] = sort(Fitness); % 按适应度排序,选择适应度最好的前 N 个解
        Next(Rank(1:N)) = true;
    elseif sum(Next) > N % 如果选择的解数量超过所需的种群大小 N
        Del  = Truncation(Population(Next).objs,sum(Next)-N); % 调用 Truncation 函数,通过截断删除多余的解
        Temp = find(Next);
        Next(Temp(Del)) = false;
    end
    % Population for next generation
    Population = Population(Next);
    Fitness    = Fitness(Next);
    % Sort the population
    [Fitness,rank] = sort(Fitness);
    Population = Population(rank);
end

%% 根据拥挤度删除多余的最拥挤的个体,直到删除K个
function Del = Truncation(PopObj,K)

    %% 裁剪,
    % SPEA2是直接循环删除最拥挤的;
    % NSGAII是先选前沿,前沿在某层超了,则保留那层两边的,然后选择拥挤度小的
    Distance = pdist2(PopObj,PopObj);  % 计算种群中每两个个体之间的距离矩阵
    Distance(logical(eye(length(Distance)))) = inf; % 将距离矩阵的对角线元素设为无穷大,以避免自身比较
    Del = false(1,size(PopObj,1)); % 初始化删除标记
    while sum(Del) < K
        Remain   = find(~Del); % 找到未被删除的个体
        Temp     = sort(Distance(Remain,Remain),2);  % 对距离进行排序
        [~,Rank] = sortrows(Temp); % 对排序结果进行排序,得到最拥挤的个体
        Del(Remain(Rank(1))) = true; % 删除最拥挤的个体
    end
end

 

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

 

  • 微信
  • 交流学习,资料分享
  • weinxin
  • 个人淘宝
  • 店铺名:言曌博客咨询部

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

发表评论

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

  

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