精华内容
下载资源
问答
  • DE、SaDE、JADE、SHADE、L-SHADE算法整理

    千次阅读 2021-02-06 13:21:06
    DE(Differential Evolution)算法 A. 基本算法原理 DE算法仍然是EA算法的一种,所以在学习DE算法之前,先让我们复习一下EA(Evolution Algorithm)算法的流程图: 在开始进行具体的流程介绍之前,先让我们来定义一些...

    DE(Differential Evolution)算法

    A. 基本算法原理

    DE算法仍然是EA算法的一种,所以在学习DE算法之前,先让我们复习一下EA(Evolution Algorithm)算法的流程图:
    Steps of EA
    在开始进行具体的流程介绍之前,先让我们来定义一些东西

    Solution

    根据问题的维度D,我们用一个D维的向量来表示为一个Solution
    需要注意的是,每一个维度都应该有自己的上界和下界

    Population

    我们将固定数量(NP)个Solution打包起来,这样就形成了一个Population
    Relationship

    B. 流程详解

    1. 初始化

    每个Solution中每一个维度的值都初始化为该维度上下限中的随机值,公式为
    x i , j , 0 = M i n j + r a n d i , j [ 0 , 1 ] ⋅ ( M a x j − M i n j ) x_{i,j,0}=Min_{j}+rand_{i,j}\left[ 0,1 \right]\cdot \left( Max_{j}-Min_{j} \right) xi,j,0=Minj+randi,j[0,1](MaxjMinj)

    这里的i是Solution的序号、j是维度序号、0是第0代

    2. 突变

    对于每一个Solution X i , G X_{i,G} Xi,G,从同代中随机选择其它3个Solution X r 1 i , G 、 X r 2 i , G 、 X r 3 i , G X_{r_{1}^{i},G}、X_{r_{2}^{i},G}、X_{r_{3}^{i},G} Xr1i,GXr2i,GXr3i,G来计算这个Solution的Mutant vector V i , G V_{i,G} Vi,G,公式如下
    V i , G = X r 1 i , G + F ⋅ ( X r 2 i , G − X r 3 i , G ) V_{i,G}=X_{r_{1}^{i},G}+F\cdot(X_{r_{2}^{i},G}-X_{r_{3}^{i},G}) Vi,G=Xr1i,G+F(Xr2i,GXr3i,G)

    i i i是正在处理的Solution的序号,由于不同的Solution所使用到的三个随机Solution不同,因此打上了上标用以提醒
    G G G是当前的代数
    F F F是比例因子(Scaling factor),其取值为(0,1.5)的常数

    3. 重组

    有两种重组方式,但都离不开 C r Cr Cr,它是该维度变量是否更新的依据,这个值是预先设定好的
    1. Binomial/Uniform Crossover

    公式如下
    u i , j , G = { v i , j , G , i f ( r a n d i , j [ 0 , 1 ] ≤ C r o r j = j r a n d ) x i , j , G , o t h e r w i s e u_{i,j,G}=\left\{ \begin{aligned} v_{i,j,G}&,&& if\left( rand_{i,j}\left[ 0,1 \right]\le{C}r\quad or\quad j=j_{rand} \right) \\ x_{i,j,G}&,&& otherwise \end{aligned}\right. ui,j,G={vi,j,Gxi,j,G,,if(randi,j[0,1]Crorj=jrand)otherwise

    u i , j , G u_{i,j,G} ui,j,G是经过重组之后生成的新的Solution U i , G U_{i,G} Ui,G j j j位置处的值
    v i , j , G v_{i,j,G} vi,j,G是经过突变之后生成的Mutant vector V i , G V_{i,G} Vi,G j j j位置处的值
    x i , j , G x_{i,j,G} xi,j,G是原Solution X i , G X_{i,G} Xi,G j j j位置处的值
    j r a n d = r a n d [ 0 , D ] j_{rand}=rand[0,D] jrand=rand[0,D],为了避免 C r Cr Cr太小,我们引入该值,来随机一些位置,强制它们发生改变

    2. Exponential(two-point modulo) Crossover
    这里需要先引入两个值 n 、 L n、L nL n n n是直接随机得到的, L L L需要进行一些计算,这里给了 L L L的伪代码

    L=0;
    DO
    {
    	L=L+1;
    }WHILE((rand[0,1]<=Cr)AND(L<D))
    

    n n n确定了Crossover的起点, L L L确定了Crossover的终点
    Crossover的公式如下
    u i , j , G = { v i , j , G , f o r   j = ⟨ n ⟩ D , ⟨ n + 1 ⟩ D , . . . , ⟨ n + L − 1 ⟩ D x i , j , G , f o r    a l l    o t h e r    j ∈ [ 1 , D ] u_{i,j,G}=\left\{ \begin{aligned} v_{i,j,G}&,&& for\: j=\langle n\rangle _{D},\langle n+1\rangle _{D},...,\langle n+L-1\rangle _{D} \\ x_{i,j,G}&,&& for\; all\; other\; j\in [1,D] \end{aligned}\right. ui,j,G={vi,j,Gxi,j,G,,forj=nD,n+1D,...,n+L1Dforallotherj[1,D]

    u i , j , G u_{i,j,G} ui,j,G是经过重组之后生成的新的Solution U i , G U_{i,G} Ui,G j j j位置处的值
    v i , j , G v_{i,j,G} vi,j,G是经过突变之后生成的Mutant vector V i , G V_{i,G} Vi,G j j j位置处的值
    x i , j , G x_{i,j,G} xi,j,G是原Solution X i , G X_{i,G} Xi,G j j j位置处的值

    简而言之,就是将 X i , G X_{i,G} Xi,G n n n n + L − 1 n+L-1 n+L1位置的值替换为 V i , G V_{i,G} Vi,G中对应位置的值

    4. 选择

    使用 f ( X i , G ) f(X_{i,G}) f(Xi,G)表示 X i , G X_{i,G} Xi,G的fitness,如果我们想要后代的fitness更小,那么使用如下公式生成后代 X i , G + 1 X_{i,G+1} Xi,G+1
    X i , G + 1 = { U i , G , i f   f ( U i , G ) ≤ f ( X i , G ) X i , G , i f   f ( U i , G ) > f ( X i , G ) X_{i,G+1}=\left\{ \begin{aligned} U_{i,G}&,&& if\: f(U_{i,G})\le f(X_{i,G})\\ X_{i,G}&,&& if\: f(U_{i,G})> f(X_{i,G}) \end{aligned}\right. Xi,G+1={Ui,GXi,G,,iff(Ui,G)f(Xi,G)iff(Ui,G)>f(Xi,G)

    U i , G U_{i,G} Ui,G X i , G X_{i,G} Xi,G的fitness一样大时,我们都会选择 U i , G U_{i,G} Ui,G

    C. 例子

    1.问题

    我们想要通过DE算法得到使 f ( x , y ) = x 2 + y 2 f(x,y)=x^2+y^2 f(x,y)=x2+y2取到最小值时的点

    2.解决问题

    1. Initialization
    根据问题得知,维度为2;我们初始化5个Solution,每个维度的取值范围都设为[-10,10]
    X 1 , 0 = [ 3 , 0 ] ; X 2 , 0 = [ 7 , 2 ] ; X 3 , 0 = [ − 2 , 6 ] ; X 4 , 0 = [ − 1 , 7 ] ; X 5 , 0 = [ 7 , − 6 ] ; X_{1,0}=[3,0]; X_{2,0}=[7,2]; X_{3,0}=[-2,6]; X_{4,0}=[-1,7]; X_{5,0}=[7,-6]; X1,0=[3,0];X2,0=[7,2];X3,0=[2,6];X4,0=[1,7];X5,0=[7,6];
    2. Mutation
    为了得到 X 1 , 0 X_{1,0} X1,0的Mutant vector,我们随机选取 X 2 , 0 、 X 3 , 0 、 X 5 , 0 X_{2,0}、X_{3,0}、X_{5,0} X2,0X3,0X5,0,并随机 F = 1 F=1 F=1,得到
    V 1 , 0 = [ 7 2 ] + 1 × { [ − 2 6 ] − [ 7 − 6 ] } = [ − 2 14 ] V_{1,0}={7\brack 2}+1\times \begin{Bmatrix}{-2\brack 6}-{7\brack -6}\end{Bmatrix}={-2\brack 14} V1,0=[27]+1×{[62][67]}=[142]
    3. Recombination
    选择Uniform Crossover方法,设置 C r Cr Cr为0.5
    x 1 , 1 , 0 x_{1,1,0} x1,1,0,根据 r a n d [ 0 , 1 ] rand[0,1] rand[0,1]生成随机数 0.6 > C r 0.6>Cr 0.6>Cr,所以 u 1 , 1 , 0 = x 1 , 1 , 0 = 3 u_{1,1,0}=x_{1,1,0}=3 u1,1,0=x1,1,0=3
    x 1 , 2 , 0 x_{1,2,0} x1,2,0,根据 r a n d [ 0 , 1 ] rand[0,1] rand[0,1]生成随机数 0.3 < C r 0.3<Cr 0.3<Cr,所以 u 1 , 2 , 0 = v 1 , 2 , 0 = 14 u_{1,2,0}=v_{1,2,0}=14 u1,2,0=v1,2,0=14
    所以 U 1 , G = [ 3 , 14 ] U_{1,G}=[3,14] U1,G=[3,14]
    4. Selection
    计算 X 1 , 0 X_{1,0} X1,0的fitness f ( 3 , 0 ) = 3 2 + 0 2 = 9 f(3,0)=3^2+0^2=9 f(3,0)=32+02=9
    计算 U 1 , 0 U_{1,0} U1,0的fitness f ( 3 , 14 ) = 3 2 + 1 4 2 = 205 f(3,14)=3^2+14^2=205 f(3,14)=32+142=205
    因为 205 > 9 205>9 205>9,所以 X 1 , 1 = X 1 , 0 = [ 3 , 0 ] X_{1,1}=X_{1,0}=[3,0] X1,1=X1,0=[3,0]
    5. 重复
    同样的步骤计算完剩余Solution后,重复步骤2-4,直至结果达到可接受的地步

    D. 补充

    1. 突变

    在突变时我们用到的为最基础的突变策略,被命名为“DE/rand/1”,另外还有4种突变策略
    DE/rand/1
    V i , G = X r 1 i , G + F ⋅ ( X r 2 i , G − X r 3 i , G ) V_{i,G}=X_{r_{1}^{i},G}+F\cdot(X_{r_{2}^{i},G}-X_{r_{3}^{i},G}) Vi,G=Xr1i,G+F(Xr2i,GXr3i,G)
    DE/best/1
    V i , G = X b e s t , G + F ⋅ ( X r 1 i , G − X r 2 i , G ) V_{i,G}=X_{best,G}+F\cdot(X_{r_{1}^{i},G}-X_{r_{2}^{i},G}) Vi,G=Xbest,G+F(Xr1i,GXr2i,G)
    DE/current-to-best/1
    V i , G = X i , G + F ⋅ ( X b e s t , G − X i , G ) + F ⋅ ( X r 1 i , G − X r 2 i , G ) V_{i,G}=X_{i,G}+F\cdot(X_{best,G}-X_{i,G})+F\cdot(X_{r_{1}^{i},G}-X_{r_{2}^{i},G}) Vi,G=Xi,G+F(Xbest,GXi,G)+F(Xr1i,GXr2i,G)
    DE/best/2
    V i , G = X b e s t , G + F ⋅ ( X r 1 i , G − X r 2 i , G ) + F ⋅ ( X r 3 i , G − X r 4 i , G ) V_{i,G}=X_{best,G}+F\cdot(X_{r_{1}^{i},G}-X_{r_{2}^{i},G})+F\cdot(X_{r_{3}^{i},G}-X_{r_{4}^{i},G}) Vi,G=Xbest,G+F(Xr1i,GXr2i,G)+F(Xr3i,GXr4i,G)
    DE/rand/2
    V i , G = X r 1 i , G + F 1 ⋅ ( X r 2 i , G − X r 3 i , G ) + F 2 ⋅ ( X r 4 i , G − X r 5 i , G ) V_{i,G}=X_{r_{1}^{i},G}+F_{1}\cdot(X_{r_{2}^{i},G}-X_{r_{3}^{i},G})+F_{2}\cdot(X_{r_{4}^{i},G}-X_{r_{5}^{i},G}) Vi,G=Xr1i,G+F1(Xr2i,GXr3i,G)+F2(Xr4i,GXr5i,G)

    命名规则:DE/x/y/z中,DE指是Differential Evolution的mutation方法,x指的是基于哪个父代,y指的是用了几对随机父代的差,z指的是用的是哪种重组方法(exp与bin)
    best:当前population中最好的solution

    2. Cr的设置

    当遇到可分的问题时,Cr一般取小值
    当遇到不可分的问题时,Cr一般取较大的值

    SaDE(Self-Adaptive DE)算法

    SaDE算法是对DE算法的改进,所以基本逻辑不变,下面只介绍SaDE中比较特别的部分

    A. 突变策略自适应

    选取DE/rand/1/bin、DE/rand-to-best/2/bin、DE/rand/2/bin、DE/current-to-rand/1四种突变策略作为待选策略
    通过LP(Learning Period)代的试验,得到每种策略的成功率

    每次突变时记录使用的突变策略,经过LP代后,可以得到各个突变策略使用了多少次,假设A策略使用了N次
    在进行选择时,如果选择的是生成的 U i , G U_{i,G} Ui,G,那么生成这个 U i , G U_{i,G} Ui,G时使用的策略被视为成功了1次,记录下每个策略各成功了多少次,假设A策略成功了n次
    A策略的成功率就是 n / N n/N n/N

    LP代后,每个Solution在进行突变操作时,根据训练得到四种策略的成功率随机选取一种策略作为这次突变的策略

    B. F值的设定

    F值被设定为服从正态分布N(0.5,0.3)的随机数
    每一个population内的F值是通用的

    C. Cr值自适应

    Cr值被设定为服从正态分布 N ( C R m , S t d ) N(CR_{m},Std) N(CRm,Std)的随机数,其中 S t d = 0.1 Std=0.1 Std=0.1 C R m CR_{m} CRm的初始值为0.5,且会不断更新;
    更新规律:
    Cr值自适应流程图

    JADE算法

    JADE算法是对DE算法的改进,所以基本逻辑不变,下面只介绍JADE中比较特别的部分

    A. 突变策略的改进

    1. 修改DE/current-to-best/1算法

    (1) 使用 X b e s t , G p X_{best,G}^p Xbest,Gp代替 X b e s t , G X_{best,G} Xbest,G
    DE/current-to-best/1算法公式为
    V i , G = X i , G + F i ⋅ ( X b e s t , G − X i , G ) + F i ⋅ ( X r 1 i , G − X r 2 i , G ) V_{i,G}=X_{i,G}+F_{i}\cdot(X_{best,G}-X_{i,G})+F_{i}\cdot(X_{r_{1}^{i},G}-X_{r_{2}^{i},G}) Vi,G=Xi,G+Fi(Xbest,GXi,G)+Fi(Xr1i,GXr2i,G)
    使用 X b e s t , G p X_{best,G}^p Xbest,Gp代替 X b e s t , G X_{best,G} Xbest,G,从而将公式改写为
    V i , G = X i , G + F i ⋅ X b e s t , G p − X i , G ) + F i ⋅ ( X r 1 i , G − X r 2 i , G ) V_{i,G}=X_{i,G}+F_{i}\cdot X_{best,G}^p-X_{i,G})+F_{i}\cdot(X_{r_{1}^{i},G}-X_{r_{2}^{i},G}) Vi,G=Xi,G+FiXbest,GpXi,G)+Fi(Xr1i,GXr2i,G)
    X b e s t , G p X_{best,G}^p Xbest,Gp X b e s t , G X_{best,G} Xbest,G不同,它并不是直接选择这一个population中fitness最好的那个Solution,而是从当前population中随机选择fitness排名在 100 p 100p 100p%中一个Solution。

    一般来说, p ∈ [ 0.05 , 0.2 ] p\in [0.05,0.2] p[0.05,0.2]
    (2)改变 X r 2 i , G X_{r_{2}^{i},G} Xr2i,G的选择范围
    X i , G 、 X b e s t , G p 、 X r 1 i , G X_{i,G}、X_{best,G}^p、X_{r_{1}^i,G} Xi,GXbest,GpXr1i,G不变,仍然是从 P P P(当前population)中选取, X r 2 , G i X_{r_{2},G}^i Xr2,Gi改为从 P ∪ A P\cup A PA中选择
    集合A:每当子代将父代取代时,我们将父代转存到集合A中,并不断随机从A中剔除一些父代,使得A的大小小于NP

    2. Cr的自适应

    每代中的每个Solution的Cr都是符合正态分布 N ( μ C r , 0.1 ) N(\mu _{Cr},0.1) N(μCr,0.1)且大小被约束在[0,1]内的随机数
    其中 μ C r \mu _{Cr} μCr遵循自更新公式
    μ C r = ( 1 − c ) ⋅ μ C r + c ⋅ m e a n A ( S C r ) \mu _{Cr}=(1-c)\cdot \mu _{Cr}+c\cdot mean_A(S_{Cr}) μCr=(1c)μCr+cmeanA(SCr)

    μ C r \mu _{Cr} μCr初始值为0.5
    c是一个常数,一般来说 1 / c ∈ [ 5 , 20 ] 1/c\in[5,20] 1/c[5,20]
    m e a n A mean_A meanA指计算算术平均数
    S C r S_{Cr} SCr为本代中每次子代solution取代父代 solution时的Cr的集合

    3. F的自适应

    每代中的每个Solution的 F i F_{i} Fi都是符合柯西分布 C ( μ F , 0.1 ) C(\mu _{F},0.1) C(μF,0.1)的随机数

    F i > 1 F_i>1 Fi>1时会被直接设为1
    F i ≤ 0 F_i\le 0 Fi0时会重新随机

    μ F \mu _F μF比例参数为0.1,且符合自更新公式
    μ F = ( 1 − c ) ⋅ μ F + c ⋅ m e a n L ( S F ) \mu _{F}=(1-c)\cdot \mu _{F}+c\cdot mean_L(S_{F}) μF=(1c)μF+cmeanL(SF)

    μ F \mu _F μF初始值为0.5
    c是一个常数,一般来说 1 / c ∈ [ 5 , 20 ] 1/c\in[5,20] 1/c[5,20]
    m e a n L ( S F ) = ∑ F ∈ S F F 2 ∑ F ∈ S F F mean_L(S_F)={\sum_{F\in S_F}{F^2}\over \sum_{F\in S_F}{F}} meanL(SF)=FSFFFSFF2
    S F S_{F} SF为本代中每次子代solution取代父代 solution时的F的集合

    SHADE(Success-History based Adaptive DE)算法

    SHADE算法是对JADE算法的修改
    JADE算法使用单个的 μ C r \mu _{Cr} μCr μ F \mu_ {F} μF,SHADE则是在 M C R M_{CR} MCR M F M_{F} MF中随机选择 μ C r \mu _{Cr} μCr μ F \mu_ {F} μF来生成Cr和F

    我们用 M C R M_{CR} MCR来表示存储了 H H H个成功的 μ C r \mu_{Cr} μCr的集合,用 M F M_{F} MF来表示存储了 H H H个成功的 μ F \mu_{F} μF的集合, H H H的值是自定义的

    数组更新
    当更新完一轮后,从头覆盖原位置来更新数组

    L-SHADE(SHADE with Linear Population Reduction)算法

    L-SHADE算法实为增加了线性参数递减的SHADE算法
    为了加快约束速度,我们根据当前已更新的参数个数线性减少一个population中的solution的数,参数的减少规律如图中黄线所示
    LPSR

    LPSR:Linear Population Size Reduction

    展开全文
  • 基于改进SHADE算法的船舶电力系统推力分配.pdf
  • LSHADE算法matlab.m

    2019-08-09 18:21:35
    Tanabe和Fukunaga [18]通过使用线性群体大小减少进一步改进了SHADE算法,并称为变体LSHADE。 在LSHADE中,DE的种群大小通过线性函数不断地减少。
  • L-shade.zip

    2020-07-13 09:28:13
    冠军算法L-SHADE的matlab版本,其中付一个测试函数,运行test文件即可,需要测试其他函数可以
  • LSHADE 算法的代码 ,但是调试时提示有错误
  • 自适应参数的DE算法——JADE,L-SHADE

    千次阅读 多人点赞 2020-07-12 10:40:08
    最近复写一个DE[1](差分进化算法)参数的自适应策略的变体L-SHADE[2](CEC冠军算法)的matlab版本,发现其提出的自适应策略对DE改进效果明显,于是把其前身JADE[3]整合到一起做个笔记(公式太多,就直接用文章里的...


    最近复写一个DE[1](差分进化算法)参数的自适应策略的变体L-SHADE[2](CEC冠军算法)的matlab版本,发现其提出的自适应策略对DE改进效果明显,于是把其前身JADE[3]整合到一起做个笔记(公式太多,就直接用文章里的截图了)。
    简单记录差分进化算法的进化机制:初始化——变异——交叉——选择,其中关键参数为变异步骤的变异系数F与交叉步骤的交叉概率CR,经典DE算法中变异系数F设定为固定值0.5,而交叉概率CR则随机从[0,1]中产生。
    (代码下载~~:https://download.csdn.net/download/Bernard_S/12608560,附一个测试函数,需要其他的可以联系我~~ ,突然发现下载的C币会自动增长,需要的就直接评论留邮箱吧)

    JADE

    JADE的改进为如下几个方面:
    **1.提出新的变异策略:**DE/current-to-best/1, 公式如下
    在这里插入图片描述
    其中,Xbest,g为随机选择一个种群中适应度排序前p*Np(Np为种群规模)的个体,p为给定比例(文中设定P为[5%,25%])。Xr1,g为种群中随机选择的个体,Xr2,g为当前种群与外部存档集合中随机选择的个体,外部存档A储存每代进化中变异交叉失败的个体,其规模固定为NP,超出规模则随机删减其中个体。
    2.自适应的参数调整策略
    JADE针对变异系数F与交叉概率CR的自适应策略如下:
    首先初始化两个参数的Mu
    在这里插入图片描述
    每一代进化中,参数更新方式如下
    在这里插入图片描述
    其中randn为状态分布,randc则为柯西分布。我认为这里选择柯西分布原因如下:大家知道,对比正态分布,柯西分布的尾部更为平滑,即选取到分布两侧值的概率更大,所以文章提到柯西分布使得变异系数F更为多样,可以避免算法早熟收敛。

    每一代进化中,Mu的更新方式如下
    在这里插入图片描述
    在这里插入图片描述
    其中,SF,SCR为成功参数集合,即本代交叉变异有效的个体对应的参数F,CR构成的集合。c为给定的值(文章给定1/c=[5,20])。meanA为标准的算数均值,meanL为 Lehmer mean,其作用是传递更大的F,以提高收敛速率,计算公式如下:
    在这里插入图片描述
    个人理解其自适应参数策略如下: 将成功进化的个体对应的参数记录下来,并依据这些参数选取对应的均值,依照均值构建概率分布并在其中选择下一代参数。这样逐渐的随着迭代参数会自适应调节,且不会使得参数过于一致从而失去了多样性。

    LSHADE

    对比上述的JADE,LSHADE采用相同的变异策略DE/current-to-best/1,而其主要改进为参数的自适应调节策略:

    1.基于历史记忆的参数策略
    初始化历史集 MCR(1:H)=0.5,MF(1:H)=0.5
    在这里插入图片描述
    其中,H为给定值(文章给定H=100)。

    参数的更新

    在这里插入图片描述
    其中,ri为[1,H]间的随机整数,┴为自定义终止值,即当Mcr满足该终止值后,CR置零,强制每代中仅一个维度进行交叉以提高收敛速率。

    历史集的更新

    文章给出的伪码如下:在这里插入图片描述
    其中SF,SCR仍为成功参数集合。即每一次迭代更新历史集中的一个位置的值,超出位置H则从位置1进行新一轮更新。更新过程中,若成功参数集为空,则该位置学习上一位置的值。否则采用meanWL进行计算,其公式如下:
    在这里插入图片描述
    其中f()为对应适应度值,该公式即通过适应度变化幅度确定权重在原本的Lehmer mean中考虑了权重的影响。
    值得注意的是,从历史更新伪代码中可见,当某一代Scr均小于零以后,MCR的值设为终止值,同时CR强制置零。而由于上一代MCR终止,会使得之后所有的MCR终止。这个策略可能是认为所有Scr均小于零意味着注重于局部开采的个体更有益于当前的搜索,于是不再对CR进行更新从而强制所有的个体开始专注开采。

    2.群体规模的自适应
    LSHADE定义了群体规模的自适应方法
    在这里插入图片描述
    其中Ninit为初始种群规模,Nmin为最终种群规模(文章给定为4)MAX_NEF为最大适应度评价次数,NEF为当前适应度评价次数。同时每代中多出的个体将依适应度删去较差的。
    这种设计可能是为了在后期将算法专注于开采,由于将不必要的个体删除,使得同样适应度评价次数下保留的个体可以多次进化以挖掘最优解。

    参考文献

    [1] R. Storn and K. Price, “Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces,” J. Global Optimiz., vol. 11, no. 4, pp. 341–359, 1997.
    [2] Tanabe R, Fukunaga AS. Improving the search performance of SHADE using linear population size reduction. In: IEEE Congress on Evolutionary Computation (CEC), Beijing, China: IEEE Press, 2014.
    [3] J. Zhang and A. C. Sanderson, “JADE: Adaptive Differential Evolution With Optional External Archive,” IEEE Tran. Evol. Comput., vol. 13, no. 5, pp. 945–958, 2009.

    展开全文
  • GAs\ES\DE with Real Decision Variables Floating Decision Variable Coding and Operators. For some real optimization problems using binary coding is not natural. And another issue is computational ...

    GAs\ES\DE with Real Decision Variables

    • Floating Decision Variable Coding and Operators.

      For some real optimization problems using binary coding is not natural. And another issue is computational complexity.

      So it’s better to use real number (integer or floating) for some certain problems. However, the operators of crossover and mutation are different

    • Operators for real-coded problems

      • Crossover

        1-point crossover or 2-point crossover is changed as:

        E.g. 1-point crossover, two parents are X = [ x 1 , x 2 , . . . x m ]   a n d   Y = [ y 1 , y 2 , . . . y m ] X=[x_{1},x_{2},...x_{m}]\,and\,Y=[y_{1},y_{2},...y_{m}] X=[x1,x2,...xm]andY=[y1,y2,...ym]

        The result of crossover is:

        X ′ = [ x 1 , x 2 , . . . , y k , y k + 1 , . . . , y m ] X'=[x_{1},x_{2},...,y_{k},y_{k+1},...,y_{m}] X=[x1,x2,...,yk,yk+1,...,ym] and Y ′ = [ y 1 , y 2 , . . . , x k , x k + 1 , . . . , x m ] Y'=[y_{1},y_{2},...,x_{k},x_{k+1},...,x_{m}] Y=[y1,y2,...,xk,xk+1,...,xm]

        /# I think it maybe a little stupid…

        Arithmetical Operator

        y n e w = λ 1 y o l d + λ 2 x o l d y_{new}=\lambda_{1}y_{old}+\lambda_{2}x_{old} ynew=λ1yold+λ2xold, and x n e w = λ 2 y o l d + λ 1 x o l d x_{new}=\lambda_{2}y_{old}+\lambda_{1}x_{old} xnew=λ2yold+λ1xold

        λ 1 \lambda_{1} λ1 and λ 2 \lambda_{2} λ2 are both manually set parameters.

        Some specific situations can be identified:

        • Convex crossover: λ 1 + λ 2 = 1 ,        λ 1 , λ 2 > 0 \lambda_{1}+\lambda_{2}=1,\,\,\,\,\,\, \lambda_{1},\lambda_{2}>0 λ1+λ2=1,λ1,λ2>0
        • Average crossover: λ 1 = λ 2 = 1 2 \lambda_{1}=\lambda_{2}=\frac{1}{2} λ1=λ2=21
        • Affine crossover: λ 1 + λ 2 = 1 \lambda_{1}+\lambda_{2}=1 λ1+λ2=1 and one of them is permitted to take negative values.
        • Linear crossover: λ 1 + λ 2 = c ,      λ 1 , λ 2 > 0 \lambda_{1}+\lambda_{2}=c, \,\,\,\,\lambda_{1},\lambda_{2}>0 λ1+λ2=c,λ1,λ2>0, and c is a positive constant, eg. c=2

        This strategy is creative enough but there is a need to ensure the generated offspring are in the feasible region.

        Direction Based Crossover: x n e w = x o l d + r ( y o l d − x o l d )     i f : f ( y o l d ) ≥ f ( x o l d ) x_{new}=x_{old}+r(y_{old}-x_{old})\,\,\,if:f(y_{old})\geq f(x_{old}) xnew=xold+r(yoldxold)if:f(yold)f(xold)

        r is a uniform random number in [0,1]

        Some Other Operators

        PCX – Parent Centric Crossover

        SBX – Simulated Binary Crossover
        BLX – Blend Crossover
        SPX - Simplex Crossover
        UNDX- unimodal Normal Distribution Crossover

        # These can be investigated if interested. Obviously I am not the interested student, neither are you.

      • Mutation

        Uniform mutation: Just generate a new value within the search range

        Gaussian mutation: x n e w = x o l d + N ( o , σ ) x_{new}=x_{old}+N(o,\sigma) xnew=xold+N(o,σ), where N ( 0 , σ ) N(0,\sigma) N(0,σ) is Gaussian distribution.

        Arithmetic mutation: x n e w = x o l d + r ( b u p − x o l d ) ( 1 − t T ) b x_{new}=x_{old}+r(b_{up}-x_{old})(1-\frac{t}{T})^{b} xnew=xold+r(bupxold)(1Tt)b or

        x n e w = x o l d − r ( x o l d − b l o w ) ( 1 − t T ) b x_{new}=x_{old}-r(x_{old}-b_{low})(1-\frac{t}{T})^{b} xnew=xoldr(xoldblow)(1Tt)b

        Two thoices are selected with equal probability.

        Where r is uniform random number in [0,1], t is the current generation number, T is the maximum number of generations. b is the manually set parameter. b u p b_{up} bup and b l o w b_{low} blow are the upper and lower bounds for this variable.

        Direction Based Mutation

        x n e w = x o l d + r d x_{new}=x_{old}+rd xnew=xold+rd

        r is a uniform random number in [0,1] and d is the fitness ascent direction, as same as the gradient of f(x). However, usually it is obtained by numerically estimated.

        If the mutated offspring move out of the fesible range, choose a random direction d to instead.

    • Evolution Strategy (ES)

      # Basically it’s all unimportant nonsense, so I copied the slide directly.

      Randomly generate an initial population of M solutions.
      Compute the fitness values of these M solutions.
      Use all initial vectors as parents to create M offspring solutions by Gaussian mutation i.e. Xnew=Xold+N(0, σ )
      N(0, σ ): normal distribution with zero mean variance σ
      Calculate the fitness of M solutions and prune the population to M fittest solutions.
      Go to the next step if the stopping condition is satisfied.
      Otherwise, go to Step 2.
      Choose the fittest one in the population in the last generation as the optimal solution.
      ES would be more effective, if we are able to obtain good initial solutions instead of randomly generated initial solutions.
      State of the art: Covariance Matrix Adapted ES – CMA-ES

    • Differential Evolution (DE)
      在这里插入图片描述

      • Initialization

        X j = [ x 1 , j , x 2 , j . . . , x i , j ] X_{j}=[x_{1,j},x_{2,j}...,x_{i,j}] Xj=[x1,j,x2,j...,xi,j] is the j t h j^{th} jth solution vector for i t h i_{th} ith dimensionality, i.e. individual

        X = [ X 1 , X 2 , . . . X j ] T X=[X_{1},X_{2},...X_{j}]^{T} X=[X1,X2,...Xj]T is a set of solution vector, i.e. population.

        In other word, j j j is the size of population and i i i is the number of decision variables.

        j j j could be chosen between 5 i i i to 10 i i i

        Just randomly initialize the population in fesible region.

      • Mutation

        V i G = X r 1 i , G + F ( X r 2 i , G − X r 3 i , G ) V_{i}^{G}=X_{r_{1}^{i},G}+F(X_{r_{2}^{i},G}-X_{r_{3}^{i},G}) ViG=Xr1i,G+F(Xr2i,GXr3i,G)

        X r 1 , X r 2 , X r 3 X_{r_{1}},X_{r_{2}},X_{r_{3}} Xr1,Xr2,Xr3 are all randomly select from the population, G is the number of generation. F is a constant from (0, 1.5) in the traditional DE.

      • Recombination

        Uniform Crossover:

        在这里插入图片描述

        v v v and x x x here are parents.

        在这里插入图片描述

        Low value of Cr is good for separable problems and high level of Cr is good for non-separable problems.

        Exponential Crossover:

        在这里插入图片描述

        < > D <>_{D} <>D denote a modulo function with modulus L
        在这里插入图片描述

        Eg. parents are : X i , G = [ 1 , 2 , 3 , 4 , 5 ] T X_{i,G}=[1,2,3,4,5]^{T} Xi,G=[1,2,3,4,5]T, V i , G = [ 6 , 7 , 8 , 9 , 10 ] T V_{i,G}=[6,7,8,9,10]^{T} Vi,G=[6,7,8,9,10]T

        Suppose n=3 and L=3 for this specific example

        < n > D , < n + 1 > D , . . . , < n + L − 1 > D <n>_{D},<n+1>_{D},...,<n+L-1>_{D} <n>D,<n+1>D,...,<n+L1>D= < 3 > 3 , < 4 > 3 , < 5 > 3 <3>_{3},<4>_{3},<5>_{3} <3>3,<4>3,<5>3=0,1,2

        when j=1 or j=2, the value of offspring comes from V i , G V_{i,G} Vi,G, i.e. 6,7

        Otherwise, the value of offspring comes from X i , G X_{i,G} Xi,G, i.e. 3,4,5

        Thus the offspring is u i , G = [ 6 , 7 , 3 , 4 , 5 ] u_{i,G}=[6,7,3,4,5] ui,G=[6,7,3,4,5]

      • Selection

        X i , G + 1 = u i , G   i f   f ( u i , G ≥ X i , G )   O t h e r w i s e X i , G X_{i,G+1}=u_{i,G}\,if\,f(u_{i,G}\geq X_{i,G})\,Otherwise X_{i,G} Xi,G+1=ui,Giff(ui,GXi,G)OtherwiseXi,G (for maximum problem)

      • Example

    在这里插入图片描述

    • Improved mutation strategy

    在这里插入图片描述

    • Improved DE: Self-Adaptive DE (SaDE)

      Mainly there are 3 parameters to be set: size of population, mutation probability and factor F

      • Size of population is set by user
      • A set of F are randomly generated from normal distribution N ( 0.5 , 0.3 ) N(0.5,0.3) N(0.5,0.3) and applied to each target vector in the current population
      • A set of Cr are randomly generated from normal distribution N ( C r m , S t d ) N(Cr_{m},Std) N(Crm,Std), C r m Cr_{m} Crm is initialized as 0.5
      • SaDE gradually adjusts the range of Cr:
        • Initialized Cr by N ( 0.5 , 0.1 ) N(0.5,0.1) N(0.5,0.1)
        • During LP number generations, record the actual Cr values generating better offspring.
        • After LP number generations, update C r m Cr_{m} Crm by the average of all successful Cr values
    • JADE

      A. V i , G = X i , G + F i ( X b e s t , G p − X i , G ) + F i ( X r 1 , G − X r 2 , G ) V_{i,G}=X_{i,G}+F_{i}(X_{best,G}^{p}-X_{i,G})+F_{i}(X_{r1,G}-X_{r2,G}) Vi,G=Xi,G+Fi(Xbest,GpXi,G)+Fi(Xr1,GXr2,G)

      X b e s t , G p X_{best,G}^{p} Xbest,Gp is a randomly chosen vector from top p% individuals in current population

      B. JADE can optionally make use of an external archive A, which stores the recently rejected inferior parents

      X b e s t , G p X_{best,G}^{p} Xbest,Gp, X i , G X_{i,G} Xi,G and X r 1 , G X_{r1,G} Xr1,G are selected from current population but X r 2 , G X_{r2,G} Xr2,G is selected from P ∪ A P\cup A PA

      C. For every generation, generate Cr with N ( μ c r , 0.1 ) N(\mu_{cr},0.1) N(μcr,0.1) and

      update μ c r = ( 1 − c ) μ c r + c . m e a n A ( S c r ) \mu_{cr}=(1-c)\mu_{cr}+c.mean_{A}(S_{cr}) μcr=(1c)μcr+c.meanA(Scr). S c r S_{cr} Scr is the set of all successful crossover Cr at generation G

      For every generation, generate Cr with C ( μ F , 0.1 ) C(\mu_{F},0.1) C(μF,0.1) (Cauchy distribution) and

      update μ F = ( 1 − c ) μ F + c . m e a n L ( S F ) \mu_{F}=(1-c)\mu_{F}+c.mean_{L}(S_{F}) μF=(1c)μF+c.meanL(SF). S F S_{F} SF is the set of all successful F at generation G and m e a n L mean_{L} meanL is the Lehmer mean:

      m e a n L ( S F ) = Σ F 2 Σ F mean_{L}(S_{F})=\frac{\Sigma F^{2}}{\Sigma F} meanL(SF)=ΣFΣF2

      A rule of thumb: 1/c chosen from [5, 20] and p from [5%, 20%]

    • Success-History based Adaptive DE (SHADE)

      A historical memory M C r   a n d   M F M_{Cr}\,and\,M_{F} MCrandMF are used to store the successful parameters. And randomly select one pair of them:

      在这里插入图片描述

      Successful Cr and F will be recorded in the memory

      At the end of generation, the contents of memory are updated by the mean values by S C r   a n d   S F S_{Cr}\,and\,S_{F} SCrandSF

    • L-SHADE: SHADE with Linear Population Reduction

      在这里插入图片描述

      Simple Variable Population Sizing (SVPS) and Deterministic Population Size Reduction (DPSR)

      Population size deceases as shown in the figure. SVPS is more general.


    Partical Swarm Optimization (PSO)

    • Variables in PSO

      x-vector: the position of particle (individual) i.e. candidate solution vector

      p-vector: the best x-vector so far

      v-vector: direction the particle will move to

      x-fitness: the fitness vector of x-vector

      p-fitness: the fitness vector of p-vector

      Update Equations:

      For each decision variable:

      V n e w = V o l d + φ 1 ∗ r a n d ( ) ∗ ( p i t s e l f − x o l d ) + φ 2 ∗ r a n d ( ) ∗ ( p g l o b a l − x o l d ) V_{new}=V_{old}+\varphi_{1}*rand()*(p_{itself}-x_{old})+\varphi_{2}*rand()*(p_{global}-x_{old}) Vnew=Vold+φ1rand()(pitselfxold)+φ2rand()(pglobalxold)

      X n e w = X o l d + V X_{new}=X_{old}+V Xnew=Xold+V

      φ 1 \varphi_{1} φ1 is called cognition component and φ 2 \varphi_{2} φ2 is called social component. Eiher of them can be set to 0. If both them are positive, the model is full model.

    • Initialization

      Randomly generate v-vector from [ − V m a x , V m a x ] [-V_{max}, V_{max}] [Vmax,Vmax].

      Randomly generate x_vector in feasible region.

    • Improvements on Velocities

      PSO with Inertia Factor

      V n e w = ω ∗ V o l d + φ 1 ∗ r a n d ( ) ∗ ( p i t s e l f − x o l d ) + φ 2 ∗ r a n d ( ) ∗ ( p g l o b a l − x o l d ) V_{new}=\omega*V_{old}+\varphi_{1}*rand()*(p_{itself}-x_{old})+\varphi_{2}*rand()*(p_{global}-x_{old}) Vnew=ωVold+φ1rand()(pitselfxold)+φ2rand()(pglobalxold)

      Where ω \omega ω is initialized to 1.0 and gradually reduced over generations.

      PSO with the Constriction Coefficient

      V n e w = k ∗ [ V o l d + φ 1 ∗ r a n d ( ) ∗ ( p i t s e l f − x o l d ) + φ 2 ∗ r a n d ( ) ∗ ( p g l o b a l − x o l d ) ] V_{new}=k*[V_{old}+\varphi_{1}*rand()*(p_{itself}-x_{old})+\varphi_{2}*rand()*(p_{global}-x_{old})] Vnew=k[Vold+φ1rand()(pitselfxold)+φ2rand()(pglobalxold)]

      Where φ = φ 1 + φ 2 \varphi=\varphi_{1}+\varphi_{2} φ=φ1+φ2, φ > 4 \varphi>4 φ>4 and k = 2 / ∣ 2 − φ − s q r t ( φ 2 − 4 φ ) ∣ k=2/|2-\varphi-sqrt(\varphi^{2}-4\varphi)| k=2/2φsqrt(φ24φ)

    • Particle Update Strategy

      Synchronously\Asynchronously

      Global PSO: Adjust the particle’s velocity according its personal best performance and the best performance achieved by all the particles (gbest).

      Local PSO: Adjust the particle’s velocity according its personal best performance and the best performance achieved by its neighborhood (glocal).

    • Dynamic multi-swarm PSO

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

      1. Small sized swarms

      2. Randomly re-group the swarm

    • Comprehensive learning PSO (CLPSO)

      v i d = ω ∗ v i d + c ∗ r a n d i d ∗ ( p b e s t f i ( d ) d − x i d ) v_{i}^{d}=\omega*v_{i}^{d}+c*rand_{i}^{d}*(pbest_{f_{i}(d)}^{d}-x_{i}^{d}) vid=ωvid+crandid(pbestfi(d)dxid)

      x i d + = v i d , d = 1 , 2 , . . . , D x_{i}^{d}+=v_{i}^{d},d=1,2,...,D xid+=vidd=1,2,...,D the number of decision variables.

      f i = [ f i ( 1 ) , f i ( 2 ) , . . . , f i ( D ) ] f_{i}=[f_{i}(1),f_{i}(2),...,f_{i}(D)] fi=[fi(1),fi(2),...,fi(D)] denotes a set of particle indices with respect to each dimension of the particle i i i. i.e. pbest of different particles in all dimensions. It take the value i i i with probability P c i Pc_{i} Pci.

      For each dimension of particle i i i, generate a random number, if the number is larger than P c i Pc_{i} Pci, the corresponding dimension of particle i i i will learn from its own pbest, otherwise learn from another particle’s pbest randomly selected or selected by tournament selection.

      If selected by tournament selection, the size is usually 2.

      We allow each particle to learn from its p b e s t f ( d ) d pbest_{f(d)}^{d} pbestf(d)d until the particle stop to improve for a certain number of generations, called the refreshing gap m m m (usually 7 generations).

      After that, we re-assign f i f_{i} fi for each particle i i i.

      Difference:

      Particle can learn from gbest of not only itself, but also other particles.

      Different dimensions may learn from different particle’s pbest.

      Instead of learn from two exemplars (pbest and gbest), each dimension of particle only learn from one exemplar (pbest). It may reduce deficiency of the premature convergenece.

    • Bandit Problem & Exploration and Exploitation (EE) problem.

    • Heterogeneous CLPSO (HCLPSO)

      Particles are re-grouped into two sub populations:

      1. Exploration group and 2. Exploitation group

      For group 1: v i d = ω ∗ v i d + c ∗ r a n d i d ∗ ( p b e s t f i ( d ) d − x i d ) v_{i}^{d}=\omega*v_{i}^{d}+c*rand_{i}^{d}*(pbest^{d}_{f_{i}(d)}-x_{i}^{d}) vid=ωvid+crandid(pbestfi(d)dxid)

      For group 2: v i d = ω ∗ v i d + c 1 ∗ r a n d 1 i d ∗ ( p b e s t f i ( d ) d − x i d ) + c 2 ∗ r a n d 2 i d ∗ ( g b e s t d − x i d ) v_{i}^{d}=\omega*v_{i}^{d}+c_{1}*rand_{1i}^{d}*(pbest^{d}_{f_{i}(d)}-x_{i}^{d})+c_{2}*rand_{2i}^{d}*(gbest^{d}-x_{i}^{d}) vid=ωvid+c1rand1id(pbestfi(d)dxid)+c2rand2id(gbestdxid)

      Adaptive Control Parameters

      在这里插入图片描述

    在这里插入图片描述


    Constraint Optimization

    • Constraint Handling

      The classical format of constraint problem:

      Minimize f ( x ) , x = [ x 1 , x 2 , . . . , x D ] f(x),x=[x_{1},x_{2},...,x_{D}] f(x),x=[x1,x2,...,xD]

      Subjected to g i ( x ) ≤ 0 , i = 1 , . . . , q g_{i}(x)\leq0, i=1,...,q gi(x)0,i=1,...,q

      and h j ( x ) = 0 , j = q + 1 , . . . , m h_{j}(x)=0, j=q+1,...,m hj(x)=0,j=q+1,...,m

      For convenience, the equality constraint can be transformed into inequality form with ϵ \epsilon ϵ by:

      ∣ h j ( x ) ∣ − ϵ ≤ 0 |h_{j}(x)|-\epsilon\leq0 hj(x)ϵ0

      Consequently, the formula can be described as:

      M i n i m i z e   f ( x ) , x = [ x 1 , x 2 , . . . , x D ] S u b j e c t e d   t o   G j ( x ) ≤ 0 ,   j = 1 , . . . , m w h e r e   G 1 , . . . , q = g 1 , . . . , q ( x ) , G q + 1 , . . . , m = ∣ h q + 1 , . . . , m ( x ) − ϵ ∣ Minimize\,f(x),x=[x_{1},x_{2},...,x_{D}]\\Subjected\,to\,G_{j}(x)\leq0,\,j=1,...,m\\where\,G_{1,...,q}=g_{1,...,q}(x),G_{q+1,...,m}=|h_{q+1,...,m}(x)-\epsilon| Minimizef(x),x=[x1,x2,...,xD]SubjectedtoGj(x)0,j=1,...,mwhereG1,...,q=g1,...,q(x),Gq+1,...,m=hq+1,...,m(x)ϵ

    • Strategies in EA

      Evolutionary algorithms (EAs) always perform unconstrained search. When solving constrained optimization problems, they require additional mechanisms to handle constraints.

      The algorithm may yields infeasible offspring.

      Rejecting Strategy

      All infeasible solutions are discarded. Likely to be highly inefficient if a large number of
      offpsirng are discarded. Also, if the feasible region is fragmented, then the
      method may not yield good results.

      Repairing Strategy

      Infeasible offsprings are corrected to make them satisfy all the constraints. Complex to implement.

      Modifying Genetic Operators

      Develop genetic operators to give only valid offsprings satisfying all constraints. Complex to implement.

      Penalty Function Approach

      q ( r , x ) = f ( x ) + P ( r , x ) q(r,x)=f(x)+P(r,x) q(r,x)=f(x)+P(r,x), P ( r , x ) P(r,x) P(r,x) here is the penalty function. It can be designed as:

      P ( r , x ) = Σ j = 1 m r j [ m a x { 0 , g j ( x ) } ] 2 P(r,x)=\Sigma_{j=1}^{m}r_{j}[max\left\{0,g_{j}(x)\right\}]^{2} P(r,x)=Σj=1mrj[max{0,gj(x)}]2

      r j r_{j} rj is to be chosen, which can reflect the importance of the constraints. Usually set it to small values initially then gradually increase them. This way allow GA to search in both feasible and infeasible regions but give valid solution in the end.

      Sometime the equation may be transformed as:

      Q ( r , x ) = C − f ( x ) − P ( r , x ) Q(r,x) = C-f(x)-P(r,x) Q(r,x)=Cf(x)P(r,x)

      So that the value of the function keep positive. Here C is a value to be set.

      Epsilon Constraint Method

      在这里插入图片描述

    • Variable reduction strategy (VRS)

      For example at first:

      m i n   x 1 2 + x 2 2 S u b j e c t e d   t o   x 1 + x 2 = 2 0 ≤ x 1 ≤ 5 ,    0 ≤ x 2 ≤ 5 min\,x_{1}^{2}+x_{2}^{2}\\Subjected\,to\,x_{1}+x_{2}=2\\0\leq x_{1}\leq5,\,\,0\leq x_{2}\leq 5 minx12+x22Subjectedtox1+x2=20x15,0x25

      We can obtain the relationship between two decision variables: x 2 = 2 − x 1 x_{2}=2-x_{1} x2=2x1, then:

      m i n   2 x 1 2 − 4 x 1 + 4 S u b j e c t e d   t o    0 ≤ x 1 ≤ 2 min\,2x_{1}^{2}-4x_{1}+4\\ Subjected\,to\,\, 0\leq x_{1} \leq 2 min2x124x1+4Subjectedto0x12

      Some corresponding very advanced looking formulas:

      Minimize f ( x ) , x = [ x 1 , x 2 , . . . , x D ] f(x),x=[x_{1},x_{2},...,x_{D}] f(x),x=[x1,x2,...,xD]

      Subjected to g i ( x ) ≤ 0 , i = 1 , . . . , q g_{i}(x)\leq0, i=1,...,q gi(x)0,i=1,...,q

      and h j ( x ) = 0 , j = q + 1 , . . . , m h_{j}(x)=0, j=q+1,...,m hj(x)=0,j=q+1,...,m

      Handle it with ∣ h j ( x ) ∣ − ϵ ≤ 0 |h_{j}(x)|-\epsilon\leq0 hj(x)ϵ0

      Assume Ω j \Omega_{j} Ωj denotes the collection of variables involved in h j ( X ) = 0 h_{j}(X)=0 hj(X)=0

      For h j ( X ) = 0 h_{j}(X)=0 hj(X)=0, if we can obtian a relationship:

      x k = R k , j ( { x l ∣ l ∈ Ω j , l ≠ k } ) x_{k}=R_{k,j}(\{x_{l}|l\in\Omega_{j},l\neq k\}) xk=Rk,j({xllΩj,l=k})

      Then we can eliminate x k x_{k} xk.

      In summary, a constraint problem can be described as:

      M i n i m i z e : f ( X ) S u b j e c t e d   t o : g i ( X ) ≤ 0 ,   i = 1 , . . . , p h j ( X ) = 0 ,   j = 1 , . . . , m l k ≤ x k ≤ u k ,   k = 1 , . . . , m Minimize:f(X)\\Subjected\,to:g_{i}(X)\leq0,\,i=1,...,p\\h_{j}(X)=0,\,j=1,...,m\\l_{k}\leq x_{k}\leq u_{k},\,k=1,...,m Minimize:f(X)Subjectedto:gi(X)0,i=1,...,phj(X)=0,j=1,...,mlkxkuk,k=1,...,m

      And VRS can be implemented as:

      M i n i m i z e : f ( X ) S u b j e c t e d   t o : g i ( X ) ≤ 0 ,   i = 1 , . . . , p h j ( X k ∣ k ∈ C ) = 0 ,   j ∈ M 2 l k ≤ R k , j ( { x l ∣ l ∈ Ω j , l ≠ k } ) ≤ u k ,   k ∈ C 1 , j ∈ M 1 l k ≤ x k ≤ u k ,   k ∈ C 2 Minimize:f(X)\\Subjected\,to:g_{i}(X)\leq 0,\,i=1,...,p\\h_{j}(X_{k}|k\in C)=0,\,j\in M_{2}\\l_{k}\leq R_{k,j}(\{x_{l}|l\in\Omega_{j},l\neq k\})\leq u_{k},\,k\in C_{1},j\in M_{1}\\l_{k}\leq x_{k}\leq u_{k},\,k\in C_{2} Minimize:f(X)Subjectedto:gi(X)0,i=1,...,phj(XkkC)=0,jM2lkRk,j({xllΩj,l=k})uk,kC1,jM1lkxkuk,kC2

      Empirically, we can reduce in following situations:

      • One variable less than or equal to second-order
      • All linear equality constraints and variables
      • Variables separately operated by one operator (e.g. x n , c o s x , l n x , a x x^{n},cosx,lnx,a^{x} xn,cosx,lnx,ax)
    展开全文
  • Shade学习方法总结

    千次阅读 2017-09-19 17:17:34
    再有很重要的一块就是图形算法,想要在通过Shader做出各种惊艳或者特殊的渲染效果,可不是只学会写Shader语法就可以做到的,就像大学里学程序设计后还要学习算法是一样的,图形渲染中也有大量的算法,从最基础的光照算法...
    
    最近网友 candycat1992的新书 《Unity Shader入门精要》出版了,估计万千的中国unity开发者又要掀起一波学Shader热潮了。我也想把自己这几年学习Shader的一些历程和心得记录下来。一来当给自己的学习做个记录,二来是给更多的后来人留些参考。

      写之前先声明几点:

      1. 本文标题中的Shader并不特指Unity Shader,本文也不涉及任何代码细节,仅是讨论学习方法。

      2. 图形技术的水很深,我还只是个小学生,只是单纯的分享自己的学习历程,大神看到了别见怪。

      3. 每个人的性格,思想都不一样,所以学习方法这种东西向来不是照搬照抄的,所以我说的不一定适合你,还需要自己取舍。

    个人历程

      容我讲讲自己学习Shader的经历,你会发现,入门并没有那么难,只要你肯下功夫。

      毕业后的第一份工作就是从事Unity客户端开发,当然了作为新人也就是写写UI,作作逻辑。恰巧当时项目的一个同事W君有Shader的经验,就每周都挑两天下班后的时间给我们上课,从最开始的矩阵变换到他离职前最后一课辉光效果。因为大学里的图形学课基本上也没怎么太认真(现在很后悔呀)。也就是这大概十几节课,让我对图形渲染有了最初的认识。就从这段时间开始,我断断续续的开始了学习Shader的路。那时候国内还没有一本专门讲UnityShader的书。而我对图形渲染的认识也是很肤浅的,只能去网上找资料,看代码例子,问同事,恰巧我有一个同事Y君,是学图形的研究生毕业,所以很多事情都可以向他请教,所以他也算是我在这方面的老师了。也是他推荐我看的《GPU编程与CG语言之阳春白雪下里巴人》,以及《Cg教程_可编程实时图形权威指南》(后来第二本书我还想尽了办法弄到一本正版实体书收藏了)。就是这两本书,还有网上那些我已经忘却名字的很多前辈的分享,我开始一点一点的去了解Shader,了解图形渲染,渐渐的也就成了我的一个兴趣点。

      到了第二年,工作上得心应手一些,我就花更多的业余时间在Shader上,一个问题想不明白就不停的想,直到能说服自己为止,也差不多就是那段时间郭浩瑜的那本《Unity 3D ShaderLab开发实战详解》出版了,要知道当初我和Y君可是每天都在关注出版进度,托了大半年终于出了,赶紧买来看。这本书现在看来别的不说,至少布局结构是极其不合理的,相当不适合新人,该详不详,该略不略。很多地方代码一扔,也不解释。不过,话说回来,因为我这人学东西如果一个地方看不懂就得想办法搞懂,所以这本书也让我知道了很多。这时候我也开始在Blog上写了第一篇Shader教程(2014年2月份,其实那时候自己也刚刚入门)。就这样边写边学,渐渐到隐藏在unityShader背后的图形渲染世界,不断的读书,写作,练习,我几乎是没有在项目里实际写Shader的,因为一般由Y君负责,但基本上所有的Shader我都会看,然后不理解的就要和Y君讨论弄明白。这样发现那段时间自己成长很快,尤其是写Blog,因为你要写给别人看,要讲的通俗易懂,还要剖析原理,写的每一句话都要负责,所以一定要搞懂。这期间还读了刘鹏翻译韩国人写的《计算机图形学-基于3D图形开发技术》,这本书其实很早就读过,那时候实在是水平不够,看不懂还怨人家翻译差,后来再看了解了不少东西。

      大概一年前,很巧合有一个机会来到了现在的公司进行了游戏引擎的开发。换工作之前也是想了很多,自己的图形渲染知识都是工作后自学的,之前两年的工作基本都是做Unity的逻辑开发工作,而且写引擎要用C++。当时还有很多机会,继续做Unity的开发工作,但还是横下心来做引擎,因为这是我这几年一直的想法,不论怎么样,有这机会就抓住,即使发现自己不适合,也会是一段很好的锻炼经历。笔试面试最后也过了。也算是对自己之前两年默默努力的一个回馈吧。

      做引擎开发者一年以来,得以有机会近距离看到游戏引擎的原理,对OGL也有了更好的了解。也知道了所有的游戏引擎核心原理没什么大的不同。但这一年来,由于没有再接触Unity,所以blog里的Shader教程长期没有更新。最近又打算重新开写了。因为渲染这东西重要的是原理和引擎是无关的。有时间我会继续更新。

      好吧,啰嗦了这么长(谁爱听啊!)。下面进入正题:


    正确的理解Shader

      很多人对Shader的理解都不同,特别是初学者,往往对Shader的认知是很肤浅的。大都认为Shader就是UnityShader,就是Unity引擎里一个用来创造画面效果的一种文件格式。

      这也是我当初刚接触Shader的时候的认知。这当然是一叶障目,不见泰山了。如果要学好Shader,用好Shader,就不能只停留在了解和使用UnityShaderLab的语法的层次。这是远远不够的,因为当你深入学习的时候你就会发现,由于你不理解Unity为你提供的某一个ShaderLab参数的具体原理,导致你也不能正常使用,即使是可以使用也不能举一反三。

      当然作为一个初学者,认知上的缺陷是难免的,但希望你在看到了这篇文章后,能看的更深远一些。Shader不只是指Unity的ShaderLab,也并不代表图形渲染的全部,它只是渲染流程上的一环,或者说是关键的一环。是很多很多步骤的结合作用才最终把画面正确的呈现出来。如果你真的想吃透Shader,用好Shader,这些东西都是你要去掌握理解的。那些渲染管线流程图什么的我就不拿过来粘贴了,本文只做学习方法总结,不讨论具体技术。

      综上,饭要一口一口吃,知识也肯定是一点一点学,循序渐进持之以恒,但如果一开始就能比较全面和整体的理解Shader的定位,那么也会在学习过程中,也就不会太自以为是,学的太肤浅。


    如何起步

      其实现在比几年前好多了,有了不少资源,很多热心网友写的教程,也有几本还能看的书。

      我还是谈谈我的建议,首先找个游戏引擎(当然你也可以不用引擎直接自己写OGL或DX),一本合适的书。unity当然是现在最容易上手的了,书的话用来入门了解的有几本是我觉得可以看的,但适不适合要看你自己了:

      1. 《GPU编程与CG语言之阳春白雪下里巴人》,严格说这不是一本书,是网上盛传的新人学习的必读物。

      2. 《Cg Programming in Unity》,这是Wiki上的一系列UnityShader教程,不过现在可能需要FQ看了。

      3. 《Cg教程_可编程实时图形权威指南》,因为Unity的Shader大部分还是用CG语言来写的,这本书虽然年代有点早,但还是值得一看的,而且Nvidia的网站上有最最新的英文版。

      4. 《Unity Shader入门精要》candycat1992,小姑娘这本书绝对的值得一看的,虽然是面向入门级的,但是里面涉及了很多底层的,原理的性的内容。国内Unity书总算有本值得买的了。

      别问我为啥不推荐那本《Unity 3D ShaderLab开发实战详解》,前面已经说了。

      有了书,打开引擎开始学,你需要的就是耐心和恒心了,我想学其他的知识也是一样吧。Shader的水很深,做好打持久战的准备,不断的练习,不断的尝试,不断的总结。

      在学习过程中遇到问题是必然的,合理的使用搜索引擎,去论坛和站点和大家交流。保持一颗谦卑的心,别人总有比你强的地方,虚心的学习,慢慢的积累。如果你身边有一个可以请教的人,那就太好。就像我遇到Y君一样。

      当你觉得自己入了一点门以后,就可以尝试着分析项目里的Shader代码了,结合着游戏中的实际效果,看看代码里用到了哪些你不知道的技术,或者说有什么你觉得不合理的地方。如果有机会,就尝试着申请在项目里实际写Shader的工作。这样的锻炼是难得的。可惜我当初做Unity时候没有这样的机会。

      起步的一开始一定会是有些无从下手的感觉,度过这段时间,找到适合自己的节奏,就会有个很快速的学习积累过程。要坚持。


    如何提高

      刚接触Shader时候会有个迷茫期,其实当你学了一段时间,感觉自己学到了很多东西以后,也会有个迷茫期,不知道怎么进一步的提高自己,感觉自己该掌握的都已经掌握了,但是又写不出什么东西。

      正如我在前面说的,我们总觉得自己好像该学的都学了,又感觉哪里好像没吃透。这说明我们还是没有触碰到我们学习内容的全貌,才只看到整个知识体系的冰山一角。所以一定会经历这个从觉得自己什么都会了,到感觉自己什么都不会了的转变。这个转变是必要的,它意味着你将了解到更深更广的知识。

      废话不说了,一般我们入了门以后还要去理解更多的知识,我总结一下,大概有几方面:

      1. 首先要对渲染管线有个透彻的了解,至少要知道每一步发生了什么。很多学Unity从业者说会Shader也就只停留在前面那个语法层次了。如果连渲染管线都不知道,就不要再往简历写会Shader了。这方面的资料很多,candyCat1992那本书以及《计算机图形学-基于3D图形开发技术》都有,还有Trace大神搬运过来的一套教程。了解渲染管线,能让你对Shader里的很多用法都能有更深入的认识。

      2. 去学习OpenGL或者DirectX的知识(如果你经历足够可以双管齐下),看好,不是说HLSL或者GLSL这些Shader语法,而是OGL和DX。了解了渲染管线之后,再去了解一下图形API,试着动手写写,你才能真正的理解渲染管线的实际流程,以及那些被游戏引擎所隐藏起来的渲染逻辑。你也就能了解到Unity中的FBX模型里到底都放了什么数据,场景模型上的MeshFilter组件和MeshRenderer组件都是起什么作用的,等等。对这些图形API有了一定的掌握,不仅可以对渲染流程有更深入的了解,甚至可以自己开发一个简单的渲染引擎了。这方面的学习资料就太多了,学OGL就是红宝书,DX的话自然就是龙书

      3. 再有很重要的一块就是图形算法,想要在通过Shader做出各种惊艳或者特殊的渲染效果,可不是只学会写Shader语法就可以做到的,就像大学里学程序设计后还要学习算法是一样的,图形渲染中也有大量的算法,从最基础的光照算法,到HDR,FXAA,Toon。再到最近次时代流行的PBR等等。有很多已经很成熟的算法,但这些算法不一定完全适合你的项目或者平台,所以必须了解他们改进它们,甚至研究出新的算法。这个过程估计是最痛苦的了,因为国内的资料不多,讨论的人也不多,算法中往往还涉及到大量的数学和物理知识。如果能持续不断的坚持学习和实践,那你也许就会是万千游戏开发大军中的的佼佼者。这方面的书虽然不多,基础类的我就不说了,很多书上都有,有一些大部头的经典如:《GPU Gems》系列,《Real-Time Rendering》,《Physically Based Rendering》。国内能读完这些书的人应该是是很少的。我自己还不到这个层次,不过也准备要开始塌下心来学习。还有一个论坛OpenGPU,也推荐给大家,不过这个不是入门向的,里面的大神太多了,不要在里面提太没营养的问题,会被鄙视的。

      4. 补补数学再学点物理知识吧。线性代数的重要性就不用我说了,如果能力和精力允许的话,就多补一补,我这数学渣就不多说话了,不过我也有时间会学一学的。这方面也有一些好的资料。我手头就有一本《Mathematics for 3D Game Programming and Computer Graphics》。这个我就不多说了,没事多学学,省着用到了挠头。

      ...

      其实还有很多,比如把C++好好学一学,不过已经不要紧了,路很长,要怎么走还是要靠你自己。我也只是个一定意义上的入门者,不想误导别人。大家一起提高,互相帮助吧。


    最后几句心里话

      其实无论别人看别人多少文章,多少教程,多少书,学习的路上往往都是没有捷径的,总要经历些坎坷和挫折。否则牛人怎么才是牛人呢,自己这几年的学习历程也是经历了很多,写这篇文章并不是能给大家提供什么捷径和速成法,只是给大家些勇气,希望大家少一些磕磕绊绊。像我这样的都能入个门,大家也一定可以的。

      也希望大家,能乐于分享,让大环境更成熟起来,也希望能涌现更多的牛人。

      尊重他人智慧成果,欢迎转载,请注明作者esfog,原文地址http://www.cnblogs.com/Esfog/p/5537624.html

    展开全文
  • shade函数

    2021-03-26 11:08:35
    这些函数用于执行数学上的通用计算或通用算法(纹理映射等),例如,需要求取入射光线的反射光线方向向量可以使用标准函数库中的 reflect 函数,求取折射光线方向向量可以使用 refract 函数,做矩阵乘法运算时可以...
  • 在深度学习中,有很多种优化算法,这些算法需要在极高维度(通常参数有数百万个以上)也即数百万维的空间进行梯度下降,从最开始的初始点开始,寻找最优化的参数,通常这一过程可能会遇到多种的情况,诸如: 1、...
  • 完整代码,可直接运行
  • 除了学习,总结也很重要,不总结的学习就像缺了光照的树苗,很难茁壮成长,而且学了这段时间总...***1.DE算法:***差分进化算法,分别进行变异,交叉和选择进行优化。 ***2.PSO算法:***粒子群优化。通过速度和位置使...
  • WOA优化算法 相关代码

    2018-03-30 12:37:11
    这里我们上传的WOA算法 是2016年提出的 主要是用来优化各种算法中的参数,在实际问题中也有很大用处,其主要是通过优化参数的方法实现算法的最优解,在实际应用中有比较不错的效果,这里上传相关代码方便大家的运用...
  • 使用 AOA 获得的解决方案优于众所周知的最新技术和最近引入的元启发式算法,例如遗传算法 (GA)、粒子群优化 (PSO)、差分进化变体 L-SHADE 和 LSHADE-EpSin、鲸鱼优化算法(WOA)、正余弦算法 (SCA)、Harris 鹰优化 ...
  • SHADE通过迭代局部搜索进行大规模全局优化。2018年度会议,IEEE进化计算大会,里约热内卢,巴西,2018年7月8日至13日, pp 1252-1259“ 它在WCCI 2018中特别是在IEEE进化计算大会上进行了介绍。 。 安装 建议使用 ...
  • 3)CMA-ES,SHADE和LSHADE-cnEpSin高性能优化器和IEEE CEC竞赛的获胜者。 在所有方法中,与LSHADE-cnEpSin相比,MPA获得了第二名,并表现出极具竞争力的结果,LSHADE-cnEpSin是表现最好的方法,并且是CEC 2017竞赛...
  • MPA的主要灵感是广泛的觅食策略,即海洋捕食者中的Lévy和Brownian运动,以及捕食者与...将MPA与三类现有的优化方法进行了比较,包括(1)GA和PSO是研究最深入的元启发式算法;(2)GSA,CS和SSA是最近开发的算法
  • 近年来,已发布了一组最新的基于人口的过度使用的方法。 尽管它们很受欢迎,但是由于操纵了系统的互联网营销,产品捆绑和广告技术,它们中的大多数具有不确定的,不成熟的性能,部分完成的验证,相似的过度使用的...
  • 创作排行有感

    2021-03-12 14:17:54
    (什么是MySQL、Linux、算法?又该怎么用?) 5、首批千万5G用户被当作小白鼠,运营商已无情抛弃,5G手机销量或下跌 6、为什么老板宁愿高薪招新员工,也不愿意给老员工加薪 7、苹果进入“复古时代”? 8、有些段子,...
  • 相关文章:Edge-Based Color Constancy 中提出闵可夫斯基模型,统一了两大经典白平衡算法,并衍生出gray edge算法,同时 Shades of Grey也符合该模型
  • 如果你看看基本原色轮你会注意到有三个不同的乐队围绕着中心。实际上应该有第四个音调,如下所示。 大多数彩色车轮只显示明亮的颜色,这会造成混乱。并不总是很容易看到每一种颜色,即使是黑色,都有一个原色作为它...
  • 差分进化算法的变体之一——JADE算法

    千次阅读 多人点赞 2018-09-30 23:41:24
    对于DE算法而言,随着迭代次数的增加,个体间的差异会逐渐降低,收敛速度也会随之下降,这会使得DE算法容易陷入局部最优和早熟收敛。所以很多研究者在原始经典的DE算法上寻求各种改进来提高DE算法的寻优能力、收敛...
  • {Zoclee}:trade_mark:阴影 是用于测试和调试SPIR-V二进制文件的虚拟机。 关于 ... Windows: : OS X(Intel): : //www.zoclee.com/shade/setup/osx Linux(32位): http : //www.zoclee.com/sh
  • 开坑记录一下白平衡相关算法,从两个最基本的白平衡算法开始。 白平衡算法之Gray World和White Patch   颜色作为物体最基本的属性,在大部分场合对人类视觉而言是一个能够轻而易举捕获的信息。但在数字成像过程中...
  • The SHADE cipher_an efficient hash-function-based
  • ISP算法高水平分析(下) 十.LSC(Lens Shade Correction)------镜头阴影矫正 Lens Shading指画面四角由于入射光线不足形成的暗角,同时,由于不同频率的光折射率差别,导致 color shading。因此需要镜头影音校正...
  • 达内java培训:本文就 目前现有面消隐算法进行 了分类,对每类算法特 点进行了总结。从每种 算法本 身的特点 、消隐空间、排序效率和对场景的限制这几方面 .重点分析比较 了几种常用的面消隐算法。1 引言消隐...
  • maven shade

    2020-12-11 10:27:14
    shade 包冲突
  • 官方离线安装包,亲测可用。使用rpm -ivh [rpm完整包名] 进行安装

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,815
精华内容 726
关键字:

shade算法

友情链接: ud215.zip