題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 大規(guī)模數(shù)值優(yōu)化中變量相關(guān)性學(xué)習(xí)的研究
- 來(lái)源：
- 第十二屆“挑戰(zhàn)杯”作品
- 小類：
- 信息技術(shù)
- 簡(jiǎn)介：
- 大規(guī)模數(shù)值優(yōu)化在多個(gè)領(lǐng)域中有著廣泛的應(yīng)用，然而目前尚未有通用的解決方法。為處理此類問(wèn)題，本作品提出了變量相關(guān)性的數(shù)學(xué)形式化定義, 并在協(xié)同演化算法中首次引入了不犯第二類錯(cuò)誤的變量相關(guān)性學(xué)習(xí)機(jī)制。實(shí)驗(yàn)研究表明，新算法性能比最先進(jìn)協(xié)同演化算法有了統(tǒng)計(jì)顯著的全面提升。申報(bào)者為一作的論文已被演化計(jì)算領(lǐng)域頂級(jí)會(huì)議PPSN’2010 接受，已由SCI、EI和ISTP 收錄，并被發(fā)明協(xié)同演化的美國(guó)研究小組引用。
- 詳細(xì)介紹：
- 大規(guī)模數(shù)值優(yōu)化在空中交通管理、傳感器網(wǎng)絡(luò)、工業(yè)設(shè)計(jì)等國(guó)民經(jīng)濟(jì)發(fā)展和工業(yè)建設(shè)的多個(gè)領(lǐng)域中有著廣泛的應(yīng)用，然而目前尚不存在通用的有效解決方法。 為處理此類問(wèn)題，本作品提出了變量相關(guān)性的數(shù)學(xué)形式化定義, 并以此位基礎(chǔ)，在協(xié)同演化算法中首次引入了不犯第二類錯(cuò)誤的變量相關(guān)性學(xué)習(xí)機(jī)制?；趪?guó)際公認(rèn)測(cè)試函數(shù)集的實(shí)驗(yàn)研究結(jié)果表明，作品中介紹的變量相關(guān)性學(xué)習(xí)機(jī)制使得新的算法的性能比當(dāng)前最先進(jìn)的協(xié)同演化算法有了統(tǒng)計(jì)顯著的全面提升，并進(jìn)一步闡明了變量相關(guān)性的學(xué)習(xí)在協(xié)同演化算法應(yīng)用中的重要性。 本作品相關(guān)的論文已被演化計(jì)算領(lǐng)域的頂級(jí)會(huì)議PPSN’2010 接受，目前已被SCI、EI 和ISTP 權(quán)威檢索收錄。作者受邀在大會(huì)上作為唯一本科生做墻報(bào)報(bào)告，獲得國(guó)際同行的廣泛認(rèn)可。目前已經(jīng)被發(fā)明協(xié)同演化的美國(guó)研究小組引用。
作品圖片
作品專業(yè)信息
撰寫(xiě)目的和基本思路
- 隨著當(dāng)今社會(huì)人口的飛速增長(zhǎng)和交通網(wǎng)絡(luò)的發(fā)展，大規(guī)模數(shù)值優(yōu)化問(wèn)題在工業(yè)生產(chǎn)和日常生活中不斷涌現(xiàn)。因?yàn)椤熬S數(shù)災(zāi)難”的存在，現(xiàn)有常規(guī)算法往往在大規(guī)模問(wèn)題上失效。為解決該類難題，本作品國(guó)際首次提出變量相關(guān)性的數(shù)學(xué)定義，并引入了系統(tǒng)的變量相關(guān)性學(xué)習(xí)機(jī)制，同時(shí)結(jié)合分而治之的思想，成功設(shè)計(jì)了一種新穎的大規(guī)模數(shù)值優(yōu)化算法?；趪?guó)際公認(rèn)測(cè)試集的研究結(jié)果表示，本作品算法性能是目前國(guó)際領(lǐng)先的。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 本作品首次提出變量相關(guān)性的數(shù)學(xué)形式化定義，基于此堅(jiān)實(shí)的理論基礎(chǔ)，在協(xié)同演化算法中首次引入不犯第二類錯(cuò)誤的變量相關(guān)性學(xué)習(xí)機(jī)制，進(jìn)而形成了一套新穎的二階段協(xié)同演化算法。在演化計(jì)算國(guó)際會(huì)議CEC'2010提供的標(biāo)準(zhǔn)測(cè)試集上，本作品算法是目前世界上已發(fā)表性能好的協(xié)同演化算法。與之前已存的先進(jìn)協(xié)同演化算法DECC-G以及MLCC相比，在絕大部分測(cè)試函數(shù)上，CCVIL都有統(tǒng)計(jì)顯著的優(yōu)勢(shì)。
應(yīng)用價(jià)值和現(xiàn)實(shí)意義
- 目前在社會(huì)生產(chǎn)生產(chǎn)生活的諸多項(xiàng)目中，因?yàn)闋可娴匠汕先f(wàn)個(gè)因素的影響，并且這些因素之間又同時(shí)存在復(fù)雜的耦合關(guān)系。常規(guī)方法往往依賴經(jīng)驗(yàn)豐富的工程師花費(fèi)大量時(shí)間精力制定策劃方案。但這樣的方案缺乏全局統(tǒng)一規(guī)劃，離理論最優(yōu)有較大差距。本作品智能分析相關(guān)性信息，結(jié)合協(xié)同演化算法之后可以高效的解決大規(guī)模數(shù)值優(yōu)化問(wèn)題。本作品將推動(dòng)相關(guān)眾多應(yīng)用領(lǐng)域的發(fā)展，對(duì)優(yōu)化整合社會(huì)資源和提高工業(yè)生產(chǎn)效益都有深遠(yuǎn)的影響。
學(xué)術(shù)論文摘要
- 近年來(lái)協(xié)同演化被認(rèn)為解決高維優(yōu)化問(wèn)題有前景的算法框架，其基本思想是，試圖探索問(wèn)題的決策變量間的相關(guān)性信息，并據(jù)此將問(wèn)題分解為多個(gè)子問(wèn)題，每個(gè)子問(wèn)題包含若干互不重疊的決策變量組，組與組之間相對(duì)獨(dú)立的進(jìn)行優(yōu)化?；ゲ幌嚓P(guān)的變量可以被當(dāng)做單獨(dú)的規(guī)模更小的子問(wèn)題來(lái)進(jìn)行優(yōu)化；而相關(guān)的變量則必須被分于同一組之中，一起優(yōu)化求解。早期研究工作采用的是簡(jiǎn)單的、相對(duì)低效的分組策略，比如單維分組法和對(duì)半分組法。隨后，研究者提出了更高效、自適應(yīng)的分組策略，例如DECC-G和MLCC。然而，現(xiàn)存的這些分組策略都是粗粒度的，不能夠適應(yīng)不同的分組大小和保證分組的合理性。在本文中，我們提出了一個(gè)新穎、具有變量相關(guān)性學(xué)習(xí)能力、基于協(xié)同演化的算法框架（CCVIL）。CCVIL首先假設(shè)給定問(wèn)題的所有變量都相互獨(dú)立，因而放于各不相同的分組之中。此后，CCVIL將采集變量相關(guān)的證據(jù)，一旦有足夠證據(jù)說(shuō)明來(lái)自不同分組的兩個(gè)變量是相關(guān)的，則將變量所在的兩個(gè)分組合并。我們將使用大規(guī)模黑盒優(yōu)化的測(cè)試函數(shù)集來(lái)衡量新算法框架的性能。
獲獎(jiǎng)情況
- "Large-Scale Global Optimization Using Cooperative Coevolution with Variable Interaction Learning", in 'Parallel Problem Solving from Nature, PPSN XI', 2010. 申請(qǐng)人為論文的第一作者及通訊作者。該論文被演化計(jì)算領(lǐng)域頂級(jí)國(guó)際會(huì)議——PPSN'2010接受，同時(shí)被SCI、EI和ISTP權(quán)威檢索。PPSN會(huì)議兩年一屆，是演化計(jì)算領(lǐng)域最早、享有盛譽(yù)的會(huì)議，第十一屆會(huì)議于2010年9月11日至2010年9月15日在波蘭克拉科夫舉辦。上屆會(huì)議于2008年在德國(guó)舉辦，中國(guó)大陸并沒(méi)有論文被接受。申請(qǐng)人作為唯一一名第一作者的本科生受邀在大會(huì)上做墻報(bào)報(bào)告，獲得國(guó)際同行的廣泛認(rèn)可。目前論文已經(jīng)被發(fā)明協(xié)同演化的美國(guó)研究小組引用。
鑒定結(jié)果
- 論文錄用通知中譯本： 我們很高興通知您提交至PPSN’2010的論文已被接受并收錄至?xí)h錄。因?yàn)槲覀兪盏搅舜罅康恼撐奶峤唬恼撐谋唤邮苁且豁?xiàng)重大的成就！
參考文獻(xiàn)
- 一、PPSN國(guó)際會(huì)議評(píng)價(jià)參考 PPSN會(huì)議官方網(wǎng)站的錄用文章列表（本文序號(hào)為#66）： ~ppsn/accepted.php Springer官方網(wǎng)站里本論文的下載入口： 二、技術(shù)文獻(xiàn)目錄 Potter, M.A., De Jong, K.A.: Cooperative coevolution: architecture for evolving coadapted subcomponents. Evolutionary Computation 8(1) (2000) 1–29 Yang, Z., Tang, K., Yao, X.: Large scale evolutionary optimization using cooperative coevolution. Information Sciences 178(15) (2008) 2985–2999 Tang, K., Li, X., Suganthan, P.N., Yang, Z., Weise, T.: Benchmark functions for the CEC’2010 special session and competition on large scale global optimization. TR, NICAL, USTC, Hefei, Anhui, China (2009) Weicker, K., Weicker, N.: On the improvement of coevolutionary optimizers by learning variable interdependencies. In: IEEE CEC, IEEE Press (1999) 1627–1632
同類課題研究水平概述
- 演化算法在國(guó)內(nèi)外已經(jīng)有了一定的研究基礎(chǔ)，其在低維問(wèn)題上可行性和有效性已經(jīng)被廣泛證實(shí)與接受。然而隨著問(wèn)題規(guī)模的增加，演化算法的性能往往出現(xiàn)明顯的下降。在實(shí)際工程應(yīng)用中，大規(guī)模優(yōu)化有著廣泛的應(yīng)用，例如大規(guī)模電力系統(tǒng)的設(shè)計(jì)，大規(guī)模維數(shù)的資源調(diào)度和大規(guī)模交通網(wǎng)絡(luò)的車輛調(diào)度問(wèn)題。該類問(wèn)題因此成為當(dāng)前研究的一大熱點(diǎn)，美國(guó)電氣和電子工程師協(xié)會(huì)（IEEE）的計(jì)算智能分會(huì)還因此成立了大規(guī)模全局優(yōu)化的特別研究小組。過(guò)去5年內(nèi)，國(guó)內(nèi)外許多研究小組投入到對(duì)大規(guī)模數(shù)值優(yōu)化難題的攻克之中。這些研究主要集中于兩個(gè)方面： 設(shè)計(jì)更適合大規(guī)模優(yōu)化的算子：發(fā)展這類算子的原因在于，經(jīng)典的演化算法算子大多針對(duì)低維問(wèn)題上所設(shè)計(jì)的。而在面對(duì)解空間復(fù)雜程度大大增加的高維問(wèn)題時(shí)，它們的效果驟降，這種現(xiàn)象激發(fā)研究人員進(jìn)行更有針對(duì)性的算子設(shè)計(jì)。這類方法將大規(guī)模黑盒優(yōu)化問(wèn)題本身當(dāng)成一個(gè)整體來(lái)進(jìn)行優(yōu)化，并未分而治之的思想，故真正使得它們性能優(yōu)越的原因在于專門設(shè)計(jì)的算子。文獻(xiàn)[1]將一種專門針對(duì)大規(guī)模問(wèn)題的自適應(yīng)策引入差分演化（Differential Evolution）算法。針對(duì)大規(guī)模問(wèn)題專門設(shè)計(jì)算子而得到的算法往往對(duì)問(wèn)題的依賴性強(qiáng)，算法的可擴(kuò)放能力有限。 [1] Brest, J., Zamuda, A., Fister, I. & Mauc?andec, M. Large scale global optimization using self-adaptive differential evolution algorithm. CEC 2010, pp. 1-8 結(jié)合協(xié)同演化算法，采用分而治之的思想。在采用協(xié)同演化算法解決大規(guī)模問(wèn)題時(shí)，如何合理分組使得各組之間不存在相互依賴關(guān)系便成為了關(guān)鍵問(wèn)題。文獻(xiàn)[2]通過(guò)函數(shù)值提升的大小估計(jì)可能的變量相關(guān)性。 [2] Omidvar, M.N., Li, X. & Yao, X. Cooperative Co-evolution with delta grouping for large scale non-separable function optimization. CEC 2010, pp. 1-8
