[發明專利]一種基于分解和最優解跟隨策略的多目標測試任務調度方法

有效

• 申請號: 201310118145.7
• 申請日: 2013-04-07
• 公開（公告）號: CN103235743A
• 公開（公告）日: 2013-08-07
• 發明（設計）人: 路輝;朱政;王曉騰
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F11/36
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 趙文利

1.一種基于分解和最優解跟隨策略測試任務調度方法，包括以下幾個步驟：

第一步：開始

進入調度方法計算接口；

第二步：初始化

確定目標函數并初始化方法的參數設置，計算權重矢量鄰域索引集并給出初始解；

2.1?確定目標函數

本發明中目標函數為：最大完成時間與資源平均工作負荷；

確定測試任務集T＝{t₁,t₂,…,t_j,…,t_N}，t_j為第j個測試任務，N為測試任務總數；確定儀器資源集R＝{r₁,r₂,…,r_i,…,r_M}，r_i為第i個儀器，M為儀器總數，與分別代表在測試任務t_j在資源r_i進行時的起始時間、完成時間以及消耗時間，有判斷矩陣表示資源與任務的需求關系，其中t_j為第j個測試任務而r_i為第i個儀器；

t_j的測試方案集為其中k_j是測試任務t_j的測試方案總數，表示測試任務t_j選擇測試方案的測試消耗時間，r_i表示測試方案中的資源，測試方案集之間的資源約束表示為：其中與分別表示任務t_j的第k個方案選擇與任務的第k^*個方案選擇；

兩個目標函數是最大完成時間與資源平均工作負荷，分別用f₁(x)與f₂(x)表示；

設任務t_j選擇方案時完成時間為r_i表示測試方案中的資源，因此最大完成時間為f1(x)=max1≤k≤kj1≤j≤nCjk;]]>

設D表示并行步數，初始值設置為1，再給所有的任務都安排測試資源后，如果D＝D+1，計算得到并行總步數，則資源平均工作負荷為：其中表示測試任務t_j選擇測試方案的測試消耗時間，判斷矩陣表示資源與任務的需求關系；

2.2?變量及參數初始化

記最優解集為EP，且初始化每個目標函數的暫時最優解z＝(z₁,…,z_i,…,z_m)^T，z_i＝min{f_i(x),x∈Ω}，即z_i為各目標函數在定義域內的理論最小值，基于分解和最優解跟隨策略測試任務調度方法的參數包括：迭代次數M，種群大小N，鄰域大小T，交叉概率CR，變異概率p，慣性權重w，學習因子c1、c2；

2.3?計算權重索引集

計算與第i個權重矢量最近的T個權重索引集，其中索引集記為B(i)＝{i₁,…,i_T}，記λⁱ為均勻分布的N個權重矢量中的第i個權重值，i∈[1,N]，是λⁱ的T個最近的權重值，N為基于分解和最優解跟隨策略的多目標測試任務調度方法的子問題的數目即種群大小，T為距離每單個的權重矢量最近的權重矢量的數量即鄰域大小。

2.4?生成初始解

隨機產生初始種群記為x¹,…,x^N，并令每個個體對應目標函數的解為f_i(x^j)，其中i∈[1,2]，j∈[1,N]；

第三步：交叉

記t代中一個體為交叉之后產生的個體為具體交叉方式如下：

xt+1i=xti+F1×(xti-xti1)+F2×(xti-xti2)rand(1)<CRxtirand(1)≥CR]]>

其中：與為權重矢量B(i)中隨機挑選的指標，F₁與F₂設置為1，rand(1)為變化范圍為0到1的一隨機小數；

第四步：變異

變異采用高斯變異，對于每一個解高斯變異算子如下所示：

其中表示變異后的新個體，為一服從正態分布的數，其中為均值，σ為方差，σ在自然數編碼中設置為決策變量變化范圍的1/20；rand(1)為變化范圍為0到1的一隨機小數，p為0.05；

第五步：鄰域與參考點更新

更新z：對任意j＝1,…,m，若z_j＜f_j(y′)，則賦值z_j＝f_j(y′)，z_j為任意一最優解；

更新鄰域：y′為變異后得到的解；定義參考點為z_i的第j個子問題的適應度函數值為其中λ^j為均勻分布的權重矢量組中一個權重矢量，對j∈B(i)，若適應度函數值F(y′)≤F(x^j)，則任意初始種群x^j＝y′,f_i(x^j)＝f_i(y′),其中i∈[1,2]；

第六步：最優解跟隨

具體過程如下：

6.1?確定自身最優解

在每一代中，如果粒子所到達的點沒有被粒子之前所到達的點支配；則自身到達的最優解p_ld為其本身；如果粒子所到達的點被粒子之前所到達的點支配，將支配現在粒子到達點的解保存到一個集合中，則p_ld為此集合中對應的目標函數空間中的點與現在到達點歐式距離最近的解；

6.2?確定全局最優解

具體確定方法為：每一次迭代過程中，在交叉變異之后，所有的非支配解作為現有的前沿，然后計算每一個粒子與前沿上的點的歐式距離，其中與粒子最近的非支配解即為全局最優解p_gd；

6.3?進行最優解跟隨操作

按照以下公式以及由6.1與6.2中確定的優值來進行最優跟隨

v_td＝w×v_td+c₁×rand₁×(p_ld-x_td)+c₂×rand₂×(p_gd-x_td)

x_td＝x_td+v_td

其中x_td代表解，v_td代表粒子飛行速度，p_ld為確定的自身到達的最優解，p_gd為全局最優解，慣性權重w與學習因子c₁、c₂一般設置為1，rand₁與rand₂為變化范圍由0到1的隨機小數；

第七步：更新最優解集

從保留最優解的解集EP中刪除被支配的解，加入新的非支配解；

第八步：輸出最優解集

在滿足停止條件后，計算停止，輸出最優解集，進而得到測試方案的任務排序以及各任務所采用的資源。