[發(fā)明專利]一種基于天牛須搜索的粒子群算法求解柔性作業(yè)車間調(diào)度的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010068722.6
• 申請(qǐng)日: 2020-01-21
• 公開(kāi)（公告）號(hào): CN111311077B
• 公開(kāi)（公告）日: 2022-02-18
• 發(fā)明（設(shè)計(jì)）人: 唐浩;黎向鋒;張立果;左敦穩(wěn);張麗萍;陸開(kāi)勝;王建明;葉磊;王子旋;劉安旭;劉晉川
• 申請(qǐng)（專利權(quán)）人: 南京航空航天大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06N3/00
• 代理公司: 南京天華專利代理有限責(zé)任公司 32218
• 代理人: 瞿網(wǎng)蘭

1.一種基于天牛須搜索的粒子群算法求解柔性作業(yè)車間調(diào)度的方法，它利用天牛須搜索對(duì)粒子群算法進(jìn)行改進(jìn)，并混合變鄰域搜索算法，實(shí)現(xiàn)柔性作業(yè)車間調(diào)度，其特征在于它包括以下步驟：

步驟1：初始化算法參數(shù)，設(shè)置PSO種群的大小為N，最大迭代次數(shù)MAX，學(xué)習(xí)因子為c1、c2、c3，以及每個(gè)甲殼蟲(chóng)天線長(zhǎng)度為d₀，天牛進(jìn)化步長(zhǎng)δ，在柔性作業(yè)車間調(diào)度中以求解最大完工時(shí)間最小為單目標(biāo)，定義適應(yīng)度值為最大完工時(shí)間的倒數(shù)；

步驟2：初始化調(diào)度解種群，該種群分兩段編碼，即機(jī)器序列編碼和工序序列編碼；機(jī)器編碼和工序編碼長(zhǎng)度相等；初始化粒子的速度向量v和慣性權(quán)重w；

步驟3：利用活動(dòng)解碼計(jì)算每個(gè)個(gè)體的適應(yīng)度，進(jìn)行適應(yīng)度排序，通過(guò)逐一比較得到當(dāng)前的全局最優(yōu)解；

步驟4：把調(diào)度解映射到個(gè)體位置向量，對(duì)種群中的適應(yīng)度靠前的少量最優(yōu)個(gè)體進(jìn)行變鄰域搜索，用于提高粒子群算法的局部搜索能力，以便跳出局部最優(yōu)；采用三種鄰域結(jié)構(gòu)：

1)鄰域結(jié)構(gòu)N1：產(chǎn)生一個(gè)隨機(jī)整數(shù)r，r∈[-l,l]，其中l(wèi)為位置向量中工序編碼長(zhǎng)度，若r0，則編碼中前r個(gè)元素移動(dòng)到編碼末端；若r0，則編碼中最后r個(gè)元素移動(dòng)到編碼前端；

2)鄰域結(jié)構(gòu)N2：在個(gè)體位置向量工序編碼中隨機(jī)選擇兩個(gè)對(duì)應(yīng)不同工件的位置元素，將后一個(gè)元素插到前一個(gè)元素前面；

3)鄰域結(jié)構(gòu)N3：在個(gè)體位置向量機(jī)器編碼中任選一個(gè)元素，該元素對(duì)應(yīng)的工序的可選機(jī)器應(yīng)該多于一臺(tái)，然后將該工序分配至不同于現(xiàn)在的機(jī)器，并按照映射公式生成新元素值；

步驟5：變鄰域算法利用閾值接受法來(lái)實(shí)現(xiàn)，經(jīng)過(guò)局部搜索后的個(gè)體重新放回種群中；

步驟6：隨機(jī)初始化每個(gè)甲殼蟲(chóng)頭部，因?yàn)榧讱はx(chóng)頭部可以朝著任意方向，因此，對(duì)于n維空間中的優(yōu)化問(wèn)題，可以生成隨機(jī)單位向量來(lái)表示和標(biāo)準(zhǔn)化它：

其中，k是空間維度，rands()為隨機(jī)函數(shù)；

步驟7：初始化x_l和x_r：

其中，x_l代表個(gè)體搜索區(qū)域的左側(cè)，x_r代表右側(cè)；

步驟8：確定每個(gè)天牛的左右觸角的氣味強(qiáng)度，即f(x_l)和f(x_r)代表左右位置氣味強(qiáng)度，同時(shí)也表征適應(yīng)度函數(shù)，并且利用其生成速度更新位置準(zhǔn)則：

其中，為隨機(jī)單位向量，δ^k為第k次迭代的天牛進(jìn)化步長(zhǎng)，sign函數(shù)為符號(hào)函數(shù)，如果sign函數(shù)為正，表示右邊適應(yīng)度高；否則，相反；

步驟9：通過(guò)步驟5中的局部搜索之后，重新評(píng)估所有個(gè)體適應(yīng)度值，得到甲蟲(chóng)的當(dāng)前位置的適應(yīng)度值，比較得到每個(gè)個(gè)體最優(yōu)位置p_b和全局最優(yōu)位置p_g，生成速度更新準(zhǔn)則；

步驟10：結(jié)合上述兩種速度更新規(guī)則，獲取每種天牛速度的當(dāng)前更新規(guī)則：

k表示當(dāng)前代數(shù)，當(dāng)前位置更新規(guī)則：

步驟11：更新粒子速度與位置，以及各項(xiàng)基本參數(shù)；更新個(gè)體最優(yōu)調(diào)度方案p_b和全局最優(yōu)調(diào)度方案p_g；

步驟12：判斷算法是否滿足終止條件，若滿足，則結(jié)束；否則，按一定概率對(duì)個(gè)體進(jìn)行交叉和變異操作，之后按照映射關(guān)系轉(zhuǎn)化成調(diào)度解，然后轉(zhuǎn)到步驟3。

2.根據(jù)權(quán)利要求1所述的方法，其特征是初始化機(jī)器序列種群方法包括：全局選擇、局部選擇和隨機(jī)選擇；其中，全局選擇和局部選擇主要是為使機(jī)器負(fù)載均衡，有利于收斂到全局最優(yōu)，并設(shè)置這三種初始化方法的占比為6:3:1；工序序列初始化方法包括工件剩余時(shí)間最長(zhǎng)、剩余工序數(shù)最多和隨機(jī)初始化，并設(shè)置這三種初始化方法的占比為5:3:2，然后通過(guò)映射關(guān)系將編碼轉(zhuǎn)換成個(gè)體位置向量。

3.根據(jù)權(quán)利要求1所述的方法，其特征是將所述的交叉和變異操作引進(jìn)到粒子群算法里，對(duì)于交叉操作，在個(gè)體位置向量的機(jī)器部分采用多點(diǎn)交叉方法，在工序排序部分采用部分匹配交叉；對(duì)于工序變異采用全排列鄰域變異，隨機(jī)取多個(gè)點(diǎn)，對(duì)它們進(jìn)行全排列，隨機(jī)挑一種排列方式，讓其運(yùn)用在粒子群算法里；對(duì)于個(gè)體位置向量的機(jī)器序列變異，運(yùn)用單點(diǎn)變異方法。

4.根據(jù)權(quán)利要求1所述的方法，其特征是所述的變鄰域搜索融入到混合粒子群算法中，變鄰域采用閾值接受法，經(jīng)過(guò)多次迭代搜索當(dāng)前優(yōu)秀個(gè)體的鄰域，獲得更好的個(gè)體位置，然后轉(zhuǎn)換成調(diào)度解，重新評(píng)價(jià)適應(yīng)度。