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

在審

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

所屬領(lǐng)域

本發(fā)明涉及作業(yè)車(chē)間調(diào)度領(lǐng)域，具體地涉及用算法求解作業(yè)車(chē)間調(diào)度問(wèn)題。

背景技術(shù)

作業(yè)車(chē)間調(diào)度問(wèn)題(Job-Shop Scheduling Problem，JSP)是制造執(zhí)行系統(tǒng)研究的核心和重點(diǎn)之一，它的研究不僅具有重大的現(xiàn)實(shí)意義，而且具有深遠(yuǎn)的理論意義。JSP就是根據(jù)產(chǎn)品制造需求合理分配資源，進(jìn)而達(dá)到合理利用產(chǎn)品制造資源、提高企業(yè)經(jīng)濟(jì)效益的目的。JSP是產(chǎn)品制造行業(yè)中共存的問(wèn)題，它與計(jì)算機(jī)集成制造系統(tǒng)(Computer Integrated Manufacturing Systems，CIMS)的工廠管理、產(chǎn)品制造層次緊密相關(guān)，是CIMS領(lǐng)域中研究的重要課題。JSP是一個(gè)典型的NP-hard問(wèn)題,它的研究必然會(huì)對(duì)NP問(wèn)題的研究起到有意義的影響。

在過(guò)去的幾十年，各種算法被應(yīng)用來(lái)解決作業(yè)車(chē)間調(diào)度問(wèn)題。傳統(tǒng)的，一般都采用最優(yōu)化方法和近似方法來(lái)解決作業(yè)車(chē)間調(diào)度方案的自動(dòng)生成問(wèn)題。最優(yōu)化方法包括枚舉法和數(shù)學(xué)規(guī)劃技術(shù)。近似法通常使用分支定界法、優(yōu)先規(guī)則、啟發(fā)式方法、迭代局部搜索算法和進(jìn)化算法。

粒子群算法(PSO)是一種智能算法，該算法最初是受到鳥(niǎo)群活動(dòng)規(guī)律的啟發(fā)，利用群體對(duì)個(gè)體信息的共享使整個(gè)群體的運(yùn)動(dòng)在問(wèn)題求解空間中產(chǎn)生從無(wú)序到有序的演化過(guò)程，從而獲得最優(yōu)解。但是，粒子群算法對(duì)離散的優(yōu)化問(wèn)題處理不佳，且容易陷入局部最優(yōu)。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)中存在的上述不足，本發(fā)明要解決的技術(shù)問(wèn)題是提供一種基于均值偏移算法和禁忌搜索算法的改進(jìn)粒子群算法。

本發(fā)明的目的則是克服現(xiàn)有技術(shù)中存在的：粒子群算法容易陷入局部最優(yōu)；粒子群算法僅對(duì)當(dāng)前粒子群信息進(jìn)行處理，沒(méi)有處理一些粒子信息變動(dòng)的異常情況；粒子群算法僅對(duì)當(dāng)前最優(yōu)解進(jìn)行擾動(dòng)，縮小了搜索范圍的問(wèn)題。

本發(fā)明為實(shí)現(xiàn)上述目的所采用的技術(shù)方案是：一種改進(jìn)的粒子群算法求解作業(yè)車(chē)間調(diào)度問(wèn)題，該算法的步驟如下：

步驟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，直到滿(mǎn)足退出條件。

步驟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)前解，而無(wú)視它與當(dāng)前解的優(yōu)劣，同時(shí)將解的響應(yīng)特性加入禁忌表中，同時(shí)修改禁忌表；

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

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

本發(fā)明的有益效果是：

1.利用加權(quán)值的方式設(shè)置粒子優(yōu)先級(jí)，避免了隨機(jī)產(chǎn)生初始解帶來(lái)的不確定性推理，減少盲目搜索時(shí)間。

2.對(duì)均值偏移算法做一點(diǎn)改進(jìn)，然后利用一種改進(jìn)的均值偏移算法對(duì)粒子位置信息預(yù)測(cè)，降低了部分異常變動(dòng)粒子對(duì)整個(gè)算法的干擾。

3.增加禁忌搜索算法避免搜索陷入局部最優(yōu)；

附圖說(shuō)明