[發明專利]基于混合粒子群算法的AGV優化調度方法

有效

• 申請號: 201410577414.0
• 申請日: 2014-10-24
• 公開（公告）號: CN104408589B
• 公開（公告）日: 2018-03-06
• 發明（設計）人: 楊瑋;李國棟;李程;曹薇;高賀云;楊超群
• 申請（專利權）人: 陜西科技大學
• 主分類號: G06F17/00
• 分類號: G06F17/00
• 代理公司: 西安通大專利代理有限責任公司61200
• 代理人: 蔡和平

1.一種基于混合粒子群算法的AGV優化調度方法，其特征在于：包括以下步驟：

步驟1：將上/下包臺、入/出庫臺及AGV定為調度對象，并以AGV完成輸送任務所花費的工作時間最小作為優化調度的目標構造AGV調度優化問題數學模型；

步驟2：以基于調度對象的三維矩陣對粒子位置進行編碼，并運用基于遺傳算法、模擬退火算法及蟻群算法的混合粒子群算法對AGV調度優化問題數學模型進行求解，得到給定任務量下AGV的最優調度方案；

所述步驟2具體包括以下步驟：

1)種群初始化

首先，設定粒子種群大小N、最大迭代數t_max、學習因子以及粒子速度VA的最大值和最小值；

然后，對種群中粒子進行初始化：

位置初始化：XA＝unifrnd(Q_i，S_i，S'_i)^T；

速度初始化：VA＝unifrnd(v_i，v_i，v_i)^T；

Q_i表示隨機選擇的AGV的編號，S_i表示隨機選擇的入/出庫臺的編號，S'_i表示隨機選擇的上/下包臺的編號，Q_i∈Q，S_i∈S，S'_i∈S'，v_i表示速度的隨機數，i＝1,2,...,N；

2)以T_k＝d_ik-r_ik+P_k×s_k×t_ijk+d_jk-r_jk+P_k×s_k×t_ijk為適應度函數，根據適應度函數計算種群中粒子的適應度值fit1；T_k表示第k輛AGV的工作時間，d_ik表示第k輛AGV離開第i個入/出庫臺的時間，r_ik表示第k輛AGV到達第i個入/出庫臺的時間，d_jk表示第k輛AGV離開第j個上/下包臺的時間，r_jk表示第k輛AGV到達第j個上/下包臺的時間，Q表示AGV的編號集合，S表示入/出庫臺的編號集合，S'表示上/下包臺的編號集合，t_ijk表示第k輛AGV從第i個入/出庫臺到第j個上/下包臺的時間；

3)根據適應度值fit1從種群中選擇出個體極值P_best以及全局極值P_gbest，記錄個體極值位置P_cbest以及全局極值位置P_cgbest；

4)經過步驟3)后，進入迭代循環，當迭代次數小于t_max時，執行如下循環操作：

(a)將粒子的第j個粒子位置x₁(j)與全局極值位置P_cgbest作交叉得到x₁'(j)，交叉公式為：x₁'(j)＝x₁(j)+ω(t)*p_cgbest；ω(t)為慣性因子；j＝1,2,...,D，D是尋優空間維度；

(b)將x₁'(j)與個體極值位置P_cbest再作交叉得到x₁”(j)，交叉公式為x₁”(j)＝x₁'(j)+ω(t)*p_cbest；

(c)對x₁”(j)進行變異操作得到x₂(j)，變異公式為x₂(j)＝[0.5+rand()]*x₁”(j)；rand()表示0～1之間的隨機數；

(d)經過步驟(c)后，計算每個粒子當前的適應度值fit2；

(e)計算每個粒子在兩個粒子位置x₂(j)和x₁(j)的適應度值的變化ΔE，ΔE＝fit2-fit1，若ΔE<e，則將粒子位置更新為x₂(j)，否則不更新粒子位置，粒子的位置仍為x₁(j)，e為允許目標函數變差的范圍；

(f)經過步驟(e)后，對個體極值與個體極值位置作更新；

(g)經過步驟(f)后，找出并記錄新的全局極值和全局極值位置；

(h)經過步驟(g)后，對所有粒子的速度與位置按照以下公式進行更新，得到下一代粒子，轉至步驟(a)，進入下一次循環：

vidt+1=ω(t)vidt+c1r1(pit-xidt)+c2r2(pgt-xidt)]]>

xidt+1=xidt+vidt+1]]>

式中，d＝1,2,...,D，D是尋優空間維度；i＝1,2,...,N；t為迭代代數；c₁、c₂為學習因子；r₁和r₂取值為在(0，1)上均勻分布的隨機數；P_i表示經過步驟(f)更新后的個體極值位置，P_g表示經過步驟(g)得到的全局極值位置，x表示粒子的位置，v表示粒子的速度；

5)當迭代代數等于t_max時，迭代停止，并輸出最終的全局極值以及全局極值位置。