[發明專利]一種用于異構系統的遺傳算法

在審

• 申請號: 201811647674.5
• 申請日: 2018-12-29
• 公開（公告）號: CN109726001A
• 公開（公告）日: 2019-05-07
• 發明（設計）人: 晏子含;鄧澤喜
• 申請（專利權）人: 中山大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06N3/12
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

1.一種用于異構系統的遺傳算法，其特征在于，包括以下步驟：

S1：種群初始化，生成一個種群，所述的種群包括若干個個，而Mapping Part的元素則通過隨機選定，且同數據同內存，所述的同數據同內存表示如下：

對于Sequence Part中的Tn，通過Mapping Part的Pn與Sequence Part中的Tn對應；對于Sequence Part中的異構系統的拓撲圖的訪問內存操作操作，通過Mapping Part的異構系統的拓撲圖的n號內存與Sequence Part中的異構系統的拓撲圖的訪問內存操作操作對應；

S2：評價個體，計算種群中每個個體的執行時間；

S3：判斷種群中執行時間最小的個體是否低于最低可接受執行時間，如滿足，跳出算法結束；如不滿足，跳至S4；

S4：通過2-錦標賽選擇法，形成新的種群，定義為第一新種群；

S5：對新種群中的個體進行交叉以產生基因重組，交叉斷點為隨機生成，交叉完成后需對子代個體進行修正，符合“同數據同內存”限制；

S6：S5交叉后，對種群中的每個個體進行變異操作，變異點為隨機生成，在變異完成后需對子代個體立即進行修正，使其符合“同數據同內存”限制，跳至S2。

2.根據權利要求1所述的遺傳算法，其特征在于，所述的S2包括以下內容：

S2.1：令數組LT的內容為個體的Sequence Part，即LT為任務的執行序列；

S2.2：定義數組RT內容為異構系統的各個處理機的最早就緒時刻，將其元素全部初始化為0，RT[pj]為處理機Pj的最早就緒時刻；數組ST內容為各任務開始執行時間，ST[ti]為任務Ti的開始執行時間；數組FT內容為各任務執行結束時間，FT[ti]為任務Ti的執行結束時間；

S2.3：定義weight[ti]為任務ti的執行用時，所述的weight[ti]通過下式進行求取：

weight[ti]＝Size[ti]/speedx

其中，所述的Size[ti]為任務大小，所述的speedx為對應的處理機處理速度；

S2.4：定義DAT[ti]為任務的就緒時間，其值為任務ti在異構系統拓撲圖上所有前繼的FT的最大值；

S2.5：依次將Ti取值為LT中的任務，然后分別執行ST[ti]＝max{RT[pj],DAT(ti)}，FT[ti]＝ST[ti]+weight[ti]，RT[pj]＝FT[ti]三條語句，直到ti取完LT的所有任務為止，所述的pj為ti對應的處理機；其中，max為求最大值函數；

S.2.6：取數組FT中元素的最大值，此即為所求的該個體的執行時間。

3.根據權利要求1或2所述的遺傳算法，其特征在于，所述的S4包括以下流程：

S4.1：從S1的種群中隨機選擇兩個個體；

S4.2：比較S4.1中選擇的兩個個體的執行時間；

S4.3：將執行時間較短的個體挑選出來，作為第一新種群的個體；

S4.4：若第一新種群的個體數量和原種群一樣時，結束執行；否則，返回S4.1。

4.根據權利要求3所述的遺傳算法，其特征在于，所述的S5包括以下流程：

S5.1：對S4中第一新的種群，更新為原種群；

S5.2：從原種群中隨機選出兩個個體；

S5.3：對于S5.2選擇出的兩個個體，在Mapping Part中隨機選擇一個位置作為交叉點，將兩個個體位于交叉點前的序列互換，生成兩個新的個體；

S5.4：對子代的個體進行修正，對于訪問同一數據的內存訪問操作，其在Mapping Part對應的內存需被設置成同一內存，符合“同數據同內存”限制；

S5.5：將新的個體加入新種群，定義為第二新的種群；

S5.5：若第二新的種群的個體數量擴充至和原種群一樣時，結束執行，否則，返回S5.2。