亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        高效秩-μ更新自動協(xié)方差矩陣自適應(yīng)演化策略

        2019-04-01 13:10:46楊勝飛
        計算機應(yīng)用與軟件 2019年2期
        關(guān)鍵詞:測試函數(shù)變體協(xié)方差

        楊勝飛 茍 剛

        (貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院 貴州 貴陽 550025)

        0 引 言

        協(xié)方差矩陣自適應(yīng)演化策略(CMA-ES)是應(yīng)用最多、性能最好的演化策略(ES)[1]之一,由Hansen和Ostermeier[2-3]提出,主要應(yīng)用實值優(yōu)化問題,使函數(shù)值達到最小值且搜索成本最低。CMA-ES易陷入局部最優(yōu),喬帥結(jié)合云推理改善陷入局部最優(yōu)[4],胡冠宇引入混沌算子使其具有良好全局搜索能力[5]。CMA-ES的一般思想是在目標(biāo)方向中使用成功搜索步驟的信息更改協(xié)方差矩陣的突變分布,不成功方向的信息隨時間而丟棄。CMA-ES發(fā)展不同的變體,如MA-ES[8]和使用不同的演化策略(μ+λ)[6]的精英CMA-ES[7],使用五分之一成功規(guī)則,可應(yīng)用于求解多目標(biāo)優(yōu)化問題。對于CMA-ES的不同變體,普遍存在更新協(xié)方差矩陣(秩-1和秩-μ)時間復(fù)雜度高的問題,計算協(xié)方差矩陣的秩-1和秩-μ時間為Θ((μ+1)n3)。Igel提出協(xié)方差矩陣cholesky秩-1更新并應(yīng)用于精英CMA-ES[9]和非精英CMA-ES[10],使用cholesky因子更新協(xié)方差矩陣,在計算時不直接計算協(xié)方差矩陣,而是對其cholesky因子進行計算,使計算協(xié)方差矩陣的秩-1更新時間減少為Θ(n2)。在進行協(xié)方差矩陣cholesky因子秩-1更新時,需考慮逆cholesky因子,Li等[11]提出一種高效的秩-1更新協(xié)方差矩陣(Li-CMA-ES),使用輔助演化路徑代替協(xié)方差矩陣cholesky因子秩-1更新的演化路徑,取消逆cholesky因子的計算。Krause等提出三角cholesky因子更新協(xié)方差矩陣,保證cholesky因子是三角矩陣,應(yīng)用于精英CMA-ES[12]和非精英CMA-ES[13]。由于CMA-ES在獲得突變信息時,只獲取成功的突變信息,而不成功的信息被動丟棄,在一定程度上使協(xié)方差矩陣的自適應(yīng)減慢。文獻[14]提出自動(active)協(xié)方差矩陣自適應(yīng)演化策略(active-CMA-ES),在協(xié)方差矩陣更新中同時使用成功和不成功的突變信息,使不成功方向的方差自動減少,加快策略集中于有用的方向。文獻[15]將active和cholesky的秩-1更新應(yīng)用于精英CMA-ES,驗證算法在某些問題上速度提升至2倍, Krimpmann等[16]將其應(yīng)用于多目標(biāo)優(yōu)化。

        目前,CMA-ES的cholesky因子更新只實現(xiàn)秩-1更新,對于秩-μ沒有實現(xiàn),自動CMA-ES增加不成功突變信息,使協(xié)方差矩陣更新的時間比CMA-ES增加了Θ((λ-μ)n3)。針對該問題,本文實現(xiàn)cholesky因子秩-μ更新,并結(jié)合Li提出的高效秩-1更新應(yīng)用active-CMA-ES形成chol-active-CMA-ES,并與標(biāo)準(zhǔn)CMA-ES、active-CMA-ES、Li-CMA-ES在一組基準(zhǔn)測試函數(shù)中驗證算法的性能和效率。

        1 背景知識

        1.1 active-CMA-ES

        在標(biāo)準(zhǔn)CMA-ES中,只有成功后代候選解的信息使用,而不成功的信息則被動丟棄,在一定程度上減慢協(xié)方差矩陣自適應(yīng)。Jastrebski提出active-CMA-ES,使用不成功突變的后代信息有助于加快演化策略的處理,active-CMA-ES由以下6個步驟組成:

        步驟1協(xié)方差矩C陣特征分解為正交矩陣B和對角矩陣D的乘積,C、B、D,均為n×n矩陣:

        C=BD(BD)T

        (1)

        步驟2在每代中后代個體(候選解)從多元正態(tài)分布N(m,C)中產(chǎn)生[17],m為搜索分布的移動均值,zi為突變向量服從正態(tài)分布N(0,I):

        xi=m+σBDzi

        (2)

        將目標(biāo)函數(shù)值f(xi)按照升序?qū)€體進行排序,個體下標(biāo)k∈[1,2,…,λ]表示第k個最好的個體。

        步驟3更新搜索分布的移動均值m為:

        m=m+σBD〈Z〉

        (3)

        步驟4Z為父代個體μ最好的平均突變向量:

        步驟5協(xié)方差矩陣和步長更新需要演化路徑Pc和共軛演化路徑Pσ:

        (5)

        (6)

        式中:cc、cσ為Pc和Pσ更新的學(xué)習(xí)率。

        步驟6自動更新協(xié)方差矩陣為:

        (7)

        步驟7更新突變強度為:

        (8)

        式中:dσ為阻尼參數(shù),χn標(biāo)準(zhǔn)正態(tài)分布的期望值。

        1.2 協(xié)方差矩陣cholesky因子秩-1更新

        在CMA-ES中,協(xié)方差矩陣秩-1和秩-μ更新時間復(fù)雜度分別為Θ(n3)和Θ(μn3),在每代中計算協(xié)方差矩陣的代價昂貴。Igel提出cholesky因子秩-1更新協(xié)方差矩陣,直接在每代中對協(xié)方差矩陣的cholesky因子進行計算,進行cholesky因子秩-1減少為Θ(n2)。Li-CMA-ES實現(xiàn)協(xié)方差矩陣高效cholesky因子秩-1更新,使用輔助演化路徑替換秩-1更新的演化路徑,具體步驟如下:

        步驟1每個對稱正定矩陣(協(xié)方差矩陣)都可分解為C=AAT,A為cholesky因子,zi~N(0,I),每代中候選解的產(chǎn)生重新定義:

        xi=m+σAzi∶N(m,σ2AAT)

        (9)

        步驟2演化路徑和共軛演化路徑更新為:

        (10)

        (11)

        步驟3分布移動均值更新為:

        (12)

        步驟4突變強度更新為:

        (13)

        步驟5協(xié)方差矩陣秩-1和秩-μ更新,δ=1-c1-cμ

        (14)

        步驟6輔助演化路徑υ應(yīng)用于協(xié)方差矩陣cholesky因子秩-1更新,υ代替A-1Pc,α=1-c1,β=c1:

        (15)

        (16)

        2 改進方法

        2.1 協(xié)方差矩陣cholesky因子秩-μ更新

        Suttorp將cholesky因子秩-1更新應(yīng)用CMA-ES,減少協(xié)方差矩陣秩-1更新時間,但對于協(xié)方差矩陣cholesky因子秩-μ更新沒有實現(xiàn),本文實現(xiàn)協(xié)方差矩陣cholesky因子秩-μ更新,相較于原始的協(xié)方差矩陣秩-μ更新,時間減少為Θ(μn2)。

        引理1設(shè)u∈Rn為任意向量,則矩陣I+uuT被因式分解為:

        I+uuT=(I+ζuuT)(I+ζuuT)

        (17)

        定理1設(shè)A∈Rn×n,z∈Rn,α,β∈R+,由υ=Az,當(dāng)z≠0時,協(xié)方差矩陣cholesky因子A為:

        (18)

        由式(17),協(xié)方差矩陣秩-μ更新重新表示為:

        (19)

        式中:υ=Azi:λ,zi~N(0,I),將式(19)迭代展開為:

        (20)

        由式(20)、引理1和定理1,協(xié)方差矩陣cholesky因子秩-μ更新在i=1,2,…,μ中依次迭代計算為:

        (21)

        式中:βi=βωi,α1=1-cμ,α2=α2=…=αμ=1。

        2.2 chol-active-CMA-ES

        表1 參數(shù)值

        算法1active-chol-CMA-ES

        初始化:m0,σ0,Pc,0=0,Pσ,0=0,A0=I

        1: repeat

        2: fori=1:λdo

        3:xi:λ=m+σyi:λ

        4: end for

        8:α=1-c1-cμ

        10: forj=1:μdo

        12: end for

        13: fork=(λ-μ+1):λdo

        15: end for

        18: until stopping criterion is met

        3 實驗結(jié)果與分析

        將提出的算法chol-active-CMA-ES與標(biāo)準(zhǔn)CMA-ES、Li-CMA-ES、active-CMA-ES在一組基準(zhǔn)測試函數(shù)(表2)上運行比較提出算法的性能,設(shè)置目標(biāo)函數(shù)值達到為最優(yōu)。每個算法在基準(zhǔn)測試函數(shù)中獨立運行100次,問題維度為[100,200,300]。在表3-表5中,F(xiàn)E表示目標(biāo)函數(shù)值,A1為標(biāo)準(zhǔn)CMA-ES算法,A2為Li-CMA-ES算法,A3為active-CMA-ES算法,A4為chol-active-CMA-ES算法。

        表2 測試函數(shù)

        圖1為各個算法在維度為100,迭代10 000次,運行目標(biāo)函數(shù)值達到時所需的最少迭代次數(shù)。chol-active-CMA-ES算法在(a)至(f)函數(shù)達到指定目標(biāo)函數(shù)值,在(c)至(f)函數(shù)中所需迭代數(shù)最少,都優(yōu)于其他CMA-ES變體。在(h)至(i)函數(shù)chol-active-CMA-ES算法與其他CMA-ES變體都未在迭代10 000次達到目標(biāo)函數(shù)值,算法在(h)和(i)中獲得較小值(見表3 粗體)。表4為圖1各個算法運行的步長大小,取平均值。

        圖1 各個算法運行目標(biāo)函數(shù)值達到10-10時所需最少迭代次數(shù)(迭代10 000次,問題維度為100)

        表3 算法運行結(jié)果(取平均值)

        表4 步長大小(取平均值)

        chol-active-CMA-ES算法與active-CMA-ES算法運行100 000次,維度為[100,200,300],比較達到目標(biāo)函數(shù)值時協(xié)方差矩陣更新的時間,見表5(更新比=原始更新/新更新),其中~為算法迭代結(jié)束后未達到指定目標(biāo)函數(shù)值,故不計算其更新時間。chol-active-CMA-ES算法中協(xié)方差矩陣更新時間比原始算法快(除了fSphere和fCigar),在fSphere中,在n=100時比原始更新快約4.1倍,n=200時比原始更新快約2.5倍,n=300時比原始更新快約8.7倍。

        表5 協(xié)方差矩陣更新時間比(取平均值)

        4 結(jié) 語

        本文實現(xiàn)cholesky因子秩-μ更新協(xié)方差矩陣,結(jié)合Li-CMA-ES形成chol-active-CMA-ES,在一組基準(zhǔn)測試函數(shù)中與其他CMA-ES變體比較性能及效率。實現(xiàn)結(jié)果表明所提出算法優(yōu)于其他CMA-ES變體,并隨著問題維度和迭代次數(shù)的增加,算法運行結(jié)果更好,更新協(xié)方差矩陣的時間比active-CMA-ES快。在未來的研究工作中,主要探索協(xié)方差矩陣秩-1和秩-μ更新更高效的方法,使算法在高維度下運行更快。

        猜你喜歡
        測試函數(shù)變體協(xié)方差
        基于DDPG算法的變體飛行器自主變形決策
        具有收縮因子的自適應(yīng)鴿群算法用于函數(shù)優(yōu)化問題
        非仿射參數(shù)依賴LPV模型的變體飛行器H∞控制
        帶勢函數(shù)的雙調(diào)和不等式組的整體解的不存在性
        不確定系統(tǒng)改進的魯棒協(xié)方差交叉融合穩(wěn)態(tài)Kalman預(yù)報器
        約束二進制二次規(guī)劃測試函數(shù)的一個構(gòu)造方法
        耀變體噴流高能電子譜的形成機制
        一種基于廣義協(xié)方差矩陣的欠定盲辨識方法
        面向真實世界的測試函數(shù)Ⅱ
        中國傳統(tǒng)文學(xué)的換形變體——論“詩化小說”的興起與傳承
        久久人妻中文字幕精品一区二区| 国产午夜福利精品| 久久99久久99精品观看| 少妇被啪出水在线视频| 成年免费a级毛片免费看无码| 97伦伦午夜电影理伦片| 欧美中文字幕在线看| 国产三级c片在线观看| 伊人情人色综合网站| 精品国产一区二区三区免费| 日韩高清无码中文字幕综合一二三区 | 狠狠色丁香婷婷久久综合| 乱人伦视频中文字幕| 在线天堂中文一区二区三区| 国产精品久久av高潮呻吟| 亚洲va韩国va欧美va| 人人妻人人澡人人爽曰本| 久久久久久久久久91精品日韩午夜福利| 亚洲综合在不卡在线国产另类| 亚洲乳大丰满中文字幕| 国产成人av一区二区三区无码| 亚洲一区二区高清在线| 日韩精品极品免费视频观看| 在线看片免费人成视频久网下载| 国产免费一级在线观看| 精品国产污黄网站在线观看| 精品香蕉99久久久久网站| 特黄a级毛片免费视频| 超碰观看| 日韩精品人妻系列中文字幕| 青草内射中出高潮| 欧美久久久久中文字幕| 国产伦精品一区二区三区| 中国美女a级毛片| 奇米影视久久777中文字幕| 亚洲国产欲色有一二欲色| 狠狠躁夜夜躁av网站中文字幕| 色偷偷久久一区二区三区| 亚洲成av人无码免费观看| 亚洲美女自拍偷拍视频| 婷婷五月六月综合缴情|