[發明專利]SoC測試中基于進化計算的掃描鏈平衡方法

無效

• 申請號: 201310070671.0
• 申請日: 2013-03-06
• 公開（公告）號: CN103217642A
• 公開（公告）日: 2013-07-24
• 發明（設計）人: 朱愛軍;李智;許川佩
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: G01R31/3185
• 分類號: G01R31/3185
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 歐陽波

1.SoC測試中基于進化計算的掃描鏈平衡方法，包括如下步驟：

步驟1、設置初始化參數

根據待測試的SoC的IP核內部掃描鏈的條數設定整數向量的維數d，

種群中的個體規模NP，

最大規定代數MaxGen，

最大變異概率m_max，

根據當前封裝掃描鏈分配的條數設定w的值，

最大遷入速率I,

最大遷出速率E；

步驟2、產生初始種群R和初始相反種群ROP

隨機產生一個種群個體規模為NP的初始種群R，

R=(X¹,X²,...,X^k,...,X^NP)，其中X^k=(X₁^k,X₂^k,...,X_p^k,...,X_d^k)，

X_p^k∈[1,w]，k∈[1,NP]，p∈[1,d]

上式中NP、d和w為步驟1所設值，k、p為整數；

根據公式Y_i^k=1+w-X_i^k,i∈[1,d]，產生一個初始相反種群ROP，

ROP=(Y¹,Y²,...,Y^k,...,Y^NP)，k∈[1,NP]；

步驟3、計算最終初始種群中所有個體的成本函數值，按照遞增排序

分別計算初始種群和初始相反種群中所有個體的成本函數值，根據基于相反點的優化方法，從初始種群R中的任一個體和其初始相反種群ROP中對應的相反個體選擇成本函數值較小者作為最終初始種群，即第0代種群的個體；計算第0代種群中所有個體的成本函數值，并且按照遞增排序,代數G=0；

成本函數為CF(Xk)=Σi=1i=w(L(Pi)-1nΣj=1j=n(L(Sj))2,]]>其中X^k為種群中的任一個體，k∈[1,NP]；L(P_i)表示第i條Wrapper掃描鏈的長度，L(S_j)表示第j條內部掃描鏈的長度；n表示內部掃描鏈的條數；w表示Wrapper掃描鏈的條數；用成本函數來衡量待選解X的適應度，成本函數值越大則代表其適應度越小；基于相反點的優化方法為：已知X為m維空間的一個點，以X為待選解,X=(X₁,X₂,…,X_m)；設Y=(Y₁,Y₂,…,Y_m)是X=(X₁,X₂,…,X_m)的相反點,m表示空間維數，如果CF(Y)≤CF(X),則用Y代替X點，否則，繼續采用X進行進化計算；

步驟4、保存第G代最優個體

將第G代種群中的第一個個體，即第G代成本函數值最小的個體，保存為第G代最優個體；

步驟5、計算第G代每個個體的遷入速率、遷出速率和轉移概率

將第G代種群的每個個體的成本函數值映射成相應個體的生物數，成本函數值最小個體的生物數映射為最大，成本函數值最大個體的生物數映射為最小；

根據公式Em_NP-k=E×(NP-k)/(Smax+1)計算每個個體的遷出速率Em_NP-k，表示第k個個體的遷出速率，式中E為最大遷出速率，Smax為個體容納生物數的最大值,k∈[1,NP]；

根據公式Im_NP-k=I×(1-(NP-k)/(Smax+1))計算每個個體的遷入速率Im_NP-k，表示第k個個體的遷入速率，其中I為最大遷入速率，Smax為個體容納生物數的最大值,k∈[1,NP]；

計算轉移概率Pr_NP-k，表示第k個體的轉移概率,其中T為數學符號轉置，k的取值從右到左為1到NP，其計算公式為：

式中k∈[1,NP]，n=Smax；

步驟6、對第G代種群進行遷徙操作

產生隨機數rand∈[0,1]，對于第k個個體X^k，k∈[1,NP]，如果rand≤Im_NP-k，則選中第k個個體的第j維，j∈[1,d]，執行遷徙操作：產生隨機數rd∈[0,1],第G代種群第t個個體的遷出速率Em_NP-t，t∈[1,NP]；如果rd≤Em_NP-t，則選中個體X^t，并用個體X^t的第j維代替個體X^k的第j維；否則個體保持不變；

步驟7、計算變異概率m_k

根據公式m_NP-k=m_max×(1-Pr_NP-k)/Pr_max計算第k個個體的變異概率m_NP-k，其中m_max為變異操作概率的最大值，步驟1已設定；Pr_max=max_0≤i≤nPr_i；

步驟8、對第G代種群進行變異操作

產生隨機數rand∈[0,1]，對于第k個個體X^k，k∈[NP/2,NP]，NP取偶數，本步驟只對NP/2的個體，即成本函數值較大的個體執行操作；

對于第k個個體X^k，k∈[NP/2,NP],如果rand≤m_NP-k，則選中X^k的第j維，j∈[1,d]，執行變異操作：隨機產生一個在1至w的整數代替原來的值；否則個體保持不變；

步驟9、保存步驟8變異操作后的當前代最差個體

計算步驟8變異操作后當前的第G代種群所有個體的成本函數值，按照成本函數值遞增的順序排序，得成本函數值最大個體，即當前代最差個體；

步驟10、獲得G=G+1代種群

用步驟4所得的第G代最優個體代替步驟9所得的當前代最差個體，該最優個體插入當前代群體中，使其中的個體按照成本函數值遞增排列，獲得G=G+1代種群；

步驟11、代數G是否達到步驟1設定的最大規定代數MaxGen，沒有達到則返回步驟4，達到則停止，輸出內部掃描鏈平衡最優解。