分布估計算法研究及其在軟硬件劃分中的應用.pdf

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

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

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

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

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

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

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