[發明專利]基于自適應蟻群優化的彈性車間調度技術

無效

• 申請號: 201310171884.2
• 申請日: 2013-04-25
• 公開（公告）號: CN103246938A
• 公開（公告）日: 2013-08-14
• 發明（設計）人: 張軍;林盈;張宇輝
• 申請（專利權）人: 中山大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于自適應蟻群優化的彈性車間調度技術，其特征在于，該方法包括以下步驟：

(1)建立解構造圖：解構造圖是一個有向連通圖，圖中每個結點表示一個操作到一臺機器可行分配，此外，圖中還有兩個虛擬結點v₀和v_T+1，分別表示螞蟻路徑的起點和終點，T表示所有可行分配的數目，除了v₀和v_T+1，每個結點v_l(1≤l≤T)分別記錄了其各自相應的作業、操作和機器的索引，所有結點通過有向弧相互連接，弧的指向滿足操作間的順序約束；

(2)初始化：初始化解構造圖上信息素分布，同時為蟻群中的每只螞蟻a初始化一個啟發式信息檔案P^(a)，P^(a)中包含該螞蟻對啟發式信息的定義及其引導力控制參數的選擇；

(3)解構造：每只螞蟻根據自身的啟發式信息檔案P^(a)構造一個彈性車間調度方案S^(a)，S^(a)由M個序列組成，每個序列S_k記錄了那些將操作分配給機器k的結點，k＝1，2，...，M，解構造過程中維護一個候選結點列表C，螞蟻每次從C中按規則選擇一個結點，并將其插入方案S^(a)中相應序列的相應位置，之后更新C中的結點，當C為空時，說明一個完整的解構造完畢；

(4)信息素更新：螞蟻每選擇一個結點，便根據局部信息素更新規則對相應的有向弧進行一次信息素更新，當所有螞蟻完成解構造過程后，再根據全局信息素更新規則對信息素進行更新；

(5)啟發式信息檔案更新：每隔G次迭代進行一次啟發式信息檔案的更新，兩次更新間隔期間，每只螞蟻構造的調度方案的工期將與該螞蟻的啟發式信息檔案共同保存到一個外部檔案A，自適應策略選擇A中工期最短的λ％個元素的啟發式信息檔案進行統計，然后根據統計量對每只螞蟻a的啟發式信息檔案進行更新；

(6)結束條件檢查：當算法對螞蟻所構造的解的評估次數達到預先設定的最大次數時，終止算法。

2.基于權利要求1所述的一種基于自適應蟻群優化的彈性車間調度技術，其特征在于，引入了一種啟發式信息的自適應設計策略來自動調整蟻群的啟發式信息定義及其引導力控制參數，具體方法為：為每只螞蟻維護一個啟發式信息檔案P^(a)，P^(a)包括啟發式信息的定義h^(a)和啟發式信息的引導力控制參數q₀及β，算法初始化時，隨機產生每只螞蟻的啟發式信息檔案，h^(a)的每個元素將在{0，1}間隨機產生，和β^(a)的值將在對應參數的預定義取值域[q_min，q_max]和[β_min，β_max]中產生，算法每隔G次迭代進行一次啟發式信息檔案的調整，兩次調整間隔期間，螞蟻的啟發式信息檔案保持不變，并且每只螞蟻構造的調度方案的工期將與該螞蟻的啟發式信息檔案共同保存到一個外部檔案A，自適應策略選擇A中工期最短的λ％個元素的啟發式信息檔案進行統計，并根據統計量對每只螞蟻a的啟發式信息檔案進行如下調整：

hi(a)=1,if r≤0.9×Σp(k)Rhi(k)/(|R|+1)0,otherwise,i=1,2,...,6---(1)]]>

q0(a)=Cauchy(μq0,σq0)---(2)]]>

β^(a)＝Cauchy(μ_β，σ_β)?????(3)

其中，r是一個(0，1)間的標準化隨機數，R表示A中工期最短的λ％個元素的子集，Cauchy表示柯西分布的密度函數，和表示參數q₀在R中取值的平均值和標準差，μ_β和σ_β則表示參數β在R中取值的平均值和標準差，每次調整結束后，清空外部檔案A為下一次調整作準備。