[發明專利]一種用于多技能資源受限項目調度的進化策略算法

在審

• 申請號: 202011001300.3
• 申請日: 2020-09-22
• 公開（公告）號: CN112148446A
• 公開（公告）日: 2020-12-29
• 發明（設計）人: 熊體凡;田源;劉振元;高鑫浩;吳航
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06N3/00
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 楊采良

1.一種用于多技能資源受限項目調度的進化策略算法，其特征在于，包括以下步驟：

S1：設置算法參數及初始化變量；

S2：初始化種群；

S3：對種群中的個體執行變異操作；

S4：評估種群適應度；

S5：更新帕累托種群；

S6：選擇下一代的父代種群；

S7：判斷是否滿足迭代的終止條件，若滿足條件，則終止程序并輸出帕累托種群，否則繼續執行步驟三。

2.根據權利要求1所述的用于多技能資源受限項目調度的進化策略算法，其特征在于：所述步驟S1具體為：設置種群大小P_size，子代生成數λ，資源平衡強度∈，最大迭代次數G_max；初始化當前迭代次數g＝0，父代種群集合子代種群集合帕累托解集帕累托解集的定義為：在多目標優化問題中，對于兩個解S1和S2，如果S1的每個目標都不差于S2且至少一個目標優于S2，則S1支配S2，如果S1沒有被種群其它解支配，則稱S1為種群非支配解，一個種群所有的非支配解組成種群的Pareto解集。

3.根據權利要求1所述的用于多技能資源受限項目調度的進化策略算法，其特征在于：所述步驟S2：種群中的個體采用長度為N的整數編碼，其表示為RL＝{R(1)，R(2)，...，R(N)}；其中N為待求解問題的任務集規模；R(i)表示任務T_i所指派的資源序號；該步驟分為兩個子步驟：

S2.1：在初始化階段，種群按照“最低成本-最長工期”策略僅生成一個個體；具體而言，為每一個任務，在能夠執行該任務的資源集合中，為其分配工時成本最低的資源，如果存在工時成本多個工時成本最低的資源，則取資源序號小的資源，即

S2.2：在適應度評估階段，計劃生成方案(SGS)將個體p的編碼轉換為可行的調度方案，并計算其目標函數。

4.根據權利要求1所述的用于多技能資源受限項目調度的進化策略算法，其特征在于：所述步驟S3：以種群P中的每個個體作為父體，每個父體(p∈P)生成λ個子代個體，從而形成子代集合Q；變異操作由資源平衡算子執行，其步驟如下：

S3.1：讀取父體生成的調度方案，根據方案中每個資源所分配到的任務π^r(r∈R)，計算每個資源的實際工作時長u_r(r∈R)；初始化計數變量n＝0；復制父體p的編碼，并命名為q；

S3.2：以資源的時間工作時長u_r為權重，根據輪盤賭規則(Roulette Selection)選出一個資源R_s(s∈R)；權重越高，被選中的概率越大；

S3.3：針對選出的資源R_s，隨機選出該資源上的某個任務(T_i∈π^r)，并將其重新分配給其他資源R_x(x∈Rⁱ)，

S3.4：將新指派資源的更改應用到新的個體編碼上；

S3.5：計數變量自增n＝n+1；如果n≤∈，則轉至步驟A2；否則，輸出新生成的個體q并加入到子代集合Q中，算子執行結束。

5.根據權利要求1所述的用于多技能資源受限項目調度的進化策略算法，其特征在于：所述步驟S4為：評估子代種群中的每個個體q∈Q的適應度，求得每個個體的所生成的工期(fitness_(q，1))和成本適應度(fitness_(q，2))。

6.根據權利要求1所述的用于多技能資源受限項目調度的進化策略算法，其特征在于：所述步驟S6：

S6.1：對PA中的個體進行排序，順序首先按照個體的支配等級升序排列；如果個體的支配等級相同，則再按照擁擠度降序排列；具體而言，假設有兩個個體(p，q∈PA)，其排列順序由下式決定：

p＞q if(p_rank＜q_rank)∨((p_rank＝q_rank)∧(p_distance＞q_distance))

S6.2：迭代次數自增g＝g+1。

7.根據權利要求1所述的用于多技能資源受限項目調度的進化策略算法，其特征在于：所述步驟S7：判斷是否滿足迭代的終止條件(g＜G_max)，若滿足條件，則終止程序并輸出PA集合中的非支配個體，否則繼續執行步驟S3。