怎樣進(jìn)行作業(yè)車間調(diào)度JSP與遺傳算法GA及其Python/Java/C++實(shí)現(xiàn)

隨著遺傳算法（genetic algorithm (GA)）在組合優(yōu)化問題的廣泛應(yīng)用，許多人開始對(duì)遺傳算法進(jìn)行深度研究。已有研究結(jié)果表明，遺傳算法對(duì)求解作業(yè)車間調(diào)度問題具有較好的效果，因此系統(tǒng)采用遺傳算法來解該問題，遺傳算法是計(jì)算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。系統(tǒng)通過模擬生物進(jìn)化，包括遺傳、突變、選擇等，來不斷地產(chǎn)生新個(gè)體，并在算法終止時(shí)求得最優(yōu)個(gè)體，即最優(yōu)解。

遺傳算法解決作業(yè)車間調(diào)度問題基本步驟：

1.初始化一定數(shù)量的種群（染色體編碼）

2.計(jì)算個(gè)體適應(yīng)度（染色體解碼）

3.采用錦標(biāo)賽法選擇染色體并交叉產(chǎn)生新個(gè)體

4.個(gè)體（染色體）變異

5.達(dá)到遺傳代數(shù)終止算法并從中選取適應(yīng)度最優(yōu)的個(gè)體作為作業(yè)車間調(diào)度問題的解

流程圖如下：

遺傳算法所需參數(shù)：

1.種群規(guī)模：種群中個(gè)體的數(shù)量，用populationNumber表示

2.染色體長(zhǎng)度：個(gè)體的染色體的長(zhǎng)度，用chromosomeSize表示

3.交叉概率：控制交叉算子的使用頻率，用crossProbability表示，并且值為0.95

4.變異概率：控制變異算子的使用頻率，用mutationProbability表示，并且值為0.05

5.遺傳代數(shù)：種群的遺傳代數(shù)，用于控制遺傳算法的終止，用times來表示

遺傳算法實(shí)現(xiàn)基本步驟及偽代碼：

1. 編碼及初始化種群

       采用工序?qū)崝?shù)編碼來表示染色體，即M臺(tái)機(jī)器，N個(gè)工件，每個(gè)工件的工序數(shù)為process_i，則染色體長(zhǎng)度為chromosome=process_1+process_2+...，對(duì)染色體編碼如下：

chromosome=...,w_i,w_j,w_k,...

其中w_i代表第i個(gè)工件編號(hào)，而出現(xiàn)的次數(shù)代表該工件的第幾道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2}，中0，1，2表示工件的編號(hào)，第幾次出現(xiàn)就代表第幾道工序。然后將每一次隨機(jī)生成的染色體個(gè)體加入到種群集合中。

算法偽代碼：

2. 解碼及計(jì)算適應(yīng)度

       將優(yōu)化目標(biāo)定義為總加工時(shí)間最短，因此適應(yīng)度定義為最短加工時(shí)間的倒數(shù)，設(shè)fitness為對(duì)應(yīng)個(gè)體的適應(yīng)度，fulfillTime為最短加工時(shí)間，因此                                                       

其中fulfillTime的計(jì)算方法如下：

首先定義如下變量

然后從左到右遍歷個(gè)體的染色體序列，其中表示第i個(gè)工件的編號(hào)，則對(duì)應(yīng)的當(dāng)前工序?yàn)?設(shè)為p。當(dāng)前工件當(dāng)前工序所使用的機(jī)器編號(hào)為，設(shè)為m。當(dāng)前工件當(dāng)前工序?qū)?yīng)的加工時(shí)間為，設(shè)為t。則工件的第p道工序的最晚開始時(shí)間為          

而第m臺(tái)機(jī)器的加工時(shí)間為                                   

工件的第p道工序的結(jié)束時(shí)間為

最后加工完所有工件的最短加工時(shí)間fulfillTime為

從而計(jì)算出適應(yīng)度fitness。

PS.小編覺得解碼的過程類似動(dòng)態(tài)規(guī)劃。

偽代碼如下：

3. 個(gè)體選擇算子

個(gè)體的選擇使用錦標(biāo)賽法，其基本策略為從整個(gè)種群中隨機(jī)抽取n個(gè)個(gè)體讓它們競(jìng)爭(zhēng)，選取其中最優(yōu)的個(gè)體。該算子的選擇過程如下

偽代碼如下：

4. 染色體交叉算子

使用Order Crossover(OX)交叉算子，該算子的交叉步驟如下：

對(duì)于一對(duì)染色體g1, g2，首先隨機(jī)產(chǎn)生一個(gè)起始位置start和終止位置end，并由從g1的染色體序列從start到end的序列中產(chǎn)生一個(gè)子代原型

 將g2中不包含在child prototype的其余編碼加入到child prototype兩側(cè)

上述步驟將產(chǎn)生一個(gè)child，交換g1, g2即可產(chǎn)生另一個(gè)child

偽代碼如下：

5. 染色體變異算子

變異的作用主要是使算法能跳出局部最優(yōu)解，因此不同的變異方式對(duì)算法能否求得全局最優(yōu)解有很大的影響。使用位置變異法作為變異算子，即從染色體中隨機(jī)產(chǎn)生兩個(gè)位置并交換這兩個(gè)位置的值

偽代碼如下：

6. 算法整體偽代碼如下：