[發(fā)明專利]一種基于改進(jìn)混合遺傳算法的作業(yè)車間調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202110036257.2
• 申請(qǐng)日: 2021-01-12
• 公開（公告）號(hào): CN112749776B
• 公開（公告）日: 2023-08-15
• 發(fā)明（設(shè)計(jì)）人: 王玉芳;繆昇;葛嘉榮
• 申請(qǐng)（專利權(quán)）人: 南京信息工程大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/06;G06Q50/04
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 田凌濤

1.一種基于改進(jìn)混合遺傳算法的作業(yè)車間調(diào)度方法，其特征在于，包括以下步驟：

步驟1、建立作業(yè)車間調(diào)度模型；

步驟2、確定調(diào)度的約束條件；

步驟3、初始化種群以及設(shè)置參數(shù)；

步驟4、計(jì)算適應(yīng)度值；

步驟5、個(gè)體進(jìn)行輪盤賭選擇法；

步驟6、個(gè)體進(jìn)行IPOX交叉，交叉概率采用自適應(yīng)公式進(jìn)行調(diào)整；調(diào)整公式為：

式中：f_min為種群中最小的目標(biāo)函數(shù)值；f’為被選擇的兩個(gè)父代個(gè)體中較小的目標(biāo)函數(shù)值；f_avg為種群的平均目標(biāo)函數(shù)值；gen為當(dāng)前迭代次數(shù)；k₁為調(diào)整參數(shù)，取值范圍為(0，1)；

步驟7、個(gè)體進(jìn)行隨機(jī)變異，變異概率采用自適應(yīng)公式進(jìn)行調(diào)整；調(diào)整公式為：

式中：f_min為種群中最小的目標(biāo)函數(shù)值；f為當(dāng)前被選擇的個(gè)體目標(biāo)函數(shù)值；f_avg為種群的平均目標(biāo)函數(shù)值；gen為當(dāng)前迭代次數(shù)；k₂為調(diào)整參數(shù)，取值范圍為(0，1)；

步驟8、個(gè)體進(jìn)行模擬退火操作，具體包含如下步驟：

步驟8.1、從經(jīng)變異操作生成的種群中挑選適應(yīng)度最高的個(gè)體作為初始解v，令當(dāng)前狀態(tài)S＝v；

步驟8.2、設(shè)置S為當(dāng)前狀態(tài)，循環(huán)計(jì)數(shù)器d＝1，種群計(jì)數(shù)器0＝1，Markov鏈長(zhǎng)L；

步驟8.3、從種群中隨機(jī)選擇一個(gè)個(gè)體，與狀態(tài)S進(jìn)行SWAP操作，產(chǎn)生新狀態(tài)S’＝v’，計(jì)算增量dE＝f(v’)-f(v)；

步驟8.4、如果dE＜0，則接受S’作為當(dāng)前狀態(tài)；如果dE＞0，則以概率exp(-dE/T_K)接受S’作為當(dāng)前解；

步驟8.5、對(duì)當(dāng)前狀態(tài)S’進(jìn)行局部基因段倒序操作得到新狀態(tài)S”＝v”，計(jì)算其適應(yīng)度；如果f(v”)＞f(v’)，則接受S”作為當(dāng)前狀態(tài)，令S＝S”；否則，保持S’作為當(dāng)前狀態(tài)，令S＝S’，保存當(dāng)前狀態(tài)，d＝d+1，轉(zhuǎn)步驟3；

步驟8.6、判斷d＞L是否為真，若是，終止內(nèi)循環(huán)；

步驟8.7、對(duì)內(nèi)循環(huán)生成的L個(gè)個(gè)體進(jìn)行適應(yīng)度排序，選擇其中最高的個(gè)體進(jìn)入新種群并作為下一個(gè)溫度迭代的初始解，0＝0+1；

步驟8.8、利用降溫公式計(jì)算下一次迭代的溫度，計(jì)算溫差，ΔT＝T_K-T_K+1，如果則進(jìn)行升溫操作，令

步驟8.9、重復(fù)執(zhí)行步驟3-8，直到生成的解達(dá)到種群規(guī)模，終止操作；

步驟9、個(gè)體進(jìn)行10％的精英保留策略；

步驟10、判斷算法是否達(dá)到最大迭代次數(shù)，如果是則算法結(jié)束；如果未達(dá)到最大迭代次數(shù)，則跳轉(zhuǎn)到步驟4。

2.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)混合遺傳算法的作業(yè)車間調(diào)度方法，其特征在于：步驟5中，個(gè)體進(jìn)行輪盤賭選擇法，具體包含如下步驟：

步驟5.1：根據(jù)已經(jīng)計(jì)算出的各個(gè)個(gè)體的適應(yīng)度f(1)，f(2)，...，f(N)，N為種群數(shù)量，然后將所有的適應(yīng)度進(jìn)行累加得到然后計(jì)算每個(gè)染色體在中的占比p(v)和累計(jì)概率q(v)，計(jì)算公式如下：

步驟5.2、產(chǎn)生一個(gè)隨機(jī)數(shù)θ∈(0，1)，如果θ≤q(1)，則選擇第一個(gè)個(gè)體，否則的話，如果q(v-1)≤θ≤q(v)，則選擇第v個(gè)個(gè)體，將這個(gè)步驟循環(huán)N次，得到所需規(guī)模的種群即可。