当前位置：网站首页>A Competitive Swarm Optimizer for Large Scale Optimization

A Competitive Swarm Optimizer for Large Scale Optimization

2022-07-27 05:46:00 【身影王座】

0、论文背景

本文实在PSO的基础上创新算法，得到新的算法CSO。在提出的CSO中，每个粒子的个人最佳位置和全局最佳位置（或邻域最佳位置）都不参与粒子的更新。相反，引入了两两竞争机制，失去竞争的粒子将通过向获胜者学习来更新其位置。

Cheng R, Jin Y. A competitive swarm optimizer for large scale optimization[J]. IEEE transactions on cybernetics, 2014, 45(2): 191-204.

1、CSO

PSO算法之前有讲过，参见博客：PSO。

然而，我们发现，当优化问题具有大量的局部优化或为高维时，PSO表现较差。上述弱点通常可以归因于在PSO中经常发生的过早收敛。在实践中，由于gbest的全球影响，pbest很可能具有与gbest相似甚至相同的值，从而大大减少了蜂群的分化。

在这项工作中，我们探索了单个群内粒子之间的竞争机制的使用。此外，输掉比赛的粒子将向获胜的粒子学习，而不是向gbest或pbesti学习。

1.1 竞争机制

在每一代中，P(t)中的粒子被随机分配到m/2对(假设群大小m是偶数)，然后在每对中的两个粒子之间进行竞争。作为每一场比赛的结果，适应性更好的粒子，以下称为获胜者，将直接传递给下一代的群体P(t+1)。而失去竞争的粒子(失败者)，将通过学习从赢家更新其位置和速度。在向获胜者学习后，失败者也将被传递给蜂群P(t+1)。

1.2 粒子位置更新机制

$\begin{aligned} V_{l, k}(t+1) &=R_{1}(k, t) V_{l, k}(t) \\ &+R_{2}(k, t)\left(X_{w, k}(t)-X_{l, k}(t)\right) \\ &+\varphi R_{3}(k, t)\left(\bar{X}_{k}(t)-X_{l, k}(t)\right) \end{aligned}$

$X_{l, k}(t+1)=X_{l, k}(t)+V_{l, k}(t+1)$

$\bar{X_{k}}(t)$ 是相关粒子的平均位置值， $\varphi$ 是控制 $\bar{X_{k}}(t)$ 影响的参数。具体来说，对于 $\bar{X_{k}}(t)$ ，可以采用全局版本和本地版本：

$\bar{X_{k}^{g}}(t)$ 为P(t)中所有粒子的全局平均位置。
$\bar{X_{l,k}^{l}}(t)$ 表示粒子在粒子l的预定义邻域中的局部平均位置。

如果采用PSO中朝gbest和pbest方向更新的话，会存在下面陷入局部最优的问题：

如果在PSO中去掉gbest，只朝pbest方向更新的话，会有两种情况，同时一种会存在下面陷入局部最优的问题：

而利用竞争机制，随机选两个粒子，进行二者之间相互竞争学习来更新，就会有效避免陷入上述局部最优的问题：

1.3 算法流程

2、算法复现以及简单实验

这里主要比较标准PSO与CSO，实验采用了一个测函数，函数评估次数保持一致，最后重复实验100次，取平均值。

clc;clear;clearvars;
% 随机生成10个数据
num_initial = 10;
num_vari = 30;
% 搜索区间
upper_bound = 5.12;
lower_bound = -5.12;
iter = 20000;
varphi = 1.5;
% 随机生成10个数据,并获得其评估值
sample_x = lhsdesign(num_initial, num_vari).*(upper_bound - lower_bound) + lower_bound.*ones(num_initial, num_vari);
sample_y = Rastrigin(sample_x);
Fmin = zeros(iter, 1);
aver_Fmin = zeros(iter, 1);

for n = 1 : 100
    k = 1;
    % 初始化一些参数
    X = sample_x;
    Y = sample_y;
    V = sample_x;
    [fmin, ~] = min(Y);
    fprintf("n: %.4f\n", n);
    UV = V;
    UX = X;
    UY = Y;
    for i = 1 : iter
        PV = [];
        PX = [];
        PY = [];
        while ~isempty(UX)
            m = size(UX, 1);
            k1 = randi(m);
            k2 = randi(m);
            while k2 == k1
                k2 = randi(m);
            end
            v1 = UV(k1, :);
            x1 = UX(k1, :);
            y1 = UY(k1, :);
            v2 = UV(k2, :);
            x2 = UX(k2, :);
            y2 = UY(k2, :);
            r1 = rand(1, num_vari);
            r2 = rand(1, num_vari);
            r3 = rand(1, num_vari);
            if y1 <= y2
                PV = [PV; v1];
                PX = [PX; x1];
                PY = [PY; y1];
                v2 = r1 .* v2 + r2 .* (x1 - x2) + varphi * r3 .* ((x1 + x2) ./ 2 - x2);
                x2 = x2 + v2;
                x2(x2 > upper_bound) = upper_bound;
                x2(x2 < lower_bound) = lower_bound;
                y2 = Rastrigin(x2);
                PV = [PV; v2];
                PX = [PX; x2];
                PY = [PY; y2];
            else
                PV = [PV; v2];
                PX = [PX; x2];
                PY = [PY; y2];
                v1 = r1 .* v1 + r2 .* (x2 - x1) + varphi * r3 .* ((x1 + x2) ./ 2 - x1);
                v1(v1 > upper_bound) = upper_bound;
                v1(v1 < lower_bound) = lower_bound;
                x1 = x1 + v1;
                x1(x1 > upper_bound) = upper_bound;
                x1(x1 < lower_bound) = lower_bound;
                y1 = Rastrigin(x1);
                PV = [PV; v1];
                PX = [PX; x1];
                PY = [PY; y1];
            end
            if k1 > k2
                UV(k1, :) = [];
                UX(k1, :) = [];
                UY(k1, :) = [];
                UV(k2, :) = [];
                UX(k2, :) = [];
                UY(k2, :) = [];
            else
                UV(k2, :) = [];
                UX(k2, :) = [];
                UY(k2, :) = [];
                UV(k1, :) = [];
                UX(k1, :) = [];
                UY(k1, :) = [];
            end
        end
        UV = PV;
        UX = PX;
        UY = PY;
        % 更新所有个体最佳位置
        [fmin, ~] = min(UY);
        % fprintf("iter %d fmin: %.4f\n", i, fmin);
        Fmin(k, 1) = fmin;
        k = k +1;
    end
    aver_Fmin = aver_Fmin + Fmin;
end
aver_Fmin = aver_Fmin ./ 100;
% disp(pbestx(gbest, :));
plot(aver_Fmin);

PSO结果：