[發明專利]一種基于分解的變鄰域多目標測試任務調度方法及平臺

有效

• 申請號: 201310303667.4
• 申請日: 2013-07-18
• 公開（公告）號: CN103345384A
• 公開（公告）日: 2013-10-09
• 發明（設計）人: 路輝;朱政;王曉騰
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F11/36
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 祗志潔

1.一種基于分解的變鄰域多目標測試任務調度方法，其特征在于，包括如下步驟：

步驟一：獲取選定測試任務集的信息，包括：

測試任務表T＝｛t₁，t_2，···，t_j…，t_N}，t_j為第j個測試任務，N為測試任務總數；

儀器資源表R={r₁，r₂，···,r_i，…，r_M}，r_i為第i個儀器，M為儀器總數；

測試方案集表，測試任務t_j的測試方案集定義為其中k_j是測試任務t_j的測試方案總數，j=1,2…,N；

以及測試任務間的時序約束關系表；

步驟二：初始化，具體包括步驟2.1～2.4；

步驟2.1：確定目標函數，目標函數包括測試時間f₁(x)和各步平均負荷f₂(x)；

測試時間其中，表示測試任務t_j選擇方案時的完成時間；x∈Ω，Ω為定義域；

設d表示并行步數，初始值為1，在所有的測試任務都安排儀器資源后，每存在兩個測試任務的儀器資源有重復時，更新d=d+1，計算總的并行步數，然后確定各步平均負荷：

其中，表示測試任務t_j在儀器r_i進行時的消耗時間；表示測試任務t_j與儀器r_i的需求關系，當測試任務t_j需要占用儀器r_i的情況下，否則

步驟2.2：變量及參數初始化；

記保存非劣解的集合為EP，且初始

初始化參考點最優解集z＝(z₁,z₂)^T，z₁＝min{f₁(x),x∈Ω}，z₂＝min{f₂(x),x∈Ω}；其中Ω代表解空間；

初始化的參數包括：最大迭代次數M'；種群大小N'；鄰域變化范圍，最大值為T_high，最小值為T_low；交叉概率CR和變異概率p；迭代次數為ger時，對應代的領域大小為

T＝floor(((T_high-T_low)/(M')²)*(ger-M')²)+T_low，floor表示向下取整；

步驟2.3：計算權重矢量鄰域索引集；找到與第i個權重矢量最近的T個權重矢量，定義第i個權重矢量鄰域索引集為B(i)＝{i₁,···,i_T}，i∈[1,N']；

步驟2.4：產生初始解；隨機產生初始種群，并確定每個個體對應的目標函數的值；每個個體中包含N個決策變量，其中第j個決策變量的值越大表示對應的第j個測試任務的執行時間越靠前；

步驟三、個體交叉；t代中的第i個個體交叉之后產生的個體為：

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

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

步驟四：個體變異；

設第t代的第i個個體為決策變量變異得到的為：

x(j)i*=normal(x(j)i,σ)rand(1)<px(j)irand(1)≥p,j=1,2,...,N]]>

其中，為一服從均值為方差為σ的正態分布的數，σ設置為決策變量變化范圍的1/20；表示xⁱ變異后的新個體；

步驟五：更新鄰域及參考點；

更新鄰域：對于j∈B(i)，定義參考點為z_i的第j個子問題的適應度為

其中表示第i個權重矢量鄰域索引集中的第j個權重矢量值；設個體y'為第i個個體變異后得到的解，對j∈B(i)，若適應度值F(y')≤F(x^j)，則更新種群個體x^j＝y',F(x^j)＝F(y')，否則，保持種群個體x^j不變；

更新z：對任意i＝1,2，若z_i＜f_i(y')，則賦值z_i＝f_i(y')；

步驟六：保存非劣解；每一代進化完成后，將所有得到的非劣解保存到集合EP中，并將集合EP中的劣解去除；

設兩個解及其目標函數值分別為：A₁(f₁(A₁),f₂(A₁))，A₂(f₁(A₂),f₂(A₂))；若f₁(A₁)≥f₁(A₂)且f₂(A₁)≥f₂(A₂)，則解A₁為劣解，刪除解A₁；

步驟七：通過層次分析法對集合EP中的非劣解進行最終決策；

步驟八：將最優方案輸出。