MOEA/D算法分析

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

MOEA/D 总结:

1)MOEA/D,基于分解的多目标进化算法

2)借鉴分解策略:将多目标优化问题分解为若干标量优化子问题

3)采用权重向量:通过预先生成的一组权重向量引导解的进化方向,确保解均匀覆盖 Pareto 前沿

4)使用邻域结构:每个子问题在其邻域内进行搜索,提高局部搜索能力(权重向量相近的为一个邻域,不同邻域之间不交互)

5)适用于大规模多目标优化问题:由于其分解策略和邻域搜索,相比NSGA-II (计算复杂度过高),MOEA/D 在处理大规模和复杂多目标优化问题时表现出色

一、MODE/D特点

  • 分解策略:MOEA/D通过将多目标优化问题分解为若干单目标子问题,每个子问题通过一个权重向量表示。每个子问题在其邻域内进行优化。
  • 邻域更新:通过在邻域内更新个体,MOEA/D能够有效地保持种群的多样性,避免过早收敛。
  • 标量化函数:使用切比雪夫标量化函数或其他标量化方法,将多目标优化问题转化为单目标子问题进行优化。

二、伪代码

初始化种群 P0
评估种群目标函数值
计算邻域

while (未达到最大代数) do
    基于邻域选择父代
    交叉和变异生成子代 Qt
    评估子代目标函数值
    更新邻域解
end while

输出Pareto前沿

代码见附录

 

三、PBI公式介绍

先看代码

% PBI方法
% 通过结合距离和角度信息,引导个体在目标空间中沿权重向量方向逼近理想点。
normW   = sqrt(sum(W(P,:).^2,2)); % 计算权重向量的模 ||w||

normP   = sqrt(sum((Population(P).objs-repmat(Z,T,1)).^2,2)); % 计算父代目标值与理想点的距离  ||a|||
CosineP = sum((Population(P).objs-repmat(Z,T,1)).*W(P,:),2)./normW./normP; % 计算父代的余弦值 cosα
g_old   = normP.*CosineP + 5*normP.*sqrt(1-CosineP.^2); % 计算父代的PBI值 g=d1+θ*d2,d1=||a||*cosα,,d2=||a||*sinα

根据理解代码,我在processon上画了个图

 

 

四、一些简单问题

1、为什么要在邻域搜索?

每个个体有一个固定的邻域集合,邻域中的个体相对较近,具有相似的权重向量。
1)局部搜索:通过在邻域内进行搜索,可以确保在解空间的局部区域进行细致的探索,发现局部最优解。
2)全局搜索:不同邻域的个体代表了种群在解空间中的不同区域,大家都在自己的领域搜索,确保种群在全局范围内保持多样性

 

2、为什么要更新邻域个体?

更新邻域的个体可以更好地保持种群的多样性,避免种群的收敛过早,促进多样性的保留。

 

3、标量化函数的目的?

  • 转化多目标问题:将多目标优化问题转化为单目标优化问题,使得可以应用单目标优化技术。
  • 提供优化方向:通过权重向量引导优化过程,确保在目标空间中的不同区域进行搜索。
  • 衡量解的优劣:通过计算标量值,比较不同解的优劣,选择更优的解进行优化。

 

4、常见标量化函数?

除了PBI之外,还有哪些标量化函数

 

5、怎么理解标量化函数代码 max(w .* abs(obj))?

如注释,求最大的,目标值*权重系数,获得最劣的解

% 对多个目标函数值标量化为一个函数值,获得最劣解,即max(目标值*权重)
function s = scalarizingFunction(obj, w)

    % 切比雪夫标量化函数
    % 情况1)max(权重 * (目标值 - 理想值))
    % 情况2)max(权重 * 目标值) 
    % 显然这里属于情况2了


    % 标量化函数
    % 假如 
    % w=[0.1,0.9], 分别是对应2个目标的权重系数
    % obj=[0.95,0.91] 分别对应2个目标函数的目标值(个体适应度)
    % w .* abs(obj) = [0.1 * 0.95, 0.9 * 0.91] = [0.095, 0.819]
    % max(w .* abs(obj)) = max([0.095, 0.819]) = 0.819

    % 求目标值*目标权重 最大的值(越大越不利,即越大越是不好的解)
    s = max(w .* abs(obj)); % 计算标量化函数值
end

 

6、MOEA/D是 GA算法吗?是一种框架吗?NSGA-II呢

MOEA/D不是GA,是一种框架。MOEA/D 不是 GA算法,虽然他也有选择、交叉和变异。它的主要特点在于将多目标优化问题分解为若干单目标子问题,并在这些子问题上进行优化。MOEA/D本质上是一种框架,具体解决子问题可以用不同的算法,如GA,DE,ABC。

NSGA-II是GA算法,不是框架。它继承了遗传算法的基本操作,如选择、交叉和变异,同时增加了用于多目标优化的非支配排序和拥挤度计算机制,以处理多目标优化问题。NSGA-II 则不是框架,而是具体的多目标优化算法

 

7、如果某个邻域有大量高质量解,比其他邻域的解多好,怎么样?

传统的MOEA/D确实可能存在这样的问题,即在某个邻域内有大量高质量解,而这些解比其他邻域的解都要好,但由于每个邻域只能选择固定数量的个体,这可能导致某些高质量解未能被选入最终的种群。这种情况可以导致最终的解集不公平,因为许多高质量解被遗漏,而其他较差的解却被保留。

改进策略
1)增加邻域内个体的选择数量:
动态调整邻域大小或增加每个邻域内被选择个体的数量,以确保更多高质量解被选入最终种群。

2)基于多样性和质量的混合选择策略:
在选择个体时,综合考虑解的质量和多样性,确保高质量解和多样性得到平衡。

3)全局精英保存策略:
保留全局精英个体,即在所有解中选出一部分最优解(不局限于邻域),这些精英个体直接进入下一代。

4)权重向量的重新分配:
根据解的分布情况动态调整权重向量,确保权重向量在高质量解区域更密集。

 

 

五、附录

MODAD.m

classdef MOEAD < ALGORITHM
% <multi/many> <real/integer/label/binary/permutation>
% Multiobjective evolutionary algorithm based on decomposition
% type --- 1 --- The type of aggregation function

%------------------------------- Reference --------------------------------
% Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based
% on decomposition, IEEE Transactions on Evolutionary Computation, 2007,
% 11(6): 712-731.
%------------------------------- 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);

            %% 生成权重向量
            [W,Problem.N] = UniformPoint(Problem.N,Problem.M);  % 生成均匀分布的权重向量
            T = ceil(Problem.N/10); % 邻域大小

            %% 检测每个解的邻居
            B = pdist2(W,W); % 计算权重向量之间的距离
            [~,B] = sort(B,2); % 对距离排序
            B = B(:,1:T); % 选择前T个最近的邻居

            %% 生成随机种群
            Population = Problem.Initialization(); % 初始化种群
            Z = min(Population.objs,[],1);  % 初始化理想点

            %% Optimization
            while Algorithm.NotTerminated(Population)
                % For each solution
                for i = 1 : Problem.N
                     % 选择父代
                    P = B(i,randperm(size(B,2))); % 从邻域中随机选择父代

                     % 生成子代
                    Offspring = OperatorGAhalf(Problem,Population(P(1:2)));

                    % 更新理想点
                    Z = min(Z,Offspring.obj);

                     % 更新邻居
                    switch type
                        case 1
                            % PBI方法
                            normW   = sqrt(sum(W(P,:).^2,2)); % 计算权重向量的模

                            normP   = sqrt(sum((Population(P).objs-repmat(Z,T,1)).^2,2)); % 计算父代目标值与理想点的距离
                            CosineP = sum((Population(P).objs-repmat(Z,T,1)).*W(P,:),2)./normW./normP; % 计算父代的余弦值
                            g_old   = normP.*CosineP + 5*normP.*sqrt(1-CosineP.^2); % 计算父代的PBI值

                            normO   = sqrt(sum((Offspring.obj-Z).^2,2)); % 计算子代目标值与理想点的距离
                            CosineO = sum(repmat(Offspring.obj-Z,T,1).*W(P,:),2)./normW./normO; % 计算子代的余弦值
                            g_new   = normO.*CosineO + 5*normO.*sqrt(1-CosineO.^2); % 计算子代的PBI值

                        case 2
                            % 切比雪夫方法
                            g_old = max(abs(Population(P).objs-repmat(Z,T,1)).*W(P,:),[],2);
                            g_new = max(repmat(abs(Offspring.obj-Z),T,1).*W(P,:),[],2);
                        case 3
                            % 归一化的切比雪夫方法
                            Zmax  = max(Population.objs,[],1);
                            g_old = max(abs(Population(P).objs-repmat(Z,T,1))./repmat(Zmax-Z,T,1).*W(P,:),[],2);
                            g_new = max(repmat(abs(Offspring.obj-Z)./(Zmax-Z),T,1).*W(P,:),[],2);
                        case 4
                            % 修改的切比雪夫方法
                            g_old = max(abs(Population(P).objs-repmat(Z,T,1))./W(P,:),[],2);
                            g_new = max(repmat(abs(Offspring.obj-Z),T,1)./W(P,:),[],2);
                    end
                    Population(P(g_old>=g_new)) = Offspring; % 更新邻居中的解
                end
            end
        end
    end
end

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

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

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

发表评论

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

  

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