[發明專利]基于變鄰域搜索和引力搜索混合算法的調度方法及系統

在審

• 申請號: 201710824708.2
• 申請日: 2017-09-11
• 公開（公告）號: CN107578178A
• 公開（公告）日: 2018-01-12
• 發明（設計）人: 裴軍;范雯娟;劉心報;張強;孔敏;陸少軍
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04
• 代理公司: 北京路浩知識產權代理有限公司11002
• 代理人: 王瑩,余罡

1.一種基于變鄰域搜索和引力搜索混合算法的調度方法，其特征在于，包括：

S1、初始化算法的輸入參數，包括工件數量n，工件基本加工時間p_i，學習因子a，啟動時間的線性因子θ，加工機器的容量C；

S2、設定改進VNS算法的執行參數，VNS算法部分包括初始解X_s，最大迭代次數I_max，最小鄰域結構索引值o_min，當前鄰域結構索引值o，最大鄰域結構索引值o_max；局部搜索算法部分包括最大迭代次數it_max，當前迭代次數it＝1，局部搜索算法種群規模Q；此外，全局最優解X_best＝X_s；

S3、設置o＝o_min；

S4、在當前全局最優解X_best的第o個鄰域中隨機選擇Q個個體，用以初始化基于局部搜索算法局部搜索中的種群個體集合S；

S5、執行局部搜索算法獲得局部近似最優解X'；

S6、判斷若X'優于當前全局最優解X_best，則將X'賦給X_best，并轉到步驟S3；否則將o+1賦給o，并判斷o是否不大于o_max，若成立則轉到步驟S4，否則轉到步驟S7；

S7、將I+1賦值給I，判斷I≤I_max是否成立，若成立則執行步驟S3，否則結束算法，輸出當前全局最優解；

所述步驟S4中的在當前全局最優解X_best的第o個鄰域中隨機選擇Q個個體步驟之前，所述方法還包括：設定鄰域結構；

其中，所述設定鄰域結構，包括：

步驟S1’：定義變量x，y，g＝1，獲得輸入的初始解X，變量o；

步驟S2’：隨機產生兩個在區間[1，n]范圍內的整數，賦值給變量x，y；

步驟S3’：選擇X中的第x個和第y個元素，將這兩個元素進行交換，得到新的解X'；

步驟S4’：令g＝g+1，判斷g≤o是否成立，若成立，則返回步驟S2’；否則，執行步驟S5’；

步驟S5’：計算適應度值，判斷解X'是否優于初始解X，若是，則輸出解X'；否則，輸出解解X。

2.根據權利要求1所述的方法，其特征在于，步驟S5中執行局部搜索算法獲得局部近似最優解X'，包括：

步驟S51：在當前全局最優解的某一鄰域隨機選擇Q個解，作為基于GSA局部搜索算法的初始解；其中，局部搜索算法的第it代種群中的第j個個體定義為1≤it≤it_max，j＝1,2,...,Q，d＝1,2,...,n，其中表示第it代種群中的第j個個體在第d維上的位置；令it＝1；

步驟S52：計算第it代種群中每個個體的適應度值，其中j個個體的適應度值記為fit_j(it)；

步驟S53：更新第it代種群的最差worst(it)和最優個體best(it)；

步驟S54：按照以下公式計算當前種群每個個體的質量；其中M_j(it)表示當前種群的第j個個體的質量；

步驟S55：按照以下公式計算當前種群每個個體的每一維上的加速度；其中，第j個個體第d維的加速度記為

步驟S56：按照以下公式更新當前種群每個個體的每一維上的位置和速度；第j個個體的第d維的速度記為

步驟S57：判斷it≤it_max是否成立，若成立，則令it＝it+1，并轉到步驟S52，否則結束算法，輸出局部最優近似解。