精华内容
下载资源
问答
  • 通过老师对算法代码的简单介绍,我对于粒子寻优算法结构有了一个大致的了解 首先根据老师说的原则,c1从小变到大,c2从大变到小,权重w先从大的开始,惯性大的冲得快,后期再往小改。 初始值: 首先更改了c2的...

    一、粒子算法的概述

    粒子群算法是一种智能优化算法。关于智能,个人理解,不过是在枚举法的基础上加上了一定的寻优机制。试想一下枚举法,假设问题的解空间很小,比如一个函数 y = x^2 ,解空间在[-1,1],现在求这个函数的最小值,我们完全可以使用枚举法,比如在这里,在解空间[-1,1]上,取1000等分,也就是步长为0.002,生成1000个x值,然后代入函数中,找到这1000个最小的y就可以了。然而实际情况不是这样的,比如为什么选1000等分,不是1w,10w等分,很显然等分的越大,计算量也就越大,带来的解当然也就越精确,那么实际问题中如何去平衡这两点呢?也就是既要计算量小(速度快),也要准确(精度高),这就是智能算法的来源了,一般的智能算法基本上都是这样的,在很大的搜索空间上,即保证了速度快,也能比较好的找到最优解。
    粒子群算法(也称PSO算法),也是一种进化算法,模拟生物群体的觅食行为,是一种群体智能算法,类似的算法想遗传算法,模拟退火算法等等。PSO是通过当前已知种群寻找到的所有解来决定新的解的寻找方向,也就是新解的生成方式依赖于这些种群历史上寻找的所有解。
    开始随机生成一堆种群,那么这些种群之间的每个个体可以相互交流,比如下一时刻,A告诉B说我的解比你好,那么B就往A那个地方飞,也就是B的解朝着A的解方向变化,当然所有粒子间都这样操作,想想一旦粒子群中间有一个粒子找到了一个最优解,是不是所有的粒子会一窝蜂朝着这个方向而去了,而在这个去的过程中,万一某个粒子找到了一个更好的解,那它还会走吗?不会了,它就告诉剩下的所有粒子说我的解更好呀,大家快来呀(很无私的),然后所有粒子又一窝蜂的照着这个粒子方向前进,当然在这个前进的过程中可能又会产生新的解,就这样一步步的迭代,最终慢慢的趋近于一个最优解,这个解是不是全局最优解,不知道,可能是,也可能不是,取决于原始问题的复杂程度,也取决于粒子前进的多少等等。
    粒子群算法相对于其他算法来说还是有很多优点的,典型的就是计算速度很快,在每次迭代时,所有粒子同时迭代,是一种并行计算方式,而且粒子的更新方式简单,朝着一个优秀解方向更新。这个优秀解包括两个部分:
    1)一个是朝着自己在迭代的历史上找到的个体最优解gbest前进
    2)一个是朝着群体在得带历史上找到的全体最优解zbest前进
    现在还有一个问题就是每次迭代的时候更新多少呢?也就是自变量的增加步长了,我们用一个速度量V来表示,也就是每个粒子的更新速度了,公式化的表示就是这样的:
    在这里插入图片描述
    从上面的速度V的更新而已看到,c1那项就是朝着自己的最优解前进,c2那一项就是朝着全局最优解那前进。用简单的图表示如下:
    在这里插入图片描述

    二、粒子算法的步骤

    粒子群的核心部分就是上面说到的那两个公式,一个是速度的更新方式,另一个是位置的更新方式,重点还是速度的更新方式;

    总结来说,粒子群的算法步骤如下:
    1.初始化粒子群个体;
    2.计算每个个体的适应度值(函数值)作为评判好坏的标准;
    3.找到每个个体自己在所有迭代过程中的最优解Pbest;
    4.找到所有个体在所有迭代过程中的最优解Zbest;
    5.根据速度公式更新速度;
    6.根据位置公式更新位置;
    7.重复步骤二直至迭代次数结束

    1. pso算法c1、c2、w的组合测试:

    首先根据老师说的原则,c1从小变到大,c2从大变到小,权重w先从大的开始,惯性大的冲得快,后期再往小改。
    初始值:
    在这里插入图片描述

    之后再用公式来表示各变量以达到实验目的:
    在这里插入图片描述
    运行算法,可以看到最优解已经浮出水面:在这里插入图片描述
    接着我们可以再运行九次以求其最佳迭代次数均值:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    416+997+477+648+245+856+286+380+423+586=5314
    5314/10=531.4 为最佳迭代次数
    即当
    c1=-0.001 * maxgen+1.5=-0.001 * 531.4+1.5= 0.9686
    c2=0.0005 * maxgen+1=0.0005 * 531.4+1=1.2657
    w=-0.0007 * maxgen+0.9=-0.0007 * 531.4+0.9=0.52802
    时更接近于寻得最优解
    结果测试:
    在这里插入图片描述

    2.pso算法dim与sizepop的组合测试:

    初始值:
    在这里插入图片描述
    在现有维度上改变种群规模:
    200->400->800->1000->10000

    在这里插入图片描述
    在这里插入图片描述

    经过多次试验可以确定当种群规模增加到400时,寻找到最优解的迭代次数多数处于200-300次之间,偶尔会迭代到900多次以上。

    到800时:
    在这里插入图片描述
    可以明显感觉到迭代时速度的力不从心,虽然收敛速度较快,集中在100-200次之间。

    1000时
    在这里插入图片描述
    可以看到实验结果很不稳定,但多集中于300-400之间

    10000时
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    当种群规模达到10000,它找到最优解的速度非常之快,,尤其前期最优适应度跌落的幅度很大,但迭代的十分缓慢,所以在得出结果时我就暂停了…
    下面就看看维度下降会产生什么影响
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    可以看到,当维度降为8时,最优适应度跌落的更快,能更快找到最优解。
    将种群规模降为1000,再继续观察
    在这里插入图片描述
    可以看到基本在100次以内能查找到最优解。
    再将维度降低
    在这里插入图片描述

    基本几乎在50次以内可以得出最优解。
    由此,可以得出结论,种群规模不变,维度越低查找到最优解的速度越快,维度不变,种群规模越大越易于查找到最优解。

    展开全文
  • 文章目录一、理论基础1、算法简介2、杂草特性二、案例背景1、问题描述2、解题思路及步骤(1) 初始化种群(2) 繁殖(3) 空间分布三、MATLAB程序实现1、清空环境变量2、初始化参数3、构建解空间4、迭代寻优5、结果...

    一、理论基础

    1、算法简介

    入侵杂草算法(Invasive Weed Optimization,IWO)是C.Lucas和A.R.Mehrabian在2006年通过模拟自然界中杂草扩散入侵过程的随机搜索仿生优化算法。该算法是一种很强大的智能优化算法,具有易于理解、收敛性好、鲁棒性强、易于实现、结构简单等优点,目前,IWO 算法已成功应用在 DNA 序列计算、线性天线设计、电力线通信系统资源分配、图像识别、图像聚类、约束工程设计、压电激励器放置等实际工程问题。

    2、杂草特性

    杂草最突出的特点是,种子通过动物、水及风等多种传播途径随机散布在田野里,每个种子独立地使用田里的资源,找到适合的生长空间,发挥强大的适应能力,并且充分利用生长环境中的资源,能够获取充分的营养快速生长。在杂草进化和繁殖的过程中,生存能力强的种子繁殖得更快,产生较多的种子。反之,不太适应环境的种子,产生较少的种子。

    二、案例背景

    1、问题描述

    本案例的寻优函数为sphere函数:f(x)=i=1nxi2,xi[10,10],i=1,2,,n(1)f(\boldsymbol x)=\sum_{i=1}^n x_i^2,\quad x_i∈[-10,10],i=1,2,\cdots,n\tag{1}本案例取n=5n=5
    sphere函数的三维立体图形如图1所示。
    在这里插入图片描述

    图1 sphere函数的三维立体图形

    2、解题思路及步骤

    (1) 初始化种群

    设置相关参数,设定最大种群规模NmaxN_{max},初始化种群数N0N_0,所求问题维数dd,最大迭代次数itermaxiter_{max},繁殖的种子数的上下限SmaxS_{max}SminS_{min},非线性调和因子(方差缩减指数)nn

    (2) 繁殖

    每个杂草产生的种子数的表达式:S=floor(Smin+ffminfmaxfmin(SmaxSmin))(2)S=floor(S_{min}+\frac{f-f_{min}}{f_{max}-f_{min}}(S_{max}-S_{min}))\tag{2}其中,floorfloor是MATLAB的一个函数,表示“向下取整”,即取不大于该值的最大整数;ff代表当前杂草的适应度值,当前种群中杂草适应度值范围为[fmin,fmax][f_{min},f_{max}],一颗杂草所能繁殖种子的数量范围为[Smin,Smax][S_{min},S_{max}]

    (3) 空间分布

    杂草产生的种子在父代个体的周围形成正态分布,其均值为零,标准差为σcur\sigma_{cur}。第ii个杂草产生的第ss个种子的位置为:Positioni,s=Positioni+N(0,σ2),SminsSmax(3)Position_{i,s}=Position_i+N(0,\sigma^2),S_{min}≤s≤S_{max}\tag{3}其中,σ\sigma为标准差。随着进化次数的增加,标准差可按下式计算:σcur=(itermaxiteritermax)n(σinitσfinal)+σfinal(4)\sigma_{cur}=\left(\frac{iter_{max}-iter}{iter_{max}}\right)^n(\sigma_{init}-\sigma_{final})+\sigma_{final}\tag{4}其中,σcur\sigma_{cur}是当前标准差,itermaxiter_{max}为最大进化迭代次数,iteriter为当前进化迭代次数。σinit\sigma_{init}σfinal\sigma_{final}分别为标准差初始值和最终值。每轮进化对应的标准差并不一样,随着进化的进行,标准差从σinit\sigma_{init}一直变化到σfinal\sigma_{final};一般情况下设置为n=3n=3

    (4) 竞争性排斥规则

    竞争性排斥规则是经过多次进化之后,当种群规模达到NmaxN_{max},按照适应度值大小对所有的个体进行排序,排除适应度较差的个体,保留其余个体。即此算法是先通过杂草迅速繁殖,占领生存空间,而后保留了竞争力更强的杂草继续进行空间搜索。

    3、算法流程

    IWO算法主要步骤如图2所示。
    在这里插入图片描述

    图2 IWO算法流程图

    三、MATLAB程序实现

    利用MATLAB提供的函数,可以方便地在MATLAB环境下实现上述步骤。

    1、清空环境变量

    程序运行之前,清除工作空间Workspace中的变量及Command Window中的命令。具体程序如下:

    %% Clear environment variables
    clc;
    clear;
    close all;
    

    2、问题设定

    在进行优化之前,需要明确优化的目标函数。具体程序如下:

    %% Problem Definition
    CostFunction = @(x) Sphere(x);     % 目标函数
    nVar = 5;              % 决策变量数
    VarSize = [1 nVar];    % 决策变量矩阵大小
    VarMin = -10;       % 决策变量下限
    VarMax = 10;        % 决策变量上限
    

    Sphere函数代码如下:

    function z = Sphere(x)
    %% 目标函数
        z = sum(x.^2);
    end
    

    3、参数设置

    代码如下:

    %% IWO Parameters
    MaxIt = 500;    % 最大迭代次数
    
    nPop0 = 10;     % 初始种群规模
    nPop = 25;      % 最大种群规模
    
    Smin = 0;       % 繁殖种子数下限
    Smax = 5;       % 繁殖种子数上限
    
    Exponent = 3;             % 方差缩减指数(非线性调和因子)
    sigma_initial = 0.5;      % 标准差初值
    sigma_final = 0.001;	  % 标准差终值
    

    4、初始化杂草种群

    在计算之前,需要对杂草种群进行初始化。同时,为了加快程序的执行速度,对于程序中涉及的一些过程变量,需要预分配其存储容量。具体程序如下:

    %% Initialization
    % 置空植物矩阵(包含位置和适应度值)
    empty_plant.Position = [];
    empty_plant.Cost = [];
    pop = repmat(empty_plant, nPop0, 1);    % 初始种群矩阵
    for i = 1:numel(pop)
        % 初始化位置
        pop(i).Position = unifrnd(VarMin, VarMax, VarSize);
        % 初始化适应度值
        pop(i).Cost = CostFunction(pop(i).Position);
    end
    % 初始化最优函数值历史记录
    BestCosts = zeros(MaxIt, 1);
    

    5、迭代优化

    迭代寻优为整个算法的核心。首先根据公式(4)计算标准差,获得最优和最差的目标函数值,并初始化子代种群;然后进行繁殖操作,根据公式(2)计算每个杂草个体产生的种子数;之后,遍历每个杂草产生的种子,根据杂草产生的种子在父代个体的周围服从N(0,σ2)N(0,\sigma^2)和公式(3)产生相应的个体,添加进子代种群;最后,合并父代和子代,并根据竞争性生存法则剔除额外成员(如果多余的话),保存每代的最优解。

    %% IWO Main Loop
    for it = 1:MaxIt
        % 更新标准偏差
        sigma = ((MaxIt - it)/(MaxIt - 1))^Exponent * (sigma_initial - sigma_final) + sigma_final;
        % 获得最佳和最差的目标值
        Costs = [pop.Cost];
        BestCost = min(Costs);
        WorstCost = max(Costs);
        % 初始化子代种群
        newpop = [];
        % 繁殖
        for i = 1:numel(pop)
            % 比例系数
            ratio = (pop(i).Cost - WorstCost)/(BestCost - WorstCost);
            % 每个杂草产生的种子数
            S = floor(Smin + (Smax - Smin)*ratio);
            for j = 1:S
                % 初始化子代
                newsol = empty_plant;         
                % 生成随机位置
                % randn是一种产生标准正态分布的随机数或矩阵的函数
                newsol.Position = pop(i).Position + sigma * randn(VarSize); 
                % 边界(下限/上限)处理
                newsol.Position = max(newsol.Position, VarMin);
                newsol.Position = min(newsol.Position, VarMax);
                % 子代的目标函数值
                newsol.Cost = CostFunction(newsol.Position);
                % 添加子代
                newpop = [newpop
                          newsol];  % #ok
            end
        end
        % 合并种群
        pop = [pop
               newpop];
        % 种群排序
        [~, SortOrder] = sort([pop.Cost]);
        pop = pop(SortOrder);
        % 竞争排除(删除额外成员)
        if numel(pop)>nPop
            pop = pop(1:nPop);
        end
        % 保存最佳种群
        BestSol = pop(1);
        % 保存最优函数值历史记录
        BestCosts(it) = BestSol.Cost;
        % 显示迭代信息
        disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCosts(it))]);
    end
    

    6、结果显示

    为了更为直观地对结果进行观察和分析,以图形的形式将结果显示出来,具体程序如下:

    %% Results
    figure;
    % plot(BestCosts, 'LineWidth', 2);
    semilogy(BestCosts, 'r', 'LineWidth', 2);
    xlabel('Iteration');
    ylabel('Best Cost');
    grid on;
    

    IWO算法进化过程如图3所示。
    在这里插入图片描述

    图3 IWO算法迭代进化过程

    四、参考文献

    [1] Mehrabian A R , Lucas C . A novel numerical optimization algorithm inspired from weed colonization[J]. Ecological Informatics, 2006, 1(4):355-366.
    [2] Kawadia V , Kumar P R . Principles and protocols for power control in wireless ad hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2005, 23(1):76-88.
    [3] Meng Fan-zhi, Wang Huan-zhao, He Hui. Connected coverage protocol using cooperative sensing model for wireless sensor networks[J]. Journal of Electronics,2011,39(4):722-799.

    展开全文
  • 文章目录一、理论基础1、发现者位置更新2、跟随者位置更新3、警戒者位置更新4、SSA算法伪代码二、仿真...相比传统算法,麻雀搜索算法结构简单、易于实现,且控制参数较少,局部搜索能力较强。该算法在单峰、多峰等基

    一、理论基础

    麻雀搜索算法(Sparrow Search Algorithm, SSA)是2020年提出的一种新兴的元启发式算法,它与粒子群算法、蜻蜓优化算法等同属于基于群体的社会化特征优化的群智能算法。该算法通过不断更新个体位置,模拟麻雀觅食和反捕食行为。相比传统算法,麻雀搜索算法的结构简单、易于实现,且控制参数较少,局部搜索能力较强。该算法在单峰、多峰等基准函数上的表现优于粒子群算法、蚁群算法等传统算法。
    在麻雀搜索算法中,将个体区分为发现者、跟随者和警戒者,每个个体位置对应一个解。根据算法设定,警戒者所占种群比例10%~20%,而发现者和跟随者是动态变化的, 即一只个体成为发现者必然意味着另一只个体将成为跟随者。按照分工划分,发现者主要为整个种群提供觅食方向和区域,跟随者则是跟随发现者进行觅食,警戒者负责对于觅食区域的监视。在觅食过程中,通过不断更新三者位置,完成资源的获取。
    设种群中有nn只麻雀,则由所有个体组成的种群可表示为X=[x1,x2,,xn]TX=[x_1,x_2,\cdots,x_n]^T,个体各自对应的适应度函数为F=[f(x1),f(x2),,f(xn)]TF=[f(x_1),f(x_2),\cdots,f(x_n)]^T。具体表示为:X=[x1,1x1,2x1,dx2,1x2,2x2,dxn,1xn,2xn,d](1)X=\begin{bmatrix} x_{1,1} & x_{1,2} & \cdots & \cdots & x_{1,d} \\x_{2,1} & x_{2,2} & \cdots & \cdots & x_{2,d} \\\vdots & \vdots & \vdots & \vdots & \vdots\\ x_{n,1} & x_{n,2} & \cdots & \cdots & x_{n,d} \\ \end{bmatrix}\tag{1}F=[f([x1,1x1,2x1,d])f([x2,1x2,2x2,d])f([xn,1xn,2xn,d])](2)F=\begin{bmatrix} f(\begin{bmatrix}x_{1,1} & x_{1,2} & \cdots & \cdots & x_{1,d}\end{bmatrix}) \\f(\begin{bmatrix}x_{2,1} & x_{2,2} & \cdots & \cdots & x_{2,d}\end{bmatrix})\\ \vdots\\ f(\begin{bmatrix}x_{n,1} & x_{n,2} & \cdots & \cdots & x_{n,d}\end{bmatrix}) \end{bmatrix}\tag{2}

    1、发现者位置更新

    发现者的位置更新方式如下:xi,jt+1={xi,jtexp(iα×itermax),R2<STxi,jt+QL,    R2ST(3)x_{i,j}^{t+1}=\begin{dcases}x_{i,j}^t\cdot \exp(\frac{-i}{\alpha×iter_{max}}),R_2<ST\\x_{i,j}^t+Q\cdot L,\quad\quad\quad\quad \,\,\,\,R_2≥ST\end{dcases}\tag{3}其中,tt表示当前迭代次数,xi,jtx_{i,j}^t表示在第tt代中第ii只麻雀在第jj维的位置,α(0,1)\alpha∈(0,1)itermaxiter_{max}是最大迭代次数,R2R_2表示报警值,STST表示安全阈值,QQ是服从正态分布的随机数,LL1×dim1×\dim的全1矩阵,dim\dim表示维度。发现者位置更新方式可总结如下:当R2<STR_2<ST时,意味着觅食区域周围没有捕食者,发现者可以广泛搜索食物;当R2STR_2≥ST时,意味着捕食者出现,所有发现者都需要飞往安全区域。

    2、跟随者位置更新

    跟随者的位置更新方式如下:xi,jt+1={Qexp(xworsttxi,jti2),  i>n2xPt+1+xi,jtxPt+1A+L,in2(4)x_{i,j}^{t+1}=\begin{dcases}Q\cdot\exp(\frac{x_{worst}^t-x_{i,j}^t}{i^2}),\quad\quad\quad\,\, i>\frac n2\\x_P^{t+1}+|x_{i,j}^t-x_P^{t+1}|\cdot \boldsymbol A^+\cdot L,\quad i≤\frac n2\end{dcases}\tag{4}其中,xworsttx_{worst}^t表示第tt代适应度最差的个体位置,xPt+1x_P^{t+1}表示第t+1t+1代中适应度最佳的个体位置。A\boldsymbol A表示1×dim1×\dim的矩阵,矩阵中每个元素随机预设为-1或1,A+=AT(AAT)1\boldsymbol A^+=\boldsymbol{A^T}\boldsymbol{(AA^T)^{-1}}。跟随者位置更新方式可总结为:当i>n2i>\frac n2时,表示第ii个加入者的适应度较低,没有同发现者竞争食物的资格,需要飞往其他区域觅食;当in2i≤\frac{n}2时,加入者将在最优个体xPx_P近觅食。

    3、警戒者位置更新

    警戒者位置更新方式如下:xi,jt+1={xbestt+βxi,jtxbestt,  fifgxbestt+k(xi,jtxbesttfifw+ε),fi=fg(5)x_{i,j}^{t+1}=\begin{dcases}x_{best}^t+\beta\cdot|x_{i,j}^t-x_{best}^t|,\quad\quad\,\, f_i≠f_g\\x_{best}^t+k\cdot(\frac{x_{i,j}^t-x_{best}^t}{|f_i-f_w|+\varepsilon}),\quad f_i=f_g\end{dcases}\tag{5}其中,xbesttx_{best}^t表示第tt代中全局最优位置,β\beta为控制步长,服从均值为0,方差为1的正态分布,k[1,1]k∈[-1,1]ε\varepsilon设置为常数,用以避免分母为0。fif_i表示当前个体的适应度值,fgf_gfwf_w表示目前全局最优和最差个体的适应度值。警戒者位置更新方式可总结为:当fifgf_i≠f_g时,意味着该个体处于种群外围,需要采取反捕食行为,不断变换位置获得更高 的适应度;当fi=fgf_i=f_g时,意味着该个体处于种群中心,它将不断接近附近的同伴,以此远离危险区域。

    4、SSA算法伪代码

    在这里插入图片描述

    图1 SSA算法的基本框架

    二、仿真实验与分析

    为了使算法更具说服力,在所有情况下,我们对每个测试函数进行30次独立试验。在每个实验中,迭代的最大次数为1000,种群大小设置为100(n=100n=100)。GWO的参数设置如下:aa的值从2线性减少到0,r1,r2r_1,r_2[0,1][0,1]中的随机向量;PSO的参数为c1=c2=1.49445,w=0.729c_1=c_2=1.49445,w=0.729;GSA的参数为G0=100,α=20G_0=100,\alpha=20。SSA的参数设置如下:发现者数量和SDSD分别占20%和10%,ST=0.8ST=0.8。以文献[1]的F1、F2、F3为例。
    下图为对比曲线。
    在这里插入图片描述在这里插入图片描述在这里插入图片描述最大值、最小值、平均值及标准差显示如下:

    函数:F1
    GWO:最大值: 1.9014e-90,最小值:1.1467e-93,平均值:2.6184e-91,标准差:5.3549e-91
    PSO:最大值: 25.6849,最小值:2.8582,平均值:9.0364,标准差:5.9129
    GSA:最大值: 6.5868e-18,最小值:2.3286e-18,平均值:4.0924e-18,标准差:1.0661e-18
    SSA:最大值: 0,最小值:0,平均值:0,标准差:0
    函数:F2
    GWO:最大值: 8.0552e-52,最小值:4.8965e-54,平均值:1.5053e-52,标准差:2.105e-52
    PSO:最大值: 14.9366,最小值:4.5229,平均值:8.2907,标准差:2.6433
    GSA:最大值: 1.2197e-08,最小值:8.179e-09,平均值:1.0214e-08,标准差:9.821e-10
    SSA:最大值: 9.1086e-306,最小值:0,平均值:3.0362e-307,标准差:0
    函数:F3
    GWO:最大值: 1.7551e-17,最小值:1.049e-25,平均值:7.2717e-19,标准差:3.1948e-18
    PSO:最大值: 255.9549,最小值:38.1862,平均值:112.098,标准差:53.1931
    GSA:最大值: 215.1596,最小值:44.459,平均值:106.1498,标准差:36.8177
    SSA:最大值: 0,最小值:0,平均值:0,标准差:0
    

    结果表明,该算法在搜索精度、收敛速度和稳定性等方面均优于现有算法。

    三、参考文献

    [1] Jiankai Xue & Bo Shen (2020) A novel swarm intelligence optimization approach: sparrow search algorithm, Systems Science & Control Engineering, 8:1, 22-34, DOI:10.1080/21642583.2019.1708830.
    [2] 段玉先,刘昌云.基于Sobol序列和纵横交叉策略的麻雀搜索算法[J/OL].计算机应用:1-9[2021-05-28].http://kns.cnki.net/kcms/detail/51.1307.TP.20210525.1453.002.html.

    四、Matlab仿真程序

    下载地址:
    https://download.csdn.net/download/weixin_43821559/19146332

    展开全文
  • 利用配电网络具有树状层次结构的特点,提出了一种逐层筛选寻优的配电网无功优化算法。 文中将辐射网逐层分解为随电压线性变化的等值负荷,并推导了等值负荷参数递推计算的方法;对 含电容器、变压器分接头的控制策略...
  • 寻优算法之遗传算法

    千次阅读 2018-04-24 07:58:22
    简单的遗传算法 导言 研究生研究的领域就是用启发算法来解决超多目标优化问题,所谓的超多目标就是要同时优化目标维数超过3维且目标之间具有一定矛盾性的问题。例如从深圳到北京的交通路线,我们若只考虑时间与价格...
        

    简单的遗传算法

    导言

    研究生研究的领域就是用启发算法来解决超多目标优化问题,所谓的超多目标就是要同时优化目标维数超过3维且目标之间具有一定矛盾性的问题。例如从深圳到北京的交通路线,我们若只考虑时间与价格这两个目标问题(二维多目标问题),会存在时长最短但是价格昂贵的路线选择(例如航班直达),也会存在价格最便宜但是很花时间的路线(例如辗转火车公交),不会存在时长最短价格最便宜的最优路线。解决多目标问题的启发算法里,遗传算法和粒子群算法的论文较多,今天讲一下简单的遗传算法。

    算法思想

    遗传算法主要是用达尔文进化论的观点,优胜劣汰适者生存,能更好地适应环境的个体将会保留下来,这些拥有较好适应度的个体基因会传给下一代,让好基因广为流传,活埋不好的基因。遗传算法主要包括种群初始化,交叉,变异和环境选择四个主要操作。遗传算法属于随机性算法,不能找到最优解,只能找到近优解,除非是非常简单的问题。

    算法过程

    比如我们要解决一个简单的单目标问题,求解目标f的最大值,x1、x2变量有约束范围

    max f (x1, x2) = 21.5 + x1·sin(4 pi x1) + x2·sin(20 pi x2)
    s. t. -3.0 <= x1 <= 12.1
            4.1 <= x2 <= 5.8
    

    对于这类连续问题,其实可以不采用网上最基础的二进制编码来进行单点交叉和单点变异的操作了。实数也可以,只要把交叉和变异操作采用模拟二进制交叉simulated binary crossover(SBX)和多项式变异Polynomial mutation就好了。所以这里的种群个体可以采用[x1,x2]的数值来代表一个个体。

    首先进行种群初始化,返回一个大小为100的种群列表,每个元素代表一个由两个变量构成的个体

    pop_size = 100    #种群规模
    population = []
    dec_num = 2    #变量个数
    dec_min_val = (-3, 4.1)
    dec_max_val = (12.1, 5.8)
    
    def init(population, pop_size, dec_num, dec_min_val, dec_max_val):
        rangeRealVal = [dec_max_val[i]-dec_min_val[i] for i in range(dec_num)]    #范围长度
        for i in range(pop_size):
            tempIndividual=[]
            for j in range(dec_num):
                temp = random.uniform(0, 1)*rangeRealVal[j]+dec_min_val[j]  #确保变量在范围类内 
                tempIndividual.append(temp)
            population.append(tempIndividual)   #population为[[dec1,dec2],[],[]..[]]   

    初始化种群后开始选择种群个体交配产生下一代,这里采用SBX,是通过二进制单点交叉改进的。例如现在有个体A的x1=9,个体B的x1变量为18,根据变量x1的约束范围可以算出x1的二进制编码长度,假设长度为6,则个体A的x1=001001,个体B有X1=010010,根据二进制单点交叉,选定随机一个index,例如index=3,则将两个个体的前三位互换,得到new_x1=010001和new_x2=001010。而SBX则可以进行实数编码,其过程如下

    clipboard.png

    ~x1和~x2是根据父代x1和x2进行SBX后的子代,代码如下,随机挑选两个父代并产生两个子代。

    Pc = 0.9     #交叉概率 小于这个概率的个体才进行交叉操作
    Dc = 1    #交叉步长,步长越大,产生子代离父代越远的概率越大
    def SBXcross_2c(population, Pc, dec_num, dec_min_val, dec_max_val, Dc):
        offspring = copy.deepcopy(population)
        for i in range(0, len(population), 2):     #随机选两个产生两个
            if random.random() > Pc:
                continue
            index1 = 0
            index2 = 0
            while index1 == index2:    #保证选到的两个父代不相同
                index1 = random.randint(0, len(population) - 1)
                index2 = random.randint(0, len(population) - 1)
            #对两个个体执行SBX交叉操作
            for j in range(dec_num):    #个体的第j个变量
                lower = dec_min_val[j]
                uper = dec_max_val[j]
                parent1 = population[index1][j]
                parent2 = population[index2][j]
                r = random.random()
                if r <= 0.5:    #betaq是采用了概率模型计算出来的,可以不用管,照着套就好了
                    betaq = (2*r)**(1.0/(Dc+1.0))
                else:
                    betaq = (0.5/(1.0-r))**(1.0/(Dc+1.0))
    
                child1 = 0.5*((1+betaq)*parent1+(1-betaq)*parent2)    #
                child2 = 0.5*((1-betaq)*parent1+(1+betaq)*parent2)
                child1 = min(max(child1, lower), uper)  #边界保护,以防超出
                child2 = min(max(child2, lower), uper)
    
                offspring[index1][j] = child1
                offspring[index2][j] = child2
        return offspring    #返回新生成种群

    产生的子代需要进行变异操作,这可以有一定几率让解跳出局部最优,去寻找全局最优,多项式变异的过程如下

    clipboard.png

    公式可以不用理解,往上套!变异过程的代码如下

    Pm = 0.1    #变异概率,小于这个概率的个体进行变异
    Dm = 1    #变异步长
    def ploy_mutation(offspring, Pm, dec_num, dec_min_val, dec_max_val, Dm):
        for i in range(len(offspring)):
            for j in range(dec_num):    
                r = random.random()
                if r <= Pm:
                    y = offspring[i][j]     #第i个个体的第j个变量
                    low = dec_min_val[j]
                    up = dec_max_val[j]
                    delta1 = 1.0*(y-low)/(up-low)   #1.0保证精度不为整数
                    delta2 = 1.0*(up-y)/(up-low)
                    r = random.random()
                    mut_pow = 1.0/(Dm+1.0)  #最外层因子
                    if r <= 0.5:
                        var = 1.0-delta1
                        lambda_ = 2.0*r+(1.0-2.0*r)*(var**(Dm+1.0))
                        deltaq = lambda_**mut_pow-1.0
                    else:
                        var = 1.0-delta2
                        lambda_ = 2.0*(1.0-r)+2.0*(r-0.5)*(var**(Dm+1.0))
                        deltaq = 1.0-lambda_**mut_pow
                    y = y+deltaq*(up-low)
                    y = min(up, max(y, low))
                    offspring[i][j] = y

    这样进行交叉和变异操作后,我们就得到了父代种群population和子代群众offspring.接下来的就是优胜劣汰的环境选择。环境选择的一部分太多不同的策略,基础本采用轮盘赌的那种策略是交叉过程中子代完全取代父代,然后根据适应值大小来决定轮盘概率的大小。自己很少采用这种方式,采用的是稳态进化的方式。主流的有N+1,N+q,和N+N模式,N+1模式是N个父代产生一个个体的时候,就要N+1种群里淘汰一个最差的个体。N+N采用的是N个父代产生N个子代,然后从2N个种群里选择最好的N个个体进入下一代,上面population+offspring就是N+N的模式了。

    N+N环境选择的代码如下

    popobj =[] #存储个体的适应值,这里为目标函数y的大小,适应值越高越需要留下
    merge = population + offspring
    
    def selection(merge, popobj, popsize,population):
        del popobj[:]
        del population[:]    #用来存储被保留的种群进入下一代
        for i in merge:    #计算每个个体的适应值大小
            popobj.append(object_fun(i))
        #根据适应值大小排序,取前N个拥有高适应值的个体存留下来
        index = sorted(range(len(popobj)), key=lambda k: popobj[k], reverse=True) #从小到大的索引值
        for i in range(popsize):
            population.append(merge[index[i]])
        score = popobj[index[0]]    #计算当前拥有最高适应值的个体的目标函数值y
        return score
       
    def object_fun(p):
        x1 = p[0]
        x2 = p[1]
        y = 21.5 + x1 * math.sin(4 * math.pi * x1) + x2 * math.sin(20 * math.pi * x2)
        return y

    目标函数图如下
    clipboard.png

    通过遗传算法的得到的最大y值为

    clipboard.png

    这篇文章的代码放在github页面上:https://github.com/kugua233/G...
    代码也写了二进制单点模拟交叉,父代每次只产生一个子代的方式的交叉方式,差分进化的方式以后再补吧。代码量比较少,没有去优化,想用为一个遗传算法小框架的话,还是要组织代码结构,可以进行不同的初始化,交叉,变异和环境选择操作。

    展开全文
  • 为了在多粒度空间中寻找一个合适的粒度空间来对不确定性目标概念进行近似描述,使误分类代价与测试代价之和尽可能小,给出属性代价贡献率的定义,并提出一种代价敏感的粒度寻优算法.实验结果表明,所提出算法能适用于...
  • 文章目录一、理论基础1、确定集群边界范围2、计算集群层次周围的温度3、计算帝企鹅间的距离4、帝企鹅位置更新5、EPO算法伪代码二、仿真实验三、参考文献四、Matlab程序 一、理论基础 帝企鹅优化(Emperor Penguin ...
  • 伺服控制系统常用参数寻优算法

    千次阅读 2018-01-26 10:04:14
    参数寻优——转自mishidemudong  参数寻优背景  参数寻优问题随处可见,举几个例子。   1. 小明假期结束回校,可以坐火车,可以坐汽车,可以坐飞机,还可以走着,小明从哪条路去学校更好呢?   2. ...
  • 各种群体寻优算法的比较(半原创)

    万次阅读 多人点赞 2019-01-10 16:31:20
    【蚁群优化算法、粒子群优化算法、细菌觅食算法、萤火虫算法、人工鱼群算法】 计算机技术不断发展,...群体智能是基于种群行为对给定的目标进行寻优的启发式搜索算法,其的核心是由众多简单个体组成的群体能够通...
  • ABC-RNDS方案采用双层网络拓扑结构,首先使用最小生成树法构建骨干网络,再使用人工蜂群优化算法通过网络参数优和限制中继节点总数的方法实现网络寿命的延长。实验验证分析表明,在成本和连通性受约束的条件下,...
  • 基于蚁群节点寻优的贝叶斯网络结构算法研究.pdf,K2算法是学习贝叶斯网络结构的经典算法。针对K2算法依赖最大父节点数和节点序的不足,以及蚁群算法搜索空间庞大的问题,提出了一种新的贝叶斯结构学习算法 MWST ACO ...
  • 相对退火法,遗传算法更有可能跳出局部最解,得到全局最解 遗传算法核心思想(代码的核心四个部分) 遗传算法是仿照了达尔文的生物进化概念:“物竞天择,适者生存” 选择:选择更适合生存者,淘汰劣势者。 ...
  • 粒子群算法源于复杂适应系统(Complex Adaptive System,CAS)。CAS理论于1994年正式提出,CAS中的成员称为主体。比如研究鸟群系统,每个鸟在这个系统中就称为主体。主体有适应性,它能够与环境及其他的主体进行交流...
  • 相对退火法,遗传算法更有可能跳出局部最解,得到全局最解 遗传算法核心思想(代码的核心四个部分) 遗传算法是仿照了达尔文的生物进化概念:“物竞天择,适者生存” 选择:选择更适合生存者,淘汰劣势者。...
  • 最短路径选择\快速路径寻优的GIS网络数据结构设计及算法研究.nh
  • 最短路径寻优 (以下关于Dijstra的说明,是借用算法与数据结构的发帖说明、侵权即删) 原帖链接 最短路径寻优 如上图所示、如何寻求从 A 出发到 G 点的最短路径呢? Dijstra算法就是要求出这个最短的路径; 让我们...
  • 【GA】GA算法寻优

    2021-05-04 15:53:44
    具备隐并行性和较好的全局寻优能力。GA在进行全局搜索和优化搜索时不依赖梯度信息,只需要搜索方向的目标函数和相应的适应度函数,所以GA提供了一种求解复杂系统问题的通用框架。 GA算法的特点 GA从问题的串集开始...
  • 粒子群优算法

    2019-12-03 20:44:38
    文章目录粒子群优算法一,粒子群算法的概述二,粒子群算法的流程三 ,代码实现%% 清空环境%% 参数初始化%% 产生初始粒子和速度%% 个体极值和群体极值%% 迭代寻优%种群更新%% 结果分析四 ,运行结果4.1改变c1,c2,w值多次...
  • 如题,并不是用遗传算法优化神经网络的结构,而是神经网络预测后可以整个函数什么的吧 然后遗传算法去寻找最值什么的 我有个范文在附件里,散尽金币求解答,下面是我自己写的神经网络的代码,请高手改正,剩下的...
  • 本博客首先转载了一篇关于遗传算法的文章,通过这个简单的例子来学习遗传算法,然后自编了一个利用遗传算法寻找最小花费路径的程序。 一、遗传算法的手工模拟计算示例(转自 ...
  • 实际上,原始的蚁群算法就是用来解决TSP问题,不过稍加改进之后可以像遗传算法一样解决函数寻优问题。 函数寻优   问题本身很简单,四个变量x1,x2,x3,x4组成方程y = x1平方+x2平方+x3平方+x4平方,四个变量取值...
  • 最短路径寻优适用场景: 1.公路/铁路/道路网最短路径规划问题 2.网络拓扑结构最短路径优化问题 问题描述 给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。我们...
  • 针对目前利用启发式算法学习贝叶斯网络结构易陷入局部最优、寻优效率低的问题,提出一种基于混合樽海鞘-差分进化算法的贝叶斯网络结构学习算法。该算法在种群划分阶段提出自适应的规模因子平衡局部搜索与全局搜索,...
  • A*算法

    千次阅读 2011-10-24 14:43:38
    译者说:无论是现在风靡的网页游戏,还是老牌的网络游戏,径几乎都是难以回避的一个话题,而径必然从A*算法开始。关于A*国外相关的资料相当丰富,很多时候让我们为难的还不是具体的算法,而是A*的基本思路和概念...
  • 利用函数双向S-粗集的结构,给出函数迁移的信度特征,函数集Q的下近似信度特征,函数集Q的上近似信度特征;利用这些结果,给出函数双向S-粗集的信度特征,提出函数双向S-粗集的随机结构与随机定理。函数双向S-粗集的...
  • %% BP网络训练 % %初始化网络结构 net=newff(inputn,outputn,5); net.trainParam.epochs=100; net.trainParam.lr=0.1; net.trainParam.goal=0.0000004; %网络训练 net=train(net,inputn,outputn); %% BP网络预测 %...
  • 存储分配方式 顺序存储结构用一段连续的存储单元一次存储线性表的数据元素 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素 ...顺序存储结构寻妖预分配存储空间,分大了容易造成空间浪费,分小了...
  • A*算法新手入门

    千次阅读 2010-06-05 11:31:00
    译者说:无论是现在风靡的网页游戏,还是老牌的网络游戏,径几乎都是难以回避的一个话题,而径必然从A*算法开始。关于A*国外相关的资料相当丰富,很多时候让我们为难的还不是具体的算法,而是A*的基本思路和概念...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,558
精华内容 2,623
关键字:

寻优算法结构