分布估計(jì)算法研究及其在軟硬件劃分中的應(yīng)用.pdf

1、嵌入式系統(tǒng)已經(jīng)廣泛地滲透到了人類生活中，它的功能實(shí)現(xiàn)有硬件和軟件兩種方式，其中硬件實(shí)現(xiàn)具有系統(tǒng)性能好但制造代價(jià)大、開發(fā)完成后難于修改等特點(diǎn)。軟件實(shí)現(xiàn)具有高靈活性、制造代價(jià)小但性能相對(duì)較差等特點(diǎn)。如何以最小的代價(jià)獲得最好的系統(tǒng)性能是嵌入式系統(tǒng)設(shè)計(jì)中的重要問題，系統(tǒng)軟硬件劃分也因此成為研究熱點(diǎn)。目前，自動(dòng)的軟硬件劃分還沒有被廣泛應(yīng)用于嵌入式系統(tǒng)商業(yè)產(chǎn)品的實(shí)際制造中，其中一個(gè)很重要的原因，就是求解算法低效。如軟硬件劃分問題常用的遺傳算法，由于

2、其進(jìn)化過程中的積木塊破壞問題，使其實(shí)際應(yīng)用受到很大制約。分布估計(jì)算法作為進(jìn)化計(jì)算領(lǐng)域新興的一個(gè)分支，是為解決遺傳算法中存在的積木塊破壞問題而提出的，它彌補(bǔ)了遺傳算法的不足，為求解軟硬件劃分問題提供了一個(gè)新的有效工具。但該算法也存在種群多樣性易失、局部搜索能力較差等問題。
　　本論文針對(duì)嵌入式系統(tǒng)的軟硬件劃分問題，著力于分布估計(jì)算法及應(yīng)用的研究，主要研究工作與成果如下：
　　1.針對(duì)分布估計(jì)算法存在的種群多樣性損失導(dǎo)致的早熟收

3、斂問題，將分布估計(jì)算法的快速收斂性與遺傳算法的種群多樣性相結(jié)合，提出了一種動(dòng)態(tài)融合的遺傳分布估計(jì)算法。該算法在每一次迭代中由二者共同產(chǎn)生種群，在進(jìn)化前期搜索主要由分布估計(jì)算法主導(dǎo)，后期則隨著迭代進(jìn)行逐漸增強(qiáng)遺傳算法的作用。通過0/1背包問題進(jìn)行仿真，結(jié)果表明算法可獲得好的尋優(yōu)結(jié)果并且收斂速度快，驗(yàn)證了所提算法的有效性。
　　2.在單變量邊緣分布算法中，前代信息和劣勢(shì)解被丟棄，但被丟棄的內(nèi)容中常攜帶有用信息。針對(duì)此問題，對(duì)前代信息和

4、劣勢(shì)解信息分別加以利用研究，提出了一種利用多信息的分布估計(jì)算法：在構(gòu)建概率模型時(shí)加入前代信息，并利用以往被丟棄的劣勢(shì)解構(gòu)建劣勢(shì)概率模型，用來對(duì)采樣產(chǎn)生的解進(jìn)行篩選，以避免產(chǎn)生差解。通過0/1背包問題進(jìn)行仿真驗(yàn)證，結(jié)果表明前代信息可以有效改善多樣性損失問題，劣勢(shì)解信息則有益于搜索，改進(jìn)收斂可靠性。
　　3.針對(duì)分布估計(jì)算法存在的局部搜索能力較差的問題，對(duì)分布估計(jì)算法進(jìn)行改進(jìn)，提出了一種精英克隆分布估計(jì)算法。該算法對(duì)精英解進(jìn)行克隆、T

5、變換和優(yōu)勢(shì)替換以加強(qiáng)局部搜索能力，對(duì)概率模型進(jìn)行修正以改善種群多樣性損失問題。通過多維背包問題進(jìn)行仿真驗(yàn)證，結(jié)果表明該算法有效改善了局部搜索能力差的問題，并保持了種群多樣性，非常有利于獲得問題的最優(yōu)解或接近最優(yōu)的滿意解。
　　4.為了提高概率模型的準(zhǔn)確性以及解的多樣性，提出了一種信息重組的多目標(biāo)分布估計(jì)算法。該算法在選擇的種群中加入了候選種群中與劣勢(shì)解集距離最遠(yuǎn)的個(gè)體，以確保多樣性。然后對(duì)所選種群進(jìn)行聚類，分別構(gòu)建各簇概率模型，并

6、利用信息熵指導(dǎo)將各概率向量組合構(gòu)成新的概率向量，以獲得父代最豐富的信息，從而保護(hù)問題解的結(jié)構(gòu)。將該算法通過多目標(biāo)背包問題進(jìn)行仿真驗(yàn)證，仿真結(jié)果表明該算法可以獲得更好的結(jié)果，驗(yàn)證了該算法的有效性。
　　5.將所提算法應(yīng)用于軟硬件劃分問題的求解。對(duì)于單目標(biāo)單約束的軟硬件劃分問題，建立了數(shù)學(xué)模型并將其轉(zhuǎn)化為0/1背包問題，由于提出的動(dòng)態(tài)融合的遺傳分布估計(jì)算法和利用多信息的分布估計(jì)算法都有效求解了0/1背包問題，所以兩種算法可有效求解此類

7、軟硬件劃分問題。對(duì)于多約束軟硬件劃分問題，建立了數(shù)學(xué)模型，將本文所提的精英克隆分布估計(jì)算法用于求解該問題，并將仿真結(jié)果與文獻(xiàn)的算法結(jié)果相比較，表明算法在36種不同的約束條件下均可獲得更好的優(yōu)化結(jié)果。對(duì)于多目標(biāo)軟硬件劃分問題，以JPEG編碼器為對(duì)象，建立了數(shù)學(xué)模型，將本文所提的信息重組多目標(biāo)分布估計(jì)算法用于求解該問題，并將仿真結(jié)果與文獻(xiàn)的遺傳算法結(jié)果相比較，所提算法能夠取得更好的尋優(yōu)結(jié)果。
　　本文所做僅是分布估計(jì)算法在軟硬件劃分問