[發明專利]一種改進的遺傳退火的片上網絡映射方法

在審

• 申請號: 201710902013.1
• 申請日: 2017-09-29
• 公開（公告）號: CN109582985A
• 公開（公告）日: 2019-04-05
• 發明（設計）人: 魏瑩
• 申請（專利權）人: 魏瑩
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.改進的遺傳退火的片上網絡映射方法包括災變遺傳和多鄰域模擬退火兩部分,在標準的遺傳操作中，引Boltzmann選擇方法接收優良個體，并使用精英操作保存最優個體，提高算法搜索效率,當個體經過交叉操作和變異操作后，對不滿足帶寬約束的個體重新進行交叉和變異操作，使其滿足約束條件，然后映射任務到片上網絡，評價個體適應度，并按照適應度大小進行排序，選擇當前L個較優解進行多鄰域模擬退火操作，加強算法的局部搜索能力，并將經退火操作的個體替換較差的個體產生新一代種群,若算法進入停滯狀態，則采用災變操作，構建新個體，形成新種群．若滿足算法終止條件，即達到最大迭代次數或者溫度已降到冷卻狀態，則算法結束，輸出最優值;否則，繼續迭代搜索最優值。

2.根據權利要求1所述的改進的遺傳退火的片上網絡映射方法，災變遺傳算法是一種啟發式隨機搜索算法，種群規模的大小對算法的搜索效率影響非常大,在片上網絡映射應用中，采用實數編碼方式，設定染色體的長度等于IP核通信任務圖中IP核的數目，并將IP核的編號作為遺傳基因，數值為1～N,由于二維網格結構中tile的位置是按固定順序排列的，該發明將tile按照從左到右、從上到下的位置編號,基因i在染色體中排在位置p，表示第i個IP核映射到第p個tile中,為了保持群體的多樣性，在早期采用較小的選擇壓力，在后期使用較大的選擇壓力，加速搜索過程。

3.根據權利要求1所述的改進的遺傳退火的片上網絡映射方法，交叉操作是基因重組產生新個體的重要操作，利用兩點交叉法實施交叉操作，產生新個體,當個體中出現相同基因時，進行基因修復操作,變異操作采用單點非常規法，當變異點上的基因與染色體上其他基因重復時，進行基因修復，將非變異點重復基因替換為原變異點上的基因，從而獲得C→T的一一映射,若出現不滿足式帶寬約束的個體，則重復交叉和變異操作進行調整，最終得到一個新的可行解。

4.根據權利要求1所述的改進的遺傳退火的片上網絡映射方法，多鄰域模擬退火操作用來對L個適應度較優的個體進一步強化搜索，在當前個體的多個鄰域內隨機產生多個候選解，并選取其中最優的一個，提高了最優值的精度，進一步明確了搜索方向，有利于搜索局部最優解． 將經過模擬退火操作的個體替換種群中適應度較差的個體，形成新的種群，進一步加速搜索最優解。