[發(fā)明專利]一種基于模擬退火算法的數(shù)據(jù)倉(cāng)庫(kù)ETL調(diào)度優(yōu)化方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202210798498.5
• 申請(qǐng)日: 2022-07-06
• 公開(kāi)（公告）號(hào): CN115129451A
• 公開(kāi)（公告）日: 2022-09-30
• 發(fā)明（設(shè)計(jì)）人: 左鋒;袁馳;蒙國(guó)學(xué);程坤;賈鋒
• 申請(qǐng)（專利權(quán)）人: 中國(guó)人民解放軍陸軍軍醫(yī)大學(xué)第一附屬醫(yī)院
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F16/25
• 代理公司: 重慶青飛知識(shí)產(chǎn)權(quán)代理有限公司 50283
• 代理人: 彭啟龍

1.一種基于模擬退火算法的數(shù)據(jù)倉(cāng)庫(kù)ETL調(diào)度優(yōu)化方法，其特征在于：該方法包括以下步驟：

S1：初始化初始溫度C、初始任務(wù)調(diào)度狀態(tài)S、每一個(gè)溫度的迭代次數(shù)D、溫度下降的速率R、最低溫度C₀；

S2：生成初始任務(wù)工作隊(duì)列Queue₀，計(jì)算初始任務(wù)調(diào)度的任務(wù)執(zhí)行時(shí)間f(0)；

S3：判斷CC₀，滿足條件的話執(zhí)行步驟S4；否則執(zhí)行步驟S9；

S4：根據(jù)產(chǎn)生新解的規(guī)則：對(duì)于初始化各個(gè)工作流的時(shí)間情況下，隨機(jī)交換最大工作流與最小工作流的其中一個(gè)任務(wù)；對(duì)于未知工作流時(shí)間的情況下，隨機(jī)交換兩個(gè)流的一個(gè)任務(wù)；根據(jù)該規(guī)則會(huì)產(chǎn)生一個(gè)新的任務(wù)工作隊(duì)列和任務(wù)執(zhí)行時(shí)間，產(chǎn)生新的任務(wù)工作隊(duì)列Queue_i和任務(wù)執(zhí)行時(shí)間f(i)，迭代計(jì)算D₀++，即迭代次數(shù)自加1，繼續(xù)執(zhí)行步驟S5；

S5：判斷f_if(0)，若滿足條件則執(zhí)行步驟S7，否則執(zhí)行步驟S6；

S6：根據(jù)Metropolis準(zhǔn)則，判斷是否成立，其中P為區(qū)間(0,1)之間的隨機(jī)數(shù)，T表示迭代過(guò)程中的控制參數(shù)，若上式成立，則繼續(xù)執(zhí)行步驟S7，否則繼續(xù)執(zhí)行步驟S8；

S7：接受當(dāng)前任務(wù)工作隊(duì)列Queue_i和f(i)，即Queue₀＝Queue_i，f(0)＝f(i)，繼續(xù)執(zhí)行步驟S8；

S8：判斷是否達(dá)到最大迭代次數(shù)，即D₀D，若是則將溫度C以一定的溫度下降速率R下降得到新的溫度，繼續(xù)執(zhí)行步驟S3，否則繼續(xù)執(zhí)行步驟S4；

S9：當(dāng)前任務(wù)工作隊(duì)列Queue₀，任務(wù)調(diào)度的任務(wù)執(zhí)行時(shí)間f(0)即為模擬退火算法所找到的最優(yōu)解。

2.根據(jù)權(quán)利要求1所述的一種基于模擬退火算法的數(shù)據(jù)倉(cāng)庫(kù)ETL調(diào)度優(yōu)化方法，其特征在于：在步驟S1中，初始化過(guò)程中對(duì)于某個(gè)ETL過(guò)程包含的m個(gè)任務(wù)，任務(wù)i執(zhí)行所需要的時(shí)間就是t_i(1≤i≤m)；所有任務(wù)通過(guò)處理后分為了n組隊(duì)列，其中第j組任務(wù)所需要的總執(zhí)行時(shí)間為T(mén)_j(1≤j≤n)：

其中的

3.根據(jù)權(quán)利要求2所述的一種基于模擬退火算法的數(shù)據(jù)倉(cāng)庫(kù)ETL調(diào)度優(yōu)化方法，其特征在于：在步驟S6中，根據(jù)Metropolis準(zhǔn)則，判斷是否成立，其中P為區(qū)間(0,1)之間的隨機(jī)數(shù)，若上式成立，則繼續(xù)執(zhí)行步驟S7，否則繼續(xù)執(zhí)行步驟S8；

所述Metropolis準(zhǔn)則基本思想在退火迭代過(guò)程中，通過(guò)一定概率接收劣解，從而可能跳出局部最優(yōu)，并且隨著溫度降低，會(huì)降低接受劣解的概率，直到溫度逐漸趨于一定值時(shí)，那么接受劣化解的概率也會(huì)接近于0，從而完成退火的過(guò)程；

Metropolis接受準(zhǔn)則數(shù)學(xué)表達(dá)式為：

其中P是當(dāng)前新解的接受概率；ΔE是當(dāng)前新解與先前解對(duì)應(yīng)目標(biāo)函數(shù)的差；T表示迭代過(guò)程中的控制參數(shù)。