[發(fā)明專利]基于關(guān)鍵節(jié)點(diǎn)選擇和蟻群優(yōu)化算法的大規(guī)模集成電路小時(shí)延故障測(cè)試通路選擇方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410642109.5
• 申請(qǐng)日: 2014-11-13
• 公開（公告）號(hào): CN104331569A
• 公開（公告）日: 2015-02-04
• 發(fā)明（設(shè)計(jì)）人: 俞洋;彭宇;陳修遠(yuǎn);彭睿
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50;G06N3/00
• 代理公司: 哈爾濱市松花江專利商標(biāo)事務(wù)所 23109
• 代理人: 張利明

1.基于關(guān)鍵節(jié)點(diǎn)選擇和蟻群優(yōu)化算法的大規(guī)模集成電路小時(shí)延故障測(cè)試通路選擇方法，其特征在于，它包括以下步驟：

步驟一：將待選擇通路的大規(guī)模集成電路按照節(jié)點(diǎn)連接結(jié)構(gòu)轉(zhuǎn)化為拓?fù)浣Y(jié)構(gòu)，并將該拓?fù)浣Y(jié)構(gòu)保存為鄰接矩陣，然后將該鄰接矩陣作為目標(biāo)電路網(wǎng)絡(luò)；

步驟二：在上述目標(biāo)電路網(wǎng)絡(luò)中，選取關(guān)鍵度評(píng)價(jià)標(biāo)準(zhǔn)中，排序前5％的節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)，根據(jù)關(guān)鍵度公式設(shè)置鏈入關(guān)鍵節(jié)點(diǎn)的連線上的信息素；

步驟三：利用蟻群優(yōu)化算法將螞蟻放置在目標(biāo)電路網(wǎng)絡(luò)的輸入節(jié)點(diǎn)處；

步驟四：根據(jù)目標(biāo)電路網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)之間的連接信息，獲得與螞蟻當(dāng)前所在節(jié)點(diǎn)連通的所有節(jié)點(diǎn)，并按概率原則在該所有節(jié)點(diǎn)中，選擇概率最大的節(jié)點(diǎn)作為螞蟻將要到達(dá)的下一個(gè)節(jié)點(diǎn)；

步驟五：判斷步驟四獲得的下一個(gè)節(jié)點(diǎn)是否為指定輸出節(jié)點(diǎn)，是則執(zhí)行步驟六，否則返回步驟四；

步驟六：將螞蟻從輸入節(jié)點(diǎn)至指定輸出接點(diǎn)之間走過的路徑作為待選擇的通路。

2.根據(jù)權(quán)利要求1所述的基于關(guān)鍵節(jié)點(diǎn)選擇和蟻群優(yōu)化算法的大規(guī)模集成電路小時(shí)延故障測(cè)試通路選擇方法，其特征在于，步驟二中所述關(guān)鍵度評(píng)價(jià)標(biāo)準(zhǔn)的依據(jù)為：Pagerank算法和HITS算法。

3.根據(jù)權(quán)利要求1所述的基于關(guān)鍵節(jié)點(diǎn)選擇和蟻群優(yōu)化算法的大規(guī)模集成電路小時(shí)延故障測(cè)試通路選擇方法，其特征在于，步驟二中所述根據(jù)關(guān)鍵度公式為：

Tau(i,j)=Tau_primary×Criticality(j)AverageCriticality,]]>

其中，i和j均為目標(biāo)電路網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，Tau_primary為信息素，Criticality(j)為關(guān)鍵節(jié)點(diǎn)j的節(jié)點(diǎn)關(guān)鍵度，AverageCriticality為整個(gè)目標(biāo)電路網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)鍵度的平均值，Tau(i,j)為目標(biāo)電路網(wǎng)絡(luò)中與關(guān)鍵節(jié)點(diǎn)i與j連接的互連線。