基于改進(jìn)免疫算法的容量限制工廠選址仿真

李睿雪，馬 良，劉 勇

(上海理工大學(xué)管理學(xué)院，上海 200093)

1 引言

傳統(tǒng)容量限制工廠選址問題解決的僅是針對某一區(qū)域網(wǎng)絡(luò)中的備選點(diǎn)和需求點(diǎn)之間最優(yōu)路徑問題，選取能使總距離最小同時(shí)能滿足需求點(diǎn)需求的位置作為最佳備選點(diǎn)。但是在實(shí)際生產(chǎn)活動(dòng)中，工廠的選址問題不僅涉及到備選點(diǎn)的位置，還涉及到備選點(diǎn)的生產(chǎn)能力。一個(gè)好的工廠位置可以降低工廠的運(yùn)輸成本，并能在滿足需求的前提下減少一定的成本消耗。因此，對于處于最優(yōu)位置并能夠滿足需求的備選位置，需要建立生產(chǎn)規(guī)模合適的工廠，使投入成本達(dá)到最低。

相關(guān)學(xué)者針對容量限制的設(shè)施選址問題做出了大量研究。于宏濤[1]在針對工廠容量受限的問題上改進(jìn)了基礎(chǔ)的容量限制模型，將其轉(zhuǎn)化為背包問題，提出貪婪蟻群算法，得到了模型的最優(yōu)解，但是在算法的改進(jìn)效果不足。肖俊華[2]在無容量限制的多目標(biāo)多級(jí)覆蓋的問題上加入了容量限制，并設(shè)計(jì)了上升式啟發(fā)式算法，對模型加以驗(yàn)證。漆楊[3]分析了容量受限的工廠選址問題的現(xiàn)有不足，將傳統(tǒng)的免疫克隆算法中的抗體生產(chǎn)和抗體變異過程進(jìn)行改進(jìn)，但算法的收斂性略有不足。俞武揚(yáng)[4]將設(shè)施的容量作為限制條件，建立模型，采用了模擬退火算法對數(shù)值例子進(jìn)行求解，得到了不同容量的選址策略。陳中武[5]在對成本約束的選址模型中加入了以顧客的隨機(jī)需求的隨機(jī)參數(shù)，利用拉格朗日松弛算法得到了較好的效果。袁藩[6]從單種產(chǎn)品的容量限制的設(shè)施選址問題拓展為k種產(chǎn)品，并采用了近似算法得到最優(yōu)解，但是對于某些單位置多工廠的方案仍未解決。尚志勇[7]針對帶有容量限制的配送中心選址問題，改進(jìn)了布谷鳥算法的發(fā)現(xiàn)概率，得到了較好的效果。

通過以上分析發(fā)現(xiàn)容量限制選址模型研究中多考慮固定的生產(chǎn)能力，忽略了備選位置的生產(chǎn)規(guī)模帶來的影響以及該位置的二次擴(kuò)建。為此本文對每一個(gè)工廠的生產(chǎn)能力進(jìn)行了劃分，設(shè)置分階段的可選擇的生產(chǎn)規(guī)模。對CPLP(Capacitated Plant Location Problem)[7]模型進(jìn)行了改進(jìn)，將建設(shè)成本分解為生產(chǎn)成本和固定建設(shè)成本，其中生產(chǎn)成本是根據(jù)需求量的大小來決定的。從而構(gòu)建考慮生產(chǎn)能力的容量限制工廠選址模型進(jìn)行優(yōu)化。

2 容量限制下的工廠選址模型

2.1 傳統(tǒng)容量限制選址的數(shù)學(xué)模型

在容量限制的選址模型中目標(biāo)是在備選位置中選擇能使距離成本最小和建設(shè)成本最小的最優(yōu)位置。設(shè)I為備選工廠的位置集；J為需求點(diǎn)的位置集；ai為備選工廠i在固定成本ci下的生產(chǎn)能力；dj為需求點(diǎn)的需求量；tij表示從備選工廠i到需求點(diǎn)j之間的運(yùn)輸成本。其目標(biāo)在于不超出工廠的生產(chǎn)能力的前提下，選擇最優(yōu)的備選位置。模型如下[14]

(1)

s.t.

(2)

xij=0，1 ?i∈I，?j∈J

(3)

yi=0，1 ?i∈I

(4)

xij≤yij?i∈I，?j∈J

(5)

模型中目標(biāo)函數(shù)是(1)表示工廠選址的運(yùn)輸成本和固定生產(chǎn)成本之和最?。患s束式(2)表示備選工廠所服務(wù)的需求點(diǎn)的需求之和不超出該備選工廠的最大生產(chǎn)能力；式(3)、式(4)表示為決策變量約束，xij為工廠i對需求點(diǎn)j服務(wù)，yi為在備選位置i選擇建設(shè)工廠，其中開放取值為1，否則是關(guān)閉取值為0；式(5)表示確保需求點(diǎn)和開放的備選位置保持對應(yīng)。

2.2 改進(jìn)容量限制選址模型

對原有的基礎(chǔ)模型和文獻(xiàn)[8]的模型進(jìn)行改進(jìn)，其中文獻(xiàn)[8]的模型盡管考慮到了對生產(chǎn)能力進(jìn)行分段考慮，但是缺少對需求點(diǎn)和備選點(diǎn)的距離的考慮。借鑒這一思想將基礎(chǔ)模型中的固定成本分解為生產(chǎn)成本和固定成本，生產(chǎn)成本由生產(chǎn)能力決定，而生產(chǎn)能力設(shè)置為分階段式，根據(jù)備選工廠所需要滿足的總需求量來選擇最合適的生產(chǎn)能力階段；并且基于實(shí)際生產(chǎn)情況考慮，在生產(chǎn)能力規(guī)模較大時(shí)，單位生產(chǎn)成本較?。还潭ǔ杀緞t是由備選點(diǎn)決定的固定值。由此建立了全新的數(shù)學(xué)模型：

設(shè)I為工廠備選位置的合集；J為需求點(diǎn)的位置合集；tij為備選位置i到需求點(diǎn)j的運(yùn)輸成本；dj表示需求點(diǎn)j的需求量；ein表示備選位置i的實(shí)際選擇的第n階段生產(chǎn)規(guī)模；gi表示備選位置i的最大生產(chǎn)規(guī)模；hi表示工廠i在該地點(diǎn)的基礎(chǔ)建設(shè)成本；kin表示工廠i在n階段生產(chǎn)能力下每單位的生產(chǎn)建設(shè)成本。模型如下

(6)

s.t.

(7)

xij=0，1 ?i∈I，?j∈J

(8)

yi=0，1 ?i∈I

(9)

xij≤yij?i∈I，?j∈J

(10)

模型中目標(biāo)函數(shù)是(6)表示工廠選址的運(yùn)輸成本和生產(chǎn)成本之和最小，其中生產(chǎn)成本由基礎(chǔ)建設(shè)成本和生產(chǎn)成本。約束式(7)表示需求點(diǎn)的需求之和大于備選工廠i的n-1階段生產(chǎn)能力且小于備選工廠i的n階段生產(chǎn)能力并且不超過備選工廠的最大生產(chǎn)能力；式(8)、式(9)表示為決策變量約束，xij為工廠i對需求點(diǎn)j服務(wù)，yi為在備選位置i以選擇建設(shè)工廠，其中開放取值為1，否則是關(guān)閉取值0；式(10)表示確保需求點(diǎn)和開放的備選位置保持對應(yīng)。

3 改進(jìn)免疫遺傳算法求解

3.1 傳統(tǒng)免疫遺傳算法的原理

傳統(tǒng)免疫遺傳算法(Immune Genetic Algorithm，IGA)[9]是基于生物免疫系統(tǒng)的啟發(fā)而形成的算法，與遺傳算法類似，但是主要區(qū)別在于免疫遺傳算法對個(gè)體的評價(jià)標(biāo)準(zhǔn)不僅有適應(yīng)度還有親和度，使得出的種群的多樣性更加豐富。其中主要的親和度就是利用了免疫系統(tǒng)的多樣性產(chǎn)生和維持機(jī)制來保持群體多樣性，克服了一般尋優(yōu)過程中會(huì)出現(xiàn)“早熟”現(xiàn)象。

3.2 傳統(tǒng)免疫遺傳算法設(shè)計(jì)

1) 編碼。將備選工廠編號(hào)和工廠與需求點(diǎn)對應(yīng)關(guān)系作為解，因此采取整數(shù)編碼。個(gè)體編碼由前半部分的位置編號(hào)信息和后半部分的選擇點(diǎn)和需求點(diǎn)對應(yīng)關(guān)系共同組成；

2) 抗體群的產(chǎn)生。初始的抗體在解空間中用隨機(jī)的方法產(chǎn)生；

3) 解的評價(jià)。親和力是抗體對抗原的識(shí)別，本算法中抗體和抗原的親合力函數(shù)Av：

(11)

其中，分母中第一項(xiàng)為目標(biāo)函數(shù)。抗體和抗體之間的親和力函數(shù)Sv

(12)

其中，kv表示為兩種抗體中相同的位數(shù)，L表示抗體的長度

抗體的濃度，即抗體在種群中的比例函數(shù)Cv

(13)

其中，N為抗體總數(shù)。

抗體和抗原間的親和力和抗體的濃度共同作用形成了期望繁殖概率函數(shù)P

(14)

其中，λ是一個(gè)常數(shù)；

4) 形成父代記憶庫。將個(gè)體按照繁殖率進(jìn)行排序，保留s個(gè)個(gè)體進(jìn)入記憶庫，進(jìn)入下次迭代；

5) 免疫操作。免疫包括了選擇、交叉和變異3種，其中選擇方式按輪盤賭策略進(jìn)行選擇；交叉方式按照單點(diǎn)交叉進(jìn)行交叉操作；變異方式按照隨機(jī)選擇變異位進(jìn)行變異操作。

3.3 改進(jìn)的免疫遺傳算法

由于傳統(tǒng)的免疫遺傳優(yōu)化算法中記憶庫中的優(yōu)秀個(gè)體的保留過于保守，隨著迭代的進(jìn)行，種群的質(zhì)量更高，卻不能保存更多的優(yōu)秀個(gè)體，造成收斂速度過慢，計(jì)算精度也會(huì)受到影響。通過設(shè)置動(dòng)態(tài)保留機(jī)制，提出了一種動(dòng)態(tài)保留優(yōu)秀個(gè)體免疫遺傳算法(New Immune Genetic Algorithm，NIGA)。對記憶庫中的優(yōu)秀個(gè)體數(shù)s設(shè)置為動(dòng)態(tài)變化，隨著種群的總體質(zhì)量的提高，優(yōu)秀個(gè)體的保存數(shù)也隨之增大。其中s由種群的質(zhì)量函數(shù)確定

(15)

其中m為備選點(diǎn)數(shù)量，n為需求點(diǎn)數(shù)量，p為記憶庫規(guī)模，ki表示選擇點(diǎn)和該需求點(diǎn)的距離在備選點(diǎn)和該需求點(diǎn)的距離集總的降序位置。

其次是免疫遺傳的選擇過程，傳統(tǒng)的免疫遺傳的遺傳部分中選擇操作多為輪盤賭等方式操作[10]，依靠一定概率來保留最優(yōu)個(gè)體，這樣往往會(huì)增加計(jì)算量和迭代次數(shù)，同時(shí)也會(huì)影響計(jì)算精度。因此，本文根據(jù)Metropolis準(zhǔn)則來對選擇操作的種群進(jìn)行選擇[11]。對一個(gè)種群中的第i個(gè)個(gè)體與第i+1個(gè)個(gè)體進(jìn)行比較，選擇接受第i+1個(gè)體規(guī)則如下，否則接受第i個(gè)體

(16)

其中f(x)表示適應(yīng)度值；rand是在[0，1]上均勻分布的隨機(jī)數(shù)；T為溫度。

3.4 改進(jìn)的免疫遺傳算法步驟

1) 產(chǎn)生初始抗體群；

2) 計(jì)算種群的適應(yīng)度值和親和度值；

3) 對群體中抗體以期望繁殖率P進(jìn)行評價(jià)；

4) 形成父代群體，進(jìn)行排序后保留s個(gè)個(gè)體和m個(gè)記憶庫個(gè)體。其中s個(gè)個(gè)體由種群的質(zhì)量決定；

5) 判斷是否滿足結(jié)束條件；

6) 對(3)形成的新群體進(jìn)行選擇、交叉、變異操作得到新群體，再取出記憶庫個(gè)體，形成新群體；

7) 繼續(xù)執(zhí)行步驟3)。

4 計(jì)算實(shí)驗(yàn)

4.1 模型對比

由于真實(shí)數(shù)據(jù)難以獲取，本文采取模擬數(shù)據(jù)的方法設(shè)立兩組算例對算法進(jìn)行驗(yàn)證，運(yùn)用Matlab2016a編程進(jìn)行模擬數(shù)據(jù)實(shí)驗(yàn)。首先模擬算例1的數(shù)據(jù)模型進(jìn)行驗(yàn)證：假設(shè)備選工廠的數(shù)量為5個(gè)，從中選出2個(gè)備選工廠位置對這些需求點(diǎn)進(jìn)行服務(wù)。需求點(diǎn)數(shù)量為30。每個(gè)需求點(diǎn)的需求量在[0，100]中隨機(jī)產(chǎn)生，需求點(diǎn)的坐標(biāo)在4000*4000的網(wǎng)格中隨機(jī)產(chǎn)生。備選工廠的位置、建廠固定成本、工廠不同階段的生產(chǎn)規(guī)模見表1。

表1 算例1備選工廠數(shù)據(jù)

改進(jìn)免疫遺傳算法的初始參數(shù)設(shè)置：初始種群大小為60，記憶庫規(guī)模為20，交叉概率0.7，變異概率0.2，種群多樣性為0.9，迭代次數(shù)為150次，初始溫度為T為180，終止溫度30度。獨(dú)立運(yùn)行了20次。得到的結(jié)果見表2。

表2 算例1數(shù)據(jù)集運(yùn)行結(jié)果

從結(jié)果中可以看出來，盡管改進(jìn)模型加入了生產(chǎn)規(guī)模的成本，但是相對于基礎(chǔ)模型的成本增加并不多，兩次結(jié)果也計(jì)算都算出了最佳的3號(hào)工廠位置為最佳位置之一，而在考慮到生產(chǎn)規(guī)模后5號(hào)位置就明顯優(yōu)于1號(hào)位置，其原因是因?yàn)?號(hào)位置的生產(chǎn)規(guī)模選擇的成本低于1號(hào)位置，使該位置的成本低于1號(hào)位置，并對需求進(jìn)行分配的能力也優(yōu)于1號(hào)位置。可見在改進(jìn)后的模型中，備選位置的生產(chǎn)規(guī)模的選擇也是決定一個(gè)備選位置的關(guān)鍵因素，能夠更加合理的分配了產(chǎn)品的生產(chǎn)和分配。

之后算例2的數(shù)據(jù)模型進(jìn)行驗(yàn)證：備選工廠的數(shù)量為10個(gè)，需求點(diǎn)數(shù)量為60。從中選出2個(gè)備選工廠位置對這些需求點(diǎn)進(jìn)行服務(wù)。每個(gè)需求點(diǎn)的需求量在[0，100]中隨機(jī)產(chǎn)生，需求點(diǎn)的坐標(biāo)在4000*4000的網(wǎng)格中隨機(jī)產(chǎn)生。備選工廠的位置、建廠固定成本、工廠不同階段的生產(chǎn)規(guī)模見表3。

表3 算例2備選工廠數(shù)據(jù)

改進(jìn)免疫遺傳算法的初始參數(shù)設(shè)置：初始種群大小為60，記憶庫規(guī)模為20，交叉概率0.8，變異概率0.3，種群多樣性為0.9，迭代次數(shù)為200次，初始溫度為T為210，終止溫度10度。獨(dú)立運(yùn)行了20次。得到的結(jié)果見表4。

表4 算例2運(yùn)行結(jié)果

從結(jié)果中可以得出，在數(shù)據(jù)量擴(kuò)大后，相對于算例1總成本提高。原模型在不考慮生產(chǎn)規(guī)模的情況下，成本低于改進(jìn)模型的成本。但是兩組算例的成本之差是由于原模型中沒有設(shè)定生產(chǎn)所產(chǎn)生的成本。在工廠位置上，兩模型都找到了最佳的位置，但改進(jìn)模型對于需求的分配更加平均，而原模型的分配方案有一定程度增加工廠生產(chǎn)負(fù)荷的風(fēng)險(xiǎn)。相比之下，改進(jìn)模型的分配方案更加合理，而且在成本上也是略高于沒有考慮生產(chǎn)規(guī)模成本的原模型?？梢姼倪M(jìn)模型更加適合工廠生產(chǎn)建設(shè)的實(shí)際情況。

4.2 算法對比

對模型改進(jìn)分析后，對算法改進(jìn)前后的效果進(jìn)行對比，具體參數(shù)保持不變，對兩種規(guī)模的模型進(jìn)行對比實(shí)驗(yàn)。迭代結(jié)果如圖1和圖2。

圖1 算例1改進(jìn)前后迭代對比圖

圖2 算例2改進(jìn)前后迭代對比圖

由圖1可以看出算例1在數(shù)據(jù)量較少時(shí)改進(jìn)的免疫遺傳算法的迭代次數(shù)比基本免疫遺傳算法提高了很多，很快就可以達(dá)到收斂，并且在計(jì)算精度也有所提升。因?yàn)橐?guī)模較小時(shí)的計(jì)算量不大，計(jì)算速度較快，所以改進(jìn)后迭代速度明顯提高而精度小幅度提高。而在算例2中數(shù)據(jù)量相對增加后改進(jìn)免疫遺傳算法收斂速度加快并且精度上也有所提升。因?yàn)樗憷?的種群中個(gè)體的編碼長度較長，依靠動(dòng)態(tài)的記憶庫個(gè)體保存機(jī)制和新的遺傳選擇方法可以在每次迭代中更大程度保留最佳的個(gè)體，從而更快的找到最優(yōu)的結(jié)果，大大提高計(jì)算速度。在計(jì)算精度上，兩組算例改進(jìn)算法都可以更加接近最低成本在運(yùn)算20次后，計(jì)算平均成本和標(biāo)準(zhǔn)差。結(jié)果見表5。

表5 算法改進(jìn)前后結(jié)果對比

根據(jù)表5結(jié)果通過多次實(shí)驗(yàn)的可以證實(shí)，改進(jìn)的免疫遺傳算法對這一模型的計(jì)算結(jié)果的精度明顯提高。相對算例1，算例2的數(shù)據(jù)量增加后，改進(jìn)后算法的效果相對傳統(tǒng)的免疫遺傳算法的提升更加明顯。

5 結(jié)論

本文提出了全新的容量限制的選址模型并采用改進(jìn)的免疫遺傳算法進(jìn)行優(yōu)化。首先，論文針對工廠選址初期的需求問題，提出了分段式的生產(chǎn)規(guī)模選址模型；然后，結(jié)合選址模型對免疫遺傳算法進(jìn)行改進(jìn)建立了對應(yīng)的容量限制選址優(yōu)化模型；最后，使用MATLAB編程分別對兩組數(shù)據(jù)進(jìn)行驗(yàn)證方法的有效性。通過數(shù)據(jù)結(jié)果可以看出：改進(jìn)的模型和算法可以有效地降低成本的同時(shí)滿足需求，更貼近實(shí)際生產(chǎn)情況，并且改進(jìn)的算法還提高模型計(jì)算的運(yùn)行速度。為了深入的研究容量限制選址問題，接下來將分析有不確定需求等因素的容量限制的選址問題，并進(jìn)行對其進(jìn)行深入的研究。