Adaptive Particle Swarm Optimization

2022年01月14日 阅读数:3
这篇文章主要向大家介绍Adaptive Particle Swarm Optimization,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Adaptive Particle Swarm Optimization

自适应粒子群算法
 
Zhi-Hui Zhan,Student Member , IEEE, Jun Zhang,Senior Member , IEEE, Y un Li,Member , IEEE, a n d
Henry Shu-Hung Chung,Senior Member , IEEE
2009
 

摘要:

  本文提出了一种具备比经典粒子群优化(PSO)更好的搜索效率的自适应粒子群优化(APSO)。更重要的是,它能够以更快的收敛速度对整个搜索空间进行全局搜索。
  APSO 包括两个主要步骤。
  首先,经过评估种群分布和粒子适应度,执行实时进化状态估计程序以识别如下四种定义的进化状态之一,包括探索、开发、收敛、跳跃状态。它能够在运行时自动控制惯性权重、加速度系数等算法参数,以提升搜索效率和收敛速度。
  而后,当进化状态被归类为收敛状态时,执行精英学习策略。该策略将做用于全局最佳粒子以跳出可能的局部最优。
APSO 已经在 12 个单峰和多峰基准函数上进行了全面评估。将研究参数适应和精英学习的影响。结果代表,APSO 在收敛速度、全局最优性、求解精度和算法可靠性方面大大提升了 PSO 范式的性能。因为 APSO 仅向 PSO 范式引入了两个新参数,所以不会引入额外的设计或实现复杂性。

I. INTRODUCTION

  为了实现这两个目标,本文提出了一种系统的参数自适应策略和精英学习策略。为了实现自适应,首先设计了一种进化状态估计技术,从而根据已肯定的进化状态,利用现有的惯性重量和加速度系数的研究成果,制定出自适应参数控制策略。
  本文在已有的惯性权重[13]-[16]和加速度系数[17]-[20]参数设置技术的基础上,提出了一种系统的自适应方案。粒子群算法的参数不只由ESE控制,还考虑了这些参数在不一样状态下的不一样影响。此外,从变异[23]、重置[25]、[26]或从新初始化[27]、[28]操做出发,本文提出ELS算法只在全局最优粒子上执行,而且只在收敛状态下执行。这不只是由于收敛状态最须要ELS,还由于计算开销很是低。此外,自适应ELS将保持种群多样性,以跳出潜在的局部最优。此外,还将对粒子群算法范式中的各类拓扑结构进行测试,以验证APSO算法的有效性,并与其余改进的粒子群算法进行更全面的比较。

II. PSO AND ITS DEVELOPMENTS(粒子群算法及其发展)

A. PSO Framework
(PSO框架)
B. Current Developments of the PSO
(粒子群优化算法的发展示状)

III. ESE FOR PSO

A. Population Distribution Information in PSO(粒子群优化算法中的种群分布信息)

  在收敛状态下,从全局最佳粒子到其余粒子的平均距离将是最小的,由于全局最佳粒子每每被群包围。相反,这个平均距离在跳出状态下最大,由于全局最好的可能会远离拥挤的蜂群。

B. ESE

Step 1: At the current position, calculate the mean distance
of each particle i to all the other particles.
(在当前位置,计算每一个粒子 i 到其余全部粒子的平均距离)
平均距离能够用欧几里德公式来测量
0
 
Step 2: Denote diof the globally best particle as dg. Compare all di’s, and determine the maximum and minimum distances dmaxand dmin.
(将全局最佳粒子的 di 表示为dg。比较全部di,并肯定最大和最小距离dmax和dmin)
进化因子:
0
Step 3: Classify f into one of the four sets S1, S2, S3 and S4, which
represent the states of exploration, exploitation, convergence, and jumping out, respectively.
(将f纳入S一、S二、S3和S4四个集合中的一个,分别表明探索、开发、收敛和跳跃状态)
状态转换将是不肯定的和模糊的,而且不一样的算法或应用可能表现出不一样的转换特性。所以,建议采用模糊分类。
Case (a)—Exploration:探测
Case (b)—Exploitation:开发
Case (c)—Convergence:收敛
Case (d)—Jumping Out:跳跃
0
  在过渡期,两个成员资格将被激活,并能够被归类为任何一个状态。对于最终分类,这里可使用两种最经常使用的去模糊化技术中的任何一种,即,“单件”或“质心”方法[55]。本文采用单例方法,由于它比质心方法更有效,而且易于与状态转移规则库结合实现。
  有了规则库,若是以前的状态是S4,则单例将挑出S1而不是S2,由于规则库(包含更改序列)决定了去模糊化时的决策。若是以前的状态是S1,则出于分类稳定性的考虑,也将其分类为S1,即不过分切换状态指示器。然而,若是以前的状态是S2或S3,则具备规则表的单例将把f分类到S2。

IV . APSO

A. Adaptive Control of PSO Parameters(粒子群算法参数的自适应控制)

1) Adaptation of the Inertia Weight(惯性权重的自适应)

  利用粒子群算法中的惯性权重ω来平衡全局搜索能力和局部搜索能力。
  在本文中,ω被初始化为0.9。因为ω不必定是随时间单调的,而是随 f 单调的,所以,ω将适应以 f 为特征的搜索环境。如前所述,在跳跃或探索状态下,较大的 f 和 ω 将有利于全局搜索。相反,当f较小时,检测到开发或收敛状态,所以,ω减少以利于局部搜索。
 

2) Control of the Acceleration Coefficients(加速度系数的控制)

  基于如下思想,能够对加速度系数进行自适应控制。参数c1表明“自我认知”,它将粒子拉到它本身的历史最佳位置,帮助探索当地的利基环境,并保持种群的多样性。
参数c2表明推进群体收敛到当前全局最佳区域的“社会影响力”,有助于快速收敛。这是两种不一样的学习机制,在不一样的进化状态下应该给予不一样的对待。在本文中,加速度系数被初始化为2.0,并根据进化状态进行自适应控制,并制定了以下策略。
  Strategy 1—Increasing c1and Decreasing c2in an Exploration State (在探索状态下增长c1和减小c2)
重要的是在勘探状态下探索尽量多的最优值。所以,增长c1和减小c2能够帮助粒子单独探索并达到它们本身的历史最佳位置,而不是汇集在可能与局部最优相关的当前最佳粒子周围。
 
  Strategy 2—Increasing c1 Slightly and Decreasing c2 Slightly in an Exploitation State (在开发状态下稍微增长c1,稍微减小c2)
在这种状态下,粒子利用局部信息并朝着由每一个粒子的历史最佳位置指示的可能的局部最优小生境进行分组。所以,缓慢增长c1并保持相对较大的值能够强调对pBesti的搜索和利用。同时,在这个阶段,全局最优粒子并不老是位于全局最优区域。所以,缓慢减少c2并保持较小的值能够避免局部最优解的欺骗。此外,开发状态更有可能出如今探索状态以后和收敛状态以前。所以,c1和c2的方向改变应该从探索状态略微改变为收敛状态。
 
  Strategy 3—Increasing c1 Slightly and Increasing c2 Slightly in a Convergence State (在收敛状态下略微增长c1和略微增长c2)
在收敛状态下,群体彷佛找到了全局最优区域,所以,应该强调c2的影响,以引导其余粒子到达可能的全局最优区域。所以,应该增长c2的值。另外一方面,应减少c1的值,使种群快速收敛。然而,对表I中给出的12个基准函数进行优化的大量实验代表,这样的策略会过早地将这两个参数分别饱和到它们的下界和上界。结果是,群体会被当前最优区域强烈吸引,致使过早收敛,若是当前最优区域是局部最优,这是有害的。为了不这种状况,c1和c2都略有增长。
注意,稍微增长两个加速度参数最终将具备与减少c1和增长c2相同的预期效果,因为c1和c2之和的上限为4.0(请参阅下一节中讨论的(12)),它们的值将绘制为2.0左右。
 
  Strategy 4—Decreasing c1and Increasing c2 in a Jumping-Out State (在跳跃状态下减小c1并增长c2)
当全局最好的粒子从局部最优跳向更好的最优时,它极可能远离拥挤的集群。一旦这个新区域由一个粒子发现,成为(多是新的)领导者,其余粒子应该跟随它,尽快飞往这个新的区域。一个较大的c2加上一个相对较小的 c1有助于达到这个目标。

3) Bounds of the Acceleration Coefficients(加速度系数的界)

  如前所述,上述对加速度系数的调整不该过于突兀。所以,两代之间的最大增量或减量的界限是|ci(g+ 1) − ci(g)| ≤ δ, i = 1, 2。

B. Effects of Parameter Adaptation(参数适应的影响)

  不管是单峰函数仍是多峰函数,参数自适应确实大大加快了粒子群算法的速度。
  当最好的粒子成为最好的粒子时,全局最好粒子的自我认知和社会影响力学习成分都几乎为零。此外,当惯性权小于1时,它的速度会变得愈来愈小。标准的学习机制并不能帮助BEST摆脱这个局部最优,由于它的速度接近于0。

C. ELS

  GPSO和VPSO在Schwefel函数上单独使用参数自适应的失败代表,为了提升这些搜索算法的全局性,跳出机制是必要的。所以,本文设计了一种“ELS”算法,并将其应用于全局最优粒子,以帮助在搜索到收敛状态时跳出局部最优区域。
  与其余粒子不一样,全球领导者没有榜样可循。它须要新的动力来提升本身。所以,发展了一种基于扰动的ELS,以帮助BEST将本身推向一个潜在的更好的区域。若是找到了另外一个更好的区域,那么其他的蜂群就会跟随领头羊跳出来,汇聚到新的区域。
  ELS随机选择gBest历史最佳位置的一个维度,第d个维度用Pd表示。只选择一个维度是由于局部最优可能具备全局最优的一些良好结构,所以应该保护这一点。因为每一个维度具备相同的选择几率,所以ELS运算能够被认为是在统计意义上对每一个维度执行的。相似于模拟退火,即进化规划或进化策略中的变异操做,精英学习是经过高斯扰动来执行的
0
  搜索范围[Xdmin,Xdmax]与问题的上下界相同。高斯(μ,σ2)是具备零均值μ和标准差(SDσ)的高斯分布的随机数,被称为“精英学习率”。与一些时变神经网络训练方案相似,建议σ随代数线性减小,代数由σ=σmax−(σmax−σmin)g / G给出,其中σmax和σmin是σ的上下界,表明到达一个新区域的学习规模。
  实证研究代表,σmax=1.0和σmin=0.1在大多数测试函数上都具备良好的性能。
Flowchart of ELS forgBestupon convergence state emerging.
0
   在统计意义上,减少的SD在早期阶段提供了较高的学习率,使其跳出可能的局部最优解,而在后期,较小的学习率引导了Beste改进解。在ELS中,若是且仅当新职位的适合性比当前的最佳职位更好时,才会接受新职位。不然,新位置用于替换群中适应度最差的粒子。

D. Search Behaviors of APSO(APSO的搜索行为)

1) APSO in Unimodal Search Space(单峰搜索空间中的APSO)

  在球面函数上研究了APSO在单峰空间中的搜索行为(表I中的f1)。在单峰空间中,对于优化或搜索算法来讲,快速收敛和精化解以得到高精度是很是重要的。图9(A)中显示的惯性权重证明,APSO在探索阶段(大约50代人)保持了一个很大的ω,而后在开发以后ω迅速降低,致使收敛,由于领先粒子找到了惟一的全局最优区域,群体跟随它。

2) APSO in Multimodal Search Space(多模态搜索空间中的APSO)

种群标准差
(N、D和X分别是全部粒子的整体大小、维数和平均位置)
0
  PSD中的变化能够指示种群的多样性水平。若是PSD值较小,则代表种群已紧密收敛到某一区域,种群多样性较低。PSD值越大,代表种群的多样性越高。然而,这并不必定意味着较大的psd老是比较小的psd更好,由于不能收敛的算法也可能出现较大的psd。所以,PSD须要与算法获得的解一块儿考虑。
  实验结果代表,在多峰空间中,APSO算法也能在早期快速找到潜在的最优区域(多是局部最优),并经过自适应参数策略快速收敛,多样性迅速减少。然而,若是当前最优区域是局部的,则群能够分离并跳出。
  所以,因为ELS处于收敛状态,APSO能够适当增长种群的多样性,以寻求更好的区域。这种具备自适应种群多样性的行为对于全局搜索算法避免陷入局部最优值和在多峰空间中寻找全局最优值具备重要意义。

V. BENCHMARK TESTS AND COMPARISONS(基准测试和比较)

A. Benchmark Functions and Algorithm Configuration
(基准函数和算法配置)
B. Comparisons on the Solution Accuracy
(求解的精度比较)
C. Comparisons on the Convergence Speed
(收敛速度的比较)
D. Comparisons on the Algorithm Reliability
(算法可靠性比较)
E. Comparisons Using t-Tests
(使用t检验进行比较)

VI. ANALYSIS OF PARAMETER ADAPTATION AND ELITIST LEARNING(参数适应与精英学习分析)

A. Merits of Parameter Adaptation and Elitist Learning(参数自适应和精英学习的优势)

  结果代表,在不进行参数自适应控制的状况下,APSO在只进行精英学习的状况下,仍然能够很好地求解多峰函数。然而,APSO在求解单峰函数时存在精度较低的问题。因为算法很容易找到单峰函数的全局最优区域,而后对解进行精化,所以收敛速度较慢可能致使精度较低。另外一方面,仅有参数自适应而没有ELS的APSO很难跳出局部最优解,从而致使多峰函数的性能较差。可是,它仍然能够很好地解决单峰问题。
注意,这两种简化的APSO算法一般都优于既不涉及自适应参数也不涉及精英学习的标准PSO。然而,完整的Apso对于任何测试过的问题都是最强大、最健壮的。这一点在f4的测试结果中最为明显。这些结果与第四-B节的结果一块儿证明了这样的假设,即参数自适应加快了算法的收敛速度,精英学习有助于群体跳出局部最优解并找到更好的解。

B. Sensitivity of the Acceleration Rate(加速度灵敏度)

  本文研究了由边界δ反映的加速度对APSO性能的影响。为此,学习率σ是固定的(例如,APSO最大=σ最小=0.5),而且APSO的其余参数保持与第V-A节中的相同。该调查包括6个δ测试策略,前3个策略分别将其值固定为0.0一、0.05和0.1,其他3个策略分别在[0.01,0.05]、[0.05,0.1]和[0.01,0.1]内使用均匀分布随机生成其值。根据在30个独立试验中找到的解决方案的平均值,结果显示在表X中。
  因而可知,APSO对加速率δ不是很敏感,六种加速率都提供了不错的性能。这多是由于使用了加速度系数和饱和度的界限来限制它们的和(12)。所以,给定c1和c2的有界值以及它们的和受(12)的限制,δ的范围[0.05,0.1]内的任意值应该是APSO算法能够接受的。

C. Sensitivity of the Elitist Learning Rate(精英学习率的敏感性)

  结果代表,若是σ很小(例如,0.1%),那么学习率不足以跳出局部最优值,这在7的性能中是显而易见的。然而,全部其余容许更大σ的设置都提供了几乎一样出色的性能,尤为是σ从1.0时变到0.1时变的策略。能够看出,较小的σ更有助于引导粒子的细化,而较大的σ更有助于引导粒子脱离现有位置,从而跳出局部最优。这证明了这样一种直觉,即应该在早期阶段适应跳跃,以免局部最优和早熟收敛,而在后期阶段的小扰动应该有助于改进全局解,正如本文所建议的那样。

VII. CONCLUSION

  本文将粒子群算法推广到APSO。粒子群算法的这一进展是由进化进化算法(ESE)实现的,它利用了种群分布和相对粒子适应度的信息,与进化策略中的内部模型有着类似的精神。基于这些信息,定义了进化因子,并用模糊分类方法计算进化因子,这有利于有效和高效的ESE方法,所以也是一种自适应算法。
如基准测试所示,惯性权重和加速系数的自适应控制使得该算法很是有效,在得到单峰和多峰函数的可接受解所需的FE数目和CPU时间方面都提供了显著提升的收敛速度。与人工神经网络中相似于竞争学习的加速界控制相结合,还设计了一种加速率控制来辅助APSO中的参数渐变。
  在此基础上,提出了一种基于高斯扰动的ELS算法,该算法能引导群体跳出任何可能的局部最优解,并精化收敛解。开发了一种时变学习率,它与模拟退火中的神经网络训练或模拟退火玻尔兹曼学习(Boltzmann)具备类似的精神,以进一步帮助实现双重学习目标。ELS大大提升了全局解的准确性,这在基准测试中是显而易见的。
  基于ESE的参数自适应技术不一样于现有的仅基于世代数的被动参数变化方案。这一技术和精英学习技术也使改进的PSO算法在解决单峰和多峰问题时很是可靠,如表VIII中详细说明的t检验结果和表IX中详细说明的比较所示。虽然APSO做为一个总体为PSO范式引入了两个新的参数,即加速速率和学习率,但它们很容易设置,而且不会增长程序设计或实现的负担。所以,在收敛速度、全局最优性、解的准确性和算法的可靠性方面,APSO仍然与标准PSO同样简单和易于使用,但性能却有很大提升。
  预计APSO将对粒子群算法在现实世界优化和搜索问题中的应用产生影响。进一步的工做包括研究基于ESE的拓扑结构自适应控制,以及将ESE技术应用于其余进化计算算法。结果将在适当时候公布。

源码:

APSO.m

function [fitnessgbest,T] = APSO( fhd,func_num,Dimension,Particle_Number,Max_Gen,VRmin,VRmax,Popmin,Popmax)
%APSO 此处显示有关此函数的摘要
%   此处显示详细说明
c1 = 2.0;
c2 = 2.0;
w = 0.9;
D = Dimension;
sizepop = Particle_Number;
maxgen = Max_Gen;%
Vmax = VRmax;
Vmin = VRmin;
popmax = Popmax;
popmin = Popmin;
Status = 'S1';


for i = 1:sizepop
    % 随机产生一个种群
    pop(i,:) = popmin+(popmax-popmin)*rand(1,D);    %初始种群
    V(i,:) = Vmin+(Vmax-Vmin)*rand(1,D);  %初始化速度
end
fitness = feval(fhd,pop',func_num);

%% V. 个体极值和群体极值
[bestfitness,bestindex] = min(fitness);
pbest = pop;    %个体最佳
gbest = pop(bestindex,:);   %全局最佳
fitnesspbest = fitness;%个体最佳适应度值

fitnessgbest = bestfitness;   %全局最佳适应度值
g = bestindex;


%% VI. 迭代寻优
for i = 1:maxgen
    for j = 1:sizepop
        % 速度更新
        V(j,:) = w*V(j,:) + c1*rand*(pbest(j,:) - pop(j,:)) + c2*rand*(gbest - pop(j,:));
        
        
        %确保速度不超出边界
        for d = 1:D
            V(j,d) = max(Vmin,min(Vmax,V(j,d)));
        end
        
        % 种群更新
        pop(j,:) = pop(j,:) + V(j,:);
        
        %确保粒子位置不超出边界
         for d = 1:D
           pop(j,d) = max(popmin,min(popmax,pop(j,d)));
         end
        
        
        % 适应度值更新
        fitness(j) = feval(fhd,pop(j,:)',func_num);
        
        %pbest和gbest更新
        if fitness(j) < fitnesspbest(j)
            pbest(j,:) = pop(j,:);
            fitnesspbest(j) = fitness(j);
            if fitness(j) < fitnessgbest
                gbest = pop(j,:);
                fitnessgbest = fitness(j);
                g = j;
            end
            
        end
        Rd = randperm(D,1);%从1-D中随机选取一个数
        variance = 1.0-0.9*i/maxgen;
%         Z = popmin+(popmax-popmin)*gaussmf(gbest(Rd),[variance 0]);
        Jump = gbest(Rd)-17+rand*34;
%         Jump = gbest(Rd)+Z;
        Jump = max(popmin,min(popmax,Jump));
        Ju = gbest;
        Ju(Rd) = Jump;
        
        Jumpfitness = feval(fhd,Ju',func_num);
        if Jumpfitness < fitnessgbest
%             Status = 'S4';
            pop(g,:) = Ju;
            pbest(g,:) = Ju;
            gbest = Ju;
            fitnesspbest(g) = Jumpfitness;
            fitnessgbest = Jumpfitness;
        end
    end
    
%     yy(i) = fitnessgbest;
    
    
%%   状态判断
    
    S(i) = MeanD(pop,g,D);
    w = 1/(1+1.5*exp(-2.6*S(i)));   
    if S(i)<0.2
        Status = 'S3';
    end
    if 0.2<=S(i)&&S(i)<0.23
        if strcmp(Status,'S1')||strcmp(Status,'S2')
            Status = 'S2';
        else
            Status = 'S3';
        end
    end
    if 0.23<=S(i)&&S(i)<0.3
        if strcmp(Status,'S2')||strcmp(Status,'S3')
            Status = 'S3';
        else
            Status = 'S2';
        end
    end
    
    if 0.3<=S(i)&&S(i)<0.4
        Status = 'S2';
    end
    if 0.4<=S(i)&&S(i)<0.5
        if strcmp(Status,'S1')||strcmp(Status,'S4')
            Status = 'S1';
        else
            Status = 'S2';
        end
    end
    if 0.5<=S(i)&&S(i)<0.6
        if strcmp(Status,'S2')||strcmp(Status,'S1')
            Status = 'S2';
        else
            Status = 'S1';
        end
    end
    
    if 0.6<=S(i)&&S(i)<0.7
        Status = 'S1';
    end
    if 0.7<=S(i)&&S(i)<0.77
        if strcmp(Status,'S3')||strcmp(Status,'S4')
            Status = 'S4';
        else
            Status = 'S1';
        end
    end
    if 0.77<=S(i)&&S(i)<0.8
        if strcmp(Status,'S4')||strcmp(Status,'S1')
            Status = 'S1';
        else
            Status = 'S4';
        end
    end
    if S(i)>=0.8
        Status ='S4';
    end
%%    根据状态调整参数
    
    if strcmp(Status,'S1')
        c1 = c1+(0.05+rand*0.05);
        c2 = c2-(0.05+rand*0.05);
    end
    
    
    if strcmp(Status,'S2')
        c1 = c1+(0.025+rand*0.025);
        c2 = c2-(0.025+rand*0.025);
    end
    
    
    if strcmp(Status,'S3')
        c1 = c1+(0.025+rand*0.025);
        c2 = c2+(0.025+rand*0.025);
    end
    
    
    if strcmp(Status,'S4')
        c1 = c1-(0.05+rand*0.05);
        c2 = c2+(0.05+rand*0.05);
    end
    if c1+c2 < 3
        c1 = c1*3/(c1+c2);
        c2 = 3-c1;
    end
    if c1+c2 > 4
        c1 = c1*4/(c1+c2);
        c2 = 4-c1;
    end
    c1 =  max(1.5,min(2.5,c1));
    c2 =  max(1.5,min(2.5,c2));

    T(i) = fitnessgbest;
end

end
View Code

MeanD.m

function Status = MeanD(x,g,D)
%MEANDISTANCE 此处显示有关此函数的摘要
%   此处显示详细说明
% rows = size(x,1);
for i = 1:size(x,1)
    distan = 0;
    for j = 1:size(x,1)
        if i==j
            continue;
        end
        for d = 1:D
            distan = distan + (x(j,d)-x(i,d))^2;
%             distance = sqrt((x(j,1)-x(i,1))^2+(x(j,2)-x(i,2))^2)+distance;
        end
    end
    distance = sqrt(distan);
    MeanDis(i) = distance/(size(x,1)-1);  
end;
% Status = MeanDis;

MaxDis = MeanDis(1);
MinDis = MeanDis(1);
for i = 1:size(x,1)
    if MeanDis(i)>MaxDis
        MaxDis = MeanDis(i);
    end
    if MeanDis(i)<MinDis
        MinDis = MeanDis(i);
    end
end
Status = (MeanDis(g)-MinDis)/(MaxDis-MinDis);


end
View Code

Others:

模糊分类:
0
0
0
规则库
模拟退火
进化计算
精英学习策略(ELS)
进化状态估计(ESE)
“没有免费午饭”定理