基于改進(jìn)啟發(fā)式

摘要：對(duì)于流水車(chē)間的調(diào)度問(wèn)題，基于啟發(fā)式算法以及遺傳算法的特性，本文提出了一種啟發(fā)式-遺傳算法的混合智能優(yōu)化算法。其主要思想是：通過(guò)構(gòu)造流水車(chē)間的數(shù)學(xué)模型，采用palmer啟發(fā)式算法生成初始種群替代遺傳算法隨機(jī)生成的種群，然后使用兩點(diǎn)交叉的方式對(duì)新生成的染色體進(jìn)行交叉操作，接下來(lái)對(duì)染色體進(jìn)行的逆序變異，“復(fù)制、交叉、變異”后最終生成新的下一代染色體，通過(guò)保存其中性能較優(yōu)的染色體，對(duì)較優(yōu)個(gè)體繼續(xù)進(jìn)行迭代操作。本文通過(guò)對(duì)比實(shí)驗(yàn)結(jié)果，得出本文算法在一定條件下優(yōu)于遺傳算法，對(duì)流水車(chē)間的最大完工時(shí)間有著優(yōu)化效果。

關(guān)鍵詞：流水車(chē)間;遺傳算法;啟發(fā)式規(guī)則;車(chē)間調(diào)度;最小化最大完工時(shí)間

一、引言

流水車(chē)間（FSP）是經(jīng)典的NP-hard調(diào)度問(wèn)題，它是很多實(shí)際流水車(chē)間調(diào)度的簡(jiǎn)化模型，廣泛用于機(jī)械設(shè)計(jì)制造及自動(dòng)化、傳統(tǒng)紡織工藝與設(shè)備、半導(dǎo)體與晶體加工工業(yè)、冶金與化工、建筑學(xué)等領(lǐng)域。潘全科[1]在車(chē)間調(diào)度問(wèn)題研究中提出了很多流水車(chē)間的車(chē)間調(diào)度模型，劉易林[2] 提出了根據(jù)兩個(gè)隨機(jī)工件的相對(duì)位置提高性能的啟發(fā)式算法。

流水車(chē)間（FSP）問(wèn)題沿用了正常車(chē)間調(diào)度的排列編碼方法，再用各種規(guī)則解碼來(lái)獲得問(wèn)題的可行解。目前，大多數(shù)的解碼方法采取先到先加工規(guī)則，以及優(yōu)先空閑機(jī)器規(guī)則，以方便智能優(yōu)化算法的操作，用各種規(guī)則解碼后，可以快速獲得問(wèn)題的最優(yōu)解，因此相關(guān)解碼方法被廣泛推廣。喬?hào)|平[3]在論文中介紹了蟻群算法在車(chē)間調(diào)度問(wèn)題中的應(yīng)用，解決車(chē)輛路徑問(wèn)題以及在機(jī)器人路徑規(guī)劃中都有廣泛的應(yīng)用。 邵晴[4]提出了一種基于粒子群算法的自適應(yīng)結(jié)合算法，通過(guò)結(jié)合實(shí)際情況對(duì)粒子群算法進(jìn)行改進(jìn)，引入“閾值”“堆棧和指針”的概念，具體分析現(xiàn)實(shí)情況結(jié)合實(shí)際大幅提高粒子群算法在優(yōu)化算法在工程應(yīng)用中的能力。張森[5]在面對(duì)灰狼算法的全局和局部搜索問(wèn)題時(shí)，設(shè)計(jì)了正交設(shè)計(jì)算子，提高了灰狼算法的全局搜索能力，并且在后期引入了差分變異概念，提高了算法后期的局部搜索能力。但其研究及應(yīng)用仍處于起步階段，存在一定的不足之處。這為我們提供了很好的改進(jìn)思路，對(duì)其他算法的改進(jìn)提供了明確的方向。

模擬退火算法[6]提出了一種模擬算法退火回火的改進(jìn)策略，通過(guò)實(shí)驗(yàn)證明了收斂速度由于傳統(tǒng)模擬退火算法，相關(guān)研究文獻(xiàn)中設(shè)計(jì)的動(dòng)力系統(tǒng)模型完全符合模擬退火算法的需求，與此同時(shí)模擬退火算法常常與群智能優(yōu)化算法混合設(shè)計(jì)與應(yīng)用，展現(xiàn)出很好的效果。本質(zhì)上，流水車(chē)間最主要解決的問(wèn)題就是時(shí)間，即盡可能讓完成調(diào)度的時(shí)間縮短，本文實(shí)驗(yàn)的目標(biāo)是：通過(guò)相關(guān)解碼方法和算法的迭代優(yōu)化，實(shí)現(xiàn)調(diào)度目標(biāo)為最小化流水車(chē)間的最大完工時(shí)間。由于單一的啟發(fā)式算法以及單一的智能優(yōu)化算法都有各自的優(yōu)缺點(diǎn)，對(duì)此我們結(jié)合兩種算法的優(yōu)點(diǎn)，提出一種啟發(fā)式-遺傳算法的混合優(yōu)化算法來(lái)解決單一算法性能不夠的問(wèn)題。

綜上，本文主要目的是將流水車(chē)間轉(zhuǎn)換為數(shù)學(xué)模型，解決流水車(chē)間的最小化最大完工時(shí)間的問(wèn)題。在實(shí)驗(yàn)方法上，將啟發(fā)式算法和傳統(tǒng)算法的優(yōu)缺點(diǎn)相結(jié)合，提出一種混合優(yōu)化算法進(jìn)行實(shí)驗(yàn)設(shè)計(jì)，試圖通過(guò)對(duì)比實(shí)驗(yàn)來(lái)驗(yàn)證混合優(yōu)化算法強(qiáng)于單一優(yōu)化算法的相關(guān)結(jié)論。

二、問(wèn)題描述及數(shù)學(xué)建模

流水車(chē)間[7]（FSP）流程描述為：有n個(gè)作業(yè)，按照不同的工序分別通過(guò)m臺(tái)機(jī)器，則n個(gè)作業(yè)m道工序，這些作業(yè)分別通過(guò)不同臺(tái)機(jī)器，并且整個(gè)加工過(guò)程全程不停，從第一個(gè)作業(yè)加工時(shí)間開(kāi)始，到最后一個(gè)作業(yè)加工結(jié)束，并且第一臺(tái)機(jī)器開(kāi)始運(yùn)行，最后一臺(tái)機(jī)器停止運(yùn)行，加工完作業(yè)。這時(shí)算完成一次完整的生產(chǎn)任務(wù)，我們本次實(shí)驗(yàn)的目的是求得流水車(chē)間最大完工時(shí)間的最小值。在FSP問(wèn)題中，有以下約束條件：1.所有工件在零時(shí)刻都可以被加工;2.一臺(tái)機(jī)器在某一時(shí)刻只能加工一個(gè)工件;3.一個(gè)工件在某一時(shí)刻只能被一臺(tái)機(jī)器加工;4.工件的某道工序在某臺(tái)設(shè)備一旦加工開(kāi)始則無(wú)法中斷，直到該工序的加工完成;5.所有機(jī)器在零時(shí)刻均可被用。

為了可以快速完成生產(chǎn)加工任務(wù)是眾多企業(yè)的第一生產(chǎn)目標(biāo)，優(yōu)化目標(biāo)的最大完工時(shí)間是我們的實(shí)驗(yàn)任務(wù)。進(jìn)行流水車(chē)間（FSP）的數(shù)學(xué)模型如下：

Min（max（C）） （1）

Xijk=1" i=1，2，…，n; j=1，2，… ，m， （2）

Cijklt;=bi（j+1）k" "i=1，2，…，n; j=1，2，…，m， （3）

Cijkgt;bijk" "i=1，2， … ，n; j=1，2，…，m， （4）

Cijk=pijk+bijk，" i=1，2，…，n; j=1，2，…，m， （5）

Xijk=0或1 （6）

其中，式（1）表示目標(biāo)，即使得整個(gè)任務(wù)的最大完成時(shí)間最小;式（2）表示的是每個(gè)工件在一道工序上加工時(shí)只能被當(dāng)前機(jī)器加工，其他機(jī)器不可使用;式（3）～式（5）是時(shí)間約束，式（3）表示上一道作業(yè)沒(méi)有完成之前，這個(gè)作業(yè)的下一個(gè)步驟不可以開(kāi)始;式（4）表示當(dāng)前加工工序未完成時(shí)，下一個(gè)本機(jī)器的加工工序不可比前一道工序先啟動(dòng);式（5）表示每個(gè)工件的完成時(shí)間等于前一工件的完成時(shí)間加上當(dāng)前工件在當(dāng)前機(jī)器上的加工時(shí)間;式（6）為變量的取值范圍。

使用以下的符號(hào)來(lái)定義整個(gè)流程中的約束：

n：加工工件的總數(shù);

m：總的加工設(shè)備數(shù);

i：作業(yè)編號(hào)，i=1，2，…，n;

j：工序編號(hào)，j=1，2，…，m;

mj：第j階段的加工設(shè)備總數(shù);

k：每個(gè)階段的設(shè)備編號(hào)，k=1，2，…，mj;

xi，j，k：取值為1或0，為1時(shí)是i作業(yè)在j流程看上，為0時(shí)不在;

pi，j，k：第i個(gè)作業(yè)的第j道流程在k上的加工時(shí)間;

bi，j，k：第i個(gè)作業(yè)的第j道流程在k上的開(kāi)始加工時(shí)間;

ci，j，k：第i個(gè)作業(yè)的第j道流程在k上的完成加工時(shí)間;

C：所有工件的完工時(shí)間。

三、Palmer-GA算法設(shè)計(jì)

本次實(shí)驗(yàn)設(shè)計(jì)了Palmer-GA混合算法，該算法是采用palmer啟發(fā)式算法與遺傳算法的結(jié)合，提出的混合優(yōu)化算法。通過(guò)結(jié)合palmer啟發(fā)式算法的優(yōu)點(diǎn)，針對(duì)遺傳算法易早熟，易陷入局部最優(yōu)的特點(diǎn)進(jìn)行了改進(jìn)操作。

Palmer-GA的基本步驟包括：初始化→工件對(duì)應(yīng)機(jī)器的選擇→選擇操作→交叉操作→變異操作→判斷是否滿(mǎn)足輸出條件，滿(mǎn)足則終止，不滿(mǎn)足則轉(zhuǎn)回第二步操作（工件對(duì)應(yīng)機(jī)器的選擇）。詳細(xì)實(shí)驗(yàn)過(guò)程闡述如下：

（一）初始化

本文選用基于操作的編碼方法。比如，如果有8個(gè)待加工的工件的FSP車(chē)間，可以取P1=[5 8 6 7 3 4 1 2]作為一個(gè)染色體的基因串。染色體與工件和機(jī)器互相對(duì)應(yīng)，染色體從頭到尾的位置代表著機(jī)器的順序，染色體內(nèi)每個(gè)基因的值代表著工件的順序，這種方法構(gòu)造的車(chē)間模擬比較相似，并且操作簡(jiǎn)單。每次進(jìn)行遺傳變異時(shí)，只需要變更染色體內(nèi)部基因的值就可以達(dá)到我們想要改變工件在機(jī)器上的加工順序。我們通過(guò)Palmer啟發(fā)式算法的方法生成初始解，其操作步驟如下：

步驟1：先對(duì)每個(gè)工件計(jì)算參量 ;

步驟2：按照參量值遞減的順序?qū)ぜM(jìn)行排列，生成一組新解;

步驟3：將啟發(fā)式算法產(chǎn)生的初始種群與隨機(jī)生成的初始種群混合，最終生成編碼的初始種群。

本次實(shí)驗(yàn)，我們將這種策略進(jìn)行進(jìn)一步改進(jìn)，使得算法可以產(chǎn)生更多的多樣性，還可以生成較優(yōu)解。使用啟發(fā)式算法產(chǎn)生初始種群后再與隨機(jī)生成的初始種群混合，這種方法比傳統(tǒng)遺傳算法隨機(jī)生成種群的方法更科學(xué)，同時(shí)可以避免遺傳算法易陷入局部最優(yōu)，很難得到最優(yōu)解的情況。此外，我們通過(guò)這種策略方法，會(huì)比以前產(chǎn)生很多隨機(jī)解，有助于對(duì)該算法進(jìn)行更好的理解和優(yōu)化。在提高算法效率方面，本次實(shí)驗(yàn)策略使得傳統(tǒng)問(wèn)題有更好的方法去加以解決，既優(yōu)化了操作，也減少了車(chē)間的完工時(shí)間，降低了車(chē)間的消耗以及不必要的浪費(fèi)。

（二）工件對(duì)應(yīng)機(jī)器的選擇

步驟1：開(kāi)始時(shí)，所有機(jī)器初始時(shí)都為可用狀態(tài)，當(dāng)一個(gè)工件在一臺(tái)機(jī)器上開(kāi)始加工后，其他工件則不能在同一時(shí)間使用這臺(tái)機(jī)器上被加工，如果其他工件想要在這臺(tái)機(jī)器上加工，需要等待前一工件完成加工后，在該機(jī)器上進(jìn)行加工，這時(shí)需要判斷當(dāng)前工件的開(kāi)工時(shí)間是否大于前一工件的完成時(shí)間;如果當(dāng)前工件的開(kāi)工時(shí)間大于前一工件的完成時(shí)間，這時(shí)，我們判定，該工件可以在該機(jī)器上被加工，否則，則不可以。

步驟2：選擇機(jī)器，優(yōu)先選取完成時(shí)間最小的機(jī)器。

步驟3：判斷是否所有工件的所有工序都已經(jīng)進(jìn)行了機(jī)器的選擇。但所有工件的所有工序都進(jìn)行了機(jī)器選擇時(shí)，結(jié)束循環(huán)，輸出調(diào)度方案;否則，返回步驟1。

（三）選擇算子

算法選用輪盤(pán)賭法進(jìn)行染色體選擇。通過(guò)計(jì)算種群中染色體的適應(yīng)度函數(shù)，每個(gè)個(gè)體被選中的概率與數(shù)值成反比，這是為了防止某些適應(yīng)度較小的染色體串被直接忽略。

（四）交叉算子

本文采用線(xiàn)性次序交叉，首先隨機(jī)生成兩個(gè)可以交叉的點(diǎn)，再交換兩個(gè)交叉位置的內(nèi)容，通過(guò)刪除父代中相同的基因后，最后從頭至尾，填入剩余基因。這樣完成一次線(xiàn)性次序交叉。

（五）變異算子

在算法中變異算子的目的是提高算法的局部搜索能力，使算法跳出局部最優(yōu)，從而得到最優(yōu)解。本文采用逆序變異的方法，這種方法能夠?qū)υ嫉娜旧w干擾比較大，能夠很好地跳出局部最優(yōu)，可以擴(kuò)大可搜索的空間。首先隨機(jī)生成兩個(gè)將要進(jìn)行變異的點(diǎn)，再對(duì)這兩個(gè)位置中所有的染色體串進(jìn)行逆序處理，生成兩條新的染色體，其中變異概率根據(jù)具體情況來(lái)設(shè)置大小。變異操作會(huì)大大增加了種群的多樣性。例，當(dāng)一串染色體串長(zhǎng)度為9時(shí)，其染色體串的內(nèi)容為 473578169，這樣一條染色體串，我們先隨機(jī)選擇兩個(gè)位置“2和7”，標(biāo)記“2”和“7”這兩個(gè)位置的基因，同時(shí)逆序變異，這時(shí)染色體變?yōu)?1875369，產(chǎn)生一條新染色體。

（六）合并種群

當(dāng)整個(gè)流程運(yùn)行時(shí)，每次循環(huán)會(huì)出現(xiàn)一個(gè)當(dāng)代最優(yōu)值，記錄最優(yōu)解，并返回循環(huán)開(kāi)頭，判斷循環(huán)條件，如果循環(huán)結(jié)束，則當(dāng)前的最優(yōu)解為本次算法運(yùn)行的在最終解，此時(shí)輸出結(jié)果，結(jié)束循環(huán)。否則，繼續(xù)循環(huán)，當(dāng)再出現(xiàn)當(dāng)代最優(yōu)值時(shí)，與之前的最優(yōu)值進(jìn)行比較，如果當(dāng)代最優(yōu)值比之前的最優(yōu)值小，則替換之前的最優(yōu)值。繼續(xù)循環(huán)，直到訓(xùn)話(huà)結(jié)束。

四、仿真實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境：本文采用matlab軟件進(jìn)行仿真模擬實(shí)驗(yàn)，版本為2020b。采用對(duì)比實(shí)驗(yàn)的方法，將本文提出算法與GA算法進(jìn)行對(duì)比，兩種算法都采用相同的迭代次數(shù)200次，種群規(guī)模為80，交叉概率0.4，變異概率0.05，對(duì)Carlier提出的算例和C.R.Reeves提出的11個(gè)算例進(jìn)行測(cè)試每個(gè)算例單獨(dú)運(yùn)行40次。因?yàn)檫z傳算法是隨機(jī)搜索算法，每次運(yùn)行時(shí)得到的結(jié)果都有所不同，我們?yōu)榱烁鼫?zhǔn)確地結(jié)果和更好的性能，我們?cè)O(shè)定判斷標(biāo)準(zhǔn)，設(shè)P為某一實(shí)驗(yàn)算例在40次內(nèi)求得的最優(yōu)值，Q為某一實(shí)驗(yàn)算例在40次循環(huán)的平均值，F(xiàn)為平均相對(duì)誤差值。F=（Q-P）/P×100。

從表1可以看出，本文算法比遺傳算法在car01， car02， car03， car06，rec11，rec15中對(duì)比平均誤差值要小，意味著本文算法比遺傳算法在一些算例中有提高。

五、結(jié)束語(yǔ)

在本文中，我們提出了P-GA算法改進(jìn)遺傳算法去解決流水車(chē)間的調(diào)度問(wèn)題。通過(guò)對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文算法在一些算例中相比遺傳算法在調(diào)度問(wèn)題的上性能有明顯的提高。通過(guò)本文的研究，我們發(fā)現(xiàn)啟發(fā)式結(jié)合智能優(yōu)化算法比單一啟發(fā)式算法和單一智能優(yōu)化算法求解能力都要優(yōu)秀，使用混合智能優(yōu)化算法來(lái)解決流水車(chē)間調(diào)度問(wèn)題是未來(lái)算法發(fā)展的重要方向。

由于設(shè)計(jì)思路和實(shí)驗(yàn)環(huán)境的局限性，本次實(shí)驗(yàn)仍存在一些不足，需要啟發(fā)式算法與其他算法進(jìn)行更多維度的混合優(yōu)化，來(lái)進(jìn)一步提高實(shí)驗(yàn)效率和效果顯著性。

作者單位：李晨" "吉桐萱" " 大連交通大學(xué)軟件學(xué)院

參" 考" 文" 獻(xiàn)

[1]潘全科.車(chē)間調(diào)度問(wèn)題研究[J].聊城大學(xué)學(xué)報(bào)（自然科學(xué)版），2004.03，17（1）：10.

[2]劉易麟. 流水車(chē)間調(diào)度問(wèn)題的一種啟發(fā)式算法[J]. 信息工程期刊：中英文版， 2014， 4（6）：6.

[3]喬?hào)|平. 蟻群算法及其應(yīng)用綜述[J].軟件導(dǎo)刊，2017，12.

[4]邵晴. 粒子群算法研究及其工程應(yīng)用案例[D].長(zhǎng)春：吉林大學(xué)，2017.

[5]張森 灰狼優(yōu)化算法及其應(yīng)用 [D].廣西民族大學(xué)，2017.

[6]李元香，項(xiàng)正龍，夏界寧.模擬退火算法的動(dòng)力系統(tǒng)模型及收斂性分析[J].計(jì)算機(jī)學(xué)報(bào)，2018-11.

[7]熊學(xué). 基于遺傳算法的排課問(wèn)題研究[D].西南交通大學(xué)，2008.