基于改進(jìn)的遺傳算法軟硬件劃分方法研究
加入技術(shù)交流群
集成電路在過(guò)去30年的發(fā)展幾乎完全遵循Moore定律，即集成電路的集成度每隔18個(gè)月就翻一番?，F在集成電路的面積進(jìn)一步減小，并獲得更高的集成度。集成度增加的結果就是能集成越來(lái)越多的功能，甚至是一個(gè)完整的系統都能夠被集成到單個(gè)芯片之中。這樣原來(lái)由微處理器、協(xié)處理器和多塊其他外圍芯片組成的系統，可以集成在一塊芯片內實(shí)現，這種一塊芯片集成一個(gè)系統的技術(shù)，叫做系統集成芯片(SOC，System-On―Chip)技術(shù)。但是傳統的系統設計面臨著(zhù)許多必須解決的矛盾問(wèn)題，首先是系統高性能和低成本之間的矛盾；其次是系統復雜性與更新?lián)Q代周期之間的矛盾。
面對這種矛盾，一個(gè)可行的解決方案是采用SOC軟硬件協(xié)同設計方法。而軟硬件劃分是軟硬件協(xié)同設計方法的關(guān)鍵問(wèn)題。軟硬件劃分問(wèn)題是一個(gè)多目標優(yōu)化問(wèn)題，在優(yōu)化過(guò)程中要針對成本、面積、功耗、時(shí)間等多個(gè)目標?，F在已經(jīng)有很多算法應用到軟硬件劃分中，如遺傳算法、螞蟻算法、禁忌搜索算法、模擬退火算法等。本文主要采用基于小生境技術(shù)(Niching Methods)和精英保持策略的改進(jìn)遺傳算法來(lái)進(jìn)行軟硬件劃分研究。
l 遺傳算法基本思想
美國Michigan大學(xué)J．Holland教授于1975年提出的遺傳算法，遺傳算法是以達爾文的自然選擇和優(yōu)勝劣汰的生物進(jìn)化理論為基礎的。和傳統的搜索算法不同，遺傳算法從一組隨機產(chǎn)生的成為種群(Population)的初始解開(kāi)始搜索。種群中的每一個(gè)體都是問(wèn)題的一個(gè)解，稱(chēng)為染色體，這些染色體在后續迭代中不斷進(jìn)化，稱(chēng)為遺傳。在新一代形成中，根據適應值的大小選擇部分后代，淘汰部分后代。經(jīng)過(guò)若干代之后，算法收斂于最好的染色體，它可能是問(wèn)題的最優(yōu)解或近似最優(yōu)解。圖l是遺傳算法基本的流程示意圖。
遺傳算法有三類(lèi)基本的操作：選擇(Selection)、交叉(Crossover)、和變異(Mutation)。選擇的目的是為了從當前群體中選出優(yōu)良的個(gè)體，是它們有機會(huì )作為父代為下一代繁殖子孫，選擇的原則是給予適應度強的個(gè)體較大的機會(huì )。交又是最主要的遺傳算法操作，它同時(shí)對兩個(gè)染色體進(jìn)行操作，組合二者的特性產(chǎn)生新的后代，遺傳算法的性能很大程度上取決于采用的交叉運算的性能。變異發(fā)生的概率最低，變異操作是在染色體上自發(fā)地產(chǎn)生隨機變化，在遺傳算法中變異可以提供初始種群中不包括的基因，為種群提供新的個(gè)體。
遺傳算法的主要優(yōu)點(diǎn)是：1)具有領(lǐng)悟無(wú)關(guān)的群體性全局搜索能力，可避免陷入局部最優(yōu)；2)搜索使用評價(jià)函數啟發(fā)過(guò)程簡(jiǎn)單；3)使用概率機制進(jìn)行迭代，具有隨機性；4)可擴展性強，易于介入已有的模型中去，且易于與其他優(yōu)化技術(shù)結合。
2 小生境技術(shù)和精英保持策略
2．1 小生境技術(shù)
早熟收斂是遺傳算法最嚴重的一個(gè)問(wèn)題，保持群體的多樣性可以有效地防止群體的早熟收斂，而且種群多樣性也是遺傳算法能夠搜索全局最優(yōu)解的基本條件。其中小生境(niching methods)技術(shù)是遺傳算法維持種群多樣性而廣為采用的方法。在生物學(xué)中，小生境是指特定環(huán)境下的一種生存環(huán)境，相同的生物生活在同一個(gè)小生境中。借鑒此概念，遺傳算法將每一代個(gè)體劃分成若干類(lèi)，每個(gè)類(lèi)中選出若干適應度較高的個(gè)體作為一個(gè)類(lèi)的優(yōu)秀代表組成一個(gè)種群，再在種群中以及不同種群之間通過(guò)雜交、變異產(chǎn)生新一代個(gè)體群，同時(shí)采用預選擇機制或者排擠機制或共享機制完成選擇操作。這樣就可以更好的保持群體的多樣性，使其具有較高的全局尋優(yōu)能力和收斂速度。遺傳算法中模擬小生境的方法主要有以下幾種：1)基于預選擇的小生境實(shí)現方法；2)基于排擠的小生境實(shí)現方法；3)基于共享函數的小生境實(shí)現方法。
2．2 精英保持策略
在遺傳算法的運行過(guò)程中，通過(guò)對個(gè)體進(jìn)行交叉、變異等遺傳操作而不斷地產(chǎn)生出新的個(gè)體。雖然隨著(zhù)群體的進(jìn)化過(guò)程會(huì )產(chǎn)生出越來(lái)越多的優(yōu)良個(gè)體，但是猶豫遺傳算法的隨機性，可能會(huì )破壞當前群體中的最好的個(gè)體。這將對遺傳算法的有效性和收斂性都有很大影響。為了使適應度最好的個(gè)體能夠保存到下一代群體中，本文使用精英保持策略(Elitlsm Preserving)來(lái)進(jìn)行優(yōu)勝劣汰，將當前群體中適應度最高的個(gè)體不參與交叉和變異運算，而是用它來(lái)替代當前代中適應度最低的個(gè)體。假設P，代表第i代的進(jìn)化群體，則精英保持策略的操作示意如圖2：
如圖2所示，精英保持策略的基本思想是對Pi進(jìn)行非劣排序，在群體中挑出最優(yōu)的個(gè)體保留到下一代Pi+1。這種保留通過(guò)在遺傳操作外部維持一個(gè)輔助群體P*來(lái)實(shí)現。P*中個(gè)體的編碼決策向量是所有解向量中的非被支配向量，即當前代的Pareto最優(yōu)解。由于每代進(jìn)化后的非支配向量大小是個(gè)不定量，外部群體P*的大小具有不確定性。為了保持外部群體大小不變，在實(shí)際操作過(guò)程中采用截斷操作的辦法防止邊界解的遺失。其具體做法是：將Pi和P*i中所有的個(gè)體復制到P*i+1。如果P*i+1的群體大小超過(guò)了N*，利用截斷操作減少|(zhì)P*i+1|；如果P*i+1的群體大小少于N*，則用被支配個(gè)體填充P*i+1。
評論