實(shí)值演化算法投資組合研究.pdf

1、實(shí)值優(yōu)化問題普遍存在于工業(yè)與工程實(shí)踐中，具有廣泛的應(yīng)用背景。演化算法是從自然界的進(jìn)化與自適應(yīng)機(jī)制中獲得啟發(fā)而發(fā)展起來的求解問題的計(jì)算方法，具有簡(jiǎn)單、易于操作和通用性強(qiáng)等特性，在實(shí)值優(yōu)化領(lǐng)域取得了廣泛的成功，受到了人們?cè)絹碓蕉嗟闹匾?。?shù)十年間，演化實(shí)值優(yōu)化獲得了飛速的發(fā)展，各種各樣的實(shí)值演化算法不斷涌現(xiàn)。這些算法的提出一方面促進(jìn)了實(shí)值演化優(yōu)化的發(fā)展，但同時(shí)也給實(shí)踐人員帶來了如何選擇算法的問題。實(shí)際中，人們所能提供的計(jì)算時(shí)間通常是有限的。因

2、此，怎樣在有限時(shí)間內(nèi)為給定問題找到盡可能好的解，具有十分重要的現(xiàn)實(shí)意義。
　　 對(duì)于一個(gè)給定的問題，人們常常事先并不知道選擇何種算法才能有效地進(jìn)行求解。由于計(jì)算時(shí)間有限，一旦所選擇的算法表現(xiàn)不佳，則很難再有足夠的時(shí)間選擇下一個(gè)算法進(jìn)行有效求解。因此，對(duì)算法的選擇是有風(fēng)險(xiǎn)的。針對(duì)這一問題，我們提出了一個(gè)用于比較兩個(gè)算法風(fēng)險(xiǎn)程度的度量標(biāo)準(zhǔn)，并討論了該標(biāo)準(zhǔn)的合理性。在定義了風(fēng)險(xiǎn)度量標(biāo)準(zhǔn)之后，我們還面臨怎樣減小已有算法的風(fēng)險(xiǎn)程度這一問題

3、。我們建議，相對(duì)于將所有計(jì)算時(shí)間都“投注”在單個(gè)算法上，將時(shí)間分配在多個(gè)算法上將能夠獲得更優(yōu)的整體性能。基于這一思想，我們?cè)O(shè)計(jì)出一種演化算法的投資組合設(shè)計(jì)框架(population—based algorithmportfolios，PAP)。它將計(jì)算時(shí)間預(yù)先分配到多個(gè)子算法上，子算法并行進(jìn)行搜索。此外，PAP通過周期性地激活遷移機(jī)制以促進(jìn)子算法間的信息交流。該框架能夠?qū)⑷我鈱?shí)值演化算法組合在一起，具有簡(jiǎn)單、易實(shí)現(xiàn)等優(yōu)點(diǎn)。我們通過理論與

4、實(shí)驗(yàn)相結(jié)合的方式。全面分析了PAP框架在提升子算法整體性能、減小子算法風(fēng)險(xiǎn)方面的潛力。
　　 接下來，我們進(jìn)一步討論了如何在有限時(shí)間內(nèi)最有效地求解一組實(shí)值優(yōu)化問題。而對(duì)于實(shí)值優(yōu)化問題，通常存在若干演化算法可以對(duì)其進(jìn)行求解。通過第二章的研究成果可以看出。相對(duì)于簡(jiǎn)單地將計(jì)算時(shí)間平均分配到各個(gè)候選算法上，或者任意選擇一個(gè)算法并將所有計(jì)算時(shí)間分配給該算法，更好的做法是在求解問題之前先進(jìn)行算法選擇?；谶@樣的考慮，我們提出了以演化算法投資

5、組合作為基本搜索算法的解決方案。該方案能夠?yàn)橐粋€(gè)給定的問題集自動(dòng)地找出最優(yōu)PAP實(shí)例，具有簡(jiǎn)單易用的優(yōu)點(diǎn)。此外，它對(duì)問題間的聯(lián)系不作任何假設(shè)，并且利用了所有算法在所有問題上的性能信息。PAP作為該解決方案的基本搜索算法，具有提升其子算法在給定問題集上整體性能的潛力。然而，怎樣選擇一個(gè)最優(yōu)的算法子集來進(jìn)行投資組合設(shè)計(jì)，在此前的工作中并沒有提及。我們第一次將這一選擇任務(wù)形式化為一個(gè)優(yōu)化問題，并提出兩個(gè)選擇方法，試圖盡可能高效地找出最優(yōu)的PA

6、P實(shí)例。實(shí)驗(yàn)結(jié)果表明，該解決方案在解決一組問題時(shí)具有十分優(yōu)異的性能。
　　 最后，我們將演化算法投資組合應(yīng)用于非均勻間隔對(duì)稱天線陣列綜合問題。由于差分演化算法和粒子群算法在該問題上都已表現(xiàn)出良好的性能，因此，我們相應(yīng)地選擇了差分演化算法的一個(gè)變體，和粒子群算法的一個(gè)變體，作為子算法進(jìn)行投資組合設(shè)計(jì)。為了評(píng)估該投資組合實(shí)例的整體性能，我們將其與非均勻天線陣列綜合領(lǐng)域代表目前最新水平的算法進(jìn)行全方面的比較。實(shí)驗(yàn)表明。該投資組合實(shí)例在