陳林,姚宏亮

（1.安徽財(cái)貿(mào)職業(yè)學(xué)院電子信息系,安徽合肥230601；2.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽合肥230009）

免疫克隆遺傳算法在物流配送中的應(yīng)用

陳林1,姚宏亮2

（1.安徽財(cái)貿(mào)職業(yè)學(xué)院電子信息系,安徽合肥230601；2.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽合肥230009）

針對免疫遺傳算法在解決物流配送出現(xiàn)局部搜索能力不足和算法過早的收斂問題,提出了基于克隆選擇的改進(jìn)算法,通過引入克隆增殖算子、高頻變異和克隆選擇算子,有效增加了種群的多樣性和提高了局部搜索能力,避免了算法過早的收斂.針對物流配送的實(shí)例論證和分析,顯示算法的有效性.

物流配送；克隆增殖；克隆選擇；免疫遺傳算法

現(xiàn)階段,我國的物流迅速發(fā)展,物流市場對配送的需求十分旺盛.而在物流的各項(xiàng)成本當(dāng)中,配送成本占了相當(dāng)高的比例.因此物流配送中合理調(diào)度車輛對降低物流成本有著重要的意義[1],車輛調(diào)度問題（Vehicle Routing Problem,VRP）也成為眾多學(xué)者研究的熱門話題.

目前研究VRP問題的算法有很多,主要分成兩大類：精確算法和啟發(fā)式算法.精確算法主要有：分支定界法（Branch and Bound Approach）、割平面法（Cutting Planes Approach）、網(wǎng)絡(luò)流算法（Network Flow Approach）和動(dòng)態(tài)規(guī)劃方法（Dynamic Programming Approach）.然而,通過精確算法計(jì)算VRP問題,計(jì)算量很大,因此實(shí)用性很有限.所以大部分學(xué)者都將研究方向定位于啟發(fā)式算法[2-6].

對VRP問題,許多研究者進(jìn)行了大量的研究.李大衛(wèi)等求解了有時(shí)間窗約束的VSP問題[7].張震優(yōu)化了有行程約束的單車場滿載問題[8].蔡延光等對滿載問題使用了禁忌搜索算法和模擬退火算法進(jìn)行了求解[9].劉浩等用模擬退火算法求解了兩車型隨機(jī)需求的VRP[10].張濤等用禁忌搜索算法和遺傳算法的混合策略求解了VRP[11].王莉用啟發(fā)式算法求解了有時(shí)限的VRP[12].袁健等用神經(jīng)網(wǎng)絡(luò)法求解了VRP[13].姜大立等分別用遺傳算法求解了無時(shí)限和有時(shí)限的物流配送車輛調(diào)度問題[14].近年來,郭耀煌等對物流配送車輛調(diào)度問題進(jìn)行了較為深入的研究,提出了多種求解算法[15].周雙貴對物流配送車輛調(diào)度問題的模型和求解方法也進(jìn)行了較為深入的研究[16].

免疫遺傳算法是在遺傳算法的基礎(chǔ)上,加入了免疫算子,算法的關(guān)鍵就是疫苗的提取.至于疫苗的提取,根據(jù)生物免疫學(xué)原理,將求解優(yōu)化問題的目標(biāo)函數(shù)和約束條件看作是“抗原”,而把優(yōu)化問題的解看成是“抗體”,那么免疫遺傳算法就類似于產(chǎn)生大量抗體的過程.

不過免疫遺傳算法也存在明顯的不足,主要表現(xiàn)在以下幾個(gè)方面：

（1）免疫遺傳算法采用是隨機(jī)全局搜索策略,忽視了局部搜索,對于復(fù)雜問題情形,難以獲得滿意的結(jié)果；

（2）單純的接種疫苗會(huì)使種群朝著一個(gè)方向進(jìn)化,失去了種群的多樣性；

（3）種群的單一性,可能會(huì)使的算法過早的收斂.

針對免疫遺傳算法上述不足,在疫苗選擇的關(guān)鍵點(diǎn)上引入了克隆選擇的機(jī)制.

1 基于克隆原理的免疫遺傳算法

克隆選擇機(jī)制指的是當(dāng)未知抗原細(xì)胞入侵系統(tǒng)時(shí),對抗體細(xì)胞進(jìn)行克隆選擇,描述了免疫應(yīng)答的過程.抗體細(xì)胞被選擇的可能性受制于親和力,親和力越大的細(xì)胞,被選擇的可能性就越小.

克隆選擇算法通過引入克隆增殖算子、高頻變異和克隆選擇算子,在保持免疫遺傳算法全局搜索行的基礎(chǔ)上,增強(qiáng)了局部搜索能力,并增加了種群的多樣性；克隆選擇是在交叉、變異等遺傳算子和群體控制的基礎(chǔ)上實(shí)現(xiàn)的,有效的改善了算法的過早收斂.

1.1 克隆選擇算子

克隆選擇主要經(jīng)歷增殖、變異和選擇的過程,這三個(gè)過程被稱之為克隆選擇算子.

（1）克隆增殖TcC：克隆增殖是模擬生物進(jìn)化過程,使得比較優(yōu)秀的抗體能夠得到復(fù)制,因此,需要對比較優(yōu)秀的基因（用親和力高低來衡量）按照一定規(guī)模進(jìn)行復(fù)制,即對親和力高的抗體細(xì)胞進(jìn)行無性繁殖（即克隆）.

（2）克隆變異TmC：對種群細(xì)胞進(jìn)行高頻變異操作（主要是進(jìn)行連續(xù)倒位操作）.可以使得變異后的群體里原始解較遠(yuǎn)的距離.

（3）克隆選擇TsC：選擇的依據(jù)是對變異前后的個(gè)體進(jìn)行親和力的比較,根據(jù)親和力的大小決定選擇變異后的個(gè)體還是變異前的個(gè)體.

1.2 免疫克隆算法的算法步驟

下面針對基于克隆選擇的免疫遺傳算法的算法思想,描述算法的步驟.

步驟1：抗原識別.將給定的目標(biāo)函數(shù)和約束條件作為待求問題的抗原；

步驟2：初始化種群.搜尋記憶抗體,若無則隨機(jī)產(chǎn)生；

步驟3：提取疫苗；

步驟4：計(jì)算抗體親和力和適應(yīng)度；

步驟5：判斷終止條件.到了無法改善解的時(shí)候,終止；

步驟6：克隆增殖；

步驟7：克隆變異.多重高頻變異；

步驟8：克隆選擇.還是根據(jù)親和力進(jìn)行選擇；

步驟9：接種疫苗；

步驟10：免疫選擇；

步驟11：更新種群.

2 免疫遺傳算法在物流配送問題中的應(yīng)用

2.1 問題描述

本文所描述的VRP問題為：在各種能力約束的條件下,使得運(yùn)輸成本最小化.約束條件有：車輛的載重量一定,車輛的行駛距離一定,車輛只允許有一條行駛路線等.

研究無時(shí)間限制閉環(huán)式問題,該問題的可描述為

上述所用符號說明如下：

K為配送車輛數(shù)目；L為需求點(diǎn)總數(shù)；Dk為第k輛車的最大行駛距離；Qk為第k輛車的最大載重量（k=1,2,…,K）；qi為需求點(diǎn)i的貨物需求量（i=1,2,…,L）；dij為需求點(diǎn)i到j(luò)的距離（i=1,2,…,L；j=1,2,…, L）；d0j為配送中心到各需求點(diǎn)的距離（j=1,2,…,L）；nk為第k輛汽車配送的需求點(diǎn)數(shù)（nk=0表示未使用第k輛汽車）；Rk為第k條路徑；rki為需求點(diǎn)在路徑k中的順序?yàn)閕（不包括配送中心）,令rk0=0表示配送中心.

式（1）至（8）為目標(biāo)函數(shù)和各種能力約束條件.

2.2 克隆選擇在問題中的應(yīng)用

在免疫遺傳算法的基礎(chǔ)上加上了克隆算子,增加了局部搜索能力、有效保證了種群的多樣性,并避免了算法過早的收斂.下面就物流配送問題,給出了克隆算子的構(gòu)造方法.

2.2.1 克隆增殖下面是克隆增殖的表達(dá)式：

Θ反映了抗體i與其他抗體的親和力,這里將其簡單定義為：

Nc是抗體群總的克隆規(guī)模,顯然,in（tx）表示取大于x的最小的整數(shù).克隆過后,種群變?yōu)椋?/p>

其中：

這里采取的變異,主要是為了保留抗體的原始信息,而不是作用到A∈ A'

多重高頻變異.例如抗體123456789,對被選擇的基因段進(jìn)行倒位操作,得到了128765439,并對此倒位操作進(jìn)行多次.

2.2.3 克隆選擇克隆操作之后,在子種群中選擇基因比較好的,保留下來.

則表明變異后的抗體Bi基因比較好,從而用此抗體來更新,否則,保留變異前的抗體Ai.

2.3 數(shù)值實(shí)驗(yàn)與分析

假設(shè)有8個(gè)需求點(diǎn)和一個(gè)配送中心的配送系統(tǒng),各個(gè)需求點(diǎn)的需求為di（i=l,2,…,8）,配送中心用兩輛車（載重量為8）配送,需求點(diǎn)與配送中心的距離如表1所示.要求優(yōu)化配送線路,使得配送成本最小化.

用基于克隆選擇的免疫遺傳算法對上述問題進(jìn)行求解,變異率如果太小,則產(chǎn)生新的染色體概率小,導(dǎo)致不成熟的收斂；太大,可能使優(yōu)秀染色體的破壞機(jī)會(huì)增加,甚至不能收斂,應(yīng)多次實(shí)驗(yàn)調(diào)整或者采用自適應(yīng)方法調(diào)整變異率通過上機(jī)運(yùn)算,得到的線路有：

路線1：0-＞4-＞2-＞6-＞0

路線2：0-＞3-＞7-＞5-＞8-＞1-＞0

運(yùn)輸總距離=83.5

通過分析,此方案是此問題的一個(gè)可行解.

表1 顧客間距離以及顧客需求Tab.1 Distance between the customerand Customerneeds

3 結(jié)論

本文針對物流配送中的路徑最優(yōu)化問題,提出了利用免疫算法求解該問題時(shí)存在的一些不足,通過改進(jìn)此算法,增加了克隆選擇的機(jī)制,有效的彌補(bǔ)了免疫遺傳算法的不足.并通過較小規(guī)模的物流配送問題的仿真分析,得到了較好的效果.

[1]李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社,2001.

[2]郎茂樣.流配送車輛調(diào)度問題的模型和算法研究[D].北京：北方交通大學(xué),2001.

[3]蔡希賢,夏士智.物流合理化的數(shù)量方法[M].武漢：華中工學(xué)院出版社,1985.

[4]劉朝暉,范榮華,萬毅.物資管理系統(tǒng)工程[M].北京：中國物資出版社,1997.

[5]馬力強(qiáng).關(guān)于我國現(xiàn)代物流發(fā)展的思考[J].交通運(yùn)輸系統(tǒng)工程與信息,2000（1）：13-15.

[6]李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社,2001.

[7]李大衛(wèi),王莉,王夢光.一個(gè)求解帶有時(shí)間窗口約束的車輛路徑問題的啟發(fā)式算法[J].系統(tǒng)工程,1998（4）：20-24.

[8]張震.城市貨運(yùn)汽車營運(yùn)組織最優(yōu)化的理論與方法[J].管理工程學(xué)報(bào),1995,9（3）：143-152.

[9]蔡延光,錢積新,孫優(yōu)賢.多重運(yùn)輸調(diào)度問題基于雙表的并行表搜索算法[J].系統(tǒng)工程理論與實(shí)踐,1998,18（1l）：20-26.

[10]蔡延光,錢積新,孫優(yōu)賢.多重運(yùn)輸調(diào)度問題的模擬退火算法[J].系統(tǒng)工程理論與實(shí)踐,1995,18（10）：11-15.

[11]劉浩,袁健,盧厚清.兩種類型車輛隨機(jī)需求路由問題[J].南京航空航天大學(xué)學(xué)報(bào),2001,33（2）：155-158.

[12]張濤,王夢光,楊建夏.不確定計(jì)劃數(shù)的軋制批量計(jì)劃的模型和算法[J].系統(tǒng)工程學(xué)報(bào),2000,15（1）：54-60.

[13]王莉.CIMS下的熱軋生產(chǎn)批量計(jì)劃的數(shù)學(xué)模型及解法[J].鞍山師范學(xué)院學(xué)報(bào),1999,1（3）：17-22.

[14]袁健,劉晉.隨機(jī)需求情形VRP的Hopfield神經(jīng)網(wǎng)絡(luò)解法[J].南京航空航天大學(xué)學(xué)報(bào),2000,32（5）：579-585.

[15]郭耀煌,李軍.車輛優(yōu)化調(diào)度[M].成都：成都科技大學(xué)出版社,1994.

[16]周雙貴.基于MATLAB的車輛路徑系統(tǒng)研究[D].北京：北方交通大學(xué),2001.

（責(zé)任編輯：盧奇）

Application of immune clonal genetic algorithm on logistics and distribution

Chen Lin1,Yao Hongliang2
（1.DepartmentofElectronic Information,AnhuiFinance&Trade VocationalCollege,Hefei230601, China；2.College ofComputer Science and Information Technology,HefeiUniversity ofTechnology, Hefei230009,China）

This paper puts forward to an improved algorithm based on clonal selection to solve the local search ability inadequacy of Immune Genetic Algorithm appeared in the Physical distribution and algorithm of convergence problem early．The introduction of cloning proliferation operator,the high frequency variation and clonal selection operator increase the diversity of population and improve the local search ability effectively as well as avoiding the algorithm convergence．The efficiency of the algorithm will be proved by demonstration and analysis of logistics and distribution．

physical distribution；clonal proliferation；clonal selection；immune genetic algorithm

TP18

A

1008-7516（2012）05-0070-05

10．3969/j．issn．1008-7516．2012．05．017

2012-07-16

陳林（1980-）,男,安徽合肥人,碩士,助教．主要從事軟件開發(fā)和數(shù)據(jù)挖掘研究．