基于免疫算法的大米加工廠選址研究

余翠蘭

摘要：針對大米加工廠選址問題，首先分析了影響大米加工廠選址的因素及介紹了免疫算法的概念和特點(diǎn)，然后采用免疫算法對大米加工廠選址進(jìn)行建模，并給出了模型的求解方法。利用該方法可以方便地得到大米加工廠選址的最優(yōu)解。

關(guān)鍵詞：大米加工廠；選址；免疫算法

中圖分類號：TP183

文獻(xiàn)標(biāo)識碼：A

DOI： 10.3969/j.issn.1003-6970.2015.07.016

0 引言

大米加工方法隨著人民生活水平的提高不斷發(fā)展，在一些地處亞熱帶地區(qū)、熱量豐富、雨量充沛、土地肥沃、盛產(chǎn)稻米的區(qū)縣建立中小型大米加工廠是非常有必要的，而建廠的位置不同則米源、市場、成本等就會不同，那么如何選址才能使投資者成本最小、利潤最大呢？

解決選址問題的方法主要有：重心法、層次分析法、專家選擇法等，但這幾種方法在進(jìn)行選址問題研究時考慮的因素比較單一，不能將多個因素有機(jī)結(jié)合起來，本文選定免疫算法來構(gòu)建大米加工廠選址模型。免疫算法是源于生物免疫系統(tǒng)的性質(zhì)而衍化出來的一種智能算法。選擇它是因?yàn)椋好庖咚惴ň哂休^強(qiáng)的全局尋優(yōu)索搜索能力；能保證解的多樣性；計算求解時采用并行搜索方式，保證解的準(zhǔn)確性；同時該算法可以把影響大米加工廠選址的各方面如距離、運(yùn)費(fèi)等因素有機(jī)結(jié)合起來。

1 大米加工廠選址的影響因素

1.1 問題描述

某縣盛產(chǎn)稻谷，投資者想建立兩個大米加工廠。假設(shè)全縣水田較多的村有M個，需要將稻谷送到大米加工廠的量較大，這M個村簡稱M個需求點(diǎn)，在這M個需求點(diǎn)中估計出N個作為加工廠的備選地點(diǎn)，那么備選地點(diǎn)中在哪兩個地點(diǎn)建廠最能使投資者的成本（包括建造成本和運(yùn)營成本）最低、利潤最大呢？

1.2 影響大米加工廠選址的因素

大米加工廠應(yīng)建在谷源豐富、谷質(zhì)優(yōu)及交通便利的地方。通過分析，本文考慮的影響大米加工廠選址的主要因素包括：距離、服務(wù)量及運(yùn)營費(fèi)用。

（1）距離：指備選地點(diǎn)到需求點(diǎn)間的距離總和，且距離的計算采用兩地點(diǎn)間使用的公路的實(shí)際距離。

（2）服務(wù)量：指備選地點(diǎn)能得到的稻谷總量。即備選地點(diǎn)服務(wù)范圍內(nèi)各村農(nóng)戶會將稻谷送到大米加工廠服務(wù)的數(shù)量。也叫需求服務(wù)量、稻谷量。

（3）運(yùn)營費(fèi)用：水、電、氣費(fèi)用、技術(shù)工人費(fèi)用、管理費(fèi)、設(shè)備維修保養(yǎng)費(fèi)以及車輛的折舊費(fèi)用等。

另外，我們還進(jìn)行下面的假設(shè)：

（1） -個備選地點(diǎn)可服務(wù)多個需求點(diǎn)，但一個需求點(diǎn)只能被一個備選地點(diǎn)服務(wù)，不允許一個服務(wù)地點(diǎn)被多個備選地點(diǎn)進(jìn)行服務(wù)。

（2）各需求點(diǎn)的需求量是已知的。

（3）備選地點(diǎn)的服務(wù)能力能夠服務(wù)范圍內(nèi)客戶的全部需求，即無服務(wù)量的限制、無庫存容量的限制。

（4）總費(fèi)用只考慮固定的大米加工廠建設(shè)費(fèi)用和運(yùn)營費(fèi)用，且建設(shè)費(fèi)用已知。

例如，通過走訪調(diào)研，可獲得各備選地點(diǎn)到需求點(diǎn)的實(shí)際距離及稻谷量，如表1為其中一個備選地點(diǎn)的數(shù)據(jù)。

2 基于免疫算法的大米加工廠選址模型構(gòu)建

2.1 免疫算法

免疫算法是一種模擬生物免疫系統(tǒng)的智能優(yōu)化算法，實(shí)現(xiàn)了類似于生物免疫系統(tǒng)的抗原識別、細(xì)胞分化、記憶和自我調(diào)節(jié)的功能，具有良好的系統(tǒng)應(yīng)答性和自主性，對干擾具有較強(qiáng)維持系統(tǒng)自平衡能力。如果將免疫算法與求解優(yōu)化問題的一般搜索方法相比較，那么抗原、抗體、抗體和抗原之間的親和度分別對應(yīng)于優(yōu)化問題的目標(biāo)函數(shù)、優(yōu)化解、解與目標(biāo)函數(shù)的匹配程度。

2.2 大米加工廠選址模型的建立

基于上節(jié)的分析及假設(shè)，根據(jù)免疫算法目標(biāo)函數(shù)，大米加工廠選址的目標(biāo)函數(shù)：

其中， 為備選地點(diǎn)與m個需求點(diǎn)（村）的距離與運(yùn)輸費(fèi)率的乘積； 為備選地點(diǎn)對需求點(diǎn)提供的服務(wù)費(fèi)用，等于備選地點(diǎn)的服務(wù)量與服務(wù)費(fèi)率的乘積； 為備選地點(diǎn)在生產(chǎn)運(yùn)營時水、電、氣、設(shè)備維修保養(yǎng)費(fèi)以及車輛的折舊費(fèi)用。N={l，2，…，n}為備選地點(diǎn)的集合，Mj={l，2，…，m}為滿足客戶需求點(diǎn)的服務(wù)村的集合；z_ij為0-1變量，表示備選地點(diǎn)與需求點(diǎn)的服務(wù)需求分配關(guān)系，當(dāng)Z_ij=1時，說明需求點(diǎn)i的稻谷由備選地點(diǎn)j進(jìn)行加工，否則z_ij=0；t_i表示備選地點(diǎn)到需求點(diǎn)的運(yùn)輸費(fèi)率；d_ij表示從需求點(diǎn)到離它最近的備選地點(diǎn)的距離；F表示需加工的稻谷總量；f表示稻谷加工費(fèi)率；P_i表示備選地點(diǎn)的平均消耗費(fèi)用。

約束條件中的第1個保證每個需求點(diǎn)只能由一個備選地點(diǎn)進(jìn)行服務(wù)，第2個確保需求點(diǎn)的服務(wù)需求量能被備選地點(diǎn)處理，第3個表示大米加工廠選址備選地點(diǎn)數(shù)量為b，第4個表示Z_ij、h_j是0-1變量，第5個保證需求點(diǎn)在備選地點(diǎn)可服務(wù)的范圍內(nèi)。

2.3 大米加工廠選址模型求解

求解選址模型的步驟如下：

步驟1：初始抗體的產(chǎn)生。（初始抗體群的產(chǎn)生）將需求點(diǎn)看作免疫算法中的抗原，抗原數(shù)量為M，用1、2、…，m表示；從中選出N個作為備選地點(diǎn)，將備選地點(diǎn)看作免疫算法中的抗體，用b₁、b₂、…、b_N表示。要在N個抗體中選出2個抗體作為與抗原進(jìn)行有效結(jié)合，其中，抗體表示全局最優(yōu)解，抗原為需解決的問題。設(shè)定種群數(shù)量為M的初始種群。

步驟2：計算抗體與抗原間的親和力。親和力用于表示抗體對抗原的識別程度，此處針對上述大米加工廠選址模型的親和力的計算公式為：

其中，F(xiàn)_v為選址問題的目標(biāo)函數(shù)，分母中第二項(xiàng)表示為違反距離約束的解給予懲罰，C取較大的正整數(shù)。endprint

步驟3：計算抗體與抗體間相似度。在免疫算法中為了表示種群中抗體的多樣性，引用了平均信息熵的概念。在選址模型問題上，平均信息熵表示：對備選地點(diǎn)求得解的平均相似信息量，在本文中表示種群個體的平均存活質(zhì)量。同一抗體間不存在平均信息熵。其性質(zhì)有平均信息熵越高，則種群多樣性越低；反之平均信息熵越低，則種群多樣性越高。本文中群體內(nèi)有抗體N個，則有該抗體的平均信息熵H（N）為：

其中，A_ij為第i個抗體與第j個抗原的親和力，表示第i個備選地點(diǎn)是否能夠需求點(diǎn)j的問題。當(dāng)抗體與抗原的相似度越高時，則該備選地點(diǎn)作為大米加工廠建廠的概率越大。

抗體間相似度表示利用免疫算法選址模型求得的有效解與解之間的相似性的百分比的度量。相同抗體是相似的，相似度等于1。抗體間相似度S_ij的公式為：

步驟4：計算抗體濃度?？贵w的濃度Cv是群體中相似抗體所占的比例。用抗體濃度的大小來衡量抗體對抗原結(jié)合程度，抗體濃度也可作為抗體個體是否優(yōu)質(zhì)性的重要依掘。C_v的公式如下：

其中， T為預(yù)先設(shè)定的一個閾值。

通過分別計算N個抗體的個體濃度，則可得到C_x和Cy（x，y<=N）（假設(shè)需選定兩個建廠地址）的抗體濃度較高，這兩個抗體可初步作為兩個全局最優(yōu)解，能夠解決全局內(nèi)出現(xiàn)的問題，即這兩個抗體可初步作為建立大米加工廠的地點(diǎn)，之后需要經(jīng)過被選擇的概率來驗(yàn)證是否有體會選擇這兩個抗體。

步驟5：計算抗體被選擇的概率。在生物群體中，抗體濃度較高時，免疫算法就會認(rèn)為該抗體越容易被生物機(jī)體選擇，因此較高的抗體可以作為全局最優(yōu)解，抗體被選擇的概率P的公式為：

在利用免疫算法求解選址問題中，求得優(yōu)質(zhì)的解是經(jīng)過免疫算法的循環(huán)計算后儲存在記憶庫中并進(jìn)行對比得出的，若該求得的解出現(xiàn)的頻率較高，且于記憶庫中在對比條件下具有優(yōu)勢時，則容易被免疫算法記憶庫保留下來，作為全局最優(yōu)解。若抗體被選擇的概率較低，免疫算法則會放棄本次選擇的抗體，繼續(xù)尋找概率較大的抗體個體。

也就是說，通過計算N個抗體被選擇的概率，假設(shè)是Px和Py最高，則說明模型求得的是全局最優(yōu)解，x和y這兩個備選地點(diǎn)可作為大米加工廠的建廠地點(diǎn)。

步驟6：計算期望繁殖概率。抗體的期望繁殖概率Q公式為：

其中，a為O

個體適應(yīng)度高與期望繁殖概率大的抗體存留于記憶庫中。在選址問題中，在機(jī)體的免疫平衡機(jī)制的作用下保證了解的多樣性，隨著需求點(diǎn)的稻谷量、運(yùn)營費(fèi)用等因素不斷變化時，選址地點(diǎn)的自身?xiàng)l件也會在市場作用下相應(yīng)的更新，能夠繼續(xù)成為最適合的建廠地點(diǎn)。

3 小結(jié)

文章首先分析了影響大米加工廠選址的因素，然后構(gòu)建了基于免疫算法的大米加工廠選址模型，給出了模型的求解方法和步驟。該方法具有很強(qiáng)的全局收斂功能，還具有解的多樣性與自適應(yīng)性等特點(diǎn)。利用免疫優(yōu)化算法可以方便地得到大米加工廠選址優(yōu)化問題的最優(yōu)解。