多精度優(yōu)化

Wang, Handing, Yaochu Jin, and John Doherty. "A Generic Test Suite for Evolutionary Multi-Fidelity Optimization."?IEEE Transactions on Evolutionary Computation?(2017). Doi:? 10.1109/TEVC.2017.2758360

很多實(shí)際優(yōu)化問(wèn)題的解的適應(yīng)度評(píng)價(jià)涉及很復(fù)雜的運(yùn)算，十分耗時(shí)胃夏。但評(píng)價(jià)的精度往往是可以控制的楷怒，精度越高买决，對(duì)解的評(píng)價(jià)就越準(zhǔn)確，但計(jì)算代價(jià)就越高彤守。反之诽凌，則評(píng)價(jià)誤差越大，但計(jì)算代價(jià)低跷坝。因此就衍生出了多精度優(yōu)化酵镜。

根據(jù)這篇文章的敘述碉碉，目前針對(duì)多精度進(jìn)化優(yōu)化的研究還不是很多，為了促進(jìn)這方面的研究淮韭，作者在文章中設(shè)計(jì)了三組多精度測(cè)試集垢粮，用來(lái)模擬實(shí)際的多精度優(yōu)化問(wèn)題。同時(shí)作者提供了基于PSO算法的實(shí)驗(yàn)結(jié)果靠粪。

文章要點(diǎn)：

1. 設(shè)計(jì)原則

在設(shè)計(jì)測(cè)試集時(shí)蜡吧，主要的原則是在真實(shí)的評(píng)價(jià)函數(shù) $f(x)$ 基礎(chǔ)上增加誤差 $e(x,\phi)$ ，得到的測(cè)試函數(shù)輸出為 $\tilde{f}(x,\phi )$ 占键。所以設(shè)計(jì)不同的測(cè)試集就轉(zhuǎn)變?yōu)樵O(shè)計(jì)不同的誤差函數(shù)了昔善。

$\tilde{f}(x,\phi ) =f(x)+e(x,\phi)$

2. 誤差及誤差函數(shù)設(shè)計(jì)

在對(duì)實(shí)際問(wèn)題的解進(jìn)行模擬（評(píng)價(jià)）時(shí)可能會(huì)有各種各樣的誤差，作者總結(jié)除了一下三種誤差畔乙，同時(shí)所提出的測(cè)試集的差別在于包含這三種不同的誤差君仆。

Resolution errors（精度誤差）可以理解為對(duì)真實(shí)的適應(yīng)度曲線模擬得有一定誤差，不同精度下的模擬適應(yīng)度曲線中的全局最優(yōu)和局部最優(yōu)可能和真實(shí)的最優(yōu)解有一定距離牲距。像下圖那樣返咱。

精度為1000時(shí)的適應(yīng)度曲線和真實(shí)的（精度為10000）時(shí)還是有不小的差距的。

Stochastic（隨機(jī)誤差）可以理解為在每次評(píng)價(jià)中加入隨機(jī)擾動(dòng)牍鞠，在文章中咖摹，作者加入了高斯噪聲。

Instability （不穩(wěn)定誤差）可以理解為以一定概率讓解的評(píng)價(jià)失敗难述，作者通過(guò)以一定概率讓誤差函數(shù)的值無(wú)限大（相對(duì)于真實(shí)的適應(yīng)度值來(lái)說(shuō)無(wú)限大萤晴，其實(shí)不是無(wú)限大，作者使用了 $l=10d$ 胁后，其中d是變量的維度）硫眯。

作者針對(duì)上面的三種誤差總共設(shè)計(jì)了13個(gè)測(cè)試函數(shù)，作者在解空間采樣了10000解择同，分別計(jì)算了在不同精度下的目標(biāo)函數(shù)值两入，并且計(jì)算了與真實(shí)目標(biāo)函數(shù)值之間的皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient)和RMSE來(lái)解釋不同精度下的評(píng)價(jià)函數(shù)和真實(shí)精度的評(píng)價(jià)函數(shù)值之間的相關(guān)性。

3. 優(yōu)化方法

測(cè)試集設(shè)計(jì)好了敲才，應(yīng)該怎么去求解這類多精度的問(wèn)題呢裹纳。其實(shí)質(zhì)是不同精度的目標(biāo)函數(shù)該怎么使用的問(wèn)題择葡。使用最高精度的評(píng)價(jià)函數(shù)很耗時(shí)，使用最低精度的評(píng)價(jià)函數(shù)雖然會(huì)很快剃氧，但是求解精度很差敏储，所以作者設(shè)計(jì)了三種精度調(diào)節(jié)策略，算法框架使用了PSO朋鞍。

1）基于代數(shù)的調(diào)整策略

該策略需要對(duì)每一代種群評(píng)價(jià)其收斂性 $M_{c}$ 和多樣性 $M_v2hdh0u$ 已添，然后用這兩個(gè)值 $s=(M_{c} ,M_j2bc0b0 )$ 作為比較支配關(guān)系的指標(biāo)去和之前所有代中積累下來(lái)的非支配解集 $S$ 作比較。若 $s$ 支配 $S$ 中的某些值滥酥，則去掉 $S$ 中被 $s$ 支配的值更舞，且將代價(jià)累加變量 $C_{deg}$ 置0。否則將該代的計(jì)算代價(jià)累加到 $C_{deg}$ 中坎吻，且將 $s$ 加入 $S$ 缆蝉。當(dāng) $C_{deg}$ 的值達(dá)到設(shè)定的閾值時(shí)，將精度等級(jí)調(diào)高一級(jí)瘦真。直到達(dá)到最高等級(jí)刊头。

2）基于個(gè)體的調(diào)整策略

該策略的主要思想為：將兩個(gè)解 $x_{1}$ 和 $x_{2}$ 的目標(biāo)函數(shù)的差 $\Delta =|\tilde{f} (x_{1},\phi )-\tilde{f} (x_{2},\phi )|$ 轉(zhuǎn)換為將這兩個(gè)解錯(cuò)誤排序的概率。作者在文章中使用了logistic回歸模型（即logisti函數(shù)）來(lái)計(jì)算此概率诸尽。計(jì)算方式如下

$LR^\phi(\Delta ) =\frac{1}{1-e^-(\beta _{0}+\beta _{1}\Delta ) }$

優(yōu)化過(guò)程為：首先原杂，在每一代的優(yōu)化中都使用最低級(jí)別的精度去評(píng)價(jià)個(gè)體；之后您机，在更新個(gè)體最優(yōu)(personal best)和全局最優(yōu)（global best）時(shí)估計(jì)兩個(gè)解的 $LR^\phi(\Delta )$ 值穿肄，若超過(guò)設(shè)定的閾值（0.05），則使用更高的精度 $\phi$ 重新計(jì)算 $LR^\phi(\Delta )$ 值往产，若仍大于閾值被碗，則直接使用最高級(jí)別的精度來(lái)更新個(gè)體最優(yōu)和全局最優(yōu)。

3）混合調(diào)整策略

將1）和2）混合仿村。

4. 實(shí)驗(yàn)

參數(shù)設(shè)置：種群大小為50锐朴，獨(dú)立實(shí)驗(yàn) 30次，算法停止準(zhǔn)則為運(yùn)算代價(jià)達(dá)到5e-09（這么低嗎蔼囊？）焚志。13個(gè)測(cè)試集中有的函數(shù)的精度等級(jí)是[0,10000]，有的是[0,10000]之間的若干值畏鼓。通過(guò)實(shí)驗(yàn)酱酬，作者將精度等級(jí)取值范圍為[0, 10000]的函數(shù)的精度等級(jí)劃分為11個(gè)等級(jí)。最終的實(shí)驗(yàn)結(jié)果如下云矫。

其中PSO表示用最高等級(jí)精度的目標(biāo)函數(shù)來(lái)優(yōu)化膳沽，PSO-AFAg，PSO-AFAi，及PSO-AFAh分別表示基于代挑社、個(gè)體和混合調(diào)整策略陨界，GOEME為一個(gè)代理模型算法。

從實(shí)驗(yàn)結(jié)果可以看出PSO-AFAh的性能最好痛阻，PSO-AFAg次之菌瘪。奇怪的是使用最高精度評(píng)價(jià)函數(shù)的PSO結(jié)果居然比不過(guò)前三種算法，考慮到停止準(zhǔn)則是計(jì)算代價(jià)達(dá)到一定閾值阱当，也就可以理解了俏扩。用最高精度的評(píng)價(jià)函數(shù)的計(jì)算代價(jià)肯定很高，所以在相同的計(jì)算代價(jià)條件下弊添，使用動(dòng)態(tài)調(diào)整評(píng)價(jià)函數(shù)精度的策略能使得算法收斂得更快录淡。同時(shí)，低精度的評(píng)價(jià)函數(shù)雖然和真實(shí)的（或者高精度的）評(píng)價(jià)函數(shù)之間有誤差表箭，但是也能幫助算法向最優(yōu)解收斂赁咙。

5. 總結(jié)

作者最后指出了幾條將來(lái)的研究方向：1. 文章中所提出的測(cè)試集能在多大程度上模擬真實(shí)的情況钮莲；2. 文中所提出的調(diào)整策略沒(méi)有考慮代理模型免钻；3. 不同精度的目標(biāo)函數(shù)之間的關(guān)系需要深入研究，以提出更有效的調(diào)整策略崔拥；4. 目前還沒(méi)有合適的評(píng)價(jià)方法來(lái)對(duì)比不同的多精度優(yōu)化算法极舔；5. 多精度測(cè)試集以及多精度優(yōu)化算法的研究還需深入。

6. 感受

讀好文章可以一口氣讀到參考文獻(xiàn)链瓦，沒(méi)有晦澀難懂的表述拆魏，也沒(méi)有復(fù)雜的公式。讀得過(guò)程中心中產(chǎn)生的每一個(gè)疑問(wèn)都能在文章中得到解答慈俯，仿佛作者知道讀者會(huì)產(chǎn)生哪些疑問(wèn)渤刃，繼而很恰到好處地幫讀者解開心中的疑惑。驚嘆作者思路之縝密贴膘，設(shè)計(jì)之精妙卖子，表述之簡(jiǎn)潔。是為榜樣刑峡！

最后編輯于：2018.11.26 23:53:40

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末洋闽，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子突梦，更是在濱河造成了極大的恐慌诫舅，老刑警劉巖，帶你破解...
沈念sama閱讀 210,914評(píng)論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件宫患，死亡現(xiàn)場(chǎng)離奇詭異刊懈，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 89,935評(píng)論 2贊 383
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門虚汛，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)当宴，“玉大人，你說(shuō)我怎么就攤上這事泽疆』福” “怎么了？”我有些...
開封第一講書人閱讀 156,531評(píng)論 0贊 345
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵殉疼，是天一觀的道長(zhǎng)梯浪。經(jīng)常有香客問(wèn)我，道長(zhǎng)瓢娜，這世上最難降的妖魔是什么挂洛？我笑而不...
開封第一講書人閱讀 56,309評(píng)論 1贊 282
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮眠砾，結(jié)果婚禮上虏劲，老公的妹妹穿的比我還像新娘。我一直安慰自己褒颈，他們只是感情好柒巫，可當(dāng)我...
茶點(diǎn)故事閱讀 65,381評(píng)論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布。她就那樣靜靜地躺著谷丸，像睡著了一般堡掏。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上刨疼，一...
開封第一講書人閱讀 49,730評(píng)論 1贊 289
城市分裂傳說(shuō)
那天泉唁，我揣著相機(jī)與錄音，去河邊找鬼揩慕。笑死亭畜，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的迎卤。我是一名探鬼主播拴鸵，決...
沈念sama閱讀 38,882評(píng)論 3贊 404
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼止吐！你這毒婦竟也來(lái)了宝踪？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 37,643評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤碍扔，失蹤者是張志新（化名）和其女友劉穎瘩燥，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體不同，經(jīng)...
沈念sama閱讀 44,095評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡厉膀，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,448評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年溶耘，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片服鹅。...
茶點(diǎn)故事閱讀 38,566評(píng)論 1贊 339
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡凳兵，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出企软，到底是詐尸還是另有隱情庐扫，我是刑警寧澤，帶...
沈念sama閱讀 34,253評(píng)論 4贊 328
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布仗哨，位于F島的核電站形庭，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏厌漂。R本人自食惡果不足惜萨醒，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,829評(píng)論 3贊 312
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望苇倡。院中可真熱鬧富纸，春花似錦、人聲如沸旨椒。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,715評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)钩乍。三九已至辞州，卻和暖如春怔锌，著一層夾襖步出監(jiān)牢的瞬間寥粹，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,945評(píng)論 1贊 264
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工埃元，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留涝涤，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,248評(píng)論 2贊 360
代替公主和親
正文我出身青樓岛杀，卻偏偏與公主長(zhǎng)得像阔拳，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子类嗤，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,440評(píng)論 2贊 348