[發明專利]基于混沌遺傳算法的測試用例集約簡算法

在審

• 申請號: 201410490197.1
• 申請日: 2014-09-23
• 公開（公告）號: CN104268077A
• 公開（公告）日: 2015-01-07
• 發明（設計）人: 蔣云良;樓俊鋼
• 申請（專利權）人: 湖州師范學院
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06N3/12
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

1.基于混沌遺傳算法的測試用例集約簡算法，其特征在于按照以下步驟進行：

步驟1：編碼、初始化種群；初始化父體編碼時滿足當父體W_i與子體g_[i]下標相等時，g_[i]＝1，其余g_[i]＝0；

步驟2：當父體編碼改變時需重新計算其適應度，適應度值主要用于輪盤賭選擇算法和混沌遺傳算法，使用傳統適應度函數計算公式，將適應度計算的對象變為對父體W_i按公式F(W_i)＝Cov(W_i)/Cost(W_i)進行適應度計算，其中，Cov(W_i)指父體的測試覆蓋度，Cov(W_i)是父體的測試運行代價，覆蓋程度Cov(W_i)為計算父體編碼W_i中覆蓋測試需求r_k的的個數；

步驟3：定義遺傳算子；遺傳算子包括選擇、交叉、變異三步，主要對父體進行遺傳變異，對其進行優化最終得到新的父體的一個過程，新父體的生產可能會增加向最優解變異的機會，因此在遺傳算子結束后需再對新的父體進行適應值評價，判斷是否滿足輸出條件，滿足則輸出最優子代，否則，則進行步驟4；

步驟4：添加混沌擾動；對當前種群中適應度后90％的父體，利用混沌系統，對其進行一定程度的微小擾動，從而提高其適應度，將選中的父體W_i＝[g_[1],g_[2],...,g_[n]]所指代的二進制的每一位都加一混沌擾動，按式g′_[k]＝(1-ε)g^*+ε·g_[k],1≤k≤n進行添加，然后按式g″_[k]＝c_i+d_i·g′_[k]映射為優化變量，進行迭代計算；其中g′_[k]為經過添加隨機擾動后形成的一個混沌變量，g^*為當前最優父體所指代的二進制編碼，g_[k]為迭代k次之后的編碼，通過g′_[k]＝(1-ε)g^*+ε·g_[k],1≤k≤n可得到一組新父體G′_[k]＝(g′_[1]g′_[2],...,g′_[n]),0＜ε＜1,對于ε的取值采用自適應進行選取，隨著搜索逐漸接近最優點，需將ε逐漸縮小，以保證在小范圍內搜索最優解：

ϵ=1-|k-1k|m,]]>

m為初始解群數，k為迭代次數，在式F(W_i)＝Cov(W_i)/Cost(W_i)中c_i,d_i為變換常數，通過式g″_[k]＝c_i+d_i·g′_[k]后得到父體的新編碼G″_[k]＝(g″_[1]g″_[2],...,g″_[n])，由于定義的編碼g″_[k]∈{0,1}，因此將g″_[k]通過式g[k]′′1g[i]′′>0.50else]]>變換到相應的取值，

不斷迭代直到前后兩次計算出的適應度平均值之差小于預先給定的最小正數ε₁為止。