[發(fā)明專利]一種改進(jìn)的粒子群算法求解作業(yè)車間調(diào)度問題

在審

• 申請(qǐng)?zhí)枺?/td>: 201610116651.6
• 申請(qǐng)日: 2016-03-02
• 公開（公告）號(hào): CN106610655A
• 公開（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: 姜艾佳;胡成華
• 申請(qǐng)（專利權(quán)）人: 四川用聯(lián)信息技術(shù)有限公司
• 主分類號(hào): G05B19/418
• 分類號(hào): G05B19/418
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種改進(jìn)的粒子群算法求解作業(yè)車間調(diào)度問題，本發(fā)明涉及作業(yè)車間調(diào)度領(lǐng)域，具體地涉及用算法求解作業(yè)車間調(diào)度問題，其特征在于：該算法的具體步驟如下：

步驟1：初始化算法參數(shù)：包括PSO粒子的數(shù)目、位置和速度等信息；

步驟2：獲得初始最優(yōu)解：采用加權(quán)法平均法設(shè)置初始粒子的優(yōu)先級(jí)，得到初始最優(yōu)解：

步驟2.1：給每個(gè)粒子編號(hào)；

步驟2.2：統(tǒng)計(jì)所有粒子的速度的和，用每個(gè)粒子的速度除速度和，得到每個(gè)粒子的優(yōu)先權(quán)值；

步驟2.3：按照優(yōu)先權(quán)大小決定粒子的先后順序，優(yōu)先權(quán)值大的工件優(yōu)先執(zhí)行；

步驟3：獲得傳統(tǒng)當(dāng)前最優(yōu)解：用粒子群算法更新粒子信息，得到當(dāng)前傳統(tǒng)粒子群算法當(dāng)前最優(yōu)解；

步驟4：預(yù)測(cè)當(dāng)前最優(yōu)解：加入一種改進(jìn)的均值偏移算法，用均值偏移算法在初始最優(yōu)解的基礎(chǔ)上對(duì)每個(gè)粒子的位置和整體位置進(jìn)行預(yù)測(cè)：

步驟4.1：初始化粒子位置信息；

步驟4.2：確定當(dāng)前粒子群中心；

步驟4.3：計(jì)算粒子群權(quán)值矩陣；

步驟4.4：計(jì)算粒子權(quán)值；

步驟4.5：用高低點(diǎn)法預(yù)測(cè)下一步粒子的位置和速度；

步驟4.6：計(jì)算相似函數(shù)；

步驟4.7：計(jì)算均值偏移向量，由均值偏移向量確定粒子群最優(yōu)預(yù)測(cè)位置和速度；

步驟4.8：循環(huán)執(zhí)行步驟4.2到步驟4.7，直到滿足退出條件；

步驟5：初選當(dāng)前最優(yōu)解：用粒子群算法的評(píng)判標(biāo)準(zhǔn)，將預(yù)測(cè)的最優(yōu)位置和速度與群體以往最好位置和速度做比較，將更好的位置信息作為當(dāng)前最好的位置信息；

步驟6：確定當(dāng)前最優(yōu)解：執(zhí)行禁忌搜索算法，找到當(dāng)前最優(yōu)解：

步驟6.1：給定一個(gè)當(dāng)前解和一種領(lǐng)域結(jié)構(gòu)，然后在當(dāng)前領(lǐng)域結(jié)構(gòu)內(nèi)確定若干候選解；

步驟6.2：若其最佳候選解對(duì)應(yīng)的目標(biāo)函數(shù)優(yōu)于已保留的最好解，則忽視其禁忌特性，用其代表當(dāng)前解和最好解，并將相應(yīng)的特性加入到禁忌表中，同時(shí)對(duì)禁忌表進(jìn)行修改；

步驟6.3：若不存在上述候選解，則在候選解中選擇非禁忌的最好解作為新的當(dāng)前解，而無視它與當(dāng)前解的優(yōu)劣，同時(shí)將解的響應(yīng)特性加入禁忌表中，同時(shí)修改禁忌表；

步驟6.4：循環(huán)步驟6.1到6.3，直到滿足停止準(zhǔn)則；

步驟7：循環(huán)執(zhí)行步驟2到步驟6，直到達(dá)到停止條件。

2.根據(jù)權(quán)利要求1所述的一種改進(jìn)的粒子群算法求解作業(yè)車間調(diào)度問題，其特征在于：所述步驟2采用加權(quán)法平均法設(shè)置初始粒子的優(yōu)先級(jí)，得到初始最優(yōu)解，其加權(quán)平均法模型如下：

（1）給每個(gè)粒子隨機(jī)編號(hào)；

（2）計(jì)算粒子初始解的優(yōu)先級(jí)： ；

（3）獲得初始最優(yōu)解：按照優(yōu)先級(jí)大小進(jìn)行排序,然后按排好序的序列先后順序執(zhí)行作業(yè)。

3.根據(jù)權(quán)利要求1所述的一種改進(jìn)的粒子群算法求解作業(yè)車間調(diào)度問題，其特征在于：所述步驟5將預(yù)測(cè)的最優(yōu)位置和速度與群體以往最好位置和速度做比較，將更好的位置信息作為當(dāng)前最好的位置信息，具體表述為：如果預(yù)測(cè)的最優(yōu)解比原來的最優(yōu)解更好，則把預(yù)測(cè)的最優(yōu)解當(dāng)作最優(yōu)解；否則，最優(yōu)解不變。

4.根據(jù)權(quán)利要求1所述的一種改進(jìn)的粒子群算法求解作業(yè)車間調(diào)度問題，其特征在于：所述步驟4改進(jìn)的均值偏移算法，其各步驟的具體計(jì)算方式如下：

（1）粒子的速度記為=（），粒子的位置記為 =（），預(yù)測(cè)局部最佳位置和預(yù)測(cè)全局最佳位置分別記為（ ）和（）；

（2）確定當(dāng)前中心粒子：規(guī)定速度最密點(diǎn)為速度中心粒子，位置最密點(diǎn)為位置中心粒子，速度中心和位置中心分別記為 ；

（3）計(jì)算權(quán)值矩陣：通過迭代的方式計(jì)算每個(gè)粒子到中心點(diǎn)的距離

則權(quán)值函數(shù) ，其中， , 為時(shí)間期限，

歸一化系數(shù)；

（4）計(jì)算粒子權(quán)值：粒子權(quán)值直方圖是為了統(tǒng)計(jì)每個(gè)粒子點(diǎn)占的權(quán)重，具體計(jì)算過程如下：首先將車間生產(chǎn)調(diào)度空間抽象為RGB顏色空間，將RGB顏色空間量化為的區(qū)間bins，然后通過式子 計(jì)算每個(gè)粒子紅色、綠色、藍(lán)色分量所占比重，再次由式子 計(jì)算直方圖統(tǒng)計(jì)中粒子總的權(quán)重，最后將權(quán)重值歸一化既可以得到目標(biāo)權(quán)值；

（5）利用高低點(diǎn)法來預(yù)測(cè)粒子速度和位置的走向：計(jì)算公式為：

其中，b代表上一次迭代得到的位置信息參數(shù)依一定比率位置信息參數(shù)變動(dòng)的部分，即：

（6）用上述（2）的方法確定預(yù)測(cè)粒子群中心點(diǎn)；

（7）計(jì)算相似函數(shù)值：本發(fā)明使用hattachyarya系數(shù)作為相似性函數(shù)，其定義為：

它的值在0—1之間，兩個(gè)模型的相似度跟的值成正比，即的值越大，表示兩個(gè)模型越相似,在JSP中則表示預(yù)測(cè)值與實(shí)際值越相近；

（8）均值偏移向量的計(jì)算：目標(biāo)定位，就是尋找使得相似度函數(shù)值達(dá)到最大的點(diǎn)，從這前一幀的中心位置 開始尋找最優(yōu)匹配的目標(biāo)：

相似度函數(shù)為：

其中，令；

由此，可以得到：

是目標(biāo)中心從起始點(diǎn) 向v移動(dòng)的向量；

（9）比較由高低點(diǎn)法和均值偏移向量預(yù)測(cè)出來的值，將更好的那組值作

為最優(yōu)預(yù)測(cè)值。