[發明專利]基于多智能體進化算法的資源受限項目調度方法

無效

• 申請號: 201210454380.7
• 申請日: 2012-11-01
• 公開（公告）號: CN103020730A
• 公開（公告）日: 2013-04-03
• 發明（設計）人: 劉靜;蔡冰琦;焦李成
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 張問芬;王品華

1.一種基于多智能體進化算法的資源受限項目調度方法，將多智能體系統與進化計算相結合，用于求解資源受限項目調度問題，其特征在于：首先根據兩種算法初始化智能體網格中的每個智能體，然后用設計的鄰域競爭算子、鄰域交叉算子、變異算子和自學習算子對智能體進行優化，具體步驟如下：

(1)參數設定：P_c為鄰域交叉概率，P_m為變異概率，t為大于或等于0的整數，表示第t代，L^t表示第t代智能體網格，L^t+1/3和L^t+2/3是L^t和L^t+1間的中間代智能體網格，Best^t是L⁰，L¹，…，L^t中最優的智能體，CBest^t是L^t中最優的智能體，rand指隨機產生的0到1之間的實數，L_i，j表示處在智能體網格第i行、第j列的智能體，energy(L_i，j)表示智能體L_i，j的能量；

(2)初始化智能體網格L⁰，更新Best⁰，令t＝0，網格大小為L_size*L_size，其中L_size為整數，設計為使網格中智能體個數大于或等于項目中任務個數的最小值，每個智能體用一個可行的任務列表表示，即列表中每個任務的所有緊前任務都必須排在這個任務的前面，循環調用算法1和算法2對智能體網格中每個智能體進行編碼；

(3)對網格L^t中每個智能體執行鄰域競爭算子，得到L^t+1/3，表示智能體L_i，j鄰域中能量最大的智能體，如果則智能體L_i，j繼續存活在網格上，否則，必須死亡，空出的格點由變異產生一個新智能體占據，變異的方法采用插入變異算子，此插入變異算子與一般組合優化的插入變異算子有所不同，變異后任務列表仍須滿足任務間優先關系；

(4)對L^t+1/3中的每個智能體，若rand＜P_c，則將鄰域交叉算子作用在其上，得到L^t+2/3，如果智能體L_i，j滿足交叉條件，則將兩點交叉算子作用在L_i，j與上，得到兩個智能體c₁和c₂，比較這兩個智能體的能量，用能量較大的一個替代L_i，j；

(5)對L^t+2/3中的每個智能體，若rand＜P_m，則將變異算子作用在其上，得到L^t+1，如果智能體L_i，j滿足變異條件，則將插入變異算子作用在其上，該變異算子與步驟(3)中變異算子相同；

(6)從L^t+1中找出CBest^t+1，并將自學習算子作用在其上，若智能體L_i，j滿足自學習條件，由L_i，j變異產生智能體h₁，變異方法與步驟(3)中變異方法相同，若energy(h₁)＞energy(L_i，j)，則用h₁替代L_i，j且自學習算子停止，否則由h₁繼續變異產生一個智能體h₂，與L_i，j比較能量，如果h₂的能量比L_i，j的大，則用h₂替代L_i，j且自學習算子停止，否則繼續由h₂變異產生一個智能體與L_i，j比較能量，按照這種方式一直變異，一旦得到一個大于L_i，j能量的智能體，則用該智能體替代L_i，j且自學習算子停止，最大變異次數為20，若還找不到一個智能體使其能量大于L_i，j的能量，則自學習算子停止，L_i，j保持不變；

(7)如果energy(CBest^t+1)＞energy(Best^t)，則把CBest^t+1的值賦予Best^t+1，否則，把Best^t的值賦予Best^t+1和CBest^t+1；

(8)如果終止條件滿足，即得到RCPSP的最優解或者達到最大進化代數，則解碼計算最小項目工期輸出，否則，令t的值自加1，并轉向步驟(3)。